|
reesej2
Guest
|
 |
« on: March 29, 2010, 03:58:32 AM » |
|
Okay, I've been perusing the forums while waiting for my latest deep zoom of the Mandelbrot to render, and I've found a lot of awesome stuff, but not what I was looking for: ideas on how to optimize calculation of the EXTERIOR of the M-Set. I've seen some brilliant stuff (thanks Pauldelbrot et al.) for eliminating chunks that are definitely inside the set, but what I'm rendering now has no points IN the set, but lots close to it. So, any ideas? I'm using C, with GMP for arbitrary precision arithmetic.
I've already implemented a couple of basic things (like saving Re(z)^2 and Im(z)^2 for bound calculations) and I have a couple ideas (like calculating two or four iterations in a row without stopping to check in between) but so far nothing that doesn't tend to cause unacceptable losses in accuracy.
Any ideas?
|
|
|
|
|
Logged
|
|
|
|
|
Timeroot
|
|
« Reply #1 on: March 29, 2010, 06:59:05 AM » |
|
A while ago I tried to get something going with alternative bailout methods... sadly, it never really took off... I did end up having a couple of weird methods which worked, though... if used, say, once every 5 iterations, they might be of some help. Really, the idea is that anything outside of the anti-buddhabrot can be eliminated. The problem is that it is, well, fractal, so you can't really "cut off" everything around it without using excessive computation. You can always try epsilon-cross methods, I think they can do useful stuff... something like "if Re(z)<(1/(abs(Imag(z))-0.5)) then bailout" or something.
|
|
|
|
|
Logged
|
Someday, man will understand primary theory; how every aspect of our universe has come about. Then we will describe all of physics, build a complete understanding of genetic engineering, catalog all planets, and find intelligent life. And then we'll just puzzle over fractals for eternity.
|
|
|
|
reesej2
Guest
|
|
« Reply #2 on: March 29, 2010, 07:21:54 AM » |
|
Yeah, I read that, I figured it would be a good idea to open a topic with a less specific title  The bailout adjustments seem promising, but the inconvenient thing is that I would think that it would tend to mess with the iteration count and therefore the smooth coloring procedure. Just a thought--are there any holes in the Buddhabrot itself? If there are, then we can simplify calculations by stopping the moment a point enters one of those regions. Or if there aren't, could there be conditional holes? Like, are there places that points with initially positive imaginary components never go? And now I'm meandering a bit... I wonder if there's any way to adjust for modified bailout. Something like "If calculation terminated early due to reaching such-and-such a bailout condition, then add x to the iteration count." |
|
|
|
|
Logged
|
|
|
|
hobold
Fractal Bachius
Posts: 573
|
|
« Reply #3 on: March 29, 2010, 04:29:30 PM » |
|
Would a bog standard level set rendering suffice? For exteriors coloured with just the iteration number, it is possible to skip computation in the flat areas. This can be done either with boundary tracing methods, or with a quadtree (or Kd-tree). These methods are an approximation based on pixel resolution, but they are backed up by the theory. Rendering errors are extremely unlikely to ever affect more than a few pixels.
|
|
|
|
|
Logged
|
|
|
|
|
reesej2
Guest
|
|
« Reply #4 on: March 29, 2010, 07:46:37 PM » |
|
Yeah, those would be helpful for certain parts (though they'd be fairly likely to cut off fine threads) but the particular image I'm rendering has very little in the way of flat areas. I need to implement boundary tracing, though, that seems very very promising...
|
|
|
|
|
Logged
|
|
|
|
|
Timeroot
|
|
« Reply #5 on: March 29, 2010, 08:06:31 PM » |
|
How would you implement boundary tracing? Are you talking about a Fractint-esque style, where it "carves out" the level sets of iteration? That way you also won't be able to use any sort of smoothed iteration...
I would also like to mention that, at deep zooms, any "weird" bailouts begin to blend in perfectly. This might indicate that they stop being useful, but in any case they stop messing with the coloring.
|
|
|
|
|
Logged
|
Someday, man will understand primary theory; how every aspect of our universe has come about. Then we will describe all of physics, build a complete understanding of genetic engineering, catalog all planets, and find intelligent life. And then we'll just puzzle over fractals for eternity.
|
|
|
hobold
Fractal Bachius
Posts: 573
|
|
« Reply #6 on: March 29, 2010, 09:50:14 PM » |
|
The boundary trace methods were popular in the 8 bit days, when floating point arithmetic was implemented in software, and pixel operations could be done purely with cheap integer arithmetic.
The quad/Kd-tree method requires less complex logic, and is probably more suitable with the faster arithmetic these days. The Kd version works like this:
1. Compute top and bottom rows, leftmost and rightmost columns.
2. If all pixels of that whole frame have the same identical number of iterations, fill the rectangle and return.
3. Otherwise split the rectangle in two and compute one single row/column of pixels at the border. Recurse into both halves. (e.g. split the longer edges at midpoint.)
This method fails only if the initial rectangle contains all of the Mandelbrot set. Or, more generally speaking, it fails only when the rectangle contains a disconnected part of the set, which cannot happen for any subset, because the Mandelbrot set is connected.
Theoretically, i.e. if you would not just sample the rectangle border on a pixel grid, but could compute the iteration of all the infinitely many points, then the method would be exact rather than an approximation. I like the method because it works automatically for the interior of the set, too, with no need for further special cases. And the "divide and conquer" type of algorithms can be parallelized naturally.
I have implemented this method in several simple Mandelbrot zoomers over the years, and have yet to encounter an image where it produced visible artifacts. It doesn't cut off antennas, because there is always a bit of a canyon around those infinitely thin structures. So even if no sample point can hit the actual line, there is usually a few pixels with different iteration counts to trigger a subdivision. Only when the rectangle gets very small, like 4x4 or 2x2 pixels, does the probability for errors increase to non-negligible values.
The biggest drawback of the method is that it only works in "boring" areas of the image. Thus experienced Mandelbrot explorers, who tend to zoom into richer collections of ornamental structures, will see less of a speedup.
|
|
|
|
|
Logged
|
|
|
|
|
Timeroot
|
|
« Reply #7 on: March 29, 2010, 11:02:54 PM » |
|
I suppose that if you're using smoothed iterations, you could do something similar by measuring the difference in color between two successive pixels along the boundary. If this difference is too great, then it should be subdivided; if over the entire rectangle it's only a shallow slope, though, it would be filled in with some interpolation. This has mathematical theory to back it up, too: the slope is actually a pretty close estimate to the derivative of the function, so by just using this value you could get a fairly accurate DE.
Perhaps this would actually be the best way to do it: Calculate the DE at each of the corner points. If the DE is greater than the size of, say, 0.6*(diagonal of rectangle), then subdivide at the middle; otherwise, fill the rectangle with interpolation from the borders.
Has anyone ever tried this? I think it might give great speed-ups, even at relatively deep zooms.
|
|
|
|
|
Logged
|
Someday, man will understand primary theory; how every aspect of our universe has come about. Then we will describe all of physics, build a complete understanding of genetic engineering, catalog all planets, and find intelligent life. And then we'll just puzzle over fractals for eternity.
|
|
|
|
reesej2
Guest
|
|
« Reply #8 on: March 30, 2010, 01:07:00 AM » |
|
Surely you mean LESS than 0.6 times the diagonal? I see the idea here... you'd get a lot of speedup unless, of course, everything's close to the set. Which would be basically whenever there's a lot of detail in the image. I like the idea, though... seems promising...
|
|
|
|
|
Logged
|
|
|
|
|
Timeroot
|
|
« Reply #9 on: March 30, 2010, 03:05:54 AM » |
|
Yeah, less.  It's true that it won't work while you're still close to the set, but if you're rendering at a high resolution, it's almost certain that you will eventually subdivide at some point into a relatively open area. I've been thinking maybe a more efficient way would be checking just the center of the rectangle for being close to the set. It would be a lot more efficient when it come to eliminating areas. To double check, use directional estimation, take the center of the side that it points to, and check its Distance Estimate. Assuming it's far enough away, compute the border and extrapolate. By the way, I think I've got a better idea of how to extrapolate the colors; I'm pretty sure that you can compute the direction of a level set of smoothed iteration - should be a fun exercise. Then maybe also compute the quadratic component, and you can get something like a Bezier curve. This is proving to be a very interesting idea, extrapolating from the borders... and it could give rise to very large speed boosts, I think... |
|
|
|
|
Logged
|
Someday, man will understand primary theory; how every aspect of our universe has come about. Then we will describe all of physics, build a complete understanding of genetic engineering, catalog all planets, and find intelligent life. And then we'll just puzzle over fractals for eternity.
|
|
|
|
reesej2
Guest
|
|
« Reply #10 on: March 30, 2010, 04:11:27 AM » |
|
Oooh, the center sounds good... also, for high-detail images, maybe start the subdivisions at smaller rectangles? So that you don't waste calculations on large parts. Also, bear in mind that it's very possible that the center happens to land on a minibrot well below the size of a pixel--so maybe several central pixels, very close together, so that details too small to see are ignored?
|
|
|
|
|
Logged
|
|
|
|
|
Botond Kósa
|
|
« Reply #11 on: March 30, 2010, 05:12:11 PM » |
|
Hi guys, I am new to this forum, but I have also been working on my own Mandelbrot generator for 5 years. I have implemented the interpolating method to speed up the calculation of monotonic areas. My algorithm works like this: 1. Check the bounds of the rectangle for monotonicity. If the parallel bounds are monotonic in the same direction, go to step 2. Else subdivide the rectangle. 2. For each monotonic bounding line, calculate the minimum and maximum of the differences of subsequent values. If abs(max)<abs(min)*threshold, got to step 3. Else subdivide the rectangle. (With lower thresholds the interpolation will be more accurate, but more subdivisions will be required. I use a threshold of 2) 3. For each inner pixel of the rectangle, compute the interpolated value of the four projected boundary pixels. For the interpolation use an average of the weighted boundary values. I experimented with several weights and averages. Weights: 1. Use the reciprocal of the distance from the boundary 2. Use the distance to the opposite boundary Averages: 1. Arithmetic mean 2. Geometric mean 3. Harmonic mean 4. Quadratic mean For a specific calculated image, the difference between the different weights and averages is very subtle and hardly noticeable, assuming the monotonicity threshold is kept low. The best method I found to quantify the accuracy of the different interpolations is to compress the image, and compare the compressed sizes (in bytes). The method with the highest compression ratio will be the best. A few words about the compression I use: My program is written in Java. I store the calculated iteration values for the pixels in an array of 32-bit floats. I convert the float values to int using Java's Float.floatToIntBits() method, which creates an int that has the same bit pattern as the float. I then split the int into one 8-bit and one 24-bit chunk (roughly the float's exponent and mantissa), and filter each row's exponent and mantissa values using a differential filter. Then I split the 24-bit mantissa into 3 bytes, create an array of bytes with width*height*4 values, and copy the following values into it: 1. The filtered exponent values 2. The first bytes of the filtered mantissa values 3. The second bytes of the filtered mantissa values 4. The third bytes of the filtered mantissa values Finally I compress the whole array with java.util.zip. Based on my measurements, for the majority of images the best weighting method is #2 (by far) and the best averaging method is #3 harmonic mean. |
|
|
|
« Last Edit: March 31, 2010, 09:46:46 AM by Botond Kósa »
|
Logged
|
|
|
|
|
Botond Kósa
|
|
« Reply #12 on: March 30, 2010, 05:23:23 PM » |
|
Another benefit of the interpolating method is that it scales well when using oversampling, because monotonic areas will be larger. The effect is similar to adaptive anti-aliasing. One example created with my application:
Original image:
Size: 640x480
Total pixels: 307200
Computed pixels: 158101 (51.47%)
4x4 oversampled image:
Size: 2560x1920
Total pixels: 4915200
Computed pixels: 1710370 (34.80%)
So despite the total pixel count being 16 times higher, the calculated pixel count is only 10.8 times higher.
|
|
|
|
|
Logged
|
|
|
|
|
Nahee_Enterprises
|
|
« Reply #13 on: March 30, 2010, 05:33:32 PM » |
|
Hi guys, I am new to this forum, but I have also been working on my
own Mandelbrot generator for 5 years. My program is written in Java. Greetings, and Welcome to this particular Forum !!!  If you got any images to share, please upload or give a link. And if you would like beta testers for your program, there are many here that would give it a whirl. |
|
|
|
|
Logged
|
|
|
|
|
Timeroot
|
|
« Reply #14 on: March 30, 2010, 06:00:45 PM » |
|
@reesej: But DE still wouldn't be able to, very consistently, tell us the size of the object. (That might be interesting to try, though.) And if any part of the set is within the rectangle, the extrapolation from the sides could end up being very inaccurate. By the way, I think I got the formula for the angle of the level sets at any given point: It's the exact same calculations as DE to get the derivative, the only difference being the final result; in leiu of 2*cabs(z)*ln(cabs(z))/cabs(zDeriv) one would use (I think - need to check my maths again) or just if you want the field lines. I'm very excited about these formulas, and I think they might produce pleasing coloring alogrithms! Just to check that they work, would someone mind trying them for me? Just copy the code for the DE formula, and change the final: part to arg(z/zDeriv).  @kbotond: I would really like to see your program? What is it called? And, one question, did you try using log(abs(max))<log(abs(min))*threshold? Or, I suppose more efficiently, abs(max)<abs(min)^threshold? It sounds like a very interesting technique you're using... |
|
|
|
« Last Edit: March 30, 2010, 06:06:39 PM by Timeroot »
|
Logged
|
Someday, man will understand primary theory; how every aspect of our universe has come about. Then we will describe all of physics, build a complete understanding of genetic engineering, catalog all planets, and find intelligent life. And then we'll just puzzle over fractals for eternity.
|
|
|
|
April 08, 2008, 01:56:05 PM
Dilber MC Theme by HarzeM