We often speak of two dimensional
or 2D and
three-dimensional
or 3D. There are several equivalent ways of
defining these ideas; let’s consider a specific one: cube counting.
Consider a chunk of some shape that passes though a cube. Subdivide that cube evenly into n divisions along each axis to make a grid of n^3 smaller cubes. How many of those smaller cubes does the shape pass through?
The exact answer to this question is overly dependent on the specifics of the case. For example, an axis-aligned straight line passes through n cubes while a straight line between opposite cube corners may passe through as many as 3n. In computing we know how to handle such constants: big-O. Any straight line passes through \Theta(n^1) cubes. Any flat plane passes through \Theta(n^2) cubes. Any solid passes through \Theta(n^3) cubes. We call the exponent in these expressions the dimensionality of the shape.
This formulation suggests we could have a fractional dimension like 1.2: we just have to find some shape that passes through \Theta(n^{1.2}) of the cubes. One way to construct such a shape is to find a shape that exhibits that ratio at one scale and recursively apply it to itself so that it exhibits that same ratio for every n.
The Koch curve starts with the following shape
With n=1 this fits in one cube, but with n=3 it needs four cubes, not three, suggesting maybe more than n^1. But if we zoom in more we find just lines. Let’s fix that by replacing each segment with another copy of the same shape
Now the pattern holds up to n=9; continuing ad infinitum we get
By construction, tripling (3n)^d = 4n^d meaning d = \frac{\log 4}{\log 3} \approx 1.26185\dots
Nothing in nature exhibits a true mathematical fractal: zoom in enough and you find 3D cells or 1D elementary particles. But many things in nature are visually more fractal than they are Platonic. Many mountains look more like fractals than they look like spheres, many trees look more like fractals than they look like cylinders, dirt accumulates in patterns that look more like fractals than they do gradients, and so on. Fractals make a useful starting point for making a stylized model of nature.
Fractals are also useful in that they break up our ability to notice patterns. The eye is much less likely to notice a low-fidelity image if the image is made up fractals than if it is made up of simple shapes. Fractals are a useful tool for making a simple model look more detailed than it is.
There are many fractals used in graphics, but four are common enough to be worth discussing in more detail.
All of these are forms of fractal noise: that is, they use pseudorandom parameters to create a fractal that looks random instead of looking mechanical or mathematical.
Brownian motion refers to the trajectory followed by a particle that randomly changes direction. The most common formulation of Fractal Brownian motion (abbreviated fBm) is a 1.x-dimensional fractal created by the position of a 1D Brownian motion on one axis and time on the other. Many other fBm formulations also exist.
In graphics, fBm noise
is used to describe any purely
stochastic fractal, even if there is no way to characterize it as the
motion of a particle.
Subdivision methods provide a computationally simple way of generating a fractal. Given a low-resolution mesh, replace each primitive with several smaller primitives and then randomly offset the vertices. Provided the expected magnitude of the random offsets is proportional to the size of the primitive, the result will be fractal.
Naïve fractal subdivision often exhibits visible patterns where the seams between the low-res primitives remain visible in the resulting fractal. To avoid this the subdivision itself should result in a smooth surface with no visible seams even if there are no random offsets.
Faulting methods are not particularly common in graphics, but they are easy to implement and thus are part of your programming assignments. As such, we have a separate page about them.
Ken Perlin made a two-part innovation in the efficient creation of fractals that has become a mainstay of computer graphics.
First, Perlin came up with a readily-computed representation of random smooth bumps. Pick points on a fixed uniform grid and at each pick a random surface normal, then fit a surface to those normals. Conceptually such a surface can be found by making one hill-and-pit pair and placing a rotated copy of it at each point. Practically it can be found using polynomially-interpolated dot products.
The original Perlin noise used a square grid to create the bumps. The turns out to result in visible axis-aligned patterns, so various alternatives such as simplex noise and opensimplex noise use different grid patterns instead.
Second, Perlin recognized that a fractal can be created from almost
any bumpy surface, including his, by adding scaled-down copies of the
surface to itself. This approach, called octaves
, is based on the
observation that if f(x) is a bumpy
function then \sum_{n=0}^{\infty} f(2^n x)
2^{-n} is a fractal, and that we can stop the sum early once the
2^{-n} term is making the subsequent
iterations have no visible impact.
Because of the significance of octave-created fractals, octave
fractals that are not based on Perlin’s random-gradient bumps are
sometimes informally called Perlin
.