Conversation
|
Some thoughts on the geometric version. Ideally, if a solid extraction exists, then it should be found. It's possible for this to still be ambiguous (the bottom steps of this model could have been two components or one): This extraction is essentially the same as the nearly combinatorial But in this case, we could either do B→C,D→A or B→A,D→C because both have no skips in cyclic order. We could further make a geometric rule to prefer the most convex out or something based on dihedral angle difference. |
|
Another thought, in "Progressive Shell Quasistatics for Unstructured Meshes" we jiggle nearly colliding vertices into intersection free configurations. Seem unprincipled but I convinced myself that the problem is sufficiently hard that a randomized algorithm is a reasonable response. I think a similar approach would work well for finding a non-self-intersecting, manifold mesh that's close(est) to the input:
Would also be a good use case for the dynamic AABB that just merged. |
The previous method (and the old one in gptoolbox) was cool cause it wouldn't just create boundaries at the non-manifold edge chains. It would identify big manifold components across non-manifold edges. Unfortunately, it was just getting lucky. It would find those if they were in order in the list of faces, and fail to correctly split the mesh oetherwise. (Some of the new tests will fail the old code).
At one point I set out to implement "Cutting and Stitching: Converting Sets of Polygons to Manifold Surfaces" [Guéziec et al. 2001] but its details are a bit confusing and it's not quite written with proofs so I got nervous I'd make an elaborate implementation and still have failure cases.
Instead, I implemented the "obvious" thing. Split all the edges, then try to stitch them back. Only allow a stitch if the resulting mesh continues to be manifold. The order still matters to get nice components, so this implementation does a depth-first traversal on stitched edges as it goes.
This is purely combinatorial. It'd be cool to use geometry to prefer outputting a "solid" mesh.
Finally, "manifold" doesn't necessarily mean orientable, but this code is assuming the output should also be orientable (I claim the common case). It shouldn't be too hard to add a flag that allows non-orientable output.