axiolid_brep_boolean/
lib.rs

1#![forbid(unsafe_code)]
2
3//! General exact booleans between exact B-reps with analytic faces.
4//!
5//! The general-fuse pipeline of ADR 0075, built in stages:
6//!
7//! - [`section_edges`]: where two operands' faces cross, as exact curves
8//!   trimmed exactly to both faces;
9//! - [`split_face`]: one face cut along its section edges into regions, in
10//!   the face's own parameters, with exact pcurves;
11//! - [`boolean`]: the regions classified against the other solid, selected
12//!   by operator and sewn into the result.
13//!
14//! Operands may touch as well as cross: faces sharing a patch of one
15//! surface, sections running along existing edges, tangent contact, and
16//! solids meeting along an edge or at a point are all handled, not
17//! refused.
18//!
19//! Nothing is approximated. A configuration a step cannot build exactly is
20//! refused by name ([`BooleanError`]), never meshed or fitted, and every
21//! decision comes from an exact predicate or certified membership: a point
22//! too close to a boundary to decide is refused, not guessed.
23
24mod assemble;
25mod classify;
26mod seams;
27mod section;
28mod split;
29mod support;
30
31pub use section::{section_edges, SectionEdge};
32pub use split::{split_face, Piece, PieceSource, Region};
33
34use axiolid_brep::ExactBRep;
35use axiolid_core::{BooleanOperator, Tolerance};
36use axiolid_evaluate::surface::{locate, normal};
37use axiolid_surface::Surface;
38use axiolid_topology::Orientation;
39
40/// The exact boolean of two exact B-rep solids.
41///
42/// ADR 0075 stages 1 and 2: faces on planes, cylinders, elliptical
43/// cylinders, cones, spheres and tori, meeting in any section
44/// `exact_surface_intersection` builds (lines, conics, ruled, torus and
45/// traced sections).
46///
47/// # Errors
48///
49/// Anything a step refuses (see [`BooleanError`]), or a result with nothing
50/// left.
51pub fn boolean(
52    a: &ExactBRep,
53    b: &ExactBRep,
54    operator: BooleanOperator,
55    tolerance: Tolerance,
56) -> Result<ExactBRep, BooleanError> {
57    // Faces that wind round their surface without a seam get one first.
58    let seamed_a = seams::with_seams(a, tolerance)?;
59    let seamed_b = seams::with_seams(b, tolerance)?;
60    let a = seamed_a.as_ref().unwrap_or(a);
61    let b = seamed_b.as_ref().unwrap_or(b);
62    let edges = section_edges(a, b, tolerance)?;
63    let solid_a = classify::Solid::new(a, tolerance)?;
64    let solid_b = classify::Solid::new(b, tolerance)?;
65    let mut kept = Vec::new();
66    let cuts: Vec<axiolid_core::Point3> = edges.iter().flat_map(|e| [e.start, e.end]).collect();
67    for (operand, other, other_solid, first) in [(a, b, &solid_b, true), (b, a, &solid_a, false)] {
68        let topology = operand.topology();
69        for index in 0..topology.faces().len() {
70            let face = topology
71                .face_id_at(index)
72                .ok_or(BooleanError::DanglingReference)?;
73            let record = &topology.faces()[index];
74            let surface: Surface = record
75                .surface
76                .and_then(|id| operand.surfaces().get(id.index()))
77                .ok_or(BooleanError::DanglingReference)?
78                .clone();
79            let mine: Vec<SectionEdge> = edges
80                .iter()
81                .filter(|e| {
82                    if first {
83                        e.face_a == face
84                    } else {
85                        e.face_b == face
86                    }
87                })
88                .cloned()
89                .collect();
90            // The other operand's faces on this face's surface: a region
91            // may lie on one of them rather than inside or outside.
92            let coincident: Vec<usize> = (0..other.topology().faces().len())
93                .filter(|&f| {
94                    other.topology().faces()[f]
95                        .surface
96                        .and_then(|s| other.surfaces().get(s.index()))
97                        .is_some_and(|s| support::same_support(&surface, s, tolerance))
98                })
99                .collect();
100            for region in split_face(operand, face, &mine, first, &cuts, tolerance)? {
101                let sign = match record.orientation {
102                    Orientation::Forward if !region.against => 1.0,
103                    Orientation::Reversed if region.against => 1.0,
104                    _ => -1.0,
105                };
106                let (keep, flip) = decide(
107                    &region,
108                    &surface,
109                    sign,
110                    other_solid,
111                    &coincident,
112                    operator,
113                    first,
114                    tolerance,
115                )?;
116                if keep {
117                    kept.push(assemble::Kept {
118                        surface: surface.clone(),
119                        orientation: record.orientation,
120                        region,
121                        flip,
122                    });
123                }
124            }
125        }
126    }
127    assemble::assemble(&kept, tolerance)
128}
129
130/// Whether a region is kept, and whether it bounds the result from its
131/// other side: classified at the first interior point that decides.
132#[allow(clippy::too_many_arguments)]
133fn decide(
134    region: &Region,
135    surface: &Surface,
136    sign: f64,
137    other_solid: &classify::Solid<'_>,
138    coincident: &[usize],
139    operator: BooleanOperator,
140    first: bool,
141    tolerance: Tolerance,
142) -> Result<(bool, bool), BooleanError> {
143    let mut last = BooleanError::Undecided;
144    for point in classify::interior_points(region, surface)? {
145        match classify_point(
146            point,
147            surface,
148            sign,
149            other_solid,
150            coincident,
151            operator,
152            first,
153            tolerance,
154        ) {
155            Err(BooleanError::Undecided) => last = BooleanError::Undecided,
156            other => return other,
157        }
158    }
159    Err(last)
160}
161
162#[allow(clippy::too_many_arguments)]
163fn classify_point(
164    point: axiolid_core::Point3,
165    surface: &Surface,
166    sign: f64,
167    other_solid: &classify::Solid<'_>,
168    coincident: &[usize],
169    operator: BooleanOperator,
170    first: bool,
171    tolerance: Tolerance,
172) -> Result<(bool, bool), BooleanError> {
173    if let Some(theirs) = other_solid.on_face(point, coincident, tolerance)? {
174        // On the other solid's boundary: kept once, from the first
175        // operand, where the operator leaves a boundary.
176        let (u, v) = locate(surface, point, tolerance).map_err(|_| BooleanError::Evaluation)?;
177        let ours = normal(surface, u, v).map_err(|_| BooleanError::Evaluation)? * sign;
178        let same = ours.dot(theirs) > 0.0;
179        let keep = first
180            && match operator {
181                BooleanOperator::Union | BooleanOperator::Intersection => same,
182                BooleanOperator::Difference => !same,
183                _ => return Err(BooleanError::UnsupportedSection),
184            };
185        return Ok((keep, false));
186    }
187    let inside = other_solid.contains(point, tolerance)?;
188    Ok(match (operator, first) {
189        (BooleanOperator::Union, _) => (!inside, false),
190        (BooleanOperator::Intersection, _) => (inside, false),
191        (BooleanOperator::Difference, true) => (!inside, false),
192        (BooleanOperator::Difference, false) => (inside, true),
193        _ => return Err(BooleanError::UnsupportedSection),
194    })
195}
196
197use axiolid_measure::ExactMeasureError;
198use core::fmt;
199
200/// Why a boolean step could not be carried out exactly.
201#[non_exhaustive]
202#[derive(Debug, Clone, PartialEq, Eq)]
203pub enum BooleanError {
204    /// Two faces' supports intersect in a curve this stage does not take
205    /// (anything but a line, circle or ellipse).
206    UnsupportedSection,
207    /// A face is trimmed by an edge or pcurve family this stage cannot
208    /// intersect or classify against.
209    UnsupportedTrim,
210    /// A point was too close to a face boundary to classify.
211    Undecided,
212    /// A curve or surface could not be evaluated or inverted.
213    Evaluation,
214    /// A handle referenced missing geometry.
215    DanglingReference,
216    /// A face domain could not be built.
217    Measure(ExactMeasureError),
218    /// A face whose surface, or a section on it, has no exact pcurve in
219    /// this stage.
220    UnsupportedSplit,
221    /// The pieces of a split face do not close into loops.
222    UnclosedSplit,
223    /// Two pieces leave a vertex of a split face in the same direction and
224    /// bend alike there, so no order between them can be read off.
225    TangentSplit,
226    /// The operation leaves nothing: an intersection of solids that only
227    /// touch, or a difference that removes everything. An exact B-rep
228    /// cannot be empty, so this is the answer, not a refusal.
229    EmptyResult,
230    /// A cavity of the result lies inside none of its solids.
231    AmbiguousCavity,
232    /// The kept faces did not sew into a valid exact B-rep.
233    Assembly,
234}
235
236impl fmt::Display for BooleanError {
237    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
238        match self {
239            Self::UnsupportedSection => {
240                f.write_str("a face pair meets in a curve this stage does not build")
241            }
242            Self::UnsupportedTrim => {
243                f.write_str("a face is trimmed by a curve family this stage cannot intersect")
244            }
245            Self::Undecided => f.write_str("a point lies too close to a face boundary to classify"),
246            Self::Evaluation => f.write_str("a curve or surface could not be evaluated"),
247            Self::DanglingReference => f.write_str("a handle references missing geometry"),
248            Self::Measure(error) => write!(f, "a face domain could not be built: {error}"),
249            Self::UnsupportedSplit => {
250                f.write_str("a face or section has no exact pcurve in this stage")
251            }
252            Self::UnclosedSplit => f.write_str("the pieces of a split face do not close"),
253            Self::TangentSplit => {
254                f.write_str("two pieces leave a vertex of a split face in one direction")
255            }
256            Self::EmptyResult => f.write_str("the operation leaves nothing"),
257            Self::AmbiguousCavity => {
258                f.write_str("a cavity of the result lies inside none of its solids")
259            }
260            Self::Assembly => f.write_str("the kept faces did not sew into a valid exact B-rep"),
261        }
262    }
263}
264
265impl std::error::Error for BooleanError {}
axiolid_brep_boolean/lib.rs

axiolid_brep_boolean/
lib.rs
