Sign in to follow this  
kiniport

Normal of a non-convex poly

Recommended Posts

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?

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
For the purposes of finding the normal, you can find a convex bounding polygon and take the normal of that. Alternatively, there may be some way to use only convex polygons that you should look into.

I think your first question to answer is either "how do you know if your polygon is concave?" or to find a way to wind a series of vertices into a polygon with a method that will drop inner vertices...I don't have a ready answer for you in this regard, but I think that's a good direction to look down.

Share this post


Link to post
Share on other sites
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.]

Share this post


Link to post
Share on other sites
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[i],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.

Share this post


Link to post
Share on other sites
Quote:
Original post by Wasting Time
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.
I disagree. Whether polygons are defined as compact subsets of the plane bounded by a finite number connected line segments or as the (non-empty) intersection of a finite number of halfplanes, or whatever, polygons always lie in the plane and are always bounded by line segments. You can define other things that you call "polygons" that lie on nonplanar surfaces such as spheres, but they're not polygons, they're "spherical polygons" (bounded by great arcs, not line segments) or "saddle polygons" or "xxx polygons", never just "polygons" (because that implies a polygon in the plane, having a boundary consisting of connected line segments).

I think you'd be hard-pressed to find much support for your stance (though I'm sure you can find some, if you look hard enough), whereas it was easy to find several references to polygons defined in the way I'm suggesting:

http://planetmath.org/encyclopedia/Polygon.html
http://en.wikipedia.org/wiki/Polygon
http://mathworld.wolfram.com/Polygon.html

As the above sources aren't exactly the most authorative references in the world, I also checked a number of mathematical handbooks and geometry textbooks that I have at home and they all support the definition of polygons as planar, and not as definable for any surface (orientable or not).

Share this post


Link to post
Share on other sites
Quote:
Original post by oliii
A polygon is by definition on a plane, so it has one normal, which is the cross product of any two of its edges.

unless I'm missing something...
You are missing that for a nonconvex polygon, depending on which two neighboring edges E1 and E2 you pick, you may get a normal that points in direction N or you may get one that points in direction -N. Which normal you get depends on whether the (internal) angle at E1 and E2 is convex or concave.

To the OP: the simple solution is to ensure you are always picking two edges E1 and E2 that have a convex (internal) angle between them. You achieve this by picking E1 and E2 to be the edges that coincide with e.g. the leftmost topmost vertex.

Quote:
Original post by Wasting Time
Do you have an example for which the algorithm fails? What you are trying to implement is Newell's Method[...]
Don't know if you have access to it, but I give an example on pages 492-493 of my book of a star-shaped polygon for which the method of just summing the normals at each vertex fail (by resulting in the zero vector), and how Newell's method handles it correctly. Newell's method is probably overkill for the OP though, and the method I outlined above should be sufficient.

Share this post


Link to post
Share on other sites

simply find the normals per vertex, not per polygon.

What I do is to compute the normals on a per vertex basis, taking the previous and the next vertex in the polygon. On a non planar polygon, it will result in a different normal on every vertex.

This method has the advantage that always generates normals that ensure a smooth view of the object, regardless the number of vertices of polygons, and is not affected by the convexity / concavity of the polygons. The only disadvantage is that it's more slow because you compute more normals.

Vic

Share this post


Link to post
Share on other sites
Quote:
Original post by Christer Ericson
I disagree.


I have heard all these arguments before. Whenever someone objects to the term "nonplanar polygon", they say "polygons are planar by definition". When you say that "but they're not polygons, they're spherical polygons", you have already have acknowledged that by including an adjective (spherical) you can allow for nonplanar things that are polygons. You cannot simultaneously say "spherical polygon" is an okay term to use but "nonplanar polygon" is not.

Share this post


Link to post
Share on other sites
Quote:
Original post by Christer Ericson
To the OP: the simple solution is to ensure you are always picking two edges E1 and E2 that have a convex (internal) angle between them. You achieve this by picking E1 and E2 to be the edges that coincide with e.g. the leftmost topmost vertex.


And when E1 and E2 meet at a convex vertex, but the edges are nearly collinear, then you can run into numerical problems. This is why Newell's method was designed in the first place. If you must search for a convex vertex, choose one for which the interior angle is as close to 90 degrees as possible. Needle-like polygons are a problem, though, no matter which method you choose.

Share this post


Link to post
Share on other sites
Quote:
Original post by Wasting Time
When you say that "but they're not polygons, they're spherical polygons", you have already have acknowledged that by including an adjective (spherical) you can allow for nonplanar things that are polygons.


In the interests of wasting time...

proof by terminology is not a method to be admired. a "spherical polygon" describes a class of objects that are similar to a polygons, but that are not polygons. since polgons are defined as planar objects you cannot have nonplanar things that are polygons, you simply have a nonplanar object.

[Edited by - jjd on March 16, 2006 10:18:07 AM]

Share this post


Link to post
Share on other sites
Quote:
Original post by Wasting Time
Quote:
Original post by Christer Ericson
I disagree.


I have heard all these arguments before. Whenever someone objects to the term "nonplanar polygon", they say "polygons are planar by definition". When you say that "but they're not polygons, they're spherical polygons", you have already have acknowledged that by including an adjective (spherical) you can allow for nonplanar things that are polygons. You cannot simultaneously say "spherical polygon" is an okay term to use but "nonplanar polygon" is not.



I would like to remind you that there is a Truth for every Context. And we are GameProgrammers, not MathGraduateStudents.

Share this post


Link to post
Share on other sites
Quote:
Original post by Wasting Time
I have heard all these arguments before. Whenever someone objects to the term "nonplanar polygon", they say "polygons are planar by definition". When you say that "but they're not polygons, they're spherical polygons", you have already have acknowledged that by including an adjective (spherical) you can allow for nonplanar things that are polygons. You cannot simultaneously say "spherical polygon" is an okay term to use but "nonplanar polygon" is not.
You are the one making extraordinary claims, deviating from the standard definition of polygon and it is therefore you who should be providing extraordinary evidence for your claims. However, while I posted several links in support of the traditional definition (and can post numerous additional definitions from authorative books I have here at home), so far you have only provided opinion and no factual support whatsoever for your stance; that's not lending any credit to your case.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this