Game Development Reference
In-Depth Information
void AdaptiveQuadtreeDecomposition (int hxSize, int hySize,
int** heights, int dx, int dy, int vertexBudget ,
set<Vertex2>& vertices)
{
MaxHeap<Block*,float> heap;
Block* b;
int x, y;
for (y = 0; y < hySize - dy; y += dy) {
for (x = 0; x < hxSize - dx; x += dx) {
b = new Block(hxSize,hySize,heights,x,x+dx,y,y+dy);
heap.Insert(b,b->mVariation);
}
b = new Block(hxSize,hySize,heights,x,x+dx-1,y,y+dy);
heap.Insert(b,b->mVariation);
}
for (x = 0; x < hxSize - dx; x += dx) {
b = new Block(hxSize,hySize,heights,x,x+dx,y,y+dy-1);
heap.Insert(b,b->mVariation);
}
b = new Block(hxSize,hySize,heights,x,x+dx-1,y,y+dy-1);
heap.Insert(b,b->mVariation);
while (vertices.size() < vertexBudget && heap.size() > 0) {
heap.Remove(b);
int x0 = b->mX0, x1 = b->mX1, y0 = b->mY0, y1 = b->mY1;
int xmax = b->mXMax, ymax = b->mYMax;
delete b;
vertices.insert(Vertex2(xmax,ymax));
if (x1 - x0 > 1 && y1 - y0 > 1) {
b = new Block(hxSize,hySize,heights,x0,xmax,y0,ymax);
heap.Insert(b, b->mVariation);
b = new Block(hxSize,hySize,heights,x0,xmax,ymax,y1);
heap.Insert(b, b->mVariation);
b = new Block(hxSize,hySize,heights,xmax,x1,y0,ymax);
heap.Insert(b, b->mVariation);
b = new Block(hxSize,hySize,heights,xmax,x1,ymax,y1);
heap.Insert(b, b->mVariation);
}
}
while (heap.size() > 0) { heap.Remove(b); delete b; }
};
Listing 10.4.
The adaptive quadtree decomposition.
10.2.3 Partitioning Vertices
A Delaunay triangulation may be applied directly to the set of vertices ob-
tained from the functions
InsertRoadVertices
,
InitialHeightVertices
,and
AdaptiveQuadtreeDecomposition
. However, even at the targeted 200K trian-
gles, the number of triangles is large enough that the Delaunay triangulation is
quite slow. The performance was improved by partitioning the vertices into small
subsets, applying a Delaunay triangulation to each subset, and then stitching the
