Weird geometry after second coplanar subtraction of cubes

[ToyboxZach]

Absolutely love this package and think its like 95% of the way there, you have done an amazing job with this but I am having one problem with coplanar faces:

Describe the bug

After a second subtraction with Coplanar objects such as two cube you start to get very weird behavior. This is improved after the triangle splitter PR, but not solved. From our experience this only happens when you have coplanar faces, when we shift these objects even slightly all the problems completely go away.

To Reproduce
Here is a fiddle:

https://jsfiddle.net/58yehc2z/28/

const baseGeometry = new BoxGeometry(1,1,1)
const firstSubtract =  new BoxGeometry(1,1,1)
const secondSubtract =  new BoxGeometry(1,1,1)
firstSubtract.translate(0.5,0.5,0);
secondSubtract.translate(0,0.5,0);

const csg = new Evaluator();
const base = new Brush(baseGeometry);
const first = new Brush(firstSubtract);
const second = new Brush(secondSubtract);

let result = csg.evaluate(base, first, SUBTRACTION);

let final_result = csg.evaluate(result, second, SUBTRACTION);

Live example

https://jsfiddle.net/58yehc2z/28/

Expected behavior
I would expect this to continue to be manifold, especially for a case such as simple cubes subtracting from each other

Screenshots
I have a much more complicated setup but the same operation ends up with something like this which is a bit easier to see than the fiddle I set up:

*edit: This picture was actually caused by an unrelated problem

This is after we pulled in the triangle splitter PR which is an amazing improvement, but doesn't solve this case.

[ToyboxZach]

With the new triangle splitter this ends up being related to a point being directly on the line

#194 (comment)_

And the picture I shared is caused by
gkjohnson/three-mesh-bvh#680

[gkjohnson]

Hello! Thanks for reporting the issue. As you've seen there are some known issues with the existing triangle splitting logic and it's something I would still like to try a new approach for. The approach in #194 was an attempt at trying a new approach but unfortunately it had issues, as well.

When I have time I would like to dive in again and try a new approach. In short, I think it would be best to split triangles into a series of n-sided polygons based on the intersection segments with other triangles. Then these polygons can be triangulated using a constrained delaunay triangulation algorithm. We'd still need to figure out how to handle parallel face intersections more robustly but this would be a good start.

If this is something you're interested in helping with that would be great. A good CDL implementation would be a great first step and is a fairly separably task, I think.

[ToyboxZach]

Hmm I am running out of time for how much more I can work on this so I don't think I can try a new triangulation algorithm

I have gotten the earcut to produce generally good results now with a few modifications, I definitely hit a limit with it though and if we intersect with too many faces it will just start to fail.

If you want to try to make earcut work a little better this is my most up to date branch and you might be able to pull the important stuff from there.

Essentially I realized that organizing the faces is an exponential problem, so if I get a case that is too hard, I just split the edge into two and do the split on the half of the edge. This does break down after my like 8th or 9th subtraction because there are just too many faces that even my optimization doesn't work anymore, likely because i'm creating essentially 0 length edges, but its gotten to a place I am happy with it.

https://github.com/ToyboxZach/three-bvh-csg/tree/ImprovedCSG

I did make a few choices that are helpful for our case, but probably not what you want in this package, so I wouldn't directly pull it in.

[gkjohnson]

Definitely understand regarding time. At some point I'll plan to revisit this.

I have gotten the earcut to produce generally good results now with a few modifications

To clarify it doesn't look like your branch is using the earcut algorithm to fill holes. I'm referring to the algorithm implemented here which was then ported to three. But I've found that it breaks down in cases where vertices are to close to eachother.

For future references here's a direct diff of your branch with this one:

improved-tri-split...ToyboxZach:three-bvh-csg:ImprovedCSG

[ToyboxZach]

Ah ok, I misunderstood what earcut was. Yeah my focus was just to use your triangle splitter, find some case it broke and figure out why. My branch would fix this issue, but still eventually fails with more complex faces likely due to floating point errors and just having too many edges to reason about.