axiolid_nurbs/
intersection_curve.rs

1//! Constructed intersection curves from certified traces (#6).
2//!
3//! # What is constructed, and why it is sound
4//!
5//! `intersect_surface_surface_certified` proves WHERE an intersection is:
6//! it returns endpoint enclosures and a transversality bound. It does not
7//! return a curve. Exact booleans, section curves, offsets, and fillets all
8//! need the curve itself, which is why this is the gate in front of them.
9//!
10//! The construction here is deliberately narrow, and its narrowness is the
11//! proof. A trace is only turned into a curve when BOTH surfaces are exact
12//! single-span AFFINE patches, which the trace certificate already
13//! establishes. Two planes meet in a straight line, so a degree-1 segment
14//! between the two certified endpoints is the EXACT intersection, not a
15//! sampled approximation of it:
16//!
17//! - each affine patch is a subset of a plane, and the signed distance to a
18//!   plane is an AFFINE function of position;
19//! - an affine function on a segment attains its extremes at the endpoints;
20//! - so a deviation bound proven at both endpoints bounds the WHOLE segment.
21//!
22//! That is why the reported `deviation_upper_bound` is a real bound over the
23//! curve rather than a bound at the two points that happened to be checked.
24//!
25//! Everything else REFUSES by name. A curved or unresolved trace has no
26//! straight-line proof, and emitting a polyline there would be a tessellation
27//! wearing the word "certified".
28
29use axiolid_contracts::{GeomError, GeomResult};
30use axiolid_core::{Point3, Scalar};
31use axiolid_curve::{BSplineCurve3, KnotSpec};
32use axiolid_surface::BSplineSurface;
33
34use crate::certified_curve_surface_intersection::{
35    intersect_curve_surface_certified, CertifiedCurveSurfaceIntersection3,
36    CertifiedCurveSurfaceIntersectionOptions,
37};
38use crate::certified_surface_surface_intersection::{
39    intersect_surface_surface_certified, CertifiedSurfaceSurfaceIntersection3,
40    CertifiedSurfaceSurfaceIntersectionOptions, TransverseSurfaceSurfaceTrace3,
41};
42
43/// Why a certified query produced no constructed intersection curve.
44#[non_exhaustive]
45#[derive(Debug, Clone, PartialEq)]
46pub enum IntersectionCurveRefusal {
47    /// The underlying certified query did not resolve every candidate.
48    ///
49    /// Constructing a curve from an incomplete cover would assert an extent
50    /// the search never proved.
51    Unresolved {
52        /// Number of conservative candidate boxes still outstanding.
53        candidates: usize,
54    },
55    /// The inputs are not the exact affine family this construction proves.
56    ///
57    /// A curved intersection has no straight-line proof; emitting a polyline
58    /// would be tessellation, not certification.
59    UnsupportedGeometry,
60    /// The surfaces provably do not meet, so there is no curve to construct.
61    Disjoint,
62}
63
64/// An intersection curve constructed from a certified trace.
65#[derive(Debug, Clone, PartialEq)]
66pub struct ConstructedIntersectionCurve3 {
67    /// The constructed curve in model space.
68    ///
69    /// Exact for the affine family: two planes meet in a straight line, so
70    /// this degree-1 curve IS the intersection, not a sampling of it.
71    pub curve: BSplineCurve3,
72    /// Upper bound on how far the curve departs from either surface.
73    ///
74    /// Valid over the WHOLE curve, not just the endpoints: distance to a plane
75    /// is affine, so its extremes on a segment are attained at the endpoints.
76    pub deviation_upper_bound: Scalar,
77    /// Transversality bound carried over from the certified trace.
78    pub normal_cross_squared_lower_bound: Scalar,
79    /// The trace this curve was constructed from.
80    pub trace: TransverseSurfaceSurfaceTrace3,
81}
82
83/// Construct intersection curves for two clamped NURBS surfaces.
84///
85/// Returns `Ok(Ok(curves))` only when every candidate was resolved AND every
86/// retained trace admits an exact straight-line construction.
87///
88/// A structurally sound refusal is `Ok(Err(..))`: "these surfaces do not meet"
89/// and "this shape is not provable here" are answers about geometry. `Err` is
90/// reserved for invalid input and exhausted budgets.
91pub fn construct_surface_surface_curves(
92    first: &BSplineSurface,
93    second: &BSplineSurface,
94    options: CertifiedSurfaceSurfaceIntersectionOptions,
95) -> GeomResult<Result<Vec<ConstructedIntersectionCurve3>, IntersectionCurveRefusal>> {
96    let traces = match intersect_surface_surface_certified(first, second, options)? {
97        CertifiedSurfaceSurfaceIntersection3::Complete { traces, .. } => traces,
98        // Partial knowledge must not become a confident curve.
99        CertifiedSurfaceSurfaceIntersection3::Unresolved {
100            candidate_boxes, ..
101        } => {
102            return Ok(Err(IntersectionCurveRefusal::Unresolved {
103                candidates: candidate_boxes.len(),
104            }));
105        }
106    };
107
108    // A resolved query with no trace is a PROOF of disjointness, which is a
109    // different fact from "we could not tell" and is named separately.
110    if traces.is_empty() {
111        return Ok(Err(IntersectionCurveRefusal::Disjoint));
112    }
113
114    let mut curves = Vec::new();
115    curves
116        .try_reserve_exact(traces.len())
117        .map_err(|_| GeomError::BudgetExceeded {
118            resource: "constructed intersection curve allocation",
119        })?;
120    for trace in traces {
121        // Every trace must be constructible. Returning the provable subset and
122        // dropping the rest would silently under-report the intersection.
123        let Some(curve) = construct_from_trace(&trace) else {
124            return Ok(Err(IntersectionCurveRefusal::UnsupportedGeometry));
125        };
126        curves.push(curve);
127    }
128    Ok(Ok(curves))
129}
130
131/// Build the exact segment between a trace endpoints.
132///
133/// Returns `None` when the endpoints coincide: a zero-length "curve" would be
134/// a point contact reported as a segment, which downstream booleans would
135/// mistake for an edge.
136fn construct_from_trace(
137    trace: &TransverseSurfaceSurfaceTrace3,
138) -> Option<ConstructedIntersectionCurve3> {
139    let start = trace.start.point;
140    let end = trace.end.point;
141    if !start.is_finite() || !end.is_finite() || start == end {
142        return None;
143    }
144
145    // Affine distance-to-plane means the endpoint residuals bound the segment.
146    let deviation_upper_bound = trace
147        .start
148        .residual_upper_bound
149        .max(trace.end.residual_upper_bound);
150    if !deviation_upper_bound.is_finite() {
151        return None;
152    }
153
154    Some(ConstructedIntersectionCurve3 {
155        curve: segment(start, end),
156        deviation_upper_bound,
157        normal_cross_squared_lower_bound: trace.normal_cross_squared_lower_bound,
158        trace: trace.clone(),
159    })
160}
161
162fn segment(start: Point3, end: Point3) -> BSplineCurve3 {
163    BSplineCurve3 {
164        degree: 1,
165        control_points: vec![start, end],
166        knots: vec![0.0, 1.0],
167        multiplicities: vec![2, 2],
168        weights: None,
169        knot_spec: KnotSpec::PiecewiseBezier,
170        closed: false,
171        self_intersect: Some(false),
172    }
173}
174
175/// A certified curve/surface crossing, reported as a point rather than a curve.
176#[derive(Debug, Clone, Copy, PartialEq)]
177pub struct ConstructedCurveSurfacePoint3 {
178    /// Native curve parameter of the crossing.
179    pub curve_parameter: Scalar,
180    /// Native surface parameters of the crossing.
181    pub surface_parameters: [Scalar; 2],
182    /// Model-space position of the crossing.
183    pub point: Point3,
184}
185
186/// Construct curve/surface intersection points for a clamped NURBS pair.
187///
188/// A transverse curve/surface intersection is ISOLATED: the correct output is
189/// a set of points, and manufacturing a curve through them would invent an
190/// extent nothing proved. A curve arises only when the curve LIES IN the
191/// surface, which is a coincident case this certification does not cover and
192/// which is refused rather than approximated.
193pub fn construct_curve_surface_points(
194    curve: &BSplineCurve3,
195    surface: &BSplineSurface,
196    options: CertifiedCurveSurfaceIntersectionOptions,
197) -> GeomResult<Result<Vec<ConstructedCurveSurfacePoint3>, IntersectionCurveRefusal>> {
198    let intersections = match intersect_curve_surface_certified(curve, surface, options)? {
199        CertifiedCurveSurfaceIntersection3::Complete { intersections, .. } => intersections,
200        CertifiedCurveSurfaceIntersection3::Unresolved {
201            candidate_boxes, ..
202        } => {
203            return Ok(Err(IntersectionCurveRefusal::Unresolved {
204                candidates: candidate_boxes.len(),
205            }));
206        }
207    };
208    if intersections.is_empty() {
209        return Ok(Err(IntersectionCurveRefusal::Disjoint));
210    }
211
212    let mut points = Vec::new();
213    points
214        .try_reserve_exact(intersections.len())
215        .map_err(|_| GeomError::BudgetExceeded {
216            resource: "constructed intersection point allocation",
217        })?;
218    for intersection in intersections {
219        points.push(ConstructedCurveSurfacePoint3 {
220            curve_parameter: midpoint(intersection.curve_parameter),
221            surface_parameters: [
222                midpoint(intersection.surface_u_parameter),
223                midpoint(intersection.surface_v_parameter),
224            ],
225            point: intersection.point,
226        });
227    }
228    Ok(Ok(points))
229}
230
231fn midpoint(interval: crate::certified_projection::ParameterInterval) -> Scalar {
232    interval.start * 0.5 + interval.end * 0.5
233}
axiolid_nurbs/intersection_curve.rs

axiolid_nurbs/
intersection_curve.rs
