Add utility for determining separated geometry

[gkjohnson]

Related to #3

Maybe related to #43

ie if a CSG operation causes two piece of a geometry to become separated and you want them to respond to physics, etc

[zalo]

I'm about to look into this for my own project (predictably, for physics destruction 😄 ).

Do groups matter or are they primarily just for tracking which brush contributed to a face?

If groups are disabled, should I expect to be able to traverse all the "connected" triangles on a manifold, or will the split faces/vertices cause me trouble?

EDIT: Seems like I'm running into #169 / #77 (?), which appears to be preventing CSG outputs from appearing as watertight / fully-connected... perhaps it has to do with which triangle attributes I'm preserving...

[gkjohnson]

Hey @zalo!

Do groups matter or are they primarily just for tracking which brush contributed to a face?

Groups are not required and the generated groups are just so that materials from each source brush can be retained on the result. If you don't need those sub materials then there's no requirement to use or generate the groups.

EDIT: Seems like I'm running into #169 / #77 (?), which appears to be preventing CSG outputs from appearing as watertight / fully-connected... perhaps it has to do with which triangle attributes I'm preserving...

Unfortunately this project isn't guaranteeing manifold results at the moment. The implemented algorithm for splitting triangles just splits along each intersected edge resulting in vertices that do not necessarily match across triangle faces. I'd been wanting to implement constrained delaunay triangulation for triangle clipping (#213) but time and other commitments haven't afforded it, yet. This should give a more expected result (ie edges matching and lining up), though due to floating point math issues you'd likely still see some cases where a non-manifold result is returned.

Manifold 3D is a CSG library aiming to guarantee a manifold result from manifold meshes - I haven't taken a close look at that project to see how it's guaranteeing that but I'm interested. I've created #219 to discuss creating a "ManifoldEvaluator" alternative to "Evaluator" for taking advantage of that project with the same CSG API if you have any other thoughts there.

Some day I'd like to get the CDT triangle clipping working in this project but with other work I'm not exactly sure when that will be.

[zalo]

Nice! I understand the bit on free time; I’m grateful for both your csg and bvh projects as they are 😄

I’m glad you’re also a fan of manifold; I’m a long time user(and contributor) to anifold (I’ve even got an open (#666💀) Minkowski Sum PR over there, which is gated on some non-manifold precision behavior we haven’t been able to isolate there too, so even it isn’t immune 😅).

For my little hobby app, I wrote a mostly common interface for both three-mesh-csg and manifold already:
https://zalo.github.io/PhysicsWorkshop/
https://github.com/zalo/PhysicsWorkshop/blob/feat-sphere-packing/src/CSGManager.js

(Please forgive it not working well on mobile and the wonky physics; I’m trying out hacky shape matching + collision proxies to get around no physics engine supporting non-convex meshes… I have a few more tricks to try for better particle distribution, like perhaps this one: https://www.shadertoy.com/view/lfKfWK (also enabled by three-mesh-bvh 😄), but if I’m really lucky, I can get my instant voronoi convex decomposition working and solve it forever…).

I was doing little timing comparisons between the two, and three-mesh-csg stacks up really favorably with the timing! (And it preserves hard mesh normals by default, which I’m having trouble interfacing with manifold to do…)

The dealbreaker in favor of Manifold is that it happens to have a “decompose” function, which works great (except it will also “decompose” hollow voids within a manifold if there are no triangle connections 💀).

[gkjohnson]

gated on some non-manifold precision behavior we haven’t been able to isolate there too, so even it isn’t immune

Good to know - I was wondering what kind of incantations must have been required to get guaranteed manifold results. I've seen that numbers are converted to integers in some cases to make corner cases easier to handle but I'm not sure if that's being used here.

I was doing little timing comparisons between the two, and three-mesh-csg stacks up really favorably with the timing! (And it preserves hard mesh normals by default, which I’m having trouble interfacing with manifold to do…)

I'm not sure if Manifold provides this and you may have already tried it but of you have a mapping of which triangle each resulting polygon was split from you should be able to calculate the barycoordinate and use that to generate an interpolated version of each vertex attribute. It's basically what this project is doing.

The dealbreaker in favor of Manifold is that it happens to have a “decompose” function, which works great (except it will also “decompose” hollow voids within a manifold if there are no triangle connections 💀).

For this project it won't be exactly right but it is the case that the resulting clipped triangles will share vertices with sibling triangles, even if they don't share a full half edge. It won't be perfect but these vertex connections could be used to determine the "connectedness" of independent sub meshes to get a similar type of functionality.

---

It looks like someone else may be looking into it but if that doesn't work out and you're interested in providing anything like a "ManifoldEvaluator" I'd be interested in supporting it in the project.