3D Graphic Java: Render fractal landscapes

Get a behind-the-scenes look at 3D graphics rendering with this hands-on discussion of fractals, quaternion transformations, shadows, rasterization, and Gouraud shading

By Merlin Hughes, JavaWorld.com, 08/01/98

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

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

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:

1. We first assign a random height to the four corner points of a grid.
   
   
2. 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.)
   
   
3. 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.
   
   
4. 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ⁿ <= perturbation <= roughnessⁿ. 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ⁿ+1 x 2ⁿ+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

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.

public class Triangle {
  private int[] i = new int[3];
  private int[] j = new int[3];
  private Triple n;
  private RGB[] rgb = new RGB[3];
  private Color color;
  public Triangle (int i0, int j0, int i1, int j1, int i2, int j2) {
    i[0] = i0;
    i[1] = i1;
    i[2] = i2;
    j[0] = j0;
    j[1] = j1;
    j[2] = j2;
  }
}

Our Triangle datastructure stores each vertex as an index (i,j) into the gridpoints of our terrain, along with normal and color information that we will fill in later. We create our array of triangles with the following piece of code:

int numTriangles = (steps * steps * 2);
Triangle[] triangles = new Triangle[numTriangles];
int triangle = 0;
for (int i = 0; i < steps; ++ i) {
  for (int j = 0; j < steps; ++ j) {
    triangles[triangle ++] = new Triangle (i, j, i + 1, j, i, j + 1);
    triangles[triangle ++] = new Triangle (i + 1, j, i + 1, j + 1, i, j + 1);
  }
}

We'll look shortly at how to actually render these triangles onto the screen. But first, some lighting issues.

Lighting and shadows

We'll do two things to spruce this up. First, we'll add ambient and diffuse light sources so that elements of our landscape are lit according to their orientation relative to the sun. Then, we'll add shadows so that virtual matter actually impedes the progress of virtual photons.

Lighting
As you recall, we thoroughly covered ambient and diffuse lighting in June's article. In a nutshell, if a diffuse (matte) surface is facing a light source, the amount of reflected light will be proportional to the cosine of the angle of incidence of the light on the surface. Light falling directly on a surface will be strongly reflected; light falling at an oblique angle will be weakly reflected. In addition, all surfaces will be evenly lit by an amount of ambient, directionless light.

We will apply this simple lighting model to our terrain. One option is to take each point on the terrain and compute whether the point is facing the sun, and if so, what the angle of incidence is; the cosine of the angle of incidence is equal to the dot product of the terrain normal and sunlight direction. Of course, doing this for every point in the scene is rather expensive. Instead, we'll perform this calculation once for every triangle. The result should be plenty good enough.

Unlike my last article, we'll consider the sun to be a point this time around. Let's forget that it's about 100 times the size of the earth and allow it to be positioned anywhere in the scene. First, we'll compute a vector from the sun to our terrain:

Free Download - 5 Minute Product Review. When slow equals Off: Manage the complexity of Web applications - Symphoniq

Free Download - 5 Minute Product Review. Realize the benefits of real user monitoring in less than an hour. - Symphoniq