Graphics Reference
In-Depth Information
P
O
t
min
t
max
t
P
Ot
t
min
t
max
P
O
t
max
t
min
t
P
O
t
min
t
max
t
Figure 8.16
The four cases encountered when intersecting the active section of the ray
against a plane (the plane shown in gray).
8.4.3
Polytope Queries on Solid-leaf BSP Trees
In addition to point and ray queries it is important to be able to perform volume
queries against the BSP tree, such as an AABB test. A rather brute-force solution is to
send each boundary polygon of the AABB down the BSP tree, splitting the polygons
as they straddle dividing planes. If any part of a polygon ends up in a solid leaf, there
is a collision. The implementation of this approach is straightforward and might look
as follows.
// Intersect polygon 'p' against the solid-leaf BSP tree 'node'
int PolygonInSolidSpace(Polygon *p, BSPNode *node)
{
Polygon *frontPart, *backPart;
while (!node-
>
IsLeaf()) {
switch (ClassifyPolygonToPlane(p, node-
>
plane)) {
case POLYGON_IN_FRONT_OF_PLANE:
node = node-
>
child[0];
break;
case POLYGON_BEHIND_PLANE:
node = node-
>
child[1];
break;
case POLYGON_STRADDLING_PLANE:
SplitPolygon(*p, node->plane, &frontPart, &backPart);
if (PolygonInSolidSpace(frontPart, node->child[0])) return 1;
if (PolygonInSolidSpace(backPart, node->child[1])) return 1;
