Some experiments with bvh-csg-0.0.10

I have been using the BVH-CSG-0.0.10 library in my code. Here are the results of some experiments. Each experiment starts with a model containing 2 meshes.
Each mesh is a closed and properly oriented single body. The two meshes are inter-penetrating - sometimes significantly, sometimes just-touch.
Calling the two meshes A1 and B1, I am doing the following with the SUBTRACTION Boolean operations.

A2 = A1 - B1
B2 = B1 - A2

The BEFORE state refers to A1 and B1.
The AFTER state refers to A2 and B2.

That’s the background. My observations are in the displayed sheet. My questions are the following:

(1) Why does the result of the subtraction (A2, B2) have degenerate triangles. Is that OK?
(2) Why does the volume of the result of a subtraction (A2, B2) exceed that of the parent sometimes?
(3) Why does the bounding box of the A2,B2 model sometimes exceed that of the A1,B1 model?
(4) In one experiment, the number of triangles in the resulting mesh increased quite drastically (order of magnitude). Is that OK?

If anyone is interesting in investigating this and needs more information, models, etc, I can provide that if you tell me how.

(I can’t guarantee that my very messy code is bug-free, but I have looked it over quite carefully :):slight_smile:

Thanks much

OLDMAN

2 Likes

The nature of floating point arithmetic makes these kinds of problems extremely difficult. It’s not so surprising that there are cases that have some odd or unexpected results. With testing and example cases some of the scenarios can be addressed but it must be recognized that achieving perfect results is not going to be attainable. Something like using integers for these kinds of operations (ie scaling to large values and dropping the decimal) can help make the math more stable but there’d be a performance hit and a rewrite and complexity would increase.

To your questions:

(1) Why does the result of the subtraction (A2, B2) have degenerate triangles. Is that OK?

Depending on how degenerate they are (literally a triangle with exactly the same 3 vertices?) then they can of course be removed. They should not cause issues, though.

(2) Why does the volume of the result of a subtraction (A2, B2) exceed that of the parent sometimes?

Again - floating point precision can make these kinds of things difficult. The code for computing mesh volume is in this file and adapted from this stackoverflow answer. Feel free to recommend or contribute improvements if you see them.

(3) Why does the bounding box of the A2,B2 model sometimes exceed that of the A1,B1 model?

There’s no guarantees about combing bounding box sizes when merging or computing sibling objects. Consider the bounding box of two merged small but far part spheres. It also looks like three.js’ compute bounding box function does not account for “drawRange” which means some vertices not being rendered could be being included in the BB generation.

(4) In one experiment, the number of triangles in the resulting mesh increased quite drastically (order of magnitude). Is that OK?

Without seeing a reproduction of the case or how the numbers in your chart are computed it’s hard to say whether or not the increase is reasonable.


If you can provide minimal repro cases of some of these issues - ideally with simple generated geometry if possible - then I’m happy to add them to the list for myself or someone else to look at when availability affords and maybe some improvements can be made the project.

(I can’t guarantee that my very messy code is bug-free, but I have looked it over quite carefully :):slight_smile:

I will ask that code be cleaned up and simplified so I can more easily follow what’s going on, though, to save time and effort.

well it seems like you drive a round bolt through a simple flat shape. the bolt side surface has to have 100s of tris to be round; the simple flat shape could have a dozen but, in order to connect to round shape smoothly, its tri-count has to go up to that one of a bolt.

2 Likes

The nature of floating point arithmetic makes these kinds of problems extremely difficult. It’s not so surprising that there are cases that have some odd or unexpected results. With testing and example cases some of the scenarios can be addressed but it must be recognized that achieving perfect results is not going to be attainable. Something like using integers for these kinds of operations (ie scaling to large values and dropping the decimal) can help make the math more stable but there’d be a performance hit and a rewrite and complexity would increase.

I’m familiar with the integer conversion idea. I understand the rewrite and effort, but why the performance hit? Integer math is faster than floating math.

To your questions:

> (1) Why does the result of the subtraction (A2, B2) have degenerate triangles. Is that OK?

Depending on how degenerate they are (literally a triangle with exactly the same 3 vertices?) then they can of course be removed. They should not cause issues, though.

These triangle have at least one side whose length is less than 0.00000001 units. I have defined that as my “zero”, based on the “typical” dimensions of the models I encounter. Based on this condition, the triangles have degenerated to either a line or a point. BTW, what value is your code using as “zero”?

> (2) Why does the volume of the result of a subtraction (A2, B2) exceed that of the parent sometimes?

Again - floating point precision can make these kinds of things difficult. The code for computing mesh volume is in this file and adapted from this stackoverflow answer. Feel free to recommend or contribute improvements if you see them.

OK, I will take a look.

> (3) Why does the bounding box of the A2,B2 model sometimes exceed that of the A1,B1 model?

There’s no guarantees about combing bounding box sizes when merging or computing sibling objects. Consider the bounding box of two merged small but far part spheres. It also looks like three.js’ compute bounding box function does not account for “drawRange” which means some vertices not being rendered could be being included in the BB generation.

I checked the “drawRange” and found that was not an issue. I understand your small sphere merging example, but that seems quite different from my case. And my bounding box changes are quite drastic, when they happen - and usually not on all three dimensions. Usually just in one dimension. Perhaps that is a clue?

> (4) In one experiment, the number of triangles in the resulting mesh increased quite drastically (order of magnitude). Is that OK?

Without seeing a reproduction of the case or how the numbers in your chart are computed it’s hard to say whether or not the increase is reasonable.


If you can provide minimal repro cases of some of these issues - ideally with simple generated geometry if possible - then I’m happy to add them to the list for myself or someone else to look at when availability affords and maybe some improvements can be made the project.

> (I can’t guarantee that my very messy code is bug-free, but I have looked it over quite carefully :):slight_smile:

I will ask that code be cleaned up and simplified so I can more easily follow what’s going on, though, to save time and effort.

I’ve been wondering how to share my data/examples with others. My code is one large monolithic piece that does many other things besides Booleans…very prototype in nature. Since the operations to be reproduced are relatively simple to code (just a Boolean subtract), would it be sufficient to share the models in these experiments? I can share the two objects/meshes for each experiment (located in their final locations in space - no repositioning needed) via “.3mf” model files. THREE has a reader for this file format. Do let me know.

And finally, thank you for your detailed reply

Best,

OLDMAN

1 Like

I’m familiar with the integer conversion idea. I understand the rewrite and effort, but why the performance hit? Integer math is faster than floating math.

In order to keep numbers stored as integers in javascript they must all be consistently rounded or truncated after operations. It’s not even clear to me that all the benefits of using ints would be realized because js assumes doubles in numeric operations.

Based on this condition, the triangles have degenerated to either a line or a point. BTW, what value is your code using as “zero”?

It depends on the condition and the context of the calculation. Most of them are fairly gut-based values and smaller than 1e-8. The values are typically suffixed with _EPSILON in the project. There could be other checks added later in the clipping steps that catch these but they will show up in cases such as where clipping occurs at a tight corner for a triangle.

my bounding box changes are quite drastic, when they happen - and usually not on all three dimensions. Usually just in one dimension. Perhaps that is a clue?

You can use the three.js’ built in BoxHelper to get a better understanding of the constructed bounding box. But I’m afraid I can’t spend my time guessing at what might be causing the problem. You’ll have to provide a simple repro to understand it.

I’ve been wondering how to share my data/examples with others. My code is one large monolithic piece that does many other things besides Booleans…very prototype in nature.

would it be sufficient to share the models in these experiments? I can share the two objects/meshes for each experiment (located in their final locations in space - no repositioning needed) via “.3mf” model files.

For the most part my open source projects are ones that I spend my spare time developing for free so reproducing issues and making minimal repro cases to understand someones problem is not something I have the bandwidth to do. It would be best to provide reproductions of these cases using simple procedural models (boxes, low poly spheres, etc). Otherwise an example loading the files you have may provide insight. There are plenty of live example hosting options online including jsfiddle and codesandbox for sharing these types of small examples.

2 Likes

I’ve maintained a 3d CSG library, and I can attest to the fact that it’s basically impossible to handle every case, when using floating point.
CSG only works perfectly with perfectly formed inputs in the sweet spot of numerical precision of the datatype you are using.

There is a paper about using integer precision combined with BSPs to do “exact” csg, but there is a lot of overhead involved in the solution. I think this may be what @gkjohnson is referring to.

Yes, manthrax, that’s true. The commercial CAD software firms (PTC, Dassault Systemes, etc.) rely on precise, mathematical (NURBS) representations for their geometry, but they too have to deal with floating-point imperfections. Perhaps they have worked out and addressed a large number of special cases.

OLDMAN

1 Like

@oldman I just want to throw it out there… If you only need the CSG to create a visual representation… there are tricks you do with the stencil buffer to render some kinds of CSG in realtime…
There’s 2 algos that i’ve read about/messed with… scs and featherstone…

I found this on google: scs-csg-subtraction-webgl - CodeSandbox

image

1 Like

I tried that and one of my 3 brain cells died while coding it. It’s not for faint-hearted.

3 Likes

Yeah it’s a mind cruncher. Stencil buffer stuff is still witchcraft to me.

Stencil is an interesting idea. I wonder if anyone can comment on how the illustrators might have gone about creating these two renderings. (1) a faucet with cutaways, (b) an oil-filter also with cutaways.

faucet
oil-filter

OLDMAN

The first once could be done with stencil buffer tricks…

The second one looks more hand illustrated or rendered… since there is translucency and interesting highlights. Maybe done in solidworks… or hand illustrated/rotoscoped.

These?

Hmm not sure if that would work, since the planes are infinite? And in the screenshot, the planes meet at the junction… whereas in the clipping plane scenario they bisect the entire worldspace.

The clipping planes are implemented in the fragment shader iirc.

@manthrax

Hmm not sure if that would work, since the planes are infinite? And in the screenshot, the planes meet at the junction… whereas in the clipping plane scenario they bisect the entire worldspace.

If I’m understanding you right - there is an option to change the clipping plane behavior to perform a “union” operation rather than subtraction which would let you clip a box out of an existing object. See Material.clipIntersection.

there are tricks you do with the stencil buffer to render some kinds of CSG in realtime…

There’s 2 algos that i’ve read about/messed with… scs and featherstone…

I’ve thought about these approaches, as well, but I think they get insanely complicated (and I imagine performance limited) once you start performing operations with anything other than a single convex object :sweat_smile: This is the paper I’ve looked at a little bit previously. Even the link you provided contains visual inconsistencies in that simple case depending on camera angle (see that the holes change where the spheres intersect depending on viewpoint):

@oldman

Stencil is an interesting idea. I wonder if anyone can comment on how the illustrators might have gone about creating these two renderings. (1) a faucet with cutaways, (b) an oil-filter also with cutaways.

Aside from the transparent fade effect (which I agree is likely illustrated or a different graphical effect) those types of cutaways should be able to be achieved with boolean operations like the ones three-bvh-csg provides as long as the objects are water-tight / two manifold. It looks like different subtraction volumes are applied to different parts of the model to give a better look at different layers.

Yeah I guess like in this example

Making end caps for this is something that makes the brain hurt even thinking about :sob::rofl:

Which is exactly why I am investing time in these simple experiments (with limited success ). Consider the oil-filter cut-a-way. There are multiple layers to this illustration. One would need to be very precise/planned about “building” a cutter object and choosing the cutee object in each of the layers. Even if that can somehow be done, I do need to ensure that the ensuing Booleans are rock solid :):).

Will work on it, slowly and steadily, as suggested by GKJ.

Can anyone comment/speculate on how this illustration might have been achieved by the original illustrator? Very tediously?

OLDMAN

In SolidWorks vizualizations with custom sectioning shapes and render options like this are trivial

1 Like

Realtime robust CSG (full geometry, not image-based) is possible:

Used in this app: https://noumenal.app/

It’s not easy, though. Some of the tricks I used:

Fast Robust Predicates for Computational Geometry (my algorithm is heavily modified, but the same idea.)
[math/9410209] Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms

2 Likes

This looks awesome!! Is it done in js? Would love to check out the library! Are you gonna open source it?