In my previous article ("Bringing Mars Down to Earth with Java3D," JDJ, Vol. 9, issue 6), readers were expected to download hundreds of megabytes of Mars data to enjoy the Java3D example. This requirement challenged even the cable modem bunch ambitious enough to get the source code in the first place. This time it's definitely different. This time, the code generates the landscapes so all you have to download is the source. We'll cover the foundational Java3D data structures suitable for terrains, and how to completely generate landscapes with fractals. (The source code for this article can be downloaded from www.sys-con.com/java/sourcec.cfm.)

Laying the Foundation
When you first started programming in Java, you may have started with the infamous "Hello World" example to introduce yourself to the basics of Java programming. In similar fashion, this article covers the basics of creating a Java3D terrain world and explores the possible approaches to creating that world.

Modeling Height Fields
No terrain article would be complete without at least a passing reference to height fields. Just in case you're new to terrain rendering, height fields or height maps represent a regular grid of longitude, latitude, and altitude values for a landscape. Interpreting these values and rendering them quickly with the right colors and lighting is at the core of rendering terrains (see Figure 1).

Each cell corner in the grid represents an altitude at a longitude and latitude location on a map. These values can be used to create three-dimensional points in the Java3D world. The longitude is mapped to the x-axis, the latitude to the z-axis, and the altitude to the y-axis. We can use a QuadArray as our first simple approach to modeling a height field in Java3D.

The QuadArray Class
The QuadArray class is one of several GeometryArray subclasses provided by Java3D to create geometries. The QuadArray class is for rendering a group of quadrilaterals by specifying the corners of each quadrilateral. This is exactly how we described a height field earlier. The secret to using a QuadArray class is how you specify the corners of the quadrilaterals (see Figure 2).

The cell corners in the height field grid can be implemented as the corners of the quadrilaterals in the Quad-Array. The corners must be specified in a counterclock-wise order. The first corner is not important, and neither is the order of the quadrilaterals. The HelloWorld example code starts in the lower left-hand corner for both. The result of running the HelloWorld example is shown in Figure 3.

The examples in this section use hard-coded values for the height field and are implemented in the getHeightField() method. The geometry-building code in the HelloWorld example is shown in Listing 1.

This example uses the GeometryInfo utility class to make using the QuadArray easier. The inner loop assigns the coordinates of one square of the height field in a counterclockwise order while also mapping the points to the Java3D coordinate system.

This approach is fine for learning but has a few drawbacks.

1.  A grid corner can be included in the coordinates array up to four times as separate copies of the same point. This approach is fine for small landscapes but will burn through memory for larger terrains. Solving this with indexed geometry arrays will be covered later in this article.

2.  While some terrain complexity reduction algorithms use quadrilaterals, most use triangles. Since we want to eventually get to build large-scale terrains and your 3D video card is optimized to render triangles, we should start thinking in terms of triangles.

3.  The Java3D specification states that quadrilaterals must be planar or the results are undefined. The example makes no attempt to make the quadrilaterals planar and it might be difficult to make natural-looking terrains with them. While I haven't experienced any problems using nonplanar quadrilaterals, triangles are a safer route in the long term.

The TriangleArray Class
The TriangleArray class is another GeometryArray subclass provided by Java3D to create geometries. The TriangleArray class is for rendering a group of triangles by specifying the corners of each triangle (see Figure 4).

Once again, the starting corner and the order of the triangles are not important. The corners must be specified in a counterclockwise order. The HelloWorld2 example implements the same terrain as HelloWorld but uses a TriangleArray with the GeometryInfo class.

The geometry-building code in the HelloWorld2 example is shown in Listing 2. (Listings 2-8 can be downloaded from www.sys-con.com/java/sourcec.cfm.) The inner loop assigns the coordinates of two triangles for each square of the height field similar to the previous example. Note that the number of coordinates is higher with a TriangleArray compared to a QuadArray for the same regular grid of height data. While we want to use triangles, this approach uses even more memory than the QuadArray.

The TriangleStripArray Class
The TriangleStripArray class is an interesting GeometryArray subclass provided by Java3D to create geometries. The TriangleStripArray class is for rendering a series of triangles that share edges in a grouping called a strip. A strip of triangles is formed by specifying the corners of a triangle based on the last two corners of the previous triangle. A picture really helps to understand this one, so refer to Figure 5.

The first triangle is formed with corners (1,0), (0,0), and (1,1). The second triangle shares the hypotenuse with the first triangle and is formed with corners (0,0), (1,1), and (0,1). Notice how the last two corners of the first triangle are the same as the first two corners of the second triangle? Java3D takes advantage of this pattern and shares the corners so that only one additional corner is required to specify the next triangle. In the HelloWorld3 example, this continues across the row until the right edge of the height field. At this point the series of corners have specified a strip of triangles and the process is repeated for the next row.

The geometry-building code in the HelloWorld3 example is shown in Listing 3. Using a TriangleStripArray requires additional information about the strips. Java3D needs to know the number of strips and the number of corners included in each strip. The number of strips is based on the size of the strip count array and the values in the array are the number of corners.

An advantage of using a TriangleStripArray is that it uses less coordinate memory than the other geometry array approaches. In addition, OpenGL is able to directly render a triangle strip array with a single call to the video card. DirectX must render each triangle individually, requiring multiple trips to the video card.

Using a TriangleStripArray does not require that the strips be organized as in the example. This was done simply for convenience and simplicity. As long as adjacent triangles share corners, you can theoretically create one long strip for your entire landscape.

The TriangleFanArray Class
Java3D provides one last option called the TriangleFan-Array. There are several terrain simplification algorithms that substantially reduce the number of triangles used to render the landscape. The reduction is achieved by varying the size of the triangles to make the view "good enough," as measured by different metrics. While these algorithms are beyond the scope of this article, it should be noted that the TriangleFanArray is especially well suited for rendering multiresolution triangulations.

Reducing Memory Burn
All of the geometry arrays explored thus far have used instances of Point3f to specify coordinates and they often represent the same 3D point several times. This approach could be optimized for large terrains if we could eliminate the use of Point3f and share the 3D points somehow.

Java3D includes additional versions of the geometry arrays called indexed geometry arrays. Once you understand how to use regular geometry arrays, the indexed counterparts are easy to understand. The indexed geometry array lets you specify the corners of the height field once and refer to them through an index. The index is used to specify which corner to use for the triangle or triangle strips (see Figure 6).

For this variety of index geometry arrays, the memory savings is realized at the shared corners where the strips touch. HelloWorld4 is a version of HelloWorld3 converted to use an IndexedTriangleStripArray. This example also eliminates the use of Point3f objects to further save memory.

The geometry-building code in the HelloWorld4 example is provided in Listing 4. In this example, the coordinates do not use Point3f objects but a float value for each of the x, y, and z values. A loop populates the coordinate array with the values for each corner in the height map. Next, the indices array is populated with the index of the corner in the coordinates array. Using an index eliminates duplicate point data. The final difference is the setting of the coordinate indices on the GeometryInfo object.

The Java3D API provides several options for modeling height fields. Using indexed geometry arrays saves memory and triangle strip arrays lets your video card render your landscape quickly.

Fractal World, Fractal World, Excellent!
You have probably heard of fractals and may have found them a bit mysterious or unapproachable. I'll demystify fractal concepts and show how you can shape them into realistic terrains (see Figure 7).

Overview
Since Beniot Mandelbrot discovered fractals over 20 years ago, many variations have been described in research papers and textbooks. The computer graphics community has come to use the term to mean anything that has a high degree of self-similarity. A self-similar object can be translated, rotated, and scaled to a subportion of itself. This concept is best described by an example called the von Koch snowflake (see Figure 8).

The von Koch snowflake is created by repeatedly replacing each line segment with a scaled-down version of the previous step. This is done by replacing each line segment in the current step with an exact copy of the previous step, scaled down by a factor of three. This process is repeated a number of times to create a self-similar snowflake. Replacing a portion of the shape with a scaled version of the previous step is the key concept behind fractals. How can fractals be applied to terrains?

Compare the ragged edges of a rock and the shapes of cliffs and mountaintops and you may observe self-similarity in nature. Because many natural forms such as plants and rocks seem to be self-similar, fractals have been used as a way to model these forms. Several fractal approaches have been used that all roughly fall into a category called fractional Brownian motion (fBm):

• Poisson faulting: The original terrain rendering approach subsequently improved by other approaches
• Fourier filtering: A complex interpretation of a Fourier transform of Gaussian white noise
• Successive random additions: A flexible and easy-to-implement subdivision scheme
• Midpoint displacement: An easy-to-understand and implement approach described in detail below
• Noise synthesis: The state of the industry in terrain generation

Midpoint Displacement
Fournier, Fussell, and Carpenter developed a way to generate fractal mountains based on a recursive subdivision. To better understand this approach, we'll first go over the one-dimensional example shown in Figure 9.

We start with a line segment of unit length along the x-axis. In the second step, we divide the line segment into two equal halves and move the mid-point in the y direction. There are two line segments and in the next step they are divided and their mid-points moved in the y direction (up or down). This process is repeated a number of times to achieve the desired effect. How much should the midpoints be moved? The algorithm determines this by averaging the y values of the line segment end points and adding a random perturbation:

xnew = 1/2(xi + xi+1), ynew = 1/2(yi + yi+1) + P(xi+1 - xi)R

where P() is a perturbation based on the length of the line segment and R is a random number between zero and one. In our case, the perturbation is called the roughness of the terrain. As long as the iterations gradually reduce the roughness, we can achieve self-similarity in the result. Applying this midpoint displacement algorithm to height fields allows us to create fractal mountain ranges. An extension of this algorithm is called the diamond-square algorithm.

The Diamond-Square Algorithm
The diamond-square algorithm gets its name from the imaginary shapes that result from the iterative midpoint displacement. This will become apparent as we walk through the algorithm. This terrain algorithm is similar to many in that it depends on the ability to split a line and have the result land squarely on a corner in the height field. To accomplish this feat, we must restrict the height field to be a square having 2n + 1 corners per side. The value of n determines how many iterations of midpoint displacement are possible, so we call this value the level of detail. A level of detail of three requires nine corners per side of the height map. For our example a level of detail of two will suffice for simplicity.

The steps in the diamond-square algorithm are:

1.  Initialize the roughness.

2.  Initialize the height field corners to form an imaginary square.

3.  For each level of detail, do the following:

• Diamonds step: Assign a height to the center of each square by averaging the height of each corner and displacing the result based on the roughness and a random number. This results in imaginary diamond shapes.
• Squares step: Assign a height to the center of each diamond by averaging the height of each corner and displacing the result based on the roughness and a random number. This results in imaginary square shapes.
• Scale down the roughness.

A Java3D Example
The FractalWorld example generates random fractal terrains with the diamond-square algorithm. This example is largely based on previous examples using the TriangleStripArray so we won't cover the geometry aspect of this example. The main generation loop is contained in the getHeightField() method shown in part in Listing 5.

This code implements the steps described above considering the boundary conditions of the height field. The diamonds step is straightforward:

private void diamond(
    float[][] terrain,
    int x,
    int y,
    int side,
    float roughness) {
    if (side > 1) {
        int half = side / 2;
        float sum = 0f;
        sum += terrain[x][y];
        sum += terrain[x + side][y];
        sum += terrain[x + side][y + side];
        sum += terrain[x][y + side];
        float average = sum / 4.0f;
        terrain[x + half][y + half] =
            average + random() * roughness;
    }
}

The boundary conditions become more of a concern for the squares step since a diamond may extend beyond the physical dimensions of the height field (see Listing 6).

When a diamond corner is outside of the height field, this implementation simply does not consider it in the average calculation. Another option that I have seen in other implementations is to wrap the diamond to the other side of the height field and use a substitute corner in the average calculation.

Running the Example
When running the FractalWorld example, use the keyboard bindings shown in Table 1 to fly through the world.

The main() method sets up the roughness and level of detail. I've found that a roughness between 0.35 and 0.55 subjectively looks the best. The level of detail has a drastic effect on the results. A value of 8 seems to be a good balance between realistic results and speed. When running the example, you'll see colors on the landscape roughly corresponding to elevation. This is done with a Java3D feature called vertex coloring.

Vertex Coloring
In the HelloWorld examples, we used the ambient color in the material object to specify the color of the shape. This provides a convenient way to uniformly color a Java3D shape. Java3D also allows each corner of the triangles in the scene to have its own color. It combines the color of the material with the smoothly interpolated corner colors to produce the overall triangle color.

Figure 11 shows the results of running the SimpleVertexColoring example. Each corner is assigned a different color and Java3D takes care of the rest. The portion of the example that assigns the colors is shown in Listing 7.

This listing uses black as the ambient color of the triangle, making the vertex colors dominate. Note that the coordinates and colors use objects instead of indexes. As we discussed in Reducing Memory Burn, a large terrain should use indexed coordinates. Java3D also allows us to index colors in a similar manner and is demonstrated in the FractalWorld example.

Vertex Coloring in FractalWorld
This example uses elevation-based colors to approximate a more natural-looking landscape. The 27 colors were arrived at by trial and error with the help of a color utility. There is nothing significant about the number of colors I chose to use; I was looking for gradual changes from one elevation to the next.

A scene like Figure 12 has over 131,000 triangles so it's a good idea to conserve memory by indexing coordinates and colors. Colors are defined once and the color indices are built for each coordinate.

float[] colors = getElevationColors();
gi.setColors3(colors);
int[] colorIndices = getElevationColorIndices(hf);
gi.setColorIndices(colorIndices);

The getElevationColors() method defines the colors and they're set on the GeometryInfo object. Because the example uses a TriangleStripArray, the color indices are built similar to the coordinate indices (see Listing 8).

The values in the height field range from 0 to 100 (lowest to highest) and the colors are defined from highest to lowest. The NUMBER_OF_COLORS static variable is used to calculate the index of the color based on the elevation.

Conclusion
After running the FractalWorld example a few times you may notice that terrain roughness does not vary much. It would be nice if the beaches and hills were smoother than the mountains. If you are interested in solving the terrain roughness issues here are a few tips. The algorithm presented here is technically a monofractal, meaning that the fractal has a single uniform fractal dimension. An approach to varying the roughness of the terrain is called multifractals. You should have enough knowledge now to research multifractals and implement them in Java3D (see Figure 13). Have fun!

Acknowledgments
Thanks to my friend Jeff Ryan and my son Ryan for reviewing my JDJ articles.

References

Copyright 2004 ? Mayo Foundation for Medical Education and Research