See also an overview of my work with terrains.
Fast terrain rendering is required in flight simulators and in some video games. When rendering a terrain, the greatest time is spent sending polygons down the graphics pipeline, where they are transformed, clipped, rasterized, shaded, textured, and z-buffered.
I'm working on hierarchical visibility, an acceleration technique that efficiently culls terrain regions that are not visible from the current (moving) viewpoint. It avoids altogether the overhead of sending these regions down the graphics pipeline. The hierarchical visibility technique has been implemented in a multiresolution terrain rendering algorithm.
A 100,000-point terrain (400 x 250) is shown below from various viewpoints. Polygon counts and rendering times are described with and without hierarchical visibility. The rendering times are from a 166 MHz Pentium PC running Linux and Mesa (an OpenGL implementation).
The left image is the rendered terrain, as seen from the viewpoint. The right image is an overhead view showing the parts of the terrain that are rendered. Each empty square region was eliminated with a single visibility test.
With multiresolution rendering, more distant parts of the terrain are rendered at a coarser resolution, using larger polygons that cover more of the terrain. Colour in the right image corresponds to resolution, where red denotes 1-by-1 squares, green denotes 2-by-2 squares, and blue denotes 4-by-4 squares. In the second and third examples below, the viewing frustum is shown with two lines and the viewpoint lies at the vertex of the frustum.
| An overhead view. Most of the terrain is visible, so there's not much acceleration. Note, however, that the visibility tests are extremely cheap. With visibility testing: 22072 polygons in 3.3 seconds. Without visibility testing: 22744 polygons in 3.4 seconds. | |
|
|
| A view from the bottom looking along a valley toward the top. Note that large hidden regions are eliminated in large blocks, each block only requiring a single visibility test. With visibility testing: 8019 polygons in 1.1 seconds. Without visibility testing: 23445 polygons in 2.8 seconds. | |
|
|
| A view from the right side looking along a valley toward the left. With visibility testing: 11093 polygons in 1.4 seconds. Without visibility testing: 20984 polygons in 2.6 seconds. | |
|
|
The effectiveness of hierarchical visibility varies with the amount of occlusion, just as one would expect. Hierarchical visibility is particularly effective when the viewpoint is in a valley whose walls occlude large parts of the terrain. This is a good technique to accelerate simulations of low-level flying, driving, and walking over a terrain.
Hierarchical visibility tests are extremely fast, so there is no risk that hierarchical visibility will noticably slow down the rendering process and that there is a very good chance that it will speed up the rendering process considerably.
More details are available in the paper.
Back to James Stewart's home page