Graphics Reference
In-Depth Information
{
for(inti=0;i<n;i++) {
// Exit with 'no containment' if p ever found outside a halfspace
if (DistPointPlane(p, h[i]) > 0.0f) return 0;
}
// p inside all halfspaces, so p must be inside intersection volume
return 1;
}
If the polyhedron is given as a set of vertices without any connectivity information,
the GJK method described in Chapter 9 serves as an efficient point containment
approach. Only a convex polyhedron can be given in this format.
If the polyhedron is given as a closed mesh, one approach is to first build a solid-
leaf BSP tree (see Chapter 8) from the mesh. Then, given this BSP tree if a point query
on the tree ends up in a solid leaf the point is inside the polyhedron (otherwise, it is
not). This method works for both convex and concave polyhedra.
A method that works with a polyhedron given either as a mesh or as an intersection
of halfspaces is to shoot a ray from the tested point in any direction (typically along
a major axis, such as the +
x
axis) and count the number of faces intersected. If an
odd number of faces is intersected, the point lies inside the polyhedron; otherwise,
the point lies outside it. Due to floating-point classification errors, this method has
robustness issues when a ray strikes (near) an edge or a vertex. To avoid dealing with
the degeneracies of these cases, one effective approach is simply to recast the ray,
although care must be taken not to hit an edge or vertex again. This method also
works for both convex and concave polyhedra.
With a custom prebuilt data structure such as the Dobkin-Kirkpatrick hierar-
chical structure (see Section 9.3.1), a point containment query can be performed
in
O
(log
n
) time.
5.4.4
Intersection of Two Planes
Let two planes,
π
1
and
π
2
, be given by the plane equations
n
1
·
X
=
d
1
and
n
2
·
X
=
d
2
.
When the planes are not parallel, they intersect in a line
L
,
L
t
d
.As
L
lies
in both planes, it must be perpendicular to the normals of both planes. Thus, the
direction vector
d
of
L
can be computed as the cross product of the two plane normals,
d
=
P
+
n
2
(Figure 5.30). If
d
is the zero vector, the planes are parallel (and separated)
or coincident; otherwise, they are intersecting.
For
L
to be fully determined, a point
P
on the line must also be given. One way of
obtaining a point on the line is to express the point as being in a plane perpendicular
to
d
. Such a plane is spanned by
n
1
and
n
2
, and thus
P
is given by
P
=
n
1
×
=
k
1
n
1
+
k
2
n
2
π
π
for some values of
k
1
and
k
2
. Furthermore,
P
must lie on both
2
, and thus it
must satisfy both plane equations. Substituting this expression for
P
(in place of
X
)
1
and
