Game Development Reference
In-Depth Information
the inheritance of vertices and texture coordinate generation. As always, technical
problems occurred during the development, and artists are fond of requesting new
features. The article contains some discussion about these problems and features.
For a good survey of decimation algorithms, including those useful for level of detail,
see [Luebke et al. 03]. Methods for decimating terrain may be found at The Virtual
Terrain Project [Collaborators 10].
10.2 The Decimation Algorithm
The level artists, of course, had full control over the painting of the 2K-by-2K TIFF
image. In addition, they specified parameters that would control the decimation.
These included a vertex budget, which by default was approximately 100K (to
produce approximately 200K triangles), and the width and height of a texel, which
were each approximately 8 feet. The vertex budget included road vertices as well
as any terrain vertices, so if a level had a large number of roads, the budget was
usually chosen to be larger than the default.
10.2.1 Initial Vertex Selection
The terrain tool maintained a set of vertices to be used for a triangle mesh repre-
senting the terrain plus roads. All the road vertices were inserted first because, as
in all racing games, the roads are what the player sees the most, and you want all
the detail you can get for them. However, our game had a free-roaming mode that
allowed players to explore the level, so the terrain needed reasonable detail even in
regions far from the roads.
The pseudocode assumes two data structures,
Vertex2
which represents a pair
of
float
coordinates, and
Edge2
which contains a pair of
Vertex2
objects. The
vertex coordinates are in units of image indices (from 0 to 2048). Each road consists
of an array of
Edge2
objects that delimit its boundaries. Listing 10.1 contains the
pseudocode for inserting the road vertices into the set of vertices that will be used
for the final terrain mesh.
Pseudocode for the initial vertex selection from the height field is given in List-
ing 10.2. The first two inputs are the number of columns of the height image and
the number of rows of the height image. The height image values are stored as a
two-dimensional array. The next two parameters are the width and height of the
initial blocks (in units of number of texels). The last parameter is the set of ver-
tices to be used in the final triangle mesh. The set of vertices is nonempty on input
because it contains all the road vertices that are required to be in the final mesh.
The incoming height field is of size 2
n
×
2
m
rather than (2
n
+1)
(2
m
+ 1), so the
×
x
-maximum vertices must be handled separately. This requires
using one less than the
hxSize
and
hySize
values for the coordinate values. The
element
InitialHeightVertices
chooses a low-resolution regular grid of vertices
-maximum and
y
