set insideCounts = 0
set outsideCounts = 0
for each pair of joined edges in the polygon
// Get the two edges in the pair: edge1 ends at edge2's first point
let edge1 = first edge of pair
let edge2 = second edge of pair
// Consider these two edges as edges of a triangle and get the midpoint of this triangle
midPoint = midPointOfTriangle( edge1.point1 , edge2.point1, edge2.point2 )
// Get the normals to the two edge vectors: in the case of a clockwise
// polygon they will point towards the inside of the polygon.
edge1Norm =
{
- (edge1.point2[y] - edge1.point1[y]) ,
edge1.point2[x] - edge1.point1[x]
}
edge2Norm =
{
- (edge2.point2[y] - edge2.point1[y]) ,
edge2.point2[x] - edge2.point1[x]
}
// Now get a vector going from the shared point of the two edges to the midpoint of the triangle
testVector =
{
midPoint[x] - edge1.point2[x],
midPoint[y] - edge1.point2[y]
}
// Now test if this point is inside the 'triangle' mentioned previously by
// dotting the testVector with the two normals we got. A true point inside
// triangle test would check against the normals of all three triangle edges.
// But for this test we only use two: if either of the dot products is zero
// then consider the point to be 'outside' the triangle.
if ( dot(testVector,edge1Norm) < 0 or dot(testVector,edge2Norm) < 0 ) then
outsideCounts = outsideCounts + 1
else
insideCounts = insideCounts + 1
end if
end for
// See if the 'inside counts' are more or equal to the outside counts. If so polygon is clockwise
if ( insideCounts >= outsideCounts ) then polygon is clockwise else anti-clockwise
Determining winding order in 2D polygon
Author
Hi everyone.
I'm currently working on a 2D game where the main structure of the level will be made out of polygons. Now these polygons can be either convex or concave, and may be wound in clockwise or counter-clockwise order. In order to render concave polygons with OpenGL (and for later collision detection) I am going to need to triangulate the polygon. I've written the code to do the triangulation and it works fine in the case of clockwise polygons, but fails if the winding order is in the opposite direction. This is down to simply to the triangulation method I am using. Although I could possibly adopt a different approach that may work with anti-clockwise polygons, I would rather the resulting triangles be in clockwise order to simply things later. Ultimately, the main thing I want to avoid is forcing the level designers of the game to sketch out these polygons in clockwise order- like most early 'Doom' level editors did as some of you may remember.
So what I need to be able to determine is simply if the polygon is wound clockwise or anti-clockwise, and fix the order if it is anti-clockwise. I've seen methods for determining this on Paul Bourke's geometry page and on mathworld, but unfortunately these approaches only work for convex polygons. If anyone has encountered or knows of any methods for determining winding order with concave polygons then I would greatly appreciate your help!
Coincedently, I have been trying to figure out a way of doing this on my own and have come up with the following ( crazy ass! [smile] ) way of determining the winding order. It seems to work in every conceivable case I've sketched, and I've sketched a lot.. I don't know why this is, or if it is based on some relation or thereom. I don't want to use it if at all possible though since I can't guarantee that it works all the time. Perhaps someone may recognise some of this from somewhere- probably not though..
What I am considering is doing the following:
Would it be possible for you to share your method of triangulation? Just the name of the algo you're using would be fine -- this is something we'll have to tackle soon ;)
Author
Cool, thanks for your help daftasbrush! Thats seems like a very nice way of doing it.
Turns out that crazy method of mine didn't work either in all cases. It is based on the assumption that for each pair of edges in the polygon, the number of times the angle between the two edges (on the inside of the polygon) is <= 180 degrees is always greater than the number of times the angle is > 180 degrees - which is not true as I have sketched some cases where it is shown otherwise.
Not to be beaten however, I've taken the logic that if it doesn't work one way then it probably works the opposite way. [smile]
The algorithm now first assumes that the polygon is in clockwise order, and if it fails (as it will always do in the case of a counter clockwise poly) it then trys to treat the polygon as counter-clockwise and repeats the triangulation process again- changing the process slightly with that assumption in mind. It's slightly wasteful doing this twice, but I don't really care to be honest as this is only a pre-processing step and speed is not that important.
Sure. I don't know what the name of the algorithm is, just kinda sat down and tried to figure out how to do this myself. I can give you the source code if you like. It's surprisingly involved ( small details like co-linear lines were screwing things up for a while till I fixed that ) , but it seems to be working fine now in all cases.
Turns out that crazy method of mine didn't work either in all cases. It is based on the assumption that for each pair of edges in the polygon, the number of times the angle between the two edges (on the inside of the polygon) is <= 180 degrees is always greater than the number of times the angle is > 180 degrees - which is not true as I have sketched some cases where it is shown otherwise.
Not to be beaten however, I've taken the logic that if it doesn't work one way then it probably works the opposite way. [smile]
The algorithm now first assumes that the polygon is in clockwise order, and if it fails (as it will always do in the case of a counter clockwise poly) it then trys to treat the polygon as counter-clockwise and repeats the triangulation process again- changing the process slightly with that assumption in mind. It's slightly wasteful doing this twice, but I don't really care to be honest as this is only a pre-processing step and speed is not that important.
Quote:Would it be possible for you to share your method of triangulation? Just the name of the algo you're using would be fine -- this is something we'll have to tackle soon ;)
Sure. I don't know what the name of the algorithm is, just kinda sat down and tried to figure out how to do this myself. I can give you the source code if you like. It's surprisingly involved ( small details like co-linear lines were screwing things up for a while till I fixed that ) , but it seems to be working fine now in all cases.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement