Calculating a polygon normal

One robust approach is to fit the points using a least-squares algorithm. Look at section 4 of the document Least Squares Fitting of Data. The implementation for planes is in the files whose name starts with Wm3PlaneFit. The points are fit with a Gaussian distribution. You expect the distribution to be "flat" in one direction, that direction becoming the plane normal. The eigenvector of the covariance matrix corresponding to the zero eigenvalue is this direction. A point on the plane is the average of your points.

Alternatively, find a convex vertex and use the two edges sharing it to create the normal. This is not necessarily robust (angle is nearly 180 degrees, lengths of edges are nearly zero).

Also of interest: Newell's method. From what I have been told, also not always robust. (Do a Google search on "Newell's method".)

So it seems like you can calculate the normal just fine except sometimes they face the wrong way. I have a solution but it might not work with some verticies if the mesh has a hole in it.

Take the calcuated normal and check for intersections between every polygon in it's mesh and the normal extended infanatly. If the number of intersections is odd, it's facing the wrong way. The reason this works is if the normal is facing inward then the ray casted by the normal will have to exit the mesh and thus intersect a triangle. If the ray is pointing outside of the mesh and it enters the mesh it also has to exit it also, resulting in two intersections. I don't know how much sense this makes but This is the solution I came up with.

Thank you guys! Newell's Method was exactly what I had run across in passing during my research (it's an orthographic projection to the three primary planes), and once you supplied the correct name, I was able to google it with no problem.

I don't see any reason why this wouldn't be robust, unless there's something I'm missing. In any event, it should produce pretty close to the optimial normal for a given plane, shouldn't it? I guess it may suffer from rounding issues if the number of verts gets to be too large?

N = {0,0,0};
for (each vertex in the polygon Vn)
{
Nx += (Vny - V(n+1)y) * (Vnz + V(n+1)z);
Ny += (Vnz - V(n+1)z) * (Vnx + V(n+1)x);
Nz += (Vnx - V(n+1)x) * (Vny + V(n+1)y);
}

And then I suppose it would be prudent to normalize the normal. I think this would work as long as the polygon is planar and simple (no holes, no self intersections) and seems easy enough to implement :)

As for the other methods suggested, I'm sure they'd work too :) Anything on Dr. Eberly's site is usually both difficult to understand and to implement. Don't get me wrong, I have a ton of respect for his stuff (I own two of his books, and have implemented several algorithms he came up with), but for something quick and easy (like this SHOULD be :) ), I prefer to stay away from that particular site, heh. I'll probably get flamed to death for that, I mean no disrespect to Dr. Eberly at all, I'm just not smart enough to get most of what he writes without studying it for hours and hours.

As for finding a convex angle and using the cross product of that, that's certainly possible (we know the left-most or bottom-most angles (for example) MUST be convex), but I can see it being prone to problems if the angles are near pi, or they could even be colinear (as you said, WT)!

Supernerd, I see what you are saying, but it implies the polygon is part of a mesh, which in my case it may or may not be, so that won't work for me. Still, it's an interesting approach! Seems like it ought to work quite nicely for polygons in meshes.

Just a quick note to say I implemented this routine this morning, and it worked like a charm! Actually, at first it didn't, but it turned out it was revealing a bug in my code in the face creation routines. Once I fixed that, it worked perfectly (and now not only do I know my face normals, my code has one fewer bugs in it! :) )

I want to say thanks again to WT and SN for the suggestions. You guys helped me a ton.