Julia sets: True shape and escape time

  • 214 Replies
  • 6971 Views

0 Members and 1 Guest are viewing this topic.

Offline Laser Blaster

  • *
  • Fractal Phenom
  • ****
  • Posts: 52
« Reply #195 on: March 25, 2020, 04:21:16 AM »
Both of those libraries have a dependency on MPFR. And MPFR itself has a dependency on GMP (and a couple other libs).

I'm trying to get MPFR to work. I'm using MinGW-w64 on Windows 64-bit. This github has pre-built .lib files, but doesn't come with any header files. I tried grabbing the standard header files gmp.h and mpfr.h off of Github, but that didn't work. GMP includes a file "features.h" which I don't have in my install. I am probably not smart enough to build MPFR myself (I always run into a ton of issues whenever I try to build a library with MinGW-w64). So I guess I give up.

Right now I'm writing a custom arbitrary precision type using inline assembly for the performance-critical parts.

Offline claude

  • *
  • 3f
  • ******
  • Posts: 1373
    • mathr.co.uk
« Reply #196 on: March 25, 2020, 06:14:55 AM »
try msys instead of mingw? https://github.com/msys2/msys2/wiki/Using-packages

EDIT if it's anything like debian or redhat, the headers are in separate packages.  try intalling gmp-dev or gmp-devel or similar
« Last Edit: March 25, 2020, 06:38:12 AM by claude, Reason: dev »

Offline marcm200

  • *
  • Fractal Frankfurter
  • *
  • Posts: 626
« Reply #197 on: March 25, 2020, 09:08:23 AM »
Right now I'm writing a custom arbitrary precision type using inline assembly for the performance-critical parts.
Inline assembly - bonus point!

_____________________

Lower bound on mset area now at: 1.46688.

Usually mset and Julia set images have the same screen width, so the current best mset area bound was derived from M13J13 (8192 image width).

Here I tried different values for M and J, the best (total time 102 min) I found was M15J13 without subdivision, which resulted in the above area (with main cardioid and period-2 bulb as exactly 7*PI/16 from post #184).

M16J13 should be possible (it still scales around 10-fold), I'm attempting this in several batches.

Optimization idea (extending LaserBlaster's hierarchical idea from #141):

The image below shows part of an M12J12 image, black is the M11J11 identified interior, blue the M12J12 new one. It is by visual inspection several layers thick.

If I could derive the position of the outer layers and only analyze those gray pixels, I could then - if a black ring is developped, flood-fill the interior with black completely, thereby omitting quite a number of gray pixels to test.

First idea here is: Instead of analyzing gray if it has a black neighbour, I'm focusing on gray that has a black neighbour in a vertical or horizontal distance of 2 and not nearer. Then after a sweep over the image, I'm looking for a closed ring and flood-fill.

If this turns out to be beneficial timewise, one might even jump refinement levels, e.g. only computing every 2nd one and use a greater distance than 2.

And ultimately I plan on using a point-sampled Mset to determine the size of some simple geometric shape within a bulb (and not just the center as I'm doing now), and then in kind of a binary fashion start analyzing gray from outwards towards the hyperbolic center, e.g. from 4 opposite directions until every one has found a black pixel, and then on a straight line closing those points to a ring.

Offline Laser Blaster

  • *
  • Fractal Phenom
  • ****
  • Posts: 52
« Reply #198 on: March 25, 2020, 01:02:06 PM »
@marcm200

Good job on the new bound. And those are some great optimization ideas!

Building on your idea, I thought of a way to directly find the boundary of a black region. First find a single adjacent black/gray pair on the edge of a bulb. Then recursively check every pixel that has both a black neighbor and a gray neighbor (in it's 3x3 box neighborhood). This way you can "walk the boundary" of the black region without ever straying more than 1 pixel from the boundary.

I'll work on my exterior detection method using the DE, and you can continue refining your interior detection. Then we can just combine the resulting images.

Offline marcm200

  • *
  • Fractal Frankfurter
  • *
  • Posts: 626
« Reply #199 on: March 26, 2020, 02:25:19 PM »
I'll work on my exterior detection method using the DE, and you can continue refining your interior detection. Then we can just combine the resulting images.
Sounds good to me.

"Floodfill-Mset"

Currently I do a 3-step approach:

1. "Initial": Analyze small rectangles around (estimated) hyperbolic centers and try to floodfill them (decreasing size of ractangle).

2. "Enlarge": Gray Mset pixels with a black neighbour at distance 2 are analyzed with repeated sweeps over the image. If no more change occurs, one floodfill round is performed.

3. "Connect" (not yet implemented): The cropped image below (lower right) shows, that due to the distance 2 there are regions that leak and cannot be floodfilled ("holes"), i.e. I need to close them. I personally can see where to try, but my computer so far cannot.

Things to attempt:

  • Do nothing. As the holes are gray pixels that have black neighbours at odd pixel distances, those will be resolved in a higher refinement level as a gray pixel turns into 2x2 new gray pixels, where then (at least some) have a distance of 2 to the next black and will be analyzed.
  • Brute-force analyze all black-gray-black pixel streaks.
  • Do a randomized brute-force version (e.g. analyzing 5% and then attempt a floodfill. Repeat as long as change occurs) - my current favourite.
  • Use LaserBlaster's "walking the boundary" method with an additional distance measure to the hyperbolic center, in case the outermost boundary cannot be closed and I have to go inward.

So far, results are promising:

  • floodfill/M14J12 (with "holes") has an area of 0.074 (without cardioid and 2-bulb), the full analyze attempt from the last days gave 0.078, so not too far off.
  • Times are identical (14-15 min), which I think is acceptable for a first, non-optimized implementation.

Currently I perform the usual refinements, but it might be advantageous here to start maybe directly at the desired resolution and use a rectangle around the hc's that is related to the size of the bulb/minibrot expected there instead of a fixed-size rectangle.

The repeated analyis of rectangles at different refinement levels that still are too big around a hc leads to quite a bit of unnecessary computational effort (the floodfill methods needs about 15% more Julia set computations, quite the opposite of what is to be expected from flood-filling. So I have some work to do there.

I hope that way I can floodfill half or more of the period-3 bulbs by just analyzing a suitable rectangle around its centers.

EDIT Just realized I was thinking way too complicated here. Most of those gray pixels are perfect candidates for the "8 neighbours black => center black" hierarchical rule.

« Last Edit: March 26, 2020, 04:18:06 PM by marcm200, Reason: Simpler idea »

Offline marcm200

  • *
  • Fractal Frankfurter
  • *
  • Posts: 626
« Reply #200 on: March 27, 2020, 09:03:59 AM »
"Lured out by mvf"

In #131 I posted a cubic Julia set with 2 period-54 cycle, where only one has been detected and the other was expected at L21/R2.

I tried this again with the mean-value-form and now the new predictor found the 2nd cycle at L20/R2. So I used its output as interior seed regions and enlarged them a bit. Some are still very small (red arrows) and would vanish in an additional downscaling step (here 128-fold).

As the mvf does not suffer from degree explosion as the 2-iterate and is faster, the mean-value-form is now the principal IA formulation I use.

Offline Laser Blaster

  • *
  • Fractal Phenom
  • ****
  • Posts: 52
« Reply #201 on: March 28, 2020, 03:13:06 AM »
try msys instead of mingw? https://github.com/msys2/msys2/wiki/Using-packages

EDIT if it's anything like debian or redhat, the headers are in separate packages.  try intalling gmp-dev or gmp-devel or similar
I finally tried MSYS 2, and wow, it's a much better experience! The package manager does all the work for me.

I was able to get MPFR installed, so you should see some trustworthy M-set exterior images from me soon.

Offline Laser Blaster

  • *
  • Fractal Phenom
  • ****
  • Posts: 52
« Reply #202 on: March 30, 2020, 08:45:33 AM »
Here is an 8K (cropped) image of the exterior with the new trustworthy DE method I've been working on. It rendered in 15 minutes on 8 threads, which is an improvement of more than 2 orders of magnitude over my previous method. The result is much less conservative than the pixel-graph method (which is good), and it is consistent with previous results (no pixels are white that were black with the old method). I will soon post more information on my method, plus proofs of my bounds on the potential function.

Offline Laser Blaster

  • *
  • Fractal Phenom
  • ****
  • Posts: 52
« Reply #203 on: March 30, 2020, 09:00:59 AM »
This gives a new upper bound (on the area of the M-set of) 1.70941 (rounded up), which is still not as good as the best know bound of 1.68288.  However, this method is so fast that I should be able to render at much higher resolutions, so I expect I'll be able to improve on the current best bound.

I'm currently using MPFR with 253 bits of mantissa for calculations. My custom floating point type is 4x faster at the same precision (I think MPFR is optimized for thousands of bits, not hundreds), but currently only implements addition multiplication, and subtraction (I need division and transcendental functions to compute the DE). Once I switch over to a custom BigFloat, I should see a factor of 4 speedup, and if I implement fixed-point arithmetic, I might get even more speed. So, once I optimize everything, I should easily be able to reach 128K resolution, and maybe even higher than that.

Offline marcm200

  • *
  • Fractal Frankfurter
  • *
  • Posts: 626
« Reply #204 on: March 30, 2020, 09:24:57 AM »
It rendered in 15 minutes on 8 threads, which is an improvement of more than 2 orders of magnitude over my previous method.
2 orders of magnitude - great!
(I'm happy in my interior program when I reach a speed-up of a factor of 2 :)

I expect my interior at M17J15 to be finished by tomorrow (judging from how the sweeps take less and less time), then we can combine the results to a huge 128k Mset image.


Offline marcm200

  • *
  • Fractal Frankfurter
  • *
  • Posts: 626
« Reply #205 on: March 31, 2020, 02:29:09 PM »
"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/217. 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 part
1. 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 on
2. 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.

Offline Laser Blaster

  • *
  • Fractal Phenom
  • ****
  • Posts: 52
« Reply #206 on: March 31, 2020, 11:00:33 PM »
128K res! Great job.

I've optimized my exterior computation program enough that 8K res executes in 17.7 seconds at the expense of making results slightly more conservative - 47 pixels are now gray that were previously white. 128K res should complete in under two hours. However I need to implement a tiling mechanism in order to support resolutions that high (currently I store an array of doubles for the entire image, which are rounded-down trustworthy DE values). I also need to implement indexed color .bmp file output, as RGBA8888 at that resolution exceeds the .bmp file size limit of 4GB. You may not see 128K from me until tomorrow.

Now I have to wonder if trustworthy DE could somehow be extended to the interior of the M-set. My feeling is no, as interior DE is much more finicky and requires calculating the period of the attracting cycle (which seems like it would require a pixel-graph type approach to do reliably anyway).

Offline Laser Blaster

  • *
  • Fractal Phenom
  • ****
  • Posts: 52
« Reply #207 on: April 01, 2020, 06:05:34 AM »
@marcm200

When I try to open your .zip file, I get an error: "Windows cannot open the folder. The compressed (zipped) folder is invalid."

I'm starting to make larger renders now, but no program I have is able to view a 32K bmp. VLIV (http://delhoume.frederic.free.fr/vliv.htm) is able to view very large images, but it seems to only work with TIFF images. The website https://easyzoom.com/ allows you to upload very large images and zoom into them online, but it doesn't support bmp.

Maybe I have to switch to outputting TIFF.

Offline marcm200

  • *
  • Fractal Frankfurter
  • *
  • Posts: 626
« Reply #208 on: April 01, 2020, 10:23:16 AM »
@ LaserBlaster: I use Windows 10 64bit, 7-zip portable 18.06 x64 to open the compressed file after renaming the extension to '.7z' (works with '.zip' as well just with a warning - so I guess when using Windows to unzip it, that might assume the "wrong" compression algorithm and not detect the correct one?) and IrfanView 4.52 64 bit to view the 16 GB bitmap.

The bitmap is 8-bit with a 256 entry color palette, created by my own custom-made Charmap struct (will be released with the general code).

When I first started on my Win XP 32-bit computer I saved those huge images as tiles not exceeding 4 GB, but discarded that when I switched to Windows 10. I could however reactivate this method if it is more convenient.

Offline Laser Blaster

  • *
  • Fractal Phenom
  • ****
  • Posts: 52
« Reply #209 on: April 01, 2020, 12:26:09 PM »
@ LaserBlaster: I use Windows 10 64bit, 7-zip portable 18.06 x64 to open the compressed file after renaming the extension to '.7z' (works with '.zip' as well just with a warning - so I guess when using Windows to unzip it, that might assume the "wrong" compression algorithm and not detect the correct one?) and IrfanView 4.52 64 bit to view the 16 GB bitmap.

The bitmap is 8-bit with a 256 entry color palette, created by my own custom-made Charmap struct (will be released with the general code).

When I first started on my Win XP 32-bit computer I saved those huge images as tiles not exceeding 4 GB, but discarded that when I switched to Windows 10. I could however reactivate this method if it is more convenient.
Ok, I was able to extract the file using 7zip.

Technically a conforming .bmp file can't exceed 4GB. It has a "file size" field in the header, and this field is a 32-bit unsigned integer that stores the total file size in bytes. PNG supports much larger sizes I believe.

There are also no programs I could find that can view a 32K .bmp image (this is a limitation of those programs, not of the .bmp format itself). So I find myself unable to view my own 32K render, at least until I write my own .bmp viewer program.


clip
3d Julia sets: True shape

Started by marcm200 on Image Threads

31 Replies
962 Views
Last post January 20, 2020, 11:42:23 AM
by marcm200
clip
True-shape based C++ oracle for the int-/exterior of Julia sets

Started by marcm200 on Programming

6 Replies
311 Views
Last post August 23, 2019, 10:47:10 AM
by marcm200
clip
3D M-set for tricomplex numbers: Escape time and shape change?

Started by marcm200 on Fractal Mathematics And New Theories

2 Replies
243 Views
Last post May 04, 2019, 09:58:37 PM
by marcm200
xx
True shape/IA 2D/3D Julia set source code

Started by marcm200 on Programming

13 Replies
608 Views
Last post March 10, 2020, 08:35:44 PM
by marcm200
clip
Escape Time Blur

Started by AlexH on Share a fractal

0 Replies
404 Views
Last post August 15, 2018, 05:42:06 AM
by AlexH