Module overlap 

Certified volume shared by two closed meshes, and the volume of their difference (#183).

Prisms, not a boolean

No mesh is built. For a closed, consistently oriented, non-self- intersecting triangle mesh A lying above a plane z = z0, a point is inside A exactly when the faces above it, counted +1 for faces facing up and -1 for faces facing down, sum to one. So, almost everywhere,

1_A = sum over faces f of  s_f * 1{ (x, y) in f', z0 < z < h_f(x, y) }

with f' the face’s shadow on the plane, h_f the height of its plane and s_f the sign of the shadow’s orientation (vertical faces cast no shadow and drop out). Multiplying two such sums and integrating,

vol(A and B) = sum over f in A, g in B of  s_f s_g * integral over f' and g' of (min(h_f, h_g) - z0)

Each term is a convex polygon – the overlap of two triangles – split by the line where the two planes cross, and a linear function integrated over each piece.

Exact decisions, enclosed arithmetic

Every vertex of every piece before the split is an input vertex or the crossing of two input edge lines, so which side of a line or of the plane crossing it lies on is the sign of a polynomial in the input coordinates: decided by interval arithmetic and else exactly in dyadics. The numbers – crossing points, heights, areas – are then computed in outward-rounded intervals, so the sum is an interval that contains the true volume. Touching bodies and shared faces cancel exactly in the decisions; their volume comes out as a small interval around zero, and is clamped to be no less than zero.

A priori bound per term (#313)

A face that is vertical but for rounding – corners that differ by about 1e-15 across, as exported building models have – still casts a shadow, a sliver. Its plane’s slope is then near 1e30, so its height at a crossing point enclosed to 1e-15 spans ±1e15, and the sliver’s term, though its true value is tiny, comes out wider than either solid. So each term is also intersected with a bound that does not depend on how well its arithmetic is conditioned. Over its own shadow a face’s plane is the triangle itself, so its height lies between its lowest and highest corner; the term’s region lies inside both shadows; and z0 is no higher than any corner of either mesh. Hence

0 <= term <= min(area f', area g') * (min(zmax_f, zmax_g) - z0)

computed outward-rounded. A sliver’s term is then no wider than the sliver’s area times its height, and the bound only ever narrows an interval that already holds the true value, so exactly coplanar faces cancel as before.

Structs

VolumeInterval

A closed interval of volumes.

Enums

Operand

Which operand an error is about.

OverlapError

Why no volume was bracketed.

Functions

difference_volume

The volume of the first mesh outside the second, certified.

enclosed_volume

The volume enclosed by a closed mesh, certified. Either winding is accepted.

intersection_volume

The volume two closed meshes share, certified.