Traversing the boundary points of a polygon made of connected triangles
I have a two dimensional polygon mesh made of connected triangles represented like this:
- vertex array:
V = A, B, C, D, E, ...
- index array, triangle vertex indices in groups of 3 in counter-clockwise-order:
I = 0, 4, 3, ...
(so that e.g.V[0], V[4], V[3]
which isA-E-D
forms a triangle)
http://img694.imageshack.us/img694/8968/meshg.png Example mesh
Now i want to traverse the boundary points in counter-clockwise-order, the starting vertex doesn't matter:
G, H, A, D, C, F
The reason for this is that i want to compute dynamic 2D shadows like in this article: http://www.gamedev.net/reference/programming/features/2dsoftshadow/page3.asp
Whats the best way to do this? I thought about computing a convex hull, but this seems too expensive because it's not using the triangle vertex indices, there has to be a better way.
Is there a way to make it work even for several polygons in one represen开发者_Go百科tation so that i get a list of boundary point lists for every connected polygon?
Thanks, abenthy
Here's one way:
- Find the boundary edges, this is done by traversing all the edges of the triangles and removing all edges which occur twice (because all edges except the boundary edges are shared by two triangles) (Also remember
(A, B)
is the same edge as(B, A)
). - You now have a list of the boundary edges. Start with one of them and successively loop through the rest of the edges until you find one which is connected, append this edge and remove it from the list. Repeat until the boundary is closed.
Since the triangles are counter clockwise the computed boundary will also be counter clockwise. This method is good because it doesn't need the actual positions of the vertices, it only uses the topology specified by the indices.
精彩评论