I have a triangulated mesh. Assume it looks like an bumpy surface. I want to be able to find all edges that fall on the surrounding border of the mesh. (forget about inner vertices)
I know I have to find edges that are only connected to one triangle, and collect all these together and that is the answer. But I want to be sure that the vertices of these edges are ordered clockwise around the shape.
I want to do this because I would like to get a polygon line around the outside of mesh.
I hope this is clear enough to understand. In a sense i am trying to "De-Triangulate" the mesh. ha! if there is such a term.
Traversal Code (not efficient - needs to be tidied up, will get to that at some point) Please Note: I store each segment in the chain as 2 indices - rather than 1 as suggested by Darren. This is purely for my own implementation / rendering needs.
Well as the saying goes - get it working - then get it working better. I noticed on my above example it assumes all the edges in the edges array do in fact link up in a nice border. This may not be the case in the real world (as I have discovered from my input files i am using!) In fact some of my input files actually have many polygons and all need borders detected. I also wanted to make sure the winding order is correct. So I have fixed that up as well. see below. (Feel I am making headway at last!)
Boundary edges are only referenced by a single triangle in the mesh, so to find them you need to scan through all triangles in the mesh and take the edges with a single reference count. You can do this efficiently (in
O(N)
) by making use of a hash table.To convert the edge set to an ordered polygon loop you can use a traversal method:
[v_start,v_next]
and add these vertices to the polygon loop.[v_i,v_j]
that has eitherv_i = v_next
orv_j = v_next
and add the other vertex (the one not equal tov_next
) to the polygon loop. Resetv_next
as this newly added vertex, mark the edge as visited and continue from 2.v_start
.The traversal will give a polygon loop that could have either clock-wise or counter-clock-wise ordering. A consistent ordering can be established by considering the signed area of the polygon. If the traversal results in the wrong orientation you simply need to reverse the order of the polygon loop vertices.