I'm tryinbg to simply and reliably trying to find the normal on a non-convex polygon. Currently, I'm summing the cross product of all neighboring edges, which works for most cases, but not all. Any ideas?

If the "polygon" is non-planar, its normal is not really well-defined (a normal being a vector perpendicular to the surface). The surface doesn't have a single perpendicular vector in this case, and assigning it one normal is going to be an approximation no matter how you do it.

You could triangulate the "polygon" and average the normals of the resulting triangles (this will probably be very similar to your current method, though).

[Edited by - jpetrie on March 15, 2006 7:23:40 PM]

Since its a non-convex polygon, if I take the cross product of a pair of edges that are on a "concave" part of the polygon, the normal will be in the wrong direction.

jpetrie: My polygons are planar. Proper triangulation of a non-convex polygon is pretty involved, and definately seems like overkill.

Quote:
Polygons are planar by definition.

I'm aware, but that doesn't stop a person from creating something that they call a polygon that doesn't fit the strict defintion of one, and it also doesn't stop the situation where, for example, you are reading quads (a type of polygon) from a data file and somebody has provided you with four non-planar points, both of which are common enough occurances to justify consideration. Or at least speculation. *shrug*

Perhaps I should have puts quotes around my use of polygon. I'll edit my post and do that now.

Quote:Original post by jjd
Polygons are planar by definition.

They are not planar by definition. For example, consider the terms "spherical triangle" and "spherical polygon". Generally, you can define a polygon on any orientable surface. What you need is the ability to specify an "inside" and an "outside" for the polygon. You can do this on an orientable surface in the same way you do this in the plane. In the plane, you place an observer on the side of the plane to which the plane normal is pointing. He looks at an ordered set of points in the plane and chooses a convention. The typical one is to say that the inside of the polygon is to the left as the observer walks from point to point (counterclockwise ordering). On an orientable surface, you can define "which side" of the surface you are on (this is why you need orientable).

Another way to choose the inside region for a planar polygon is to use the Jordan Curve Theorem. The simple polygon partitions the plane into two connected regions. The bounded region is "inside" the polygon. This definition does not work generally. For example, a spherical triangle partitions the sphere into two bounded regions.

Given a simple polygon on an orientable surface, you can always triangulate it.

What is a problem is when someone says they have an ordered set of points/edges in space, calling the object a "nonplanar polygon", and they want to triangulate the polygon. This is an ill-posed problem because they have not specified on which orientable surface the points lie. For example, consider the points V0 = (0,0,0), V1 = (1,0,0), V2 = (1,1,0), V3 = (0,1,0), V4 = (0,0,1), V5 = (1,0,1), V6 = (1,1,1), and V7 = (1,1,0). One possible triangulation is <V0,V1,V2>, <V0,V2,V3>, <V0,V3,V4>, <V3,V7,V4>, <V4,V7,V6>, and <V4,V6,V5>. Another possible triangulation is <V0,V4,V5>, <V0,V5,V1>, <V5,V6,V2>, <V5,V2,V1>, <V6,V7,V3>, and <V6,V3,V2>. [If I typed these correctly, the two triangulated surfaces together form a cube.]

Quote:Original post by kiniport
I'm tryinbg to simply and reliably trying to find the normal on a non-convex polygon. Currently, I'm summing the cross product of all neighboring edges, which works for most cases, but not all.

Do you have an example for which the algorithm fails? What you are trying to implement is Newell's Method, which is discussed in Graphics Gems 3. This is supposed to be a robust method. If your ordered vertices are V[0] through V[m-1], I believe the formula for the normal reduces to N = (1/(m-2))*sum_{i=0}^{m-1} Cross(V,V[i+1]), where V[m] is defined to be V[0]. You can skip the 1/(m-2) term since you will most likely normalize the sum.