How to detect a hole in the triangular mesh?

Question

Actually, I can detect border or edges of a convex triangular mesh by checking which edge of the triangle does not have any neighbor. So, if a mesh has some holes, then we can highlight that part easily because we have edge vertices.

But the issue is, if we just have the edge vertices or borders, how can we know that the mesh has some holes ? and how many holes the mesh has ?

I thought enough about this issue, but unable to get it, any idea ? What should be the condition or check for hole detection ?

After detection of a hole I want to fill it. But first thing is to detect it ?

Thanks.

Answer 1

Assuming that the mesh is connected and you can highlight all the boundaries. You are left with all the holes + one additional boundary which is that of mesh itself. You can just discard the boundary with the biggest length of them and get all the holes.

Answer 2

A triangular mesh derived from a scanner (eg. Kinect) can have small fragments (isolated patches) as well as small holes. I suggest a hole can generally be detected by counting the number of vertices that neighbor the vertices on the boundary. It is not a hole if there are fewer neighboring vertices than boundary vertices.

Answer 3

My answer will only work for a closed mesh, but it will handle the case of concave and convex holes.

For the sake of explanation, lets imagine a 2D mesh.

Calculate a bounding box for the mesh. In our example the bounding box needs to store min and max values for the X and Y axis, and a corresponding vertex index for each value:

struct BoundingBox
{
  float minX,maxX,minY,maxY;
  int vminX,vmaxX,vminY,vmaxY;
}

Iterate over every vertex in the mesh, growing the bounding box as you add each point. When a vertex is responsible for changing one of the min/max values, store or overwrite the corresponding vmin/vmax value with the vertex mesh index.

E.g.

BoundingBox bounds;
bounds.minX = verts[0].X;
bounds.maxX = verts[0].X;
bounds.minY = verts[0].Y;
bounds.maxY = verts[0].Y;
bounds.vminX = bounds.vmaxX = bounds.vminY = bounds.vmaxY = 0;
for (int i = 1; i < numVerts; i++)
{
  Vertex v = verts[i];
  if (v.X < bounds.minX) { bounds.minX = v.X; bounds.vminX = i; }
  if (v.X > bounds.maxX) { bounds.maxX = v.X; bounds.vmaxX = i; }
  if (v.Y < bounds.minY) { bounds.minY = v.Y; bounds.vminY = i; }
  if (v.Y > bounds.maxY) { bounds.maxY = v.Y; bounds.vmaxY = i; }
}

Now iterate over your boundaries until you find one which contains ALL the vertices you gathered in the bounding box. This is your outer boundary. The remaining boundaries are holes within the mesh.