Graphics Reference
In-Depth Information
Figure 6.6.
Surrounding test based on barycentric
coordinates.
Figure 6.7.
Surrounding test based on
wedges.
The rays from this point through all the vertices of
Q
then divide the plane into infi-
nite wedges that are cut in half by the associated edge of
Q
. One can find the wedge
that contains
p
by doing a binary search for the angle of
qp
among the angles of the
vectors
qp
i
. Finally one checks where
p
lies with respect to the edge of
Q
in the wedge.
See Figure 6.7. Because binary search is fast, this can be a good algorithm.
Next, we look at surrounding tests for arbitrary (possibly nonconvex) polyhedra.
The Parity or Crossings Test (Arbitrary Q).
For this test one checks how many
times
any
ray starting at
p
will intersect the boundary of
Q
. If it intersects an even
number of times,
p
is outside
Q
. If it intersects an odd number of times,
p
is inside
Q
. See Figure 6.8. For this to work though one must count an intersection twice
if the ray is “tangent” to the boundary of
Q
at that point. In the two-dimensional case
“tangent” means that the boundary edges containing the intersection point lie entirely
to one side of the ray. In the three-dimensional case the boundary faces containing
the point should lie entirely to one side of a “tangent” plane containing the ray. The
polyhedron does
not
have to be convex for the parity test, but it can be made more
efficient in the convex case.
The intersection tests and tests for tangency could make this a somewhat com-
plicated test to implement without some tricks, especially in three dimensions. We
