Fractal Mountains
Volume Number: 7
Issue Number: 5
Column Tag: C Workshop
Fractal Mountain Climbing 
By Eli Meir, Ben Haller, Ithaca, NY
Note: Source code files accompanying article are located on MacTech CD-ROM orsource code disks.
[Eli Meir is a student at Cornell University. He has previously worked in a
computer graphics company and is currently programming analog to digital, modelling,
and analysis programs on the Macintosh for a neurobiology laboratory. He can be
reached at nq5@cornella.bitnet, or at 149 Grandview Ct, Ithaca, NY 14850.
Ben Haller is a student at UC Berkeley. He has done extensive programming on
the Macintosh, releasing a good deal of PD and shareware under the name AppleSauce
Designs and Stick Software, including the game Solarian II for the Mac II, and doing
some consulting work. He can be reached at deadman@garnet.berkeley.edu.]
Fractal landscapes are common in movies and animations. They are also fairly
easy to generate. In this article, we examine one method of creating and displaying
simple fractal mountains which look quite good. Creating and displaying the mountains
are two separate problems, so this article and the associated code are divided into two
parts: how to create fractal mountains, and a simple method of displaying them.
Before launching into an explanation of the code, let us give a brief description of
the program. The ‘File’ menu contains two commands, Calculate and Quit. Calculate
calculates and displays a fractal mountain. The next five menus contain parameters
which govern the generation of the mountain. The ‘Iterations’ menu governs how
detailed the mountain will be, with higher numbers indicating more detail. The
‘Contour’ menu governs the relative steepness at different heights, with higher
numbers giving steeper peaks and flatter lowlands. The ‘Smoothness’ menu governs
how jagged the sides of the mountain will be, with higher numbers indicating smoother
sides. The ‘Height’ menu governs both the overall height of the mountains, and also
where the treeline will be. Finally, the ‘Profile’ menu gives four options for the
overall shape of the mountain. All these menu items, and how they produce their
effects, will be discussed in more detail below.
Generating Fractal Mountains
Fractal mountains are generated by taking an equilateral triangle and
recursively subdividing it into smaller and smaller triangles. As each triangle is
subdivided, each new midpoint generated is raised or lowered by a random amount. The
smaller the subdivisions, the less each new midpoint may be moved, so the overall
effect is to get small perturbations of the mountain superimposed on bigger
perturbations, which are superimposed on even bigger perturbations. This creates an
appearance similar to natural mountains.
The way this works in practice is as follows. Two equilateral triangles are used,
set side by side to form a parallelogram, since this makes the code a little easier. The
‘Iteration’ menu specifies how many times to subdivide each initial triangle. Thus,
when the algorithm is done, each side of the initial triangles will have been divided into
2 ^ num_of_iter smaller sides. These smaller sides will have endpoints which still line
up if looked at from above (their x and y coordinates haven’t been changed), but have
been moved up and down (their z coordinates have been changed).
Figure 1: The figure shows the grid of triangles formed after two iterations. The
darkest lines represent the initial two triangles, the lighter lines define the triangles
formed during the first iteration and the broken lines show the triangles formed during
the second iteration. For this example, the points can be stored in a square 5x5 array
(2 ^ num_of_iterations + 1 points per side).
As can be seen in figure 1, when all the subdivisions have been made the
triangles form a square array of triangle points, 2 ^ num_of_iter + 1 points per side,
with each point belonging to up to six triangles. By simply storing the heights of each
point in a two-dimensional array, all the triangles are defined. Note that the numbers
used to access the array are not identical to the x and y coordinates of the points. Since
the array is representing a parallelogram as opposed to a square, the lines of the array
must be shifted over by varying amounts to give the x coordinate (the y coordinate is the
same as the array indexor).
The function CalcMountains() is the top level function to generate the heights.
CalcMountains() first calls InitMountains(), which allocates and initializes the array
‘map’ where the mountains will be stored and sets the values of some variables based
on values selected in the menus. CalcMountains() then sets up some initial heights and
calls IterCalc() to start the recursive calculation of heights. We will talk about the
initial heights later on. Notice that since we are starting with two triangles,
IterCalc() must be called twice.
IterCalc() is the main calculating function. Given as input the three points of a
triangle and an iteration number which indicates the depth of recursion, IterCalc()
chops the triangle into four smaller triangles, figures out the heights for the new
points which were created, and then, if the recursion hasn’t reached the bottom level,
IterCalc() calls itself with each of the newly created triangles.
Figure 2: The points s1, s2 and a are passed to IterCalc(), which then finds the points
ns1, ns2, and na. These six points then define four smaller triangles as shown, which
are recursively passed to IterCalc().
The cutting is done by finding the midpoint of each line segment of the triangle,
yielding three new points, and then using the three new midpoints plus the old endpoints
to construct four new, smaller triangles (see fig. 2). The three old points are passed to
IterCalc() not as x,y,z coordinates, but rather as offsets into the array ‘map’. The
array is originally set up to be exactly the right size for the number of iterations being
done. Thus to find the midpoint between two of the old points, with both midpoint and
endpoints being given as offsets into the array, IterCalc() simply adds the offsets of the
endpoints and divides by two.
Once the midpoints are found, their heights have to be set. First IterCalc()
checks to see if the height was previously set (since each point can be shared by more
than one triangle but should only be set once). Initially, all the points in the array are
set to 0x80000000, so if the height is different from that then the height was
previously set. If the height hasn’t already been set, IterCalc() sets it to the average of
the heights of the two endpoints, and then passes it to DeviatePoint().
DeviatePoint() is the function which introduces randomness into the picture,
and thus gives the mountains their texture. It randomly raises or lowers the height of a
point by a number which falls within a certain range. The range of possible deviations
is determined by MaxDeviation(), and is based upon what depth the recursion is
currently at. The deeper the level of recursion, the smaller the range of possible
deviations.
For a given point, the range of possible deviations is calculated using the
iteration number and the roughness variable. The iteration number starts out at the
maximum number of iterations possible ( currently 9) plus one, and is decremented
every time IterCalc() call itself. The roughness variable is set in the ‘Smoothness’
menu, and is a number between 0 and 5.0. The iteration variable times 8 is raised to
the power of the roughness variable, and this is returned from MaxDeviation() as the
maximum deviation possible for this point. DeviatePoint() then feeds this number into
Rand(), which returns a random number between -maximum and maximum, and that
number is then added to the point’s height. Since the iteration number is decremented
by one at each recursion, smaller triangles end up with smaller deviations, at a rate
governed by the roughness variable.
The depth of recursion is given by the menu ‘Iterations’. IterCalc() must bottom
out (not recurse again) when it has recursed this many times. The traditional way to
bottom out would be to have a number representing the number of iterations left to go,
decrement that number every recursion, and bottom out when that number reaches
zero. IterCalc() does pass down a number similar to this, the iteration number used
above in MaxDeviation(), but this number always starts at the maximum number of
iterations possible so that all mountain ranges will be the same height, regardless of
how detailed they are. Rather than passing down an additional number, IterCalc() uses
a little trick. When the bottom of the recursion has been reached, the length of each
side of any triangle will be one. IterCalc() tests to see if the length of the horizontal
side of one of the subtriangles equals one, and if it does IterCalc() bottoms out.
The last step in calculating the mountains is a call to NormalizeMap(), which
scales the height of the mountain to be the height selected in the ‘Height’ menu, and also
applies the contour transformation. The contour transformation works by raising each
height to the power of the number selected in the ‘Contour’ menu. Thus, if contour is
less than one, the mountains are made more concave, while if contour is more than one,
the mountains are made more convex.
While the shape of the mountains is determined by the random deviations of the
biggest triangles, the overall outline is determined by the initial heights given to the
corners of the first two triangles. For instance, if the top right corner is given a very
high value, and the bottom left corner is given a low value, with the other corners given
intermediate values, a mountain will be generated which slopes down from the right
into the sea on the left. The menu ‘Profile’ allows selection between four combinations
of raising some corners and lowering others. CalcMountains() uses this menu selection
to give the corners their initial values.
The outcome of this whole process is an array of points, each with a certain
height, and the whole array defines the triangles which make up our mountain range.
Next we’ll give the drawing techniques necessary to turn these numbers into a pretty
picture on your screen.
Drawing Fractal Mountains
In drawing the fractal mountains, the way we color each triangle is critical, as
this is what will give a sense of height and shape to the picture. Without proper
coloring, we will just display a bunch of triangles on the screen. We also need to rotate
the mountains so that we are looking at them from near the ground, instead of from the
top in a birds-eye view (since the mountain’s x-y plane is initially the same as the
plane of the screen). In addition, we need to use a hidden surface algorithm, so that
triangles which are hidden by other triangles are not visible.
DrawMountains() is the top level function of the drawing routines. After setting
a couple variables which will be discussed later, DrawMountains() proceeds to call
DrawTriangle() with each triangle in the array. The order that it draws these triangles
is important. We are tipping the mountains backwards to give us a more interesting
view, and this tipping means that some parts of the mountain are going to obscure other
parts. We need to draw the triangles so that the obscured parts are in fact hidden from
view. DrawMountains() does this by simply drawing the triangles in back (those with
the smallest y’s) first. Then, any triangles farther forward that hide those triangles
will be drawn over them, and thus the hidden surface problem is solved.
DrawTriangle() and _DrawTriangle() are the functions which do the actual
coloring and drawing. DrawTriangle() is given the x and y coordinates of the three
points of a triangle. It then looks up the z coordinate of each of the points, and passes all
the points to _DrawTriangle(), which does the coloring and drawing. The main job of
DrawTriangle() is to perform some clipping which will be discussed a little later.
We use a fairly simple coloring algorithm. The mountains are divided into three
main colors based on height, with the brightness of the color used being determined by
the angle of each triangle with a light source. Thus all triangles below a height of 0 are
colored blue for ocean, all triangles with medium heights are colored green, and all
triangles above a certain height are colored grey (on a computer with less than 256
colors, these are different black and white patterns).
After deciding on the main color, the three points of the triangle are scaled and
rotated to find the points used in drawing the triangle. The scaling is done to account for
the size of the window and the fact that the triangles must be drawn smaller as the
number of iterations gets larger, and the points are rotated backwards for the reasons
discussed above. The routine which does this rotating and scaling is CalcPoint3(). It
does this by multiplying the point by some scaling variables and by a 3x3 rotation
matrix. The formula for rotating points in 3-space can be found in any book on graphics
(or in a textbook on vector geometry). The rotation in this example is a -70 degree
(-1.396 radian) rotation around the x-axis. The constant xTh holds the angle of
rotation in radians, and this can be changed, but if any rotation other than a 0 to -90
degree rotation around the x-axis were done, the hidden surface routine would have to
be changed, since the back to front ordering of the triangles would be different.
With the proper drawing coordinates known, a triangle is built using
Quickdraw’s polygon routines. The base color of each triangle has already been figured
out using its height. What remains is to decide how bright the color should be. This
involves a bit of vector arithmetic, which is beyond the scope of this article. We will
briefly summarize the way brightness is calculated in the following paragraph. For
those of you not wishing to try to figure out vectors, the whole calculation of brightness
can be safely thought of as a black box, without much loss of understanding. For those
of you who would like a deeper understanding, we have included a couple references at
the end of the article on vectors and computer graphics.