Example that reproduces problems with missing triangles (for subtraction), and a possible fix

[coolvision]

I made a demo that allows to interactively "cut off" pieces of a mesh: https://github.com/coolvision/three-bvh-csg/blob/iterative-dev/examples/iterative.js

demo video:

It does subtraction, and the mesh is iteratively updated to the CSG result each time, so that subtractions accumulate. In this case, lots of coplanar triangles are created, and when testing with current three-bvh-csg version, lots of triangles are missing:

I've added a fix for adding coplanar triangles, and in this case it works fine: https://github.com/gkjohnson/three-bvh-csg/commit/718868914c96f11b28bf5b194eca0c9953d0af0f#diff-172f17787715fc8aa7225b6a6716874d91c005133ed9670a86c84ab2081ca063

When I use a cone for the brush instead of a box. there are still missing and non-clipped triangles, albeit less than without the fix, so there is still work to do:

Would some of this be useful? I can add a PR for the fix, and for the demo/example as well, I think it's a useful testcase for improving bunch of corner cases.

[coolvision]

found one issue with cones -- in ConeGeometry there are some degenerate triangles (because of the way it's build out of CylinderGeometry). A check for input triangles solves it: https://github.com/coolvision/three-bvh-csg/commit/8f7d1d300454f9e61ffb19f953aca17182416b16#diff-fafbaae52166e47a0cb45ec83abbb8b4008ee65b84fc346b7cc1aafa2d022f10R199-R202

[gkjohnson]

Hey @coolvision! Thanks for taking a deeper look at this this stuff. As you can tell - the implementation for triangle clipping and CSG isn't perfect (yet?) but I'd like to put some more time into it at some point.

To your change about handling COPLANAR triangles that change looks good given the current implementation. It's likely we need the same kind of change in the DIFFERENCE operation, as well. Feel free to make a PR!

Regarding the degenerate triangles in the cone geometry - can you elaborate a bit more on why cones get a degenerate triangle and where it shows up? Is this an issue with three.js' cone generation? Handling these degenerate triangle cases is a little odd because the apparent "degeneracy" of a triangle changes depending on what frame you measure in. I'll have to think about how to handle this a bit better in the future.

Also if CSG is something you're interested in the project could always use more help! Happy to talk about some of the next steps I'd take on the project if you want to contribute more.

[coolvision]

Regarding the degenerate triangles in the cone geometry - can you elaborate a bit more on why cones get a degenerate triangle and where it shows up? Is this an issue with three.js' cone generation?

Yes, it's three.js specific -- cylinder "torso" is made of rectangles, each one has 2 triangles. when the same code is used for cone geometry, rectangles are collapsed into triangles, but still use 2 triangles, with one of the triangles collapsed (2 of the vertices are equal). This is how intersection of a cone with a box looks, those line segment sticking out are collapsed triangles, they are not handled correctly by performWholeTriangleOperations.

It is a three.js issues, I might try to push a fix there, but in any case there might be degenerate triangles in other kinds of inputs. I think if 2 vertices are exactly the same, it would not depend on the frame of reference that the triangle is useless for CSG?

Also if CSG is something you're interested in the project could always use more help! Happy to talk about some of the next steps I'd take on the project if you want to contribute more.

I'm just starting to familiarize with the code, so will stick to debugging for now, but if I'll get more comfortable, then will ask for directions, thanks!

I'm mainly interested in this use case of accumulated subtractions, and am trying to understand the source of problems with it. For example, applying a cone subtraction twice in the same spot (second time to the result of first subtraction), causes a missing triangle:

[gkjohnson]

Yes, it's three.js specific -- cylinder "torso" is made of rectangles, each one has 2 triangles.

I see now - yes this will result in problematic triangles with ambiguous half edge connectivity. I'm tempted to suggest that this is an invalid mesh that needs to be fixed in order to be used with the project. And perhaps there can be a utility to detect and/or fix these issues.

One of the strategies for keeping performance up, for example, is retaining a 1:1 half-edge connectivity graph of the model which lets us quickly discover fully connected sets of faces. If a degenerate triangle sits on another triangle edge this will potentially disrupt the fidelity of the half edge structure resulting in an invalid / less performant structure. To that end I'd like to eventually guarantee that the result of a CSG operation is a fully connected half-edge structure, as well (see #27, #51, #77). It's possible we'll still need handling of these types of corner cases but it doesn't seem as simple as just ignoring them during processing. At some point it's possible the project should throw an error if a non-connected mesh is encountered.

This is a good case to be aware of that I didn't know about, though.

I'm mainly interested in this use case of accumulated subtractions, and am trying to understand the source of problems with it. For example, applying a cone subtraction twice in the same spot (second time to the result of first subtraction), causes a missing triangle:

Coplanar triangles are a complicated case, at the moment, that's susceptible to floating point error when checking for the coplanar case. Ultimately these cases need more robust (and probably different) handling to be resilient to these kinds of problems.

[gkjohnson]

@coolvision Are you able to test this on the latest version of then project and latest three-mesh-bvh?