Graphics Reference
In-Depth Information
for(inti=0;i<3;i++) {
float delta = pObject-
>
center[i] - pTree-
>
center[i];
if (Abs(delta) < pTree-
>
halfWidth + pObject-
>
radius) {
straddle = 1;
break;
}
if (delta > 0.0f) index |= (1 << i);
// ZYX
}
if (!straddle && pTree-
>
pChild[index]) {
// Fully contained in existing child node; insert in that subtree
InsertObject(pTree-
>
pChild[index], pObject);
} else {
// Straddling, or no child node to descend into, so
// link object into linked list at this node
pObject-
>
pNextObject = pTree-
>
pObjList;
pTree->pObjList = pObject;
}
}
InsertObject()
can be changed so that whenever a child node pointer is NULL
a new node is allocated and linked into the tree, with the object inserted into this
new node.
if (!straddle) {
if (pTree-
>
pChild[index] == NULL) {
pTree-
>
pChild[index] = new Node;
...initialize node contents here...
}
InsertObject(pTree-
>
pChild[index], pObject);
} else {
...same as before...
}
If nodes should be deleted in a corresponding manner whenever they no longer
contain any objects, a pointer (or similar mechanism) is required in the node structure
to be able to access the parent node for updating. The creation of new nodes can be
delayed until a node contains
n
objects. When this happens, the node is split into
eight child nodes, and the objects are reassigned among the children. When creating
child nodes dynamically, all that is needed to build an octree incrementally is to create
the initial root node; all other nodes are created as needed. Testing a dynamic octree
