Graphics Reference
In-Depth Information
For the star-shaped polygon used earlier, Newell's method consistently produces
the expected normal (pointing out of the page):
K
n
1
(0, 0, 40)
2
(0, 0, 80)
3
(0, 0, 120)
4
(0, 0, 160)
The following code illustrates how Newell's method can be implemented to com-
pute a robust representative plane for a polygon. Here, the polygon centroid — that
is, the average of all vertices — is used as the representative point on the plane when
computing the plane equation.
// Given n-gon specified by points v[], compute a good representative plane p
void NewellPlane(int n, Point v[], Plane *p)
{
// Compute normal as being proportional to projected areas of polygon onto the yz,
// xz, and xy planes. Also compute centroid as representative point on the plane
Vector centroid(0.0f, 0.0f, 0.0f), normal(0.0f, 0.0f, 0.0f);
for(inti=n-1,j=0;j<n;i=j,j++) {
normal.x += (v[i].y - v[j].y) * (v[i].z + v[j].z);
// projection on yz
normal.y += (v[i].z - v[j].z) * (v[i].x + v[j].x);
// projection on xz
normal.z += (v[i].x - v[j].x) * (v[i].y + v[j].y);
// projection on xy
centroid += v[j];
}
// Normalize normal and fill in the plane equation fields
p-
>
n = Normalize(normal);
p-
>
d = Dot(centroid, p-
>
n)/n;
// “centroid / n” is the true centroid point
}
Newell's method can be seen as computing a “best-fit” plane, using all vertices.
Yet another alternative approach is to fit a plane to the polygon vertices using the
method of
least-squares fit
(see [Eberly01] for details).
Computing plane equations using Newell's method is clearly more expensive than
just taking the cross product of two coincident edges. Storing plane equations with
the polygons is one option, but this is unattractive memory-wise. A compromise is
still computing normals and plane equations at runtime using a cross product, but
after having made sure the polygon is output so that the first three stored vertices of
