This chapter describes the well known midpoint
displacement algorithm and how it can be used to create mountain silhouettes and also
3D mountains. Height, roughness and sea levels are also introduced. Lastly, new methods
such as negative slopes and extended size of the
mountain will be explained.
Benoit Mandelbrot was the first to introduce this technique. This has also been described by [6, 7] and by Paul Bourke  who has also done a lot of interesting related work.
Mandelbrot used the example of a coastline to explain fractals and
fractal geometry. The idea is that the coastline will look generally the same independent
of the distance from which the coastline is observed.
The coastline in Figure 11 could represent a view from five inches
or five miles above. He also described a way to model this phenomenon, where he started
with a straight line and broke that line into two jointed lines with a random angle
between them. Each of the two new lines are in turn broken into yet two more lines and so
on. This technique was used to model a coastline, but with some modifications this
technique can also be used to model a mountain, as also suggested by Mandelbrot.
The technique for modeling mountains requires the usage of the
middle point in between the endpoints instead of an arbitrary point along the line between
the points. This is shown in Figure 12, and works as follows: Start
off with a straight line (Step 1). The midpoint of this line is moved straight up or down
a random distance thus creating two new straight lines (Step 2). The midpoint of each new
line is again moved straight up or down by a random distance (Step 3). This process is
repeated a number of times until the mountain silhouette has a satisfactory resolution.
The maximum displacement has to be decreased after every step, otherwise the surface will
be very rough. Maximum displacement will normally be set between 0.4 and 0.95 times its
previous size after each iteration where half the size gives a very smooth curve, and 0.95
a very rough curve. This parameter is called the roughness parameter. The number of
vertices will be 2n+1, where n is the number of iterations.
It is possible to set a sea level so that all points below that
level will form a sea.
The advantage of moving the midpoint straight up or down is that the
node number gives the position in one dimension and the height for that node gives the
position in the other dimension. This is very memory efficient. If no restraints are made
on memory usage it is possible to move the midpoint in a random direction and distance,
thus allowing for negative slopes. This will be discussed in greater depth later on.
There are two efficient methods that can be used to create 3D mountains using midpoint displacement.
It is possible to use recursive functions in both
cases. The figure below shows recursive square subdivision.
Recursive square subdivision pseudo code:
Subdivide(X1, X2, Y1, Y2)
if max. subdivision is not reached
The overhead is quite large when the above recursive subdivision is
used. We have instead used a method where every loop calculates all possible midpoints
using the set of line segments already calculated. This must be done in two passes when
using the square subdivision. In the first pass, the midpoint of all horizontal and
vertical lines are displaced yielding two new lines each (Figure 15
column a), just as in the example of 2D midpoint displacement. If lines are drawn between
all points that have been defined so far a check pattern appears as shown in Figure 15 column a. In pass two, the midpoint of each square is
displaced from the four points surrounding it in horizontal and vertical direction (Figure 15 b). It is also possible to displace the point from the average
of the surrounding eight points (See dotted arrows in Figure 15 Loop
1 (b)), weighting them according to the distance from the intersection point. This is
useful when a smooth surface is desired which otherwise tends to look a bit boxy (i.e. the
shorelines will go either in a horizontal or vertical direction, not diagonally). Note
that all the displaced midpoints are used in later iterations to create new displaced
midpoints. The displacement of the first points will therefore have the most important
impact on the shape of the mountain.
Subdivision of triangles is made in three passes. The midpoints for
lines in the three different directions are calculated in each pass. This technique is
better when steep slopes are desired because every midpoint is calculated as the average
of only two endpoints, giving more freedom of changes in the vertical direction.
When the final mountain is displayed, the squares or triangles are
projected onto the viewplane. To improve speed, each square can be divided into two
triangles (Figure 19). This way all triangular surfaces are flat. If a perspective
projection is created the triangles at the back should be displayed first. The triangles
that are closer to the viewpoint are projected later (back to front projection scheme).
This way no Z-buffering is necessary as the hidden surfaces are overwritten when triangles
are projected in back to front manner.
All we need to control the mountain generator is: the original maximum displacement and the roughness parameter after each loop. The first few points (the four corners and the center for example) can also be taken as an input in order to gain more control of the surface generation. These vertices will therefore not be calculated using the midpoint displacement technique.
It is not possible to get vertical or negative slopes of the
mountain wall, since the midpoint is only moved vertically. This may still give good
results in most cases, but an extension of this method allows negative slopes to be
generated. First a random direction and distance are generated. Instead of moving the
midpoint straight up or down as described previously, the midpoint is moved over the
randomized distance in the randomized direction as shown in Figure 21.
This means that the 3D position must now be stored, instead of just the height for each
node, increasing the memory usage. This technique gives an uneven rate of nodes over the
surface. The maximum displacement is determined by the length of the edge from which the
midpoint is displaced from (See Figure 21) times the roughness
parameter. The maximum displacement factor must be multiplied with a roughness parameter
with a value between 0.4 and 0.95 just as in the previously described technique.
The extended size technique is based on the fact that it is possible
to set the height of the points along the borders of a surface before the rest of the
mountain is calculated. The reason is that the points along the border are not affected by
any other points on the surface. The points along one border are all midpoint
displacements from other points on the same border (except for the corner points that are
set from the beginning). First, we calculate one mountain surface and display it on the
screen. The memory storing the height map of the mountain can be recycled after the
mountain has been displayed on the screen. If the mountain is extended to the right the
height information about the right border (from the first mountain) is copied to the left
border (used for the second mountain) and the rest of the height map matrix is cleared.
The right border of the first mountain that was created and displayed will now be
identical to the left border of the new mountain, and they can be pasted together.
This process can be repeated as many times as wanted. To expand the
mountain model in the direction from the horizon towards the viewpoint, the height values
of the border closest to the viewpoint must be stored in an array. When a new row of
surfaces is calculated, the top border of heights is copied from the array for each
mountain square before the rest of the mountain matrix is generated. When the mountain is
displayed on the screen, the border closest to the viewpoint is copied to the array (shown
by dark lines in Figure 23). The right and left borders are copied as described above.
The best way to control the main structure of the mountain is to specify the height of the corners in the mountain matrices. The mountains can become very tall and valleys can become very deep if this is not done.
Maximum displacement and roughness parameter are the only parameters that are needed. It is possible to specify the initial height at as many points of the surface as desired and therefore good control of the shape of the mountain can be obtained. Sea level, color and the number of iterations can also be set by the user.
The mountains that are generated normally look too bare to fool the audience. When the mountain is "clothed" by placing 3D vegetation and is surrounded by water, the image will look honorably realistic.
The mountain can be scaled in the y-direction by changing the maximum displacement parameter. The roughness of the surface is set by the roughness parameter as shown in Figure 20. The overall shape of the mountain can also be set by specifying the heights of a set of points.
The speed of this algorithm depends mainly on the type of shading algorithm and how fast the scene can be drawn on the screen. The calculation for creating the scene by itself is very fast (i.e. it takes less than 10% of the time it takes to draw the scene on the screen on a normal PC).