Manifoldness repair

[pca006132]

Outline

Repair triangle soup that are not manifold.

Details

Basically, a valid solid mesh should be both manifold and has no self-intersection. However, models from the internet may contain defects. This project is about coming up with an algorithm that converts and repair a triangle soup into a manifold mesh.

This will contain a lot of heuristics, basically what we need is:

• Stitching faces together, and maybe join faces that are close enough.
• Fill holes.
• Duplicate vertices and edges such that the result is a manifold in terms of connectivity.

Expected Outcome

Implementation of said algorithm.

Future Possibilities

Project Properties

Skills

• C++
• Graph data structure.
• Algorithms.

Difficulty

Hard.

Size

Long (350h)

Additional Information

• Potential mentor(s): @elalish @pca006132
• Organization website: https://manifoldcad.org/
• Communication channels: https://github.com/elalish/manifold/discussions

[elalish]

We have a starter algorithm for this: Merge() that only merges nearby edges. It's conservative and gives up if the mesh is not close to manifold to begin with. Still, it's a reasonable place to start.

We do not expect a result free of self-intersections for this project - that's a separate project.

In general, a non-manifold mesh can require a lot of heuristic additional surfaces, so part of this project is artistic in nature: what additions make the most sense and look reasonable?

[Abhyudaya30Singh]

Hi @elalish @pca006132 , I'm Abhyudaya Singh, and I would love to contribute to this issue! I notice the Merge() function assists in stitching together neighbouring edges. What are its existing constraints when working with non-manifold meshes, specifically situations where the merge vectors were compromised? Are there known failure modes or edge cases that need special treatment?

[pca006132]

I think you can check the definition of manifoldness first. By non-manifold, we typically mean meshes with holes, as well as meshes that are non-manifold geometrically (due to shared vertices/edges). I am not sure what you mean by "the merge vectors were compromised".

[elalish]

Generally the merge vectors are not so much "compromised" as missing entirely. Merge() can only stitch together verts within tolerance of each other - it simply hopes this is enough to make a manifold. For any larger gaps or holes, a more serious bunch of heuristics are necessary. Our triangulator may help with hole filling, but it may need some help with significantly non-planar ones. Perhaps something like our CreateFaces function could first break the holes into more nearly planar patches? Anyway, there are lots of possibilities. First step is to go find a set of popular meshes that aren't manifold (which is most of them), so we can test.

[elalish]

I'd recommend looking at art / video game style assets and 3D scans - they often have much worse manifoldness than e.g. 3D printing meshes.