Queens > CISC > James Stewart > Research > Terrains

Terrain Rendering

Some of my research involves the fast and accurate rendering of terrains. Terrains can be rendered fast if occluded (hidden) parts are culled. They can be rendered accurately if a good estimate is made of the amount of light arriving at each part.

Both of these can be achieved by computing the horizon as seen from each point on the terrain. This computation is described in a paper on horizon computation in terrains.

The use of horizons for occlusion culling is described in a paper on occlusion culling in terrains.

These topics are discussed briefly below. Please see the papers for the full story.

Occlusion Culling in Terrains

A terrain is usually represented as a mesh of sample points. Occlusion culling involves detecting parts of the terrain that are hidden, in order to avoid rendering them.

This work exploits the following fact: If the current viewpoint is below the horizon of a particular sample point, then that sample point is hidden. In a preprocessing step, we compute the horizon at each sample point of the terrain. Points are grouped hierarchically (in a quad-tree) and a conservative horizon is constructed for each group.

When rendering, we determine visibility by testing the current viewpoint against the precomputed horizons. Each square block in the overhead views (shown below) was culled with a single horizon test, for a considerable savings in rendering time. The occlusion culling method works with a continuous level-of-detail representation, as shown below on the right.

large Martian terrain
A 100,000-point terrain on Mars
View from valley
on right, looking left
Levels of detail: red is finest,
then green, blue, brown, ...
Overhead view showing culled regionsLevels of detail

Better Shape Perception in Terrains

Typical geographic information systems use a point light at infinity to illuminate a terrain. The intensity of the terrain varies with the cosine of the angle between the light and the surface normal. For an overhead light, horizontal surfaces are bright and sloped surfaces are dark. This is known to provide poor 3D shape perception (e.g. a bright valley might be mistaken for a bright peak).

Better 3D shape perception is provided under ``cloudy day'' illumination, in which peaks are bright and valleys are dark. To determine the terrain intensity under this illumination, we compute the horizon at each of a large number of sample point on the terrain. At each sample point, we integrate over those directions above the horizon to determine the point's direct primary irradiance, from which a close approximation of the point's radiance is computed.

Point source at infinity
(poor shape perception)
Cloudy day
(better shape perception)

Triangle Meshing with Continuous Level of Detail

The occlusion culling work (above) has been augmented with a continuous level of detail terrain representation, based on the Siggraph'96 work by Lindstrom et al. A key contribution of their work is a triangulation method that avoids ``T vertices'' between different levels of detail and, hence, avoid gaps in the mesh. The left figure below shows the level of detail (red is finest, then green, blue, and brown) and the corresponding triangulation. The shaded, reduced-resolution terrain is shown on the right. It differs very little from the full-resolution terrain shown above on the right.

Level of detail and triangulation Corresponding image (compare with
full resolution image directly above)

Up to James Stewart's home page.