1

I have to find the normal of a polygon, but in order to do that I first have to order the vertices (x,y,z) in anticlockwise direction. Lets say I am given n number of vertices points entered by the user, how do I order the vertices in anticlockwise direction to turn them into a polygon?

Jason C
  • 38,729
  • 14
  • 126
  • 182
Tal Zamirly
  • 117
  • 1
  • 11

2 Answers2

10

You can't order your points without knowing the normal, and vice-versa. If you say "anti-clockwise from the front" then you need to know what side is the front, and thus you need to know the normal. So your question doesn't have an answer, as it stands, because it is a bit circular: You don't have enough information to determine what you are looking for.

You need a little bit more information. For example, if this polygon is part of a convex surface, you can compute the geometric center of the surface. Then pick any 3 non-colinear points a, b, c on your polygon, calculate the normal (norm((a - b) cross (c - b))), calculate the vector from the centroid to one of your points (e.g. b - centroid), then check if the normal faces the same (or opposite, whatever) direction as that vector (sign of normal dot (b - centroid)) and flip it if it's the wrong way. Essentially you just calculate a perpendicular unit vector (there are two, remember), then make sure it's pointing towards the inside / outside of your object.

If your face is part of a concave surface, you can make all the normals point the same general direction by taking the dot product of your normal with an adjacent face's normal and flipping it if it's negative. You'd still need to decide on a way to determine which side of the face was on the inside vs. outside of the surface, but at least all the normals would be pointing towards one or the other.

If you don't have information about the general direction the normal should be facing, you'll have to get your anti-clockwise info from elsewhere. You can sort the points around the center of your polygon to get them in order, but to determine if that order is clockwise vs. anti-clockwise requires additional info (e.g. ask the user, etc.).

Note that the atan-based 2D solutions implicitly rely on some extra information: The rely on the fact that the normal faces out of the screen / off the paper and towards you, the viewer, and thus you can sort in a known direction around that normal. That assumption is generally made without anybody ever actually speaking of it. However, in reality, you need to decide which side is the front and the back - not always easy for 3D (if you are rendering to the screen and you have a viewpoint set up, you could use that as the extra info - say the normal faces the camera, then order around that normal).

Another way to phrase the above is, in general, we have 3 unknowns:

  1. What is the winding order when viewed from the "front"?
  2. Which of the two perpendicular unit vectors to the plane do we choose to be on the "front" or "which side is the front"?
  3. What is the sort order of the given points that corresponds to the winding order?

We need to have two of these to determine the third.

In response to Andon's comments below: For the rasterizer, it defines #1 itself (or takes it from configuration), and #3 is assumed by API requirements, and so #2 can be inferred.

In the 2D cases that you often see described (which I mentioned above), #1 is specified as a requirement, #2 is assumed to be "the side facing the viewer is the front", and so #3 can be determined with atan and sorting in increasing/decreasing order.

In your original question, you know #1 (you've defined it), but you don't know #2 (which side is the front?), and therefore you cannot determine #3. You need some way to determine #2 (e.g. facing away from centroid, facing towards viewer, whatever).

Jason C
  • 38,729
  • 14
  • 126
  • 182
  • Except that front / back is often defined in terms of winding. This way the rasterizer can determine which side of a polygon it is shading without knowing the normal. Since rasterization occurs in screen-space, which has clearly defined axes, this is trivial. – Andon M. Coleman Apr 10 '14 at 16:15
  • @AndonM.Coleman What the rasterizer does is not directly related to the precise normal, only to "which side is the front". Also it is unrelated to this because this question is about *determining* the winding given arbitrary points. The rasterizer makes assumptions about what side is the front based on winding, just like our normal calculation makes assumptions about what side is the front based on winding. The rasterizer has the same exact problem we have here, and it's "extra information" is the knowledge that the a certain winding is assumed and that the "front" faces the viewer. – Jason C Apr 10 '14 at 16:21
  • @AndonM.Coleman Remember, we have the following unknowns to deal with here (the rasterizer has the same): 1. What is the winding order when viewed from the "front"? 2. Which of the *two* perpendicular unit vectors to the plane do we choose to be on the "front" *or* "which side is the front"? 3. What is the sort order of the given points that corresponds to the winding order? We need to have two of these to calculate the third. For the rasterizer, it defines #1 itself (or takes it from configuration), and #3 is assumed by API requirements, and so #2 can be inferred. :) – Jason C Apr 10 '14 at 16:24
  • 1
    I was referring to your comment that the question makes no sense. It makes perfect sense in the proper context, the normal is not necessary to determine front. In OpenGL, front is determined after projection and transformation into screen-space, based on the winding with respect to the image plane looking down the Z-axis and the winding that is established to represent front (CCW by default). – Andon M. Coleman Apr 10 '14 at 16:29
  • @AndonM.Coleman In OpenGL, winding is *specified* by [`glFrontFace`](http://www.opengl.org/sdk/docs/man2/xhtml/glFrontFace.xml), that gives the information for #1. The *order* is part of the API requirements and is determined by the order you call `glVertex` in, for example, that's #3. Therefore GL has enough information to determine #2: Which side is the front. In all cases, including OpenGL, you need two of those pieces of information to determine the third. – Jason C Apr 10 '14 at 16:33
  • 1
    @AndonM.Coleman I see what you mean about "makes no sense", though, the question itself does make sense, I shouldn't have said that - it was poorly worded. I've edited that part. (What I meant was, "it makes no sense" in the same way that "a + b = c and c = 3, how do I find a?" doesn't "make sense"). – Jason C Apr 10 '14 at 16:35
0

See atan.

To find the angle of a point (X,Y), you just need to do atan(Y/X). Here are some caveats:

http://upload.wikimedia.org/math/5/7/1/571efb70f630041f9e2b00019025171e.pngAtan domains

Finally, order your results from lowest to highest (add 360 to negative numbers).

Suedocode
  • 2,504
  • 3
  • 23
  • 41
  • thank you, but I think I described my question wrong. I don't have points (x,y) i have vertices (x, y, z). does that make a huge difference? – Tal Zamirly Apr 10 '14 at 05:07
  • What exactly is anti-clockwise in 3 dimensions? In any case, take the cross product of any 2 points and you'll get a normal, assuming that each polygon is 3 connected points to form a plane in 3d space and the center is located at origin. – Suedocode Apr 10 '14 at 05:17
  • It's worth noting that the 2D case here (and many 2D *atan*-based examples in general) implicitly assumes that a normal is facing out of the plane and towards the viewer; because clockwise is anti-clockwise from the other side, even in 2D (e.g. imagine holding a piece of paper with the points drawn on up to a light and looking at it from the back, then the angle sort is in the opposite direction). This is a fine assumption, but don't forget that it *is* an assumption. – Jason C Apr 10 '14 at 05:20