Game Development Reference
// We need to recalculate our bounding volume.
// Otherwise we need to work out which child gets to keep
// the inserted body. We give it to whoever would grow the
// least to incorporate it.
if (children->volume.getGrowth(newVolume) <
At each node in the tree we choose the child whose bounding volume would be
least expanded by the addition of the new object. The new bounding volume is cal-
culated based on the current bounding volume and the new object. The line between
the centers of both spheres is found, as is the distance between the extremes of the
two spheres along that line. The center point is then placed on that line between the
two extremes, and the radius is half the calculated distance. Figure 12.6 illustrates this
Note that the combined bounding sphere encompasses both child bounding
spheres: it is not normally the smallest sphere that encloses the child objects. We suf-
fer this extra wasted space for performance reasons. To calculate the bounding sphere
around two objects, we need to get down to the nitty-gritty of their geometries. This
makes the process too slow for in-game use.
We can perform a similar algorithm to remove an object. In this case it is useful to
be able to access the parent node of any node in the tree. Therefore we need to extend
the data structure holding the hierarchy, like this:
Excerpt from include/cyclone/collide_coarse.h
* A base class for nodes in a bounding volume hierarchy.
* This class uses a binary tree to store the bounding volumes.