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.

  1. Previous work

  2. Benoit Mandelbrot was the first to introduce this technique. This has also been described by [6, 7] and by Paul Bourke [8] who has also done a lot of interesting related work.

  3. Fractals in nature

  4. 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.

    fig11.gif (650 bytes)

    Figure 11: Coastline, seen from five inches or five miles?

    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.

  5. Midpoint displacement

  6. 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.

    fig12.gif (2592 bytes)

    Figure 12: Generations of midpoint displacement fractal mountain silhouette.

    It is possible to set a sea level so that all points below that level will form a sea.

    fig13.gif (998 bytes)
    Figure 13: Sea level.

    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.

  7. Third dimension

  8. There are two efficient methods that can be used to create 3D mountains using midpoint displacement.

    1. Square subdivision
    2. Triangular subdivision

    It is possible to use recursive functions in both cases. The figure below shows recursive square subdivision.

    fig14.gif (4336 bytes)

    Figure 14: Recursive square subdivision.

    Recursive square subdivision pseudo code:

    Subdivide(X1, X2, Y1, Y2)

    if max. subdivision is not reached
       Midpoint displace top and left edge plus center of current square
       Subdivide(X1, X2/2, Y1, Y2/2) //Top left square
       Midpoint displace right edge of current square
       Subdivide(X2/2, X2, Y1, Y2/2) //Top right square
       Midpoint displace bottom edge of current square
       Subdivide(X1, X2/2,Y2/2, Y2) //Bottom left square
       Subdivide(X2/2, X2,Y2/2, Y2) //Bottom right square
    } else return

    end Subdivide

    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.

    fig15.gif (4527 bytes)

    Figure 15: Two pass square midpoint displacement.

    Figure 16: Creation of a mountain.

    Figure 17: Mountain

  9. Triangular subdivision

  10. 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.

    Figure 18: Triangular subdivision.

    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.

    fig19.gif (1644 bytes)

    Figure 19: Dividing each square into two triangles.

    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.

  11. A new way of generating Negative Slopes using random values

  12. 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.

    Figure 20: Mountains with roughness parameter of (a) 0.55 (b) 0.65 (c) 0.80

    fig21.gif (2729 bytes)

    Figure 21: Mountain silhouette with a negative slope.

    The memory usage becomes a problem when detailed surfaces are to be generated. Already when a matrix of 1024*1024 is used and the height is stored in one byte, 1 Mb of memory is required. It is however, possible to calculate one part of the whole area at a time if certain rules are obeyed. In this case this algorithm will only require a fraction of the memory that is used with the previously described technique.

  13. A new method for mountains: Extended size

  14. 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.

    fig22.gif (1778 bytes)

    Figure 22: Expanding a mountain model horizontally by copying one border.

    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.

    fig23.gif (4425 bytes)

    Figure 23: Top down view. Expanding mountain model in the horizontal plane using height arrays.

    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.

    You must have a Java enabled browser to see this.

    Figure 24: Large area of mountains.

  15. Evaluation

  16. 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).


anarule.gif (1534 bytes)


naprev_cmp.gif (1754 bytes)nahome_cmp.gif (1799 bytes)naup_cmp.gif (1668 bytes)nanext_cmp.gif (1698 bytes)