Module exact_distance

Expand description

Certified distance between the boundaries of two exact B-reps (#125, C18).

§What is certified

boundary_distance returns an interval [lower, upper] that contains the true minimum distance between the two boundaries, and two computed points, one on each boundary within its evaluation rounding, whose boundary points upper covers (#439). Both ends are guarantees, not estimates:

upper is at least the distance between two points that lie on the boundaries, which the two computed witnesses stand for: points on edges, or surface points at parameters the face’s domain is certified to contain (the crate-private Domain classifier). It is their computed distance plus their rounding (see “Rounding”).
lower comes from bounding spheres that enclose every point of a patch of a face’s parameter domain, from Lipschitz bounds on the exact surface, with a margin for rounding. Patches are dropped only when certified to lie outside the face.

A rule that compares a distance with a limit asks boundary_clearance, which refines only until the interval clears the limit and otherwise says Clearance::Indeterminate – a value within rounding of the limit is never reported as a pass or a fail.

§Method

Branch and bound over pairs of elements, one from each B-rep: face patches (a rectangle of a face’s parameters) and edge spans. The pair with the smallest lower bound is refined by splitting its larger element. Refinement stops when the smallest remaining lower bound is within the requested accuracy of the best upper bound, or the step budget runs out; either way the interval returned is sound.

Bounds are second order where the family allows: the range of d . x over a patch is exact for planes, cylinders, elliptical cylinders, cones, spheres and tori and for line, circle and ellipse edges, and d is taken along the line between centres and along each patch’s normal. A face patch whose normals cannot point at the other element is dropped from that pair (critical_possible): the closest pair of two separated boundaries is critical on each face it lies inside or lies on an edge, and edges are elements of their own.

§Convergence

An isolated nearest pair (pole to pole, apex to sphere, a wall to a block face) closes to 1e-9 in well under a second. Where the nearest points form a whole line – two parallel columns – every slice along that line is a near-minimal pair and refinement slows; ask such cases for a looser accuracy, or use boundary_clearance, which stops as soon as the limit is cleared. The step budget is fixed; when it runs out the interval returned is still sound, only wider.

Where a lower bound does not depend on a patch’s size – along a planar patch’s own normal, against a parallel planar patch or a line edge – the minimum is reached on a whole region and the bound is right from the start; what never closes is the upper bound, since patch centres line up only by chance. Such ties close on foot witnesses (witness): the foot, on a planar face, of the other element’s witness, and the closest points of two line spans, each certified as any witness is (#318).

§Touching and crossing boundaries

Where the boundaries meet, the distance is zero, but witnesses at patch centres and edge midpoints land on the contact only by chance, so the refinement alone would close on it only when the patches round it were within the accuracy – often not within the step budget. A pair popped with a lower bound of zero is therefore first asked for a point of each element that the two share (#273): the closest points of two line edges, or a point of a line edge and the point of a planar face at the same place, each evaluated on its own boundary as any witness is, the face’s certified by the face’s domain. Two such points no farther apart than the rounding margin (128 ulps of the points’ magnitudes: about 6e-14 at unit scale) end the search with [0, d'], d' their distance plus their rounding (#439), they being the witnesses: no lower bound can rise above zero there, so this is the interval the search would only converge to. Two boxes sharing a face, or crossing, stop within a few steps. A gap wider than that margin is never taken for a touch, and boundaries that are apart measure exactly as before. Curved faces and circle or ellipse edges show no touch this way and are refined as before.

§Rounding (#318)

Every margin is derived from the magnitudes the computed numbers are summed from, in units of eps (f64::EPSILON, twice the unit roundoff), not from 1e-12 of the points’ magnitudes, which left an interval about 1e-5 wide at georeferenced coordinates (450000, 5600000), where a point cannot be computed to better than a few 1e-9.

M is the summed magnitude of the terms a point of an element is computed from, taken at the element’s farthest parameters. It never grows when an element is split, since a child’s rectangle or span lies in its parent’s:

element	`M`
plane patch	`
cylinder patch	`
elliptical cylinder patch	`
cone patch	`
sphere patch	`
torus patch	`
B-spline patch (sphere)	the largest control point
B-spline patch (witness)	`(p_u + p_v + 1) (w_max / w_min) max
line span	`
circle span	`
ellipse span	`

where o is the frame origin, s the frame’s scale, Lu and Lv the Lipschitz bounds of the parameters. A side’s scale S is the largest M over its root elements, and every element of that side is padded by it. The pad is therefore the same for every element, so it cannot reorder the queue: a pair’s lower bound is its geometric bound less a constant of the whole search, and the rounding floor enters once.

The margins, with u = eps / 2 the unit roundoff and gamma_n the usual n u / (1 - n u):

POINT (16): a computed centre or witness against the exact point. A coordinate sums at most twelve rounded terms of magnitude at most M (gamma_12 = 6 eps), a vector’s length takes a factor sqrt 3 (10.4 eps), and the midpoint of the parameters and a cone’s apex add the rest.
PROJECTION (8): each end of a projected range d . x: a sum of rounded products of terms at most M against a unit direction.
RATIO (8): relative: lengths, sums, differences, and directions that are unit only to rounding.
FLOOR (128): the width a search settles at, in eps (S_a + S_b). At zero size the computed bound may lie 2 (POINT + PROJECTION) eps (S_a + S_b) = 48 eps (S_a + S_b) below the exact one, and the witnesses’ own evaluation adds up to 32 eps (S_a + S_b): 80, with room to spare.

A witness is a point evaluated at a parameter, so it is off its boundary by POINT eps W, W the side’s witness scale: the largest witness M over its root elements, equal to S unless the side has a B-spline face. The reported upper bound is |pa - pb| (1 + RATIO eps) + POINT eps (W_a + W_b), so it is at least the distance between the boundary points the witnesses stand for, and Clearance::Below is never claimed within rounding of a limit the distance does not go below (#439). The search order and the witnesses are those of the computed distance; only the stop test and the reported value widen. A plan overlap shown by two planar faces still reports [0, 0]. The floor adds POINT eps ((W_a - S_a) + (W_b - S_b)), nothing without B-spline faces.

A B-spline sphere’s M is its control points, since its patch is enclosed by them, but a witness runs p_u + p_v levels of de Boor in homogeneous coordinates and divides by the weight. Each level adds at most 4 eps of the largest homogeneous coordinate w_max |P|max; the division by a weight of at least w_min gives ((8L + 0.5) rho + 0.5) eps |P|max per coordinate (L = p_u + p_v, rho = w_max / w_min). Times sqrt 3 that is below 16 (L + 1) rho eps |P|max, which is POINT eps M for the witness M of the table. This is first order in L rho eps (the division is by the computed weight sum, off by up to 4 L eps w_max), so a weight ratio above 1 / (64 L eps) is refused, as is a non-positive weight.

The RATIO guards of the pair and point bounds and a point query’s own pad PROJECTION eps |p| cover rounding that another margin covers too (#447): S is at least the magnitude of every point of its side, so a computed gap or projection is off by a few eps (S_a + S_b) at most, inside the side pads. They stay, so each bound is sound by its own arithmetic, but no test can observe their loss.

The libm functions the evaluators call are assumed within one ulp. The floor is about 3.2e-7 at (450000, 5600000) and about 6e-14 at unit scale. It only stops refinement and changes neither bound; an accuracy below it settles at it and is never reported as met, so the width of the interval returned shows what was reached.

§In plan

plan_boundary_distance measures between the bodies’ projections onto the XY plane (#217). A solid’s shadow is its boundary’s, so the same search applies with every gap, direction and enclosing disc horizontal: elements carry a plan radius from their horizontal speeds, lower bounds project onto horizontal directions only (a normal by its horizontal part), and a face patch is dropped only where no normal of it is horizontal and along the plan offset. plan_overlap shows two shadows overlap over a patch of positive area from two planar faces, not vertical, whose shadows share an open patch, and shows them apart once the lower bound is positive. When the distance search shows neither, a second search over patches of such faces alone, coarsest pair first, looks for the overlap (#237): in the first, pairs of walls and edges whose shadows merely cross take the budget, and a plan distance of zero met between two boundary points ends it.

§Scope

This is the distance between BOUNDARIES. Two solids that overlap measure the distance between their surfaces where they cross (zero), but a solid wholly inside another measures the gap between the two boundaries, not zero. Containment is a separate classification.

Structs§

DistanceBounds: An interval certain to contain the distance between two boundaries, and two witnesses. point_a and point_b are computed points, each within its evaluation rounding of a point of its boundary (POINT eps W, see “Rounding” in the module docs), and upper is at least the distance between those two boundary points (#439): the computed |point_a - point_b| plus that rounding, never less. In plan, an overlap shown by two planar faces reports [0, 0].

Enums§

Clearance: How a certified distance compares with a limit.
PlanOverlap: Whether the plan projections of two bodies overlap.

Functions§

boundary_clearance: Refine the distance only until it clears limit.
boundary_distance: Distance between the boundaries of a and b, to within accuracy.
plan_boundary_clearance: plan_boundary_distance refined only until it clears limit.
plan_boundary_distance: Distance between the plan projections of a and b – their shadows on the XY plane – to within accuracy (#217).
plan_overlap: Whether the plan projections of a and b overlap over a patch of positive area, are certainly apart, or neither could be shown (#217).