Buddhabrot Fractal

Question

I am trying to implement buddhabrot fractal. I can't understand one thing: all implementations I inspected pick random points on the image to calculate the path of the particle escaping. Why do they do this? Why not go over all pixels?

What purpose do the random points serve? More points make better pictures so I think going over all pixels makes the best picture - am I wrong here?

From my test data:

Working on 400x400 picture. So 160 000 pixels to iterate if i go all over.

Using random sampling, Picture only starts to take shape after 1 million points. Good results show up around 1 billion random points which takes hours to compute.

Tidemark

In regards to your edit - is that test data from random sampling, or by the brute force method of going over all the pixels? While I'd expect random sampling to be faster (on average) I'd be curious to see how the two methods actually compare for you in practice. – Tohubohu

my mistake forgot to mention it. This data is from random sampling. – Tidemark

Hmm, the numbers seem a bit weird then - how are you doing your random sampling - I would think that after a billion of so points you'd have captured every point of interest at least a few times (although there is no guarantee of that) from a sample set of 160, 000 . Do you get the same quality of image when you go over each pixel once by brute force? – Tohubohu

after a billion points i get good quality picture but takes 2-3 hours to compute. i am modifying my code to iterate all pixels. will update the question with results. – Tidemark

Answer 1

Random sampling is better than grid sampling for two main reasons. First because grid sampling will introduce grid-like artifacts in the resulting image. Second is because grid sampling may not give you enough samples for a converged resulting image. If after completing a grid pass, you wanted more samples, you would need to make another pass with a slightly offset grid (so as not to resample the same points) or switch to a finer grid which may end up doing more work than is needed. Random sampling gives very smooth results and you can stop the process as soon as the image has converged or you are satisfied with the results.

I'm the inventor of the technique so you can trust me on this. :-)

Kite

Answer 2

The same holds for flame fractals: Buddha brot are about finding the "attractors", so even if you start with a random point, it is assumed to quite quickly converge to these attracting curves. You typically avoid painting the first 10 pixels in the iteration or so anyways, so the starting point is not really relevant, BUT, to avoid doing the same computation twice, random sampling is much better. As mentioned, it eliminates the risk of artefacts.

But the most important feature of random sampling is that it has all levels of precision (in theory, at least). This is VERY important for fractals: they have details on all levels of precision, and hence require input from all levels as well.

Blintze

Answer 3

While I am not 100% aware of what the exact reason would be, I would assume it has more to do with efficiency. If you are going to iterate through every single point multiple times, it's going to waste a lot of processing cycles to get a picture which may not look a whole lot better. By doing random sampling you can reduce the amount work needed to be done - and given a large enough sample size still get a result that is difficult to "differentiate" from iterating over all the pixels (from a visual point of view).

Tohubohu

Answer 4

This is possibly some kind of Monte-Carlo method so yes, going over all pixels would produce the perfect result but would be horribly time consuming.

Why don't you just try it out and see what happens?

Benedetto

I think that you and others are a little hung up on the same unspoken assumption that there are only a finite number of starting points. Pixels are not points; they are square regions. Starting with different points within a given pixel can generate drastically different trajectories. – Kite

Answer 5

Random sampling is used to get as close as possible to the exact solution, which in cases like this cannot be calculated exactly due to the statistical nature of the problem.

You can 'go over all pixels', but since every pixel is in fact some square region with dimensions dx * dy, you would only use num_x_pixels * num_y_pixels points for your calculation and get very grainy results.

Another way would be to use a very large resolution and scale down the render after the calculation. This would give some kind of 'systematic' render where every pixel of the final render is divided in equal amounts of sub pixels.

Permatron

Right - iterating over the pixels doesn't produce nearly enough sample points, too many grid artifacts, and it couples your sample plane to your view plane. That said, your sample grid and your pixel resolution can be totally different, ie sample grid can be many many times the "resolution" of your pixels. – Outpour

Answer 6

I realize this is an old post, but wanted to add my thoughts based on a current project.

The problem with tying your samples to pixels, like others said:

• Couples your sample grid to your view plane, making it difficult to do projections, zooms, etc

• Not enough fidelity. Random sampling is more efficient as everyone else said, so you need even more samples if you want to sample using a uniform grid

• You're much more likely to see grid artifacts at equivalent sample counts, whereas random sampling tends to just look grainy at low counts

However, I'm working on a GPU-accelerated version of buddhabrot, and ran into a couple issues specific to GPU code with random sampling:

• I've had issues with overhead/quality of PRNGs in GPU code where I need to generate thousands of samples in parallel
• Random sampling produces highly scattered traces, and the GPU really, really wants threads in a given block/warp to move together as much as possible. The performance difference for clustered vs scattered traces was extreme in my testing
• Hardware support in modern GPUs for efficient atomicAdd means writes to global memory don't bottleneck GPU buddhabrot nearly as much now
• Grid sampling makes it very easy to do a two-pass render, skipping blocks of sample points based on a low-res pass to find points that don't escape or don't ever touch a pixel in the view plane

Long story short, while the GPU technically has to do more work this way for equivalent quality, it's actually faster in practice AFAICT, and GPUs are so fast that re-rendering is often a matter of seconds/minutes instead of hours (or even milliseconds at lower resolution / quality levels, realtime buddhabrot is very cool)

Outpour