Crate axiolid_brep_boolean

Expand description

General exact booleans between exact B-reps with analytic faces.

The general-fuse pipeline of ADR 0075, built in stages:

section_edges: where two operands’ faces cross, as exact curves trimmed exactly to both faces;
split_face: one face cut along its section edges into regions, in the face’s own parameters, with exact pcurves;
boolean: the regions classified against the other solid, selected by operator and sewn into the result.

Operands may touch as well as cross: faces sharing a patch of one surface, sections running along existing edges, tangent contact, and solids meeting along an edge or at a point are all handled, not refused. A traced section along an operand’s line or conic edge takes that edge’s curve, so a revolution’s cap coplanar with a face sews (#382).

Nothing is meshed or fitted. A configuration a step cannot build is refused by name (BooleanError).

§What a result guarantees

Every surface of the result is an operand’s surface, unchanged. Every new edge lies on an exact section curve (a closed form or a certified trace); vertices are those curves evaluated in f64.

Exact decisions. Which section two supports have (closed forms, ruled, torus and traced sections), where a section crosses the surface next to a face’s edge (exact_curve_surface_intersection), whether a point lies in a face (certified membership; too close to decide is refused, not guessed) and whether it lies in a solid (ray parity over exact ray/surface intersections).

Decisions within tolerance. Operands built or placed separately meet faces that agree only up to rounding (#228). These decisions use the caller’s Tolerance and nothing else: eps = tolerance.linear() for distances, alpha = tolerance.angular() for directions.

two supports are one surface when their normals or axes agree within alpha and their offsets within eps;
two supports touch rather than cross where their normals agree within alpha;
a point lies on an edge, or on a pole, within eps;
a section runs along an edge when every point of the edge is proved within eps of it (two lines, or two circles, in closed form);
a section that touches the surface next to an edge, whose double root rounding split or lost, is cut where it meets the edge itself, within eps;
cuts on a section (traced sections too, #381) within eps of each other are one cut, a boundary split within eps of the boundary piece’s end is that end, a cut on an edge imprinted from a coincident face within eps of that edge’s own end is that end (#276), and two evaluations of a vertex within eps are one vertex;
a section is an iso-parameter curve of a face within eps;
a plane is parallel or perpendicular to a cylinder’s axis, or touches the cylinder, when that moves the plane by at most eps over where the section can matter: the largest common box of any pair of their faces, one reading per pair of supports.

One contact, every face pair (#243). A plane read as touching a cylinder (a round hole tangent to a face, placed separately, or a fraction of the tolerance into or short of it) stands for the plane moved onto the cylinder, touching it along one ruling. Every face pair that crosses either surface near it agrees: a curve on the cylinder (a cap’s circle, a face’s circle across the axis) and a line in the plane (a cap’s chord, the plane’s own edge) are cut where they meet that contact ruling, not at their exact roots 2 sqrt(2 r d) apart; and no point where the given and the moved plane disagree on a side decides a piece or a region. A curve whose meeting with the ruling cannot be placed is refused (BooleanError::UnsupportedContact) at that tolerance (see the finer retry below). An exactly tangent pair is decided by the exact predicates instead.

Oblique round walls (#287). An exact extrusion along a leaning direction sweeps each arc of its profile into a tilted EllipticalCylinder whose axis is the direction. Such a face is evaluated, inverted (the angle of the section coordinates over the semi-axes) and classified like any other. A plane meets it in an ellipse, or a circle where it is exactly one, and a plane along its axis in rulings; a cylinder or another such wall on an exactly parallel axis meets it in rulings: all closed forms, cased by exact predicates, with closed-form pcurves. Other pairs take the ruled and traced sections as before. The within-tolerance plane/cylinder readings above are for right cylinders only: whether a plane is parallel to such a wall’s axis or touches it is always decided exactly.

A hole touching a fillet (#249). A round hole touching a flange with root fillets touches each fillet too, and the perpendicular cylinders meet in two loops crossing at the fillet/flange edge. The trace is taken over the fillet’s whole turn when its face’s box cuts through the crossing, a section is cut at a smooth edge where the edge crosses the other surface, and under a contact reading the crossing is placed on the contact; where the section misses the contact point by more than the tolerance the reading is refused (BooleanError::UnsupportedContact) and the boolean is cut again at the finer tolerance below, where a hole a fraction of the tolerance off the flange is no contact but a gap, decided exactly. See tangency.

Exact first (#236). A reading about the operands’ own surfaces – two supports are one, a plane is parallel or perpendicular to a cylinder’s axis or touches it – is first put to an exact predicate on the operands’ f64 numbers (dyadic arithmetic, axiolid-exact). Faces that are exactly coplanar, parallel or perpendicular, as operands placed by matrices with entries 0 and +-1 meet, are decided exactly and use no tolerance. A reading the exact predicate rejects is not exact even when its f64 measure is exactly zero (one general rotation turns a hole’s axis and a wall’s normal into the same f64 vector, though the numbers given are not perpendicular), so a tolerance with a zero part never takes it (#251): at Tolerance::ZERO the exact answer stands and the general closed form decides. A reading about constructed points (a cut, a vertex, a point on an edge) compares f64 evaluations of exact curves, so a residue up to 2^-40 of the operands’ extent (about four thousand units in the last place) is the rounding of one exact point, read without the tolerance; only a larger residue is a decision within tolerance. The widening that covers such unrecorded residues is BooleanReport::rounding_floor (#244): ROUNDING_FACTOR times BooleanReport::extent, which defines the extent exactly, plus the move of an angular residue of that factor (radians) over the same extent. It is not the threshold for a decision.

Guarantee. boolean_with_report returns a BooleanReport of the within-tolerance decisions that fired, by kind, with the furthest each moved or turned the operands. When it is empty (BooleanReport::is_exact), the result is the exact boolean of the operands as given: every decision was exact, and new vertices are exact points evaluated in f64. Constructed points closer than ROUNDING_FACTOR times BooleanReport::extent count as one point and are not reported, and BooleanReport::rounding_floor covers them, so a consumer widening distances on any result, exact or not, widens them by that floor too. At Tolerance::ZERO nothing can be read within tolerance, so every result is exact (and still has its floor); operands that only miss each other by rounding are then refused, not guessed. The report’s session enforces it (#251): a decision recorded at Tolerance::ZERO, or beyond the caller’s tolerance, is a debug assertion, and otherwise refused (BooleanError::ToleranceExceeded) rather than returned with a report that misdescribes it. When the report is not empty, the result is the exact boolean of operands whose faces were moved by at most eps (and, for a coincidence or contact of directions, turned by at most alpha), with every surface and curve exact for those; the report bounds how far. A reading that no single such perturbation explains is refused instead: cuts chained within eps of each other over more than eps are BooleanError::NearCoincidence. Features further apart than the tolerance always go through the exact predicates: a gap of ten tolerances stays a gap.

Finer where the readings fail (#332). Two features of the operands closer than eps but further apart than rounding are each read within the tolerance, and the readings need not agree: the sides of two abutting openings in a curved wall, one reaching a few micrometres (or just under a millimetre) past the other, their planes turned by more than alpha, leave cuts merged at a point on neither face’s boundary, and the faces do not sew. A boolean refused at the caller’s tolerance is cut again at FINER_FACTOR (2^-10) times it, where such features are apart and decided by the exact predicates, and the readings still cover the rounding of separately placed operands. The result is then the exact boolean of operands moved by at most the finer tolerance, and BooleanReport::finer says so; a boolean refused at both returns the refusal at the caller’s tolerance. A boolean that succeeds at the caller’s tolerance is never cut again.

A line edge short of the face it ends on (#409). A door stopping 3e-7 short of a wall’s face has its end face read as the wall’s, but the edge of its floor along that face ends that short of the wall floor’s edge, further than the fixed slack with which a split face welds piece ends, so the wall’s floor does not split round the door’s footprint. A boolean still refused at the finer tolerance is cut a last time at the caller’s, with an imprinted line edge extended to the crossing with the other face’s boundary where that lies within eps of the edge’s end (imprint_cuts), mirroring the door past the face, whose edge the crossing falls inside. The move is a merge of points above the rounding floor, so the report is not exact; a boolean the finer tolerance cuts is never cut so.

A point near a support it is not read on (#332, #327). A region is classified at a point inside it by ray parity, and a point within eps of any face’s support is first not trusted: a reading may have moved that face onto the point’s own. Where no point of a region is decided so, its points are classified again reading the ray’s start exactly: a point is on a support only within the rounding floor, but for the faces read as its own support. A box whose face is tangent to a curved wall’s inner cylinder (its face’s points micrometres to millimetres from the cylinder, off the contact ruling) is then decided at the caller’s tolerance, for the operands as given.

Operands far from the origin (#418, #419). A coordinate a million metres out has a nanometre ulp, and the certified decisions work at the scale of the operands: the same union that sews at the origin was refused (“the kept faces do not sew”, “a point too close to a face boundary to classify”) at (6e5, 5.6e6, 200). Operands whose common vertex box lies at least four diagonals from the origin are moved by -c first, c its centre rounded to the ulp of the largest coordinate, and the result is moved back by +c. The move is taken only where ExactBRep::translated_exactly proves that every vertex, frame origin, curve origin and control point moves with no rounding: the recentred operands are then the same solids, shifted, and a vertex of an operand that survives returns to its own coordinates. A new vertex is rounded once, to the ulp of its far coordinate. The report refers to the operands as given, whose extent scales the rounding floor. An axis whose centre lies within four diagonals of zero is not moved. Operands that do not move exactly (a curve or control point whose sum with c rounds, an elevated or banked curve), and operands whose recentred cut is refused, are cut where they are, as before: planar faces charted in world coordinates (#227) keep parameters as far out as they were, and the classifier cannot decide them there. Operands nearer the origin on every axis are cut bit for bit as without it.

Checked before it is returned (#445). Every vertex of a result lies on the curve of each edge it bounds, and on each edge use’s pcurve lifted through its face’s surface at the use’s ends, within the caller’s linear tolerance and, for an exact report, within the rounding floor too (at Tolerance::ZERO the floor alone). A result over that bound is refused (BooleanError::VertexOffCurve) rather than returned with a report that misdescribes it; the check runs inside the cut, so the retries above apply to its refusal. Far from the origin the floor can exceed the caller’s tolerance (a tolerance within a few ulps of the coordinates is refused this way); the check caps what reaches a vertex, it does not tighten the floor.

Bookkeeping in a face’s parameters (ordering pieces leaving a vertex, naming a point’s parameters on the surface it was evaluated from) uses fixed relative slacks. Relative to a parameter they are far below any tolerance only near the origin: in world-charted parameters such as a line’s -y = 5.6e6 they span 5.6e-6, more than a tolerance. So a window’s end never replaces a feature cut within the slack of it (#445), and the check above refuses what a slack leaves. Two piece ends weld into one vertex of a split face only where they also lie within the tolerance on the surface (#332), so a slack spanning more of a long arc than a fine tolerance never joins what a split kept apart. It never decides geometry: an order it cannot settle is refused (BooleanError::TangentSplit, BooleanError::UnclosedSplit).

Structs§

BooleanReport: The within-tolerance decisions one boolean took (#236).
Piece: One stretch of a split face’s boundary, in the direction the region’s loop runs.
Region: One region of a split face: an outer loop and its holes.
SectionEdge: A piece of an intersection curve lying on a face of each operand.
ToleranceDecision: The worst reading of one kind a boolean made within tolerance.

Enums§

BooleanError: Why a boolean step could not be carried out exactly.
PieceSource: Where a piece of a split face’s boundary came from.
ToleranceDecisionKind: What a within-tolerance decision read (#236).

Constants§

FINER_FACTOR: The ratio of the tolerance a refused boolean is cut again at to the caller’s (#332): 2^-10, about a micrometre under a millimetre.
ROUNDING_FACTOR: The rounding floor relative to the operands’ extent: 2^-40 (#236, #244).

Functions§

boolean: The exact boolean of two exact B-rep solids.
boolean_with_report: boolean, with the within-tolerance decisions it took (#236).
section_edges: Every section edge between the faces of a and the faces of b.
split_face: Split face of brep along the section edges lying on it.