Exact Boolean V2 #114476

New Issue

Howard Trickey · 2023-11-04T02:47:34+01:00

Howard Trickey commented

2023-11-04 02:47:34 +01:00

Exact Boolean V2

The current Exact Boolean works pretty well, but except on small meshes, it is too slow. This is especially apparent when used as a geometry node, where frequent reevaluations are often called for as the user edits the node tree. A top user request is for a much faster Mesh Boolean geometry node. Attempts to improve the speed of the current exact boolean through parallelization and other means seemed to have reached diminishing returns. There are three big obstacles to further improvements:

The underlying exact arithmetic uses GMP for multiprecision rational numbers, and the numerators and denominators get pretty big (needing many memory allocation calls).
For very large meshes, each face gets converted into and out of multiprecision, regardless of whether they are actually involved in intersections.
The logic needed to figure out inside vs outside via a partitioning by cells is quite complicated and somewhat slow.

A recent paper, EMBER: Exact Mesh Booleans via Efficient & Robust Local Arrangements, by Trettner, Nehring-Wirxel, and Kobbelt, uses a new method that their measurements show is even faster than the floating-point implementations compared against. Their approach has several aspects that get around the above obstacles:

Instead of multiprecision rational numbers, exact arithmetic is done by using fixed-width multiprecision integers (256 bits work for Blender), with input float coordinates scaled to fit in smallish integers (26 bits work for Blender).
The meshes are successively divided along approximately bisecting planes until there are only about 20 faces in a leaf, at which point only the intersections of the face parts in a leaf need to be tested for intersection. The subdivision allows for big savings when large portions of a huge mesh don't overlap with the other mesh(es) at all; in many cases, whole swaths of computation can be avoided.
The mesh subdividing also helps improve the speed of the inside/outside computation: as the subdivision proceeds, the algorithm makes a reference point with known insideness/outsideness in the new subproblems. Then, at the leaves, one only needs to see what faces are intersected on a line to the reference point to calculate whether that face survives in the answer or not.

I am currently implementing the algorithm of the EMBER paper in Blender, in branch exactboolv2 in howardt/blender . The fixed-width multiprecision integers are currently implemented using a library that Jacques wrote. The code works on native Mesh structures, not BMesh.

Current status (Nov 3, 2023):

Modified the Mesh Boolean geometry node to have a "Solver" option, with three options: Exact, Float, and Exact Old. This is for testing/comparison, and the final interface will likely not have these same options.
The mesh_exact_bool.cc file is for the new Ember boolean implementation.
Input meshes' vertex coordinates are scaled and offset to fit into 26 bits.
The input meshes are converted into a polygon soup, with each argument mesh going into its own subsoup.
The initial polygon soup is successively dividing by bisecting planes, until a certain leaf size is reached. Where polygons are cut by a dividing plane, they are cut in two and converted to an internal form which has a support plane and other planes to define the edges of the polygon by intersection with each other and the support plane. As subdividing proceeds, new reference points are created, and a 'trace' procedure finds the insideness/outsideness of for each subsoup by finding which polygons are intercepted by the trace.
The "leaf problems" are solved using a binary space partitioning algorithm, and a triangle-triangle intersection routine developed for this application.
The faces found in the previous step are tested for insideness/outsidness by tracing to their reference point, and then a function determined by the boolean mode (UNION, INTERSECTION, DIFFERENCE) decides whether that face is in the output or not
A placeholder output routine just outputs the individual faces (not connected together yet).

So the initial test of a boolean operation works, except that the output mesh is not connected and doesn't have proper attribute calculation, and doesn't have extraneous edges removed. Also, the code doesn't yet handle coplanar faces (but it will later.) Still lots to do.

**Exact Boolean V2** The current Exact Boolean works pretty well, but except on small meshes, it is too slow. This is especially apparent when used as a geometry node, where frequent reevaluations are often called for as the user edits the node tree. A top user request is for a much faster Mesh Boolean geometry node. Attempts to improve the speed of the current exact boolean through parallelization and other means seemed to have reached diminishing returns. There are three big obstacles to further improvements: 1. The underlying exact arithmetic uses GMP for multiprecision rational numbers, and the numerators and denominators get pretty big (needing many memory allocation calls). 2. For very large meshes, each face gets converted into and out of multiprecision, regardless of whether they are actually involved in intersections. 3. The logic needed to figure out inside vs outside via a partitioning by cells is quite complicated and somewhat slow. A recent paper, [EMBER: Exact Mesh Booleans via Efficient & Robust Local Arrangements](https://dl.acm.org/doi/10.1145/3528223.3530181), by Trettner, Nehring-Wirxel, and Kobbelt, uses a new method that their measurements show is even faster than the floating-point implementations compared against. Their approach has several aspects that get around the above obstacles: 1. Instead of multiprecision rational numbers, exact arithmetic is done by using fixed-width multiprecision integers (256 bits work for Blender), with input float coordinates scaled to fit in smallish integers (26 bits work for Blender). 2. The meshes are successively divided along approximately bisecting planes until there are only about 20 faces in a leaf, at which point only the intersections of the face parts in a leaf need to be tested for intersection. The subdivision allows for big savings when large portions of a huge mesh don't overlap with the other mesh(es) at all; in many cases, whole swaths of computation can be avoided. 3. The mesh subdividing also helps improve the speed of the inside/outside computation: as the subdivision proceeds, the algorithm makes a reference point with known insideness/outsideness in the new subproblems. Then, at the leaves, one only needs to see what faces are intersected on a line to the reference point to calculate whether that face survives in the answer or not. I am currently implementing the algorithm of the EMBER paper in Blender, in branch [exactboolv2](https://projects.blender.org/howardt/blender/src/branch/exactboolv2) in [howardt/blender](https://projects.blender.org/howardt/blender) . The fixed-width multiprecision integers are currently implemented using a library that Jacques wrote. The code works on native Mesh structures, not BMesh. Current status (Nov 3, 2023): - Modified the Mesh Boolean geometry node to have a "Solver" option, with three options: Exact, Float, and Exact Old. This is for testing/comparison, and the final interface will likely not have these same options. - The `mesh_exact_bool.cc` file is for the new Ember boolean implementation. - Input meshes' vertex coordinates are scaled and offset to fit into 26 bits. - The input meshes are converted into a polygon soup, with each argument mesh going into its own subsoup. - The initial polygon soup is successively dividing by bisecting planes, until a certain leaf size is reached. Where polygons are cut by a dividing plane, they are cut in two and converted to an internal form which has a support plane and other planes to define the edges of the polygon by intersection with each other and the support plane. As subdividing proceeds, new reference points are created, and a 'trace' procedure finds the insideness/outsideness of for each subsoup by finding which polygons are intercepted by the trace. - The "leaf problems" are solved using a binary space partitioning algorithm, and a triangle-triangle intersection routine developed for this application. - The faces found in the previous step are tested for insideness/outsidness by tracing to their reference point, and then a function determined by the boolean mode (UNION, INTERSECTION, DIFFERENCE) decides whether that face is in the output or not - A placeholder output routine just outputs the individual faces (not connected together yet). So the initial test of a boolean operation works, except that the output mesh is not connected and doesn't have proper attribute calculation, and doesn't have extraneous edges removed. Also, the code doesn't yet handle coplanar faces (but it will later.) Still lots to do.

👍 19 ❤️ 11 🚀 5

Howard Trickey added the

Type

Design

label 2023-11-04 02:47:34 +01:00

Howard Trickey referenced this issue

2023-11-04 02:50:18 +01:00

Bevel V2 #98674

Howard Trickey added this to the Modeling project 2023-11-04 03:10:04 +01:00

Howard Trickey self-assigned this 2023-11-04 03:10:12 +01:00

Howard Trickey added the