The chaos game as we have discussed it in the previous section can be generalized to a more powerful algorithm for generating fractals. As before, we simulate the movement of a point in the plane, but instead of moving the point toward a randomly chosen corner of a triangle, we instead transform it
using a randomly chosen function. For reasons we will explain in a moment, we usually associate with each function \(f_k\) a probability \(p_k\), which determines how frequently the chaos game chooses this function relative to the others. We call the combination of functions and their
probabilities an iterated function system or IFS.
It’s easy to see that this is a proper generalization: If \(\vec {c}_1, \vec {c}_2, \vec {c}_3\) are the corners of a triangle, we can define three functions that move a given point \(\vec {p}\) halfway toward each of the corners:
If we start with a point inside the triangle and repeatedly transform it using a randomly chosen function from the set \(\{f_1,f_2,f_3\}\), we end up with a random process that is equivalent to the chaos game from the previous section. In the case of the Sierpiński triangle,
all three corners are chosen with the same probability, so we set \(p_k=1/3\). When visualizing fractals that are less symmetric, these probabilities can be used to control the distribution of the points produced by the chaos game.
The Barnsley Fern
A famous example of a fractal based on iterated function systems is the Barnsley fern shown in Fig. 1.4. The fern consists of a stem that bends to the right and an infinite number of branches and leaves that are attached to the left and the right of
the stem. Each branch is itself a scaled and rotated version of the Barnsley fern, as are the leaves of each branch: If you zoom into any part of the Barnsley fern, you find an endless number of smaller copies of the whole shape.
Figure 1.4 The Barnsley fern is a plant-like fractal that consists of countless smaller copies of itself (left). It is generated by four affine transformations, each of which corresponds to one part of the fractal (right).
The Barnsley fern is generated by an iterated function system that consists of four functions and four probabilities:
\(\seteqnumber{0}{1.}{1}\)
\begin{align*}
f_0(\vec {p}) &= \begin{pmatrix} 0 & 0\\ 0 & 0.16 \end {pmatrix} \vec {p} + \begin{pmatrix} 0\\0 \end {pmatrix} & p_0=0.01 \\ f_1(\vec {p}) &= \begin{pmatrix} 0.85 & 0.04\\ -0.04 & 0.85 \end {pmatrix}\vec {p} + \begin{pmatrix}
0\\1.6 \end {pmatrix} & p_1=0.85 \\ f_2(\vec {p}) &= \begin{pmatrix} 0.2 & -0.26\\ 0.23 & 0.22 \end {pmatrix} \vec {p} + \begin{pmatrix} 0\\1.6 \end {pmatrix} & p_2=0.07 \\ f_3(\vec {p}) &= \begin{pmatrix} -0.15 & 0.28\\ 0.26
& 0.24 \end {pmatrix} \vec {p} + \begin{pmatrix} 0\\0.44 \end {pmatrix} & p_3=0.07
\end{align*}
All four functions have the same form: They first multiply the vector \(\vec {p}\) by a \(2\times 2\) matrix and then translate the result by adding a vector. Functions of this form are called affine transformations, and they describe a wide range of geometric transformations such as rotation, scaling, shearing, and translation; see also Box 1.1.
Box 1.1: Linear and Affine TransformationsMany important geometric transformations can be described mathematically using matrix operations. For example, scaling vectors by a constant factor \(\alpha \)
and similar matrix versions exist for other transformations such as rotation around the origin, shearing, and reflection. In general, a mapping that can be described by a matrix multiplication is called a linear transformation:
\(\seteqnumber{0}{1.}{1}\)
\begin{align*}
\vec {p} \quad \mapsto \quad \vec {A}\vec {p} \qquad \text {or}\qquad \begin{pmatrix} x \\ y \end {pmatrix} \quad \mapsto \quad \begin{pmatrix} a & b\\ c & d \end {pmatrix} \begin{pmatrix} x \\ y \end {pmatrix} = \begin{pmatrix} ax + by\\ cx + dy
\end {pmatrix}.
\end{align*}
An important generalization of linear transformations are affine transformations, which first perform a matrix multiplication and then add a fixed vector \(\vec {t}\):
\(\seteqnumber{0}{1.}{1}\)
\begin{align*}
\vec {p} \quad \mapsto \quad \vec {A}\vec {p} +\vec {t} \qquad \text {or}\qquad \begin{pmatrix} x \\ y \end {pmatrix} \quad \mapsto \quad \begin{pmatrix} a & b\\ c & d \end {pmatrix} \begin{pmatrix} x \\ y \end {pmatrix} + \begin{pmatrix} t_x \\
t_y \end {pmatrix} = \begin{pmatrix} ax + by + t_x\\ cx + dy + t_y \end {pmatrix}.
\end{align*}
Affine transformations let us rotate, scale, and shear as before, but they can also be used to move geometric objects in the plane. We will discuss affine transformations in more detail in Section 3.2.
The right part of Fig. 1.4 illustrates how these four affine transformations determine the shape and structure of the Barnsley fern. Imagine a rectangle that encloses the Barnsley fern and then transform this bounding box using each
of the four transformations. The first transformation \(f_0\) flattens the box into a short vertical line that forms the stem of the fern; \(f_1\) moves a slightly scaled and rotated version of the bounding box to the end of the stem and generates the upper part of the fern; and the last two
transformations \(f_2\) and \(f_3\) form the first leaf on the left and right of the fern, respectively. Notice that \(f_3\) also flips the coordinate system and introduces a slight shear, so the leaves on the right side of the fern bend to the left and are slightly skewed. Smaller details of the fern are
obtained by applying multiple functions in sequence. For instance, applying \(f_2\) followed by \(f_0\) produces the stem of the left branch, and applying \(f_1\) followed by \(f_3\) the second branch on the right. Every part of the fractal corresponds to a particular combination of the four
functions in its iterated function system; you can think of the four functions as the fractal’s geometric blueprint.
This geometric blueprint is filled with a random distribution of points using the chaos game. The probabilities \(p_1,\dots ,p_3\) control how the points are distributed over the different parts of the fractal: In the case of the Barnsley fern, the probabilities are \(0.01\), \(0.85\), \(0.07\),
and \(0.07\), which means that approximately 1% of all points will be placed in the fern’s stem (or one of its many copies), 85% in its body, and 7% in the left and right leaves each. The four probabilities sum to 1, which reflects the fact that every point is allocated to one
of the available transformations.
It is instructive to consider what happens if we choose other values for the probabilities. If we set all probabilities to \(1/4\), for instance, each part of the fractal receives the same number of points, and we obtain the rendering of the Barnsley fern shown in the left part of Fig. 1.5. With this choice of probabilities, most points end up in or close to the stem of the Barnsley fern and fewer points in its leaves. If, on the other hand, we set the four probabilities to 0.01, 0.94, 0.025, and 0.025, most points are
allocated to the function \(f_1\), which increases the density of points in the tips of the branches, as illustrated in the right part of Fig. 1.5.
Figure 1.5 The influence of IFS probabilities. The probabilities associated with an iterated function system determine the spatial distribution of points produced by the chaos game. Decreasing the probability of the stem places more points in the leaves (left) whereas
increasing it emphasizes the stem but places fewer points in the leaves (right).
In practice, suitable values for the probabilities must usually be determined by trial and error, especially if the primary goal is to produce pleasing images. But it is possible to compute reasonable starting values so that more points end up in parts of the fractal that cover a large surface area; we will discuss
one such an approach in Exercise 1.5.
Affine Iterated Function Systems
An affine transformation is a function that consists of a linear transformation — usually a combination of rotation, scaling, and shearing — followed by a translation. We usually write affine transformations in the following form:
\(\seteqnumber{0}{1.}{1}\)
\begin{equation}
\label {eq:affine} \vec {p}\quad \mapsto \quad \begin{pmatrix} a & b\\ c & d \end {pmatrix}\vec {p} + \begin{pmatrix} t_x\\t_y \end {pmatrix}.
\end{equation}
where \(\vec {p}\) is the point being transformed. The transform is completely defined by six numbers: the four coefficients \(a, b, c, d\) of the \(2\times 2\) matrix and the two coefficients \(t_x, t_y\) of the translation vector. To implement affine transformations, we define a record called Affine that stores these six numbers as floating-point numbers (Listing 1.5).
Listing 1.5ch1β―/β―Affine
// An affine transformation in 2D.
public record Affine(
double a, double b,
double c, double d,
double tx, double ty) {
// ...
}
If we set \(\vec {p}=\left (\begin {smallmatrix}x\\y\end {smallmatrix}\right )\) and expand the matrix product in Eq. (1.2), we obtain the coordinates \(x'\) and \(y'\) of the
transformed point:
The transformPoint() method in Listing 1.6 uses this formula to apply an affine transformation to a given Point, producing a new Point. Since we will often work with lists of points, we also define a second method transformPoints() that transforms multiple points and returns the result as a new list. That’s all the functionality we need for now, although we will extend Affine with few additional methods in Chapter 3.
Listing 1.6ch1β―/β―Affine
// Transform a single point.
public Point transformPoint(Point p) {
return new Point(a * p.x() + b * p.y() + tx,
c * p.x() + d * p.y() + ty);
}
// Transform a list of points.
public List<Point> transformPoints(List<Point> points) {
var result = new ArrayList<Point>(points.size());
for (Point p : points)
result.add(transformPoint(p));
return result;
}
We can now represent an affine iterated function system as an array of affine transformations of type Affine together with an array of probabilities of type double (Listing 1.7). The constructor of AffineIFS initializes transforms using the argument of the same
name, but for probabilities it performs an additional normalization step to ensure that its entries sum to 1. Normalizing the probabilities ensures that exactly one of the affine transformations is
chosen by the chaos game in each step. The second argument of AffineIFS() is therefore simply an array of frequencies that indicate how often each affine transformation is chosen relative to
the others, which is then converted into a table of probabilities by dividing each entry by total, the sum of all frequencies.
Listing 1.7ch1β―/β―AffineIFS
// Representation of an affine iterated function system.
public class AffineIFS {
public final Affine[] transforms;
public final double[] probabilities;
public AffineIFS(Affine[] transforms, double[] frequencies) {
this.transforms = transforms;
this.probabilities = new double[frequencies.length];
double total = 0.0;
for (double freq : frequencies)
total += freq;
for (int i = 0; i < frequencies.length; i++)
this.probabilities[i] = frequencies[i] / total;
}
// ...
}
Listing 1.8 demonstrates how to construct an instance of AffineIFS that represents the Barnsley fern. In this case, the probabilities in the second array are
already normalized.
Listing 1.8ch1β―/β―AffineIFS
public static AffineIFS BARNSLEY_FERN = new AffineIFS(
new Affine[]{
new Affine(0, 0, 0, 0.16, 0, 0),
new Affine(0.85, 0.04, -0.04, 0.85, 0, 1.6),
new Affine(0.2, -0.26, 0.23, 0.22, 0, 1.6),
new Affine(-0.15, 0.28, 0.26, 0.24, 0, 0.44),
},
new double[]{0.01, 0.85, 0.07, 0.07}
);
We can now turn to the problem of implementing the generalized version of the chaos game that lets us visualize the fractals described by affine iterated function systems. The formal description of this algorithm is shown in Algorithm 1.2. The main difference compared to the original chaos game in Algorithm 1.1 is that the algorithm now uses a fixed set of functions \(f_1,\dots , f_K\) and associated
probabilities \(p_1,\dots ,p_K\) to move the current point in each step. In Line 4, we choose one of the functions by calling a function ChooseIndex, which returns an integer \(k\) between 1 and \(K\), and in Line 5, we move the current point \(\vec {p}\) to its new position by transforming it using the \(k\)th
function \(f_k\).
Algorithm 1.2
Given a starting point \(\vec {s}\), produce a sequence of \(n\) points in the plane. The variables \(f_1,f_2,\dots f_K\) are affine transformations and \(p_1,p_2,\dots p_K\) the associated probabilities.
The job of the ChooseIndex function referenced in Algorithm 1.2 is to take a sequence of probabilities \(p_1,\dots ,p_K\) and
generate a random index between 1 and \(K\) so that the integer \(k\) occurs with probability \(p_k\) (in other words, it returns the number 1 with probability \(p_1\), the number 2 with probability \(p_2\), and so on). How can we implement ChooseIndex?
One solution is to approach the problem geometrically. If the probabilities are normalized, we have \(p_1+\cdots +p_K=1\), which we can visualize by subdividing the interval \([0,1]\) into \(K\) sub-intervals of length \(p_1,p_2,\dots \):
The \(k\)th interval starts at \(p_1+\dots +p_{k-1}\) and ends at \(p_1+\dots +p_{k}\) and therefore has length \(p_k\). If we now pick a random real number \(u\) between 0 and 1, the probability that \(u\) lands in any particular sub-interval is obviously equal to the length of
that interval, and the probability that it lands in the \(k\)th interval is \(p_k\). The index of the interval that contains \(u\) is therefore an integer between 1 and \(K\) with the desired probability distribution.
To find the interval that contains \(u\) we can simply try them one after another. If \(u<p_1\), the number lies in the leftmost interval with index \(k=1\); if \(u<p_0+p_1\), it lies in the second interval with index \(k=1\); otherwise, we continue in this manner until we find the first
index \(k\) such that \(u<p_0+p_1+\dots +p_k\). The resulting algorithm is shown in Algorithm 1.3. The variable \(s\) accumulates the probabilities so it always contains the upper limit of the current interval,
and the smallest index for which \(u < s\) is the desired random index.
Algorithm 1.3
Generate a random integer with a given distribution. The return value is an integer between 1 and \(K\), and the number \(k\) is returned with probability \(p_k\).
The generalized version of the chaos game can now be implemented as shown in Listing 1.9. The extendedChaosGame()
method simulates the movement of the point start over the specified number of iterations and returns a list of visited points. In each iteration, the function appends the current position to points and then advances to the next point applying
one of the affine transformations chosen at random. The chooseIndex() method implements the ChooseIndex algorithm: It uses the given random number generator to produce one floating point number between 0 and 1 and then searches for the interval that contains this number.
Listing 1.9ch1β―/β―AffineIFS
public List<Point> extendedChaosGame(
Point start, int iterations, Random rng) {
Point p = start;
var points = new ArrayList<Point>(iterations);
for (int i = 0; i < iterations; i++) {
points.add(p);
p = transforms[chooseIndex(rng)].transformPoint(p);
}
return points;
}
public int chooseIndex(Random rng) {
double u = rng.nextDouble();
double sum = 0.0;
for (int i = 0; i < probabilities.length - 1; i++) {
sum += probabilities[i];
if (u < sum)
return i;
}
return probabilities.length - 1;
}
