April 22, 2018

**Update:** I wrote a new version with WebGPU, try it out at: https://donghaoren.org/buddhabrot/.

Buddhabrot is a fractal technique derived from the Mandelbrot set.
Recall that the Mandelbrot set is the collection of points *c* in the complex plane for which the iterative formula \(z_{n+1} = z_n^2 + c\) starting from \(z_0 = 0\) does not go to infinity.
The Buddhabrot image can be generated by computing the 2D density map of all the *z* sequences what goes to infinity given a uniform random sample of *c* values.

While the Mandelbrot set can be rendered fairly quickly with GPU acceleration, rendering the Buddhabrot is much more computationally intensive.
Alexander Boswell described the challenge and showed how the Metropolis-Hastings Algorithm could be used for sampling *c* points. Aluminum Studios has made a great video using his custom rendering software. Benedikt Bitterli used an importance sampling method to speed up the rendering.

Recently, I need to render the Buddhabrot and its variants (by changing the iterative formula) in **realtime** for a project.
Initially, I thought about using the importance sampling method to generate initial *c* points, and then execute a geometry shader to do the iteration for each *c*. However, it came to me that it might be possible to do this in the new WebGL 2 standard, which adds a Transform Feedback process to the pipeline. We can do the following algorithm:

- Perform importance sampling in a GPU shader, and store importance values in a texture.
- Sample points using the importance values (this is in the CPU, we’ll need to read the importance values back).
- In the first iteration, check whether the point tends to infinity. For remaining iterations, render the points and update the points for the next iteration.

The transform feedback process is right for the last item. In the vertex shader, we perform one iteration and write the result to the transform feedback buffer. This approach turned out to work. A modern graphics card can render at around 10-20fps with reasonable quality.

- The source code is available at: https://github.com/donghaoren/buddhabrot-renderer

In initial versions, I did not check whether the points tend to infinity before putting them on the screen. Below are some interesting results. They are not technically correct, but still looks interesting and has a lot of detail.

I also wrote an offline renderer. Here is an animation produced with it: