Friday, February 11, 2011

The Hills Are Alive! (Outdoor Terrain)

This week, I thought I'd talk about the terrain in Elpis. I like terrain! Terrain is nice!
Also, an afore warning: this post is likely to transform into a musical featuring Julie Andrews...

Implementation of Choice

The terrain implementation in Elpis can be found in an article in Game Programming Gems 6, titled "GPU Terrain Rendering" by Harald Vistnes (Chapter 5.5).  Seeing as the article in the book articulates the technique far better than I could, I will not be describing the method in detail. I will, however, skim over the implementation and record any modifications I plan to make and eventually how I intend to make them.

The general idea behind this algorithm is to provide a high detailed terrain while keeping memory and CPU requirements low, and pre-load time to a minimum. To do this, a small regular grid vertex buffer is repeatedly scaled according to the LoD (Level of Detail), morphed on the GPU according to the heightmap, positioned, and drawn.

Figure 0 - 17x7 LoD/Quadtree
The single vertex buffer used contains a 17x17 patch of vertices. As seen in figure 0, each patch of the terrain is divided into four more patches, which have been scaled to half the width and height. The division is essentially a quadtree.

The denser areas in figure 0 are one level of detail higher than the patch of lower density.

Figure 1 - Terrain

Figure 2 - Wireframe
The heightmap and normal map used for the terrain in figure 1 and 2 were borrowed from Game Programming Gems 6's CD-ROM.

Figure 1 shows the terrain in solid render mode and figure 2 is rendered in wireframe mode. In figure 2 we can see that it is a regular grid terrain implementation and there is a clear separation between terrain patches.  Along the edges of each patch, skirts are generated to cheaply and effectively eliminate cracks that occur when mixing LoDs.

Feature Lust

It is a very good terrain rendering algorithm, but the article was kept intentionally simple and featureless for ease of comprehension. For instance: it is rendered in a single (kind of ugly) colour; lighting is static; culling is minimal; and other lacking features that I can't think of right now, or that I'll describe later.

Figure 3 - Bounding Boxes
Ah yes, here's another! In figure 3, the bounding boxes for a single LoD are displayed. It's plain to see that the bounding volumes were calculated using the minimum and maximum height of the entire terrain (since they are all identical in size and align at the top), rather than that of the patch's height. In fact, the implementation uses the minimum (0) and maximum ALLOWED height (1 * MAX_HEIGHT). The bounding box is currently used for frustum culling, but can later be used for other things like collision detection.

The point of frustum culling is to cut out unseen data as early as possible, to avoid unnecessary GPU work. The tighter the fit of the bounding volumes, the more accurate the incision will be, the fewer useless draw calls are made.

Summary of feature lust: I want sweet colours and textures, fancy dynamic lighting and shading, tighter bounding volumes for frustum culling, and maybe some occlusion culling if necessary. It would also be nice to use displacement maps for terrain morphing, but I haven't a use for this yet.


You can expect posts regarding the features mentioned above to pop up every now and again. My next post will be of a more immediate feature that I have made reference to in my first post: Large world support.

Here's a small clip of the terrain in wireframe mode to show the changes in LoD:

No comments:

Post a Comment