The Terraformer - Project Overview

1 Introduction

Computer generated terrains can be very striking and they are surprisingly easy to do. Most of us have seen some kind of randomly generated terrain of one form or another, but here is something that I'll bet you haven't seen: a program that generates an entire world and allows you to zoom in to any point as if you were standing there, all at interactive speeds. Terra is an unusual terrain generator in two important ways. First, it generates terrains on triangles, not squares, so the terrains can easily be mapped to the surface of a sphere. Second, it allows an extremely wide range of magnifications, from a few feet to many thousands of miles. (Can you tell I'm proud of it? The only thing comparable that I have seen is the "Genesis planet" sequence in Star Trek II: The Wrath of Kahn .)

I must apologize in advance for the sparseness of this page. I realize that it would benefit from some nice diagrams and more careful explanations, but prudence demands that I focus my current energies on other projects.

2 Terrain Generation

Here I give a quick intro to the terrain generation methods used in Terra . For a more detailed explanation, you might look in Chaos and Fractals, New Frontiers of Science by Peitgen, Juergens, and Saupe (Springer-Verlag, New York 1992), which I used as a reference.

2.1 Why Triangles?

Terrain generators for games often build their terrains on rectangular domains, even when these terrains are to be mapped to the surface of a sphere. When this mapping is done, the surface looks normal around the equator, and is horribly warped toward the poles. This is because there is no easy way to map a rectangular domain to the surface of a sphere.

If we use triangles instead of rectangles, the problem changes. We can create a sphere by linking together 20 triangles into an icosohedron, and subdividing each of these into smaller triangles. This does not get rid of the warping problem completely (with this method, triangles toward the center of the first triangle are a bit larger than the ones toward the vertices) but warping is so minimal that it is more or less undetectable.

2.2 Brownian Motion Applied to Terrains

Most terrain generators are based on brownian motion. When we look at a plot of brownian motion with time along an x axis and displacement along a y axis, we get something which looks vaguely like terrain. Generating brownian motion is easy. Given two points in time, connect them with a straight line and find the midpoint. Then displace this point's y value by a gaussian random number (with a carefully chosen mean) and repeat as many times as you like. I use a method like this for generating my terrains. Given three points on a surface joined in a triangle, find and displace 3 midpoints. This gives us a subdivision method for creating 4 smaller triangles from a single triangle.

Another important part of how I generate terrain is keeping a random seed at each vertex. When a new vertex is added, it gets a seed which is derived from the vertices on either side. This means that no matter which part of the terrain you happen to be looking at, you are guarenteed that it lines up with terrain generated in other parts. For each line joining two triangles Points on that line will always be generated the same way, no matter which triangle we subdivide.

2.3 The Four Refinement Stages

Simple brownian motion creates terrain that is way too erratic and doesn't look much like terrain when we zoom in. In order to get realistic terrain, we have to play with the parameters quite a bit. There is a huge design space here. I chose to do subdivision in 4 basic phases, starting with the initial 20 faces of the icosohedron. In the first phase (the first three steps) we assign a gaussian random altitude with a unit variance, and there is no relation between neighboring vertices. This gives a completely random spread over the first few vertices.

The next phase covers the next 5 steps. At the beginning of this phase, we assign to each vertex a mean which is its altitude. We then subdivide by assigning to new vertices a new mean which is equal to the averate of the means of its neighbors, plus some gaussian random jitter (with more jitter if the mean is high). THEN we compute an altitude which is a gaussian displacement from that mean. the variance for this displacement is keyed off of the mean. This has the effect of making the terrain much more jagged where the mean is high (making mountains) and smooth where the mean is low (making the terrain level off into the ocean).

In the third phase, we proceed with standard brownian subdivision, in which midpoints are displaced by a gaussian random number, and the variance for this number goes down by 1/2 at each step. The initial variance is close to 0 if the terrain is close to sea level, and rises to 1/4 in the mountains. This helps to keep the terrain smoother toward the ocean, and gives us well-behaved mountains. This phase continues for the next 8 steps.

The final 8 steps cover the generation of only about 250 feet of terrain, and need to be much less rugged than the surrounding terrain or the ground will look like it is covered with spikes. In the final phase, we reduce the variance by 1/4 at each step, and this smooths out the terrain to something reasonable in the last few steps.

There are a few drawbacks of this method. The biggest problem is with the second phase, which adds jitter to the terrain. Because this jitter is added to existing terrain, and can cause considerable changes, features will often "pop" into view all of a sudden. This discontinuity can be distracting. Also, because the smoothness of the terrain variations are closely tied to the subdivision level, the terrain tends to look "triangular" when viewed straight down, i.e. The major features tend to fall in a triangular pattern. In practice, this is not to distracting. There are many ways to address these problems, but most of them are terribly complicated. The question of how to manage subdivision remains an open problem.
*

3 The Interface

The rendering system I use to display these terrains was built with Mesa (a public-domain version of OpenGL) and GLUT on a Unix (HP-UX) system. The interface is basically a fly-through with an optional info bar that gives a key for interpreting the colors, current latitude, longitude, altitude, and speed. The user flies toward/away from a point on the screen, or rotates in place. There are also controls for speeding up or slowing down, and for increasing or decreasing the level of detail. All of these features are pretty much what you'd expect. The interesting part is how the surface itself is rendered.

3.1 Subdivision is Your Friend

If an edge of a top level triangle represents about 4000 miles, and an edge of a bottom level triangle is about a foot, we need only 25 levels of refinement from the top level to the bottom level. Fortunately, 25 is not a very large number of recursive calls to make, so this subdivision method gives us a very simple rendering algorithm. Every time the planet needs to be displayed, test each top level triangle against the view frustum. For those that intersect, see if the projected area of the triangle is smaller than some threshold. If it is, render it. If not, subdivide and repeat. This algorithm gets rid of unneeded detail very quickly. Even when we are hovering just over the surface, the time needed to do this subdivision is much, much less than the time needed to scan-convert all the triangles.

3.2 Pitfalls

This interface is not without it's problems. Here are a few of the more dramatic ones.

3.2.1 Disappearing Terrain

It's sometimes possible for some terrain feature to take up a lot of projected area on the screen at deep levels of refinement and almost no area at shallow levels. A mountain, for example, may poke up into the view frustum even though the triangle it grew from is nearly parallel to the view direction. But, since we do not subdivide a triangle if it just misses the view volume at a SHALLOW level of refinement, that mountain may disappear suddenly because of a decision made way up the tree. This causes some terrain features to occasionally blink in and out of view. This can be very distracting, and it's hard to predict when it will happen. There are no good ways to fix it that I know of. Everything I have tried to fix the problem causes an explosion in the number of subdivisions that makes the system hang.

3.2.2 Numerical Precision

Most rendering libraries use 32-bit precision floating point numbers to do calculations, but that does not give sufficient detail to render objects on the scale of feet alongside objects on the scale of a few thousand miles. This requires that we either do something sneaky to join different scales or, do our own view transformations in double-precision, converting to single-precision only at the last step. The second is much easier, and that is the road I take in the program. There can still be problems, however, if we are not careful about setting the front and back clipping planes. If we always include the entire world, then the z-buffer will not have enough precision to distinguish objects. We must be careful to scale down the depth of the view volume as more detail comes into view.

3.2.3 Cracks

It is a natural feature of this algorithm that triangles of one level of refinement will be drawn next to triangles at a deeper level of refinement. Since the altitude of a point is displaced when it is refined, this means it is possible that the triangles will not appear to line up, and we will see cracks in the surface. This is VERY distracting.

I deal with this problem by stitching back together the triangles so that they all line up before rendering them. Each seam between triangles is examined, and if a crack is present, the larger triangle is subdivided and moved slightly to fill the crack. This adds additional triangles and processing time, resulting in a 30% performance hit, which is why the feature can be turned off. The results are very good, though, as the pictures show. * Without Crack Removal * With Crack Removal

4 Results and Future Improvements

Despite the problems mentioned, I believe this method of generating terrain shows great promise. There are ways of dealing with most of the probems this structure causes, and it is sufficiently general to allow all sorts of extensions. Performance is also pretty good. On my HP workstation with no graphics hardware, I get about a frame every 1/5 seconds without crack removal, or every 2 seconds with crack removal. I admit that it is a stretch to call these "interactive speeds" but since most of the processing time seems to be taken by the renderer, it is likely that this speed could improve greatly with some rendering hardware.

There are many ways to improve the generation of continents, such as generating explicit tectonic plates and subdividing their silhouette as we recurse down the tree. We could also keep terrain types around each vertex, allowing us to vary altitude, variance, or even color with terrain type. We could even go so far as to specify where trees on the surface lie. The possibilities are truly endless. Where I go with this in the future will probably depend on who expresses and interest in which features.

5 Acknowledgements

I must thank my brother, Rhett Davis , who guided me through the mathematics of terrain generation and provided me with a set of random number generator functions. He was also my inspiration... which is always invaluable. Also, many, many, MANY thanks go to Laura Downs , who was always cool on the side when I got frantic, and gave me a LOT of great ideas (the entire view-frustum-intersection/subdivision scheme grew out of a number of her suggestions). Thanks Laura.