Game Development Reference
In-Depth Information
For all spatial data structures, leaves will usually be capable of carrying any num-
ber of objects. This is where bounding volume hierarchies can be useful: the group of
objects at the leaf of the BSP can be represented as a BVH:
enum BSPChildType
{
NODE,
OBJECTS
};
struct BSPChild
{
BSPChildType type;
union {
BSPNode *node;
BoundingSphereHierarchy *objects;
};
};
struct BSPNode
{
Plane plane;
BSPChild front;
BSPChild back;
};
Let's assume we have a BSP tree where objects that intersect a plane are placed in
both child nodes. In other words, one object can be at several locations in the tree.
The only collisions that can possibly occur are between objects at the same leaf in the
tree. We can simply consider each leaf of the tree in turn. If it has at least two objects
contained within it, then all pair combinations of those objects can be sent to the fine
collision detector for detailed checking.
If we place a bounding volume hierarchy at the leaves of the BSP tree, we can then
call the coarse collision detection algorithm for each hierarchy. In this case we have
two coarse collision detection steps.
If there are many objects, some large objects, or lots of partition planes, then
having an object in multiple branches of the tree can lead to huge data structures
and poor performance. The preceding algorithm can be modified to detect collisions
when overlapping objects are sent to only one child node or are held in a list with the
parent node. See Ericson [2005] for more comprehensive details.
BSP trees are common in rendering engines, and as with bounding volume hier-
archies, you may be able to use an existing implementation for your physics system.
Search Nedrilad ::




Custom Search