Code:
void CTerrain::BuildQuadTree(TerrainPatch *pNode,
float Width,
float wx,
float wz,
float wx2,
float wz2)
{
float patch_width = (wx2 - wx);
float radius = fabs(patch_width * 0.5f);
pNode->bound_sphere.m_Radius = radius;
D3DXVECTOR3 vecPatchPos;
vecPatchPos.x = (wx + wx2) * 0.5f;
vecPatchPos.y = 0.0f;
vecPatchPos.z = (wz + wz2) * 0.5f;
pNode->bound_sphere.m_vecPos = vecPatchPos;
pNode->patchID = addPatchPos(vecPatchPos,pNode);
m_num_nodes++;
if (patch_width == Width)
{
pNode->isLeaf = true;
m_num_patches++;
return;
}
pNode->isLeaf = false;
float midwx = (wx2 + wx) * 0.5f;
float midwz = (wz2 + wz) * 0.5f;
pNode->NW = new TerrainPatch();
pNode->NW->patch_direction = NORTH_WEST;
pNode->NW->Parent = pNode;
BuildQuadTree(pNode->NW,Width,wx,wz,midwx,midwz);
pNode->NE = new TerrainPatch();
pNode->NE->Parent = pNode;
pNode->NE->patch_direction = NORTH_EAST;
BuildQuadTree(pNode->NE,Width,midwx,wz,wx2,midwz);
pNode->SW = new TerrainPatch();
pNode->SW->Parent = pNode;
pNode->SW->patch_direction = SOUTH_WEST;
BuildQuadTree(pNode->SW,Width,wx,midwz,midwx,wz2);
pNode->SE = new TerrainPatch();
pNode->SE->Parent = pNode;
pNode->SE->patch_direction = SOUTH_EAST;
BuildQuadTree(pNode->SE,Width,midwx,midwz,wx2,wz2);
pNode->NW->E_id = pNode->NE->patchID;
pNode->NW->S_id = pNode->SW->patchID;
pNode->NE->W_id = pNode->NW->patchID;
pNode->NE->S_id = pNode->SE->patchID;
pNode->SW->N_id = pNode->NW->patchID;
pNode->SW->E_id = pNode->SE->patchID;
pNode->SE->W_id = pNode->SW->patchID;
pNode->SE->N_id = pNode->NE->patchID;
}
That's the code for building the quad tree.