search

gkjohnson / three-bvh-csg

A flexible, memory compact, fast and dynamic CSG implementation on top of three-mesh-bvh
MIT License
602 stars 46 forks source link

Add utility to confirm manifold / solid-ness of a geometry #27

Closed gkjohnson closed 1 year ago

gkjohnson commented 2 years ago

Related to #3

Thoughts

Also see #96

gkjohnson commented 2 years ago

Currently the result of a CSG is not properly manifold. In order to achieve that we need to make sure that all sibling edges are clipped symmetrically so they line up. #19 could help.

johncalvinyoung commented 2 years ago

@gkjohnson can you expand on symmetrical clipping here and how #19 can help? Been noticing that the CSG result mesh is not manifold, frequently has (significant) missing triangles in my use case (based on ExtrudeGeometry), always loses some sliver triangles destructively (i.e. not actually 0-area). Might be able to drive some improvements if I better understand your existing thinking on this.

gkjohnson commented 2 years ago

Yes there are still a number of issues to be figured out. The logic for splitting triangles is very susceptible to floating point error issues so they can be hard to track down. Perhaps there's a more robust way to handle it that's definitely an are that needs work when talking about missing tris. See the bug list for some of the known issues and areas that need work in that respect. And feel free to add new issues with new bugs an I can help point you in the right direction with some more specificity if you're interested in helping out.

In terms of manifoldness - with the way triangles are currently split means that the final model can result in T-junctions at edges which means there is not a 1-to-1 map of edges:

image

Specifically we shouldn't add any additional edge vertices to a triangle if we can avoid it. This is also leads to a performance issue since these types of T-Junctions mean the half-edge structure cannot be fully generated. I've made #4 to investigate this further. If that's something you're interested in contributing to it would be a big improvement to the project.

how https://github.com/gkjohnson/three-bvh-csg/issues/19 can help

Sorry I think I likely meant to link to #4 or #51 when writing the comment. By symmetrically I meant that when a triangle is split we must ensure that the sibling triangles wind up with edges that are split in the same way so they can be joined in the half edge structure.

gkjohnson commented 1 year ago

Created a "FragmentedEdgeMap" but it seems to suffer from floating point error. Putting this aside for now.

https://github.com/gkjohnson/three-bvh-csg/tree/frag-edge-map