hobold
Fractal Bachius
Posts: 573
|
 |
« Reply #15 on: March 30, 2010, 06:29:16 PM » |
|
Two more cents on algorithmic ideas ...
- Skipping rectangular regions with distance estimates works best for squares. So a quadtree would probably win over a Kd-tree. Unless the Kd-tree is modified to prefer square cells.
- Calculating a DE in the center makes it harder to re-use the result later. Values at corners stay at corners after subdivision. A possible solution would be to subdivide into 3x3 squares rather than 2x2, but that would be less adaptive, so not a clear win.
|
|
|
|
|
Logged
|
|
|
|
|
Botond Kósa
|
|
« Reply #16 on: March 30, 2010, 10:30:10 PM » |
|
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. Here are some low resolution (320x240) examples illustrating the effect of pixel interpolation. - left: fully computed image - center: interpolated (partially computed) image - right: interpolated image showing computed pixels only As you can see, there is no visible difference between the fully computed and interpolated versions. |
|
|
|
Logged
|
|
|
|
|
reesej2
Guest
|
|
« Reply #17 on: March 30, 2010, 11:16:53 PM » |
|
Wow, very impressive. What kind of time improvement does it allow? I can see that it would be a LOT faster than basic computation.
I like your method a lot, kbotond, because it doesn't require that all the boundary points have the same escape time, which always struck me as a very hard-to-meet condition.
|
|
|
|
|
Logged
|
|
|
|
|
Botond Kósa
|
|
« Reply #18 on: March 31, 2010, 12:04:48 AM » |
|
Wow, very impressive. What kind of time improvement does it allow? I can see that it would be a LOT faster than basic computation. The time savings come from skipping the computationally intensive z->z 2+c iterations, so the higher escape values can be interpolated, the better. The savings depend on two major factors, as I learned: 1. The complexity of the image. The more plain (inside) or monotonic (outside) areas are on the image, the more pixels can be interpolated. Unfortunately, as you zoom in and more fine detail starts to appear, the savings in outside areas converge to zero. After reaching the resolution capability of 64-bit double numbers (at a magnification of ~ 2E-45), the savings become insignificant, especially in the area around minibrots. Inside the minibrots however, the savings can be huge, especially at high maximum count values. 2. The resolution of the image. The higher resolution the image is computed, the higher the ratio of interpolated pixels can be. See the attached images, which show the same area computed without, with 2x2, with 4x4, and with 8x8 oversampling. I got the following savings: - no oversampling: 72.32% of pixels, 76.89 of iterations computed. Savings: ~23% - 2x2 oversampling: 59.62% of pixels, 66.11 of iterations computed. Savings: ~34% - 4x4 oversampling: 48.59% of pixels, 56.50 of iterations computed. Savings: ~43% - 8x8 oversampling: 39.86% of pixels, 48.66 of iterations computed. Savings: ~51% |
|
|
|
Logged
|
|
|
|
|
Botond Kósa
|
|
« Reply #19 on: March 31, 2010, 12:07:10 AM » |
|
(These are the samples for 4x4 and 8x8 oversampling. I couldn't attach them to my previous post.)
|
|
|
|
Logged
|
|
|
|
|
reesej2
Guest
|
|
« Reply #20 on: March 31, 2010, 01:25:50 AM » |
|
That's some serious time savings. I take it the technique never becomes noticeably detrimental?
|
|
|
|
|
Logged
|
|
|
|
|
Botond Kósa
|
|
« Reply #21 on: March 31, 2010, 09:45:53 AM » |
|
That's some serious time savings. I take it the technique never becomes noticeably detrimental?
I have experienced no performance degradations so far. The costs of monotonicity checking and interpolation are lower than that of computing the actual pixel values, by orders of magnitude. |
|
|
|
« Last Edit: March 31, 2010, 10:59:20 AM by Botond Kósa »
|
Logged
|
|
|
|
|
Botond Kósa
|
|
« Reply #22 on: March 31, 2010, 11:07:43 AM » |
|
I like your method a lot, kbotond, because it doesn't require that all the boundary points have the same escape time, which always struck me as a very hard-to-meet condition.
I also considered implementing some kind of boundary tracing algorithm in the past. Since it would require equal boundary point values, it could not be used with continuous coloring, so I dropped the idea and came up with the interpolating technique instead. It proved to be a good trade-off between reasonable savings and nice visuals. |
|
|
|
|
Logged
|
|
|
|
|
reesej2
Guest
|
|
« Reply #23 on: March 31, 2010, 08:06:13 PM » |
|
I wonder if this method could be extended? For instance, instead of requiring it to be monotonic, require that it change directions no more than once (like a parabola). Making it line up properly would be tricky though.
|
|
|
|
|
Logged
|
|
|
|
|
Timeroot
|
|
« Reply #24 on: March 31, 2010, 10:00:58 PM » |
|
Botond, that's really nice. Where do the seemingly random lines come from? They seem the be just as monotonic as everything else, pretty much. I could imagine that they are the places to which either side the iteration increases, but the doesn't explain why there are sometimes two crossing each other, or why they wind back, etc.
|
|
|
|
|
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 #25 on: March 31, 2010, 11:18:15 PM » |
|
Botond: I assume you're using either a linear or a logarithmic color map for turning the smooth iteration values into colors? I tried this algorithm with HPDZ's rank order coloring strategy ( http://www.fractalforums.com/programming/non-parametric-color-mapping-techniques/) and it had some very intriguing errors. I think they're fixable, though--I'm going to work on it. |
|
|
|
|
Logged
|
|
|
|
|
Botond Kósa
|
|
« Reply #26 on: April 01, 2010, 11:26:37 AM » |
|
Botond, that's really nice. Where do the seemingly random lines come from? They seem the be just as monotonic as everything else, pretty much. I could imagine that they are the places to which either side the iteration increases, but the doesn't explain why there are sometimes two crossing each other, or why they wind back, etc.
You're right. These lines contain pixels where either the horizontal or vertical line has a local maximum or minimum of iterations. See the attachment. The left image has continuous coloring, the middle one uses integer iteration values only, and the right one shows only the computed pixels. The curves on the right image cross the stripe boundaries at their extreme (leftmost, bottommost etc.) points. The crossing lines in one of my previous examples (y.png) are a result of some rounding errors produced by the double-double arithmetic ( http://www.fractalforums.com/programming/%28java%29-double-double-library-for-128-bit-precision/). This has no visible effect on the image quality though. |
|
|
|
Logged
|
|
|
|
|
Botond Kósa
|
|
« Reply #27 on: April 01, 2010, 11:50:14 AM » |
|
I wonder if this method could be extended? For instance, instead of requiring it to be monotonic, require that it change directions no more than once (like a parabola). Making it line up properly would be tricky though.
This could be quite tricky, but it could spare the curves demonstrated in my previous post. I will give it a try. Maybe instead of checking the monotonicity of the line, I could check for the monotonicity of the first differential. That could allow such parabolic areas to be interpolated directly. In fact, when I interpolate large areas, I have to use some "cheating". You can see some computed pixels aligned on a grid inside the large interpolated areas. I need them to avoid false interpolations, because my algorithm cannot decide if the rectangle contains a convex or concave area based on the boundary values only (see attachment). So if the size of the interpolated area exceeds a certain threshold (8x8 pixels), I compute this grid of pixels, interpolate the vertical and horizontal lines between those pixels, then interpolate the resulting small rectangles. |
|
|
|
Logged
|
|
|
|
hobold
Fractal Bachius
Posts: 573
|
|
« Reply #28 on: April 01, 2010, 02:25:20 PM » |
|
If you can get the second order (parabolic) interpolation to work, it should automatically be able to approximate convex and concave cases.
|
|
|
|
|
Logged
|
|
|
|
|
Botond Kósa
|
|
« Reply #29 on: April 01, 2010, 03:23:56 PM » |
|
If you can get the second order (parabolic) interpolation to work, it should automatically be able to approximate convex and concave cases.
I am not sure if any kind of interpolation can be precise on a larger area, since the actual pixel values do not follow any analytic function. (If that were the case, it wouldn't be a fractal.) So I would have to use a grid of calculated inner points anyway, only a sparser one. But even the grid I currently use has only 1 calculated point for every 8x8 rectangle, that is only 1.5% of the total pixels. |
|
|
|
|
Logged
|
|
|
|
|
April 08, 2008, 01:56:05 PM
Dilber MC Theme by HarzeM