20.3. Implementation

Now that we have discussed the internal design of RealWorldz, we can look more closely at some of the implementation details. This section covers a lot of ground: noise values and derivatives, tile sets, function trees, terrain coloring, altitude and gradient maps, lighting, and performance considerations. To fully explain the concepts, we look at specific texture examples used by some RealWorldz planets and describe some of the shader code that implements these concepts.

20.3.1. Noise Values and Derivatives

Noise textures are stored as 8-bit per-channel RGB textures, with the function value packed into the R channel, and the partial derivatives packed into the G and B channels. When a texture is read, the color components are in the range [0,1]. Noise functions range in value from -1 to 1, so unpacking the R channel from a [0,1] range to a [-1,1] range function value is done by subtracting 0.5 and then scaling by 2.0.

The range of partial derivatives varies from noise texture to noise texture, depending on the scale of the noise texture. The partial derivatives of Voronoi noise textures often have a relatively large range; linearly packing the partial derivatives causes visible artifacts on the terrain because partial derivatives of small magnitude lack precision. The work-around is to take the cube root of the partial derivatives before they are packed. This means that there is less precision loss when partial derivatives of small magnitude are stored, and more precision loss for large derivativesbut visually, it is a great improvement. The derivatives are unpacked by cubing, which is efficient and doesn't require branching. So mapping from a [0,1] range to a [r,+r] range is done by subtracting 0.5, scaling, and cubing.

Some graphics hardware can operate on vectors at the same speed as floating-point values, so it makes sense to pack the function value and derivatives into a vector. The function value is stored as the x component, with the derivatives being the y and z components. Unpacking a noise texture sample into function value and derivatives can then be done in a shader as follows:

// Initially, the vector "noise" holds a color sampled from
// a noise texture. All components are in the range [0, 1].
// The color has been implicitly converted to a vector with
// red being X; green being Y; and blue being Z.

// Subtracting 0.5 is the first step in unpacking both
// value and derivative

noise.xyz -= vec3(0.5, 0.5, 0.5);

// Component-wise multiply. Unpack the value (x) by scaling
// by 2.0. Unpack the derivatives (yz) by scaling by a
// noise texture-dependent value.

noise.xyz *= vec3(2.0, 4.566148, 4.566148);

// Component-wise multiply. Cube the y and z values to complete
// the unpacking of the partial derivatives.

noise.yz = noise.yz * noise.yz * noise.yz;

Graphics hardware that operates on vectors can perform this unpacking with one add and three multiplies.

Storing the value and derivatives as a vector has some useful advantages. First, scaling a function value by v means scaling the partial derivatives by v as well. This can be done by scaling the entire vector by v since the value and derivatives are stored as components of a vector. Second, adding two values together means adding the partial derivatives as well. This can be done simply by adding the vectors together.

20.3.2. Tile Sets

A tile set reduces the appearance of repeating patterns by pregenerating a set of n 1 x 1 tiles and selecting a random tile from that set to cover each region (u, v)(u+1, v+1) on the plane, where u and v are integers. This can be implemented in a fragment shader in the following way.

First, the tile set is packed into a texture map (see Color Plate 26A). Four tiles can be packed into a 2 x 2 arrangement; eight into a 4 x 2 arrangementany number that's the product of two powers-of-two is possible. Let this texture map be scaled up and translated so each of the tiles covers a unit square on the planethat is, the region (u, v)(u+1, v+1) for integers u and v.

The pseudorandom selection of a tile for each unit square is done as follows. Another texture map is employed, filled with random values; it is called the "offset" texture (see Color Plate 26B). It is sampled in nearest-neighbor mode and scaled up so each texel exactly overlaps a tile from the tile set texture map. The values read from the offset texture will be constant over the region of a tile; it is discontinuous only on the boundaries between tiles. As the name implies, the value read from the offset texture is used to offset the location at which the texture map containing all the tiles is sampled. The offset amount is an exact multiple of the tile size: for instance, if the tiles were packed into the texture map in a 4 x 4 arrangement, then the offset of each coordinate could be 0.0, 0.25, 0.5, 0.75,. . ..

In pseudocode, it works as follows. (Details of scaling and translating the offset and tile set texture reads so the texture maps are aligned as described above have been omitted.)

Color Plate 26 illustrates this process. Color Plate 26A shows the tile set image covering the plane, with tile edges emphasized. Color Plate 26B shows the offset texture, scaled up so that each texel exactly covers a tile. Color Plate 26C shows the tile set overlaid with the offset texture. The result of adding the tile set and the offset texture is shown in Color Plate 26Dtiles pseudorandomly scattered.

20.3.3. The Function Tree

The fragment shader code to evaluate the fractal terrain is programmatically generated from the terrain function tree. Each node in the terrain function tree becomes a procedure. A math node that sums, averages, or multiplies the values of its child nodes becomes a procedure that calls the procedures for each child, then combines those results. A distorted multifractal evaluates its child node (which defines the distortion) and applies the resulting offset to the parameter before evaluating the multifractal.

In RealWorldz, the planet artist specifies the number of octaves of noise a multifractal should use. This is different from the standard practice, where smaller and smaller octaves of noise are evaluated until they have no effect on the rendered image. Because the multifractal uses a fixed number of octaves, the code for evaluating multifractals can have the summation loop unrolled. This allows almost all the coefficients in the evaluation code to be precomputed, which is a great advantage since it avoids calls to potentially expensive functions (such as pow) in the fragment shader. Another benefit is that the code makes no use of branches or loops.

For instance, here is fragment shader code for evaluating a two-octave monofractal. Note the "Octave 0" and "Octave 1" commentsthey indicate each section of the unrolled multifractal evaluation loop. If the user specified a three-octave monofractal, another block of code to evaluate the third octave would be inserted immediately before the "Final scale and offset" comment.

The variable currHdH is a vector storing height and the two partial derivatives of height, as the x, y, and z components, respectively. The eighteen-digit numbers are precalculated values, written to 18 decimal places for precision. (Current graphics hardware supports single-precision floating-point calculations at most, but there may come a day when double precision is supported as well. It is needed to support the dynamic range necessary for modeling on a planetary scale.)

vec2  texCoord;
vec3  currHdH = vec3(0,0,0);

vec2  distParam = param;
vec3  noise;
float signal;
float increment;
vec3  newHdH;
float mfOffset= -0.200000000000000010;

// Octave 0
texCoord = (distParam * 0.005000000000000000) +
            vec2(1.090196078431372700, -0.588235294117647190);


// Sample noise texture 0 at parameter "texCoord";
// put the result into "noise"

texNT(noise, NT0, texCoord, 256);

noise     -= vec3(0.5, 0.5, 0.5);

noise.xyz *= vec3(2.0, 4.566148, 4.566148);
noise.yz   = noise.yz * noise.yz * noise.yz;
increment  = (noise.x - mfOffset) * 1.000000000000000000;
newHdH.x   = currHdH.x + increment;
newHdH.yz  = currHdH.yz + (noise.yz * 0.005000000000000000);
currHdH    = newHdH;

// Octave 1
texCoord = (distParam * 0.010000000000000000) +
           vec2 (0.949019607843137440, -0.964705882352941300);

// Sample noise texture 0 at parameter "texCoord";
// put the result into "noise"

texNT(noise, NT0, texCoord, 256);

noise -    = vec3(0.5, 0.5, 0.5);
noise.xyz *= vec3 2.0, 4.566148, 4.566148);
noise.yz   = noise.yz * noise.yz * noise.yz;
increment  = (noise.x - mfOffset) * 0.435275281648062060;
newHdH.x   = currHdH.x + increment;
newHdH.yz  = currHdH.yz + (noise.yz * 0.004352752816480621);
currHdH    = newHdH;

// Final scale and offset
float heightScale  = 1.000000000000000000;
float heightOffset = 0.000000000000000000;

HdH    = currHdH * heightScale;
HdH.x += heightOffset;

All the exponentiations have been precalculated, reducing the mathematics to multiplies and addsthis is true for the other multifractals (heterofractal and mountainfractal) as well as for the monofractal used here. The texNT function does a bilinearly filtered texture read from the appropriate noise texture and handles the additional work if a tile set is in usethat is, an additional texture read, multiply, and add.

So, the process of evaluating a multifractal has been reduced to operations for which graphics hardware is designed: 2D texture reads, multiplies, and adds. No branches are required, no slow or higher-order computations are done; and only one texture read is required per octave.

20.3.4. Terrain Color

In the preceding sections, the process for calculating the height and slope of the terrain has been described. The next step is to color and illuminate the terrain.

The standard way to color fractal terrain is to create a function involving the terrain height and slope, then add texture with multifractals. A more hardware-friendly approach was taken for RealWorldz. Here, a 3D texture is used, where each slice is a different surface typefor example, sand, grass, snow, rock, or earth. The altitude and gradient are looked up in a 2D texture map called the "altgrad" map; it selects which slice from the 3D texture to use.

Terrain with texture based on height or slope alone is very obvious; the idea behind the altgrad image was to complicate things so the texture transitions had a less obvious pattern, and to do so in a way that could be controlled by the planet artist.

For accessing the altgrad map, height is Y and gradient is X. So a low point on the terrain means a low Y; mountaintops have a high Y; a perfectly level area has X = 0; a steep slope has high X. The color obtained from the altgrad map is used as the Z component for accessing the 3D texture.

20.3.5. AltGrad Map for Snow

The altgrad map used for the Snow planet is shown as the second image in Color Plate 36A, and images of the planet are shown in Color Plate 36F, Color Plate 37E, and Color Plate 38A.

The 3D texture has only two slices; one is snow, the other gray rock. The light gray in the altgrad image selects the snowy slice; the dark gray selects the gray rock texture slice.

The light gray is restricted to the left-hand side of the image, which corresponds to flat areas. The width of the light gray area does vary slightly, but on the whole the effect is that flat terrain has snow, and areas that are too steep have bare rock. The abrupt transition between colors in the altgrad map means that there will be an abrupt change in texture.

20.3.6. AltGrad Map for AlienRockArt

The first image in Color Plate 36A is the altgrad texture used for the AlienRockArt planet, and Color Plate 36E is an image of the planet showing the rock art.

The AlienRockArt altgrad texture is the means by which the orange rock art is created. The altgrad image has three colors: very dark gray, which selects the orange slice of the 3D texture; mid-gray, which selects the white limestone texture, and light gray, which selects the brown burned-grass texture. A point on the terrain is colored orange if in this altgrad map the height and slope correspond to a point that is darkest gray. The darkest gray in the altgrad map is deliberately confined to the bottom right-hand part of the altgrad map, restricting it to lowish and steepish terrain, but the shape of the dark gray color is deliberately complex so that the resulting combinations of height and slope that yield the orange color will be too complex for a pattern to be evident. The other deliberate choice made for painting the altgrad map was to make a hard edge between the darkest gray and mid-gray colors to create a sharp division between the limestone texture and the orange texture.

The AlienRockArt planet started life as an experiment to reduce the repeating pattern of the limestone texture. Two different limestone textures were created, assigned to different slices of the 3D texture, and the altgrad map was edited so that there would be frequent transitions between two texturesthe idea being that the transitions would obscure the periodic features. To clarify where the transitions were, one of the limestone textures was colored orange, and the alien rock art pattern emerged.

The light gray region is restricted to the triangle in the upper left, indicating flat and high areas. Low areas have to be fairly flat for there to be brown grass on them; but as the terrain gets higher, the brown grass appears on progressively steeper terrain. The gentle transition from mid-gray to light gray means that there is a smooth cross-fade between the limestone and the brown grass.

The two mid-gray strokes cut into the light-gray region are responsible for the thin paths that can be seen at the boundaries of the grass.

20.3.7. AltGrad Map for DragonRidges

The altgrad map for the DragonRidges planet is the third image in Color Plate 36A, and an image of the planet is shown in Color Plate 36D. Four texture slices from this planet are shown in Color Plate 36B. From left to right, they are selected by the darkest gray to the lightest gray in the altgrad map.

The four texture slices contain a carefully painted transition from bare rock to grass. The bare rock image has subtle darkenings due to the cracks in the second texture map, and the grassy areas in the third image follow the cracks too, so features can be followed across the transitions between the different texture maps. Even the grass in the third texture matches the texture of the grass in the fourth texture.

The first texture slice has only subtle featureslighting and shadowing due to terrain shape overpowers the minor features of the texture, so it is difficult to see a repeating pattern when it is used. However, the other three texture slices have more obvious features, and so the repeating texture pattern is visible when the slices are used across a large area. The altgrad image that controls their use has been carefully painted so these textures don't cover areas large enough for the repeating pattern to be obvious.

The image of DragonRidges (Color Plate 36D) shows the complex distribution of the grass and rock. The grass is affected by the shape of the terrain: Patches of grass are bounded by changes from flat to slope, or other terrain features. The rock changes from cracked to smooth depending on exposure. These effects result from the use of small patches of color in the altgrad map: anything more than a minor change to height or slope moves the sample point out of the color patch, meaning that the texture of the ground changes in response to those minor changes in height and slope.

20.3.8. Lighting

The fragment shader has now calculated the terrain color and the partial derivatives from which the surface normal is calculated. Since the fragment shader for doing all this work is programmatically generated, it is straightforward to allow the planet artist to write custom lighting calculation code and for this code to be inserted into the fragment shader code when it is generated.

The default lighting code implements the Phong lighting equation, but since the code is specific to each planet, custom lighting effects are possible. For instance, the lighting code for the Cerberus planet (Color Plate 38B) lightens and reddens the ground color so that low-lying areas glow white-hot. The lighting code for the Tar planet adds back-lighting, to give the whitish color to the shaded sides of terrain. For the Meran planet (Color Plate 36C and Color Plate 38D), the gouges in the boulders are darkened. The lighting code for the Ring planet goes beyond just applying light effects and also calculates the base color, using the 3D texture slice as a source of noise.

Allowing users to supply their own lighting code was relatively easy to implement, but turned out to be a powerful and useful tool.

20.3.9. Performance Considerations

RealWorldz has to render terrain with a high frame rate in addition to generating the new terrain texture maps. Even with each octave requiring just one texture read and some simple mathematics and planets pared to the bare minimum number of octaves, the fragment shader takes over a thirtieth of a second to generate a new 256 x 256 texture map. A period this long is unacceptable for real-time rendering.

The solution is to spread the work of generating the new texture map across several frames by generating a subset of the new texture map during each frame. The more frames across which the work is split, the smaller the drop in frame ratebut taking longer to generate means that it will take longer before low-resolution terrain is replaced with higher-resolution terrain. In RealWorldz, the generation of each 256 x 256 texture map was spread across six frames.