I created a smaller test case with singular vertices. As you can see in the image below, the holes are being wrongly identified and we have triangles overlapping eachother.

The left hole is identified in CW and middle hole is in CCW rotation.

from repair.

The left hole is identified in CW and middle hole is in CCW rotation.

So, the bad normal vectors are due to the hole detection algorithm identifying some holes clockwise and some others counter clockwise. Interesting 🙄

from repair.

The result of filling the mesh can be seen here:

from repair.

As can be seen above:

1. Holes are actually filled, depending upon the correct threshold value.
2. But some new triangles have the reverse normal vector. It means the vertex order is somehow reverse.

from repair.

Apparently, the hole detection algorithm is problematic. Looks like this is what's happening:

1. A hole is wrongly detected. The wrong hole consists of actual triangles.
2. The wrong hole is filled with triangles. This causes multiple triangles on top of each other.

But I still don't understand why the newly created triangles have the wrong normal vectors. I think maybe we have two problems now:

• Hole detection algorithm is bad.
• Hole filler normal vector is sometimes bad.

I'm not sure 🙄

from repair.

Note: Vertices of faces in a 3D object must be ordered in CCW orientation when looking at their front side. If we have vertices $v_1, v_2, v_3$ in CCW order forming a triangle face, the normal of that face is calculated as CrossProduct($v_2-v_1, v_3-v_1$). Following the right hand rule, this makes the normal vector point out towards the viewer.

The Liepa algorithm also requires holes to be in CCW orientation. The reason for this, is that in the "Trace Algorithm" (please refer to Section 6.2 of "Filling Gaps in the Boundary of a Polyhedron" by Barequet and Sharir), uses this order for adding new triangles. If the hole vertices are $v_1, v_2, ..., v_N$, a new triangle is added as $v_i, v_o, v_k$ with $i < o < k$. The result is that the new triangles added use the same orientation as the input hole.

So in summary, if the input hole is in CW orientation, the added triangles are also in CW which is wrong and if the hole is CCW, the triangles are CCW. Singular vertices cause the holes to be wrongly identified. Sometimes the hole is correctly identified but with the wrong orientation, sometimes the hole is identified completely wrong, as seen in some of the images above.

from repair.

Options

1. Research a new hole-filling method by inspecting blender's source code.
2. Lets consider this a special case that does not often happen in real applications, skip it for now.
3. Try to fix the hole-detection code to work correctly when reaching singular vertices.
4. In order to create less problems for the hole-filling algorithm, the intersection checking method can be edited to let edge cases slide. This causes less triangles to be deleted, and perhaps less issues will arise from hole-filling.

from repair.

For now, we will move forward with option 2 and close this issue.

from repair.

Mesh repair has lower priority, as discussed with others. That's why it's closed.

from repair.