1use crate::{
2 interpolate_curve, project_point_to_surface, project_point_to_surface_seeded, AnalyticSurface,
3 DiagnosticSeverity, KernelDiagnostics, KernelStage, KnotVector, NurbsCurve, NurbsSurface, Vec3,
4 Vec4, KNOT_IDENTITY_TOL,
5};
6
7const EPSILON: f64 = crate::tolerance::FP_FLOOR;
8const LINEAR_TOLERANCE: f64 = crate::tolerance::DEFAULT_MODEL;
9
10struct PcurvePhaseClock {
12 started: Option<web_time::Instant>,
13 phase: &'static str,
14 samples: usize,
15 tracking: bool,
16}
17impl PcurvePhaseClock {
18 fn new(phase: &'static str, samples: usize, tracking: bool) -> Self {
19 Self { started: crate::profile::profile_enabled().then(web_time::Instant::now), phase, samples, tracking }
20 }
21}
22impl Drop for PcurvePhaseClock {
23 fn drop(&mut self) {
24 if let Some(started) = self.started {
25 crate::imprint::profile_emit(format_args!("pcurve.phase_time phase={} initial_samples={} tracking={} ms={:.3}", self.phase, self.samples, self.tracking, started.elapsed().as_secs_f64()*1000.0));
26 }
27 }
28}
29
30fn surface_domains(surface: &NurbsSurface) -> Result<([f64; 2], [f64; 2]), String> {
31 Ok((
32 KnotVector::new(surface.knots_u.clone(), surface.degree_u)?.domain(),
33 KnotVector::new(surface.knots_v.clone(), surface.degree_v)?.domain(),
34 ))
35}
36
37fn surface_closedness(surface: &NurbsSurface) -> Result<(bool, bool), String> {
44 surface.closed_directions()
45}
46
47thread_local! {
48 static PCURVE_REJECT_BOUNDS: std::cell::Cell<bool> = const { std::cell::Cell::new(false) };
49}
50struct PcurveRejectScope(bool);
51impl PcurveRejectScope {
52 fn open(enabled: bool) -> Self {
53 Self(PCURVE_REJECT_BOUNDS.with(|state| state.replace(enabled)))
54 }
55}
56impl Drop for PcurveRejectScope {
57 fn drop(&mut self) { PCURVE_REJECT_BOUNDS.with(|state| state.set(self.0)); }
58}
59
60thread_local! {
61 static PCURVE_STACK_POINT: std::cell::Cell<bool> = const { std::cell::Cell::new(false) };
62}
63struct PcurveStackPointScope(bool);
64impl PcurveStackPointScope {
65 fn open(enabled: bool) -> Self { Self(PCURVE_STACK_POINT.with(|state| state.replace(enabled))) }
66}
67impl Drop for PcurveStackPointScope {
68 fn drop(&mut self) { PCURVE_STACK_POINT.with(|state| state.set(self.0)); }
69}
70
71#[cfg_attr(feature = "profile-wall", track_caller)]
78fn section_extended_point(surface: &NurbsSurface, u: f64, v: f64, enabled: bool) -> Result<Vec3, String> {
79 let _reader = crate::reader_profile::Point::open(crate::reader_profile::SURFACE, std::panic::Location::caller());
80 let _wall = crate::wall_profile::Scope::enter(crate::wall_profile::POINT);
81 if enabled && u.is_finite() && v.is_finite()
82 && surface.degree_u <= crate::curve::MAX_STACK_DEGREE
83 && surface.degree_v <= crate::curve::MAX_STACK_DEGREE {
84 let [u0,u1] = surface.domain_u()?;
85 let [v0,v1] = surface.domain_v()?;
86 let mut uu = u;
87 let mut vv = v;
88 if u < u0 || u > u1 || v < v0 || v > v1 {
89 let (closed_u, closed_v) = surface_closedness(surface)?;
90 if closed_u && (u < u0 || u > u1) { uu = u0 + (u - u0).rem_euclid(u1 - u0); }
93 if closed_v && (v < v0 || v > v1) { vv = v0 + (v - v0).rem_euclid(v1 - v0); }
94 }
95 if uu >= u0 && uu <= u1 && vv >= v0 && vv <= v1 {
96 let point = surface.evaluate_homogeneous(uu, vv)?;
97 if point.w.abs() <= EPSILON {
98 return Err("NurbsSurface: zero evaluated weight".into());
99 }
100 return Ok(Vec3::new(point.x, point.y, point.z).scale(1.0 / point.w));
101 }
102 }
103 surface.evaluate_extended(u,v)
104}
105
106struct PcurveSampleCache {
109 curve_trace: Option<crate::imprint::reuse_profile::Trace<u64>>,
110 surface_trace: Option<crate::imprint::reuse_profile::Trace<(u64, u64, bool, bool)>>,
111 rollover: bool,
112 point_limit: usize,
113 surface: usize,
114 curve: usize,
115 curves: rustc_hash::FxHashMap<u64, Vec3>,
116 surfaces: rustc_hash::FxHashMap<(u64, u64, bool, bool), Vec3>,
117 inversions: rustc_hash::FxHashMap<[u64; 3], ([f64; 2], f64)>,
118 requests: [usize; 4],
119 hits: [usize; 4],
120 speeds: rustc_hash::FxHashMap<(u64, u64), f64>,
121}
122thread_local! {
123 static PCURVE_SAMPLES: std::cell::RefCell<Vec<Option<PcurveSampleCache>>> = const { std::cell::RefCell::new(Vec::new()) };
124}
125struct PcurveSampleScope<'a>(std::marker::PhantomData<(&'a NurbsSurface, &'a NurbsCurve)>);
126impl<'a> PcurveSampleScope<'a> {
127 fn open(surface: &'a NurbsSurface, curve: &'a NurbsCurve, enabled: bool) -> Self {
128 Self::open_limit(surface, curve, enabled, switch!("BREP_PCURVE_SAMPLE_ROLLOVER", false),
129 if larger_working_set() { 65536 } else { PCURVE_SAMPLE_CACHE_LIMIT })
130 }
131 fn open_config(surface: &'a NurbsSurface, curve: &'a NurbsCurve, enabled: bool, rollover: bool) -> Self {
132 Self::open_limit(surface, curve, enabled, rollover, PCURVE_SAMPLE_CACHE_LIMIT)
133 }
134 fn open_limit(surface: &'a NurbsSurface, curve: &'a NurbsCurve, enabled: bool, rollover: bool, point_limit: usize) -> Self {
135 let cache = enabled
136 .then(|| PcurveSampleCache {
137 curve_trace: crate::imprint::reuse_profile::Trace::open("curve", || serde_json::json!({"curve":curve,"identity":curve as *const _ as usize,"limit":point_limit})),
138 surface_trace: crate::imprint::reuse_profile::Trace::open("surface", || serde_json::json!({"surface":surface,"identity":surface as *const _ as usize,"curve":curve,"limit":point_limit})),
139 rollover, point_limit, surface: surface as *const _ as usize,
140 curve: curve as *const _ as usize, curves: Default::default(),
141 surfaces: Default::default(), inversions: Default::default(), requests: [0; 4], hits: [0; 4], speeds: Default::default() });
142 PCURVE_SAMPLES.with(|stack| stack.borrow_mut().push(cache));
143 Self(std::marker::PhantomData)
144 }
145}
146impl Drop for PcurveSampleScope<'_> {
147 fn drop(&mut self) {
148 PCURVE_SAMPLES.with(|stack| {
149 let _wall = crate::wall_profile::Scope::enter(crate::wall_profile::LOOKUP);
150 if let Some(Some(cache)) = stack.borrow_mut().pop() {
151 if crate::profile::profile_enabled() {
152 profile_line!("pcurve.samples requests={:?} hits={:?} retained={:?}", cache.requests,
153 cache.hits, [cache.curves.len(), cache.surfaces.len(), cache.inversions.len(), cache.speeds.len()]);
154 }
155 }
156 });
157 }
158}
159const PCURVE_SAMPLE_CACHE_LIMIT: usize = 16384;
160
161pub(crate) fn larger_working_set() -> bool {
165 switch!("BREP_PCURVE_WORKING_SET", false)
166}
167
168fn retain_sample<K: std::hash::Hash + Eq, V>(
173 map: &mut rustc_hash::FxHashMap<K, V>, key: K, value: V, rollover: bool, limit: usize,
174) {
175 if rollover && map.len() >= limit { map.clear(); }
176 if map.len() < limit { map.insert(key, value); }
177}
178fn section_u_speed(surface: &NurbsSurface, u: f64, v: f64) -> Result<f64, String> {
179 let key = (u.to_bits(), v.to_bits());
180 let (active, hit) = PCURVE_SAMPLES.with(|stack| {
181 let _wall = crate::wall_profile::Scope::enter(crate::wall_profile::LOOKUP);
182 let mut stack = stack.borrow_mut();
183 let Some(Some(cache)) = stack.last_mut() else { return (false, None) };
184 if cache.surface != surface as *const _ as usize { return (false, None) }
185 cache.requests[3] += 1;
186 let hit = cache.speeds.get(&key).copied();
187 cache.hits[3] += usize::from(hit.is_some());
188 (true, hit)
189 });
190 if let Some(hit) = hit { return Ok(hit) }
191 let speed = surface.deriv1(u, v)?.1.length();
192 if active { PCURVE_SAMPLES.with(|stack| {
193 let _wall = crate::wall_profile::Scope::enter(crate::wall_profile::LOOKUP);
194 let mut stack = stack.borrow_mut();
195 let cache = stack.last_mut().unwrap().as_mut().unwrap();
196 if cache.speeds.len() < PCURVE_SAMPLE_CACHE_LIMIT { cache.speeds.insert(key, speed); }
197 }); }
198 Ok(speed)
199}
200
201#[track_caller]
202fn section_curve_point(curve: &NurbsCurve, parameter: f64) -> Result<Vec3, String> {
203 let caller = std::panic::Location::caller();
204 let key = parameter.to_bits();
205 let (active, hit) = PCURVE_SAMPLES.with(|stack| {
206 let _wall = crate::wall_profile::Scope::enter(crate::wall_profile::LOOKUP);
207 let mut stack = stack.borrow_mut();
208 let Some(Some(cache)) = stack.last_mut() else { return (false, None) };
209 if cache.curve != curve as *const _ as usize { return (false, None) }
210 cache.requests[0] += 1;
211 let hit = cache.curves.get(&key).copied();
212 cache.hits[0] += usize::from(hit.is_some());
213 if hit.is_some() { if let Some(trace) = &mut cache.curve_trace { trace.access(&key, caller, true, true); } }
214 (true, hit)
215 });
216 if let Some(hit) = hit { return Ok(hit) }
217 let result = curve.evaluate(parameter);
218 let point = match result {
219 Ok(point) => point,
220 Err(error) => {
221 if active { PCURVE_SAMPLES.with(|stack| {
222 let _wall = crate::wall_profile::Scope::enter(crate::wall_profile::LOOKUP); if let Some(trace) = &mut stack.borrow_mut().last_mut().unwrap().as_mut().unwrap().curve_trace {
223 trace.access(&key, caller, false, false);
224 } }); }
225 return Err(error);
226 }
227 };
228 if active { PCURVE_SAMPLES.with(|stack| {
229 let _wall = crate::wall_profile::Scope::enter(crate::wall_profile::LOOKUP);
230 let mut stack = stack.borrow_mut();
231 let cache = stack.last_mut().unwrap().as_mut().unwrap();
232 if let Some(trace) = &mut cache.curve_trace { trace.access(&key, caller, false, true); }
233 retain_sample(&mut cache.curves, key, point, cache.rollover, cache.point_limit);
234 }); }
235 Ok(point)
236}
237#[track_caller]
238fn section_surface_point(surface: &NurbsSurface, u: f64, v: f64, extended: bool) -> Result<Vec3, String> {
239 let caller = std::panic::Location::caller();
240 let stack_point = PCURVE_STACK_POINT.with(|state| state.get());
243 let key = (u.to_bits(), v.to_bits(), extended, stack_point);
244 let (active, hit) = PCURVE_SAMPLES.with(|stack| {
245 let _wall = crate::wall_profile::Scope::enter(crate::wall_profile::LOOKUP);
246 let mut stack = stack.borrow_mut();
247 let Some(Some(cache)) = stack.last_mut() else { return (false, None) };
248 if cache.surface != surface as *const _ as usize { return (false, None) }
249 cache.requests[1] += 1;
250 let hit = cache.surfaces.get(&key).copied();
251 cache.hits[1] += usize::from(hit.is_some());
252 if hit.is_some() { if let Some(trace) = &mut cache.surface_trace { trace.access(&key, caller, true, true); } }
253 (true, hit)
254 });
255 if let Some(hit) = hit { return Ok(hit) }
256 let result = if extended { section_extended_point(surface, u, v, stack_point) } else { surface.evaluate(u, v) };
257 let point = match result {
258 Ok(point) => point,
259 Err(error) => {
260 if active { PCURVE_SAMPLES.with(|stack| {
261 let _wall = crate::wall_profile::Scope::enter(crate::wall_profile::LOOKUP); if let Some(trace) = &mut stack.borrow_mut().last_mut().unwrap().as_mut().unwrap().surface_trace {
262 trace.access(&key, caller, false, false);
263 } }); }
264 return Err(error);
265 }
266 };
267 if active { PCURVE_SAMPLES.with(|stack| {
268 let _wall = crate::wall_profile::Scope::enter(crate::wall_profile::LOOKUP);
269 let mut stack = stack.borrow_mut();
270 let cache = stack.last_mut().unwrap().as_mut().unwrap();
271 if let Some(trace) = &mut cache.surface_trace { trace.access(&key, caller, false, true); }
272 retain_sample(&mut cache.surfaces, key, point, cache.rollover, cache.point_limit);
273 }); }
274 Ok(point)
275}
276fn invert_checked(surface: &NurbsSurface, point: Vec3) -> Result<([f64; 2], f64), String> {
277 let key = [point.x.to_bits(), point.y.to_bits(), point.z.to_bits()];
278 let (active, hit) = PCURVE_SAMPLES.with(|stack| {
279 let _wall = crate::wall_profile::Scope::enter(crate::wall_profile::LOOKUP);
280 let mut stack = stack.borrow_mut();
281 let Some(Some(cache)) = stack.last_mut() else { return (false, None) };
282 if cache.surface != surface as *const _ as usize { return (false, None) }
283 cache.requests[2] += 1;
284 let hit = cache.inversions.get(&key).copied();
285 cache.hits[2] += usize::from(hit.is_some());
286 (true, hit)
287 });
288 if let Some(hit) = hit { return Ok(hit) }
289 let projection = invert_checked_uncached(surface, point)?;
290 if active { PCURVE_SAMPLES.with(|stack| {
291 let _wall = crate::wall_profile::Scope::enter(crate::wall_profile::LOOKUP);
292 let mut stack = stack.borrow_mut();
293 let cache = stack.last_mut().unwrap().as_mut().unwrap();
294 if cache.inversions.len() < PCURVE_SAMPLE_CACHE_LIMIT { cache.inversions.insert(key, projection); }
295 }); }
296 Ok(projection)
297}
298
299fn invert_checked_uncached(surface: &NurbsSurface, point: Vec3) -> Result<([f64; 2], f64), String> {
300 let _lap = crate::projection_profile::Lap::enter(crate::projection_profile::LANE_INVERT_CHECKED, surface);
301 if surface.is_affine()? {
302 let ([u0, _], [v0, _]) = surface_domains(surface)?;
303 let (origin, du, dv) = surface.deriv1(u0, v0)?;
304 let delta = point.sub(origin);
305 let uu = du.dot(du);
306 let uv = du.dot(dv);
307 let vv = dv.dot(dv);
308 let along_u = delta.dot(du);
309 let along_v = delta.dot(dv);
310 let determinant = uu * vv - uv * uv;
311 if determinant.abs() > EPSILON {
312 let parameter = [
313 u0 + (along_u * vv - along_v * uv) / determinant,
314 v0 + (along_v * uu - along_u * uv) / determinant,
315 ];
316 let foot = origin.add(du.scale(parameter[0] - u0)).add(dv.scale(parameter[1] - v0));
320 return Ok((parameter, point.sub(foot).length()));
321 }
322 }
323 let projection = project_point_to_surface(surface, point)?;
324 Ok(([projection.u, projection.v], projection.distance))
325}
326
327fn cone_apex_u() -> bool {
332 switch!("BREP_PCURVE_CONE_APEX_U", true)
333}
334
335fn worst_first() -> bool {
339 switch!("BREP_PCURVE_WORST_FIRST", true)
340}
341
342fn c0_joins() -> bool {
346 switch!("BREP_PCURVE_C0_JOIN", true)
347}
348
349fn seeded_inserts() -> bool {
350 switch!("BREP_PCURVE_SEEDED_INSERTS", true)
351}
352
353fn invert_near(
363 surface: &NurbsSurface,
364 point: Vec3,
365 seed: [f64; 2],
366 neighbour_gap: f64,
367) -> Result<([f64; 2], f64), String> {
368 if !seeded_inserts() || surface.is_affine()? || surface.analytic().is_some() || surface.affine_sphere().is_some() {
369 return invert_checked(surface, point);
370 }
371 let seeded = project_point_to_surface_seeded(surface, point, seed[0], seed[1])?;
372 if seeded.distance <= neighbour_gap + PCURVE_REFINEMENT_TOLERANCE {
373 return Ok(([seeded.u, seeded.v], seeded.distance));
374 }
375 invert_checked(surface, point)
376}
377
378fn unwrap_periodic(values: &mut [f64], minimum: f64, maximum: f64) {
379 let period = maximum - minimum;
380 for index in 1..values.len() {
381 while values[index] - values[index - 1] > period / 2.0 {
382 values[index] -= period;
383 }
384 while values[index] - values[index - 1] < -period / 2.0 {
385 values[index] += period;
386 }
387 }
388 if values.len() > 1 {
389 while values[0] - values[1] > period / 2.0 {
390 values[0] -= period;
391 }
392 while values[0] - values[1] < -period / 2.0 {
393 values[0] += period;
394 }
395 }
396 if values.len() > 1 {
406 let excursion = |shift: f64| -> f64 {
407 values
408 .iter()
409 .map(|value| {
410 let v = value + shift;
411 (minimum - v).max(0.0) + (v - maximum).max(0.0)
412 })
413 .sum::<f64>()
414 };
415 let mean = values.iter().copied().sum::<f64>() / values.len() as f64;
416 let center = 0.5 * (minimum + maximum);
417 let base_k = ((center - mean) / period).round() as i64;
418 let mut best_shift = 0.0;
419 let mut best_excursion = f64::INFINITY;
420 for k in (base_k - 1)..=(base_k + 1) {
421 let shift = k as f64 * period;
422 let value = excursion(shift);
423 if value < best_excursion {
424 best_excursion = value;
425 best_shift = shift;
426 }
427 }
428 if best_shift != 0.0 {
429 for value in values.iter_mut() {
430 *value += best_shift;
431 }
432 }
433 }
434}
435
436fn build_interpolant(
442 surface: &NurbsSurface,
443 raw_parameters: &[[f64; 2]],
444 curve_parameters: &[f64],
445) -> Result<(NurbsCurve, f64, f64), String> {
446 build_interpolant_joined(surface, raw_parameters, curve_parameters, &[])
447}
448
449fn build_interpolant_joined(
463 surface: &NurbsSurface,
464 raw_parameters: &[[f64; 2]],
465 curve_parameters: &[f64],
466 joins: &[f64],
467) -> Result<(NurbsCurve, f64, f64), String> {
468 let _clock = PcurvePhaseClock::new("interpolant", raw_parameters.len(), false);
469 let ([u0, u1], [v0, v1]) = surface_domains(surface)?;
470 let (closed_u, closed_v) = surface_closedness(surface)?;
471 let mut parameters = raw_parameters.to_vec();
472 if cone_apex_u() && matches!(surface.analytic(), Some(AnalyticSurface::RuledRevolution { .. })) && parameters.len() >= 2 {
482 let speeds = parameters
483 .iter()
484 .map(|parameter| section_u_speed(surface, parameter[0], parameter[1]))
485 .collect::<Result<Vec<_>, _>>()?;
486 let reference = speeds.iter().copied().fold(0.0_f64, f64::max);
487 let singular = |index: usize| speeds[index] <= reference * 1e-2;
488 if let (Some(first), Some(last)) = (
489 (0..parameters.len()).find(|&index| !singular(index)),
490 (0..parameters.len()).rfind(|&index| !singular(index)),
491 ) {
492 for index in 0..first {
493 parameters[index][0] = parameters[first][0];
494 }
495 for index in last + 1..parameters.len() {
496 parameters[index][0] = parameters[last][0];
497 }
498 }
499 }
500 let sphere_u_singular = if matches!(surface.analytic(), Some(AnalyticSurface::Sphere { .. })) {
512 let speeds = parameters
513 .iter()
514 .map(|parameter| {
515 section_u_speed(surface, parameter[0], parameter[1])
516 })
517 .collect::<Result<Vec<_>, _>>()?;
518 let reference = speeds.iter().copied().fold(0.0_f64, f64::max);
519 speeds
520 .into_iter()
521 .map(|speed| speed <= reference * 1e-2)
526 .collect::<Vec<_>>()
527 } else {
528 vec![false; parameters.len()]
529 };
530 let has_interior_pole_crossing = sphere_u_singular
538 .iter()
539 .position(|singular| !singular)
540 .zip(sphere_u_singular.iter().rposition(|singular| !singular))
541 .is_some_and(|(first, last)| sphere_u_singular[first..=last].iter().any(|value| *value));
542 let period = (u1 - u0).abs();
543 let interior_pole_branch_reset = closed_u
544 && has_interior_pole_crossing
545 && parameters.windows(2).zip(sphere_u_singular.windows(2)).any(
546 |(parameter_pair, singular_pair)| {
547 (singular_pair[0] || singular_pair[1])
548 && (parameter_pair[1][0] - parameter_pair[0][0]).abs()
549 >= 0.5 * period - 1e-12 * period.max(1.0)
550 },
551 );
552 if closed_u {
553 let mut values = parameters.iter().map(|value| value[0]).collect::<Vec<_>>();
554 if interior_pole_branch_reset {
555 let mut start = 0;
556 while start < values.len() {
557 while start < values.len() && sphere_u_singular[start] {
558 start += 1;
559 }
560 let mut end = start;
561 while end < values.len() && !sphere_u_singular[end] {
562 end += 1;
563 }
564 unwrap_periodic(&mut values[start..end], u0, u1);
565 start = end;
566 }
567 } else {
568 unwrap_periodic(&mut values, u0, u1);
569 }
570 for (parameter, value) in parameters.iter_mut().zip(values) {
571 parameter[0] = value;
572 }
573 }
574 if closed_v {
575 let mut values = parameters.iter().map(|value| value[1]).collect::<Vec<_>>();
576 unwrap_periodic(&mut values, v0, v1);
577 for (parameter, value) in parameters.iter_mut().zip(values) {
578 parameter[1] = value;
579 }
580 }
581 let mut excursion = 0.0_f64;
598 let mut distance = 0.0_f64;
599 let mut points = Vec::with_capacity(parameters.len());
600 for parameter in parameters {
601 let u = if closed_u {
602 parameter[0]
603 } else {
604 parameter[0].clamp(u0, u1)
605 };
606 let v = if closed_v {
607 parameter[1]
608 } else {
609 parameter[1].clamp(v0, v1)
610 };
611 let pulled = ((parameter[0] - u).powi(2) + (parameter[1] - v).powi(2)).sqrt();
612 if pulled > 0.0 {
613 excursion = excursion.max(pulled);
614 let extended = surface.evaluate_extended(parameter[0], parameter[1])?;
615 distance = distance.max(extended.sub(surface.evaluate(u, v)?).length());
616 }
617 points.push(Vec3::new(u, v, 0.0));
618 }
619 let degree = 3usize.min(points.len() - 1);
620 let mut bounds: Vec<usize> = joins
621 .iter()
622 .filter_map(|join| curve_parameters.iter().position(|parameter| parameter == join))
623 .filter(|&index| index > 0 && index + 1 < curve_parameters.len())
624 .collect();
625 bounds.sort_unstable();
626 bounds.dedup();
627 if degree < 3 || bounds.is_empty() || !c0_joins() {
628 let curve = interpolate_curve(&points, degree, curve_parameters)?;
629 return Ok((curve, excursion, distance));
630 }
631 let mut pieces = vec![0usize];
634 for bound in bounds {
635 if bound + 1 - pieces[pieces.len() - 1] >= 4 {
636 pieces.push(bound);
637 }
638 }
639 if curve_parameters.len() - pieces[pieces.len() - 1] < 4 {
640 pieces.pop();
641 }
642 pieces.push(curve_parameters.len() - 1);
643 if pieces.len() < 3 {
644 let curve = interpolate_curve(&points, degree, curve_parameters)?;
645 return Ok((curve, excursion, distance));
646 }
647 let mut knots: Vec<f64> = Vec::with_capacity(curve_parameters.len() + 4);
648 let mut control: Vec<Vec4> = Vec::with_capacity(curve_parameters.len());
649 let last_piece = pieces.len() - 2;
650 for piece in 0..=last_piece {
651 let (from, to) = (pieces[piece], pieces[piece + 1]);
652 let fitted = interpolate_curve(&points[from..=to], 3, &curve_parameters[from..=to])?;
653 if piece == 0 {
654 knots.extend(fitted.knots[..4].iter().copied());
655 }
656 knots.extend(fitted.knots[4..fitted.knots.len() - 4].iter().copied());
657 let multiplicity = if piece == last_piece { 4 } else { 3 };
658 knots.extend(std::iter::repeat(curve_parameters[to]).take(multiplicity));
659 control.extend(fitted.control_points.iter().skip(usize::from(piece > 0)).copied());
660 }
661 let curve = NurbsCurve::new(3, knots, control)?;
662 Ok((curve, excursion, distance))
663}
664
665pub const PCURVE_REFINEMENT_TOLERANCE: f64 = 1e-7;
713
714const MAX_PCURVE_SAMPLES: usize = 600;
730
731const PCURVE_RAISED_SAMPLES: usize = 2000;
737
738#[derive(Clone, Copy, Debug, PartialEq)]
751pub struct PcurveFitReport {
752 pub residual: f64,
759 pub floor: f64,
761 pub samples: usize,
763 pub exit: PcurveFitExit,
765 pub off_surface: f64,
772 pub raised: bool,
775 pub clamped_excursion: f64,
792 pub clamped_distance: f64,
796}
797
798impl PcurveFitReport {
799 pub fn met_floor(&self) -> bool {
801 self.residual <= self.floor
802 }
803
804 pub fn on_bar(&self) -> bool {
819 self.residual <= self.floor + self.off_surface
820 }
821}
822
823#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
827pub enum PcurveFitExit {
828 Converged,
831 SampleCeiling,
836 RoundBudget,
839 Stalled,
849 SpanFloor,
858}
859
860#[derive(Clone, Debug)]
862pub struct PcurveFit {
863 pub curve: NurbsCurve,
864 pub report: PcurveFitReport,
865}
866
867#[derive(Clone, Copy, Debug, Default, PartialEq)]
887pub struct PcurveFitLedger {
888 pub fits: u64,
890 pub unmet: u64,
892 pub sample_ceiling: u64,
894 pub round_budget: u64,
896 pub stalled: u64,
898 pub span_floor: u64,
901 pub worst_unmet_residual: f64,
903 pub raised: u64,
906 pub raise_declined: u64,
909 pub worst_off_surface: f64,
911 pub clamped: u64,
914 pub worst_clamped_excursion: f64,
916 pub worst_clamped_distance: f64,
918}
919
920impl PcurveFitLedger {
921 fn record(&mut self, report: &PcurveFitReport) {
922 self.fits += 1;
923 if report.raised {
924 self.raised += 1;
925 }
926 self.worst_off_surface = self.worst_off_surface.max(report.off_surface);
927 if report.clamped_excursion > 0.0 {
928 self.clamped += 1;
929 self.worst_clamped_excursion = self.worst_clamped_excursion.max(report.clamped_excursion);
930 self.worst_clamped_distance = self.worst_clamped_distance.max(report.clamped_distance);
931 }
932 if report.met_floor() {
933 return;
934 }
935 self.unmet += 1;
936 match report.exit {
937 PcurveFitExit::Converged => {}
938 PcurveFitExit::SampleCeiling => {
939 self.sample_ceiling += 1;
940 if !report.raised {
941 self.raise_declined += 1;
942 }
943 }
944 PcurveFitExit::RoundBudget => self.round_budget += 1,
945 PcurveFitExit::Stalled => self.stalled += 1,
946 PcurveFitExit::SpanFloor => self.span_floor += 1,
947 }
948 self.worst_unmet_residual = self.worst_unmet_residual.max(report.residual);
949 }
950
951 fn fold(&mut self, child: &PcurveFitLedger) {
952 self.fits += child.fits;
953 self.unmet += child.unmet;
954 self.sample_ceiling += child.sample_ceiling;
955 self.round_budget += child.round_budget;
956 self.stalled += child.stalled;
957 self.span_floor += child.span_floor;
958 self.worst_unmet_residual = self.worst_unmet_residual.max(child.worst_unmet_residual);
959 self.raised += child.raised;
960 self.raise_declined += child.raise_declined;
961 self.worst_off_surface = self.worst_off_surface.max(child.worst_off_surface);
962 self.clamped += child.clamped;
963 self.worst_clamped_excursion = self.worst_clamped_excursion.max(child.worst_clamped_excursion);
964 self.worst_clamped_distance = self.worst_clamped_distance.max(child.worst_clamped_distance);
965 }
966
967 pub fn report_into(&self, diagnostics: &mut KernelDiagnostics) {
973 diagnostics.count_n("pcurve.fits", self.fits);
974 diagnostics.count_n("pcurve.unmet_floor", self.unmet);
975 diagnostics.count_n("pcurve.exit.sample_ceiling", self.sample_ceiling);
976 diagnostics.count_n("pcurve.exit.round_budget", self.round_budget);
977 diagnostics.count_n("pcurve.exit.stalled", self.stalled);
978 diagnostics.count_n("pcurve.exit.span_floor", self.span_floor);
979 diagnostics.count_n("pcurve.budget_raised", self.raised);
980 diagnostics.count_n("pcurve.budget_raise_declined", self.raise_declined);
981 diagnostics.measure_max("pcurve.worst_unmet_residual", self.worst_unmet_residual);
982 diagnostics.measure_max("pcurve.worst_off_surface", self.worst_off_surface);
983 diagnostics.count_n("pcurve.clamped", self.clamped);
984 diagnostics.measure_max("pcurve.worst_clamped_excursion", self.worst_clamped_excursion);
985 diagnostics.measure_max("pcurve.worst_clamped_distance", self.worst_clamped_distance);
986 if self.unmet > 0 {
987 diagnostics.event(
988 DiagnosticSeverity::Degraded,
989 KernelStage::Refine,
990 "pcurve.unmet_floor",
991 format!(
992 "{} of {} pcurve fits did not reach the {:.0e} floor \
993 (sample ceiling {}, round budget {}, stalled {}, span floor {}); \
994 worst residual {:.3e}; budget raised on {}, declined on {}; \
995 edge curves sit off their surfaces by up to {:.3e}{}",
996 self.unmet,
997 self.fits,
998 PCURVE_REFINEMENT_TOLERANCE,
999 self.sample_ceiling,
1000 self.round_budget,
1001 self.stalled,
1002 self.span_floor,
1003 self.worst_unmet_residual,
1004 self.raised,
1005 self.raise_declined,
1006 self.worst_off_surface,
1007 if self.clamped > 0 {
1008 format!(
1009 "; {} fit(s) clamped into their chart by up to {:.3e} in parameter, {:.3e} in 3D",
1010 self.clamped, self.worst_clamped_excursion, self.worst_clamped_distance
1011 )
1012 } else {
1013 String::new()
1014 },
1015 ),
1016 );
1017 }
1018 }
1019}
1020
1021thread_local! {
1022 static FOOT_MEMO: std::cell::RefCell<Option<FootMemo>> = const { std::cell::RefCell::new(None) };
1024}
1025
1026struct FootMemo {
1045 surface: *const NurbsSurface,
1046 global: rustc_hash::FxHashMap<[u64; 3], Option<crate::SurfaceProjection>>,
1047 seeded: rustc_hash::FxHashMap<[u64; 5], Option<crate::SurfaceProjection>>,
1048 pending_global: Vec<([u64; 3], Option<crate::SurfaceProjection>)>,
1049 pending_seeded: Vec<([u64; 5], Option<crate::SurfaceProjection>)>,
1050}
1051
1052impl FootMemo {
1053 fn new(surface: *const NurbsSurface) -> Self {
1054 Self { surface, global: Default::default(), seeded: Default::default(), pending_global: Vec::new(), pending_seeded: Vec::new() }
1055 }
1056
1057 fn fold_pending(&mut self) {
1060 if !self.pending_global.is_empty() {
1061 self.global.reserve(self.pending_global.len());
1062 self.global.extend(self.pending_global.drain(..));
1063 }
1064 if !self.pending_seeded.is_empty() {
1065 self.seeded.reserve(self.pending_seeded.len());
1066 self.seeded.extend(self.pending_seeded.drain(..));
1067 }
1068 }
1069}
1070
1071thread_local! {
1072 static DEFER_FOOT_INSERTS: std::cell::Cell<bool> = const { std::cell::Cell::new(false) };
1073}
1074
1075pub(crate) fn defer_foot_inserts<T>(read: impl FnOnce() -> T) -> T {
1078 let previous = DEFER_FOOT_INSERTS.with(|cell| cell.replace(true));
1079 let result = read();
1080 DEFER_FOOT_INSERTS.with(|cell| cell.set(previous));
1081 result
1082}
1083
1084pub(crate) struct FootMemoScope<'a> {
1091 previous: Option<Option<FootMemo>>,
1092 _surface: std::marker::PhantomData<&'a NurbsSurface>,
1093 _thread_bound: std::marker::PhantomData<*const ()>,
1095}
1096
1097impl<'a> FootMemoScope<'a> {
1098 pub(crate) fn open(surface: &'a NurbsSurface) -> Self {
1099 let key = surface as *const NurbsSurface;
1100 let previous = FOOT_MEMO.with(|memo| {
1101 let _wall = crate::wall_profile::Scope::enter(crate::wall_profile::LOOKUP);
1102 let mut memo = memo.borrow_mut();
1103 if memo.as_ref().is_some_and(|open| std::ptr::eq(open.surface, key)) {
1104 None
1105 } else {
1106 Some(memo.replace(FootMemo::new(key)))
1107 }
1108 });
1109 Self { previous, _surface: std::marker::PhantomData, _thread_bound: std::marker::PhantomData }
1110 }
1111}
1112
1113impl Drop for FootMemoScope<'_> {
1114 fn drop(&mut self) {
1115 if let Some(previous) = self.previous.take() {
1116 FOOT_MEMO.with(|memo| *memo.borrow_mut() = previous);
1117 }
1118 }
1119}
1120
1121fn point_bits(point: Vec3) -> [u64; 3] {
1122 [point.x.to_bits(), point.y.to_bits(), point.z.to_bits()]
1123}
1124
1125#[track_caller]
1131fn memo_global_foot(surface: &NurbsSurface, point: Vec3) -> Option<crate::SurfaceProjection> {
1132 if crate::projection::global_site_filter_active() {
1133 return project_point_to_surface(surface, point).ok();
1134 }
1135 let key = point_bits(point);
1136 let deferring = DEFER_FOOT_INSERTS.with(|cell| cell.get());
1137 let hit = FOOT_MEMO.with(|memo| {
1138 let _wall = crate::wall_profile::Scope::enter(crate::wall_profile::LOOKUP);
1139 memo.borrow_mut().as_mut().filter(|open| std::ptr::eq(open.surface, surface)).map(|open| {
1140 match open.global.get(&key).copied() {
1141 Some(foot) => Some(foot),
1142 None if !deferring && !open.pending_global.is_empty() => {
1143 open.fold_pending();
1144 open.global.get(&key).copied()
1145 }
1146 None => None,
1147 }
1148 })
1149 });
1150 match hit {
1151 Some(Some(foot)) => foot,
1152 Some(None) => {
1153 let foot = project_point_to_surface(surface, point).ok();
1154 FOOT_MEMO.with(|memo| {
1155 let _wall = crate::wall_profile::Scope::enter(crate::wall_profile::LOOKUP);
1156 if let Some(open) = memo.borrow_mut().as_mut().filter(|open| std::ptr::eq(open.surface, surface)) {
1157 if deferring {
1158 open.pending_global.push((key, foot));
1159 } else {
1160 open.global.insert(key, foot);
1161 }
1162 }
1163 });
1164 foot
1165 }
1166 None => project_point_to_surface(surface, point).ok(),
1167 }
1168}
1169
1170fn memo_seeded_foot(surface: &NurbsSurface, point: Vec3, seed_u: f64, seed_v: f64) -> Option<crate::SurfaceProjection> {
1173 let [x, y, z] = point_bits(point);
1174 let key = [x, y, z, seed_u.to_bits(), seed_v.to_bits()];
1175 let deferring = DEFER_FOOT_INSERTS.with(|cell| cell.get());
1176 let hit = FOOT_MEMO.with(|memo| {
1177 let _wall = crate::wall_profile::Scope::enter(crate::wall_profile::LOOKUP);
1178 memo.borrow_mut().as_mut().filter(|open| std::ptr::eq(open.surface, surface)).map(|open| {
1179 match open.seeded.get(&key).copied() {
1180 Some(foot) => Some(foot),
1181 None if !deferring && !open.pending_seeded.is_empty() => {
1182 open.fold_pending();
1183 open.seeded.get(&key).copied()
1184 }
1185 None => None,
1186 }
1187 })
1188 });
1189 match hit {
1190 Some(Some(foot)) => foot,
1191 Some(None) => {
1192 let foot = project_point_to_surface_seeded(surface, point, seed_u, seed_v).ok();
1193 FOOT_MEMO.with(|memo| {
1194 let _wall = crate::wall_profile::Scope::enter(crate::wall_profile::LOOKUP);
1195 if let Some(open) = memo.borrow_mut().as_mut().filter(|open| std::ptr::eq(open.surface, surface)) {
1196 if deferring {
1197 open.pending_seeded.push((key, foot));
1198 } else {
1199 open.seeded.insert(key, foot);
1200 }
1201 }
1202 });
1203 foot
1204 }
1205 None => project_point_to_surface_seeded(surface, point, seed_u, seed_v).ok(),
1206 }
1207}
1208
1209thread_local! {
1210 static PCURVE_FIT_SCOPES: std::cell::RefCell<Vec<PcurveFitLedger>> =
1212 const { std::cell::RefCell::new(Vec::new()) };
1213}
1214
1215static PCURVE_TRACK_CALL: std::sync::atomic::AtomicU64 = std::sync::atomic::AtomicU64::new(0);
1219
1220pub struct PcurveFitScope {
1227 _thread_bound: std::marker::PhantomData<*const ()>,
1229}
1230
1231impl PcurveFitScope {
1232 pub fn open() -> Self {
1233 PCURVE_FIT_SCOPES.with(|scopes| scopes.borrow_mut().push(PcurveFitLedger::default()));
1234 Self {
1235 _thread_bound: std::marker::PhantomData,
1236 }
1237 }
1238
1239 pub fn close(self) -> PcurveFitLedger {
1241 let ledger = PCURVE_FIT_SCOPES.with(|scopes| {
1242 let mut scopes = scopes.borrow_mut();
1243 let ledger = scopes.pop().unwrap_or_default();
1244 if let Some(parent) = scopes.last_mut() {
1245 parent.fold(&ledger);
1246 }
1247 ledger
1248 });
1249 std::mem::forget(self);
1250 ledger
1251 }
1252}
1253
1254impl Drop for PcurveFitScope {
1255 fn drop(&mut self) {
1256 PCURVE_FIT_SCOPES.with(|scopes| {
1257 scopes.borrow_mut().pop();
1258 });
1259 }
1260}
1261
1262pub(crate) fn record_fit(report: &PcurveFitReport) {
1263 crate::imprint::work_profile::add(|c| { c.fit_reports += 1; c.fit_samples += report.samples as u64; c.fit_raised += u64::from(report.raised); });
1264 if env_read!("BREP_DEBUG_PCURVE_FIT").is_some() {
1268 eprintln!("PCURVE-FIT {report:?}");
1269 }
1270 PCURVE_FIT_SCOPES.with(|scopes| {
1271 if let Some(open) = scopes.borrow_mut().last_mut() {
1272 open.record(report);
1273 }
1274 });
1275}
1276
1277fn probe_residual(
1282 surface: &NurbsSurface,
1283 curve: &NurbsCurve,
1284 pcurve: &NurbsCurve,
1285 parameters: &[f64],
1286 domain: [f64; 2],
1287 _u_domain: [f64; 2],
1288 _v_domain: [f64; 2],
1289) -> Result<f64, String> {
1290 probe_residual_at(surface, curve, pcurve, parameters, domain, &[0.25, 0.5, 0.75])
1291}
1292
1293const TRACKING_ACCEPTANCE_POINTS: usize = 16;
1302
1303struct ProbeCurveReader<'a> {
1308 curve: &'a NurbsCurve,
1309 enabled: bool,
1310 domain: Option<[f64; 2]>,
1311 span: Option<usize>,
1312 previous: Option<u64>,
1313 basis: [f64; crate::curve::MAX_STACK_ORDER],
1314 left: [f64; crate::curve::MAX_STACK_ORDER],
1315 right: [f64; crate::curve::MAX_STACK_ORDER],
1316}
1317impl<'a> ProbeCurveReader<'a> {
1318 fn new(curve: &'a NurbsCurve, enabled: bool) -> Self {
1319 Self { curve, enabled, domain: None, span: None, previous: None,
1320 basis: [0.0; crate::curve::MAX_STACK_ORDER],
1321 left: [0.0; crate::curve::MAX_STACK_ORDER], right: [0.0; crate::curve::MAX_STACK_ORDER] }
1322 }
1323 #[cfg_attr(feature = "profile-wall", track_caller)]
1324 fn evaluate(&mut self, parameter: f64) -> Result<Vec3, String> {
1325 let _reader = crate::reader_profile::Point::open(crate::reader_profile::PCURVE, std::panic::Location::caller());
1326 if !self.enabled || self.curve.degree > crate::curve::MAX_STACK_DEGREE || !parameter.is_finite() {
1327 return self.curve.evaluate(parameter);
1328 }
1329 let _wall = crate::wall_profile::Scope::enter(crate::wall_profile::POINT);
1330 let [start, end] = match self.domain {
1331 Some(domain) => domain,
1332 None => {
1333 let domain = self.curve.domain()?;
1334 if self.curve.knots.windows(2).any(|w| w[1] < w[0]) {
1337 self.enabled = false;
1338 return self.curve.evaluate(parameter);
1339 }
1340 self.domain = Some(domain); domain
1341 }
1342 };
1343 let parameter = parameter.clamp(start, end);
1344 if self.previous != Some(parameter.to_bits()) {
1345 let knots = &self.curve.knots;
1346 let degree = self.curve.degree;
1347 let span = match self.span {
1348 Some(mut span) if parameter > start && parameter < end && parameter >= knots[span] => {
1349 while parameter >= knots[span + 1] { span += 1; }
1350 span
1351 }
1352 _ => crate::curve::knot_find_span(knots, degree, parameter),
1353 };
1354 match degree {
1358 1 => self.fill_basis::<1>(span, parameter),
1359 2 => self.fill_basis::<2>(span, parameter),
1360 3 => self.fill_basis::<3>(span, parameter),
1361 4 => self.fill_basis::<4>(span, parameter),
1362 5 => self.fill_basis::<5>(span, parameter),
1363 6 => self.fill_basis::<6>(span, parameter),
1364 7 => self.fill_basis::<7>(span, parameter),
1365 _ => self.fill_basis::<0>(span, parameter),
1366 }
1367 self.span = Some(span);
1368 self.previous = Some(parameter.to_bits());
1369 }
1370 let span = self.span.unwrap();
1371 let _reader_part = crate::reader_profile::Part::open(crate::reader_profile::ACCUMULATE);
1372 let mut point = Vec4 { x: 0.0, y: 0.0, z: 0.0, w: 0.0 };
1373 for (index, value) in self.basis[..=self.curve.degree].iter().enumerate() {
1374 point = point.add(self.curve.control_points[span - self.curve.degree + index].scale(*value));
1375 }
1376 point.point()
1377 }
1378 #[inline(always)]
1379 fn fill_basis<const DEGREE: usize>(&mut self, span: usize, parameter: f64) {
1380 crate::curve::basis_functions_raw_into(&self.curve.knots, DEGREE, span, parameter,
1381 EPSILON, &mut self.basis, &mut self.left, &mut self.right);
1382 }
1383}
1384
1385fn probe_batch_enabled() -> bool { switch!("BREP_PCURVE_PROBE_BATCH", false) }
1386
1387fn probe_residual_at(
1391 surface: &NurbsSurface,
1392 curve: &NurbsCurve,
1393 pcurve: &NurbsCurve,
1394 parameters: &[f64],
1395 [t0, t1]: [f64; 2],
1396 locals: &[f64],
1397) -> Result<f64, String> {
1398 crate::imprint::work_profile::add(|c| { c.pcurve_probe_passes += 1; c.pcurve_probe_samples += (parameters.len().saturating_sub(1) * locals.len()) as u64; });
1399 let mut worst = 0.0_f64;
1400 let mut reader = ProbeCurveReader::new(pcurve, probe_batch_enabled());
1401 for span in parameters.windows(2) {
1402 for &local in locals {
1403 let fraction = span[0] + (span[1] - span[0]) * local;
1404 let parameter = reader.evaluate(fraction)?;
1405 let on_surface =
1406 section_surface_point(surface, parameter.x, parameter.y, true)?;
1407 let on_curve = section_curve_point(curve, t0 + (t1 - t0) * fraction)?;
1408 let distance = on_surface.sub(on_curve).length();
1413 if !distance.is_finite() {
1414 return Err(format!(
1415 "probe_residual: non-finite image distance {distance} at fraction {fraction}"
1416 ));
1417 }
1418 worst = worst.max(distance);
1419 }
1420 }
1421 Ok(worst)
1422}
1423
1424pub(crate) fn native_probe_fractions(curves: &[&NurbsCurve]) -> Result<Vec<f64>, String> {
1431 let locals: Vec<f64> = [0.25, 0.5, 0.75]
1432 .into_iter()
1433 .chain((1..=TRACKING_ACCEPTANCE_POINTS).map(|index| index as f64 / (TRACKING_ACCEPTANCE_POINTS + 1) as f64))
1434 .collect();
1435 let mut fractions = Vec::new();
1436 for curve in curves {
1437 let [q0, q1] = curve.domain()?;
1438 fractions.push(q0);
1439 fractions.push(q1);
1440 let mut knots: Vec<f64> = curve.knots.iter().copied().filter(|k| *k >= q0 && *k <= q1).collect();
1441 knots.dedup();
1442 for span in knots.windows(2).filter(|w| w[1] > w[0]) {
1443 for &local in &locals {
1444 fractions.push(span[0] + (span[1] - span[0]) * local);
1445 }
1446 }
1447 }
1448 fractions.sort_by(f64::total_cmp);
1449 fractions.dedup();
1450 Ok(fractions)
1451}
1452
1453#[derive(Clone, Copy, Debug, PartialEq)]
1462struct NativeRead {
1463 tracking: f64,
1464 deviation: f64,
1465 standoff: f64,
1466}
1467
1468fn native_read(surface: &NurbsSurface, curve: &NurbsCurve, pcurve: &NurbsCurve, [t0, t1]: [f64; 2], fractions: &[f64]) -> Result<NativeRead, String> {
1469 crate::imprint::work_profile::add(|c| { c.pcurve_native_passes += 1; c.pcurve_native_samples += fractions.len() as u64; });
1470 let mut read = NativeRead { tracking: 0.0, deviation: 0.0, standoff: 0.0 };
1471 let mut reader = ProbeCurveReader::new(pcurve, probe_batch_enabled());
1472 for &fraction in fractions {
1473 let parameter = reader.evaluate(fraction)?;
1474 let image = section_surface_point(surface, parameter.x, parameter.y, true)?;
1475 let on_curve = section_curve_point(curve, t0 + (t1 - t0) * fraction)?;
1476 let foot = crate::projection::project_point_to_surface_from_seed(surface, on_curve, [parameter.x, parameter.y])?;
1477 let tracking = image.sub(foot.point).length();
1478 let deviation = image.sub(on_curve).length();
1479 if !(tracking.is_finite() && deviation.is_finite() && foot.distance.is_finite()) {
1480 return Err(format!("native read: non-finite reading at fraction {fraction}"));
1481 }
1482 read.tracking = read.tracking.max(tracking);
1483 read.deviation = read.deviation.max(deviation);
1484 read.standoff = read.standoff.max(foot.distance);
1485 }
1486 Ok(read)
1487}
1488
1489fn standoff_candidate_accepted(standing: NativeRead, candidate: NativeRead, candidate_fields_finite: bool, floor: f64) -> bool {
1495 candidate_fields_finite
1496 && candidate.tracking.is_finite()
1497 && candidate.deviation.is_finite()
1498 && candidate.tracking <= floor
1499 && candidate.tracking < standing.tracking
1500 && candidate.deviation <= standing.deviation
1501}
1502
1503fn tracking_acceptance_residual(
1509 surface: &NurbsSurface,
1510 curve: &NurbsCurve,
1511 pcurve: &NurbsCurve,
1512 parameters: &[f64],
1513 domain: [f64; 2],
1514) -> Result<f64, String> {
1515 let locals: Vec<f64> = [0.25, 0.5, 0.75]
1516 .into_iter()
1517 .chain((1..=TRACKING_ACCEPTANCE_POINTS).map(|index| index as f64 / (TRACKING_ACCEPTANCE_POINTS + 1) as f64))
1518 .collect();
1519 probe_residual_at(surface, curve, pcurve, parameters, domain, &locals)
1520}
1521
1522fn tracking_candidate_accepted(standing: f64, standing_dense: bool, floor: f64, exit: PcurveFitExit, reading: f64) -> bool {
1544 if exit == PcurveFitExit::Converged && !standing_dense {
1545 return reading <= floor && reading < standing;
1546 }
1547 if exit != PcurveFitExit::Converged && !(standing > floor) {
1548 return false;
1549 }
1550 reading.is_finite() && reading <= floor && reading < standing
1551}
1552
1553fn judge_tracking_candidate(
1560 standing: f64,
1561 standing_dense: bool,
1562 floor: f64,
1563 exit: PcurveFitExit,
1564 own: f64,
1565 dense: impl FnOnce() -> Result<f64, String>,
1566) -> (Result<Option<f64>, String>, bool) {
1567 judge_tracking_candidate_with_bounds(standing, standing_dense, floor, exit, own, dense, false)
1568}
1569
1570fn judge_tracking_candidate_with_bounds(
1571 standing: f64,
1572 standing_dense: bool,
1573 floor: f64,
1574 exit: PcurveFitExit,
1575 own: f64,
1576 dense: impl FnOnce() -> Result<f64, String>,
1577 bounds: bool,
1578) -> (Result<Option<f64>, String>, bool) {
1579 if bounds && exit != PcurveFitExit::Converged && own > floor {
1583 if crate::profile::profile_enabled() { profile_line!("pcurve.reject_bound kind=quarter_residual"); }
1584 return (Ok(Some(own)), false);
1585 }
1586 let reading = if exit == PcurveFitExit::Converged && !standing_dense {
1587 Ok(Some(own))
1588 } else if exit == PcurveFitExit::Converged || standing > floor {
1589 dense().map(Some)
1590 } else {
1591 Ok(None)
1592 };
1593 let accepted = matches!(
1594 reading,
1595 Ok(Some(value)) if tracking_candidate_accepted(standing, standing_dense, floor, exit, value)
1596 );
1597 (reading, accepted)
1598}
1599
1600struct Refinement {
1603 exit: PcurveFitExit,
1604 residual: f64,
1605 off_surface: f64,
1606 raised: bool,
1607 clamped: [f64; 2],
1610}
1611
1612#[allow(clippy::too_many_arguments)]
1645fn refine_pcurve(
1646 surface: &NurbsSurface,
1647 curve: &NurbsCurve,
1648 domain: [f64; 2],
1649 u_domain: [f64; 2],
1650 v_domain: [f64; 2],
1651 floor: f64,
1652 joins: &[f64],
1653 parameters: &mut Vec<f64>,
1654 raw: &mut Vec<[f64; 2]>,
1655 pcurve: &mut NurbsCurve,
1656 off_surface: f64,
1657 clamped: [f64; 2],
1658 mut insert: impl FnMut(f64, Vec3, Vec3) -> Result<(Option<[f64; 2]>, f64), String>,
1659) -> Result<Refinement, String> {
1660 let trace = env_read!("BREP_DEBUG_PCURVE_FIT").is_some();
1663 let call = if trace {
1664 PCURVE_TRACK_CALL.fetch_add(1, std::sync::atomic::Ordering::Relaxed) + 1
1665 } else {
1666 0
1667 };
1668 let reject_bounds = PCURVE_REJECT_BOUNDS.with(|state| state.get());
1669 let mut best = refine_pcurve_pass(surface, curve, domain, u_domain, v_domain,
1670 floor, joins, parameters, raw, pcurve, off_surface, clamped, false, 1.0, false, &mut insert, false)?;
1671 if trace {
1672 eprintln!(
1673 "PCURVE-TRACK call={call} first-pass exit={:?} residual={:e} floor={floor:e} off_surface={:e} samples={} raised={} tracking={}",
1674 best.exit,
1675 best.residual,
1676 best.off_surface,
1677 parameters.len(),
1678 best.raised,
1679 if best.off_surface <= floor { "eligible" } else { "standoff-tracking" }
1680 );
1681 }
1682 if best.off_surface > floor {
1683 if !standoff_tracking_enabled() {
1703 return Ok(best);
1704 }
1705 return standoff_tracking_rungs(surface, curve, domain, u_domain, v_domain, floor, joins,
1706 parameters, raw, pcurve, best, trace, call, &mut insert);
1707 }
1708 let baseline_parameters = parameters.clone();
1713 let baseline_raw = raw.clone();
1714 let baseline_curve = pcurve.clone();
1715 let baseline_off_surface = best.off_surface;
1716 let baseline_clamped = best.clamped;
1717 let standing_misses = best.residual > floor;
1726 Ok(tracking_rungs(
1727 best,
1728 floor,
1729 trace,
1730 call,
1731 true,
1732 |fraction| {
1733 let mut refined_parameters = baseline_parameters.clone();
1734 let mut refined_raw = baseline_raw.clone();
1735 let mut refined_curve = baseline_curve.clone();
1736 let candidate = refine_pcurve_pass(surface, curve, domain, u_domain, v_domain,
1737 floor, joins, &mut refined_parameters, &mut refined_raw, &mut refined_curve,
1738 baseline_off_surface, baseline_clamped, true, fraction, standing_misses, &mut insert, reject_bounds && !standing_misses);
1739 (candidate, (refined_parameters, refined_raw, refined_curve))
1740 },
1741 |state: &RungState| tracking_acceptance_residual(surface, curve, &state.2, &state.0, domain),
1742 |state: &RungState| state.0.len(),
1743 |(refined_parameters, refined_raw, refined_curve): RungState| {
1744 *parameters = refined_parameters;
1745 *raw = refined_raw;
1746 *pcurve = refined_curve;
1747 },
1748 ))
1749}
1750
1751type RungState = (Vec<f64>, Vec<[f64; 2]>, NurbsCurve);
1754
1755#[allow(clippy::too_many_arguments)]
1765fn tracking_rungs<S>(
1766 mut best: Refinement,
1767 floor: f64,
1768 trace: bool,
1769 call: u64,
1770 thread_dense: bool,
1771 mut run_pass: impl FnMut(f64) -> (Result<Refinement, String>, S),
1772 mut dense: impl FnMut(&S) -> Result<f64, String>,
1773 samples: impl Fn(&S) -> usize,
1774 mut adopt: impl FnMut(S),
1775) -> Refinement {
1776 let mut standing_dense = false;
1779 let reject_bounds = PCURVE_REJECT_BOUNDS.with(|state| state.get());
1780 for fraction in [0.1, 0.01] {
1781 if best.residual <= floor * fraction {
1782 if trace {
1783 eprintln!(
1784 "PCURVE-TRACK call={call} candidate fraction={fraction} skipped best_residual={:e} <= {:e}",
1785 best.residual,
1786 floor * fraction
1787 );
1788 }
1789 continue;
1790 }
1791 let (candidate, state) = run_pass(fraction);
1792 let judged_dense = matches!(&candidate, Ok(seen) if seen.exit != PcurveFitExit::Converged || standing_dense);
1796 let (effective, accepted) = match &candidate {
1797 Ok(seen) => judge_tracking_candidate_with_bounds(best.residual, standing_dense, floor, seen.exit, seen.residual, || {
1798 dense(&state)
1799 }, reject_bounds),
1800 Err(_) => (Ok(None), false),
1801 };
1802 if trace {
1803 let judged_on = match &effective {
1804 Ok(Some(reading)) => format!("{reading:e}"),
1805 Ok(None) => "-".to_string(),
1806 Err(message) => format!("error:{message:?}"),
1807 };
1808 match &candidate {
1809 Ok(seen) => eprintln!(
1810 "PCURVE-TRACK call={call} candidate fraction={fraction} exit={:?} residual={:e} judged_on={judged_on} standing_dense={standing_dense} floor={floor:e} off_surface={:e} samples={} raised={} residual_meets_floor={} decision={}",
1811 seen.exit,
1812 seen.residual,
1813 seen.off_surface,
1814 samples(&state),
1815 seen.raised,
1816 seen.residual <= floor,
1817 if accepted { "accept" } else { "decline-stop" }
1818 ),
1819 Err(message) => eprintln!(
1820 "PCURVE-TRACK call={call} candidate fraction={fraction} error={message:?} decision=decline-stop"
1821 ),
1822 }
1823 }
1824 match candidate {
1825 Ok(mut candidate) if accepted => {
1826 if let Ok(Some(reading)) = effective {
1828 candidate.residual = reading;
1829 }
1830 if thread_dense {
1832 standing_dense |= judged_dense;
1833 }
1834 adopt(state);
1835 best = candidate;
1836 }
1837 _ => break,
1838 }
1839 }
1840 best
1841}
1842
1843fn standoff_tracking_enabled() -> bool {
1847 switch!("BREP_PCURVE_STANDOFF_TRACKING", true)
1848}
1849
1850#[allow(clippy::too_many_arguments)]
1866fn standoff_tracking_rungs(
1867 surface: &NurbsSurface,
1868 curve: &NurbsCurve,
1869 domain: [f64; 2],
1870 u_domain: [f64; 2],
1871 v_domain: [f64; 2],
1872 floor: f64,
1873 joins: &[f64],
1874 parameters: &mut Vec<f64>,
1875 raw: &mut Vec<[f64; 2]>,
1876 pcurve: &mut NurbsCurve,
1877 mut best: Refinement,
1878 trace: bool,
1879 call: u64,
1880 insert: &mut impl FnMut(f64, Vec3, Vec3) -> Result<(Option<[f64; 2]>, f64), String>,
1881) -> Result<Refinement, String> {
1882 let first = native_probe_fractions(&[&*pcurve]).and_then(|probes| native_read(surface, curve, pcurve, domain, &probes));
1883 if trace {
1884 eprintln!("PCURVE-TRACK call={call} standoff-tracking first-pass native={first:?} floor={floor:e}");
1885 }
1886 let Ok(first) = first else { return Ok(best) };
1887 if first.tracking <= floor {
1888 return Ok(best);
1889 }
1890 let baseline_parameters = parameters.clone();
1891 let baseline_raw = raw.clone();
1892 let baseline_curve = pcurve.clone();
1893 for fraction in [0.1, 0.01] {
1894 let mut refined_parameters = baseline_parameters.clone();
1895 let mut refined_raw = baseline_raw.clone();
1896 let mut refined_curve = baseline_curve.clone();
1897 let candidate = refine_pcurve_pass(surface, curve, domain, u_domain, v_domain, floor, joins,
1898 &mut refined_parameters, &mut refined_raw, &mut refined_curve, best.off_surface, best.clamped,
1899 true, fraction, true, &mut *insert, false);
1900 let reads = candidate.as_ref().ok().map(|_| {
1901 native_probe_fractions(&[&*pcurve, &refined_curve]).and_then(|probes| {
1902 Ok((native_read(surface, curve, pcurve, domain, &probes)?, native_read(surface, curve, &refined_curve, domain, &probes)?))
1903 })
1904 });
1905 let fields_finite = matches!(&candidate, Ok(seen) if seen.residual.is_finite() && seen.off_surface.is_finite());
1906 let decision = match &reads {
1907 Some(Ok((standing, read))) => standoff_rung_decision(*standing, *read, fields_finite, floor),
1908 _ => RungDecision::Stop,
1909 };
1910 if trace {
1911 eprintln!(
1912 "PCURVE-TRACK call={call} standoff-tracking fraction={fraction} candidate={} reads={reads:?} decision={}",
1913 match &candidate { Ok(seen) => format!("{:?}/{:e}/raised={}", seen.exit, seen.residual, seen.raised), Err(message) => format!("error:{message:?}") },
1914 match decision { RungDecision::Accept => "accept", RungDecision::Continue => "decline-continue", RungDecision::Stop => "decline-stop" }
1915 );
1916 }
1917 let (Ok(mut taken), Some(Ok((_, read))), RungDecision::Accept) = (candidate, reads, decision) else {
1918 if decision == RungDecision::Continue {
1919 continue;
1920 }
1921 break;
1922 };
1923 taken.residual = read.deviation;
1924 taken.off_surface = taken.off_surface.max(read.standoff);
1925 *parameters = refined_parameters;
1926 *raw = refined_raw;
1927 *pcurve = refined_curve;
1928 best = taken;
1929 if read.tracking <= floor * 0.01 {
1930 break;
1931 }
1932 }
1933 Ok(best)
1934}
1935
1936#[derive(Clone, Copy, Debug, PartialEq, Eq)]
1939enum RungDecision {
1940 Accept,
1942 Continue,
1947 Stop,
1949}
1950
1951fn standoff_rung_decision(standing: NativeRead, candidate: NativeRead, fields_finite: bool, floor: f64) -> RungDecision {
1952 if standoff_candidate_accepted(standing, candidate, fields_finite, floor) {
1953 RungDecision::Accept
1954 } else if candidate.tracking.is_finite() && candidate.tracking < standing.tracking {
1955 RungDecision::Continue
1956 } else {
1957 RungDecision::Stop
1958 }
1959}
1960
1961fn takes_raise(exit: PcurveFitExit, raised: bool, residual: f64, off_surface: f64, floor: f64, unmet_tracking: bool) -> bool {
1968 exit == PcurveFitExit::SampleCeiling && !raised && (residual > off_surface + floor || unmet_tracking)
1969}
1970
1971fn refine_pcurve_pass(
1972 surface: &NurbsSurface,
1973 curve: &NurbsCurve,
1974 [t0, t1]: [f64; 2],
1975 [u0, u1]: [f64; 2],
1976 [v0, v1]: [f64; 2],
1977 floor: f64,
1978 joins: &[f64],
1979 parameters: &mut Vec<f64>,
1980 raw: &mut Vec<[f64; 2]>,
1981 pcurve: &mut NurbsCurve,
1982 mut off_surface: f64,
1983 mut clamped: [f64; 2],
1984 track_projection: bool,
1985 tracking_fraction: f64,
1986 raise_unmet_tracking: bool,
1987 mut insert: impl FnMut(f64, Vec3, Vec3) -> Result<(Option<[f64; 2]>, f64), String>,
1988 reject_budget: bool,
1989) -> Result<Refinement, String> {
1990 let _clock = PcurvePhaseClock::new("refinement", parameters.len(), track_projection);
1991 let tracking_floor = if track_projection { floor * tracking_fraction } else { floor };
1992 let mut max_samples = MAX_PCURVE_SAMPLES;
1993 let mut raised = false;
1994 loop {
1995 let mut exit = PcurveFitExit::RoundBudget;
1999 let mut residual = None;
2000 for round in 0..4 {
2001 crate::imprint::work_profile::add(|c| c.refinement_rounds += 1);
2002 if parameters.len() >= max_samples {
2003 exit = PcurveFitExit::SampleCeiling;
2004 break;
2005 }
2006 let mut inserts = Vec::new();
2007 let mut round_max = 0.0_f64;
2008 let mut truncated = false;
2009 let mut skipped_narrow = false;
2010 let mut reader = ProbeCurveReader::new(pcurve, probe_batch_enabled());
2011 for index in 0..parameters.len() - 1 {
2012 if parameters.len() + inserts.len() >= max_samples {
2013 truncated = true;
2014 break;
2015 }
2016 let start = parameters[index];
2017 let end = parameters[index + 1];
2018 if end - start < if track_projection { SPAN_FLOOR } else { 1e-3 } {
2022 skipped_narrow = true;
2023 continue;
2024 }
2025 for local_fraction in [0.25, 0.5, 0.75] {
2026 if parameters.len() + inserts.len() >= max_samples {
2027 truncated = true;
2028 break;
2029 }
2030 let fraction = start + (end - start) * local_fraction;
2031 let parameter = reader.evaluate(fraction)?;
2032 let on_surface =
2033 section_surface_point(surface, parameter.x, parameter.y, true)?;
2034 let on_curve = section_curve_point(curve, t0 + (t1 - t0) * fraction)?;
2035 let deviation = on_surface.sub(on_curve).length();
2036 if !deviation.is_finite() {
2042 return Err(format!(
2043 "refine_pcurve_pass: non-finite station distance {deviation} at fraction {fraction}"
2044 ));
2045 }
2046 round_max = round_max.max(deviation);
2047 if deviation <= tracking_floor {
2048 continue;
2049 }
2050 let (surface_parameter, gap) = insert(fraction, parameter, on_curve)?;
2051 off_surface = off_surface.max(gap);
2052 if let Some(surface_parameter) = surface_parameter {
2053 if raised || track_projection {
2062 let projected =
2063 section_surface_point(surface, surface_parameter[0], surface_parameter[1], false)?;
2064 if on_surface.sub(projected).length() <= tracking_floor {
2065 continue;
2066 }
2067 }
2068 inserts.push((index + 1, fraction, surface_parameter));
2069 }
2070 }
2071 }
2072 if inserts.is_empty() {
2073 exit = if truncated {
2078 PcurveFitExit::SampleCeiling
2079 } else if round_max > floor {
2080 PcurveFitExit::Stalled
2081 } else if skipped_narrow {
2082 PcurveFitExit::SpanFloor
2083 } else {
2084 residual = Some(round_max);
2085 PcurveFitExit::Converged
2086 };
2087 break;
2088 }
2089 if reject_budget && round == 3 && !truncated {
2094 if crate::profile::profile_enabled() { profile_line!("pcurve.reject_bound kind=fifth_round"); }
2095 return Err("pcurve tracking candidate requires a fifth round".into());
2096 }
2097 for (at, fraction, surface_parameter) in inserts.into_iter().rev() {
2098 parameters.insert(at, fraction);
2099 raw.insert(at, surface_parameter);
2100 }
2101 let (rebuilt, excursion, distance) = build_interpolant_joined(surface, raw, parameters, joins)?;
2102 *pcurve = rebuilt;
2103 clamped = [excursion, distance];
2104 if truncated {
2105 exit = PcurveFitExit::SampleCeiling;
2106 break;
2107 }
2108 }
2109 let residual = match residual {
2110 Some(measured) => measured,
2111 None => probe_residual(
2115 surface,
2116 curve,
2117 pcurve,
2118 parameters,
2119 [t0, t1],
2120 [u0, u1],
2121 [v0, v1],
2122 )?,
2123 };
2124 if exit == PcurveFitExit::SpanFloor && residual <= floor {
2125 exit = PcurveFitExit::Converged;
2126 }
2127 let unmet_tracking = track_projection
2144 && raise_unmet_tracking
2145 && exit == PcurveFitExit::SampleCeiling
2146 && !raised
2147 && native_probe_fractions(&[&*pcurve])
2148 .and_then(|probes| native_read(surface, curve, pcurve, [t0, t1], &probes))
2149 .is_ok_and(|read| read.tracking > tracking_floor);
2150 if takes_raise(exit, raised, residual, off_surface, floor, unmet_tracking) {
2151 raised = true;
2152 max_samples = PCURVE_RAISED_SAMPLES;
2153 continue;
2154 }
2155 return Ok(Refinement {
2156 exit,
2157 residual,
2158 off_surface,
2159 raised,
2160 clamped,
2161 });
2162 }
2163}
2164
2165struct AffineInversion {
2173 origin: Vec3,
2174 du: Vec3,
2175 dv: Vec3,
2176 u0: f64,
2177 v0: f64,
2178 uu: f64,
2179 uv: f64,
2180 vv: f64,
2181 determinant: f64,
2182}
2183
2184impl AffineInversion {
2185 fn of(surface: &NurbsSurface) -> Result<Option<Self>, String> {
2190 if !surface.is_affine()? {
2191 return Ok(None);
2192 }
2193 let ([u0, _], [v0, _]) = surface_domains(surface)?;
2194 let (origin, du, dv) = surface.deriv1(u0, v0)?;
2195 let uu = du.dot(du);
2196 let uv = du.dot(dv);
2197 let vv = dv.dot(dv);
2198 let determinant = uu * vv - uv * uv;
2199 if determinant.abs() <= 1e-18 {
2200 return Ok(None);
2201 }
2202 Ok(Some(Self {
2203 origin,
2204 du,
2205 dv,
2206 u0,
2207 v0,
2208 uu,
2209 uv,
2210 vv,
2211 determinant,
2212 }))
2213 }
2214
2215 fn uv_of(&self, point: Vec3) -> [f64; 2] {
2216 let delta = point.sub(self.origin);
2217 let along_u = delta.dot(self.du);
2218 let along_v = delta.dot(self.dv);
2219 [
2220 self.u0 + (along_u * self.vv - along_v * self.uv) / self.determinant,
2221 self.v0 + (along_v * self.uu - along_u * self.uv) / self.determinant,
2222 ]
2223 }
2224
2225 fn image_of(&self, curve: &NurbsCurve) -> Result<NurbsCurve, String> {
2228 let control_points = curve
2229 .control_points
2230 .iter()
2231 .map(|control| {
2232 let [u, v] = self.uv_of(control.point()?);
2233 Ok(Vec4::from_point(Vec3::new(u, v, 0.0), control.w))
2234 })
2235 .collect::<Result<Vec<_>, String>>()?;
2236 NurbsCurve::new(curve.degree, curve.knots.clone(), control_points)
2237 }
2238}
2239
2240fn sphere_iso_enabled() -> bool {
2241 env_read!("BREP_PCURVE_SPHERE_ISO").is_none_or(|mode| mode != "0")
2242}
2243
2244fn sphere_iso_fit(surface: &NurbsSurface, curve: &NurbsCurve) -> Option<PcurveFit> {
2251 if surface.degree_u != 2 { return None; }
2254 let [t0, t1] = curve.domain().ok()?;
2255 let [u0, u1] = surface.domain_u().ok()?;
2256 let [v0, v1] = surface.domain_v().ok()?;
2257 if !matches!(surface.analytic(), Some(AnalyticSurface::Sphere { .. })) { return None; }
2258 let middle = curve.evaluate(t0 + (t1 - t0) * 0.5).ok()?;
2259 let projected = project_point_to_surface(surface, middle).ok()?;
2260 let mut candidates = vec![projected.u];
2261 for &knot in &surface.knots_u {
2264 if (knot - projected.u).abs() <= 1e-12 && !candidates.contains(&knot) { candidates.push(knot); }
2265 }
2266 for u in candidates {
2267 if !(u >= u0 && u <= u1) { continue; }
2268 let iso = surface.iso_curve_u(u).ok()?;
2269 if iso.degree != curve.degree || iso.knots.len() != curve.knots.len()
2270 || iso.control_points.len() != curve.control_points.len() { continue; }
2271 for reverse in [false, true] {
2272 let n = iso.control_points.len();
2273 fn exact_difference(a: f64, b: f64) -> Option<f64> {
2279 if !(a.is_finite() && b.is_finite()) || a.abs().max(b.abs()) > 1e100 { return None; }
2280 let x = a - b;
2281 let bv = a - x;
2282 let av = x + bv;
2283 let error = (a - av) + (bv - b);
2284 (error == 0.).then_some(x)
2285 }
2286 fn exact_fraction(offset: f64, span: f64) -> Option<f64> {
2287 if !(1e-100..=1e100).contains(&span) { return None; }
2288 let ratio = offset / span;
2289 if !(0.0..=1.0).contains(&ratio) || (ratio != 0. && ratio < 1e-100) { return None; }
2290 (ratio.mul_add(span, -offset) == 0.).then_some(ratio)
2291 }
2292 let knots_match = (|| {
2293 let section_span = exact_difference(t1, t0)?;
2294 let native_span = exact_difference(v1, v0)?;
2295 for (i, &knot) in curve.knots.iter().enumerate() {
2296 let section = exact_difference(knot, t0)?;
2297 let native = if reverse { exact_difference(v1, iso.knots[iso.knots.len() - 1 - i])? }
2298 else { exact_difference(iso.knots[i], v0)? };
2299 if exact_fraction(section, section_span)? != exact_fraction(native, native_span)? { return None; }
2300 }
2301 Some(())
2302 })().is_some();
2303 if !knots_match { continue; }
2304 let mut bound = 0.0_f64;
2305 let mut matches = true;
2306 for (i, control) in curve.control_points.iter().enumerate() {
2307 let native = &iso.control_points[if reverse { n - 1 - i } else { i }];
2308 if !(control.w > 0.) || control.w != native.w { matches = false; break; }
2309 let distance = control.point().ok()?.sub(native.point().ok()?).length();
2310 if !distance.is_finite() { matches = false; break; }
2311 bound = bound.max(distance);
2312 }
2313 if !matches || bound > PCURVE_REFINEMENT_TOLERANCE * 0.0625 { continue; }
2314 let (start, end) = if reverse { (v1, v0) } else { (v0, v1) };
2315 let pcurve = NurbsCurve::new(1, vec![0., 0., 1., 1.], vec![
2316 Vec4::from_point(Vec3::new(u, start, 0.), 1.),
2317 Vec4::from_point(Vec3::new(u, end, 0.), 1.),
2318 ]).ok()?;
2319 for i in 0..=96 {
2324 let fraction = i as f64 / 96.;
2325 let uv = pcurve.evaluate(fraction).ok()?;
2326 let image = surface.evaluate(uv.x, uv.y).ok()?;
2327 let on_curve = curve.evaluate(t0 + (t1 - t0) * fraction).ok()?;
2328 let error = image.sub(on_curve).length();
2329 if !error.is_finite() { matches = false; break; }
2330 bound = bound.max(error);
2331 }
2332 if !matches || bound > PCURVE_REFINEMENT_TOLERANCE * 0.0625 { continue; }
2333 crate::imprint::work_profile::constructed("analytic_certified", 0, pcurve.control_points.len());
2334 return Some(PcurveFit { curve: pcurve, report: PcurveFitReport {
2335 residual: bound, floor: PCURVE_REFINEMENT_TOLERANCE, samples: 2,
2336 exit: PcurveFitExit::Converged, off_surface: bound, raised: false,
2337 clamped_excursion: 0., clamped_distance: 0.,
2338 } });
2339 }
2340 }
2341 None
2342}
2343
2344pub fn fit_pcurve_on_surface(
2354 surface: &NurbsSurface,
2355 curve: &NurbsCurve,
2356) -> Result<PcurveFit, String> {
2357 let _wall = crate::wall_profile::Scope::enter(crate::wall_profile::FIT);
2358 crate::imprint::work_profile::add(|c| c.fit_calls += 1);
2359 if sphere_iso_enabled() {
2360 if let Some(fit) = sphere_iso_fit(surface, curve) { return Ok(fit); }
2361 }
2362 let mode = env_read!("BREP_PCURVE_EVAL_CACHE").unwrap_or_default();
2363 let bounds = env_read!("BREP_PCURVE_REJECT_BOUNDS").unwrap_or_else(|| "on".into());
2364 let stack = env_read!("BREP_PCURVE_STACK_POINT").unwrap_or_else(|| "on".into());
2365 if mode == "check" || bounds == "check" || stack == "check" {
2366 let old = fit_pcurve_on_surface_cached(surface, curve, false, false, false)?;
2367 if matches!(surface.analytic(), Some(AnalyticSurface::Sphere { .. })) {
2368 let candidate = fit_pcurve_on_surface_cached(surface, curve, mode == "check" || mode == "on" || mode == "1", bounds == "check" || bounds == "on" || bounds == "1", stack == "check" || stack == "on" || stack == "1");
2369 let identical = candidate.as_ref().is_ok_and(|new| {
2370 old.curve.degree == new.curve.degree
2371 && old.curve.knots.len() == new.curve.knots.len()
2372 && old.curve.knots.iter().zip(&new.curve.knots).all(|(a, b)| a.to_bits() == b.to_bits())
2373 && old.curve.control_points.len() == new.curve.control_points.len()
2374 && old.curve.control_points.iter().zip(&new.curve.control_points).all(|(a, b)| {
2375 [a.x.to_bits(), a.y.to_bits(), a.z.to_bits(), a.w.to_bits()]
2376 == [b.x.to_bits(), b.y.to_bits(), b.z.to_bits(), b.w.to_bits()]
2377 }) && old.report == new.report
2378 });
2379 if let Ok(path) = std::env::var("BREP_PCURVE_EVAL_CENSUS") {
2380 use std::io::Write;
2381 if let Ok(mut file) = std::fs::OpenOptions::new().create(true).append(true).open(path) {
2382 let _ = writeln!(file, "pcurve.eval_census identical={identical} controls={} samples={}", old.curve.control_points.len(), old.report.samples);
2383 }
2384 }
2385 }
2386 return Ok(old);
2387 }
2388 fit_pcurve_on_surface_cached(surface, curve, mode == "1" || mode == "on", bounds == "1" || bounds == "on", stack == "1" || stack == "on")
2389}
2390
2391fn fit_pcurve_on_surface_cached(surface: &NurbsSurface, curve: &NurbsCurve, enabled: bool, bounds: bool, stack: bool) -> Result<PcurveFit, String> {
2392 let _stack = PcurveStackPointScope::open(stack && matches!(surface.analytic(), Some(AnalyticSurface::Sphere { .. })));
2393 let _samples = PcurveSampleScope::open(surface, curve, enabled
2397 || !matches!(surface.analytic(), Some(AnalyticSurface::Sphere { .. })));
2398 let _bounds = PcurveRejectScope::open(bounds && matches!(surface.analytic(), Some(AnalyticSurface::Sphere { .. })));
2399 let [t0, t1] = curve.domain()?;
2400 if surface.is_affine()? {
2401 let Some(inversion) = AffineInversion::of(surface)? else {
2402 return Err("build_pcurve_on_surface: singular affine parameterization".into());
2403 };
2404 let pcurve = inversion.image_of(curve)?;
2405 crate::imprint::work_profile::constructed("affine", 0, pcurve.control_points.len());
2406 return Ok(PcurveFit {
2407 report: PcurveFitReport {
2408 residual: 0.0,
2409 floor: PCURVE_REFINEMENT_TOLERANCE,
2410 samples: pcurve.control_points.len(),
2411 exit: PcurveFitExit::Converged,
2412 off_surface: 0.0,
2413 raised: false,
2414 clamped_excursion: 0.0,
2415 clamped_distance: 0.0,
2416 },
2417 curve: pcurve,
2418 });
2419 }
2420
2421 let scale = 1.0 + curve.evaluate((t0 + t1) / 2.0)?.length();
2422 let drop_tolerance = 1e-4 * scale;
2423 let endpoint_tolerance = 1e-3 * scale;
2424 let refinement_tolerance = PCURVE_REFINEMENT_TOLERANCE;
2425 let ([u0, u1], [v0, v1]) = surface_domains(surface)?;
2426 let invert =
2427 |fraction: f64| invert_checked(surface, section_curve_point(curve, t0 + (t1 - t0) * fraction)?);
2428
2429 let mut parameters = Vec::with_capacity(25);
2430 let mut raw_surface_parameters = Vec::with_capacity(25);
2431 let mut off_surface = 0.0_f64;
2434 let corners = range_breaks(curve, t0, t1, true);
2437 let mut stations: Vec<f64> = (0..=24).map(|index| index as f64 / 24.0).collect();
2438 stations.retain(|station| {
2441 *station == 0.0 || *station == 1.0 || corners.contains(station)
2442 || !corners.iter().any(|corner| (*station - corner).abs() <= SPAN_FLOOR)
2443 });
2444 for &corner in &corners {
2445 let at = stations.partition_point(|value| *value < corner);
2446 if stations.get(at) != Some(&corner) {
2447 stations.insert(at, corner);
2448 }
2449 }
2450 let joins = corners;
2451 for (index, &fraction) in stations.iter().enumerate() {
2452 let (parameter, distance) = invert(fraction)?;
2453 off_surface = off_surface.max(distance);
2454 if distance > drop_tolerance && index != 0 && index != stations.len() - 1 {
2455 continue;
2456 }
2457 if distance > endpoint_tolerance {
2458 if std::env::var("BREP_DEBUG_PCURVE").is_ok() {
2459 let p3 = curve.evaluate(t0 + (t1 - t0) * fraction).ok();
2460 let p0 = curve.evaluate(t0).ok();
2461 let p1 = curve.evaluate(t1).ok();
2462 eprintln!(
2463 "PCURVE-FAIL idx={index} frac={fraction} dist={distance} endpt_tol={endpoint_tolerance} scale={scale}\n curve3D@frac={p3:?}\n curve3D@t0={p0:?} curve3D@t1={p1:?}\n surf_domain=u[{u0},{u1}] v[{v0},{v1}] invpar={parameter:?}\n surf@invpar={:?}",
2464 surface.evaluate(parameter[0], parameter[1]).ok()
2465 );
2466 }
2467 return Err(format!(
2468 "build_pcurve_on_surface: endpoint projection failed (distance={distance})"
2469 ));
2470 }
2471 parameters.push(fraction);
2472 raw_surface_parameters.push(parameter);
2473 }
2474
2475 let (mut pcurve, excursion, distance) =
2476 build_interpolant_joined(surface, &raw_surface_parameters, ¶meters, &joins)?;
2477 let refinement = refine_pcurve(
2478 surface,
2479 curve,
2480 [t0, t1],
2481 [u0, u1],
2482 [v0, v1],
2483 refinement_tolerance,
2484 &joins,
2485 &mut parameters,
2486 &mut raw_surface_parameters,
2487 &mut pcurve,
2488 off_surface,
2489 [excursion, distance],
2490 |fraction, _parameter, _on_curve| {
2491 let (surface_parameter, distance) = invert(fraction)?;
2492 Ok((
2493 (distance <= drop_tolerance).then_some(surface_parameter),
2494 distance,
2495 ))
2496 },
2497 )?;
2498 crate::imprint::work_profile::constructed("projected_global", parameters.len(), pcurve.control_points.len());
2499 Ok(PcurveFit {
2500 curve: pcurve,
2501 report: PcurveFitReport {
2502 residual: refinement.residual,
2503 floor: refinement_tolerance,
2504 samples: parameters.len(),
2505 exit: refinement.exit,
2506 off_surface: refinement.off_surface,
2507 raised: refinement.raised,
2508 clamped_excursion: refinement.clamped[0],
2509 clamped_distance: refinement.clamped[1],
2510 },
2511 })
2512}
2513
2514pub fn build_pcurve_on_surface(
2519 surface: &NurbsSurface,
2520 curve: &NurbsCurve,
2521) -> Result<NurbsCurve, String> {
2522 let fit = fit_pcurve_on_surface(surface, curve)?;
2523 record_fit(&fit.report);
2524 Ok(fit.curve)
2525}
2526
2527struct SectionFitClock {
2529 started: Option<web_time::Instant>,
2530 global: std::time::Duration,
2531 seeded: bool,
2532}
2533impl SectionFitClock {
2534 fn new() -> Self {
2535 Self { started: crate::profile::profile_enabled().then(web_time::Instant::now),
2536 global: std::time::Duration::ZERO, seeded: false }
2537 }
2538}
2539impl Drop for SectionFitClock {
2540 fn drop(&mut self) {
2541 if let Some(started) = self.started {
2542 crate::imprint::profile_emit(format_args!("pcurve.section_time global={:.3} seeded={:.3} result={}",
2543 self.global.as_secs_f64() * 1000.0,
2544 started.elapsed().saturating_sub(self.global).as_secs_f64() * 1000.0,
2545 if self.seeded { "seeded" } else { "global" }));
2546 }
2547 }
2548}
2549
2550pub fn fit_pcurve_on_surface_marched(
2581 surface: &NurbsSurface,
2582 curve: &NurbsCurve,
2583) -> Result<PcurveFit, String> {
2584 let _wall = crate::wall_profile::Scope::enter(crate::wall_profile::FIT);
2585 crate::imprint::work_profile::add(|c| c.fit_calls += 1);
2586 fn run(surface: &NurbsSurface, curve: &NurbsCurve, eager: bool) -> Result<PcurveFit, String> {
2587 let _samples = PcurveSampleScope::open(surface, curve, true);
2590 let mut clock = SectionFitClock::new();
2591 let mut fallback = || {
2595 let started = clock.started.map(|_| web_time::Instant::now());
2596 let fit = fit_pcurve_on_surface(surface, curve);
2597 if let Some(started) = started { clock.global += started.elapsed(); }
2598 fit
2599 };
2600 let global = if eager { Some(fallback()?) } else { None };
2601 if !eager { curve.domain()?; }
2605 if env_read!("BREP_SECTION_PCURVE_MARCH").as_deref() == Some("0") || surface.is_affine()? {
2606 return global.map_or_else(&mut fallback, Ok);
2607 }
2608 let [t0, t1] = curve.domain()?;
2609 if curve.evaluate(t0)?.sub(curve.evaluate(t1)?).length() <= 1e-6 {
2612 return global.map_or_else(&mut fallback, Ok);
2613 }
2614 const SAMPLES: usize = 24;
2615 let fractions: Vec<f64> = (0..=SAMPLES).map(|i| i as f64 / SAMPLES as f64).collect();
2616 let edge: Vec<Vec3> = fractions
2617 .iter()
2618 .map(|fraction| curve.evaluate(t0 + (t1 - t0) * fraction))
2619 .collect::<Result<Vec<_>, _>>()?;
2620 let scale = 1.0 + curve.evaluate((t0 + t1) / 2.0)?.length();
2621 let endpoint_tolerance = 1e-3 * scale;
2622 let (first, first_distance) = invert_checked(surface, edge[0])?;
2623 let (last, last_distance) = invert_checked(surface, edge[SAMPLES])?;
2624 if first_distance > endpoint_tolerance || last_distance > endpoint_tolerance {
2625 return global.map_or_else(&mut fallback, Ok);
2626 }
2627 let mut off_surface = first_distance.max(last_distance);
2630 let ([u0, u1], [v0, v1]) = surface_domains(surface)?;
2631 let u_span = (u1 - u0).abs().max(EPSILON);
2632 let v_span = (v1 - v0).abs().max(EPSILON);
2633 let (closed_u, closed_v) = surface_closedness(surface)?;
2634 let norm_step = |a: [f64; 2], b: [f64; 2]| -> f64 {
2635 let mut du = a[0] - b[0];
2636 if closed_u {
2637 while du > 0.5 * u_span {
2638 du -= u_span;
2639 }
2640 while du < -0.5 * u_span {
2641 du += u_span;
2642 }
2643 }
2644 let mut dv = a[1] - b[1];
2645 if closed_v {
2646 while dv > 0.5 * v_span {
2647 dv -= v_span;
2648 }
2649 while dv < -0.5 * v_span {
2650 dv += v_span;
2651 }
2652 }
2653 ((du / u_span).powi(2) + (dv / v_span).powi(2)).sqrt()
2654 };
2655 let mut raw = vec![first];
2657 let mut previous = first;
2658 for index in 1..SAMPLES {
2659 let seeded =
2660 crate::projection::project_point_to_surface_from_seed(surface, edge[index], previous)?;
2661 let (_, global_distance) = invert_checked(surface, edge[index])?;
2662 if seeded.distance > 4.0 * global_distance + endpoint_tolerance {
2666 return global.map_or_else(&mut fallback, Ok);
2667 }
2668 off_surface = off_surface.max(seeded.distance);
2669 previous = [seeded.u, seeded.v];
2670 raw.push(previous);
2671 }
2672 raw.push(last);
2673 let mut steps: Vec<f64> = (1..raw.len())
2679 .map(|i| norm_step(raw[i], raw[i - 1]))
2680 .collect();
2681 let endpoint_gap = steps.pop().unwrap_or(0.0);
2682 steps.sort_by(f64::total_cmp);
2683 let median = steps
2684 .get(steps.len() / 2)
2685 .copied()
2686 .unwrap_or(0.0)
2687 .max(EPSILON);
2688 if endpoint_gap > (4.0 * median).max(0.05) {
2689 return global.map_or_else(&mut fallback, Ok);
2690 }
2691 let mut parameters = fractions;
2695 let (mut pcurve, excursion, distance) = build_interpolant(surface, &raw, ¶meters)?;
2696 let refinement_tolerance = PCURVE_REFINEMENT_TOLERANCE;
2697 let refinement = refine_pcurve(
2700 surface,
2701 curve,
2702 [t0, t1],
2703 [u0, u1],
2704 [v0, v1],
2705 refinement_tolerance,
2706 &[],
2707 &mut parameters,
2708 &mut raw,
2709 &mut pcurve,
2710 off_surface,
2711 [excursion, distance],
2712 |_fraction, seed, on_curve| {
2713 let seeded = crate::projection::project_point_to_surface_from_seed(surface, on_curve, [seed.x, seed.y])?;
2714 Ok((Some([seeded.u, seeded.v]), seeded.distance))
2715 },
2716 )?;
2717 clock.seeded = true;
2718 crate::imprint::work_profile::constructed("projected_seeded", parameters.len(), pcurve.control_points.len());
2719 Ok(PcurveFit {
2720 curve: pcurve,
2721 report: PcurveFitReport {
2722 residual: refinement.residual,
2723 floor: refinement_tolerance,
2724 samples: parameters.len(),
2725 exit: refinement.exit,
2726 off_surface: refinement.off_surface,
2727 raised: refinement.raised,
2728 clamped_excursion: refinement.clamped[0],
2729 clamped_distance: refinement.clamped[1],
2730 },
2731 })
2732 }
2733
2734 let mode = match std::env::var("BREP_PCURVE_LAZY_GLOBAL") {
2735 Ok(mode) => mode,
2736 Err(std::env::VarError::NotPresent) => "on".to_owned(),
2737 Err(std::env::VarError::NotUnicode(_)) => String::new(),
2738 };
2739 if mode != "check" {
2740 return run(surface, curve, !matches!(mode.as_str(), "1" | "on"));
2741 }
2742 let lazy_surface = surface.clone();
2745 let lazy_curve = curve.clone();
2746 let eager = run(surface, curve, true);
2747 let lazy = run(&lazy_surface, &lazy_curve, false);
2748 let identical = match (&eager, &lazy) {
2749 (Ok(a), Ok(b)) => {
2750 a.curve.degree == b.curve.degree
2751 && a.curve.knots.len() == b.curve.knots.len()
2752 && a.curve.knots.iter().zip(&b.curve.knots).all(|(a,b)| a.to_bits() == b.to_bits())
2753 && a.curve.control_points.len() == b.curve.control_points.len()
2754 && a.curve.control_points.iter().zip(&b.curve.control_points).all(|(a,b)| {
2755 [a.x.to_bits(),a.y.to_bits(),a.z.to_bits(),a.w.to_bits()]
2756 == [b.x.to_bits(),b.y.to_bits(),b.z.to_bits(),b.w.to_bits()]
2757 })
2758 && a.report == b.report
2759 && [a.report.residual, a.report.floor, a.report.off_surface,
2760 a.report.clamped_excursion, a.report.clamped_distance].map(f64::to_bits)
2761 == [b.report.residual, b.report.floor, b.report.off_surface,
2762 b.report.clamped_excursion, b.report.clamped_distance].map(f64::to_bits)
2763 }
2764 (Err(a), Err(b)) => a == b,
2765 _ => false,
2766 };
2767 if let Ok(path) = std::env::var("BREP_PCURVE_LAZY_GLOBAL_CENSUS") {
2768 use std::io::Write;
2769 let mut file = std::fs::OpenOptions::new().create(true).append(true).open(path)
2770 .expect("open lazy-global differential ledger");
2771 writeln!(file, "pcurve.lazy_global identical={identical} eager_ok={} lazy_ok={} degree={} controls={}",
2772 eager.is_ok(), lazy.is_ok(), curve.degree, curve.control_points.len())
2773 .expect("append lazy-global differential ledger");
2774 }
2775 assert!(identical, "lazy global pcurve fallback changed the curve, report or error");
2776 eager
2777}
2778
2779pub fn build_pcurve_on_surface_marched(
2783 surface: &NurbsSurface,
2784 curve: &NurbsCurve,
2785) -> Result<NurbsCurve, String> {
2786 let fit = fit_pcurve_on_surface_marched(surface, curve)?;
2787 record_fit(&fit.report);
2788 Ok(fit.curve)
2789}
2790
2791pub fn fit_pcurve_on_surface_range(
2799 surface: &NurbsSurface,
2800 curve: &NurbsCurve,
2801 edge_start: f64,
2802 edge_end: f64,
2803 forward: bool,
2804 tolerance: f64,
2805) -> Result<PcurveFit, String> {
2806 let _wall = crate::wall_profile::Scope::enter(crate::wall_profile::FIT);
2807 crate::imprint::work_profile::add(|c| c.fit_calls += 1);
2808 if let Some(exact) =
2809 affine_pcurve_on_range(surface, curve, edge_start, edge_end, forward, tolerance)?
2810 {
2811 return Ok(exact);
2812 }
2813 fit_pcurve_on_surface_range_dense(
2814 surface, curve, edge_start, edge_end, forward, tolerance, 64, 3, 513,
2815 )
2816}
2817
2818pub fn build_pcurve_on_surface_range(
2822 surface: &NurbsSurface,
2823 curve: &NurbsCurve,
2824 edge_start: f64,
2825 edge_end: f64,
2826 forward: bool,
2827 tolerance: f64,
2828) -> Result<NurbsCurve, String> {
2829 accept_fit(fit_pcurve_on_surface_range(
2830 surface, curve, edge_start, edge_end, forward, tolerance,
2831 )?)
2832}
2833
2834fn station_fit_tracing() -> bool {
2837 debug_flag!("BREP_DEBUG_STATION_FIT")
2838}
2839
2840const SPAN_FLOOR: f64 = 1e-6;
2847
2848const RAISED_ROUNDS: usize = 40;
2851
2852pub const PCURVE_OFF_BAR: &str = "pcurve fit refused: the trim misses its stations by";
2854
2855fn accept_fit(fit: PcurveFit) -> Result<NurbsCurve, String> {
2868 let report = fit.report;
2869 if report.on_bar() {
2870 return Ok(fit.curve);
2871 }
2872 Err(off_bar_message(&report))
2873}
2874
2875fn off_bar_message(report: &PcurveFitReport) -> String {
2876 format!(
2877 "{PCURVE_OFF_BAR} {:.3e} out of sample against a bar of {:.3e} (asked {:.1e}, the \
2878 stations stand {:.3e} off the carrier; {:?} at {} samples{}{})",
2879 report.residual,
2880 report.floor + report.off_surface,
2881 report.floor,
2882 report.off_surface,
2883 report.exit,
2884 report.samples,
2885 if report.raised { ", after the raise" } else { "" },
2886 if report.clamped_excursion > 0.0 {
2887 format!(
2888 "; clamped into the chart by {:.3e} in parameter, {:.3e} in 3D",
2889 report.clamped_excursion, report.clamped_distance
2890 )
2891 } else {
2892 String::new()
2893 },
2894 )
2895}
2896
2897pub(crate) const PCURVE_OFF_BAR_WHAT: &str = "pcurve_fit_off_bar";
2903
2904pub(crate) fn is_pcurve_off_bar(refusal: &crate::KernelRefusal) -> bool {
2906 matches!(&refusal.class, crate::RefusalClass::NonConvergence { what } if what == PCURVE_OFF_BAR_WHAT)
2907}
2908
2909pub(crate) fn build_pcurve_on_surface_range_classed(
2913 surface: &NurbsSurface,
2914 curve: &NurbsCurve,
2915 edge_start: f64,
2916 edge_end: f64,
2917 forward: bool,
2918 tolerance: f64,
2919 stage: KernelStage,
2920 what: &'static str,
2921) -> Result<NurbsCurve, crate::KernelRefusal> {
2922 use crate::OrRefuse;
2923 let fit = fit_pcurve_on_surface_range(surface, curve, edge_start, edge_end, forward, tolerance)
2924 .or_refuse(stage, what)?;
2925 accept_fit_classed(fit, stage)
2926}
2927
2928pub(crate) fn accept_fit_classed(fit: PcurveFit, stage: KernelStage) -> Result<NurbsCurve, crate::KernelRefusal> {
2931 if fit.report.on_bar() {
2932 return Ok(fit.curve);
2933 }
2934 Err(crate::KernelRefusal {
2935 class: crate::RefusalClass::NonConvergence { what: PCURVE_OFF_BAR_WHAT.into() },
2936 stage,
2937 message: off_bar_message(&fit.report),
2938 })
2939}
2940
2941fn affine_pcurve_on_range(
2963 surface: &NurbsSurface,
2964 curve: &NurbsCurve,
2965 edge_start: f64,
2966 edge_end: f64,
2967 forward: bool,
2968 tolerance: f64,
2969) -> Result<Option<PcurveFit>, String> {
2970 if std::env::var("BREP_AFFINE_RANGE_PCURVE").as_deref() == Ok("0") {
2976 return Ok(None);
2977 }
2978 let Some(inversion) = AffineInversion::of(surface)? else {
2979 return Ok(None);
2980 };
2981 if !(edge_start.is_finite() && edge_end.is_finite() && edge_start < edge_end) {
2982 return Ok(None);
2984 }
2985 let [t0, t1] = curve.domain()?;
2986 let start = edge_start.max(t0);
2987 let end = edge_end.min(t1);
2988 if end - start <= 2.0 * KNOT_IDENTITY_TOL {
2991 return Ok(None);
2992 }
2993 let mut restricted = curve.clone();
2994 if end < t1 - KNOT_IDENTITY_TOL {
2995 restricted = restricted.split(end)?.0;
2996 }
2997 if start > t0 + KNOT_IDENTITY_TOL {
2998 restricted = restricted.split(start)?.1;
2999 }
3000 let mut pcurve = inversion.image_of(&restricted)?;
3001 if !forward {
3002 pcurve = pcurve.reversed()?;
3003 }
3004 let first = pcurve.knots[0];
3005 let last = pcurve.knots[pcurve.knots.len() - 1];
3006 if !(last - first > 0.0) {
3007 return Ok(None);
3008 }
3009 let knots = pcurve
3010 .knots
3011 .iter()
3012 .map(|knot| (knot - first) / (last - first))
3013 .collect::<Vec<_>>();
3014 let pcurve = NurbsCurve::new(pcurve.degree, knots, pcurve.control_points.clone())?;
3015
3016 let scale = 1.0 + curve.evaluate((start + end) / 2.0)?.length();
3022 let bar = tolerance.max(1e-11 * scale);
3023 let mut residual = 0.0_f64;
3024 for index in 0..=32 {
3025 let fraction = index as f64 / 32.0;
3026 let uv = pcurve.evaluate(fraction)?;
3027 let on_carrier = surface.evaluate_extended(uv.x, uv.y)?;
3031 let edge_fraction = if forward { fraction } else { 1.0 - fraction };
3032 let on_edge = curve.evaluate(start + (end - start) * edge_fraction)?;
3033 residual = residual.max(on_carrier.sub(on_edge).length());
3034 if residual > bar {
3035 return Ok(None);
3036 }
3037 }
3038 let samples = pcurve.control_points.len();
3039 crate::imprint::work_profile::constructed("affine_range", 0, pcurve.control_points.len());
3040 Ok(Some(PcurveFit {
3041 curve: pcurve,
3042 report: PcurveFitReport {
3043 residual,
3044 floor: bar,
3049 samples,
3050 exit: PcurveFitExit::Converged,
3051 off_surface: 0.0,
3052 raised: false,
3053 clamped_excursion: 0.0,
3054 clamped_distance: 0.0,
3055 },
3056 }))
3057}
3058
3059fn align_collapsed_endpoints(surface: &NurbsSurface, raw: &mut [[f64; 2]]) -> Result<(), String> {
3060 let anchor = surface.control_points[0][0].point()?;
3061 let mut extent = 0.0_f64;
3062 for control in surface.control_points.iter().flatten() {
3063 extent = extent.max(control.point()?.sub(anchor).length());
3064 }
3065 let pole_band = (1e-10 * (1.0 + extent)).min(LINEAR_TOLERANCE);
3070 for (endpoint, neighbor) in [(0, 1), (raw.len() - 1, raw.len() - 2)] {
3071 let point = surface.evaluate(raw[endpoint][0], raw[endpoint][1])?;
3072 for axis in 0..2 {
3073 let mut candidate = raw[endpoint];
3074 candidate[axis] = raw[neighbor][axis];
3075 if candidate == raw[endpoint]
3076 || surface
3077 .evaluate(candidate[0], candidate[1])?
3078 .sub(point)
3079 .length()
3080 > pole_band
3081 {
3082 continue;
3083 }
3084 let row = if axis == 0 {
3085 surface.iso_curve_v(raw[endpoint][1])?
3086 } else {
3087 surface.iso_curve_u(raw[endpoint][0])?
3088 };
3089 let mut collapsed = true;
3090 for control in &row.control_points {
3091 if control.point()?.sub(point).length() > pole_band {
3092 collapsed = false;
3093 break;
3094 }
3095 }
3096 if collapsed {
3097 raw[endpoint] = candidate;
3098 }
3099 }
3100 }
3101 Ok(())
3102}
3103
3104fn repair_branch_jumps(
3127 surface: &NurbsSurface,
3128 edge_points: &[Vec3],
3129 raw: &mut [[f64; 2]],
3130 tolerance: f64,
3131) -> Result<(), String> {
3132 if raw.len() < 3 {
3133 return Ok(());
3134 }
3135 if surface.is_affine()? {
3138 return Ok(());
3139 }
3140 if std::env::var("BREP_NO_PCURVE_REPAIR").is_ok() {
3142 return Ok(());
3143 }
3144 align_collapsed_endpoints(surface, raw)?;
3148 let ([u0, u1], [v0, v1]) = surface_domains(surface)?;
3149 let u_span = (u1 - u0).abs().max(EPSILON);
3150 let v_span = (v1 - v0).abs().max(EPSILON);
3151 let (closed_u, closed_v) = surface_closedness(surface)?;
3152 let norm_step = |a: [f64; 2], b: [f64; 2]| -> f64 {
3156 let mut du = a[0] - b[0];
3157 if closed_u {
3158 while du > 0.5 * u_span {
3159 du -= u_span;
3160 }
3161 while du < -0.5 * u_span {
3162 du += u_span;
3163 }
3164 }
3165 let mut dv = a[1] - b[1];
3166 if closed_v {
3167 while dv > 0.5 * v_span {
3168 dv -= v_span;
3169 }
3170 while dv < -0.5 * v_span {
3171 dv += v_span;
3172 }
3173 }
3174 ((du / u_span).powi(2) + (dv / v_span).powi(2)).sqrt()
3175 };
3176 const JUMP_THRESHOLD: f64 = 0.2;
3180 let count = raw.len();
3181
3182 let (mut best_start, mut best_len, mut run_start) = (0usize, 1usize, 0usize);
3186 for index in 1..count {
3187 if norm_step(raw[index], raw[index - 1]) > JUMP_THRESHOLD {
3188 if index - run_start > best_len {
3189 best_len = index - run_start;
3190 best_start = run_start;
3191 }
3192 run_start = index;
3193 }
3194 }
3195 if count - run_start > best_len {
3196 best_len = count - run_start;
3197 best_start = run_start;
3198 }
3199 let (spine_lo, spine_hi) = (best_start, best_start + best_len - 1);
3200
3201 let reseat = |edge_point: Vec3,
3207 previous: [f64; 2],
3208 global: [f64; 2]|
3209 -> Result<[f64; 2], String> {
3210 let global_step = norm_step(global, previous);
3211 if global_step <= JUMP_THRESHOLD {
3212 return Ok(global);
3213 }
3214 let seeded =
3215 project_point_to_surface_seeded(surface, edge_point, previous[0], previous[1])?;
3216 let candidate = [seeded.u, seeded.v];
3217 let global_residual = surface
3218 .evaluate(global[0], global[1])?
3219 .sub(edge_point)
3220 .length();
3221 let on_surface = seeded.distance <= 4.0 * global_residual + tolerance.max(1e-12);
3222 if on_surface && norm_step(candidate, previous) < 0.5 * global_step {
3223 if std::env::var("BREP_DEBUG_PCURVE").is_ok() {
3224 eprintln!(
3225 "pcurve repair: jump {global_step:.4} ({global:?}) -> {:.4} ({candidate:?}) res {:.2e}->{:.2e}",
3226 norm_step(candidate, previous),
3227 global_residual,
3228 seeded.distance
3229 );
3230 }
3231 Ok(candidate)
3232 } else {
3233 Ok(global)
3234 }
3235 };
3236
3237 let mut previous = raw[spine_hi];
3251 for index in (spine_hi + 1)..count.saturating_sub(1) {
3252 raw[index] = reseat(edge_points[index], previous, raw[index])?;
3253 previous = raw[index];
3254 }
3255 let mut previous = raw[spine_lo];
3256 for index in (1..spine_lo).rev() {
3257 raw[index] = reseat(edge_points[index], previous, raw[index])?;
3258 previous = raw[index];
3259 }
3260 Ok(())
3261}
3262
3263#[allow(clippy::too_many_arguments)]
3279pub fn fit_pcurve_on_surface_range_dense(
3280 surface: &NurbsSurface,
3281 curve: &NurbsCurve,
3282 edge_start: f64,
3283 edge_end: f64,
3284 forward: bool,
3285 tolerance: f64,
3286 base_samples: usize,
3287 refinement_rounds: usize,
3288 parameter_cap: usize,
3289) -> Result<PcurveFit, String> {
3290 let _wall = crate::wall_profile::Scope::enter(crate::wall_profile::FIT);
3291 crate::imprint::work_profile::add(|c| c.fit_calls += 1);
3292 if !(edge_start.is_finite() && edge_end.is_finite() && edge_start < edge_end) {
3293 return Err("build_pcurve_on_surface_range: invalid edge interval".into());
3294 }
3295 let evaluate_edge = |fraction: f64| {
3296 let edge_fraction = if forward { fraction } else { 1.0 - fraction };
3297 curve.evaluate(edge_start + (edge_end - edge_start) * edge_fraction)
3298 };
3299 let breaks = range_breaks(curve, edge_start, edge_end, forward);
3300 let ask = tolerance.max(PCURVE_REFINEMENT_TOLERANCE);
3301 let fit = fit_station_pcurve(
3302 surface,
3303 &evaluate_edge,
3304 &breaks,
3305 &breaks,
3306 ask,
3307 base_samples,
3308 refinement_rounds,
3309 parameter_cap,
3310 SPAN_FLOOR,
3311 )?;
3312 end_span_challenger(surface, curve, &evaluate_edge, edge_start, edge_end, forward, &breaks, ask, base_samples, refinement_rounds, parameter_cap, fit)
3313}
3314
3315fn native_end_knot_fractions(curve: &NurbsCurve, edge_start: f64, edge_end: f64, forward: bool, pcurve: &NurbsCurve) -> Result<Vec<f64>, String> {
3320 let [q0, q1] = pcurve.domain()?;
3321 let mut interior: Vec<f64> = pcurve.knots.iter().copied().filter(|k| *k > q0 && *k < q1).collect();
3322 interior.dedup();
3323 let (Some(&first), Some(&last)) = (interior.first(), interior.last()) else { return Ok(Vec::new()) };
3324 let (low, high) = (edge_start.min(edge_end), edge_start.max(edge_end));
3325 let span = edge_end - edge_start;
3326 let mut fractions: Vec<f64> = curve
3327 .knots
3328 .iter()
3329 .copied()
3330 .filter(|k| *k > low && *k < high)
3331 .map(|k| {
3332 let along = (k - edge_start) / span;
3333 if forward { along } else { 1.0 - along }
3334 })
3335 .filter(|f| f.is_finite() && ((*f > q0 && *f < first) || (*f > last && *f < q1)))
3336 .collect();
3337 fractions.sort_by(f64::total_cmp);
3338 fractions.dedup();
3339 Ok(fractions)
3340}
3341
3342fn foot_admitted(foot: &crate::SurfaceProjection, [u0, u1]: [f64; 2], [v0, v1]: [f64; 2]) -> bool {
3346 let finite = |p: Vec3| p.x.is_finite() && p.y.is_finite() && p.z.is_finite();
3347 foot.distance.is_finite() && finite(foot.point) && foot.u.is_finite() && foot.v.is_finite() && (u0..=u1).contains(&foot.u) && (v0..=v1).contains(&foot.v)
3348}
3349
3350fn verification_fractions(pcurve: &NurbsCurve, verify: &[f64]) -> Result<Vec<f64>, String> {
3356 let mut fractions = native_probe_fractions(&[pcurve])?;
3357 fractions.extend(pcurve.knots.iter().copied());
3358 fractions.extend(verify.iter().copied());
3359 fractions.retain(|f| f.is_finite() && (0.0..=1.0).contains(f));
3360 fractions.sort_by(f64::total_cmp);
3361 fractions.dedup();
3362 Ok(fractions)
3363}
3364
3365pub(crate) fn floor_admits(old: [f64; 3], new: [f64; 3]) -> bool {
3384 let floor = PCURVE_REFINEMENT_TOLERANCE;
3385 old.iter().chain(new.iter()).all(|v| v.is_finite())
3386 && new[0] < old[0]
3387 && (new[1] <= old[1] || (new[0] <= floor && new[2] <= floor))
3388}
3389
3390fn common_foot(
3398 global: Option<crate::SurfaceProjection>,
3399 reference: Option<crate::SurfaceProjection>,
3400 candidate: Option<crate::SurfaceProjection>,
3401 domain_u: [f64; 2],
3402 domain_v: [f64; 2],
3403) -> Option<crate::SurfaceProjection> {
3404 [global, reference, candidate]
3405 .into_iter()
3406 .flatten()
3407 .filter(|f| foot_admitted(f, domain_u, domain_v))
3408 .min_by(|a, b| a.distance.total_cmp(&b.distance))
3409}
3410
3411pub(crate) fn range_use_probes(curves: &[&NurbsCurve], edge_curve: &NurbsCurve, t0: f64, t1: f64, forward: bool) -> Result<Vec<f64>, String> {
3418 let mut probes = native_probe_fractions(curves)?;
3419 for curve in curves {
3420 probes.extend(curve.knots.iter().copied());
3421 }
3422 let span = t1 - t0;
3423 if span.is_finite() && span != 0.0 {
3424 let (low, high) = (t0.min(t1), t0.max(t1));
3425 let mut knots: Vec<f64> = edge_curve.knots.iter().copied().filter(|k| *k >= low && *k <= high).collect();
3426 knots.push(low);
3427 knots.push(high);
3428 knots.sort_by(f64::total_cmp);
3429 knots.dedup();
3430 let locals: Vec<f64> = [0.25, 0.5, 0.75]
3431 .into_iter()
3432 .chain((1..=TRACKING_ACCEPTANCE_POINTS).map(|index| index as f64 / (TRACKING_ACCEPTANCE_POINTS + 1) as f64))
3433 .collect();
3434 let mut ts = knots.clone();
3435 for pair in knots.windows(2).filter(|w| w[1] > w[0]) {
3436 for &local in &locals {
3437 ts.push(pair[0] + (pair[1] - pair[0]) * local);
3438 }
3439 }
3440 for t in ts {
3441 let along = (t - t0) / span;
3442 probes.push(if forward { along } else { 1.0 - along });
3443 }
3444 }
3445 probes.retain(|f| f.is_finite() && (0.0..=1.0).contains(f));
3446 probes.sort_by(f64::total_cmp);
3447 probes.dedup();
3448 Ok(probes)
3449}
3450
3451#[cfg_attr(not(test), allow(dead_code))]
3459pub(crate) fn range_common_read(
3460 surface: &NurbsSurface,
3461 edge_curve: &NurbsCurve,
3462 t0: f64,
3463 t1: f64,
3464 forward: bool,
3465 old: &NurbsCurve,
3466 new: &NurbsCurve,
3467) -> Result<((f64, f64), (f64, f64)), String> {
3468 let (o, n) = range_common_read_with_excess(surface, edge_curve, t0, t1, forward, old, new)?;
3469 Ok(((o[0], o[1]), (n[0], n[1])))
3470}
3471
3472#[cfg_attr(not(test), allow(dead_code))]
3478pub(crate) fn range_common_read_with_excess(
3479 surface: &NurbsSurface,
3480 edge_curve: &NurbsCurve,
3481 t0: f64,
3482 t1: f64,
3483 forward: bool,
3484 old: &NurbsCurve,
3485 new: &NurbsCurve,
3486) -> Result<([f64; 3], [f64; 3]), String> {
3487 for curve in [old, new] {
3488 if !matches!(curve.domain(), Ok([a, b]) if a == 0.0 && b == 1.0) {
3489 return Err("range common read: a trim not on [0, 1]".into());
3490 }
3491 }
3492 let probes = range_use_probes(&[old, new], edge_curve, t0, t1, forward)?;
3493 let evaluate = |fraction: f64| -> Result<Vec3, String> {
3494 let along = if forward { fraction } else { 1.0 - fraction };
3495 edge_curve.evaluate(t0 + (t1 - t0) * along)
3496 };
3497 common_station_read_with_excess(surface, &evaluate, old, new, &probes)
3498}
3499
3500pub(crate) fn common_station_read(
3513 surface: &NurbsSurface,
3514 evaluate_edge: &dyn Fn(f64) -> Result<Vec3, String>,
3515 legacy: &NurbsCurve,
3516 candidate: &NurbsCurve,
3517 probes: &[f64],
3518) -> Result<((f64, f64), (f64, f64)), String> {
3519 let (old, new) = common_station_read_with_excess(surface, evaluate_edge, legacy, candidate, probes)?;
3520 Ok(((old[0], old[1]), (new[0], new[1])))
3521}
3522
3523fn tracking_closed_foot_enabled() -> bool {
3532 let enabled = crate::switch!("BREP_TRACKING_CLOSED_FOOT", true);
3533 enabled
3534}
3535
3536
3537pub(crate) fn common_station_read_with_excess(
3538 surface: &NurbsSurface,
3539 evaluate_edge: &dyn Fn(f64) -> Result<Vec3, String>,
3540 legacy: &NurbsCurve,
3541 candidate: &NurbsCurve,
3542 probes: &[f64],
3543) -> Result<([f64; 3], [f64; 3]), String> {
3544 let (domain_u, domain_v) = surface_domains(surface)?;
3545 let finite = |p: Vec3| p.x.is_finite() && p.y.is_finite() && p.z.is_finite();
3546 let mut read = ([0.0_f64, 0.0, f64::NEG_INFINITY], [0.0_f64, 0.0, f64::NEG_INFINITY]);
3550 let same = std::ptr::eq(legacy, candidate);
3555 let ellipsoid = if same && surface.analytic().is_none() { surface.affine_sphere() } else { None };
3562 let analytic = if same && ellipsoid.is_none() && tracking_closed_foot_enabled() {
3578 surface.analytic().filter(|analytic| !matches!(analytic, crate::AnalyticSurface::Plane { .. }))
3579 } else {
3580 None
3581 };
3582 for &fraction in probes {
3583 let point = evaluate_edge(fraction)?;
3584 let old_uv = legacy.evaluate(fraction)?;
3585 let new_uv = if same { old_uv } else { candidate.evaluate(fraction)? };
3586 let old_image = surface.evaluate_extended(old_uv.x, old_uv.y)?;
3587 let new_image = if same { old_image } else { surface.evaluate_extended(new_uv.x, new_uv.y)? };
3588 if !(finite(point) && finite(old_image) && finite(new_image)) {
3589 return Err(format!("common station read: non-finite point at fraction {fraction}"));
3590 }
3591 let closed_form = ellipsoid.and_then(|ellipsoid| ellipsoid.project(surface, point)).or_else(|| {
3592 analytic
3593 .and_then(|analytic| analytic.project(surface, point))
3594 .filter(|foot| foot_admitted(foot, domain_u, domain_v))
3595 });
3596 let foot = if let Some(foot) = closed_form {
3597 common_foot(Some(foot), Some(foot), Some(foot), domain_u, domain_v)
3598 } else {
3599 let reference_foot = memo_seeded_foot(surface, point, old_uv.x, old_uv.y);
3600 let candidate_foot = if same {
3601 reference_foot
3602 } else {
3603 memo_seeded_foot(surface, point, new_uv.x, new_uv.y)
3604 };
3605 common_foot(
3606 memo_global_foot(surface, point),
3607 reference_foot,
3608 candidate_foot,
3609 domain_u,
3610 domain_v,
3611 )
3612 }
3613 .ok_or_else(|| format!("common station read: no admitted foot at fraction {fraction}"))?;
3614 let values = [
3615 old_image.sub(foot.point).length(),
3616 old_image.sub(point).length(),
3617 new_image.sub(foot.point).length(),
3618 new_image.sub(point).length(),
3619 ];
3620 if values.iter().any(|v| !v.is_finite()) {
3621 return Err(format!("common station read: non-finite distance at fraction {fraction}"));
3622 }
3623 if !foot.distance.is_finite() {
3624 return Err(format!("common station read: non-finite foot distance at fraction {fraction}"));
3625 }
3626 read.0[0] = read.0[0].max(values[0]);
3627 read.0[1] = read.0[1].max(values[1]);
3628 read.0[2] = read.0[2].max(values[1] - foot.distance);
3629 read.1[0] = read.1[0].max(values[2]);
3630 read.1[1] = read.1[1].max(values[3]);
3631 read.1[2] = read.1[2].max(values[3] - foot.distance);
3632 }
3633 Ok(read)
3634}
3635
3636fn edge_end_span_fractions(curve: &NurbsCurve, edge_start: f64, edge_end: f64, forward: bool) -> Vec<f64> {
3641 let (low, high) = (edge_start.min(edge_end), edge_start.max(edge_end));
3642 let mut knots: Vec<f64> = curve.knots.iter().copied().filter(|k| *k > low && *k < high).collect();
3643 knots.dedup();
3644 let spans = match (knots.first(), knots.last()) {
3645 (Some(&first), Some(&last)) => vec![(low, first), (last, high)],
3646 _ => vec![(low, high)],
3647 };
3648 let span = edge_end - edge_start;
3649 let mut out = Vec::new();
3650 for (a, b) in spans {
3651 if !(b > a) {
3652 continue;
3653 }
3654 for local in [0.25, 0.5, 0.75].into_iter().chain((1..=TRACKING_ACCEPTANCE_POINTS).map(|index| index as f64 / (TRACKING_ACCEPTANCE_POINTS + 1) as f64)) {
3655 let along = (a + (b - a) * local - edge_start) / span;
3656 let fraction = if forward { along } else { 1.0 - along };
3657 if fraction.is_finite() && (0.0..=1.0).contains(&fraction) {
3658 out.push(fraction);
3659 }
3660 }
3661 }
3662 out.sort_by(f64::total_cmp);
3663 out.dedup();
3664 out
3665}
3666
3667const WORST_SPANS: usize = 4;
3669const WORST_SPAN_SEEDS: usize = 7;
3671
3672fn legacy_worst_span_seeds(
3681 evaluate_edge: &dyn Fn(f64) -> Result<Vec3, String>,
3682 surface: &NurbsSurface,
3683 pcurve: &NurbsCurve,
3684 bar: f64,
3685 extra_probes: &[f64],
3686) -> Result<Vec<f64>, String> {
3687 let [q0, q1] = pcurve.domain()?;
3688 let mut knots: Vec<f64> = pcurve.knots.iter().copied().filter(|k| *k >= q0 && *k <= q1).collect();
3689 knots.dedup();
3690 let locals: Vec<f64> = [0.25, 0.5, 0.75]
3691 .into_iter()
3692 .chain((1..=TRACKING_ACCEPTANCE_POINTS).map(|index| index as f64 / (TRACKING_ACCEPTANCE_POINTS + 1) as f64))
3693 .collect();
3694 let mut over: Vec<(f64, f64, f64)> = Vec::new();
3695 for span in knots.windows(2).filter(|w| w[1] > w[0]) {
3696 let mut worst = 0.0_f64;
3697 let inside = extra_probes.iter().copied().filter(|f| *f > span[0] && *f < span[1]);
3698 for fraction in locals.iter().map(|local| span[0] + (span[1] - span[0]) * local).chain(inside) {
3699 let uv = pcurve.evaluate(fraction)?;
3700 let deviation = surface.evaluate_extended(uv.x, uv.y)?.sub(evaluate_edge(fraction)?).length();
3701 if !deviation.is_finite() {
3702 return Err(format!("worst-span read: non-finite deviation at fraction {fraction}"));
3703 }
3704 worst = worst.max(deviation);
3705 }
3706 if worst > bar {
3707 over.push((worst, span[0], span[1]));
3708 }
3709 }
3710 over.sort_by(|a, b| b.0.total_cmp(&a.0).then(a.1.total_cmp(&b.1)));
3711 over.truncate(WORST_SPANS);
3712 Ok(over
3713 .into_iter()
3714 .flat_map(|(_, lo, hi)| (1..=WORST_SPAN_SEEDS).map(move |index| lo + (hi - lo) * index as f64 / (WORST_SPAN_SEEDS + 1) as f64))
3715 .collect())
3716}
3717
3718#[derive(Clone, Copy, Debug, PartialEq, Eq)]
3720enum ChallengerTrigger {
3721 Deviation,
3723 Tracking,
3727}
3728
3729fn challenger_trigger(residual: f64, off_surface: f64, ask: f64, tracking: impl FnOnce() -> Option<f64>) -> Option<ChallengerTrigger> {
3739 if residual > ask + off_surface {
3740 return Some(ChallengerTrigger::Deviation);
3741 }
3742 if !(off_surface > ask) {
3743 return None;
3744 }
3745 match tracking() {
3746 Some(value) if value.is_finite() && value > ask => Some(ChallengerTrigger::Tracking),
3747 _ => None,
3748 }
3749}
3750
3751#[allow(clippy::too_many_arguments)]
3770fn end_span_challenger(
3771 surface: &NurbsSurface,
3772 curve: &NurbsCurve,
3773 evaluate_edge: &dyn Fn(f64) -> Result<Vec3, String>,
3774 edge_start: f64,
3775 edge_end: f64,
3776 forward: bool,
3777 breaks: &[f64],
3778 ask: f64,
3779 base_samples: usize,
3780 refinement_rounds: usize,
3781 parameter_cap: usize,
3782 legacy: PcurveFit,
3783) -> Result<PcurveFit, String> {
3784 if !(legacy.report.residual > ask + legacy.report.off_surface) {
3792 return Ok(legacy);
3793 }
3794 let _feet = FootMemoScope::open(surface);
3797 let Ok(end_knots) = native_end_knot_fractions(curve, edge_start, edge_end, forward, &legacy.curve) else { return Ok(legacy) };
3798 let edge_end_probes = edge_end_span_fractions(curve, edge_start, edge_end, forward);
3812 let Ok(mut fixed) = native_probe_fractions(&[&legacy.curve]) else { return Ok(legacy) };
3819 fixed.extend(edge_end_probes.iter().copied());
3820 let (low, high) = (edge_start.min(edge_end), edge_start.max(edge_end));
3821 let mut edge_knots: Vec<f64> = curve.knots.iter().copied().filter(|k| *k >= low && *k <= high).collect();
3822 edge_knots.push(low);
3823 edge_knots.push(high);
3824 edge_knots.sort_by(f64::total_cmp);
3825 edge_knots.dedup();
3826 let to_fraction = |t: f64| {
3827 let along = (t - edge_start) / (edge_end - edge_start);
3828 if forward { along } else { 1.0 - along }
3829 };
3830 for span in edge_knots.windows(2).filter(|w| w[1] > w[0]) {
3831 for local in [0.25, 0.5, 0.75] {
3832 fixed.push(to_fraction(span[0] + (span[1] - span[0]) * local));
3833 }
3834 }
3835 fixed.extend(edge_knots.iter().map(|&t| to_fraction(t)));
3836 fixed.extend(end_knots.iter().copied());
3837 fixed.extend(legacy.curve.knots.iter().copied());
3838 fixed.retain(|f| f.is_finite() && (0.0..=1.0).contains(f));
3839 fixed.sort_by(f64::total_cmp);
3840 fixed.dedup();
3841 let trigger = challenger_trigger(legacy.report.residual, legacy.report.off_surface, ask, || {
3842 common_station_read(surface, evaluate_edge, &legacy.curve, &legacy.curve, &fixed).ok().map(|((tracking, _), _)| tracking)
3843 });
3844 let Some(trigger) = trigger else { return Ok(legacy) };
3845 let Ok(worst_seeds) = legacy_worst_span_seeds(evaluate_edge, surface, &legacy.curve, ask + legacy.report.off_surface, &edge_end_probes) else { return Ok(legacy) };
3846 if trigger == ChallengerTrigger::Deviation && end_knots.is_empty() && worst_seeds.is_empty() {
3850 return Ok(legacy);
3851 }
3852 let mut stations: Vec<f64> = breaks.iter().copied().chain(end_knots.iter().copied()).chain(worst_seeds.iter().copied()).collect();
3853 stations.sort_by(f64::total_cmp);
3854 stations.dedup();
3855 let initial = base_samples.max(1).checked_add(1).and_then(|count| count.checked_add(stations.len()));
3860 if initial.is_none_or(|count| count > parameter_cap) {
3861 return Ok(legacy);
3862 }
3863 let Ok(candidate) = fit_station_pcurve_mode(surface, evaluate_edge, &stations, breaks, ask, base_samples, refinement_rounds, parameter_cap, SPAN_FLOOR, true, Some(&legacy.curve), &fixed) else {
3864 return Ok(legacy);
3865 };
3866 if !(candidate.report.residual.is_finite() && candidate.report.off_surface.is_finite() && candidate.report.clamped_excursion.is_finite() && candidate.report.clamped_distance.is_finite()) {
3867 return Ok(legacy);
3868 }
3869 let Ok(mut probes) = native_probe_fractions(&[&candidate.curve]) else { return Ok(legacy) };
3873 probes.extend(fixed.iter().copied());
3874 probes.extend(candidate.curve.knots.iter().copied());
3875 probes.retain(|f| f.is_finite() && (0.0..=1.0).contains(f));
3876 probes.sort_by(f64::total_cmp);
3877 probes.dedup();
3878 let readings = common_station_read_with_excess(surface, evaluate_edge, &legacy.curve, &candidate.curve, &probes);
3879 let accepted = matches!(&readings, Ok((old, new)) if floor_admits(*old, *new));
3880 if station_fit_tracing() {
3881 eprintln!(
3882 "STATION-FIT end-span challenger: trigger={trigger:?} end_knots={} worst_span_seeds={} edge_end_probes={} legacy={:?}/{:e} candidate={:?}/{:e} common={readings:?} decision={}",
3883 end_knots.len(), worst_seeds.len(), edge_end_probes.len(), legacy.report.exit, legacy.report.residual, candidate.report.exit, candidate.report.residual,
3884 if accepted { "candidate" } else { "legacy" }
3885 );
3886 }
3887 Ok(if accepted { candidate } else { legacy })
3888}
3889
3890
3891#[allow(clippy::too_many_arguments)]
3894pub fn build_pcurve_on_surface_range_dense(
3895 surface: &NurbsSurface,
3896 curve: &NurbsCurve,
3897 edge_start: f64,
3898 edge_end: f64,
3899 forward: bool,
3900 tolerance: f64,
3901 base_samples: usize,
3902 refinement_rounds: usize,
3903 parameter_cap: usize,
3904) -> Result<NurbsCurve, String> {
3905 accept_fit(fit_pcurve_on_surface_range_dense(
3906 surface,
3907 curve,
3908 edge_start,
3909 edge_end,
3910 forward,
3911 tolerance,
3912 base_samples,
3913 refinement_rounds,
3914 parameter_cap,
3915 )?)
3916}
3917
3918pub(crate) fn range_breaks(
3928 curve: &NurbsCurve,
3929 edge_start: f64,
3930 edge_end: f64,
3931 forward: bool,
3932) -> Vec<f64> {
3933 let mut fractions = Vec::new();
3934 let span = edge_end - edge_start;
3935 if !(span.abs() > 0.0) {
3936 return fractions;
3937 }
3938 let (low, high) = (edge_start.min(edge_end), edge_start.max(edge_end));
3939 let mut index = 0;
3940 while index < curve.knots.len() {
3941 let value = curve.knots[index];
3942 let run = curve.knots[index..]
3943 .iter()
3944 .take_while(|knot| **knot == value)
3945 .count();
3946 if value > low && value < high && run >= curve.degree.max(1) {
3947 let along = (value - edge_start) / span;
3948 fractions.push(if forward { along } else { 1.0 - along });
3949 }
3950 index += run;
3951 }
3952 fractions.sort_by(f64::total_cmp);
3953 fractions
3954}
3955
3956#[allow(clippy::too_many_arguments)]
4007pub fn fit_pcurve_on_surface_stations(
4008 surface: &NurbsSurface,
4009 stations: &dyn Fn(f64) -> Result<Vec3, String>,
4010 breaks: &[f64],
4011 tolerance: f64,
4012 base_samples: usize,
4013 refinement_rounds: usize,
4014 parameter_cap: usize,
4015) -> Result<PcurveFit, String> {
4016 let _wall = crate::wall_profile::Scope::enter(crate::wall_profile::FIT);
4017 crate::imprint::work_profile::add(|c| c.fit_calls += 1);
4018 fit_station_pcurve(
4019 surface, stations, breaks, &[], tolerance.max(PCURVE_REFINEMENT_TOLERANCE),
4020 base_samples, refinement_rounds, parameter_cap, SPAN_FLOOR,
4021 )
4022}
4023
4024pub(crate) fn analytic_station_pcurve(
4028 surface: &NurbsSurface,
4029 stations: &dyn Fn(f64) -> Result<Vec3, String>,
4030 tolerance: f64,
4031) -> Result<NurbsCurve, String> {
4032 if surface.analytic().is_none() {
4033 return Err("analytic pcurve requires an analytic carrier".into());
4034 }
4035 let mut breaks = Vec::new();
4036 for _ in 0..4 {
4037 let fit = fit_station_pcurve(surface, stations, &breaks, &[], tolerance, 64, 64, 8192, 1e-10)?;
4038 if fit.report.residual > tolerance || fit.report.off_surface > tolerance {
4039 return Err(format!(
4040 "analytic pcurve construction missed its contract: {:?}",
4041 fit.report
4042 ));
4043 }
4044 let mut failed = Vec::new();
4045 for pair in fit.curve.knots.windows(2) {
4048 if pair[1] <= pair[0] {
4049 continue;
4050 }
4051 for local in [
4052 0.06943184420297371,
4053 0.33000947820757187,
4054 0.6699905217924281,
4055 0.9305681557970262,
4056 ] {
4057 let t = pair[0] + (pair[1] - pair[0]) * local;
4058 let uv = fit.curve.evaluate(t)?;
4059 if surface
4060 .evaluate_extended(uv.x, uv.y)?
4061 .sub(stations(t)?)
4062 .length()
4063 > tolerance
4064 {
4065 failed.push(t);
4066 }
4067 }
4068 }
4069 if failed.is_empty() {
4070 return Ok(fit.curve);
4071 }
4072 if breaks.len() + failed.len() > 8192 {
4073 break;
4074 }
4075 breaks.extend(failed);
4076 breaks.sort_by(f64::total_cmp);
4077 breaks.dedup();
4078 }
4079 Err("analytic pcurve failed independent knot-span witnesses".into())
4080}
4081
4082#[allow(clippy::too_many_arguments)]
4083fn fit_station_pcurve(
4084 surface: &NurbsSurface,
4085 stations: &dyn Fn(f64) -> Result<Vec3, String>,
4086 breaks: &[f64],
4087 corners: &[f64],
4088 tolerance: f64,
4089 base_samples: usize,
4090 refinement_rounds: usize,
4091 parameter_cap: usize,
4092 span_floor: f64,
4093) -> Result<PcurveFit, String> {
4094 fit_station_pcurve_mode(surface, stations, breaks, corners, tolerance, base_samples, refinement_rounds, parameter_cap, span_floor, false, None, &[])
4095}
4096
4097#[allow(clippy::too_many_arguments)]
4116fn fit_station_pcurve_mode(
4117 surface: &NurbsSurface,
4118 stations: &dyn Fn(f64) -> Result<Vec3, String>,
4119 breaks: &[f64],
4120 corners: &[f64],
4121 tolerance: f64,
4122 base_samples: usize,
4123 refinement_rounds: usize,
4124 parameter_cap: usize,
4125 span_floor: f64,
4126 track_projection: bool,
4127 reference: Option<&NurbsCurve>,
4128 verify: &[f64],
4129) -> Result<PcurveFit, String> {
4130 let domains = if track_projection { Some(surface_domains(surface)?) } else { None };
4132 let tracking_of = |represented: Vec3, edge_point: Vec3, uv: Vec3, fraction: f64| -> Result<(f64, [f64; 2], f64), String> {
4139 let (domain_u, domain_v) = domains.ok_or_else(|| "station tracking: legacy mode".to_string())?;
4140 let finite = |p: Vec3| p.x.is_finite() && p.y.is_finite() && p.z.is_finite();
4141 let reference_seed = match reference {
4142 Some(curve) => curve.evaluate(fraction).ok().and_then(|seed| memo_seeded_foot(surface, edge_point, seed.x, seed.y)),
4143 None => None,
4144 };
4145 let foot = common_foot(
4148 memo_global_foot(surface, edge_point),
4149 reference_seed,
4150 memo_seeded_foot(surface, edge_point, uv.x, uv.y),
4151 domain_u,
4152 domain_v,
4153 )
4154 .ok_or_else(|| "station tracking: no admitted foot".to_string())?;
4155 let tracking = represented.sub(foot.point).length();
4156 if !(finite(represented) && tracking.is_finite()) {
4157 return Err("station tracking: non-finite reading".into());
4158 }
4159 Ok((tracking, [foot.u, foot.v], foot.distance))
4160 };
4161 let mut tracking_unmet = false;
4163 let evaluate_edge = stations;
4164 let base_samples = base_samples.max(1);
4165 let mut parameters = (0..=base_samples)
4174 .map(|index| index as f64 / base_samples as f64)
4175 .collect::<Vec<_>>();
4176 let mut joins = Vec::with_capacity(corners.len());
4189 for &fraction in breaks {
4190 if !(fraction > 0.0 && fraction < 1.0) {
4191 continue;
4192 }
4193 let corner = corners.contains(&fraction);
4194 let at = parameters.partition_point(|parameter| *parameter < fraction);
4195 let near_left = at > 0 && fraction - parameters[at - 1] <= span_floor;
4196 let near_right = at < parameters.len() && parameters[at] - fraction <= span_floor;
4197 if near_left || near_right {
4198 if corner {
4202 joins.push(if near_right { parameters[at] } else { parameters[at - 1] });
4203 }
4204 continue;
4205 }
4206 parameters.insert(at, fraction);
4207 if corner {
4208 joins.push(fraction);
4209 }
4210 }
4211 let mut edge_points = parameters
4214 .iter()
4215 .map(|fraction| evaluate_edge(*fraction))
4216 .collect::<Result<Vec<_>, _>>()?;
4217 let mut off_surface = 0.0_f64;
4220 let mut raw = Vec::with_capacity(edge_points.len());
4221 let mut gaps = Vec::with_capacity(edge_points.len());
4222 for point in &edge_points {
4223 let (parameter, gap) = invert_checked(surface, *point)?;
4224 off_surface = off_surface.max(gap);
4225 raw.push(parameter);
4226 gaps.push(gap);
4227 }
4228 repair_branch_jumps(surface, &edge_points, &mut raw, tolerance)?;
4229 let (mut pcurve, mut excursion, mut distance) =
4230 build_interpolant_joined(surface, &raw, ¶meters, &joins)?;
4231
4232 let mut cap = parameter_cap.max(parameters.len());
4233 let mut rounds = refinement_rounds;
4234 let mut raised = false;
4235 loop {
4236 let mut exit = PcurveFitExit::RoundBudget;
4237 let mut converged_max = None;
4238 let mut tracking_met = false;
4241 for _ in 0..rounds {
4242 if parameters.len() >= cap {
4243 exit = PcurveFitExit::SampleCeiling;
4244 break;
4245 }
4246 let target = tolerance;
4254 let mut candidates = Vec::new();
4255 let mut round_max = 0.0_f64;
4256 let mut truncated = false;
4257 let mut skipped_narrow = false;
4258 let worst_first = worst_first();
4259 'spans: for index in 0..parameters.len() - 1 {
4260 if parameters[index + 1] - parameters[index] < span_floor {
4269 skipped_narrow = true;
4270 continue;
4271 }
4272 for local in [0.25, 0.5, 0.75] {
4273 if !worst_first && parameters.len() + candidates.len() >= cap {
4274 truncated = true;
4275 break 'spans;
4276 }
4277 let fraction =
4278 parameters[index] + (parameters[index + 1] - parameters[index]) * local;
4279 let uv = pcurve.evaluate(fraction)?;
4280 let represented = surface.evaluate_extended(uv.x, uv.y)?;
4281 let edge_point = evaluate_edge(fraction)?;
4282 let deviation = represented.sub(edge_point).length();
4283 let (reading, foot) = if track_projection {
4286 let (tracking, foot_uv, foot_gap) = tracking_of(represented, edge_point, uv, fraction)?;
4287 (tracking, Some((foot_uv, foot_gap)))
4288 } else {
4289 (deviation, None)
4290 };
4291 round_max = round_max.max(reading);
4292 if reading <= target {
4293 continue;
4294 }
4295 candidates.push((index, fraction, edge_point, uv, reading, foot));
4296 }
4297 }
4298 let mut verify_blocked = false;
4311 if track_projection && candidates.is_empty() && !truncated && !skipped_narrow {
4312 for fraction in verification_fractions(&pcurve, verify)? {
4313 let index = parameters.partition_point(|parameter| *parameter <= fraction).saturating_sub(1).min(parameters.len() - 2);
4314 let uv = pcurve.evaluate(fraction)?;
4315 let represented = surface.evaluate_extended(uv.x, uv.y)?;
4316 let edge_point = evaluate_edge(fraction)?;
4317 let (tracking, foot_uv, foot_gap) = tracking_of(represented, edge_point, uv, fraction)?;
4318 round_max = round_max.max(tracking);
4319 if tracking <= target {
4320 continue;
4321 }
4322 if fraction - parameters[index] <= span_floor || parameters[index + 1] - fraction <= span_floor {
4323 verify_blocked = true;
4324 continue;
4325 }
4326 if let Some(last) = candidates.last_mut() {
4329 if last.0 == index && fraction - last.1 <= span_floor {
4330 if tracking > last.4 {
4331 *last = (index, fraction, edge_point, uv, tracking, Some((foot_uv, foot_gap)));
4332 }
4333 continue;
4334 }
4335 }
4336 candidates.push((index, fraction, edge_point, uv, tracking, Some((foot_uv, foot_gap))));
4337 }
4338 }
4339 tracking_unmet = track_projection && round_max > target;
4340 let room = cap.saturating_sub(parameters.len());
4350 if candidates.len() > room {
4351 truncated = true;
4352 let mut order: Vec<usize> = (0..candidates.len()).collect();
4353 order.sort_by(|&a, &b| candidates[b].4.total_cmp(&candidates[a].4).then(a.cmp(&b)));
4354 order.truncate(room);
4355 order.sort_unstable();
4356 candidates = order.into_iter().map(|index| candidates[index]).collect();
4357 }
4358 let mut inserts = Vec::with_capacity(candidates.len());
4359 for (index, fraction, edge_point, uv, _, foot) in candidates {
4360 let (parameter, gap) = match foot {
4364 Some(placed) => placed,
4365 None => invert_near(surface, edge_point, [uv.x, uv.y], gaps[index].max(gaps[index + 1]))?,
4366 };
4367 inserts.push((index + 1, fraction, edge_point, parameter, gap));
4368 }
4369 if station_fit_tracing() {
4370 eprintln!(
4371 "STATION-FIT round: samples={} target={target:.3e} round_max={round_max:.3e} inserts={} truncated={truncated}{}",
4372 parameters.len(),
4373 inserts.len(),
4374 if track_projection { " mode=tracking" } else { "" }
4376 );
4377 }
4378 if inserts.is_empty() {
4379 exit = if truncated {
4380 PcurveFitExit::SampleCeiling
4381 } else if skipped_narrow {
4382 PcurveFitExit::SpanFloor
4385 } else if track_projection {
4386 tracking_met = !verify_blocked;
4395 PcurveFitExit::Stalled
4396 } else {
4397 converged_max = Some(round_max);
4398 PcurveFitExit::Converged
4399 };
4400 break;
4401 }
4402 for (index, fraction, edge_point, parameter, gap) in inserts.into_iter().rev() {
4403 parameters.insert(index, fraction);
4404 edge_points.insert(index, edge_point);
4405 raw.insert(index, parameter);
4406 gaps.insert(index, gap);
4407 off_surface = off_surface.max(gap);
4408 }
4409 repair_branch_jumps(surface, &edge_points, &mut raw, tolerance)?;
4413 let rebuilt = build_interpolant_joined(surface, &raw, ¶meters, &joins)?;
4414 pcurve = rebuilt.0;
4415 excursion = rebuilt.1;
4416 distance = rebuilt.2;
4417 if truncated {
4418 exit = PcurveFitExit::SampleCeiling;
4419 break;
4420 }
4421 }
4422 let residual = match converged_max {
4423 Some(measured) => measured,
4424 None => {
4425 station_residual(surface, evaluate_edge, &pcurve, ¶meters, tolerance, &mut off_surface)?
4426 }
4427 };
4428 if station_fit_tracing() {
4429 eprintln!(
4430 "STATION-FIT pass raised={raised} exit={exit:?} samples={} residual={residual:.3e} off_surface={off_surface:.3e}",
4431 parameters.len()
4432 );
4433 if residual > tolerance + off_surface && (exit == PcurveFitExit::Converged || raised) {
4434 let (mut worst, mut at) = (0.0f64, 0usize);
4437 for (index, span) in parameters.windows(2).enumerate() {
4438 let fraction = 0.5 * (span[0] + span[1]);
4439 let uv = pcurve.evaluate(fraction)?;
4440 let deviation = surface.evaluate_extended(uv.x, uv.y)?.sub(evaluate_edge(fraction)?).length();
4441 if deviation > worst {
4442 worst = deviation;
4443 at = index;
4444 }
4445 }
4446 let ([u0, u1], [v0, v1]) = surface_domains(surface)?;
4447 let (closed_u, closed_v) = surface_closedness(surface)?;
4448 eprintln!(
4449 "STATION-FIT OFF BAR: worst {worst:.3e} between stations {at} and {}; surface degree {}x{} net {}x{} domain u[{u0},{u1}] v[{v0},{v1}] closed ({closed_u},{closed_v}) analytic {:?}",
4450 at + 1,
4451 surface.degree_u,
4452 surface.degree_v,
4453 surface.control_points.len(),
4454 surface.control_points[0].len(),
4455 surface.analytic().map(|_| "yes").unwrap_or("no")
4456 );
4457 {
4458 let fraction = 0.5 * (parameters[at] + parameters[at + 1]);
4459 let uv = pcurve.evaluate(fraction)?;
4460 let image = surface.evaluate_extended(uv.x, uv.y)?;
4461 let station = evaluate_edge(fraction)?;
4462 let foot = project_point_to_surface(surface, station)?;
4463 let seeded = project_point_to_surface_seeded(surface, station, raw[at][0], raw[at][1])?;
4464 eprintln!(
4465 " at the worst midpoint: deviation {:.4e}, station gap {:.4e} (seeded {:.4e}), image-to-foot {:.4e} (to seeded foot {:.4e}), foot uv ({:.7}, {:.7}) seeded ({:.7}, {:.7}) image uv ({:.7}, {:.7})",
4466 image.sub(station).length(), foot.distance, seeded.distance, image.sub(foot.point).length(), image.sub(seeded.point).length(), foot.u, foot.v, seeded.u, seeded.v, uv.x, uv.y
4467 );
4468 }
4469 let lo = at.saturating_sub(3);
4470 let hi = (at + 4).min(parameters.len() - 1);
4471 for index in lo..=hi {
4472 eprintln!(
4473 " station {index}: fraction {:.6} uv ({:.6}, {:.6}) point ({:.4}, {:.4}, {:.4})",
4474 parameters[index], raw[index][0], raw[index][1], edge_points[index].x, edge_points[index].y, edge_points[index].z
4475 );
4476 }
4477 }
4478 }
4479 if !track_projection && exit == PcurveFitExit::SpanFloor && residual <= tolerance + off_surface {
4486 exit = PcurveFitExit::Converged;
4487 }
4488 if tracking_met && residual <= tolerance {
4489 exit = PcurveFitExit::Converged;
4490 }
4491 if exit != PcurveFitExit::Converged
4492 && !raised
4493 && (residual > tolerance + off_surface || tracking_unmet)
4494 && cap < PCURVE_RAISED_SAMPLES
4495 {
4496 raised = true;
4497 cap = PCURVE_RAISED_SAMPLES;
4498 rounds = RAISED_ROUNDS;
4505 continue;
4506 }
4507 crate::imprint::work_profile::constructed("station_fit", parameters.len(), pcurve.control_points.len());
4508 return Ok(PcurveFit {
4509 curve: pcurve,
4510 report: PcurveFitReport {
4511 residual,
4512 floor: tolerance,
4513 samples: parameters.len(),
4514 exit,
4515 off_surface,
4516 raised,
4517 clamped_excursion: excursion,
4518 clamped_distance: distance,
4519 },
4520 });
4521 }
4522}
4523
4524pub fn build_pcurve_on_surface_stations(
4527 surface: &NurbsSurface,
4528 stations: &dyn Fn(f64) -> Result<Vec3, String>,
4529 breaks: &[f64],
4530 tolerance: f64,
4531 base_samples: usize,
4532 refinement_rounds: usize,
4533 parameter_cap: usize,
4534) -> Result<NurbsCurve, String> {
4535 accept_fit(fit_pcurve_on_surface_stations(
4536 surface,
4537 stations,
4538 breaks,
4539 tolerance,
4540 base_samples,
4541 refinement_rounds,
4542 parameter_cap,
4543 )?)
4544}
4545
4546fn station_residual(
4554 surface: &NurbsSurface,
4555 stations: &dyn Fn(f64) -> Result<Vec3, String>,
4556 pcurve: &NurbsCurve,
4557 parameters: &[f64],
4558 tolerance: f64,
4559 off_surface: &mut f64,
4560) -> Result<f64, String> {
4561 let mut worst = 0.0_f64;
4562 let mut read = |fraction: f64| -> Result<(), String> {
4563 let uv = pcurve.evaluate(fraction)?;
4564 let represented = surface.evaluate_extended(uv.x, uv.y)?;
4565 let station = stations(fraction)?;
4566 let deviation = represented.sub(station).length();
4567 worst = worst.max(deviation);
4568 if deviation > tolerance + *off_surface {
4569 *off_surface = off_surface.max(invert_checked(surface, station)?.1);
4570 }
4571 Ok(())
4572 };
4573 for span in parameters.windows(2) {
4574 for local in [0.25, 0.5, 0.75] {
4575 read(span[0] + (span[1] - span[0]) * local)?;
4576 }
4577 }
4578 Ok(worst)
4579}
4580
4581
4582