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.

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.