3D computer graphics have many uses -- from games to data visualization, virtual reality, and beyond. More often than not, speed is of prime importance, making specialized software and hardware a must to get the job done. Special-purpose graphics libraries provide a high-level API, but hide how the real work is done. As nose-to-the-metal programmers, though, that's not good enough for us! We're going to put the API in the closet and take a behind-the-scenes look at how images are actually generated -- from the definition of a virtual model to its actual rendering onto the screen.

We'll be looking at a fairly specific subject: generating and rendering terrain maps, such as the surface of Mars or a few atoms of gold. Terrain-map rendering can be used for more than just aesthetic purposes -- many data-visualization techniques produce data that can be rendered as terrain maps. My intentions are, of course, entirely artistic, as you can see by the picture below! Should you so desire, the code that we will produce is general enough that with only minor tweaking it can also be used to render 3D structures other than terrains.

Click here to view and manipulate the terrain applet.

In preparation for our discussion today, I suggest that you read June's "Draw textured spheres" if you haven't already done so. The article demonstrates a ray-tracing approach to rendering images (firing rays into a virtual scene to produce an image). In this article, we'll be rendering scene elements directly onto the display. Although we're using two different techniques, the first article contains some background material on the `java.awt.image`

package that I will not rehash in this discussion.

## Terrain maps

Let's start by defining a

*terrain map*

. A terrain map is a function that maps a 2D coordinate

*(x,y)*

to an altitude

*a*

and color

*c*

. In other words, a terrain map is simply a function that describes the topography of a small area.

Let us define our terrain as an interface:

public interface Terrain { public double getAltitude (double i, double j); public RGB getColor (double i, double j); }

For the purpose of this article we will assume that *0.0 <= i,j,altitude <= 1.0*. This is not a requirement, but will give us a good idea where to find the terrain that we'll be viewing.

The color of our terrain is described simply as an RGB triplet. To produce more interesting images we might consider adding other information such as the surface shininess, etc. For now, however, the following class will do:

public class RGB { private double r, g, b; public RGB (double r, double g, double b) { this.r = r; this.g = g; this.b = b; } public RGB add (RGB rgb) { return new RGB (r + rgb.r, g + rgb.g, b + rgb.b); } public RGB subtract (RGB rgb) { return new RGB (r - rgb.r, g - rgb.g, b - rgb.b); } public RGB scale (double scale) { return new RGB (r * scale, g * scale, b * scale); } private int toInt (double value) { return (value < 0.0) ? 0 : (value > 1.0) ? 255 : (int) (value * 255.0); } public int toRGB () { return (0xff << 24) | (toInt (r) << 16) | (toInt (g) << 8) | toInt (b); } }

The `RGB`

class defines a simple color container. We provide some basic facilities for performing color arithmetic and converting a floating-point color to packed-integer format.

## Transcendental terrains

We'll start by looking at a transcendental terrain -- fancyspeak for a terrain computed from sines and cosines:

public class TranscendentalTerrain implements Terrain { private double alpha, beta; public TranscendentalTerrain (double alpha, double beta) { this.alpha = alpha; this.beta = beta; } public double getAltitude (double i, double j) { return .5 + .5 * Math.sin (i * alpha) * Math.cos (j * beta); } public RGB getColor (double i, double j) { return new RGB (.5 + .5 * Math.sin (i * alpha), .5 - .5 * Math.cos (j * beta), 0.0); } }

Our constructor accepts two values that define the frequency of our terrain. We use these to compute altitudes and colors using `Math.sin()`

and `Math.cos()`

. Remember, those functions return values *-1.0 <= sin(),cos() <= 1.0*, so we must adjust our return values accordingly.

## Fractal terrains

Simple mathematical terrains are no fun. What we want is something that looks at least passably real. We could use real topography files as our terrain map (the San Francisco Bay or the surface of Mars, for example). While this is easy and practical, it's somewhat dull. I mean, we've

*been*

there. What we really want is something that looks passably real

*and*

has never been seen before. Enter the world of fractals.

A fractal is something (a function or object) that exhibits *self-similarity*. For example, the Mandelbrot set is a fractal function: if you magnify the Mandelbrot set greatly you will find tiny internal structures that resemble the main Mandelbrot itself. A mountain range is also fractal, at least in appearance. From close up, small features of an individual mountain resemble large features of the mountain range, even down to the roughness of individual boulders. We will follow this principal of self-similarity to generate our fractal terrains.

Essentially what we'll do is generate a coarse, initial random terrain. Then we'll recursively add additional random details that mimic the structure of the whole, but on increasingly smaller scales. The actual algorithm that we will use, the Diamond-Square algorithm, was originally described by Fournier, Fussell, and Carpenter in 1982 (see Resources for details).

These are the steps we'll work through to build our fractal terrain:

We first assign a random height to the four corner points of a grid.

We then take the average of these four corners, add a random perturbation and assign this to the midpoint of the grid (

*ii*in the following diagram). This is called the*diamond*step because we are creating a diamond pattern on the grid. (At the first iteration the diamonds don't look like diamonds because they are at the edge of the grid; but if you look at the diagram you'll understand what I'm getting at.)We then take each of the diamonds that we have produced, average the four corners, add a random perturbation and assign this to the diamond midpoint (

*iii*in the following diagram). This is called the*square*step because we are creating a square pattern on the grid.- Next, we reapply the diamond step to each square that we created in the square step, then reapply the
*square*step to each diamond that we created in the diamond step, and so on until our grid is sufficiently dense.

An obvious question arises: How much do we perturb the grid? The answer is that we start out with a roughness coefficient *0.0 < roughness < 1.0*. At iteration *n* of our Diamond-Square algorithm we add a random perturbation to the grid: *-roughness ^{n} <= perturbation <= roughness^{n}*. Essentially, as we add finer detail to the grid, we reduce the scale of changes that we make. Small changes at a small scale are fractally similar to large changes at a larger scale.

If we choose a small value for *roughness*, then our terrain will be very smooth -- the changes will very rapidly diminish to zero. If we choose a large value, then the terrain will be very rough, as the changes remain significant at small grid divisions.

Here's the code to implement our fractal terrain map:

public class FractalTerrain implements Terrain { private double[][] terrain; private double roughness, min, max; private int divisions; private Random rng; public FractalTerrain (int lod, double roughness) { this.roughness = roughness; this.divisions = 1 << lod; terrain = new double[divisions + 1][divisions + 1]; rng = new Random (); terrain[0][0] = rnd (); terrain[0][divisions] = rnd (); terrain[divisions][divisions] = rnd (); terrain[divisions][0] = rnd (); double rough = roughness; for (int i = 0; i < lod; ++ i) { int q = 1 << i, r = 1 << (lod - i), s = r >> 1; for (int j = 0; j < divisions; j += r) for (int k = 0; k < divisions; k += r) diamond (j, k, r, rough); if (s > 0) for (int j = 0; j <= divisions; j += s) for (int k = (j + s) % r; k <= divisions; k += r) square (j - s, k - s, r, rough); rough *= roughness; } min = max = terrain[0][0]; for (int i = 0; i <= divisions; ++ i) for (int j = 0; j <= divisions; ++ j) if (terrain[i][j] < min) min = terrain[i][j]; else if (terrain[i][j] > max) max = terrain[i][j]; } private void diamond (int x, int y, int side, double scale) { if (side > 1) { int half = side / 2; double avg = (terrain[x][y] + terrain[x + side][y] + terrain[x + side][y + side] + terrain[x][y + side]) * 0.25; terrain[x + half][y + half] = avg + rnd () * scale; } } private void square (int x, int y, int side, double scale) { int half = side / 2; double avg = 0.0, sum = 0.0; if (x >= 0) { avg += terrain[x][y + half]; sum += 1.0; } if (y >= 0) { avg += terrain[x + half][y]; sum += 1.0; } if (x + side <= divisions) { avg += terrain[x + side][y + half]; sum += 1.0; } if (y + side <= divisions) { avg += terrain[x + half][y + side]; sum += 1.0; } terrain[x + half][y + half] = avg / sum + rnd () * scale; } private double rnd () { return 2. * rng.nextDouble () - 1.0; } public double getAltitude (double i, double j) { double alt = terrain[(int) (i * divisions)][(int) (j * divisions)]; return (alt - min) / (max - min); } private RGB blue = new RGB (0.0, 0.0, 1.0); private RGB green = new RGB (0.0, 1.0, 0.0); private RGB white = new RGB (1.0, 1.0, 1.0); public RGB getColor (double i, double j) { double a = getAltitude (i, j); if (a < .5) return blue.add (green.subtract (blue).scale ((a - 0.0) / 0.5)); else return green.add (white.subtract (green).scale ((a - 0.5) / 0.5)); } }

In the constructor, we specify both the roughness coefficient `roughness`

and the level of detail `lod`

. The level of detail is the number of iterations to perform -- for a level of detail *n*, we produce a grid of *(2 ^{n}+1 x 2^{n}+1)* samples. For each iteration, we apply the diamond step to each square in the grid and then the square step to each diamond. Afterwards, we compute the minimum and maximum sample values, which we'll use to scale our terrain altitudes.

To compute the altitude of a point, we scale and return the *closest* grid sample to the requested location. Ideally, we would actually interpolate between surrounding sample points, but this method is simpler, and good enough at this point. In our final application this issue will not arise because we will actually match the locations where we sample the terrain to the level of detail that we request. To color our terrain, we simply return a value between blue, green, and white, depending upon the altitude of the sample point.

## Tessellating our terrain

We now have a terrain map defined over a square domain. We need to decide how we are going to actually draw this onto the screen. We could fire rays into the world and try to determine which part of the terrain they strike, as we did in the previous article. This approach would, however, be extremely slow. What we'll do instead is approximate the smooth terrain with a bunch of connected triangles -- that is, we'll tessellate our terrain.

*Tessellate: to form into or adorn with mosaic (from the Latin* tessellatus*).*

To form the triangle mesh, we will evenly sample our terrain into a regular grid and then cover this grid with triangles -- two for each square of the grid. There are many interesting techniques that we could use to simplify this triangle mesh, but we'd only need those if speed was a concern.

The following code fragment populates the elements of our terrain grid with fractal terrain data. We scale down the vertical axis of our terrain to make the altitudes a bit less exaggerated.

double exaggeration = .7; int lod = 5; int steps = 1 << lod; Triple[] map = new Triple[steps + 1][steps + 1]; Triple[] colors = new RGB[steps + 1][steps + 1]; Terrain terrain = new FractalTerrain (lod, .5); for (int i = 0; i <= steps; ++ i) { for (int j = 0; j <= steps; ++ j) { double x = 1.0 * i / steps, z = 1.0 * j / steps; double altitude = terrain.getAltitude (x, z); map[i][j] = new Triple (x, altitude * exaggeration, z); colors[i][j] = terrain.getColor (x, z); } }

You may be asking yourself: So why triangles and not squares? The problem with using the squares of the grid is that they're not flat in 3D space. If you consider four random points in space, it's extremely unlikely that they'll be coplanar. So instead we decompose our terrain to triangles because we can guarantee that any three points in space will be coplanar. This means that there'll be no gaps in the terrain that we end up drawing.