Finding order of vertices

[Ashley Perrien]

As some background, it's been a while sine I've done any opengl programming and even then it was very basic. I'm currently beginning work on a new project that will make use of it.

One thing I'm going to need to figure out is if I have a list of vertices in no particular order, how can I go about ordering them correctly for drawing? The points will be coplanar and they will form a convex shape. I've done some searching and found ways to find the correct winding but they all assume that the points are already in the correct order and that's the part that I need.

Any suggestions on how to accomplish that? Any pointers, web links or pseudo-code would be much appreciated.

Ashley

[remdul]

Sounds like you'll need to implement a convex-hull algorithm:

http://en.wikipedia.org/wiki/Convex_hull

2d is relatively easy, 3d quickly becomes very complex, if you want it to be fast.

Read this to get an overview: http://en.wikipedia.org/wiki/Convex_hull_algorithms

For 2D convex hulls: http://softsurfer.com/Archive/algorithm_0109/algorithm_0109.htm (with code sample)

For 3D convex hulls, I would suggest to take one of the existing algorithms code samples to get you up and running. Of course, if you want a deeper understanding (always a good idea), read the respective research paper.

Remember that OpenGL expects counter-clockwise winding by default. Though you can override this,
see http://www.opengl.org/sdk/docs/man/xhtml/glFrontFace.xml .

PS, since you mention that the vertices are known to lie on the same plane, you'll be best off by projecting the vertices to this plane, and then construct a 2D convex hull. The results should include vertex order information.