Get the boundary of a mesh: the algorithm and C# implementation

06 Sep

Given a mesh, we might occasionally want to filter those internal vertices and keeps only the outline or silhouettes. But how to do that? The problem came to my mind several years ago, when the Department of Mechanical Engineering I was serving need to drive a laser cutter to trim some shapes. So I decided to refresh my mind and use it in my current project in text morphing.

So the input might be some triangulated mesh, and the output is the silhouettes, as shown below.

image  image

Looking at my past source code, I soon found the solution. Considering the below simple rectangle, where two triangles exist:


For two triangles <1,2,3> and <1,3,4>:

  • Step I: we first get all edges  <1,2>, <2,3>, <1,3>, <1,3>, <3,4>, <1,4>, here we use point index to refer to a vertex.
  • Step 2: We remove the internal edges, which occur more than once. In our case the edge <1,3> satisfy this.
  • Step 3: Keep only edges that occur once, we got the outline edges <1,2>, <2,3>,<3,4>, <1,4> only!

Simple, but it worked! Below is the C# Snippet:


Here we use a tuple to represent an edge:image

The tricky part is the EdgeComparer class, where we regard edge <1,2> and edge <2,1> as the same edge, i.e. an edge from point 1 –> point 2 is identical to an edge from point 2 –> point 1.


By grouping all edges according to their emergence multiplicity, we can easily filter out those “duplicate” or internal edges, and therefore external boundaries or outlines are kept.

Thanks to C#’s LINQ feature, the above algorithm is very easy to implement! Enjoy!

Leave a comment

Posted by on September 6, 2013 in CAD, CAX, Dotnet/C#, Programming


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: