"Floodfill Mset: Interior"

**Results**Level M17J15 is finished and gave a lower bound on the area: 116944698 * (4 / 131072)^2 + 7*PI/16 >=

**1.48336**.

This is currently my computational limit: the next level M18 would need about 80 GB of memory and approx. 720 hours.

It was nice to see (first image, marked "I", red arrows), that the algorithm finds the cardioids of some minibrots.

Total computation time starting from scratch was 91 hours, with ongoing optimizations employed at each refinement step, the last one using (my first attempt with) OpenMP to analyze dynamically up to four Julia sets at once.

Refinement now scales about 8-fold, so it is less exponential as the previous, non-flood-filling algorithm (10-fold there). Using a classic 2x2 refinement is still the best option, both timewise and area-increase-wise.

The compressed file below (extension changed to '.zip' to upload it, it's actually '.7z', so one might need to rename it) contains a 128k resolution Mandelbrot image (16 GB, 8-bit bitmap), that can be used as a trustworthy filter. The lower left corner pixel represents the complex c interval [-2..-2+d] x [-2..-2+d]*i with d=4/2

^{17}. Black is definite interior, gray and white are for illustration purposes.

Up to M16J14 ~730000 sets were analyzed of which ~424000 were deemed interior and an additional ~930000 were floodfilled (I did not record numbers for the last step as it was performed in several batches)..

I will release the code when the documentation is ready.

Two plausibility checks were performed on the final image:

- I used LaserBlaster's 8k Mset, upscaled it trustworthily to 128k and compared my image to it: if one image has a definite color, the other has the same or is gray.
- I randomly chose 25 black Mset pixels that have a gray neighbour (omitting main cardioid and period-2) and computed the full interval Julia sets. All showed interior at L15R2.

**Algorithmic chain** (second image)

(Green Mset pixels have at least one corner in the main cardioid or the period-2 bulb and are internally used as a wall so those two bulbs are not analyzed).

Point-sampling part1. I start with a point-sampled Mset and inscribed squares (blue) that gives me a list of centers and widths values. The hyperbolic components usually have more than 1 square, but that's fine for my purpose.

True shape part from here on2. I start with mostly a gray image ([-2..1] x [-1.5..1.5]*i is gray, the outside is white) and analyze the c-intervals of the inscribed squares' rectangular boundary (starting with a square half the inscribed size, then 1/4th, then 1/8th). If a rectangular surrounding is analyzed to be completely black, the interior is filled (brownish). I only use hc's whose inscribed region is at least 16 pixels in width in the current Mset resolution (empirical value).

3. I extend all black areas found by analyzing gray Mset pixels that have a distance of 3 to a black one (3 gives a speed-up of 10% over distance=2), which resulted in black shell-like layers, stopping when no longer change in the image occurs. This step ends with non-black-turnable pixels (yellow).

4. Since the shells are often leaky and cannot directly be floodfilled, I introduce a sparse grid around the hc and analyze the c intervals lying on the grid lines only, in an outward-from-the-center fashion. A direction is aborted when the first gray pixel cannot be turned black. This results in a sectorized shell shape.

5. Every gray pixel that has a black neighbour is now used as a seed for flood-filling with black. If it leaks by leaving the screen or encountering a white pixel (leaked pixels and their paths are marked red), those visited pixels are marked as ROLLBACK and also used as a leak indicator.

6. The final image where all intermediate colors are reverted back to gray.

**Notes**There is potential for an increase in interior Mset pixels. At distance=3 there might be points in distance 1 or 2 around the hc's regions that contain black pixels as well as some unclosed small regions which could be rendered flood-fillable by carefully analyzing some pixels. A quick estimate (counting all gray/black pairs times 3) showed, that the increase in area is less then 0.0007, so I did not implement any further action here (see first image, marked "III")

For speed reasons normally the gridding (algorithmic step 4) is only applied if the hc's center has already been judged as interior (by a previous step or refinement). Here at the highest possible level, I performed gridding at every hc, which resulted in the emergence of some small seed regions (first image, marked "II" and blue arrows in 'I'). As gridding uses a width of 1/32th of the inscribed square, whereas the hc center method (step 2) uses at least 1/8th for speed-up, I hoped to get some more black emerged. Those grid-like regions would be delt with in the next refinement level by the shell extension.

As I optimized the program during computation in terms of algorithmic order, distance etc., the final image here most probably will look different from what would be obtained if I now were to restart the whole computational process with the current fastest routines alone.