kiniport 130 Report post Posted March 15, 2006 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? 0 Share this post Link to post Share on other sites
oliii 2196 Report post Posted March 15, 2006 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... 0 Share this post Link to post Share on other sites
jpetrie 13200 Report post Posted March 15, 2006 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] 0 Share this post Link to post Share on other sites
kiniport 130 Report post Posted March 15, 2006 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. 0 Share this post Link to post Share on other sites
jjd 2140 Report post Posted March 15, 2006 Quote:Original post by jpetrieIf the polygon is non-planar...Polygons are planar by definition. 0 Share this post Link to post Share on other sites
jpetrie 13200 Report post Posted March 15, 2006 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. 0 Share this post Link to post Share on other sites
Bucket_Head 308 Report post Posted March 15, 2006 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. 0 Share this post Link to post Share on other sites
Wasting Time 411 Report post Posted March 15, 2006 Quote:Original post by jjdPolygons 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.] 0 Share this post Link to post Share on other sites
Wasting Time 411 Report post Posted March 16, 2006 Quote:Original post by kiniportI'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. 0 Share this post Link to post Share on other sites
Christer Ericson 840 Report post Posted March 16, 2006 Quote:Original post by Wasting TimeQuote:Original post by jjdPolygons 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.htmlhttp://en.wikipedia.org/wiki/Polygonhttp://mathworld.wolfram.com/Polygon.htmlAs 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). 0 Share this post Link to post Share on other sites
Christer Ericson 840 Report post Posted March 16, 2006 Quote:Original post by oliiiA 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 TimeDo 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. 0 Share this post Link to post Share on other sites
vicviper 130 Report post Posted March 16, 2006 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 0 Share this post Link to post Share on other sites
jjd 2140 Report post Posted March 16, 2006 Quote:Original post by Wasting TimeQuote:Original post by jjdPolygons are planar by definition.They are not planar by definition.Polygon 0 Share this post Link to post Share on other sites
Wasting Time 411 Report post Posted March 16, 2006 Quote:Original post by Christer EricsonI 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. 0 Share this post Link to post Share on other sites
Wasting Time 411 Report post Posted March 16, 2006 Quote:Original post by Christer EricsonTo 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. 0 Share this post Link to post Share on other sites
jjd 2140 Report post Posted March 16, 2006 Quote:Original post by Wasting TimeWhen 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] 0 Share this post Link to post Share on other sites
haphazardlynamed 340 Report post Posted March 16, 2006 Quote:Original post by Wasting TimeQuote:Original post by Christer EricsonI 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. 0 Share this post Link to post Share on other sites
kiniport 130 Report post Posted March 16, 2006 Thank you Wasting Time, Newell's method is exactly what I needed(and pretty close to what I had guessed). ;) 0 Share this post Link to post Share on other sites
Christer Ericson 840 Report post Posted March 17, 2006 Quote:Original post by Wasting TimeI 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. 0 Share this post Link to post Share on other sites
Bob Janova 769 Report post Posted March 17, 2006 Just pretend the OP used the word 'surface' instead :P. 0 Share this post Link to post Share on other sites