Normal of a non-convex poly

Math and Physics Programming

Started by kiniport March 15, 2006 05:12 PM

18 comments, last by Bob Janova 18 years, 1 month ago

840

March 16, 2006 02:21 AM

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.

Christer Ericson
http://realtimecollisiondetection.net/blog/

vicviper

130

March 16, 2006 03:19 AM

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

jjd

2,140

March 16, 2006 08:02 AM

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

They are not planar by definition.

Polygon

--www.physicaluncertainty.com
--linkedin
--irc.freenode.net#gdnet

Wasting Time

411

March 16, 2006 10:04 AM

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.

Wasting Time

411

March 16, 2006 10:07 AM

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.

jjd

2,140

March 16, 2006 10:18 AM

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]

--www.physicaluncertainty.com
--linkedin
--irc.freenode.net#gdnet

haphazardlynamed

340

March 16, 2006 10:26 AM

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.

kiniport

130

Author

March 16, 2006 02:15 PM

Thank you Wasting Time, Newell's method is exactly what I needed(and pretty close to what I had guessed). ;)

Christer Ericson

840

March 17, 2006 04:18 AM

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.

Christer Ericson
http://realtimecollisiondetection.net/blog/

Bob Janova

769

March 17, 2006 01:33 PM

Just pretend the OP used the word 'surface' instead :P.