How-to: Epic visualizations of 3D fractals?

Question

I have seen videos like this before in the past of things like "3D Mandlebulbs" and similar fractal sets, but can anyone tell me what sorts of programs are actually used create these visualizations? How computationally expensive are these visualizations to make? Also, what sort of simulations are these? I mean, what sort of coordinate system, or mesh, are these sorts of structures realized on? I have most of my experience with computational simulations in FORTRAN, Python, and Matlab, and I just don't see how you would even begin to undertake creating the data to produce these sorts of visualizations in those languages.

Thanks.

Answer 1

Recently I happened to wonder somewhat similar questions expect I was, in particular, interested in real time visualization of three-dimensional fractals. Since other answers consider two-dimensional fractals, I decided to include some knowledge I have acquired on three-dimensional rendering and ray marching.

Definition of a surface and ray tracing

One way to define a surface in three-dimensions is through a function $f:\mathbb{R}^3\rightarrow\mathbb{R}$ which satisfies $$f(\boldsymbol{x})=0,$$ for every point $\boldsymbol{x}\in \mathbb{R}^3$ that belongs to the surface. Thus, the surface $S$ can be defined as $$S=\{\boldsymbol{x} \in \mathbb{R}^3\,|\,f(\boldsymbol{x})=0\}.$$ For one to visualize the surface $S$, the intersection point $\boldsymbol{p} \in \mathbb{R}^3$ of a ray—starting from the camera position $\boldsymbol{c} \in \mathbb{R}^3$ to some direction $\boldsymbol{d} \in \mathbb{R}^3$, $\|\boldsymbol{d}\|=1$—and the surface must be sought. After these intersection points are known for sufficiently many rays, a visualization can be constructed (some examples follow).

One way to find the intersection point $\boldsymbol{p}$ is through analytical calculations: the surface defined by $S$ is sometimes so simple that this calculation can be done by hand. An example that considers the intersection of a ray and a sphere can be found from Wikipedia. This is exactly what the traditional ray tracing is all about.

In a more general setting, no analytical relationship exists for finding the intersection point $\boldsymbol{p}$. In such a case, one must rely to numerical methods.

Numerical methods for finding the intersection point

A proficient applied mathematician would immediately attempt to apply, e.g., Secant method to the problem: find $t \in \mathbb{R}$ such that $$f(\boldsymbol{c}+t\boldsymbol{d}) \approx 0.$$ There is, however, a caveat. For a general $f$ the function $$g(t):=f(\boldsymbol{c}+t\boldsymbol{d})$$ might have several roots and in Secant method (or similar) nothing guarantees that a root nearest to the camera is recovered. You might end up drawing the wrong side of the object of interest! Thus, the applied numerical method should be guaranteed to find a root nearest to the camera.

Ray marching and distance fields

A somewhat trivial method to find the nearest (or approximately nearest) root is to fix a sufficiently small constant step size $\Delta t$ and then find the smallest $n \in \mathbb{N} \cup \{0\}$ such that $$f(\boldsymbol{c}+n \Delta t \boldsymbol{d})\approx 0.$$ This is known as ray marching and is indeed a valid method for visualizing the surface $S$. The problem is that it's tremendously slow since one must try every possible $n$ starting from zero!

Fortunately, there exists a clever trick to make the computation faster by ensuring that $f$ defines a distance field of $S$. This means that at every point $\boldsymbol{x}$ in the space $\mathbb{R}^3$ the value $f(\boldsymbol{x})$ represents the minimum distance from $\boldsymbol{x}$ to the surface $S$. This sounds like a hard restriction to satisfy but for many fractals the distance fields (or approximate distance fields) have already been derived by enthusiasts (see Fractal Forums).

The algorithm goes as follows:

1. $\boldsymbol{p}:=\boldsymbol{c}$
2. $\boldsymbol{p}:=\boldsymbol{p}+f(\boldsymbol{p})\boldsymbol{d}$
3. If $f(\boldsymbol{p})$ is larger than some tolerance go back to step 2. Otherwise, break.

Output of the prescribed algorithm is the intersection point $\boldsymbol{p}$.

Visualizing fractals in practice

If you happen to own a sufficiently fast graphics processing unit and know the function $f$ for some fractal then this method can be implemented in real time using, e.g., OpenGL Shading Language. See the following Shadertoy entry I constructed as an example:

https://www.shadertoy.com/view/MtX3zr

Getting the coloring and other visuals right requires of course lots of experience (or trial-and-error) but this is the basic idea for generating such animations. I tried to add some comments to the shader code and attempted to use same symbols as in this post.

Answer 2

There is no reason at all for the fractals to be defined by iterative algorithms: fractals are carefully defined mathematical objects. For example, the Mandelbrot set is defined as the set of points $$ M= \{z \in\mathbb{C} \mid \text{the iteration }f_z(f_z(\cdots(f_z(0))\cdots) \text{ does not diverge}\}, \qquad f_z(x) = x^2+z. $$

Once you have this set of points (and it really doesn't matter how you define it, except that the final images will be more or less interesting), the next task is to render it. Drawing an object means that you have a rectangular array of pixels in an image, and to each pixel you need to assign a colour; the colour is then chosen based on the set of points you want to draw. The simplest method is to map the centre of each pixel $p$ to a point $z_p$ in the complex plane, and draw it with one colour if $z_p\in M$, and another if $z_p\notin M$.

In 3d the procedure is roughly the same, only the rendering techniques are more complicated. For drawing objects like fractals ray-tracing is often used, using software like PBRT or POV-Ray.

I think you have a number of misconceptions in your question, but I can't guess what it is that you are thinking. The important thing is to be clear about what mathematical objects you want to draw (a set of points, a set of line segments like in a finite approximation of a Koch snowflake, etc.), and how you produce an image from it (how you map pixels to the object you are drawing, how you choose colours for each pixel, etc.).