Gamasutra - Features "Dynamic Level of Detail Terrain Rendering with Bézier Patches"


				\|\|\|\|

By Mike Rayner
[Author's Bio]
Gamasutra
March 21, 2002

Introduction

Level of Detail System

Conclusions and Further Work

	Printer Friendly Version

This feature originally appeared in the proceeding of Game Developers Conference 2002

2002 GDC Proceedings
CD-ROM
Price: $150.00 + S&H

This feature originally appeared in the proceeding of Game Developers Conference 2002

2002 GDC Proceedings
CD-ROM
Price: $150.00 + S&H

Letters to the Editor:
Write a letter
View all letters

Features

Dynamic Level of Detail Terrain Rendering with Bézier Patches

Level of Detail System

To create an image that most accurately represents the terrain surface as described by the artist we want to evaluate the curved surfaces to a high level of detail. If all patches are tessellated to the same degree then we will generate just as much polygonal detail for far away patches as we do for close up patches. The total number of polygons that the hardware is required to render in most cases will limit us to a lower geometric resolution than we would like. With an LOD system we render polygon detail only where it is required. The results are near identical quality with fewer polygons to render. Unfortunately if all patches are not evaluated to the same degree, seams and "tearing" will be seen between the patches. The result is quite unacceptable for the quality expected of modern video games. The goal is to tessellate patches to different degrees without generating seems.

The algorithm presented here ensures that no tears or seams are created between neighbouring patches with different tessellation levels. The only constraint is that patches must have at least C⁰ continuity with their neighbours. C⁰ continuity requires that neighbouring patches share control points along the boundary connecting them. Note that C¹ continuity is required for smooth lighting and physics calculations between patches but is not required for the LOD algorithm to work.

With these constraints in place the run time evaluation of the terrain will not need to be aware of neighbouring information to produce a seamless tessellation of the entire terrain with changing LOD. Most other algorithms that fix the "cracking" problem require neighbour information and usually a second pass in order to correct errors. The evaluation of the Bézier polynomial can be performed using various methods depending on the implementer's preference. There are many methods of evaluating equation 4 such as direct evaluation, forward differencing, and recursive subdivision. The evaluation method chosen to implement this system is not important.

A run time heuristic is used to determine the tessellation level of each of the four boundary curves of the Bézier patch. If each boundary curve requires the same level, then the entire patch is uniformly tessellated to the same degree. If the 4 boundary levels differ, then a non-uniform patch is generated. The number of edge vertices generated is directly a function of the boundary edge heuristic. As such the number of vertices on the boundary of two patches is always the same so long as C⁰ edge continuity exists. The "cracking" problem is reduced to ensuring that a non-uniform patch does not create any inner cracks or seems while retaining the number of edge vertices as determined by the boundary heuristic.

A non-uniform patch is treated as a uniform inner patch connected to the edge vertices with 4 triangle strips. Let the number of points per edge be specified clockwise as E0, E1, E2, and E3 respectively. The resolution of the inner patch is then defined as NxM where N = max(E0,E2)-2 and M = max(E1,E3)-2. This choice for NxM conservatively rounds up the degree of the inner patch to highest boundary degree both vertically and horizontally. The 4 strips generated are created from boundary edge vertices and the perimeter inner mesh vertices. S0=strip(E0,Nl), S1=strip(E1,Mt), S2=strip(E2,Nr), S3=strip(E3,Mb). See Figure 2.



	Figure 2: Non-uniform mesh evaluation

The LOD heuristic is chosen as a function of distance from the camera position C_pos. A minimum LOD_min and maximum LOD_max boundary evaluation is chosen. A distance from the camera for minimum Dist_near and maximum Dist_far level of detail is chosen. Only the end control points of each edge p₀ and p₁ are used to determine the degree evaluation.

For speed the dist function is actually chosen as the squared distance as apposed to the square root. For a visible distance of 500 meters the near distance would be something like 25 meters and the far lets say 250 meters. All boundary edges at 25 meters or closer will have maximum detail. All boundary edges at 250 meters or farther will be minimum level of detail. If we choose a good distance range relative to average patch edge length and only a few different LOD levels then most patches will be uniformly tessellated with non-uniform patches existing as a row of patches connecting different uniform levels of detail at a fixed radius to the camera.

More exotic heuristics can be chosen that take into account things like edge or patch curvature, however one must be careful to ensure that the heuristic exhibits good hysteresis so that patches do not fluctuate between different LODs giving away the effect.

______________________________________________________

Conclusions and Further Work