Finding holes in mesh

Question

I have a mesh that has holes. I found a paper, An Automatic Hole-Filling Algorithm for Polygon Meshes

It details an algorithm that uses a k-d tree for finding holes (from a manifold triangle mesh). The steps are as follows:

Step1: Compute the center of each triangle and the correspondences between the center and three vertexes of the triangle;

Step2: Set up the Kd-tree according the centers of triangles;

Step3: Search the Kd-tree and check up the topological connectivity of the corresponding edges, and find the boundary edges;

Step4: Distinguish the different boundary loops according to the topological connectivity of vertexes;

I do not not understand how this algorithm actually finds the hole, can some please explain this in Layman's terms so that I can implement it --- I know there are probably better way out there of finding holes but I need to understand this particular algorithm.

Please help

Answer 1

I took a glance at the paper and it was very vaguely written (even for academic papers).

If you check the papers that cited them, they only used the paper as reference for their filling algorithm and not their "novel" hole-detecting algorithm.

It raises questions like:

---

What is k?

What is the center? (there are different centers, like the circumcenter [what I'm thinking they used] in Delaunay's algorithm for meshing)

What topological connectivity?

---

What is the reason you want to understand that specific algorithm? (I wrote this as an answer since it's nicer to write haha)

EDIT:

If we know the adjacency matrix of the mesh, the solution is trivial (check for triangles (quads) with less than 3 (4) edge connections)

Otherwise, we would normally check every edge with every other edge O(n^2) with n triangles (meshes)

If we wanted a kd-tree implementation, we would get anywhere from O(nlog(n)) to O(n^2) since it's not too easy to implement self-balancing kd-trees.

Let's assume we have a kd-tree implementation done.

We get the circumcenters of all triangles (quads) and place them in a kd-tree. If the distance between two centers is less than the sum of the two corresponding radii that come from the circumscribed circles, they are possible connected triangles (quads).

That's all I got, maybe someone else can give deeper insight in this problem.

Answer 2

I don't know about using a KD Tree for this but to find holes in a triangular mesh you must find all the border edges of the mesh which belong only to one triangle.

One algorithm would be to iterate over every edge of the mesh and maintain a set of border edges. For every edge, if the edge is not in the set, then add it. If the edge is already in the set, then remove it. Once you have iterated over all of your edges this set will contain all the border edges of your mesh.

You can then start with any border edge and add neighboring border edges to it until you make your way back to the first border edge. You just found a hole. Repeat this until no more border edges are left and you've found all the holes.