Using Fractals and Recursion to Create a Digital World

Kevin Bertman, Math 674 Topic 4, University of Waterloo

Trees

Look at the trunk of a tree; it has branches growing out of it. Look at those branches; they also have branches growing out of them, which also have branches growing out of them and so on. This is an example of the fractal nature of trees. If we look closely at any branch, it looks similar to its parent branch, which looks similar to its parent branch. Computer programmers can use this property along with a programming technique known as recursion to quicklty create assets, some of which will be discussed on this page, for use in two-dimensional and three-dimensional digital worlds.

Consider a tree trunk out of which two branches grow. We can create this programatically by passing the coordinates of the trunk to a function which will draw the trunk and its two branches. This is demonstrated in figure 1.

If we wish to replace the branches with a smaller version of the original trunk and two branches we can pass the coordinates of the branches to the function. This is done within the function itself and is an example of recursion. Recursion will continue indefinitely unless we introduce a counter to keep track of the current level of recursion. This is demonstrated in figure 2, which has 10 levels of recursion.

drawTree

trunk coordinates

function drawTree coordinates

draw trunk using coordinates
draw left branch using coordinates
draw right branch using coordinates

Figure 1

drawTree

trunk coordinates

function drawTree coordinates step

draw trunk using coordinates
calculate left branch coordinates using coordinates

if step <= 10

drawTree

left branch coordinates

step+1

calculate right branch coordinates using coordinates

if step <= 10

drawTree

right branch coordinates

step+1

Figure 2

Figure 3 shows the growth of a tree. The first image shows step 1, whose branches are then replaced with a scaled down version of this design in the second image which represents step 2, whose smallest branches are replaced with a scaled down version of step 1 in the third image which represents step 3. The fourth image shows step 10. You may adjust positions of the branches in step 1 by clicking anywhere in the gray areas.

Figure 3
Figure 3 is an example of an Lindenmayer system (or L-system), introduced in 1968 by Hungarian biologist Aristid Lindenmayer [1].

Real trees never look as "mathematically perfect" as these fractal trees. We can introduce some randomness to make them look more natural. There are four variables which affect the look of the tree. These are the angles of the two branches (angles α and β in figure 4), and their lengths relative to their parent branch (scalars a and b in figure 4). If we add a random number to each of these variables in every iteration the tree will look a little more natural. You may adjust the positions of the branches in step 1 of figure 4 by clicking anywhere in the gray areas. Repeatedly clicking the same point will demonstrate the randomness applied to the four variables.

Figure 4
Ferns

Now let us turn our attention to something smaller. Figure 5 shows a red quadrilateral which is replaced with three smaller black versions of itself. These three smaller quadrilaterals are then each replaced with three even smaller versions of themselves. This process in repeated. In step 1 you can change the sizes and positions of the three black quadrilaterals by adjusting the position of the red dots. Click on the + or - to increase or decrease the step number. If we don't change the positions of the red dots by too much, after many iterations the result is something that has the appearance of a fern.

Figure 5

These kinds of ferns were popularised by British mathematician Michael Barnsley in 1988 [2].

Since each iteration triples the number of leaves, after n steps we will have

leaves. This number gets very big very fast. At step 20 there will be 3,486,784,401 leaves which will take time to render even on the most powerful computer. This is a problem when creating a fern because different leaves in the same iteration are different sizes, so if we simply stop after a fixed number of iterations we may have some very small small leaves, and some relatively large leaves. Ideally we would like all of our leaves to be very small. To solve this problem we can keep running the program for an unlimited number of iterations but draw the leaves once they have reached a certain size. This is acomplished by keeping track of the scale of the current leaf compared to the size of the original leaf, and is demonstrated in figure 6 (this is also how figure 5 is able to show a large number of iterations). Leaves are only drawn once their dimensions are less than 1% of the dimensions of the original leaf.

drawFern

fern coordinates

function drawFern coordinates scale

if scale < 0.01

draw fern using

coordinates

else

calculate left leaf coordinates using coordinates

drawFern

left leaf coordinates

(left leaf scale)*scale

calculate right leaf coordinates using coordinates

drawFern

right leaf coordinates

(right leaf scale)*scale

calculate top leaf coordinates using coordinates

drawFern

top leaf coordinates

(top leaf scale)*scale

Figure 6

Lightning

Now let us turn our attention to the sky. Suppose we wish to simulate lightning. We can do this using our tree model from figure 3. Instead of giving each branch two smaller branches of its own we give it one branch (whether this is the left or the right branch is randomly determined) and then we randomly determine whether or not to give it the other branch. Increasing or decreasing the probability that each branch gains the other branch changes the density of the lightning. This is demonstrated in figure 7. Click on the image to generate new lightning.

If we turn the tree upside down, adjust the angles and lengths of the branches, and change the thickness of each branch it looks more realistic. Also, since we don't have to draw every branch of the tree we can perform more iterations in less time than if we were drawing the whole tree. This is demonstrated in figure 8, which displays two "trees". Click on the image to animate the lightning.

Figure 7

Figure 8

Two-Dimensional Landscapes and Cityscapes

The next part of this page will focus on creating large objects which create the shape and structure of a digital world. Suppose we have two points connected by a straight line and we take the midpoint of this line and give it a small vertical offset. The size of this offset is randomly determined, is less than a certain specified maximum value, and is either subtracted or added (which is also randomly determined). We now have two straight lines. Clicking on figure 9 will repeat this process, repeatedly dividing each line into two and halving the maximum offset in each iteration. Step 1 starts with two lines to give us more influence over the look of the final structure. After step 3 we fill in our creation with colour, and add some similar structures in the background. Eventually we create something which resembles a mountain range. Return to step 1 to create a new random mountain range.

Figure 9

Modelling landscapes in this way was introduced by French-American mathematician Benoit Mandelbrot [3].

Using the same method as in figure 9, instead of just drawing a line between two adjacent points we can draw a building from the ground to each point. If the y-coordinate of each point represents the height of the building we can easily create randomly generated city skylines. Figure 10 shows three layers of buildings. Click on the image to randomly generate a new skyline.

Figure 10

Three-Dimensional Landscapes and Cityscapes

We can use a similar method as the one in figure 10 to create terrain in three dimensions. Suppose we have four sets of three-dimensional coordinates which represent the position of each corner of a square plot of land (looking from above). Take the centre of the square, give it a height equal to the mean of the heights of the four corners plus or minus a random offset and connect it to the corners of the square. This is demonstrated in step 1 of figure 11. Now suppose we divide the original square into four smaller smaller squares using the midpoints of each side and the centre of the square from step 1. We then continue to divide these smaller squares in the same we we divided the original square. this is demonstrated in step 2 of figure 11. We continue this process, reducing the maximum random offset in each iteration, and eventually we create something which resembles a three-dimensional mountain range. Note that the first four steps of figure 11 shows a three-dimensional view of the square plot of land along with the view from above. After step 4 three more plots of land are introduced. Return to step 0 to create a new random mountain range.

Figure 11

The function used to create figure 11 has a similar structure to our fern example. This is demonstrated in figure 12.

draw3DMountain

square vertices coordinates

function draw3DMountain coordinates step

calculate

midpoint

using

coordinates

apply random vertical offset to

midpoint

if step = 9

draw four triangle faces using

coordinates

and

midpoint

else

calculate

top square coordinates

using

coordinates

and

midpoint

draw3DMountain

top square coordinates

step+1

calculate

left square coordinates

using

coordinates

and

midpoint

draw3DMountain

left square coordinates

step+1

calculate

right square coordinates

using

coordinates

and

midpoint

draw3DMountain

right square coordinates

step+1

calculate

bottom square coordinates

using

coordinates

and

midpoint

draw3DMountain

bottom square coordinates

step+1

Figure 12

The colour of each triangular face in figure 11 is determined by finding a normal vector to the face (using the vector product of two vectors from one of the verticies to the other two vertices) and then determining the cosine of the angle between this vector

and a vector which represents the direction of the sunlight

using

cos θ

The value of cos θ is then used to determine the brightness of each face. A value closer to 1 represents a brighter face while a value closer to -1 represents a darker face.

The three-dimensional terrain is created using only two-dimensional drawing techniques with Javascript on a HTML5 canvas. This means that the three-dimensional coordinates are converted into two-dimensional coordinates (the x and y-coordinates are recalculated depending on the z-coordinate), and each iteration is calculated and drawn from the back to the front so elements which are further away, and possibly obscured by closer elements, are rendered first.

Instead of using triangles to create the mountain range we can use square prisms and only allow heights that are multiples of a constant. This gives our landscape a similar look to the popular game Minecraft. Click on figure 13 to generate the landscape. Note that because we wish for the terrain to appear as blocks we do not need to perform as many iterations. Return to step 0 to create a new random mountain range.

Figure 13

If we include gaps between the square prisms, design them like a building, and reduce the maximum random offset by a smaller amount in each iteration we can create a three dimensional city. Click on figure 14 to randomly generate a new city.

Figure 14

Planetary Sized Objects

Finally let's turn our attention to space. Start with a regular icosahedron and divide each triangular face into four smaller triangles using the midpoints of each side of the face. However, these midpoints are protruded so they are at a distance from the centre of the icosahedron which is equal to the mean of the distances of the endpoints, plus or minus a random offset. If we keep repeating this process, reducing the maximum size of the random offset in each iteration, we create something which resembles a comet. Note that it is possible to begin with a tetrahedron or an octahedron but icosahedrons result in triangles of a similar shape and size after many iterations [4]. Click on figure 15 to create the comet. After step 3 realistic shading is introduced, created in the same way as the three-dimensional mountain range shading. Return to step 0 to create a new randomly generated comet.

Figure 15

To avoid any gaps adjacent faces need to apply the same random offset to their shared edge. This is accomplished by creating an array of random values when the program is first run. A face will then determine which value from this array to use for the random offset using the coordinates of the two endpoints of the edge. Shared edges will then always be given the same random offset.

If we reduce the size of the maximum random offset in each iteration and color each face depending on its distance from the centre we can create moon and earth-like bodies. Click on figure 16 to generate a new earth and moon. Note that the earth and its clouds are made from two layers with two different colour schemes. The earth colours faces at sea-level in blue, and higher surfaces in green, then yellow, then white. The clouds are formed by creating another "earth" but making all faces white, making faces at sea-level transparent, and gradually reducing this transparency as the height of the surface increases. The moon uses various shades of grey for its faces.

Figure 16

References

1.	Lindenmayer, A. (1968) Mathematical Models for Cellular Interactions in Development. Journal of Theoretical Biology Volume 18, 300-315.
2.	Barnsley, M. F. (1988) Fractals Everywhere. Boston: Academic Press.
3.	Mandelbrot, B. B. (1982) The Fractal Geometry of Nature. San Francisco: W. H. Freeman and Company
4.	Kooima, Leigh, Johnson, Roberts, SubbaRao, Defanti (2009) Planetary-Scale Terrain Composition. Institute of Electrical and Electronics Engineers Transactions on Visualization and Computer Graphics Volume 15 Issue 5, 719-733.