axiolid_nurbs/
certified_projection.rs

1//! Public policy and certificate values for exhaustive projection.
2
3use axiolid_contracts::{GeomError, GeomResult};
4use axiolid_core::{Point2, Point3, Scalar, Tolerance};
5
6/// Closed native-parameter interval that may contain a global minimizer.
7#[derive(Debug, Clone, Copy, PartialEq)]
8pub struct ParameterInterval {
9    /// Inclusive lower parameter.
10    pub start: Scalar,
11    /// Inclusive upper parameter.
12    pub end: Scalar,
13}
14
15/// Explicit work and accuracy policy for globally certified projection.
16///
17/// Certification succeeds only when the returned global distance-bound gap is
18/// no larger than `tolerance.linear()`. `max_nodes` independently caps both
19/// pre-search refinement work and generated subdivision cells; pair queries
20/// share one refinement allowance across both input curves. One refinement
21/// work unit is one newly allocated homogeneous-control, expanded-knot, emitted
22/// control, or cell slot. Binary subdivision is also depth-bounded. There is
23/// deliberately no context-free `Default`.
24#[derive(Debug, Clone, Copy, PartialEq)]
25pub struct CertifiedProjectionOptions {
26    tolerance: Tolerance,
27    max_nodes: u32,
28    max_depth: u16,
29}
30
31impl CertifiedProjectionOptions {
32    /// Construct a non-vacuous certification policy.
33    pub fn new(tolerance: Tolerance, max_nodes: u32, max_depth: u16) -> GeomResult<Self> {
34        if max_nodes == 0 || max_depth == 0 {
35            return Err(GeomError::InvalidInput(
36                "certified projection budgets must be non-zero".to_owned(),
37            ));
38        }
39        Ok(Self {
40            tolerance,
41            max_nodes,
42            max_depth,
43        })
44    }
45
46    /// Required upper-minus-lower global distance gap.
47    pub const fn tolerance(self) -> Tolerance {
48        self.tolerance
49    }
50
51    /// Maximum refinement-allocation work units per query phase and maximum
52    /// number of generated search cells. Pair queries share the refinement
53    /// allowance across both curves.
54    pub const fn max_nodes(self) -> u32 {
55        self.max_nodes
56    }
57
58    /// Maximum binary subdivision depth of one Bézier segment.
59    pub const fn max_depth(self) -> u16 {
60        self.max_depth
61    }
62}
63
64/// Maximum accepted shared work budget for certified surface projection.
65pub const MAX_CERTIFIED_SURFACE_PROJECTION_WORK: u32 = 100_000;
66
67/// Maximum accepted binary subdivision depth for certified surface projection.
68pub const MAX_CERTIFIED_SURFACE_PROJECTION_DEPTH: u16 = 64;
69
70/// Explicit accuracy and work policy for globally certified surface projection.
71///
72/// `distance_tolerance` bounds the certified model-space distance gap.
73/// `parameter_tolerance` independently bounds both native parameter widths;
74/// native parameters are not assumed to have model-space units. `max_work`
75/// is one shared cap for Bézier conversion, generated search cells, root and
76/// child patch bounds, patch restriction, and representative enclosure.
77#[derive(Debug, Clone, Copy, PartialEq)]
78pub struct CertifiedSurfaceProjectionOptions {
79    distance_tolerance: Tolerance,
80    parameter_tolerance: Scalar,
81    max_work: u32,
82    max_depth: u16,
83}
84
85impl CertifiedSurfaceProjectionOptions {
86    /// Construct a non-vacuous, hard-capped certification policy.
87    pub fn new(
88        distance_tolerance: Tolerance,
89        parameter_tolerance: Scalar,
90        max_work: u32,
91        max_depth: u16,
92    ) -> GeomResult<Self> {
93        if !parameter_tolerance.is_finite() || parameter_tolerance <= 0.0 {
94            return Err(GeomError::InvalidInput(
95                "surface projection parameter tolerance must be positive and finite".to_owned(),
96            ));
97        }
98        if max_work == 0
99            || max_work > MAX_CERTIFIED_SURFACE_PROJECTION_WORK
100            || max_depth == 0
101            || max_depth > MAX_CERTIFIED_SURFACE_PROJECTION_DEPTH
102        {
103            return Err(GeomError::InvalidInput(format!(
104                "surface projection budgets must be in 1..={MAX_CERTIFIED_SURFACE_PROJECTION_WORK} work units and 1..={MAX_CERTIFIED_SURFACE_PROJECTION_DEPTH} depth"
105            )));
106        }
107        Ok(Self {
108            distance_tolerance,
109            parameter_tolerance,
110            max_work,
111            max_depth,
112        })
113    }
114
115    /// Required outward upper-minus-lower global distance gap.
116    pub const fn distance_tolerance(self) -> Tolerance {
117        self.distance_tolerance
118    }
119
120    /// Required maximum width of each retained native parameter interval.
121    pub const fn parameter_tolerance(self) -> Scalar {
122        self.parameter_tolerance
123    }
124
125    /// Shared conversion, search, restriction, and bound-construction work cap.
126    pub const fn max_work(self) -> u32 {
127        self.max_work
128    }
129
130    /// Maximum binary subdivision depth of one root Bézier patch.
131    pub const fn max_depth(self) -> u16 {
132        self.max_depth
133    }
134}
135
136/// Closed native `(u, v)` box that may contain a global minimizer.
137#[derive(Debug, Clone, Copy, PartialEq)]
138pub struct SurfaceParameterBox {
139    /// Closed native U interval.
140    pub u: ParameterInterval,
141    /// Closed native V interval.
142    pub v: ParameterInterval,
143}
144
145/// Why a valid surface projection remains unresolved without exhausting work.
146#[derive(Debug, Clone, Copy, PartialEq, Eq)]
147pub enum SurfaceProjectionUnresolvedReason {
148    /// At least one surviving candidate reached the configured depth cap.
149    DepthLimit,
150    /// Binary64 midpoint subdivision no longer advances on surviving candidates.
151    FloatingPointNoProgress,
152}
153
154/// Globally bounded closest-point certificate for a spatial surface.
155///
156/// The representative is a deterministic scalar-oracle evaluation. Its exact
157/// binary64 `(u, v)` parameters are also interval-evaluated, and that enclosure
158/// provides `distance_upper_bound`; the scalar `distance` is descriptive and
159/// is not substituted for the outward certificate bound.
160#[derive(Debug, Clone, PartialEq)]
161pub struct SurfaceProjectionCertificate3 {
162    /// Native U parameter of the attained representative.
163    pub u: Scalar,
164    /// Native V parameter of the attained representative.
165    pub v: Scalar,
166    /// Scalar-oracle approximation of the surface point at `(u, v)`.
167    pub point: Point3,
168    /// Euclidean distance of the scalar-oracle representative.
169    pub distance: Scalar,
170    /// Outward lower bound on the global minimum distance.
171    pub distance_lower_bound: Scalar,
172    /// Outward upper bound from evaluating the exact representative parameters.
173    pub distance_upper_bound: Scalar,
174    /// Closed native boxes whose union contains every global minimizer.
175    pub possible_minimizer_boxes: Vec<SurfaceParameterBox>,
176    /// Number of generated search cells, including root patches.
177    pub visited_nodes: u32,
178}
179
180impl SurfaceProjectionCertificate3 {
181    /// Outward-rounded certified global distance gap.
182    pub fn gap(&self) -> Scalar {
183        crate::certified_bezier::next_up(
184            (self.distance_upper_bound - self.distance_lower_bound).max(0.0),
185        )
186    }
187}
188
189/// Exhaustive bounded outcome for spatial surface projection.
190#[derive(Debug, Clone, PartialEq)]
191pub enum CertifiedSurfaceProjection3 {
192    /// All global-distance and native-parameter proof obligations were met.
193    Complete(SurfaceProjectionCertificate3),
194    /// Bounds and candidates remain sound, but the configured depth or floating
195    /// point parameter resolution prevented completion.
196    Unresolved {
197        /// Retained partial global certificate.
198        certificate: SurfaceProjectionCertificate3,
199        /// Exact reason completion stopped.
200        reason: SurfaceProjectionUnresolvedReason,
201    },
202}
203
204/// Globally bounded closest-point result for a planar curve.
205#[derive(Debug, Clone, PartialEq)]
206pub struct CurveProjectionCertificate2 {
207    /// Native parameter of the attained representative candidate.
208    pub parameter: Scalar,
209    /// Scalar-oracle evaluation at `parameter`.
210    pub point: Point2,
211    /// Euclidean distance of the representative scalar evaluation.
212    pub distance: Scalar,
213    /// Conservative lower bound on the global minimum distance.
214    pub distance_lower_bound: Scalar,
215    /// Conservative upper bound attained by the candidate enclosure.
216    pub distance_upper_bound: Scalar,
217    /// Parameter cells not excluded from containing another global minimizer.
218    pub possible_minimizer_intervals: Vec<ParameterInterval>,
219    /// Number of generated Bézier subdivision cells.
220    pub visited_nodes: u32,
221}
222
223impl CurveProjectionCertificate2 {
224    /// Certified global upper-minus-lower distance gap.
225    pub fn gap(&self) -> Scalar {
226        (self.distance_upper_bound - self.distance_lower_bound).max(0.0)
227    }
228}
229
230/// Globally bounded closest-point result for a spatial curve.
231#[derive(Debug, Clone, PartialEq)]
232pub struct CurveProjectionCertificate3 {
233    /// Native parameter of the attained representative candidate.
234    pub parameter: Scalar,
235    /// Scalar-oracle evaluation at `parameter`.
236    pub point: Point3,
237    /// Euclidean distance of the representative scalar evaluation.
238    pub distance: Scalar,
239    /// Conservative lower bound on the global minimum distance.
240    pub distance_lower_bound: Scalar,
241    /// Conservative upper bound attained by the candidate enclosure.
242    pub distance_upper_bound: Scalar,
243    /// Parameter cells not excluded from containing another global minimizer.
244    pub possible_minimizer_intervals: Vec<ParameterInterval>,
245    /// Number of generated Bézier subdivision cells.
246    pub visited_nodes: u32,
247}
248
249impl CurveProjectionCertificate3 {
250    /// Certified global upper-minus-lower distance gap.
251    pub fn gap(&self) -> Scalar {
252        (self.distance_upper_bound - self.distance_lower_bound).max(0.0)
253    }
254}
255
256/// Product-domain box that may contain a globally closest curve pair.
257#[derive(Debug, Clone, Copy, PartialEq)]
258pub struct CurvePairParameterBox {
259    /// Parameter interval on the first curve.
260    pub first: ParameterInterval,
261    /// Parameter interval on the second curve.
262    pub second: ParameterInterval,
263}
264
265/// Globally bounded minimum-distance result for two planar curves.
266#[derive(Debug, Clone, PartialEq)]
267pub struct CurveDistanceCertificate2 {
268    /// Representative parameter on the first curve.
269    pub first_parameter: Scalar,
270    /// Representative parameter on the second curve.
271    pub second_parameter: Scalar,
272    /// Scalar-oracle point on the first curve.
273    pub first_point: Point2,
274    /// Scalar-oracle point on the second curve.
275    pub second_point: Point2,
276    /// Euclidean distance between representative scalar evaluations.
277    pub distance: Scalar,
278    /// Conservative lower bound on the global minimum distance.
279    pub distance_lower_bound: Scalar,
280    /// Conservative upper bound attained by a candidate enclosure.
281    pub distance_upper_bound: Scalar,
282    /// Product cells not excluded from containing another global minimizer.
283    pub possible_minimizer_boxes: Vec<CurvePairParameterBox>,
284    /// Number of generated product cells.
285    pub visited_nodes: u32,
286}
287
288impl CurveDistanceCertificate2 {
289    /// Certified global upper-minus-lower distance gap.
290    pub fn gap(&self) -> Scalar {
291        (self.distance_upper_bound - self.distance_lower_bound).max(0.0)
292    }
293}
294
295/// Globally bounded minimum-distance result for two spatial curves.
296#[derive(Debug, Clone, PartialEq)]
297pub struct CurveDistanceCertificate3 {
298    /// Representative parameter on the first curve.
299    pub first_parameter: Scalar,
300    /// Representative parameter on the second curve.
301    pub second_parameter: Scalar,
302    /// Scalar-oracle point on the first curve.
303    pub first_point: Point3,
304    /// Scalar-oracle point on the second curve.
305    pub second_point: Point3,
306    /// Euclidean distance between representative scalar evaluations.
307    pub distance: Scalar,
308    /// Conservative lower bound on the global minimum distance.
309    pub distance_lower_bound: Scalar,
310    /// Conservative upper bound attained by a candidate enclosure.
311    pub distance_upper_bound: Scalar,
312    /// Product cells not excluded from containing another global minimizer.
313    pub possible_minimizer_boxes: Vec<CurvePairParameterBox>,
314    /// Number of generated product cells.
315    pub visited_nodes: u32,
316}
317
318impl CurveDistanceCertificate3 {
319    /// Certified global upper-minus-lower distance gap.
320    pub fn gap(&self) -> Scalar {
321        (self.distance_upper_bound - self.distance_lower_bound).max(0.0)
322    }
323}
axiolid_nurbs/certified_projection.rs

axiolid_nurbs/
certified_projection.rs
