Subtracting interior, non axis-aligned boxes

[starseeker]

I'm not sure if this is an issue, something about how I'm processing, or simply an inevitability of floating point and the boolean algorithms themselves, but I've encountered a surprising result from a boolean operation...

The input is an interior box subtracted from an exterior box (neither is axis aligned, but they appear to be parallel relative to each other:

The "ground truth" expectation for the evaluated form of this shape (per our raytracing of the CSG boolean tree) is a frame:

The result I am getting when I convert the two shapes to meshes and subtract them is:

I've pulled .glb files for the two inputs and the evaluated subtraction, in case they are useful.
https://brlcad.org/~starseeker/s.wind6.glb
https://brlcad.org/~starseeker/s.wind6.i.glb
https://brlcad.org/~starseeker/s.wind6-s.wind6.i.glb

If this is an expected phenomena I apologize in advance for the noise, but since for our use case it registers visually as a "wrong" result (albeit manifold) I wanted to check and see if there were any good options...

[pca006132]

Are the height of the two objects exactly the same? This can be caused by floating point errors and the usual advice is to increase the height of the inner box slightly. Not sure if there are better ways.

[starseeker]

OK. I was afraid that might be the case.

[elalish]

Indeed, this is expected behavior. What you have here we call "marginal geometry"; from our wiki:

By this definition, the inputs and results are considered approximate, bounded by their respective precisions which are tracked internally. Therefore, any geometric differences within this precision are considered "in the noise" and are not considered to affect the geometric validity of the result.

If you do the Boolean first and then the rotations, you'll probably get the expected result, as then the coords are exactly identical and our symbolic perturbation does the right thing. But there's simply no way to get exactly coplanar results when things are rotated, since you've introduced rounding errors.

[OLDMAN75914091]

This is a rather important test case - can often happen in real life.

Please answer the 3 questions asked in the above image.

[starseeker]

If done naively, that's possible (although statistically less likely if the perturbations are random). That's why I say the CSG Boolean tree is likely to be important - my current thought is I'll have to investigate the models, identify coplanar or near-coplanar faces ahead of time, and selectively perturb in or out along the face normals based on the specific Boolean operation + surface configuration at play in each case. If I perturb coplanar faces rather than vertices directly (readily possible with certain of our implicit primitives) I should be able to avoid most cases where I'd be perturbing into a problem case. It would probably be hard to come up with an algorithm that could be formally proved to be reliable, but if we can come up with something that is practical for the common subset of real world cases we see in practice (sort of like Manifold's epsilon polygon triangulation) then it would still be much better than having to manually adjust everything.

[OLDMAN75914091]

I have a project where I am also contending with such things. And for me all such interventions need to be totally automatic/programmatic - not practical to manually grab and perturb scene objects.

What I have attempted is this: Before every pairwise Boolean, choose any one of two parent objects and ever-so-slightly rotate it by a very small angle about a certain 3D vector passing through its centroid. I choose this 3D vector to be something irregular - meaning not the global X or Y or Z vector directions and the like. And after the Boolean I undo this object rotation to keep the overall scene geometry undisturbed.

I do this for ALL Booleaned object-pairs, not just for objects with planar faces since the problem can arise in other cases too, I think.

As you stated, this intervention works sometimes but not always. I'm still not entirely clear on why it sometimes fails to produce a manifold resulting object. I see two possible reasons: (a) bugs in this particular Boolean implementation code, (b) inappropriate choice of perturbation values (3D-vector and rotation-angle) for that specific object pair.

And this is exactly what prompted me to search for a better solution - leading to my discovery of Manifold.

[starseeker]

Hmm. Using the above rectangle-within-rectangle case as an example, my naive expectation would be that such a rotation (depending on which vector you chose) would produce something like what you actually see in the image above? (Assuming it didn't just fail outright to produce a manifold output...) Wouldn't you be doing basically what the floating point fuzz and/or rounding errors did inadvertently with my example?

[elalish]

Yes, those perturbations sometimes fix an unreliable computational geometry algorithm, but they can't fix everything. If your coplanar cases tend to be axis-aligned, Manifold's symbolic perturbation is designed carefully to avoid generating thin webs and other undesirable geometry. If you can avoid introducing rounding errors by things like inexact rotations, you'll get the best results. Our own Rotate() function is designed to be exact for any multiple of 90 degrees (part of why we use degrees instead of radians).

[OLDMAN75914091]

That's correct, starseeker. And yes, it did fail outright to produce a manifold output since, as I now surmise, the faceted Boolean package I am using there is imperfect.

Also, this expectation of co-planar cases being axis-aligned is really not reasonable for real-life cases.

Conclusion: I should give Manifold a try :)