Fractal Mountains

Fractal systems repeat the same type of features on smaller and smaller scales when you look closer and closer. Mountains are one example of this - a mountain range is rugged - a mountain is rugged - a valley on the mountain is rugged - and the rocks in the valley on the mountain are rugged. Such terrain can be generated by computer by starting with a few random heights and breaking the landscape down and down, making more variation as it goes. The method of this decomposition determines the overall appearance of the mountain. There are three different methods, or floor plans, presented here.

Java applet cannot run. Page banner is screenshot.

These techniques are demonstrated by this applet. Initially the mountain's first approximation is shown but by pressing return more and more detail will be revealed up to the limit of the rendering system. Choose the floor plan that you want and then explore further by moving the camera. Movement is controlled either using the arrow keys and page up/down or using the number keypad. Turing the camera can be achieved by pressing shift in combination with the normal movement keys. Pressing space will return the camera to the default position above the terrain. If the controls do not seem to be working try clicking on the applet first.

Mountain Slopes

To explain the decomposition process it is easiest to consider the one dimensional case first, let us consider a world 100 units across and 100 units high, for x and y coordinates respectively. The initial approximation to a mountain (or a slope in this case) is made by choosing two random heights in the range [0..100] on the y axis for x = 0 and x = 100. To form a more accurate model work out the current height at x = 50 and modify this by a random amount in the range [-25..25]. Next do the same for x = 25 and x = 75 using a still smaller range [-12..12].

The range through which the line should be perturbed depends on the width of the current segment, probably calculated as a simple fraction. Although this is the technique used in the demonstration above there is one problem. Here valleys and mountains are fundamentally the same, an inverted landscape which switch them around. In the real world this does not happen. To combat this the vertical range should be limited both by the width of the current segment and also the average height of the current segment.

Mountain Floor Plans

There are three floor plans in current use, they each extend the one dimensional case in their own way. First a summary diagram showing them all - triangles, squares, and hexagons - the first approximation in black and the second in blue.

Triangles have simple calculations, each side of the triangle is split half way and together these three new points split the original triangle up into four smaller triangles. However mountains created using this technique can suffer from creasing, which is visible in the demonstration above. Noticeable ridges are seen in the three triangle directions because they form early on and can never be removed by subsequent decomposition.

Squares avoids this problem to some extend by offsetting the grid during decomposition. The height of each new vertex depends on all the neighbouring vertices. For example the top-left blue vertex's height is

(9 * TL + 3 * TR + 3 * BL + 1 * BR) / 16

where TL is the top-left black vertex, and BR is the bottom-right black vertex, and so on. However the problem is still there at a lesser extent.

Hexagons finally solve the problem using a more complex system. During decomposition each hexagon is broken up into three smaller hexagon. There are no endless lines in this technique, at each decomposition they are crinkled, and no creases appear on the final mountain. The height of additional vertices for the smaller hexagons are averaged from neighbouring vertices. In the case of the central vertices there are six neighbours, for other vertices the two closest neighbours can be used or alternatively this can be expanded to six, some taken from the neighbouring hexagon.

For more detail examination the source code is available:

Hexagons are by far the most complicated of the floor plans and the current implementation has some problems. Storage is inefficient with many hexagon objects are required to represent a mountain, triangles and square need only one object no matter how detailed. Multiple hexagons each making their own calculations causes cracks appear in the mountain after only two decompositions. To prevent this in the future either vertex duplicates must be removed or some more coordinated calculation effort must be made. Beyond the third level of recursion another hexagon problem shows itself, the hexagon grid breaks down due to a flaw in the code.

Credits

Each floor plan was developed separately. Thanks to Fourier for the triangles, Miller for the squares, and Mandelbrot for the hexagons. Thanks also to Ron Poet at the University of Glasgow for covering this material in his lectures.