Graphics Reference
In-Depth Information
If it is not known whether the triangle is clockwise or counterclockwise, the same
approach can still be used. Containment of
P
in
ABC
is then indicated by
P
lying on
the same side of all edges of the triangle. That is, either
P
lies to the left of all edges
or to the right of all edges. If neither is true,
P
is not contained in the triangle. In
terms of implementation, the code must be changed to test that the 2D pseudo cross
products all have the same sign.
// Test if 2D point P lies inside 2D triangle ABC
int PointInTriangle2D(Point2D p, Point2D a, Point2D b, Point2D c)
{
float pab = Cross2D(p - a,b-a);
float pbc = Cross2D(p - b,c-b);
// If P left of one of AB and BC and right of the other, not inside triangle
if (!SameSign(pab, pbc)) return 0;
float pca = Cross2D(p - c,a-c);
// If P left of one of AB and CA and right of the other, not inside triangle
if (!SameSign(pab, pca)) return 0;
// P left or right of all edges, so must be in (or on) the triangle
return 1;
}
Because the value returned by
Cross2D(p - a,b-a)
is twice the signed area
of the triangle
PAB
(positive if
PAB
is counterclockwise, otherwise negative), yet
another version of this test is to compute the areas of
PAB
,
PBC
, and
PCA
and see if
their sum exceeds that of the area of
ABC
, in which case
P
lies outside
ABC
.Tosave
on computations, the area of
ABC
could be stored with the triangle. As with the 3D
test, this test can be optimized by storing plane equations for each edge that have
been normalized to compute the barycentric coordinates of the query point.
5.4.3
Testing Point in Polyhedron
There are several available methods for testing if a point lies inside a given polyhedron.
How the polyhedron is specified and whether it is convex or concave determine which
methods are appropriate in a given situation. This section outlines a few different
approaches, some of which are discussed in more detail in Chapters 8 and 9.
The simplest test is when the polyhedron is convex and given implicitly as the
intersection volume of a number of halfspaces. In this case, the point lies inside the
polyhedron if it lies inside each halfspace.
// Test if point p inside polyhedron given as the intersection volume of n halfspaces
int TestPointPolyhedron(Point p, Plane *h, int n)
