Concave Hull

Working on some arcane aspect of my landscape pipeline I find I need to identify whether points in my mesh are part of the “outside edge” of the mesh. I am familiar with the calculation of a Convex Hull – but this creates the shorest line that connects encompasses the mesh, and is not limited to triangles that already exist in the mesh. This means that the Convex Hull probably does not resemble the shape of the original mesh.

The solution to the problem jumped into my head rather than searching for it on the web – it was a really simple solution when I considered what made an “exterior” point different from an “interior” point. We can visually see an interior point because it is completely surrounded by triangles – but what does that “surrounded” mean mathematically ?

It means that the sum of all the angles between the subject point and all the other points of the triangles it forms part of are exactly 360 degrees. Anything less than that; then the point is an “exterior” point.

In order to determine a convex hull for a point cloud I follow the following logic

  1. Triangulate the mesh.
  2. For each point, select all the triangles it it part of
  3. For each of those triangles, calculate the angle formed between the subject point and the other two points.
  4. Iterate all the triangles that use this point, and sum the angles found.
  5. If they are less than 360 then this point is not wholly surrounded by triangles and is therefore exterior.

This method works for meshes that do not have interior holes in them, as the points on the hole boundary would be treated as part of the Concave Hull.



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