Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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

share|improve this question

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
I need to understand it because it's the only paper I found for fixing holes in a polygon mesh. Although their hole finding algorithm requires a triangle mesh. Most poeple have been telling me to use software like Blender to fix non-watertight meshes. I need algorithms which are independent of software --- people do not seem to understand that. My understanding of k-d trees is that they are data structures for splitting k-dimensional space into nodes. I'm finding step 2 hard to understand. –  Adeeb Feb 10 '13 at 8:29
    
One way you can do it is to place it in an octree based on their circumcenter. If the distance between the two centers is less than the sum of both radii, it is a possible connection. Otherwise, sorry but I'm not sure how they implemented it and I don't blame you for not understanding their obscure method =/. –  Yuuta Feb 10 '13 at 8:46

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.