Graphics Reference
In-Depth Information
else {
// Construct and fill in 'root' of this subtree
Node *pNode = new Node;
pNode->center = center;
pNode-
>
halfWidth = halfWidth;
pNode-
>
pObjList = NULL;
// Recursively construct the eight children of the subtree
Point offset;
float step = halfWidth * 0.5f;
for(inti=0;i<8;i++) {
offset.x = ((i & 1) ? step : -step);
offset.y = ((i & 2) ? step : -step);
offset.z = ((i & 4) ? step : -step);
pNode-
>
pChild[i] = BuildOctree(center + offset, step, stopDepth - 1);
}
return pNode;
}
}
Because objects have been restricted to reside in a single cell, the simplest linked-
list solution for handling multiple objects in a cell is to embed the linked-list next
pointer in the object. For the sample code given here, the object is assumed to be
structured as follows.
struct Object {
Point center;
// Center point for object
float radius;
// Radius of object bounding sphere
...
Object *pNextObject;
// Pointer to next object when linked into list
};
The code for inserting an object now becomes:
void InsertObject(Node *pTree, Object *pObject)
{
int index = 0, straddle = 0;
// Compute the octant number [0..7] the object sphere center is in
// If straddling any of the dividing x, y, or z planes, exit directly
