Module boolean 

Booleans between closed triangle meshes, decided exactly.

boolean takes two closed, outward-wound, 2-manifold meshes that do not cross themselves and answers their union, intersection or difference as one more such mesh. boolean_with_shape meshes a solid first and does the same.

Exact decisions, rounded new vertices

Every decision is the exact sign of a polynomial in the input coordinates: which side of a plane a point lies on, whether two triangles meet, the order of points along a line, whether a point lies inside a triangle, the winding number of a mesh about a point. A point the operands make, where an edge of one crosses a triangle of the other or two coplanar edges cross, is never rounded while decisions are made on it: it is kept as the input coordinates that define it, and every test on it is evaluated in interval arithmetic first and exactly when the interval cannot tell. So the topology of the answer is the topology of the exact boolean of the two polyhedra.

Only at the end are the new vertices rounded to f64, each to the coordinates nearest its exact position within a few units in the last place. MeshBoolean::rounding bounds how far any moved. The input vertices kept are not moved at all. Rounding leaves the connectivity as decided; where two operands’ faces cross at a vanishing angle it can tilt a sliver piece, a few units in the last place across, past its neighbour.

How

1. Every pair of triangles whose boxes touch is met exactly: the points and segments they share.
2. Points found more than once under different names, as where an edge passes exactly through a vertex, are merged by exact comparison.
3. Each triangle that met the other operand is triangulated afresh with those points and segments as constraints, the points on its edges shared with its neighbours, so each cut operand is again closed.
4. The pieces are grouped into regions that no segment separates, and each region is classified once: on the other operand, where a piece lies in a coplanar triangle of it, and otherwise inside or outside it by an exact winding number.
5. The operation keeps the regions it selects, and the pieces are welded at the shared points.

Coplanar faces

Where the operands share a plane, the shared area is cut out of both along the other’s edges, and each piece there is on the other operand, its normal the same as the other’s or opposite. One copy of a shared face with the same normal is kept by a union or an intersection, and none by a difference; a shared face with opposite normals, where the solids touch from outside, is dropped by a union and an intersection and kept, from the first operand, by a difference. These are the boundaries of the regularised booleans.

Refused

An operand that is open, not 2-manifold, has a degenerate triangle, crosses itself, or is wound inside out, by name. Operands that do not meet, neither touching nor one holding the other. A result that would not be a 2-manifold, where the operands touch along an edge or at a point without overlapping there.

References

The implicit points and the filtered predicates over them follow M. Attene, Indirect Predicates for Geometric Constructions, and the pipeline of pairs, per-triangle cuts and region labels follows G. Cherchi, M. Livesu, R. Scateni and M. Attene, Fast and Robust Mesh Arrangements using Floating-point Arithmetic, and G. Cherchi, F. Pellacini, M. Attene and M. Livesu, Interactive and Robust Mesh Booleans. Rays through edges are resolved as in H. Edelsbrunner and E. P. Mücke, Simulation of Simplicity; points are found by the stochastic walk of O. Devillers, S. Pion and M. Teillaud, Walking in a Triangulation.

Structs

MeshBoolean

The answer of a mesh boolean.

Enums

BoolKind

A boolean operation.

Functions

boolean

The boolean op of two closed meshes.

boolean_with_shape

The boolean op of a closed mesh and a solid, the solid meshed first to chord: triangulate with Deflection::with_chord, then boolean with the mesh as the first operand.