Game Development Reference
In-Depth Information
10
Shape-Preserving Terrain
Decimation and Associated Tools
David Eberly
10.1 Introduction
I worked on a truck-racing game with large terrains, each level approximately 3 miles
by 3 miles in size.
1
The game shipped on Xbox 360 and Playstation 3. Level artists
initially created each terrain as a height field by painting a 2K-by-2K, 16-bit TIFF
image, each texel value representing the terrain height. A regular tessellation of
the grid using two triangles per texel produces 8M triangles, which is too many
triangles to draw per frame. We wanted a decimation algorithm that would give
us a greatly reduced number of triangles yet still preserve the general shape of the
terrain. Our target was 2.5 percent of the full count, which is approximately 200K
triangles. The first portion of this article is a discussion about the algorithm I
developed to solve this problem. The shape-preserving heuristic was a good one,
although we settled for a slightly larger percent, and the algorithm was not too
complicated.
The level artists created lofted roads (the racing tracks) using a plugin for 3D
Studio Max and stitched them into the terrain mesh. Each lofted road was itself
a height field—a quad strip with two triangles per quad. When stitched into the
terrain, the road was required to conform to the shape of the terrain. This meant
that any terrain vertices covered by a road needed to be inherited by the road
geometry, and the texture coordinates for the lofted road had to be interpolated
to generate texture coordinates for the inherited vertices. This process is tedious
and time consuming, especially given that the artists iterated frequently, making
modifications to the decimated terrain and to the roads. We wanted a tool that
would automate this process. The second portion of this article is a discussion
about the tools to support the automation. They involve constrained Delaunay
triangulation for the automated stitching and some detailed programming to handle
1
Baja: Edge of Control
, by 2XL Games Inc, THQ publisher (2008)
127
