Game Development Reference
In-Depth Information
void PartitionVertices (const set<Vertex2>& vertices,
int hxSize, int hySize, vector<vector<Vertex2>>& tiles)
{
int numXTiles = hxSize/256, numYTiles = hySize/256;
int numTiles = numXTiles*numYTiles;
tiles.resize(numTiles);
set<Vertex2>::iterator iter = vertices.begin();
set<Vertex2>::iterator end = vertices.end();
for (
/**/
; iter != end; ++iter) {
Vertex2 v = *iter;
float xNT = v[0]*numXTiles, yNT = v[1]*numYTiles;
float xFTile = xNT/hxSize, yFTile = yNT/hySize;
int xITile = (int)xFTile, yITile = (int)yFTile;
int i = xITile + numXTiles*yITile;
bool onXEdge = (xFTile-xITile == 0.0f) && xITile > 0;
bool onYEdge = (yFTile-yITile == 0.0f) && yITile > 0;
bool onBoth = (onXEdge & onYEdge);
tiles[i].push_back(v);
if (onXEdge) { tiles[i-1].push_back(v); }
if (onYEdge) { tiles[i-numXTiles].push_back(v); }
if (onBoth)
{ tiles[i-1-numXTiles].push_back(v); }
}
}
Listing 10.5.
Partition the vertices to prepare for fast Delaunay triangulation
results together. The final triangulation is not necessarily the Delaunay triangu-
lation of the original set of vertices, but the quality was sucient for the game
application.
Experimentation showed that the performance was reasonable when the domain
of the height field was divided by 256 in each dimension; that is, the array of tiles had
hxSize/256
columns and
hySize/256
rows. The pseudocode for the partitioning
is shown in Listing 10.5. The
if
-tests ensure that vertices on the boundaries of the
tiles are inserted into all the vertex arrays that share those boundaries.
10.2.4 Processing Tiles
Delaunay triangulation must be applied to each tile, followed by stitching together
all the triangulations. High-level pseudocode for this is contained in Listing 10.6.
The input to
ProcessTiles
is the set of vertices (road and height field) and
the array of tiles. The output is an array of unique terrain vertices,
terrVertices
.
The array
terrIndices
contains triples of indices into
terrVertices
.Ifthereare
T
,thetri-
angle's two-dimensional vertices are given by
terrVertices[terrIndices[3*t+j]
for 0
triangles in the mesh,
terrIndices
has 3
×T
indices. For such an index
t
2. The output array
terrAdjacencies
contains triples of triangle
indices. Triangle
≤ j ≤
t
has up to three edge-adjacent neighbors. If there is a neighbor
