Jump to content
  • Advertisement
Sign in to follow this  
kiniport

Normal of a non-convex poly

This topic is 4478 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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
Advertisement
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...

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:
Original post by jpetrie
If the polygon is non-planar...


Polygons are planar by definition.


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,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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!