How to determine ordering of 3D vertices

Question

If I have 5 Vertices in 3D coordinate space how can I determined the ordering of those Vertices. i.e clockwise or anticlockwise.

If I elaborate more on this,

I have a 3D model which consists of set of polygons. Each polygon is collection of vertices and I want to calculate the norm of the polygon surface. To calculate the norm I have to consider the vertices in counter clockwise order . My question is given set of vertices how can I determine whether it is ordered in clockwise or counter clockwise?

Answer 1

Your question is too poorly defined to give a complete answer, but here's the skeleton of one.

The missing part (the meat if you will), is a function that takes any two coordinates and tells you which one is 'greater' than the other. Without a solid definition for this, you won't be able to make anything work.

The rest, the skeleton, is pretty simple. Sort your list of vectors using your comparison function. For five vectors, a simple bubble sort will be all you need, although if the number of vertices increases considerably you may want to look into a faster sorting algorithm (ie. Quicksort).

If your chosen language / libraries provide sorting for you, you've already got your skeleton.

EDIT After re-reading your question, it also occurred to me that since these n vertices define a polygon, you can probably make the assumption that all of them lie on the same plane (if they don't, then good luck rendering that).

So, if you can map the vector coordinates to 2d positions on that plane, you can reduce your problem to ordering them clockwise or counterclockwise in a two dimensional space.

Answer 2

As others have noted, your question isn't entirely clear. Is the for something like a 3D backface culling test? If so, you need a point to determine the winding direction relative to. Viewed from one side of the polygon the vertices will appear to wind clockwise. From the other side they'll appear to wind counter clockwise.

But suppose your polygon is convex and properly planar. Take any three consecutive vertices A, B, and C. Then you can find the surface normal vector using the cross product:

N = (B - A) x (C - A)

Taking the dot product of the normal with a vector from the given view point, V, to one of the vertices will give you a value whose sign indicates which way the vertices appear to wind when viewed from V:

w = N . (A - V)

Whether this is positive for clockwise and negative for anticlockwise or the opposite will depend on the handedness of your coordinate system.

Answer 3

I think your confusion comes from the fact that methods for computing cross products are sometimes taught in terms of clockwiseness, with a check of the clockwiseness of 3 points A,B,C determining the sign of: (B-A) X (C - A) However a better definition actually determines this for you. In general 5 arbitrary points in 3 dimensions can't be said to have a clockwise ordering but 3 can since 3 points always lie in a plane.

Answer 4

This is for navigation mesh generation where I want to remove the polygons which cannot be walked by the agent. To do so my approach is to calculate the surface norm(perpendicular vector of the polygon) and remove the polygon based on the angle with 2D plane. To calculate the norm I should know in which order points are arranged. So for given set of points in polygon how can I determine the order of the arrangement of points.

Ex.

polygon1 consist of Vertex1 = [-21.847065 -2.492895 19.569759], Vertex2 [-22.279873 1.588395 16.017160], Vertex3 [-17.234818 7.132950 7.453146] these 3 points and how can I determine the order of them