Exact Boolean with Incorrect Result - multiprecision/float round trips not exact #82903

New Issue

Philip Holzmann · 2020-11-21T15:59:09+01:00

Philip Holzmann commented

2020-11-21 15:59:09 +01:00

System Information
Operating system: Windows 64 bit
Graphics card: Nvidia GTX 750 Ti

Blender Version
Broken: 2.91.0 Beta dca36a8ec9

Short description of error
Another case, where the exact boolean does not work as expected. (Sorry @howardt, I had to break it. I have to admit, that I have not run into this problem in a real scene.)
Again, this manifests after applying the same difference operation several times.

Exact steps for others to reproduce the error
boolean_rotated_box3.blend
Look at the scene.
The first run of the modifier works as expected, the second creates overlapping faces, the third removes most of the mesh.
This "bug" is very erratic, and if the transform of the objects is slightly changed, it does not occur.

This is what I see:

The expected behavior is that the second and third modifier do nothing.

**System Information** Operating system: Windows 64 bit Graphics card: Nvidia GTX 750 Ti **Blender Version** Broken: 2.91.0 Beta dca36a8ec922 **Short description of error** Another case, where the exact boolean does not work as expected. (Sorry @howardt, I had to break it. I have to admit, that I have not run into this problem in a real scene.) Again, this manifests after applying the same difference operation several times. **Exact steps for others to reproduce the error** [boolean_rotated_box3.blend](https://archive.blender.org/developer/F9348291/boolean_rotated_box3.blend) Look at the scene. The first run of the modifier works as expected, the second creates overlapping faces, the third removes most of the mesh. This "bug" is very erratic, and if the transform of the objects is slightly changed, it does not occur. This is what I see: ![boolean_rotated_box3.png](https://archive.blender.org/developer/F9348287/boolean_rotated_box3.png) The expected behavior is that the second and third modifier do nothing.

Philip Holzmann commented

2020-11-21 15:59:09 +01:00

Added subscribers: @howardt, @Foaly

Germano Cavalcante commented

2020-11-23 21:11:00 +01:00

Added subscriber: @mano-wii

Germano Cavalcante commented

2020-11-23 21:11:00 +01:00

I can confirm but I'm not sure if this is a limitation with float precision.
So I will wait for a second opinion.

I can confirm but I'm not sure if this is a limitation with float precision. So I will wait for a second opinion.

Howard Trickey self-assigned this 2020-11-24 01:53:39 +01:00

Howard Trickey commented

2020-11-24 01:53:39 +01:00

Changed status from 'Needs Triage' to: 'Confirmed'

Howard Trickey commented

2020-11-24 01:53:39 +01:00

I suspect the problem is the round trips back and forth between multiprecision and floats are not idempotent, especially when combined with the application of a transform matrix and its inverse. I think it might be true that if I did the successive steps all in multiprecision, without the intermediate trips to float and back, that it would work exactly as expected: the subsequent operations would be no-ops.

I further suspect that the the trip back to float causes a well-formed (that is, manifold and volume enclosing) mesh to become non-well-formed, taking it into the territory that boolean is not guaranteed to work in. Hence the final result being seeming nonsensical.

The paper that I got the algorithm from warned that this could happen, and has an expensive, not-guaranteed-to-work workaround where they snap to float precision while still in multiprecision, and then check for self-intersections, and if they are found, redoes the whole thing again to resolve those self intersections. I skipped doing that step because it seemed pretty expensive even to detect the self intersections. Maybe I will add it in the future, perhaps as optional. I'd like to see if this actually occurs in real production uses rather than in contrived tests, before taking that step.

At this time I'm not going to verify the guesses I've made above because it would likely take days of my time (I already spent days on the last one, and gave up because it just got too hard to understand the topology of the intermediate results). Maybe some day I'll develop a new way of debugging that will let me tackle this. Perhaps a way to "expand" really tiny or narrow triangles while keeping the topology the same, so that I can examine them visually in Blender. Until then, I don't know what state to leave this in. I guess it is a low priority bug.

I suspect the problem is the round trips back and forth between multiprecision and floats are not idempotent, especially when combined with the application of a transform matrix and its inverse. I think it might be true that if I did the successive steps all in multiprecision, without the intermediate trips to float and back, that it would work exactly as expected: the subsequent operations would be no-ops. I further suspect that the the trip back to float causes a well-formed (that is, manifold and volume enclosing) mesh to become non-well-formed, taking it into the territory that boolean is not guaranteed to work in. Hence the final result being seeming nonsensical. The paper that I got the algorithm from warned that this could happen, and has an expensive, not-guaranteed-to-work workaround where they snap to float precision while still in multiprecision, and then check for self-intersections, and if they are found, redoes the whole thing again to resolve those self intersections. I skipped doing that step because it seemed pretty expensive even to detect the self intersections. Maybe I will add it in the future, perhaps as optional. I'd like to see if this actually occurs in real production uses rather than in contrived tests, before taking that step. At this time I'm not going to verify the guesses I've made above because it would likely take days of my time (I already spent days on the last one, and gave up because it just got too hard to understand the topology of the intermediate results). Maybe some day I'll develop a new way of debugging that will let me tackle this. Perhaps a way to "expand" really tiny or narrow triangles while keeping the topology the same, so that I can examine them visually in Blender. Until then, I don't know what state to leave this in. I guess it is a low priority bug.

Howard Trickey changed title from ~~Exact Boolean with Incorrect Result~~ to Exact Boolean with Incorrect Result - multiprecision/float round trips not exact

2021-02-07 14:44:13 +01:00

Philipp Oeser removed the

Download

What's New

Blender Studio

Manual

Developers Blog

Documentation

Benchmark

Blender Conference

Development Fund

One-time Donations

Exact Boolean with Incorrect Result - multiprecision/float round trips not exact #82903