#### Archived

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

# algorithm for making vertices in CCW order

This topic is 5155 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]

##### Share on other sites
Which algorithm is that? Do share.

Kami no Itte ga ore ni zettai naru!

##### Share on other sites
You calculate the center point of the polygon, by adding up all the vertices and deviding by the number of vertices (like finding the ''average'' point)

Then you can find vectors from the center point to any vertex in the polygon.

By comparing 2 vectors (with dotProduct), you can determine the angle between the 2 vectors.

So, starting with any vertex in the poly, find a vector by subtracting it from the center point. Find vectors similarly for all other vertices in the poly.

Taking any arbitrary vertex as the ''first'' vertex, you can determine the next vertex by seeing which vector has the smallest angle with your start one.

This way, you get your vertices ordered, although you dont know if they are CW or CCW at this point. By looking at the normal of the poly, you can tell if you need to reverse your verts or not, depending on whether you want CW or CCW.

I havnt implemented it yet, and there are probably a bunch of quirks and special cases I havnt thought of, but I dont think these will affect the time complexity of the algorith, except by a constant factor, and it is not NP as far as I can tell.

##### Share on other sites
If your polygon is simple convex, it should work.

For an arbitrary, possibly concave or self-intersecting
polygon, the problem of ordering into CW or CCW is quite
a bit harder (if even possible).

For one thing, finding the "center" of the polygon is, um,
not easy.

I mentioned NP because your original problem didn''t have
the convex constraint.

Try the following (number denotes a vertex):

.................
.............1...
.................
...4....3........
.................
.............2...
.................

The polygon is supposed to look like 1324 (in CW order).

Now imagine for 100+ points.

Kami no Itte ga ore ni zettai naru!

##### Share on other sites
Its true I didnt mention that my polys were convex in my original post, but I did say it in a subsequent post. Besides, isnt it safe to assume that everyone''s polys are convex unless otherwise stated? I mean, who uses concave polys in games anyway?

Seriously though, I thought it was rare to use for example a square instead of a triangle, let alone some weirdo concave shape.

Finding the center for convex polys is as simple as finding the average of all the vertices, as I mentioned. It doesnt even have to really be the exact center for my purposes, just a point that is inside the polygon. It just so happens that for convex polys, its easy enough to find the exact center that you might as well do it.

Thanks for all your input. I might post back here again before my task is complete.

##### Share on other sites
Here's some code I wrote to do the sorting of vertices. Sorry its not commented, its just one of things I wrote and forgot about. My polygon3d struct used linked lists for the vertices so it may be a bit hard to follow, but im sure if you spend some time with it, itll make sense.

int SortVertices2 (Polygon3d *poly){	double BiggestAngle;	double dp;	Vertex3d *Biggest=NULL;;	Vector3d a;	Vector3d b;	Vector3d an;	Vector3d bn;	Vertex3d *tempvert1;	Vertex3d *tempvert2;	tempvert1=poly->vertexlist;	a.x=tempvert1->next->vertex.x-tempvert1->vertex.x;	a.y=tempvert1->next->vertex.y-tempvert1->vertex.y;	a.z=tempvert1->next->vertex.z-tempvert1->vertex.z;	an.x=a.x;	an.y=a.y;	an.z=a.z;	a=Normalize(&a);	for (int i=0; i<poly->num_pts-1; i++) {			BiggestAngle=1;				tempvert2=tempvert1->next;		for (int j=i+1; j<poly->num_pts; j++) {						b.x=tempvert2->vertex.x-tempvert1->vertex.x;			b.y=tempvert2->vertex.y-tempvert1->vertex.y;			b.z=tempvert2->vertex.z-tempvert1->vertex.z;			bn.x=b.x;			bn.y=b.y;			bn.z=b.z;			b=Normalize(&b);						dp=DotProduct(&a,&b);			if (dp<BiggestAngle) {				BiggestAngle=dp;				Biggest=tempvert2;			}			tempvert2=tempvert2->next;		}		a.x=tempvert1->vertex.x-Biggest->vertex.x;		a.y=tempvert1->vertex.y-Biggest->vertex.y;		a.z=tempvert1->vertex.z-Biggest->vertex.z;		an.x=a.x;		an.y=a.y;		an.z=a.z;		a=Normalize(&a);		SwapVertices (tempvert1->next,Biggest);				tempvert1=tempvert1->next;	}	return 1;}

Stefan Hajnoczi originally wrote a version in his paper here:

http://folk.uio.no/stefanha/MAPFiles.pdf

Stefan's original version had an issue where the angle between the vectors formed by the center of the polygon and two vertices of the polygon would end up being smaller than the angle between the current vertex and the vertex thats supposed to be next in order. Hard to explain really, but it would end up with incorrectly ordered vertices. I found a fix to the problem and implemented it in my code, but its been so long since I wrote this, I forgot what the fix boiled down to and how it differed from his code.

I have both versions still in code and I think my version searched for the largest angle rather than the smallest.

One last thing, this might actually sort them in CW order. Heh, I really dont remember.

In any event, I hope this helps.

-=[ Megahertz ]=-

[edited by - Megahertz on January 12, 2004 1:32:43 PM]

[edited by - Megahertz on January 12, 2004 7:03:33 PM]

##### Share on other sites
Ok I looked over my code and figured out how mine works =)

Basically rather than using a center point as a base for the vectors, I basically pick 2 vertices, then create a vector using these 2 vertices. I then iterate through the other vertices and find biggest angle between the two vectors I can find. Once I do, I know that the last segment I created with the 3rd vertex is the first edge of the polygon. From there I just continue using the other vertices to create vectors and compare the angles, every time i find the biggest angle, that segment is the next edge of the polygon.

This method will only work with convex polygons as far as I can tell.

-=[ Megahertz ]=-

##### Share on other sites
Thanks, Megahertz! That helps a whack.

I havnt had a chance yet to look through your code in detail, but one thing I noticed is that you use a variable called biggestAngle and in your explanation I think you even said that you look for the biggest angle.

As far as I know, this is incorrect. Im not saying its an incorrect way of doing it, just that you seem to be confused.

The dotProduct funcion will return a float value between -1 and 1. These values can be mapped to degree angles that we are more used to. For example:

-1 is 180 degrees
0 is 90 degrees
+1 is 0 degrees

So when you say "biggestAngle", and you are referring to the -1 to +1 value returned by this code:

dp=DotProduct(&a,&b);

, then I think what you actually mean is "smallestAngle", since they are inversely related. For example, the biggest value of "biggestAngle", as you call it, would be +1, which is actually 0 degrees, which is the smallest angle.

Anyway, aside from that I expect to learn a lot from your code, esecially with regard to that special case where you can get the wrong vertex as you said.

Thanks again. If you like, I can post my final version when I get it working (complete with comments! oohhh! ahhh!)

[edited by - AndreTheGiant on January 12, 2004 5:00:38 PM]

##### Share on other sites
Dot product is given by

u * v = Len(u) * Len(v) * cos(angle between u and v)

so to get the cosine you should divide by Len(u)*Len(v)

The problem is that dot-product give you no info about versus; in practice if a second vertex is CW or CCW you get the same result (because cos(-x)=cos(x) )

You should use also the cross product to resolve this...

given two 2D vector in (x,y) plane the cross product is

u ^ v = ((ux*vy)-(uy*vx)) z = K z // z is the versor that goes from your monitor to your face...

Note that K is also proportional to sin(angle between u and v)
and it's positive if v is CCW from u, negative if v is CW and zero if u and v are parallel (0 and 180 degree)

Application of math

Consider a point O that is inside your polygon and consider an arbitrary vector (for example v = (0,1) )

For every vertex compute the angle between u = (vertex-O) and v
and use this value to 'sort' your vertices

L = Len(u)*Len(v)
cosa = (u*v)/L
sina = ((ux*vy)-(uy*vx))/L

to get the angle...

REAL  Math::GetAngle(REAL cosa, REAL sina){  cosa = Clamp((REAL)-1, cosa, (REAL)1);  REAL angle = ACos(cosa);  return(sina<0 ? -angle : angle );}

If the angle is positive u is CW and vicevers if the angle is negative u is CCW; in the case the angle is negative you can add 2PI to this value to convert angles to positive values; simply use this value to sort vertices in CW order or invert the list and get CCW.

To extend to 3D your problem you should compute the extended cross product w = u^v and normalize it.
Compute the plane-normal n of your poly (select 3 arbitrary vertices and put n = (P2-P0)^(P1-P0) and normalize it).
Then compute K = w*n (dot prod)-> K give you sina.

Compute the 'normalized' dot product
cosa=(u*v)/(Len(u)*Len(v))

Use sina, cosa to get the angle, add 2PI if it is negative, sort in descending order (CCW).

The problem in 3D is that you cannot really sort your vertices in CW or CCW order because...it depends from the observer! If you go behind the poly the order is inverted.
However you can disable the back face culling...

That's all, sorry for my english...

[edited by - blizzard999 on January 12, 2004 7:19:24 PM]