Graphics Reference
In-Depth Information
(a)
(b)
Figure 8.17
(a) An AABB query against the original intersection volume. (b) To allow the
AABB query to be replaced by a point query, the planes of the halfspace intersection volume
are offset outward by the radius of the AABB (as projected onto their plane normals) to form
an expanded volume. However, this alone does not form the proper Minkowski sum, as the
offset shape extends too far at the corners, causing false collisions in these regions.
Beveling
planes
(a)
(b)
Figure 8.18
(a) To form the Minkowski sum of the intersection volume and the AABB, addi-
tional beveling planes must be added to the BSP tree. (b) The planes after offsetting correspond
to the shape formed by sweeping the AABB around the boundary of the intersection volume.
tree corresponds to a convex polyhedron. Therefore, the AABB query on the BSP tree
can be seen as intersection tests between the AABB and the polytopes “stored” in
the solid leaves.
For a given AABB polytope test, the separating-axis test specifies exactly which axes
must be tested to determine if a collision has occurred. The planes of the polytope,
as stored in the BSP tree, correspond to the separating axes of the polytope faces.
The missing beveling planes are therefore those corresponding to the separating axes
of the AABB faces and those corresponding to the cross product of edges from the
AABB and edges from the polytope.
