#### Archived

This topic is now archived and is closed to further replies.

# algorithm for making vertices in CCW order

This topic is 5248 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Part of my code spits out a bunch of vertices that make up a polygon. the problem is, it spits them out in essentially random order. In order for OpenGL to render a polygon correctly, it needs the vertices in either clockwise or counter-clockwise order, correct? Otherwise you dont get the polygon you expect. For example, if your polygon is a square, but you have the vertices in the wrong order, for example this order:
1-------2
|       |
|       |
|       |
3-------4

then what OpenGL will actually draw is some wierd triangle thingy instead. Follow me so far? So is there such thing as an algorithm that will take all the vertices of a polygon like the one above, and consistanly order them? For example, I want an algorithm that would either produce this:
1-------2
|       |
|       |
|       |
4-------3

or this:
1-------4
|       |
|       |
|       |
2-------3

consistantly. Thanks! Edit: My ascii drawings never turn out on the first try [edited by - AndreTheGiant on January 11, 2004 4:50:54 PM]

##### Share on other sites
Uhm, it seems to me that it would almost be faster to just turn off back face culling because that''s a difficult algorithm even in 2D...

##### Share on other sites
Wouldnt disabling backface culling merely make it so it didnt matter whether your vertices were listed in CCW or CW order? You would still have to have them listed in at least some kind of order though, wouldnt you?

##### Share on other sites
The source of the problem is your algorithm, so try to fix
it there. Rearranging random points into CW or CCW is not
a trivial problem (I suspect it''s NP!).

Here is one idea: generate your points such that each point
makes a "left" turn from the previous point. Left turns give
you CCW while right turns give you CW.

Kami no Itte ga ore ni zettai naru!

##### Share on other sites
Well at least generate your points in SOME order, and turning off back face culling, because making them CCW is NOT TRIVIAL. I can barely come up with a way to do it in 2D, and in 3D, that''s crazy O_o.

##### Share on other sites
Well, Im looking at my algorithm that generates the points right now. If I didnt know how to write a stand alone algorithm to order the vertices, I dont know how Im going to be able to modify this one to do it, because it would be essentially the same problem wouldnt it?

If you can find an algorithm in 2d, then there is one in 3d as well. Also, I think that all my polys are convex, so that possibly simplifies things. Off the top of my head, you might be able to use the fact that a correct ordering of the vertices produeces a polygon with maximum area. At the very least, I suppose I could loop through all possible orderings of vertices and check the area... but even this is tricky even in 2d as you said. If the algorithm is NP, that doesnt matter much to me, since most of my polys will only have 4 verts anyway.

[edited by - AndreTheGiant on January 11, 2004 5:42:35 PM]

##### Share on other sites
What you''re describing in known as Convex Hull in Computational
Geometry.

Look up the Graham Scan algorithm for computing Convex Hull.
There are other algorithms as well.

The algorithm runs in O(n log n) time. Very efficient.

For 4 points, that''s almost instantaneous.

Kami no Itte ga ore ni zettai naru!

##### Share on other sites
He''s not looking for a convex hull.. What if his polygon isn''t convex?

Actually, this is a trivial problem. You''re sorting a list of points into CW or CCW order. That word "sorting" is key. Now, you''ve given this in the context of a 3d environment. However, unless all your points are co-planar, that doesn''t make sense. So I''ll assume the points are co-planar.

The algorithm then has three basic steps:

1. Find a transformation that puts all the points into the X-Y plane, with the origin in the middle of the set of points.

2. Sort the points. If you''re using the standard C qsort function, the comparison function between two points would look something like this:

int compar(const void *v1, const void *v2){    point *p1 = (point *)v1;    point *p2 = (point *)v2;    return (p1->x * p2->y) - (p2->x * p1->y);}

3. Reverse the transformation from step 1

Now you''ve got the list of points sorted in either CW or CCW order... I can never remember which I''m doing when I write the comparison function. Obviously, if you need the other order, just change the return statement to reverse the sign of the value being returned (ie, swap the two expressions on opposite sides of the minus sign).

##### Share on other sites
quote:
Original post by Anonymous Poster
He''s not looking for a convex hull.. What if his polygon isn''t convex?

No?

Then what does the following say?

quote:

]Original post by AndreTheGiant
Also, I think that all my polys are convex, so that possibly simplifies things.

Hmmm?

Kami no Itte ga ore ni zettai naru!

##### Share on other sites
quote:

Original post by tangentz[i]
The source of the problem is your algorithm, so try to fix
it there. Rearranging random points into CW or CCW is not
a trivial problem (I suspect it's NP!).

Here is one idea: generate your points such that each point
makes a "left" turn from the previous point. Left turns give
you CCW while right turns give you CW.

Im getting the vertices by reading an input file that I have no control over. Therefore, I cant "build-in" the vertex sorting algorithm into the file read function, unless I just tack it on the end, in which case I might as well have a separate function for it.

Anyway I think Ive found the algorithm, and its not NP, its n^2 as far as I can tell.

[edited by - AndreTheGiant on January 12, 2004 7:52:27 AM]

• 10
• 16
• 9
• 13
• 41