Game Development Reference
In-Depth Information
vertical distance is maintained. The block at the root of the max-heap is processed,
selecting the maximum-distance vertex for the final triangle mesh and subdividing
the block into four subblocks (if the vertex is interior) or into two subblocks (if the
vertexisonablockedge).
Figure10.2
showsthetypicalblockdecompositionsfor
a height field representing a surface.
The block of height-field information is a structure shown in Listing 10.3. The
block stores the bounding
-values and the location and variation of the
maximum-variation vertex for that block. The constructor is passed the bounds of
the block and the height field so that bilinear interpolation may be used to compute
variation.
Assuming a data structure
MaxHeap<Block*,float>
for the max-heap, pseu-
docode for the adaptive subdivision is shown in Listing 10.4. The max-heap struc-
ture supports an insertion and removal of blocks from the heap. Although the
variation is stored by
Block
, the max-heap knows nothing about
Block
,sothe
variation is duplicated.
x
-and
y
class Block
{
public:
Block (int hxSize, int hySize, int** heights,
int x0, int x1, int y0, int y1)
:
mX0(x0), mX1(x1), mY0(y0), mY1(y1),
mXMax(-1), mYMax(-1), mVariation(-1.0f)
{
float h00 = (float)heights[mY0][mX0];
float h10 = (float)heights[mY0][mX1];
float h01 = (float)heights[mY1][mX0];
float h11 = (float)heights[mY1][mX1];
float invDx = 1.0f/(mX1 - mX0), invDy = 1.0f/(mY1 - mY0);
for (int y = mY0; y <= mY1; ++y) {
float dy = invDy*(y - mY0), omdy = 1.0f - dy;
for (int x = mX0; x <= mX1; ++x) {
float dx = invDx*(x - mX0), omdx = 1.0f - dx;
float z = omdx*(omdy*h00+dy*h01)+dx*(omdy*h10+dy*h11);
float var = fabs(z - (float)heights[y][x]);
if (var > mVariation) {
mXMax = x;
mYMax = y;
mVariation = var;
}
}
}
}
// Block is (x,y) with x0 <= x <= x1 and y0 <= y <= y1.
int mX0, mX1, mY0, mY1;
// Maximum-variation vertex is at (xmax,ymax;variation).
int mXMax, mYMax;
float mVariation;
};
Listing 10.3.
The Block data structure.
