Traversing the boundary points of a polygon made of connected triangles

Question

Hello

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 is A-E-D forms a triangle)

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 representation so that i get a list of boundary point lists for every connected polygon?

Thanks, abenthy

Answer 1

Here's one way:

1. 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)).
2. 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.