Graphics Reference
In-Depth Information
the polygon give the best representative result. It is also possible to simplify Newell's
method for specific primitives. For example, given a quadrilateral
ABCD
the normal
obtained by Newell's method can be reduced to that of computing the cross product
of the two diagonals
AC
and
DB
because
2(
AC
×
DB
)
=
(
AB
×
AD
)
+
(
BC
×
BA
)
+
(
CD
×
CB
)
+
(
DA
×
DC
).
The right-hand side of the expression corresponds to the summing of the cross
product normals at each vertex. Interestingly, it is thus actually cheaper to compute
a robust normal for a quadrilateral than it is to do the same for a triangle!
After having computed a good representative plane for a polygon, it is finally
possible to test the planarity of the polygon by putting each of its vertices, in turn,
through the computed plane equation to see by how much each vertex deviates from
the plane. If they are all within a preset tolerance distance from the plane, the polygon
is considered planar. An implementation of this test follows.
// Test if n-gon specified by vertices v[] is planar
int IsPlanar(int n, Point v[])
{
// Compute a representative plane for the polygon
Plane p;
NewellPlane(n, v, &p);
// Test each vertex to see if it is farther from plane than allowed max distance
for(inti=0;i<n;i++) {
float dist = Dot(p.n, v[i]) - p.d;
if (Abs(dist) > PLANARITY_EPSILON) return 0;
}
// All points passed distance test, so polygon is considered planar
return 1;
}
In [Sunday02], the author addresses how to reduce the number of arithmetic
operations needed to compute Newell normals and polygon areas.
12.5
Triangulation and Convex Partitioning
Although it would be possible to perform collision detection directly against the
merged faces, tests involving convex faces only are often simpler, faster, and more
robust. It therefore makes sense to decompose nonconvex faces into two or more
convex pieces, a process known as
convex partitioning
. One alternative is simply to
