Graphics Reference
In-Depth Information
// No collision
return 0;
}
}
// Now at a leaf, inside/outside status determined by solid flag
return node-
>
IsSolid();
}
Unfortunately, there are (at least) two problems with this solution. First, as a
boundary test this will not detect a collision if the AABB ends up fully encompassing
some small free-floating part of the solid represented by the BSP tree. Second, this
test is quite expensive, as it may have to perform up to six subqueries to determine
the query result (and even more for general polytopes).
The first objection can be addressed by representing the query volume as a solid
BSP tree and then testing if the intersection of the two trees is empty through the set
operations on BSP trees described in [Thibault87]. However, intersecting BSP trees
against each other does not really address the second objection.
A more interesting approach is to attempt to form a new BSP tree that represents
the expanded volume corresponding to the Minkowski sum of the AABB and the
original BSP tree [Melax00]. Testing a stationary AABB against the original BSP tree is
now just a point query against the new
expanded
tree. (The expanded tree is sometimes
also called a
bloated
,or
grown
, tree.) Similarly, the intersection of a moving AABB
against the original tree becomes a ray test against the new tree. In both cases, the
query on the tree now corresponds to a problem already solved.
The expanded volume can, in part, be formed by offsetting all planes in the original
BSP tree outward along their normals by the radius
r
of the AABB (with respect to
the plane normal). If the stored plane equation at a tree node is given by
n
·
X
=
d
,
the offset plane is obtained by adding
r
to the
d
-term:
n
·
X
=
d
+
r
. The projected
radius
r
itself is given by
e
1
n
y
+
r
=
e
0
|
n
x
| +
e
2
|
n
z
|
,
where
e
0
,
e
1
, and
e
2
are the half-extents of the AABB and
n
=
(
a
,
b
,
c
) is the normal
of the stored plane equation (see Section 5.2.3).
However, although offsetting the existing planes in the BSP tree is necessary it is
not sufficient. As the rightmost drawing of Figure 8.17 illustrates, the resulting volume
extends too far at the vertices (and, in 3D, at the edges), causing false collisions in
these regions. To obtain the correct result, additional
beveling planes
must be added to
the new tree so that when offset with the other planes they help form the Minkowski
sum between the BSP tree and the AABB (Figure 8.18).
To see what additional planes are needed, note first that due to being the inter-
section of a number of halfspaces the volume described by a solid leaf of a solid BSP
