Module deviation

Expand description

How far the exact geometry may lie from a compiled mesh (#232).

ReferenceMeshCompiler::compile_mesh_with_deviation returns, next to the mesh, a DeviationReport: a certified upper bound on the distance from any point of the exact surface the graph describes to the nearest mesh triangle, which paths contributed to it, and whether it is within the chord budget the caller asked for. This is the quantity #231 proves for revolutions, spheres, tori and sweeps along one arc; for the paths that have no proof by construction it is computed for the mesh at hand.

§A bound, never an estimate

Every number in a report is an upper bound: either a construction’s proof (DeviationBound::Proven) or a computation that only uses certified derivative bounds and exact distances (DeviationBound::Certified). Where neither exists the path is named DeviationBound::Unbounded with its reason, and the report’s overall bound is None; nothing is filled in with a sampled or heuristic value. The bounds are one-sided, exact surface to mesh: the bound limits how far the exact surface lies from the mesh; it does not detect extra material in the mesh (a cap the exact solid does not have) and does not change with it. A measured all-planar boolean is the exception (#329): it also reports how far its mesh lies from the exact result, under MESH_TO_EXACT.

§How each path is bounded

Authored meshes are their own exact surface: 0. An authored polygon face within the linear tolerance of its plane counts as planar and adds nothing. A face warped beyond it has no unique surface (#254): it is triangulated in its fit plane and reported DeviationBound::Certified under the detail "non-planar authored face", never Proven. The value is the width of the slab the face’s corners (holes included) span about that fit plane, largest minus smallest signed distance (#261): every reading of the face that lies in that slab (either diagonal triangulation, the face flattened onto the plane, a bilinear patch) is within it of the mesh wherever it lies over the face, and the mesh within it of each reading that covers the face (crate::planar gives the argument); the worst face of the mesh is reported.
Profiles (axiolid_construct::profile::profile_deviation): the chord budget for every family the flattener certifies (lines, arcs, circles, ellipses, B-splines), plus any merged near-duplicate point, scaled by a derived profile’s stretch. An extrusion’s walls and caps are within that of the exact solid.
Revolutions: the profile’s bound plus the half budget the turn gets (#231). Tapered revolutions only between straight-edged profiles, whose rings correspond exactly; tapered extrusions are unbounded (their twisted walls are not measured).
Swept disks: along lines, polylines (filleted, open or closed) and chains of segments and arcs by axiolid_construct::pipe‘s proof (#232, #245, #248: a loop’s closing twist is part of it), along one circular arc by #231’s; a corner mitred beside an arc (#248) is certified by the branch and bound below, over the bend’s band of torus up to the mitre plane and the planar face between the two tubes’ sections (each trimmed by certain inequalities on its cells), and reported DeviationBound::Certified under the detail MITRE_BESIDE_AN_ARC; along an ellipse, a B-spline, or an elevated or banked curve without a grade break (#252, its derivative bounds in plan distance from axiolid_reference::elevated), certified against the exact tube (walls, bore and square end caps) by branch and bound, below, its centre over an intrinsic plan read from a certified position table whose error the bound carries (#393); an elevated curve whose grade breaks, or over a chain plan, or under an intrinsic profile, is unbounded by name. A straight plan under a constant grade is a segment. Fixed-reference sweeps along a segment, or along a circle whose plane the reference is normal to, by #231; other frame laws, polyline and composite directrices are unbounded here.
Primitives: spheres and tori by #231, cylinders and cones by #232 (axiolid_reference::primitive), flat-faced ones exactly.
B-rep faces: planar faces with straight edges exactly; a face that declares no surface and whose corners lie off their fit plane beyond the linear tolerance (#257) as a warped authored face is, by its slab width, DeviationBound::Certified under the detail "non-planar face without a surface"; curved faces per triangle from the surface’s second derivatives over the triangle, plus the trim lens of each pcurve chord (the B-rep tessellator’s module notes give the argument).

§Branch and bound against an exact parameterisation

Where the mesh’s vertices sit at no known surface parameters (a tube’s stations stand on frames read off its sampled path, a boolean’s cut curve wherever the mesh boolean put it), the exact surface T is covered by parameter cells. A cell with centre x_c and half-widths h maps into T(x_c) + DT(x_c) [-h, h] grown by e2 = 1/2 (A h_x^2 + 2 B h_x h_y + C h_y^2), with A, B, C certified bounds on T‘s second partials over the cell (for a tube, from the directrix’s derivative bounds through its normalised frame). Distance to one triangle is convex, so over a piece of that parallelogram it is at most the largest of the piece’s corners’; the best triangle per piece and the worst piece, plus e2, bound the cell. Cells are split worst first until the worst bound is within 10% of the largest exact distance sampled at a cell centre, or a work cap is reached; the reported value is always the worst bound over all cells. A tube (#252) settles once within the budget, joins its slightly twisted quads as flat regions up to a twentieth of the budget thick (that thickness is part of the bound), and cuts each cell the way that lowers its halves more, so a long tube’s long, thin quads do not force every cell down to the width of their diagonals.

Surfaces trimmed by a parameter rectangle (#311): a uniform grid of cells whose corners are exact surface points, each cell within 1/8 ((A + B) h_u^2 + (C + B) h_v^2) of its two triangles from the surface’s certified interpolation bounds over the cell (crate::trimmed), DeviationBound::Certified; a cell a B-spline knot line of full multiplicity crosses is DeviationBound::Unbounded by name.
Instances scale the bound by an upper bound on their transform’s largest stretch (stretch): the largest column length grown by 1 + 96 eps when the columns are orthogonal, else the Frobenius norm. The margin keeps it above one even for an identity or a rotation, since an f64 rotation is orthonormal only to rounding; the source is meshed to the budget shrunk by that factor, down to the largest value whose rounded product with it is within the budget (shrunk_budget, as #255 shrinks a curve-bounded plane’s), so a rigid or scaled instance of a body meshed to exactly its budget reports at most the requested budget, nested instances included (#258). Uniform, non-uniform and sheared instances grow the bound by their full stretch and stay sound. The rounding of moving each vertex is added on top (#295, “Placement rounding” below). The rounding of computing a construction’s own vertices is not part of any bound. Collections take the worst member.
Runs of sections at stations (#247): stationed spines and sectioned surfaces are bounded cell by cell as they are sampled (crate::station‘s bound module): the vertex paths’ chord bound from certified derivative bounds of the frame law, breakpoints at seams inside a cell, and the wall quad’s axiolid_construct::loft::quad_deviation, plus a spine’s profile flattening, DeviationBound::Certified, a frame read by quadrature (an ellipse, a B-spline, an offset of a curve in closed form) bounded against its exact law (#316); a frame on an intrinsic curve, a chain or an offset beside one, a cell beside a mitre on a curved piece or with a changing section, and different curved profiles are DeviationBound::Unbounded by name.
Instances at stations (#264) move their source rigidly: on a line basis the frame is exact and the source’s bound stands. On any other the frame is the exact curve’s at a distance read by an estimate (the arc-length inverse, quadrature), and crate::station::placement_accuracy states how far the placement lies from the exact one (#405): on a circle, a polyline, an elevated or banked curve over a line or a circle, an intrinsic plan alone or under a closed-form profile and composites of them, a DeviationBound::Certified error F of any point of the source (point_error + axis_error R, R the largest sum |x| + |y| + |z| over the source mesh’s vertices) that every contribution grows by as it grows by the placement’s rounding, and that is named once under the path DeviationPath::StationPlacement; the source is re-meshed with room for the rounding and F when they would carry it over the budget. Any other basis (a frame read by quadrature, a chain, a basis itself placed inexactly, a station beside a seam it is not read on) is DeviationBound::Unbounded under that path, with the reason named.
Booleans (#235): cutting two meshes moves the intersection curve, and a one-sided bound on each operand does not bound it, so nothing is derived from the operands. Where ReferenceExactCompiler builds the exact result of the same node (booleans of placed extrusions and revolutions, #228, #376, #378, and half-space clips, #234; for the report also booleans with a mesh operand, any operator, below), the mesh is certified against that exact B-rep by the branch and bound above, over each face’s trimmed parameter domain; a boolean it refuses is unbounded with the refusal’s name. The bound is relative to the exact compiler’s result, the exact boolean of operands moved by at most the tolerance (#228), not to the boolean of the unperturbed operands. It runs only for a report, and only for the booleans whose result is emitted, not for the inner booleans of a chain; the search stops once within the requested budget. When the exact result is all planar the other direction is measured too (#329): how far any point of the mesh lies from the exact result, against a witness mesh built on the exact faces, a separate DeviationPath::Boolean contribution under the detail MESH_TO_EXACT, so material the mesh has and the exact result lacks (a strip of a clipped wall the mesh kept) shows in the report’s bound. Both directions are carried through instances like any other contribution.
Operands snapped together (#276, #291): before the mesh boolean, operand coordinates a rounding residue (16 f64::EPSILON of the operands’ largest coordinate) from the other operand’s axis-aligned faces are set onto them exactly (crate::snap), so a skin that thin is not cut as one; a thicker skin is kept. The largest move is a DeviationBound::Certified contribution of DeviationPath::Boolean under the detail SNAPPED_OPERANDS, carried through instances and enclosing booleans, the measured ones included; it never exceeds the tolerance. A boolean whose snapped operands are refused is cut as given and reports no snap.
Warped operands (#266): an operand that is an authored mesh, or a B-rep whose faces are all planes with straight edges or warped faces without a surface, is measured as the exact polyhedron of its triangle mesh: a warped face flattened to its triangles, within its slab width w of every reading of the face (crate::planar), both ways. That is how an operand’s certified bound composes into a boolean’s: not as a one-sided bound (above), but as a two-sided perturbation of the operand. The boolean’s mesh is measured against the exact boolean of the flattened operands (ADR 0080: the exact boolean of operands perturbed within the reported deviation), by d, and its contribution is DeviationBound::Certified d + w, w the largest slab width of any operand flattened beneath it, under the detail “measured against the exact boolean of operands flattened within their slab width, plus it”. The search settles within the budget less w, so a boolean whose slab widths fit the budget reports within it, and meets_requested follows. Each warped operand’s own contribution (“non-planar authored face”, “non-planar face without a surface”) is carried as the snap is, so the report names it. Transversal to the cut, the boolean of the unflattened operands is within d + w of the mesh too; near tangency the guarantee is ADR 0080’s, relative to the flattened operands. Where the exact boolean cannot take the flattened operand (a mesh that is not a closed two-manifold, a B-rep with a curved face, a tool that is itself a boolean, a configuration the general boolean refuses) the boolean is DeviationBound::Unbounded with that refusal’s name, and the warp is still named. An unwarped mesh operand (w = 0) is measured like any exact operand, against the exact boolean of the operands as given when no decision within tolerance fired.
Operand faces read as one surface (#324): where the general boolean reads a face of one operand on a face of the other within tolerance (a niche flush with a curved wall’s inner face, or a unit in the last place inside it), the furthest the reading moved an operand is a DeviationBound::Certified contribution of DeviationPath::Boolean under the detail COINCIDENT_OPERANDS, next to the boolean’s measured one. Like a snap’s move, it names the perturbation the exact result stands for; it is not carried through enclosing booleans, whose exact result merges the reading’s report.
Every reading within tolerance (#421): the furthest any kind of reading (merged points, contact, an incident point, coincident supports, …) moved a feature is a DeviationBound::Certified contribution of DeviationPath::Boolean under TOLERANCE_READINGS, and the report’s rounding floor under BOOLEAN_ROUNDING_FLOOR. The boolean’s own contribution is widened by their sum: the bound covers the boolean of the operands as read, each moved by at most the named readings, so they add to the measured distance rather than being the worst of it and them. A reading may change the topology against the operands as given; the named readings are what say so.

§Placement rounding

An Instance or an InstanceAtStation moves its source’s vertices by applying its transform in f64, which rounds each coordinate by a few ulps of its magnitude: an absolute error, about 1e-9 at georeferenced coordinates of 6e6, that no relative factor covers (#295). Every reported bound therefore carries, for each transform applied, the term r = 4 eps M (PLACEMENT_EPSILONS, placement_rounding): M is the largest magnitude a placed coordinate sums, sum_j |a_ij| |p_j| + |t_i| over the source’s vertices p (the coordinate’s own magnitude where nothing cancels), and the constant covers sqrt 3 gamma_4 < 3.47 eps: four rounded operations per coordinate, three coordinates per point. A source bound d placed with stretch s reports s d + r, its kind kept; a nested instance grows the inner r by the outer stretch and adds its own. The term is named under DeviationPath::Placement / PLACEMENT_ROUNDING. A row that copies a coordinate (one coefficient +-1, no translation) rounds nothing, so an identity or a mirror adds nothing.

The source’s budget leaves room for it: the source is meshed to the budget less a room, shrunk by the stretch, so s b + room rounds to within the budget (shrunk_budget_within). The room starts at the floor r reaches at the translation’s scale (the term at the origin) plus a 2^-20 share of what is left, for the source’s own coordinates; where the source’s mesh then rounds by more than that and its bound would carry the instance over the budget, it is meshed once more with room for an eighth more than it showed. A budget at or below the floor at the translation’s scale, or below the rounding of the placed vertices themselves, is refused with BUDGET_BELOW_PLACEMENT_ROUNDING rather than reported as met.

Structs§

DeviationContribution: One path’s share of a report.
DeviationReport: A certified bound on the distance from the exact surface to a compiled mesh (#232).

Enums§

DeviationBound: A bound on how far the exact surface may lie from the mesh.
DeviationPath: The construction path a part of the mesh came from.

Constants§

BOOLEAN_ROUNDING_FLOOR: The DeviationContribution::detail of a boolean measured against an exact result: the rounding floor of its report (#244, #421), within which constructed points were read as one without a decision. Present whenever the floor is not zero, exact result or not. The boolean’s own bound is widened by it.
BUDGET_BELOW_PLACEMENT_ROUNDING: The input family a compilation is refused with when its chord budget, in an instance’s frame, is at or below the rounding of placing the instance’s vertices (#295): at the translation’s scale before the source is meshed, at the placed vertices’ scale after. No mesh placed in f64 there is within the budget, so none is reported as meeting it.
COINCIDENT_OPERANDS: The DeviationContribution::detail of a boolean measured against an exact result in which faces of the two operands were read as one surface within tolerance (#324: a niche’s inner cylinder a unit in the last place off a curved wall’s inner face): its bound is the furthest that reading moved an operand, so the exact result the mesh is measured against is the boolean of operands perturbed by at most that much (ADR 0080). It names the perturbation, as SNAPPED_OPERANDS does; the boolean’s own contribution bounds the mesh’s distance to that result.
EMPTY_RESULT: The DeviationContribution::detail of a boolean whose exact result is empty and whose mesh is too (#326): nothing is left in either, so the distance between them is certified 0, widened like any bound by the readings and the rounding floor of the exact result’s report. The bound is unbounded by name when the empty result is that of operands flattened within a warped slab width. The exact compiler holds the empty result internally and refuses it only as a root, so the report cannot be measured against a B-rep; an empty exact result against a mesh with triangles, or the reverse, is unbounded by name.
MESH_TO_EXACT: The DeviationContribution::detail of a measured boolean’s other direction (#329): a certified bound on how far any point of the mesh lies from the exact compiler’s result (the same result as the boolean’s own contribution), widened like it by the flattening, the readings and the rounding floor. Only for an all-planar exact result.
MITRE_BESIDE_AN_ARC: The DeviationContribution::detail of the corners a swept disk mitres beside an arc (#248): the bend’s band and the planar face between the two tubes’ sections, certified against the mesh by branch and bound; the rest of the pipe stays proven under its own detail.
PLACEMENT_EPSILONS: How many f64::EPSILON of the largest summed coordinate magnitude bound the rounding of applying a transform to a point (#295): a coordinate sums four terms, each rounded at most four times, so it is off by at most gamma_4 < 2.000_001 eps of its summed magnitude, and a point by sqrt 3 of that, below 3.47 eps; 4 also covers computing the magnitude itself in f64 (see the module’s “Placement rounding”).
PLACEMENT_ROUNDING: The DeviationContribution::detail of DeviationPath::Placement: the rounding of applying an instance’s transform to its source’s vertices in f64 (#295), PLACEMENT_EPSILONS f64::EPSILON of the largest coordinate magnitude the placement sums (see the module’s “Placement rounding”). Every other contribution of the instance is grown by it too.
REFEREED_DIFFERENCE: REFEREED_UNION for a difference whose mesh held a void the exact result lacks, bounded by skins within rounding where the cutter met its host, and which the exact compiler decided (#423, ADR 0098). A difference with no extra shell, or whose faces the exact compiler read further than rounding, is never refereed: a skin or void thinner than the tolerance stays as authored (ADR 0096, D7).
REFEREED_DIFFERENCE_EXACT: REFEREED_DIFFERENCE when no decision within the tolerance fired.
REFEREED_INTERSECTION: REFEREED_DIFFERENCE for an intersection, on the same trigger: its mesh held a shell the exact result lacks (#423, ADR 0098).
REFEREED_INTERSECTION_EXACT: REFEREED_INTERSECTION when no decision within the tolerance fired.
REFEREED_UNION: The DeviationContribution::detail of a union the mesh cut could not settle and the exact compiler decided (#391, ADR 0098): the mesh is the exact compiler’s union tessellated, and the exact union is that of operands read as in contact within the tolerance (COINCIDENT_OPERANDS names how far). The bound is the tessellation’s: how far the exact union’s surface lies from the mesh.
REFEREED_UNION_EXACT: REFEREED_UNION when no decision within the tolerance fired: the mesh is the tessellation of the exact union of the operands as given.
SNAPPED_OPERANDS: The DeviationContribution::detail of a boolean whose operands were moved onto each other’s faces by a rounding residue, within the linear tolerance, before the mesh boolean cut them (#276, #291): its bound is the largest distance any operand vertex moved, so the mesh is the boolean of operands perturbed by at most that much. It travels with the boolean’s result through instances (scaled, plus the placement’s rounding, #295) and enclosing booleans, also where an enclosing boolean is measured against its exact result.
TOLERANCE_READINGS: The DeviationContribution::detail of a boolean measured against an exact result whose report holds readings within tolerance (#421): its bound is the largest distance any kind of reading moved a feature (BooleanReport::linear: merged points, an incident point, coincident supports, …, or an angle turned, as a distance over the operands’ extent), so the exact result the mesh is measured against is the boolean of operands perturbed by at most that much (a reading may change the topology against the operands as given: this contribution is what says so). The boolean’s own bound is widened by it. COINCIDENT_OPERANDS names the coincident supports’ share.