I have not analysed your code toroughly, a bit of headache and it misses some comments and the rest of the code for my poor head (well working on something different and difficult at the same time). So I am not 100% sure.

But still I can't see well how atan() could be enough in cases you have angles of more than 90 degrees. So try with 4 vertices and two angles of more than 90 degrees, and see if it still works. For instance these points :
(-1,0) (0,10) (+1,0) (0,-10)

Try them in different orders.

Just out of curiosity. If the polygon is convex then why do you need an interior point to build a fan?

Probably for the same underlying reason as I recommanded it for numerical precision when recovering the winding order : balance.

It's possibly worth to have one more vertex and one more triangle if the triangles are more balanced. I remember how narrow rather vertical triangles were perf killers in my software renderers. I guess it's still the same even with the latest 3D hardware.

Else. If something is computed at vertices and interpolated (lighting maybe) it's also more balanced on the whole shape. Still in my proposal the center could just be used temporarilly and not kept in the end.

Well maybe an argument to test seriously. I never took the pain to make such a banchamrk on 3D cards. One more argument against simplistic polycount.

First of all, sorry for not replying sooner, I've been at work at lot and haven't had the chance to have reply.
Thanks for all the replies people, very helpful, even if I only understand a few bits from each post :)

For the posters who use a 'sidedness' test - I'm sorry, I just don't understand how the order of the vertices could be gained from knowing the side a point lies on, I get how this would be employed to remove duplicates but that's about it.

@LilBudyWizer:
Yeah, a fan could be rendered without the use of a centre vertex, and this would be a nice little triangle saver, but as Charles B correctly points out, it does result in nasty, extremely thin triangles being produced: these typically render very poorly in OpenGL. I hadn't realised the fact that the centre vertex could be dropped until you had pointed it out though, so I'm not going to pretend that I knew all along, and I feel a might stupid for not realising this before :blush:


I've read, re-read and read again all of the posts, and nothing 'clicked'; I had another read and Palidines post finally made (partial) sense, so I decided to implement that as I understood at least some of it.


A description of what I've done:

Grab centre vertex in 3D.

I find the two most significant axes from the 3D vertices by dropping the largest abs component from the normal of the plane describing the polygon, e.g. if PlaneNormal = (23,-45,128), then I would use the x and y axes, as abs(z) is greater than abs(x) or abs(y).

Using these two axes I degenenerate my 3D list to a 2D one (Vtx2D), and also change the centre vertex to 2D.

I invert the sign value on the components of the 2D centre vertex (CV2D) and add this to all the other vertices, thereby effectively translating them to (0,0): CV2D = CV2D * -1, loop through all the 2D vertices and use Vtx2D[Loop] = Vtx2D[Loop] + CV2D.

Now I calculate the angle between (1,0) and each vertex in Vtx2D using this formula: normalise vectors V1 and V2, then angle = arccos( dot(V1,V2) ).

Now I sort my 2D vertices based upon the angles that I just calculated.

The final step is to re-order the initial 3D vertices from the order of the 2D ones, and add centre vertex (3D) as position [0] in the array.


Guess what? It fails yet again :( I felt that I must be doing something stupid with the code, but after going over it a fair few times everything seems to fine; therefore it must be my maths skills (again, *sigh*) that are the problem - I wonder if someone would be so kind as to verify that the steps outlined above are indeed correct, and that I am not making some foolish error.

Again, thanks to all for taking the time to read and reply :)

/edit: My terrible grammar.

Well I'm using arctan2 instead of arccos, and results are looking reasonably good, still some problems with 4 sided polygons and fans, but it's getting there; as to your kind offer v71 - sure, I would like to see how else it can be done, now that the code is written I feel I won't be using other peoples ideas before I've tried my own (I like the challenge). If you're happy to share your code then that would be great, proper credit will obviously be given of course.

To all those that helped, a big thankyou, it's nice to know that some people still like to help :)

There are several known algorithms for this problem, which is analogous in both 2D and 3D. Check out this web page for some nice Java applets animating several of these solutions:

http://www.cse.unsw.edu.au/~lambert/java/3d/hull.html

Yeah, I've seen that page before - it deals with the creation of a set of points that represent a convex hull, from a list of 'random' points that may or may not be part of it; the points that I have form a convex hull already, with no duplicates or points in/out of the hull - it's getting the winding order of these points that is the problem.

Thanks for the link anyway :)