use crate::{
interpolate_curve, project_point_to_surface, project_point_to_surface_seeded, AnalyticSurface,
DiagnosticSeverity, KernelDiagnostics, KernelStage, KnotVector, NurbsCurve, NurbsSurface, Vec3,
Vec4, KNOT_IDENTITY_TOL,
};
const EPSILON: f64 = crate::tolerance::FP_FLOOR;
const LINEAR_TOLERANCE: f64 = crate::tolerance::DEFAULT_MODEL;
struct PcurvePhaseClock {
started: Option<web_time::Instant>,
phase: &'static str,
samples: usize,
tracking: bool,
}
impl PcurvePhaseClock {
fn new(phase: &'static str, samples: usize, tracking: bool) -> Self {
Self { started: crate::profile::profile_enabled().then(web_time::Instant::now), phase, samples, tracking }
}
}
impl Drop for PcurvePhaseClock {
fn drop(&mut self) {
if let Some(started) = self.started {
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));
}
}
}
fn surface_domains(surface: &NurbsSurface) -> Result<([f64; 2], [f64; 2]), String> {
Ok((
KnotVector::new(surface.knots_u.clone(), surface.degree_u)?.domain(),
KnotVector::new(surface.knots_v.clone(), surface.degree_v)?.domain(),
))
}
fn surface_closedness(surface: &NurbsSurface) -> Result<(bool, bool), String> {
surface.closed_directions()
}
thread_local! {
static PCURVE_REJECT_BOUNDS: std::cell::Cell<bool> = const { std::cell::Cell::new(false) };
}
struct PcurveRejectScope(bool);
impl PcurveRejectScope {
fn open(enabled: bool) -> Self {
Self(PCURVE_REJECT_BOUNDS.with(|state| state.replace(enabled)))
}
}
impl Drop for PcurveRejectScope {
fn drop(&mut self) { PCURVE_REJECT_BOUNDS.with(|state| state.set(self.0)); }
}
thread_local! {
static PCURVE_STACK_POINT: std::cell::Cell<bool> = const { std::cell::Cell::new(false) };
}
struct PcurveStackPointScope(bool);
impl PcurveStackPointScope {
fn open(enabled: bool) -> Self { Self(PCURVE_STACK_POINT.with(|state| state.replace(enabled))) }
}
impl Drop for PcurveStackPointScope {
fn drop(&mut self) { PCURVE_STACK_POINT.with(|state| state.set(self.0)); }
}
fn section_extended_point(surface: &NurbsSurface, u: f64, v: f64, enabled: bool) -> Result<Vec3, String> {
if enabled && u.is_finite() && v.is_finite()
&& surface.degree_u <= crate::curve::MAX_STACK_DEGREE
&& surface.degree_v <= crate::curve::MAX_STACK_DEGREE {
let [u0,u1] = surface.domain_u()?;
let [v0,v1] = surface.domain_v()?;
let mut uu = u;
let mut vv = v;
if u < u0 || u > u1 || v < v0 || v > v1 {
let (closed_u, closed_v) = surface_closedness(surface)?;
if closed_u && (u < u0 || u > u1) { uu = u0 + (u - u0).rem_euclid(u1 - u0); }
if closed_v && (v < v0 || v > v1) { vv = v0 + (v - v0).rem_euclid(v1 - v0); }
}
if uu >= u0 && uu <= u1 && vv >= v0 && vv <= v1 {
let point = surface.evaluate_homogeneous(uu, vv)?;
if point.w.abs() <= EPSILON {
return Err("NurbsSurface: zero evaluated weight".into());
}
return Ok(Vec3::new(point.x, point.y, point.z).scale(1.0 / point.w));
}
}
surface.evaluate_extended(u,v)
}
struct PcurveSampleCache {
surface: usize,
curve: usize,
curves: rustc_hash::FxHashMap<u64, Vec3>,
surfaces: rustc_hash::FxHashMap<(u64, u64, bool, bool), Vec3>,
inversions: rustc_hash::FxHashMap<[u64; 3], ([f64; 2], f64)>,
requests: [usize; 4],
hits: [usize; 4],
speeds: rustc_hash::FxHashMap<(u64, u64), f64>,
}
thread_local! {
static PCURVE_SAMPLES: std::cell::RefCell<Vec<Option<PcurveSampleCache>>> = const { std::cell::RefCell::new(Vec::new()) };
}
struct PcurveSampleScope<'a>(std::marker::PhantomData<(&'a NurbsSurface, &'a NurbsCurve)>);
impl<'a> PcurveSampleScope<'a> {
fn open(surface: &'a NurbsSurface, curve: &'a NurbsCurve, enabled: bool) -> Self {
let cache = enabled
.then(|| PcurveSampleCache { surface: surface as *const _ as usize,
curve: curve as *const _ as usize, curves: Default::default(),
surfaces: Default::default(), inversions: Default::default(), requests: [0; 4], hits: [0; 4], speeds: Default::default() });
PCURVE_SAMPLES.with(|stack| stack.borrow_mut().push(cache));
Self(std::marker::PhantomData)
}
}
impl Drop for PcurveSampleScope<'_> {
fn drop(&mut self) {
PCURVE_SAMPLES.with(|stack| {
if let Some(Some(cache)) = stack.borrow_mut().pop() {
if crate::profile::profile_enabled() {
profile_line!("pcurve.samples requests={:?} hits={:?} retained={:?}", cache.requests,
cache.hits, [cache.curves.len(), cache.surfaces.len(), cache.inversions.len(), cache.speeds.len()]);
}
}
});
}
}
const PCURVE_SAMPLE_CACHE_LIMIT: usize = 16384;
fn section_u_speed(surface: &NurbsSurface, u: f64, v: f64) -> Result<f64, String> {
let key = (u.to_bits(), v.to_bits());
let (active, hit) = PCURVE_SAMPLES.with(|stack| {
let mut stack = stack.borrow_mut();
let Some(Some(cache)) = stack.last_mut() else { return (false, None) };
if cache.surface != surface as *const _ as usize { return (false, None) }
cache.requests[3] += 1;
let hit = cache.speeds.get(&key).copied();
cache.hits[3] += usize::from(hit.is_some());
(true, hit)
});
if let Some(hit) = hit { return Ok(hit) }
let speed = surface.deriv1(u, v)?.1.length();
if active { PCURVE_SAMPLES.with(|stack| {
let mut stack = stack.borrow_mut();
let cache = stack.last_mut().unwrap().as_mut().unwrap();
if cache.speeds.len() < PCURVE_SAMPLE_CACHE_LIMIT { cache.speeds.insert(key, speed); }
}); }
Ok(speed)
}
fn section_curve_point(curve: &NurbsCurve, parameter: f64) -> Result<Vec3, String> {
let key = parameter.to_bits();
let (active, hit) = PCURVE_SAMPLES.with(|stack| {
let mut stack = stack.borrow_mut();
let Some(Some(cache)) = stack.last_mut() else { return (false, None) };
if cache.curve != curve as *const _ as usize { return (false, None) }
cache.requests[0] += 1;
let hit = cache.curves.get(&key).copied();
cache.hits[0] += usize::from(hit.is_some());
(true, hit)
});
if let Some(hit) = hit { return Ok(hit) }
let point = curve.evaluate(parameter)?;
if active { PCURVE_SAMPLES.with(|stack| {
let mut stack = stack.borrow_mut();
let cache = stack.last_mut().unwrap().as_mut().unwrap();
if cache.curves.len() < PCURVE_SAMPLE_CACHE_LIMIT { cache.curves.insert(key, point); }
}); }
Ok(point)
}
fn section_surface_point(surface: &NurbsSurface, u: f64, v: f64, extended: bool) -> Result<Vec3, String> {
let stack_point = PCURVE_STACK_POINT.with(|state| state.get());
let key = (u.to_bits(), v.to_bits(), extended, stack_point);
let (active, hit) = PCURVE_SAMPLES.with(|stack| {
let mut stack = stack.borrow_mut();
let Some(Some(cache)) = stack.last_mut() else { return (false, None) };
if cache.surface != surface as *const _ as usize { return (false, None) }
cache.requests[1] += 1;
let hit = cache.surfaces.get(&key).copied();
cache.hits[1] += usize::from(hit.is_some());
(true, hit)
});
if let Some(hit) = hit { return Ok(hit) }
let point = if extended { section_extended_point(surface, u, v, stack_point)? } else { surface.evaluate(u, v)? };
if active { PCURVE_SAMPLES.with(|stack| {
let mut stack = stack.borrow_mut();
let cache = stack.last_mut().unwrap().as_mut().unwrap();
if cache.surfaces.len() < PCURVE_SAMPLE_CACHE_LIMIT { cache.surfaces.insert(key, point); }
}); }
Ok(point)
}
fn invert_checked(surface: &NurbsSurface, point: Vec3) -> Result<([f64; 2], f64), String> {
let key = [point.x.to_bits(), point.y.to_bits(), point.z.to_bits()];
let (active, hit) = PCURVE_SAMPLES.with(|stack| {
let mut stack = stack.borrow_mut();
let Some(Some(cache)) = stack.last_mut() else { return (false, None) };
if cache.surface != surface as *const _ as usize { return (false, None) }
cache.requests[2] += 1;
let hit = cache.inversions.get(&key).copied();
cache.hits[2] += usize::from(hit.is_some());
(true, hit)
});
if let Some(hit) = hit { return Ok(hit) }
let projection = invert_checked_uncached(surface, point)?;
if active { PCURVE_SAMPLES.with(|stack| {
let mut stack = stack.borrow_mut();
let cache = stack.last_mut().unwrap().as_mut().unwrap();
if cache.inversions.len() < PCURVE_SAMPLE_CACHE_LIMIT { cache.inversions.insert(key, projection); }
}); }
Ok(projection)
}
fn invert_checked_uncached(surface: &NurbsSurface, point: Vec3) -> Result<([f64; 2], f64), String> {
let _lap = crate::projection_profile::Lap::enter(crate::projection_profile::LANE_INVERT_CHECKED, surface);
if surface.is_affine()? {
let ([u0, _], [v0, _]) = surface_domains(surface)?;
let (origin, du, dv) = surface.deriv1(u0, v0)?;
let delta = point.sub(origin);
let uu = du.dot(du);
let uv = du.dot(dv);
let vv = dv.dot(dv);
let along_u = delta.dot(du);
let along_v = delta.dot(dv);
let determinant = uu * vv - uv * uv;
if determinant.abs() > EPSILON {
let parameter = [
u0 + (along_u * vv - along_v * uv) / determinant,
v0 + (along_v * uu - along_u * uv) / determinant,
];
let foot = origin.add(du.scale(parameter[0] - u0)).add(dv.scale(parameter[1] - v0));
return Ok((parameter, point.sub(foot).length()));
}
}
let projection = project_point_to_surface(surface, point)?;
Ok(([projection.u, projection.v], projection.distance))
}
fn cone_apex_u() -> bool {
switch!("BREP_PCURVE_CONE_APEX_U", true)
}
fn worst_first() -> bool {
switch!("BREP_PCURVE_WORST_FIRST", true)
}
fn c0_joins() -> bool {
switch!("BREP_PCURVE_C0_JOIN", true)
}
fn seeded_inserts() -> bool {
switch!("BREP_PCURVE_SEEDED_INSERTS", true)
}
fn invert_near(
surface: &NurbsSurface,
point: Vec3,
seed: [f64; 2],
neighbour_gap: f64,
) -> Result<([f64; 2], f64), String> {
if !seeded_inserts() || surface.is_affine()? || surface.analytic().is_some() || surface.affine_sphere().is_some() {
return invert_checked(surface, point);
}
let seeded = project_point_to_surface_seeded(surface, point, seed[0], seed[1])?;
if seeded.distance <= neighbour_gap + PCURVE_REFINEMENT_TOLERANCE {
return Ok(([seeded.u, seeded.v], seeded.distance));
}
invert_checked(surface, point)
}
fn unwrap_periodic(values: &mut [f64], minimum: f64, maximum: f64) {
let period = maximum - minimum;
for index in 1..values.len() {
while values[index] - values[index - 1] > period / 2.0 {
values[index] -= period;
}
while values[index] - values[index - 1] < -period / 2.0 {
values[index] += period;
}
}
if values.len() > 1 {
while values[0] - values[1] > period / 2.0 {
values[0] -= period;
}
while values[0] - values[1] < -period / 2.0 {
values[0] += period;
}
}
if values.len() > 1 {
let excursion = |shift: f64| -> f64 {
values
.iter()
.map(|value| {
let v = value + shift;
(minimum - v).max(0.0) + (v - maximum).max(0.0)
})
.sum::<f64>()
};
let mean = values.iter().copied().sum::<f64>() / values.len() as f64;
let center = 0.5 * (minimum + maximum);
let base_k = ((center - mean) / period).round() as i64;
let mut best_shift = 0.0;
let mut best_excursion = f64::INFINITY;
for k in (base_k - 1)..=(base_k + 1) {
let shift = k as f64 * period;
let value = excursion(shift);
if value < best_excursion {
best_excursion = value;
best_shift = shift;
}
}
if best_shift != 0.0 {
for value in values.iter_mut() {
*value += best_shift;
}
}
}
}
fn build_interpolant(
surface: &NurbsSurface,
raw_parameters: &[[f64; 2]],
curve_parameters: &[f64],
) -> Result<(NurbsCurve, f64, f64), String> {
build_interpolant_joined(surface, raw_parameters, curve_parameters, &[])
}
fn build_interpolant_joined(
surface: &NurbsSurface,
raw_parameters: &[[f64; 2]],
curve_parameters: &[f64],
joins: &[f64],
) -> Result<(NurbsCurve, f64, f64), String> {
let _clock = PcurvePhaseClock::new("interpolant", raw_parameters.len(), false);
let ([u0, u1], [v0, v1]) = surface_domains(surface)?;
let (closed_u, closed_v) = surface_closedness(surface)?;
let mut parameters = raw_parameters.to_vec();
if cone_apex_u() && matches!(surface.analytic(), Some(AnalyticSurface::RuledRevolution { .. })) && parameters.len() >= 2 {
let speeds = parameters
.iter()
.map(|parameter| section_u_speed(surface, parameter[0], parameter[1]))
.collect::<Result<Vec<_>, _>>()?;
let reference = speeds.iter().copied().fold(0.0_f64, f64::max);
let singular = |index: usize| speeds[index] <= reference * 1e-2;
if let (Some(first), Some(last)) = (
(0..parameters.len()).find(|&index| !singular(index)),
(0..parameters.len()).rfind(|&index| !singular(index)),
) {
for index in 0..first {
parameters[index][0] = parameters[first][0];
}
for index in last + 1..parameters.len() {
parameters[index][0] = parameters[last][0];
}
}
}
let sphere_u_singular = if matches!(surface.analytic(), Some(AnalyticSurface::Sphere { .. })) {
let speeds = parameters
.iter()
.map(|parameter| {
section_u_speed(surface, parameter[0], parameter[1])
})
.collect::<Result<Vec<_>, _>>()?;
let reference = speeds.iter().copied().fold(0.0_f64, f64::max);
speeds
.into_iter()
.map(|speed| speed <= reference * 1e-2)
.collect::<Vec<_>>()
} else {
vec![false; parameters.len()]
};
let has_interior_pole_crossing = sphere_u_singular
.iter()
.position(|singular| !singular)
.zip(sphere_u_singular.iter().rposition(|singular| !singular))
.is_some_and(|(first, last)| sphere_u_singular[first..=last].iter().any(|value| *value));
let period = (u1 - u0).abs();
let interior_pole_branch_reset = closed_u
&& has_interior_pole_crossing
&& parameters.windows(2).zip(sphere_u_singular.windows(2)).any(
|(parameter_pair, singular_pair)| {
(singular_pair[0] || singular_pair[1])
&& (parameter_pair[1][0] - parameter_pair[0][0]).abs()
>= 0.5 * period - 1e-12 * period.max(1.0)
},
);
if closed_u {
let mut values = parameters.iter().map(|value| value[0]).collect::<Vec<_>>();
if interior_pole_branch_reset {
let mut start = 0;
while start < values.len() {
while start < values.len() && sphere_u_singular[start] {
start += 1;
}
let mut end = start;
while end < values.len() && !sphere_u_singular[end] {
end += 1;
}
unwrap_periodic(&mut values[start..end], u0, u1);
start = end;
}
} else {
unwrap_periodic(&mut values, u0, u1);
}
for (parameter, value) in parameters.iter_mut().zip(values) {
parameter[0] = value;
}
}
if closed_v {
let mut values = parameters.iter().map(|value| value[1]).collect::<Vec<_>>();
unwrap_periodic(&mut values, v0, v1);
for (parameter, value) in parameters.iter_mut().zip(values) {
parameter[1] = value;
}
}
let mut excursion = 0.0_f64;
let mut distance = 0.0_f64;
let mut points = Vec::with_capacity(parameters.len());
for parameter in parameters {
let u = if closed_u {
parameter[0]
} else {
parameter[0].clamp(u0, u1)
};
let v = if closed_v {
parameter[1]
} else {
parameter[1].clamp(v0, v1)
};
let pulled = ((parameter[0] - u).powi(2) + (parameter[1] - v).powi(2)).sqrt();
if pulled > 0.0 {
excursion = excursion.max(pulled);
let extended = surface.evaluate_extended(parameter[0], parameter[1])?;
distance = distance.max(extended.sub(surface.evaluate(u, v)?).length());
}
points.push(Vec3::new(u, v, 0.0));
}
let degree = 3usize.min(points.len() - 1);
let mut bounds: Vec<usize> = joins
.iter()
.filter_map(|join| curve_parameters.iter().position(|parameter| parameter == join))
.filter(|&index| index > 0 && index + 1 < curve_parameters.len())
.collect();
bounds.sort_unstable();
bounds.dedup();
if degree < 3 || bounds.is_empty() || !c0_joins() {
let curve = interpolate_curve(&points, degree, curve_parameters)?;
return Ok((curve, excursion, distance));
}
let mut pieces = vec![0usize];
for bound in bounds {
if bound + 1 - pieces[pieces.len() - 1] >= 4 {
pieces.push(bound);
}
}
if curve_parameters.len() - pieces[pieces.len() - 1] < 4 {
pieces.pop();
}
pieces.push(curve_parameters.len() - 1);
if pieces.len() < 3 {
let curve = interpolate_curve(&points, degree, curve_parameters)?;
return Ok((curve, excursion, distance));
}
let mut knots: Vec<f64> = Vec::with_capacity(curve_parameters.len() + 4);
let mut control: Vec<Vec4> = Vec::with_capacity(curve_parameters.len());
let last_piece = pieces.len() - 2;
for piece in 0..=last_piece {
let (from, to) = (pieces[piece], pieces[piece + 1]);
let fitted = interpolate_curve(&points[from..=to], 3, &curve_parameters[from..=to])?;
if piece == 0 {
knots.extend(fitted.knots[..4].iter().copied());
}
knots.extend(fitted.knots[4..fitted.knots.len() - 4].iter().copied());
let multiplicity = if piece == last_piece { 4 } else { 3 };
knots.extend(std::iter::repeat(curve_parameters[to]).take(multiplicity));
control.extend(fitted.control_points.iter().skip(usize::from(piece > 0)).copied());
}
let curve = NurbsCurve::new(3, knots, control)?;
Ok((curve, excursion, distance))
}
pub const PCURVE_REFINEMENT_TOLERANCE: f64 = 1e-7;
const MAX_PCURVE_SAMPLES: usize = 600;
const PCURVE_RAISED_SAMPLES: usize = 2000;
#[derive(Clone, Copy, Debug, PartialEq)]
pub struct PcurveFitReport {
pub residual: f64,
pub floor: f64,
pub samples: usize,
pub exit: PcurveFitExit,
pub off_surface: f64,
pub raised: bool,
pub clamped_excursion: f64,
pub clamped_distance: f64,
}
impl PcurveFitReport {
pub fn met_floor(&self) -> bool {
self.residual <= self.floor
}
pub fn on_bar(&self) -> bool {
self.residual <= self.floor + self.off_surface
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub enum PcurveFitExit {
Converged,
SampleCeiling,
RoundBudget,
Stalled,
SpanFloor,
}
#[derive(Clone, Debug)]
pub struct PcurveFit {
pub curve: NurbsCurve,
pub report: PcurveFitReport,
}
#[derive(Clone, Copy, Debug, Default, PartialEq)]
pub struct PcurveFitLedger {
pub fits: u64,
pub unmet: u64,
pub sample_ceiling: u64,
pub round_budget: u64,
pub stalled: u64,
pub span_floor: u64,
pub worst_unmet_residual: f64,
pub raised: u64,
pub raise_declined: u64,
pub worst_off_surface: f64,
pub clamped: u64,
pub worst_clamped_excursion: f64,
pub worst_clamped_distance: f64,
}
impl PcurveFitLedger {
fn record(&mut self, report: &PcurveFitReport) {
self.fits += 1;
if report.raised {
self.raised += 1;
}
self.worst_off_surface = self.worst_off_surface.max(report.off_surface);
if report.clamped_excursion > 0.0 {
self.clamped += 1;
self.worst_clamped_excursion = self.worst_clamped_excursion.max(report.clamped_excursion);
self.worst_clamped_distance = self.worst_clamped_distance.max(report.clamped_distance);
}
if report.met_floor() {
return;
}
self.unmet += 1;
match report.exit {
PcurveFitExit::Converged => {}
PcurveFitExit::SampleCeiling => {
self.sample_ceiling += 1;
if !report.raised {
self.raise_declined += 1;
}
}
PcurveFitExit::RoundBudget => self.round_budget += 1,
PcurveFitExit::Stalled => self.stalled += 1,
PcurveFitExit::SpanFloor => self.span_floor += 1,
}
self.worst_unmet_residual = self.worst_unmet_residual.max(report.residual);
}
fn fold(&mut self, child: &PcurveFitLedger) {
self.fits += child.fits;
self.unmet += child.unmet;
self.sample_ceiling += child.sample_ceiling;
self.round_budget += child.round_budget;
self.stalled += child.stalled;
self.span_floor += child.span_floor;
self.worst_unmet_residual = self.worst_unmet_residual.max(child.worst_unmet_residual);
self.raised += child.raised;
self.raise_declined += child.raise_declined;
self.worst_off_surface = self.worst_off_surface.max(child.worst_off_surface);
self.clamped += child.clamped;
self.worst_clamped_excursion = self.worst_clamped_excursion.max(child.worst_clamped_excursion);
self.worst_clamped_distance = self.worst_clamped_distance.max(child.worst_clamped_distance);
}
pub fn report_into(&self, diagnostics: &mut KernelDiagnostics) {
diagnostics.count_n("pcurve.fits", self.fits);
diagnostics.count_n("pcurve.unmet_floor", self.unmet);
diagnostics.count_n("pcurve.exit.sample_ceiling", self.sample_ceiling);
diagnostics.count_n("pcurve.exit.round_budget", self.round_budget);
diagnostics.count_n("pcurve.exit.stalled", self.stalled);
diagnostics.count_n("pcurve.exit.span_floor", self.span_floor);
diagnostics.count_n("pcurve.budget_raised", self.raised);
diagnostics.count_n("pcurve.budget_raise_declined", self.raise_declined);
diagnostics.measure_max("pcurve.worst_unmet_residual", self.worst_unmet_residual);
diagnostics.measure_max("pcurve.worst_off_surface", self.worst_off_surface);
diagnostics.count_n("pcurve.clamped", self.clamped);
diagnostics.measure_max("pcurve.worst_clamped_excursion", self.worst_clamped_excursion);
diagnostics.measure_max("pcurve.worst_clamped_distance", self.worst_clamped_distance);
if self.unmet > 0 {
diagnostics.event(
DiagnosticSeverity::Degraded,
KernelStage::Refine,
"pcurve.unmet_floor",
format!(
"{} of {} pcurve fits did not reach the {:.0e} floor \
(sample ceiling {}, round budget {}, stalled {}, span floor {}); \
worst residual {:.3e}; budget raised on {}, declined on {}; \
edge curves sit off their surfaces by up to {:.3e}{}",
self.unmet,
self.fits,
PCURVE_REFINEMENT_TOLERANCE,
self.sample_ceiling,
self.round_budget,
self.stalled,
self.span_floor,
self.worst_unmet_residual,
self.raised,
self.raise_declined,
self.worst_off_surface,
if self.clamped > 0 {
format!(
"; {} fit(s) clamped into their chart by up to {:.3e} in parameter, {:.3e} in 3D",
self.clamped, self.worst_clamped_excursion, self.worst_clamped_distance
)
} else {
String::new()
},
),
);
}
}
}
thread_local! {
static FOOT_MEMO: std::cell::RefCell<Option<FootMemo>> = const { std::cell::RefCell::new(None) };
}
struct FootMemo {
surface: *const NurbsSurface,
global: rustc_hash::FxHashMap<[u64; 3], Option<crate::SurfaceProjection>>,
seeded: rustc_hash::FxHashMap<[u64; 5], Option<crate::SurfaceProjection>>,
pending_global: Vec<([u64; 3], Option<crate::SurfaceProjection>)>,
pending_seeded: Vec<([u64; 5], Option<crate::SurfaceProjection>)>,
}
impl FootMemo {
fn new(surface: *const NurbsSurface) -> Self {
Self { surface, global: Default::default(), seeded: Default::default(), pending_global: Vec::new(), pending_seeded: Vec::new() }
}
fn fold_pending(&mut self) {
if !self.pending_global.is_empty() {
self.global.reserve(self.pending_global.len());
self.global.extend(self.pending_global.drain(..));
}
if !self.pending_seeded.is_empty() {
self.seeded.reserve(self.pending_seeded.len());
self.seeded.extend(self.pending_seeded.drain(..));
}
}
}
thread_local! {
static DEFER_FOOT_INSERTS: std::cell::Cell<bool> = const { std::cell::Cell::new(false) };
}
pub(crate) fn defer_foot_inserts<T>(read: impl FnOnce() -> T) -> T {
let previous = DEFER_FOOT_INSERTS.with(|cell| cell.replace(true));
let result = read();
DEFER_FOOT_INSERTS.with(|cell| cell.set(previous));
result
}
pub(crate) struct FootMemoScope<'a> {
previous: Option<Option<FootMemo>>,
_surface: std::marker::PhantomData<&'a NurbsSurface>,
_thread_bound: std::marker::PhantomData<*const ()>,
}
impl<'a> FootMemoScope<'a> {
pub(crate) fn open(surface: &'a NurbsSurface) -> Self {
let key = surface as *const NurbsSurface;
let previous = FOOT_MEMO.with(|memo| {
let mut memo = memo.borrow_mut();
if memo.as_ref().is_some_and(|open| std::ptr::eq(open.surface, key)) {
None
} else {
Some(memo.replace(FootMemo::new(key)))
}
});
Self { previous, _surface: std::marker::PhantomData, _thread_bound: std::marker::PhantomData }
}
}
impl Drop for FootMemoScope<'_> {
fn drop(&mut self) {
if let Some(previous) = self.previous.take() {
FOOT_MEMO.with(|memo| *memo.borrow_mut() = previous);
}
}
}
fn point_bits(point: Vec3) -> [u64; 3] {
[point.x.to_bits(), point.y.to_bits(), point.z.to_bits()]
}
#[track_caller]
fn memo_global_foot(surface: &NurbsSurface, point: Vec3) -> Option<crate::SurfaceProjection> {
if crate::projection::global_site_filter_active() {
return project_point_to_surface(surface, point).ok();
}
let key = point_bits(point);
let deferring = DEFER_FOOT_INSERTS.with(|cell| cell.get());
let hit = FOOT_MEMO.with(|memo| {
memo.borrow_mut().as_mut().filter(|open| std::ptr::eq(open.surface, surface)).map(|open| {
match open.global.get(&key).copied() {
Some(foot) => Some(foot),
None if !deferring && !open.pending_global.is_empty() => {
open.fold_pending();
open.global.get(&key).copied()
}
None => None,
}
})
});
match hit {
Some(Some(foot)) => foot,
Some(None) => {
let foot = project_point_to_surface(surface, point).ok();
FOOT_MEMO.with(|memo| {
if let Some(open) = memo.borrow_mut().as_mut().filter(|open| std::ptr::eq(open.surface, surface)) {
if deferring {
open.pending_global.push((key, foot));
} else {
open.global.insert(key, foot);
}
}
});
foot
}
None => project_point_to_surface(surface, point).ok(),
}
}
fn memo_seeded_foot(surface: &NurbsSurface, point: Vec3, seed_u: f64, seed_v: f64) -> Option<crate::SurfaceProjection> {
let [x, y, z] = point_bits(point);
let key = [x, y, z, seed_u.to_bits(), seed_v.to_bits()];
let deferring = DEFER_FOOT_INSERTS.with(|cell| cell.get());
let hit = FOOT_MEMO.with(|memo| {
memo.borrow_mut().as_mut().filter(|open| std::ptr::eq(open.surface, surface)).map(|open| {
match open.seeded.get(&key).copied() {
Some(foot) => Some(foot),
None if !deferring && !open.pending_seeded.is_empty() => {
open.fold_pending();
open.seeded.get(&key).copied()
}
None => None,
}
})
});
match hit {
Some(Some(foot)) => foot,
Some(None) => {
let foot = project_point_to_surface_seeded(surface, point, seed_u, seed_v).ok();
FOOT_MEMO.with(|memo| {
if let Some(open) = memo.borrow_mut().as_mut().filter(|open| std::ptr::eq(open.surface, surface)) {
if deferring {
open.pending_seeded.push((key, foot));
} else {
open.seeded.insert(key, foot);
}
}
});
foot
}
None => project_point_to_surface_seeded(surface, point, seed_u, seed_v).ok(),
}
}
thread_local! {
static PCURVE_FIT_SCOPES: std::cell::RefCell<Vec<PcurveFitLedger>> =
const { std::cell::RefCell::new(Vec::new()) };
}
static PCURVE_TRACK_CALL: std::sync::atomic::AtomicU64 = std::sync::atomic::AtomicU64::new(0);
pub struct PcurveFitScope {
_thread_bound: std::marker::PhantomData<*const ()>,
}
impl PcurveFitScope {
pub fn open() -> Self {
PCURVE_FIT_SCOPES.with(|scopes| scopes.borrow_mut().push(PcurveFitLedger::default()));
Self {
_thread_bound: std::marker::PhantomData,
}
}
pub fn close(self) -> PcurveFitLedger {
let ledger = PCURVE_FIT_SCOPES.with(|scopes| {
let mut scopes = scopes.borrow_mut();
let ledger = scopes.pop().unwrap_or_default();
if let Some(parent) = scopes.last_mut() {
parent.fold(&ledger);
}
ledger
});
std::mem::forget(self);
ledger
}
}
impl Drop for PcurveFitScope {
fn drop(&mut self) {
PCURVE_FIT_SCOPES.with(|scopes| {
scopes.borrow_mut().pop();
});
}
}
pub(crate) fn record_fit(report: &PcurveFitReport) {
if env_read!("BREP_DEBUG_PCURVE_FIT").is_some() {
eprintln!("PCURVE-FIT {report:?}");
}
PCURVE_FIT_SCOPES.with(|scopes| {
if let Some(open) = scopes.borrow_mut().last_mut() {
open.record(report);
}
});
}
fn probe_residual(
surface: &NurbsSurface,
curve: &NurbsCurve,
pcurve: &NurbsCurve,
parameters: &[f64],
domain: [f64; 2],
_u_domain: [f64; 2],
_v_domain: [f64; 2],
) -> Result<f64, String> {
probe_residual_at(surface, curve, pcurve, parameters, domain, &[0.25, 0.5, 0.75])
}
const TRACKING_ACCEPTANCE_POINTS: usize = 16;
fn probe_residual_at(
surface: &NurbsSurface,
curve: &NurbsCurve,
pcurve: &NurbsCurve,
parameters: &[f64],
[t0, t1]: [f64; 2],
locals: &[f64],
) -> Result<f64, String> {
let mut worst = 0.0_f64;
for span in parameters.windows(2) {
for &local in locals {
let fraction = span[0] + (span[1] - span[0]) * local;
let parameter = pcurve.evaluate(fraction)?;
let on_surface =
section_surface_point(surface, parameter.x, parameter.y, true)?;
let on_curve = section_curve_point(curve, t0 + (t1 - t0) * fraction)?;
let distance = on_surface.sub(on_curve).length();
if !distance.is_finite() {
return Err(format!(
"probe_residual: non-finite image distance {distance} at fraction {fraction}"
));
}
worst = worst.max(distance);
}
}
Ok(worst)
}
pub(crate) fn native_probe_fractions(curves: &[&NurbsCurve]) -> Result<Vec<f64>, String> {
let locals: Vec<f64> = [0.25, 0.5, 0.75]
.into_iter()
.chain((1..=TRACKING_ACCEPTANCE_POINTS).map(|index| index as f64 / (TRACKING_ACCEPTANCE_POINTS + 1) as f64))
.collect();
let mut fractions = Vec::new();
for curve in curves {
let [q0, q1] = curve.domain()?;
fractions.push(q0);
fractions.push(q1);
let mut knots: Vec<f64> = curve.knots.iter().copied().filter(|k| *k >= q0 && *k <= q1).collect();
knots.dedup();
for span in knots.windows(2).filter(|w| w[1] > w[0]) {
for &local in &locals {
fractions.push(span[0] + (span[1] - span[0]) * local);
}
}
}
fractions.sort_by(f64::total_cmp);
fractions.dedup();
Ok(fractions)
}
#[derive(Clone, Copy, Debug, PartialEq)]
struct NativeRead {
tracking: f64,
deviation: f64,
standoff: f64,
}
fn native_read(surface: &NurbsSurface, curve: &NurbsCurve, pcurve: &NurbsCurve, [t0, t1]: [f64; 2], fractions: &[f64]) -> Result<NativeRead, String> {
let mut read = NativeRead { tracking: 0.0, deviation: 0.0, standoff: 0.0 };
for &fraction in fractions {
let parameter = pcurve.evaluate(fraction)?;
let image = section_surface_point(surface, parameter.x, parameter.y, true)?;
let on_curve = section_curve_point(curve, t0 + (t1 - t0) * fraction)?;
let foot = crate::projection::project_point_to_surface_from_seed(surface, on_curve, [parameter.x, parameter.y])?;
let tracking = image.sub(foot.point).length();
let deviation = image.sub(on_curve).length();
if !(tracking.is_finite() && deviation.is_finite() && foot.distance.is_finite()) {
return Err(format!("native read: non-finite reading at fraction {fraction}"));
}
read.tracking = read.tracking.max(tracking);
read.deviation = read.deviation.max(deviation);
read.standoff = read.standoff.max(foot.distance);
}
Ok(read)
}
fn standoff_candidate_accepted(standing: NativeRead, candidate: NativeRead, candidate_fields_finite: bool, floor: f64) -> bool {
candidate_fields_finite
&& candidate.tracking.is_finite()
&& candidate.deviation.is_finite()
&& candidate.tracking <= floor
&& candidate.tracking < standing.tracking
&& candidate.deviation <= standing.deviation
}
fn tracking_acceptance_residual(
surface: &NurbsSurface,
curve: &NurbsCurve,
pcurve: &NurbsCurve,
parameters: &[f64],
domain: [f64; 2],
) -> Result<f64, String> {
let locals: Vec<f64> = [0.25, 0.5, 0.75]
.into_iter()
.chain((1..=TRACKING_ACCEPTANCE_POINTS).map(|index| index as f64 / (TRACKING_ACCEPTANCE_POINTS + 1) as f64))
.collect();
probe_residual_at(surface, curve, pcurve, parameters, domain, &locals)
}
fn tracking_candidate_accepted(standing: f64, standing_dense: bool, floor: f64, exit: PcurveFitExit, reading: f64) -> bool {
if exit == PcurveFitExit::Converged && !standing_dense {
return reading <= floor && reading < standing;
}
if exit != PcurveFitExit::Converged && !(standing > floor) {
return false;
}
reading.is_finite() && reading <= floor && reading < standing
}
fn judge_tracking_candidate(
standing: f64,
standing_dense: bool,
floor: f64,
exit: PcurveFitExit,
own: f64,
dense: impl FnOnce() -> Result<f64, String>,
) -> (Result<Option<f64>, String>, bool) {
judge_tracking_candidate_with_bounds(standing, standing_dense, floor, exit, own, dense, false)
}
fn judge_tracking_candidate_with_bounds(
standing: f64,
standing_dense: bool,
floor: f64,
exit: PcurveFitExit,
own: f64,
dense: impl FnOnce() -> Result<f64, String>,
bounds: bool,
) -> (Result<Option<f64>, String>, bool) {
if bounds && exit != PcurveFitExit::Converged && own > floor {
if crate::profile::profile_enabled() { profile_line!("pcurve.reject_bound kind=quarter_residual"); }
return (Ok(Some(own)), false);
}
let reading = if exit == PcurveFitExit::Converged && !standing_dense {
Ok(Some(own))
} else if exit == PcurveFitExit::Converged || standing > floor {
dense().map(Some)
} else {
Ok(None)
};
let accepted = matches!(
reading,
Ok(Some(value)) if tracking_candidate_accepted(standing, standing_dense, floor, exit, value)
);
(reading, accepted)
}
struct Refinement {
exit: PcurveFitExit,
residual: f64,
off_surface: f64,
raised: bool,
clamped: [f64; 2],
}
#[allow(clippy::too_many_arguments)]
fn refine_pcurve(
surface: &NurbsSurface,
curve: &NurbsCurve,
domain: [f64; 2],
u_domain: [f64; 2],
v_domain: [f64; 2],
floor: f64,
joins: &[f64],
parameters: &mut Vec<f64>,
raw: &mut Vec<[f64; 2]>,
pcurve: &mut NurbsCurve,
off_surface: f64,
clamped: [f64; 2],
mut insert: impl FnMut(f64, Vec3, Vec3) -> Result<(Option<[f64; 2]>, f64), String>,
) -> Result<Refinement, String> {
let trace = env_read!("BREP_DEBUG_PCURVE_FIT").is_some();
let call = if trace {
PCURVE_TRACK_CALL.fetch_add(1, std::sync::atomic::Ordering::Relaxed) + 1
} else {
0
};
let reject_bounds = PCURVE_REJECT_BOUNDS.with(|state| state.get());
let mut best = refine_pcurve_pass(surface, curve, domain, u_domain, v_domain,
floor, joins, parameters, raw, pcurve, off_surface, clamped, false, 1.0, false, &mut insert, false)?;
if trace {
eprintln!(
"PCURVE-TRACK call={call} first-pass exit={:?} residual={:e} floor={floor:e} off_surface={:e} samples={} raised={} tracking={}",
best.exit,
best.residual,
best.off_surface,
parameters.len(),
best.raised,
if best.off_surface <= floor { "eligible" } else { "standoff-tracking" }
);
}
if best.off_surface > floor {
if !standoff_tracking_enabled() {
return Ok(best);
}
return standoff_tracking_rungs(surface, curve, domain, u_domain, v_domain, floor, joins,
parameters, raw, pcurve, best, trace, call, &mut insert);
}
let baseline_parameters = parameters.clone();
let baseline_raw = raw.clone();
let baseline_curve = pcurve.clone();
let baseline_off_surface = best.off_surface;
let baseline_clamped = best.clamped;
let standing_misses = best.residual > floor;
Ok(tracking_rungs(
best,
floor,
trace,
call,
true,
|fraction| {
let mut refined_parameters = baseline_parameters.clone();
let mut refined_raw = baseline_raw.clone();
let mut refined_curve = baseline_curve.clone();
let candidate = refine_pcurve_pass(surface, curve, domain, u_domain, v_domain,
floor, joins, &mut refined_parameters, &mut refined_raw, &mut refined_curve,
baseline_off_surface, baseline_clamped, true, fraction, standing_misses, &mut insert, reject_bounds && !standing_misses);
(candidate, (refined_parameters, refined_raw, refined_curve))
},
|state: &RungState| tracking_acceptance_residual(surface, curve, &state.2, &state.0, domain),
|state: &RungState| state.0.len(),
|(refined_parameters, refined_raw, refined_curve): RungState| {
*parameters = refined_parameters;
*raw = refined_raw;
*pcurve = refined_curve;
},
))
}
type RungState = (Vec<f64>, Vec<[f64; 2]>, NurbsCurve);
#[allow(clippy::too_many_arguments)]
fn tracking_rungs<S>(
mut best: Refinement,
floor: f64,
trace: bool,
call: u64,
thread_dense: bool,
mut run_pass: impl FnMut(f64) -> (Result<Refinement, String>, S),
mut dense: impl FnMut(&S) -> Result<f64, String>,
samples: impl Fn(&S) -> usize,
mut adopt: impl FnMut(S),
) -> Refinement {
let mut standing_dense = false;
let reject_bounds = PCURVE_REJECT_BOUNDS.with(|state| state.get());
for fraction in [0.1, 0.01] {
if best.residual <= floor * fraction {
if trace {
eprintln!(
"PCURVE-TRACK call={call} candidate fraction={fraction} skipped best_residual={:e} <= {:e}",
best.residual,
floor * fraction
);
}
continue;
}
let (candidate, state) = run_pass(fraction);
let judged_dense = matches!(&candidate, Ok(seen) if seen.exit != PcurveFitExit::Converged || standing_dense);
let (effective, accepted) = match &candidate {
Ok(seen) => judge_tracking_candidate_with_bounds(best.residual, standing_dense, floor, seen.exit, seen.residual, || {
dense(&state)
}, reject_bounds),
Err(_) => (Ok(None), false),
};
if trace {
let judged_on = match &effective {
Ok(Some(reading)) => format!("{reading:e}"),
Ok(None) => "-".to_string(),
Err(message) => format!("error:{message:?}"),
};
match &candidate {
Ok(seen) => eprintln!(
"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={}",
seen.exit,
seen.residual,
seen.off_surface,
samples(&state),
seen.raised,
seen.residual <= floor,
if accepted { "accept" } else { "decline-stop" }
),
Err(message) => eprintln!(
"PCURVE-TRACK call={call} candidate fraction={fraction} error={message:?} decision=decline-stop"
),
}
}
match candidate {
Ok(mut candidate) if accepted => {
if let Ok(Some(reading)) = effective {
candidate.residual = reading;
}
if thread_dense {
standing_dense |= judged_dense;
}
adopt(state);
best = candidate;
}
_ => break,
}
}
best
}
fn standoff_tracking_enabled() -> bool {
switch!("BREP_PCURVE_STANDOFF_TRACKING", true)
}
#[allow(clippy::too_many_arguments)]
fn standoff_tracking_rungs(
surface: &NurbsSurface,
curve: &NurbsCurve,
domain: [f64; 2],
u_domain: [f64; 2],
v_domain: [f64; 2],
floor: f64,
joins: &[f64],
parameters: &mut Vec<f64>,
raw: &mut Vec<[f64; 2]>,
pcurve: &mut NurbsCurve,
mut best: Refinement,
trace: bool,
call: u64,
insert: &mut impl FnMut(f64, Vec3, Vec3) -> Result<(Option<[f64; 2]>, f64), String>,
) -> Result<Refinement, String> {
let first = native_probe_fractions(&[&*pcurve]).and_then(|probes| native_read(surface, curve, pcurve, domain, &probes));
if trace {
eprintln!("PCURVE-TRACK call={call} standoff-tracking first-pass native={first:?} floor={floor:e}");
}
let Ok(first) = first else { return Ok(best) };
if first.tracking <= floor {
return Ok(best);
}
let baseline_parameters = parameters.clone();
let baseline_raw = raw.clone();
let baseline_curve = pcurve.clone();
for fraction in [0.1, 0.01] {
let mut refined_parameters = baseline_parameters.clone();
let mut refined_raw = baseline_raw.clone();
let mut refined_curve = baseline_curve.clone();
let candidate = refine_pcurve_pass(surface, curve, domain, u_domain, v_domain, floor, joins,
&mut refined_parameters, &mut refined_raw, &mut refined_curve, best.off_surface, best.clamped,
true, fraction, true, &mut *insert, false);
let reads = candidate.as_ref().ok().map(|_| {
native_probe_fractions(&[&*pcurve, &refined_curve]).and_then(|probes| {
Ok((native_read(surface, curve, pcurve, domain, &probes)?, native_read(surface, curve, &refined_curve, domain, &probes)?))
})
});
let fields_finite = matches!(&candidate, Ok(seen) if seen.residual.is_finite() && seen.off_surface.is_finite());
let decision = match &reads {
Some(Ok((standing, read))) => standoff_rung_decision(*standing, *read, fields_finite, floor),
_ => RungDecision::Stop,
};
if trace {
eprintln!(
"PCURVE-TRACK call={call} standoff-tracking fraction={fraction} candidate={} reads={reads:?} decision={}",
match &candidate { Ok(seen) => format!("{:?}/{:e}/raised={}", seen.exit, seen.residual, seen.raised), Err(message) => format!("error:{message:?}") },
match decision { RungDecision::Accept => "accept", RungDecision::Continue => "decline-continue", RungDecision::Stop => "decline-stop" }
);
}
let (Ok(mut taken), Some(Ok((_, read))), RungDecision::Accept) = (candidate, reads, decision) else {
if decision == RungDecision::Continue {
continue;
}
break;
};
taken.residual = read.deviation;
taken.off_surface = taken.off_surface.max(read.standoff);
*parameters = refined_parameters;
*raw = refined_raw;
*pcurve = refined_curve;
best = taken;
if read.tracking <= floor * 0.01 {
break;
}
}
Ok(best)
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
enum RungDecision {
Accept,
Continue,
Stop,
}
fn standoff_rung_decision(standing: NativeRead, candidate: NativeRead, fields_finite: bool, floor: f64) -> RungDecision {
if standoff_candidate_accepted(standing, candidate, fields_finite, floor) {
RungDecision::Accept
} else if candidate.tracking.is_finite() && candidate.tracking < standing.tracking {
RungDecision::Continue
} else {
RungDecision::Stop
}
}
fn takes_raise(exit: PcurveFitExit, raised: bool, residual: f64, off_surface: f64, floor: f64, unmet_tracking: bool) -> bool {
exit == PcurveFitExit::SampleCeiling && !raised && (residual > off_surface + floor || unmet_tracking)
}
fn refine_pcurve_pass(
surface: &NurbsSurface,
curve: &NurbsCurve,
[t0, t1]: [f64; 2],
[u0, u1]: [f64; 2],
[v0, v1]: [f64; 2],
floor: f64,
joins: &[f64],
parameters: &mut Vec<f64>,
raw: &mut Vec<[f64; 2]>,
pcurve: &mut NurbsCurve,
mut off_surface: f64,
mut clamped: [f64; 2],
track_projection: bool,
tracking_fraction: f64,
raise_unmet_tracking: bool,
mut insert: impl FnMut(f64, Vec3, Vec3) -> Result<(Option<[f64; 2]>, f64), String>,
reject_budget: bool,
) -> Result<Refinement, String> {
let _clock = PcurvePhaseClock::new("refinement", parameters.len(), track_projection);
let tracking_floor = if track_projection { floor * tracking_fraction } else { floor };
let mut max_samples = MAX_PCURVE_SAMPLES;
let mut raised = false;
loop {
let mut exit = PcurveFitExit::RoundBudget;
let mut residual = None;
for round in 0..4 {
if parameters.len() >= max_samples {
exit = PcurveFitExit::SampleCeiling;
break;
}
let mut inserts = Vec::new();
let mut round_max = 0.0_f64;
let mut truncated = false;
let mut skipped_narrow = false;
for index in 0..parameters.len() - 1 {
if parameters.len() + inserts.len() >= max_samples {
truncated = true;
break;
}
let start = parameters[index];
let end = parameters[index + 1];
if end - start < if track_projection { SPAN_FLOOR } else { 1e-3 } {
skipped_narrow = true;
continue;
}
for local_fraction in [0.25, 0.5, 0.75] {
if parameters.len() + inserts.len() >= max_samples {
truncated = true;
break;
}
let fraction = start + (end - start) * local_fraction;
let parameter = pcurve.evaluate(fraction)?;
let on_surface =
section_surface_point(surface, parameter.x, parameter.y, true)?;
let on_curve = section_curve_point(curve, t0 + (t1 - t0) * fraction)?;
let deviation = on_surface.sub(on_curve).length();
if !deviation.is_finite() {
return Err(format!(
"refine_pcurve_pass: non-finite station distance {deviation} at fraction {fraction}"
));
}
round_max = round_max.max(deviation);
if deviation <= tracking_floor {
continue;
}
let (surface_parameter, gap) = insert(fraction, parameter, on_curve)?;
off_surface = off_surface.max(gap);
if let Some(surface_parameter) = surface_parameter {
if raised || track_projection {
let projected =
section_surface_point(surface, surface_parameter[0], surface_parameter[1], false)?;
if on_surface.sub(projected).length() <= tracking_floor {
continue;
}
}
inserts.push((index + 1, fraction, surface_parameter));
}
}
}
if inserts.is_empty() {
exit = if truncated {
PcurveFitExit::SampleCeiling
} else if round_max > floor {
PcurveFitExit::Stalled
} else if skipped_narrow {
PcurveFitExit::SpanFloor
} else {
residual = Some(round_max);
PcurveFitExit::Converged
};
break;
}
if reject_budget && round == 3 && !truncated {
if crate::profile::profile_enabled() { profile_line!("pcurve.reject_bound kind=fifth_round"); }
return Err("pcurve tracking candidate requires a fifth round".into());
}
for (at, fraction, surface_parameter) in inserts.into_iter().rev() {
parameters.insert(at, fraction);
raw.insert(at, surface_parameter);
}
let (rebuilt, excursion, distance) = build_interpolant_joined(surface, raw, parameters, joins)?;
*pcurve = rebuilt;
clamped = [excursion, distance];
if truncated {
exit = PcurveFitExit::SampleCeiling;
break;
}
}
let residual = match residual {
Some(measured) => measured,
None => probe_residual(
surface,
curve,
pcurve,
parameters,
[t0, t1],
[u0, u1],
[v0, v1],
)?,
};
if exit == PcurveFitExit::SpanFloor && residual <= floor {
exit = PcurveFitExit::Converged;
}
let unmet_tracking = track_projection
&& raise_unmet_tracking
&& exit == PcurveFitExit::SampleCeiling
&& !raised
&& native_probe_fractions(&[&*pcurve])
.and_then(|probes| native_read(surface, curve, pcurve, [t0, t1], &probes))
.is_ok_and(|read| read.tracking > tracking_floor);
if takes_raise(exit, raised, residual, off_surface, floor, unmet_tracking) {
raised = true;
max_samples = PCURVE_RAISED_SAMPLES;
continue;
}
return Ok(Refinement {
exit,
residual,
off_surface,
raised,
clamped,
});
}
}
struct AffineInversion {
origin: Vec3,
du: Vec3,
dv: Vec3,
u0: f64,
v0: f64,
uu: f64,
uv: f64,
vv: f64,
determinant: f64,
}
impl AffineInversion {
fn of(surface: &NurbsSurface) -> Result<Option<Self>, String> {
if !surface.is_affine()? {
return Ok(None);
}
let ([u0, _], [v0, _]) = surface_domains(surface)?;
let (origin, du, dv) = surface.deriv1(u0, v0)?;
let uu = du.dot(du);
let uv = du.dot(dv);
let vv = dv.dot(dv);
let determinant = uu * vv - uv * uv;
if determinant.abs() <= 1e-18 {
return Ok(None);
}
Ok(Some(Self {
origin,
du,
dv,
u0,
v0,
uu,
uv,
vv,
determinant,
}))
}
fn uv_of(&self, point: Vec3) -> [f64; 2] {
let delta = point.sub(self.origin);
let along_u = delta.dot(self.du);
let along_v = delta.dot(self.dv);
[
self.u0 + (along_u * self.vv - along_v * self.uv) / self.determinant,
self.v0 + (along_v * self.uu - along_u * self.uv) / self.determinant,
]
}
fn image_of(&self, curve: &NurbsCurve) -> Result<NurbsCurve, String> {
let control_points = curve
.control_points
.iter()
.map(|control| {
let [u, v] = self.uv_of(control.point()?);
Ok(Vec4::from_point(Vec3::new(u, v, 0.0), control.w))
})
.collect::<Result<Vec<_>, String>>()?;
NurbsCurve::new(curve.degree, curve.knots.clone(), control_points)
}
}
fn sphere_iso_enabled() -> bool {
env_read!("BREP_PCURVE_SPHERE_ISO").is_none_or(|mode| mode != "0")
}
fn sphere_iso_fit(surface: &NurbsSurface, curve: &NurbsCurve) -> Option<PcurveFit> {
if surface.degree_u != 2 { return None; }
let [t0, t1] = curve.domain().ok()?;
let [u0, u1] = surface.domain_u().ok()?;
let [v0, v1] = surface.domain_v().ok()?;
if !matches!(surface.analytic(), Some(AnalyticSurface::Sphere { .. })) { return None; }
let middle = curve.evaluate(t0 + (t1 - t0) * 0.5).ok()?;
let projected = project_point_to_surface(surface, middle).ok()?;
let mut candidates = vec![projected.u];
for &knot in &surface.knots_u {
if (knot - projected.u).abs() <= 1e-12 && !candidates.contains(&knot) { candidates.push(knot); }
}
for u in candidates {
if !(u >= u0 && u <= u1) { continue; }
let iso = surface.iso_curve_u(u).ok()?;
if iso.degree != curve.degree || iso.knots.len() != curve.knots.len()
|| iso.control_points.len() != curve.control_points.len() { continue; }
for reverse in [false, true] {
let n = iso.control_points.len();
fn exact_difference(a: f64, b: f64) -> Option<f64> {
if !(a.is_finite() && b.is_finite()) || a.abs().max(b.abs()) > 1e100 { return None; }
let x = a - b;
let bv = a - x;
let av = x + bv;
let error = (a - av) + (bv - b);
(error == 0.).then_some(x)
}
fn exact_fraction(offset: f64, span: f64) -> Option<f64> {
if !(1e-100..=1e100).contains(&span) { return None; }
let ratio = offset / span;
if !(0.0..=1.0).contains(&ratio) || (ratio != 0. && ratio < 1e-100) { return None; }
(ratio.mul_add(span, -offset) == 0.).then_some(ratio)
}
let knots_match = (|| {
let section_span = exact_difference(t1, t0)?;
let native_span = exact_difference(v1, v0)?;
for (i, &knot) in curve.knots.iter().enumerate() {
let section = exact_difference(knot, t0)?;
let native = if reverse { exact_difference(v1, iso.knots[iso.knots.len() - 1 - i])? }
else { exact_difference(iso.knots[i], v0)? };
if exact_fraction(section, section_span)? != exact_fraction(native, native_span)? { return None; }
}
Some(())
})().is_some();
if !knots_match { continue; }
let mut bound = 0.0_f64;
let mut matches = true;
for (i, control) in curve.control_points.iter().enumerate() {
let native = &iso.control_points[if reverse { n - 1 - i } else { i }];
if !(control.w > 0.) || control.w != native.w { matches = false; break; }
let distance = control.point().ok()?.sub(native.point().ok()?).length();
if !distance.is_finite() { matches = false; break; }
bound = bound.max(distance);
}
if !matches || bound > PCURVE_REFINEMENT_TOLERANCE * 0.0625 { continue; }
let (start, end) = if reverse { (v1, v0) } else { (v0, v1) };
let pcurve = NurbsCurve::new(1, vec![0., 0., 1., 1.], vec![
Vec4::from_point(Vec3::new(u, start, 0.), 1.),
Vec4::from_point(Vec3::new(u, end, 0.), 1.),
]).ok()?;
for i in 0..=96 {
let fraction = i as f64 / 96.;
let uv = pcurve.evaluate(fraction).ok()?;
let image = surface.evaluate(uv.x, uv.y).ok()?;
let on_curve = curve.evaluate(t0 + (t1 - t0) * fraction).ok()?;
let error = image.sub(on_curve).length();
if !error.is_finite() { matches = false; break; }
bound = bound.max(error);
}
if !matches || bound > PCURVE_REFINEMENT_TOLERANCE * 0.0625 { continue; }
return Some(PcurveFit { curve: pcurve, report: PcurveFitReport {
residual: bound, floor: PCURVE_REFINEMENT_TOLERANCE, samples: 2,
exit: PcurveFitExit::Converged, off_surface: bound, raised: false,
clamped_excursion: 0., clamped_distance: 0.,
} });
}
}
None
}
pub fn fit_pcurve_on_surface(
surface: &NurbsSurface,
curve: &NurbsCurve,
) -> Result<PcurveFit, String> {
if sphere_iso_enabled() {
if let Some(fit) = sphere_iso_fit(surface, curve) { return Ok(fit); }
}
let mode = env_read!("BREP_PCURVE_EVAL_CACHE").unwrap_or_default();
let bounds = env_read!("BREP_PCURVE_REJECT_BOUNDS").unwrap_or_else(|| "on".into());
let stack = env_read!("BREP_PCURVE_STACK_POINT").unwrap_or_else(|| "on".into());
if mode == "check" || bounds == "check" || stack == "check" {
let old = fit_pcurve_on_surface_cached(surface, curve, false, false, false)?;
if matches!(surface.analytic(), Some(AnalyticSurface::Sphere { .. })) {
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");
let identical = candidate.as_ref().is_ok_and(|new| {
old.curve.degree == new.curve.degree
&& old.curve.knots.len() == new.curve.knots.len()
&& old.curve.knots.iter().zip(&new.curve.knots).all(|(a, b)| a.to_bits() == b.to_bits())
&& old.curve.control_points.len() == new.curve.control_points.len()
&& old.curve.control_points.iter().zip(&new.curve.control_points).all(|(a, b)| {
[a.x.to_bits(), a.y.to_bits(), a.z.to_bits(), a.w.to_bits()]
== [b.x.to_bits(), b.y.to_bits(), b.z.to_bits(), b.w.to_bits()]
}) && old.report == new.report
});
if let Ok(path) = std::env::var("BREP_PCURVE_EVAL_CENSUS") {
use std::io::Write;
if let Ok(mut file) = std::fs::OpenOptions::new().create(true).append(true).open(path) {
let _ = writeln!(file, "pcurve.eval_census identical={identical} controls={} samples={}", old.curve.control_points.len(), old.report.samples);
}
}
}
return Ok(old);
}
fit_pcurve_on_surface_cached(surface, curve, mode == "1" || mode == "on", bounds == "1" || bounds == "on", stack == "1" || stack == "on")
}
fn fit_pcurve_on_surface_cached(surface: &NurbsSurface, curve: &NurbsCurve, enabled: bool, bounds: bool, stack: bool) -> Result<PcurveFit, String> {
let _stack = PcurveStackPointScope::open(stack && matches!(surface.analytic(), Some(AnalyticSurface::Sphere { .. })));
let _samples = PcurveSampleScope::open(surface, curve, enabled
|| !matches!(surface.analytic(), Some(AnalyticSurface::Sphere { .. })));
let _bounds = PcurveRejectScope::open(bounds && matches!(surface.analytic(), Some(AnalyticSurface::Sphere { .. })));
let [t0, t1] = curve.domain()?;
if surface.is_affine()? {
let Some(inversion) = AffineInversion::of(surface)? else {
return Err("build_pcurve_on_surface: singular affine parameterization".into());
};
let pcurve = inversion.image_of(curve)?;
return Ok(PcurveFit {
report: PcurveFitReport {
residual: 0.0,
floor: PCURVE_REFINEMENT_TOLERANCE,
samples: pcurve.control_points.len(),
exit: PcurveFitExit::Converged,
off_surface: 0.0,
raised: false,
clamped_excursion: 0.0,
clamped_distance: 0.0,
},
curve: pcurve,
});
}
let scale = 1.0 + curve.evaluate((t0 + t1) / 2.0)?.length();
let drop_tolerance = 1e-4 * scale;
let endpoint_tolerance = 1e-3 * scale;
let refinement_tolerance = PCURVE_REFINEMENT_TOLERANCE;
let ([u0, u1], [v0, v1]) = surface_domains(surface)?;
let invert =
|fraction: f64| invert_checked(surface, section_curve_point(curve, t0 + (t1 - t0) * fraction)?);
let mut parameters = Vec::with_capacity(25);
let mut raw_surface_parameters = Vec::with_capacity(25);
let mut off_surface = 0.0_f64;
let corners = range_breaks(curve, t0, t1, true);
let mut stations: Vec<f64> = (0..=24).map(|index| index as f64 / 24.0).collect();
stations.retain(|station| {
*station == 0.0 || *station == 1.0 || corners.contains(station)
|| !corners.iter().any(|corner| (*station - corner).abs() <= SPAN_FLOOR)
});
for &corner in &corners {
let at = stations.partition_point(|value| *value < corner);
if stations.get(at) != Some(&corner) {
stations.insert(at, corner);
}
}
let joins = corners;
for (index, &fraction) in stations.iter().enumerate() {
let (parameter, distance) = invert(fraction)?;
off_surface = off_surface.max(distance);
if distance > drop_tolerance && index != 0 && index != stations.len() - 1 {
continue;
}
if distance > endpoint_tolerance {
if std::env::var("BREP_DEBUG_PCURVE").is_ok() {
let p3 = curve.evaluate(t0 + (t1 - t0) * fraction).ok();
let p0 = curve.evaluate(t0).ok();
let p1 = curve.evaluate(t1).ok();
eprintln!(
"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={:?}",
surface.evaluate(parameter[0], parameter[1]).ok()
);
}
return Err(format!(
"build_pcurve_on_surface: endpoint projection failed (distance={distance})"
));
}
parameters.push(fraction);
raw_surface_parameters.push(parameter);
}
let (mut pcurve, excursion, distance) =
build_interpolant_joined(surface, &raw_surface_parameters, ¶meters, &joins)?;
let refinement = refine_pcurve(
surface,
curve,
[t0, t1],
[u0, u1],
[v0, v1],
refinement_tolerance,
&joins,
&mut parameters,
&mut raw_surface_parameters,
&mut pcurve,
off_surface,
[excursion, distance],
|fraction, _parameter, _on_curve| {
let (surface_parameter, distance) = invert(fraction)?;
Ok((
(distance <= drop_tolerance).then_some(surface_parameter),
distance,
))
},
)?;
Ok(PcurveFit {
curve: pcurve,
report: PcurveFitReport {
residual: refinement.residual,
floor: refinement_tolerance,
samples: parameters.len(),
exit: refinement.exit,
off_surface: refinement.off_surface,
raised: refinement.raised,
clamped_excursion: refinement.clamped[0],
clamped_distance: refinement.clamped[1],
},
})
}
pub fn build_pcurve_on_surface(
surface: &NurbsSurface,
curve: &NurbsCurve,
) -> Result<NurbsCurve, String> {
let fit = fit_pcurve_on_surface(surface, curve)?;
record_fit(&fit.report);
Ok(fit.curve)
}
struct SectionFitClock {
started: Option<web_time::Instant>,
global: std::time::Duration,
seeded: bool,
}
impl SectionFitClock {
fn new() -> Self {
Self { started: crate::profile::profile_enabled().then(web_time::Instant::now),
global: std::time::Duration::ZERO, seeded: false }
}
}
impl Drop for SectionFitClock {
fn drop(&mut self) {
if let Some(started) = self.started {
crate::imprint::profile_emit(format_args!("pcurve.section_time global={:.3} seeded={:.3} result={}",
self.global.as_secs_f64() * 1000.0,
started.elapsed().saturating_sub(self.global).as_secs_f64() * 1000.0,
if self.seeded { "seeded" } else { "global" }));
}
}
}
pub fn fit_pcurve_on_surface_marched(
surface: &NurbsSurface,
curve: &NurbsCurve,
) -> Result<PcurveFit, String> {
fn run(surface: &NurbsSurface, curve: &NurbsCurve, eager: bool) -> Result<PcurveFit, String> {
let _samples = PcurveSampleScope::open(surface, curve, true);
let mut clock = SectionFitClock::new();
let mut fallback = || {
let started = clock.started.map(|_| web_time::Instant::now());
let fit = fit_pcurve_on_surface(surface, curve);
if let Some(started) = started { clock.global += started.elapsed(); }
fit
};
let global = if eager { Some(fallback()?) } else { None };
if !eager { curve.domain()?; }
if env_read!("BREP_SECTION_PCURVE_MARCH").as_deref() == Some("0") || surface.is_affine()? {
return global.map_or_else(&mut fallback, Ok);
}
let [t0, t1] = curve.domain()?;
if curve.evaluate(t0)?.sub(curve.evaluate(t1)?).length() <= 1e-6 {
return global.map_or_else(&mut fallback, Ok);
}
const SAMPLES: usize = 24;
let fractions: Vec<f64> = (0..=SAMPLES).map(|i| i as f64 / SAMPLES as f64).collect();
let edge: Vec<Vec3> = fractions
.iter()
.map(|fraction| curve.evaluate(t0 + (t1 - t0) * fraction))
.collect::<Result<Vec<_>, _>>()?;
let scale = 1.0 + curve.evaluate((t0 + t1) / 2.0)?.length();
let endpoint_tolerance = 1e-3 * scale;
let (first, first_distance) = invert_checked(surface, edge[0])?;
let (last, last_distance) = invert_checked(surface, edge[SAMPLES])?;
if first_distance > endpoint_tolerance || last_distance > endpoint_tolerance {
return global.map_or_else(&mut fallback, Ok);
}
let mut off_surface = first_distance.max(last_distance);
let ([u0, u1], [v0, v1]) = surface_domains(surface)?;
let u_span = (u1 - u0).abs().max(EPSILON);
let v_span = (v1 - v0).abs().max(EPSILON);
let (closed_u, closed_v) = surface_closedness(surface)?;
let norm_step = |a: [f64; 2], b: [f64; 2]| -> f64 {
let mut du = a[0] - b[0];
if closed_u {
while du > 0.5 * u_span {
du -= u_span;
}
while du < -0.5 * u_span {
du += u_span;
}
}
let mut dv = a[1] - b[1];
if closed_v {
while dv > 0.5 * v_span {
dv -= v_span;
}
while dv < -0.5 * v_span {
dv += v_span;
}
}
((du / u_span).powi(2) + (dv / v_span).powi(2)).sqrt()
};
let mut raw = vec![first];
let mut previous = first;
for index in 1..SAMPLES {
let seeded =
crate::projection::project_point_to_surface_from_seed(surface, edge[index], previous)?;
let (_, global_distance) = invert_checked(surface, edge[index])?;
if seeded.distance > 4.0 * global_distance + endpoint_tolerance {
return global.map_or_else(&mut fallback, Ok);
}
off_surface = off_surface.max(seeded.distance);
previous = [seeded.u, seeded.v];
raw.push(previous);
}
raw.push(last);
let mut steps: Vec<f64> = (1..raw.len())
.map(|i| norm_step(raw[i], raw[i - 1]))
.collect();
let endpoint_gap = steps.pop().unwrap_or(0.0);
steps.sort_by(f64::total_cmp);
let median = steps
.get(steps.len() / 2)
.copied()
.unwrap_or(0.0)
.max(EPSILON);
if endpoint_gap > (4.0 * median).max(0.05) {
return global.map_or_else(&mut fallback, Ok);
}
let mut parameters = fractions;
let (mut pcurve, excursion, distance) = build_interpolant(surface, &raw, ¶meters)?;
let refinement_tolerance = PCURVE_REFINEMENT_TOLERANCE;
let refinement = refine_pcurve(
surface,
curve,
[t0, t1],
[u0, u1],
[v0, v1],
refinement_tolerance,
&[],
&mut parameters,
&mut raw,
&mut pcurve,
off_surface,
[excursion, distance],
|_fraction, seed, on_curve| {
let seeded = crate::projection::project_point_to_surface_from_seed(surface, on_curve, [seed.x, seed.y])?;
Ok((Some([seeded.u, seeded.v]), seeded.distance))
},
)?;
clock.seeded = true;
Ok(PcurveFit {
curve: pcurve,
report: PcurveFitReport {
residual: refinement.residual,
floor: refinement_tolerance,
samples: parameters.len(),
exit: refinement.exit,
off_surface: refinement.off_surface,
raised: refinement.raised,
clamped_excursion: refinement.clamped[0],
clamped_distance: refinement.clamped[1],
},
})
}
let mode = match std::env::var("BREP_PCURVE_LAZY_GLOBAL") {
Ok(mode) => mode,
Err(std::env::VarError::NotPresent) => "on".to_owned(),
Err(std::env::VarError::NotUnicode(_)) => String::new(),
};
if mode != "check" {
return run(surface, curve, !matches!(mode.as_str(), "1" | "on"));
}
let lazy_surface = surface.clone();
let lazy_curve = curve.clone();
let eager = run(surface, curve, true);
let lazy = run(&lazy_surface, &lazy_curve, false);
let identical = match (&eager, &lazy) {
(Ok(a), Ok(b)) => {
a.curve.degree == b.curve.degree
&& a.curve.knots.len() == b.curve.knots.len()
&& a.curve.knots.iter().zip(&b.curve.knots).all(|(a,b)| a.to_bits() == b.to_bits())
&& a.curve.control_points.len() == b.curve.control_points.len()
&& a.curve.control_points.iter().zip(&b.curve.control_points).all(|(a,b)| {
[a.x.to_bits(),a.y.to_bits(),a.z.to_bits(),a.w.to_bits()]
== [b.x.to_bits(),b.y.to_bits(),b.z.to_bits(),b.w.to_bits()]
})
&& a.report == b.report
&& [a.report.residual, a.report.floor, a.report.off_surface,
a.report.clamped_excursion, a.report.clamped_distance].map(f64::to_bits)
== [b.report.residual, b.report.floor, b.report.off_surface,
b.report.clamped_excursion, b.report.clamped_distance].map(f64::to_bits)
}
(Err(a), Err(b)) => a == b,
_ => false,
};
if let Ok(path) = std::env::var("BREP_PCURVE_LAZY_GLOBAL_CENSUS") {
use std::io::Write;
let mut file = std::fs::OpenOptions::new().create(true).append(true).open(path)
.expect("open lazy-global differential ledger");
writeln!(file, "pcurve.lazy_global identical={identical} eager_ok={} lazy_ok={} degree={} controls={}",
eager.is_ok(), lazy.is_ok(), curve.degree, curve.control_points.len())
.expect("append lazy-global differential ledger");
}
assert!(identical, "lazy global pcurve fallback changed the curve, report or error");
eager
}
pub fn build_pcurve_on_surface_marched(
surface: &NurbsSurface,
curve: &NurbsCurve,
) -> Result<NurbsCurve, String> {
let fit = fit_pcurve_on_surface_marched(surface, curve)?;
record_fit(&fit.report);
Ok(fit.curve)
}
pub fn fit_pcurve_on_surface_range(
surface: &NurbsSurface,
curve: &NurbsCurve,
edge_start: f64,
edge_end: f64,
forward: bool,
tolerance: f64,
) -> Result<PcurveFit, String> {
if let Some(exact) =
affine_pcurve_on_range(surface, curve, edge_start, edge_end, forward, tolerance)?
{
return Ok(exact);
}
fit_pcurve_on_surface_range_dense(
surface, curve, edge_start, edge_end, forward, tolerance, 64, 3, 513,
)
}
pub fn build_pcurve_on_surface_range(
surface: &NurbsSurface,
curve: &NurbsCurve,
edge_start: f64,
edge_end: f64,
forward: bool,
tolerance: f64,
) -> Result<NurbsCurve, String> {
accept_fit(fit_pcurve_on_surface_range(
surface, curve, edge_start, edge_end, forward, tolerance,
)?)
}
fn station_fit_tracing() -> bool {
debug_flag!("BREP_DEBUG_STATION_FIT")
}
const SPAN_FLOOR: f64 = 1e-6;
const RAISED_ROUNDS: usize = 40;
pub const PCURVE_OFF_BAR: &str = "pcurve fit refused: the trim misses its stations by";
fn accept_fit(fit: PcurveFit) -> Result<NurbsCurve, String> {
let report = fit.report;
if report.on_bar() {
return Ok(fit.curve);
}
Err(off_bar_message(&report))
}
fn off_bar_message(report: &PcurveFitReport) -> String {
format!(
"{PCURVE_OFF_BAR} {:.3e} out of sample against a bar of {:.3e} (asked {:.1e}, the \
stations stand {:.3e} off the carrier; {:?} at {} samples{}{})",
report.residual,
report.floor + report.off_surface,
report.floor,
report.off_surface,
report.exit,
report.samples,
if report.raised { ", after the raise" } else { "" },
if report.clamped_excursion > 0.0 {
format!(
"; clamped into the chart by {:.3e} in parameter, {:.3e} in 3D",
report.clamped_excursion, report.clamped_distance
)
} else {
String::new()
},
)
}
pub(crate) const PCURVE_OFF_BAR_WHAT: &str = "pcurve_fit_off_bar";
pub(crate) fn is_pcurve_off_bar(refusal: &crate::KernelRefusal) -> bool {
matches!(&refusal.class, crate::RefusalClass::NonConvergence { what } if what == PCURVE_OFF_BAR_WHAT)
}
pub(crate) fn build_pcurve_on_surface_range_classed(
surface: &NurbsSurface,
curve: &NurbsCurve,
edge_start: f64,
edge_end: f64,
forward: bool,
tolerance: f64,
stage: KernelStage,
what: &'static str,
) -> Result<NurbsCurve, crate::KernelRefusal> {
use crate::OrRefuse;
let fit = fit_pcurve_on_surface_range(surface, curve, edge_start, edge_end, forward, tolerance)
.or_refuse(stage, what)?;
accept_fit_classed(fit, stage)
}
pub(crate) fn accept_fit_classed(fit: PcurveFit, stage: KernelStage) -> Result<NurbsCurve, crate::KernelRefusal> {
if fit.report.on_bar() {
return Ok(fit.curve);
}
Err(crate::KernelRefusal {
class: crate::RefusalClass::NonConvergence { what: PCURVE_OFF_BAR_WHAT.into() },
stage,
message: off_bar_message(&fit.report),
})
}
fn affine_pcurve_on_range(
surface: &NurbsSurface,
curve: &NurbsCurve,
edge_start: f64,
edge_end: f64,
forward: bool,
tolerance: f64,
) -> Result<Option<PcurveFit>, String> {
if std::env::var("BREP_AFFINE_RANGE_PCURVE").as_deref() == Ok("0") {
return Ok(None);
}
let Some(inversion) = AffineInversion::of(surface)? else {
return Ok(None);
};
if !(edge_start.is_finite() && edge_end.is_finite() && edge_start < edge_end) {
return Ok(None);
}
let [t0, t1] = curve.domain()?;
let start = edge_start.max(t0);
let end = edge_end.min(t1);
if end - start <= 2.0 * KNOT_IDENTITY_TOL {
return Ok(None);
}
let mut restricted = curve.clone();
if end < t1 - KNOT_IDENTITY_TOL {
restricted = restricted.split(end)?.0;
}
if start > t0 + KNOT_IDENTITY_TOL {
restricted = restricted.split(start)?.1;
}
let mut pcurve = inversion.image_of(&restricted)?;
if !forward {
pcurve = pcurve.reversed()?;
}
let first = pcurve.knots[0];
let last = pcurve.knots[pcurve.knots.len() - 1];
if !(last - first > 0.0) {
return Ok(None);
}
let knots = pcurve
.knots
.iter()
.map(|knot| (knot - first) / (last - first))
.collect::<Vec<_>>();
let pcurve = NurbsCurve::new(pcurve.degree, knots, pcurve.control_points.clone())?;
let scale = 1.0 + curve.evaluate((start + end) / 2.0)?.length();
let bar = tolerance.max(1e-11 * scale);
let mut residual = 0.0_f64;
for index in 0..=32 {
let fraction = index as f64 / 32.0;
let uv = pcurve.evaluate(fraction)?;
let on_carrier = surface.evaluate_extended(uv.x, uv.y)?;
let edge_fraction = if forward { fraction } else { 1.0 - fraction };
let on_edge = curve.evaluate(start + (end - start) * edge_fraction)?;
residual = residual.max(on_carrier.sub(on_edge).length());
if residual > bar {
return Ok(None);
}
}
let samples = pcurve.control_points.len();
Ok(Some(PcurveFit {
curve: pcurve,
report: PcurveFitReport {
residual,
floor: bar,
samples,
exit: PcurveFitExit::Converged,
off_surface: 0.0,
raised: false,
clamped_excursion: 0.0,
clamped_distance: 0.0,
},
}))
}
fn align_collapsed_endpoints(surface: &NurbsSurface, raw: &mut [[f64; 2]]) -> Result<(), String> {
let anchor = surface.control_points[0][0].point()?;
let mut extent = 0.0_f64;
for control in surface.control_points.iter().flatten() {
extent = extent.max(control.point()?.sub(anchor).length());
}
let pole_band = (1e-10 * (1.0 + extent)).min(LINEAR_TOLERANCE);
for (endpoint, neighbor) in [(0, 1), (raw.len() - 1, raw.len() - 2)] {
let point = surface.evaluate(raw[endpoint][0], raw[endpoint][1])?;
for axis in 0..2 {
let mut candidate = raw[endpoint];
candidate[axis] = raw[neighbor][axis];
if candidate == raw[endpoint]
|| surface
.evaluate(candidate[0], candidate[1])?
.sub(point)
.length()
> pole_band
{
continue;
}
let row = if axis == 0 {
surface.iso_curve_v(raw[endpoint][1])?
} else {
surface.iso_curve_u(raw[endpoint][0])?
};
let mut collapsed = true;
for control in &row.control_points {
if control.point()?.sub(point).length() > pole_band {
collapsed = false;
break;
}
}
if collapsed {
raw[endpoint] = candidate;
}
}
}
Ok(())
}
fn repair_branch_jumps(
surface: &NurbsSurface,
edge_points: &[Vec3],
raw: &mut [[f64; 2]],
tolerance: f64,
) -> Result<(), String> {
if raw.len() < 3 {
return Ok(());
}
if surface.is_affine()? {
return Ok(());
}
if std::env::var("BREP_NO_PCURVE_REPAIR").is_ok() {
return Ok(());
}
align_collapsed_endpoints(surface, raw)?;
let ([u0, u1], [v0, v1]) = surface_domains(surface)?;
let u_span = (u1 - u0).abs().max(EPSILON);
let v_span = (v1 - v0).abs().max(EPSILON);
let (closed_u, closed_v) = surface_closedness(surface)?;
let norm_step = |a: [f64; 2], b: [f64; 2]| -> f64 {
let mut du = a[0] - b[0];
if closed_u {
while du > 0.5 * u_span {
du -= u_span;
}
while du < -0.5 * u_span {
du += u_span;
}
}
let mut dv = a[1] - b[1];
if closed_v {
while dv > 0.5 * v_span {
dv -= v_span;
}
while dv < -0.5 * v_span {
dv += v_span;
}
}
((du / u_span).powi(2) + (dv / v_span).powi(2)).sqrt()
};
const JUMP_THRESHOLD: f64 = 0.2;
let count = raw.len();
let (mut best_start, mut best_len, mut run_start) = (0usize, 1usize, 0usize);
for index in 1..count {
if norm_step(raw[index], raw[index - 1]) > JUMP_THRESHOLD {
if index - run_start > best_len {
best_len = index - run_start;
best_start = run_start;
}
run_start = index;
}
}
if count - run_start > best_len {
best_len = count - run_start;
best_start = run_start;
}
let (spine_lo, spine_hi) = (best_start, best_start + best_len - 1);
let reseat = |edge_point: Vec3,
previous: [f64; 2],
global: [f64; 2]|
-> Result<[f64; 2], String> {
let global_step = norm_step(global, previous);
if global_step <= JUMP_THRESHOLD {
return Ok(global);
}
let seeded =
project_point_to_surface_seeded(surface, edge_point, previous[0], previous[1])?;
let candidate = [seeded.u, seeded.v];
let global_residual = surface
.evaluate(global[0], global[1])?
.sub(edge_point)
.length();
let on_surface = seeded.distance <= 4.0 * global_residual + tolerance.max(1e-12);
if on_surface && norm_step(candidate, previous) < 0.5 * global_step {
if std::env::var("BREP_DEBUG_PCURVE").is_ok() {
eprintln!(
"pcurve repair: jump {global_step:.4} ({global:?}) -> {:.4} ({candidate:?}) res {:.2e}->{:.2e}",
norm_step(candidate, previous),
global_residual,
seeded.distance
);
}
Ok(candidate)
} else {
Ok(global)
}
};
let mut previous = raw[spine_hi];
for index in (spine_hi + 1)..count.saturating_sub(1) {
raw[index] = reseat(edge_points[index], previous, raw[index])?;
previous = raw[index];
}
let mut previous = raw[spine_lo];
for index in (1..spine_lo).rev() {
raw[index] = reseat(edge_points[index], previous, raw[index])?;
previous = raw[index];
}
Ok(())
}
#[allow(clippy::too_many_arguments)]
pub fn fit_pcurve_on_surface_range_dense(
surface: &NurbsSurface,
curve: &NurbsCurve,
edge_start: f64,
edge_end: f64,
forward: bool,
tolerance: f64,
base_samples: usize,
refinement_rounds: usize,
parameter_cap: usize,
) -> Result<PcurveFit, String> {
if !(edge_start.is_finite() && edge_end.is_finite() && edge_start < edge_end) {
return Err("build_pcurve_on_surface_range: invalid edge interval".into());
}
let evaluate_edge = |fraction: f64| {
let edge_fraction = if forward { fraction } else { 1.0 - fraction };
curve.evaluate(edge_start + (edge_end - edge_start) * edge_fraction)
};
let breaks = range_breaks(curve, edge_start, edge_end, forward);
let ask = tolerance.max(PCURVE_REFINEMENT_TOLERANCE);
let fit = fit_station_pcurve(
surface,
&evaluate_edge,
&breaks,
&breaks,
ask,
base_samples,
refinement_rounds,
parameter_cap,
SPAN_FLOOR,
)?;
end_span_challenger(surface, curve, &evaluate_edge, edge_start, edge_end, forward, &breaks, ask, base_samples, refinement_rounds, parameter_cap, fit)
}
fn native_end_knot_fractions(curve: &NurbsCurve, edge_start: f64, edge_end: f64, forward: bool, pcurve: &NurbsCurve) -> Result<Vec<f64>, String> {
let [q0, q1] = pcurve.domain()?;
let mut interior: Vec<f64> = pcurve.knots.iter().copied().filter(|k| *k > q0 && *k < q1).collect();
interior.dedup();
let (Some(&first), Some(&last)) = (interior.first(), interior.last()) else { return Ok(Vec::new()) };
let (low, high) = (edge_start.min(edge_end), edge_start.max(edge_end));
let span = edge_end - edge_start;
let mut fractions: Vec<f64> = curve
.knots
.iter()
.copied()
.filter(|k| *k > low && *k < high)
.map(|k| {
let along = (k - edge_start) / span;
if forward { along } else { 1.0 - along }
})
.filter(|f| f.is_finite() && ((*f > q0 && *f < first) || (*f > last && *f < q1)))
.collect();
fractions.sort_by(f64::total_cmp);
fractions.dedup();
Ok(fractions)
}
fn foot_admitted(foot: &crate::SurfaceProjection, [u0, u1]: [f64; 2], [v0, v1]: [f64; 2]) -> bool {
let finite = |p: Vec3| p.x.is_finite() && p.y.is_finite() && p.z.is_finite();
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)
}
fn verification_fractions(pcurve: &NurbsCurve, verify: &[f64]) -> Result<Vec<f64>, String> {
let mut fractions = native_probe_fractions(&[pcurve])?;
fractions.extend(pcurve.knots.iter().copied());
fractions.extend(verify.iter().copied());
fractions.retain(|f| f.is_finite() && (0.0..=1.0).contains(f));
fractions.sort_by(f64::total_cmp);
fractions.dedup();
Ok(fractions)
}
pub(crate) fn floor_admits(old: [f64; 3], new: [f64; 3]) -> bool {
let floor = PCURVE_REFINEMENT_TOLERANCE;
old.iter().chain(new.iter()).all(|v| v.is_finite())
&& new[0] < old[0]
&& (new[1] <= old[1] || (new[0] <= floor && new[2] <= floor))
}
fn common_foot(
global: Option<crate::SurfaceProjection>,
reference: Option<crate::SurfaceProjection>,
candidate: Option<crate::SurfaceProjection>,
domain_u: [f64; 2],
domain_v: [f64; 2],
) -> Option<crate::SurfaceProjection> {
[global, reference, candidate]
.into_iter()
.flatten()
.filter(|f| foot_admitted(f, domain_u, domain_v))
.min_by(|a, b| a.distance.total_cmp(&b.distance))
}
pub(crate) fn range_use_probes(curves: &[&NurbsCurve], edge_curve: &NurbsCurve, t0: f64, t1: f64, forward: bool) -> Result<Vec<f64>, String> {
let mut probes = native_probe_fractions(curves)?;
for curve in curves {
probes.extend(curve.knots.iter().copied());
}
let span = t1 - t0;
if span.is_finite() && span != 0.0 {
let (low, high) = (t0.min(t1), t0.max(t1));
let mut knots: Vec<f64> = edge_curve.knots.iter().copied().filter(|k| *k >= low && *k <= high).collect();
knots.push(low);
knots.push(high);
knots.sort_by(f64::total_cmp);
knots.dedup();
let locals: Vec<f64> = [0.25, 0.5, 0.75]
.into_iter()
.chain((1..=TRACKING_ACCEPTANCE_POINTS).map(|index| index as f64 / (TRACKING_ACCEPTANCE_POINTS + 1) as f64))
.collect();
let mut ts = knots.clone();
for pair in knots.windows(2).filter(|w| w[1] > w[0]) {
for &local in &locals {
ts.push(pair[0] + (pair[1] - pair[0]) * local);
}
}
for t in ts {
let along = (t - t0) / span;
probes.push(if forward { along } else { 1.0 - along });
}
}
probes.retain(|f| f.is_finite() && (0.0..=1.0).contains(f));
probes.sort_by(f64::total_cmp);
probes.dedup();
Ok(probes)
}
#[cfg_attr(not(test), allow(dead_code))]
pub(crate) fn range_common_read(
surface: &NurbsSurface,
edge_curve: &NurbsCurve,
t0: f64,
t1: f64,
forward: bool,
old: &NurbsCurve,
new: &NurbsCurve,
) -> Result<((f64, f64), (f64, f64)), String> {
let (o, n) = range_common_read_with_excess(surface, edge_curve, t0, t1, forward, old, new)?;
Ok(((o[0], o[1]), (n[0], n[1])))
}
#[cfg_attr(not(test), allow(dead_code))]
pub(crate) fn range_common_read_with_excess(
surface: &NurbsSurface,
edge_curve: &NurbsCurve,
t0: f64,
t1: f64,
forward: bool,
old: &NurbsCurve,
new: &NurbsCurve,
) -> Result<([f64; 3], [f64; 3]), String> {
for curve in [old, new] {
if !matches!(curve.domain(), Ok([a, b]) if a == 0.0 && b == 1.0) {
return Err("range common read: a trim not on [0, 1]".into());
}
}
let probes = range_use_probes(&[old, new], edge_curve, t0, t1, forward)?;
let evaluate = |fraction: f64| -> Result<Vec3, String> {
let along = if forward { fraction } else { 1.0 - fraction };
edge_curve.evaluate(t0 + (t1 - t0) * along)
};
common_station_read_with_excess(surface, &evaluate, old, new, &probes)
}
pub(crate) fn common_station_read(
surface: &NurbsSurface,
evaluate_edge: &dyn Fn(f64) -> Result<Vec3, String>,
legacy: &NurbsCurve,
candidate: &NurbsCurve,
probes: &[f64],
) -> Result<((f64, f64), (f64, f64)), String> {
let (old, new) = common_station_read_with_excess(surface, evaluate_edge, legacy, candidate, probes)?;
Ok(((old[0], old[1]), (new[0], new[1])))
}
pub(crate) fn common_station_read_with_excess(
surface: &NurbsSurface,
evaluate_edge: &dyn Fn(f64) -> Result<Vec3, String>,
legacy: &NurbsCurve,
candidate: &NurbsCurve,
probes: &[f64],
) -> Result<([f64; 3], [f64; 3]), String> {
let (domain_u, domain_v) = surface_domains(surface)?;
let finite = |p: Vec3| p.x.is_finite() && p.y.is_finite() && p.z.is_finite();
let mut read = ([0.0_f64, 0.0, f64::NEG_INFINITY], [0.0_f64, 0.0, f64::NEG_INFINITY]);
let same = std::ptr::eq(legacy, candidate);
let ellipsoid = if same && surface.analytic().is_none() { surface.affine_sphere() } else { None };
for &fraction in probes {
let point = evaluate_edge(fraction)?;
let old_uv = legacy.evaluate(fraction)?;
let new_uv = if same { old_uv } else { candidate.evaluate(fraction)? };
let old_image = surface.evaluate_extended(old_uv.x, old_uv.y)?;
let new_image = if same { old_image } else { surface.evaluate_extended(new_uv.x, new_uv.y)? };
if !(finite(point) && finite(old_image) && finite(new_image)) {
return Err(format!("common station read: non-finite point at fraction {fraction}"));
}
let closed_form = ellipsoid.and_then(|ellipsoid| ellipsoid.project(surface, point));
let foot = if let Some(foot) = closed_form {
common_foot(Some(foot), Some(foot), Some(foot), domain_u, domain_v)
} else {
let reference_foot = memo_seeded_foot(surface, point, old_uv.x, old_uv.y);
let candidate_foot = if same {
reference_foot
} else {
memo_seeded_foot(surface, point, new_uv.x, new_uv.y)
};
common_foot(
memo_global_foot(surface, point),
reference_foot,
candidate_foot,
domain_u,
domain_v,
)
}
.ok_or_else(|| format!("common station read: no admitted foot at fraction {fraction}"))?;
let values = [
old_image.sub(foot.point).length(),
old_image.sub(point).length(),
new_image.sub(foot.point).length(),
new_image.sub(point).length(),
];
if values.iter().any(|v| !v.is_finite()) {
return Err(format!("common station read: non-finite distance at fraction {fraction}"));
}
if !foot.distance.is_finite() {
return Err(format!("common station read: non-finite foot distance at fraction {fraction}"));
}
read.0[0] = read.0[0].max(values[0]);
read.0[1] = read.0[1].max(values[1]);
read.0[2] = read.0[2].max(values[1] - foot.distance);
read.1[0] = read.1[0].max(values[2]);
read.1[1] = read.1[1].max(values[3]);
read.1[2] = read.1[2].max(values[3] - foot.distance);
}
Ok(read)
}
fn edge_end_span_fractions(curve: &NurbsCurve, edge_start: f64, edge_end: f64, forward: bool) -> Vec<f64> {
let (low, high) = (edge_start.min(edge_end), edge_start.max(edge_end));
let mut knots: Vec<f64> = curve.knots.iter().copied().filter(|k| *k > low && *k < high).collect();
knots.dedup();
let spans = match (knots.first(), knots.last()) {
(Some(&first), Some(&last)) => vec![(low, first), (last, high)],
_ => vec![(low, high)],
};
let span = edge_end - edge_start;
let mut out = Vec::new();
for (a, b) in spans {
if !(b > a) {
continue;
}
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)) {
let along = (a + (b - a) * local - edge_start) / span;
let fraction = if forward { along } else { 1.0 - along };
if fraction.is_finite() && (0.0..=1.0).contains(&fraction) {
out.push(fraction);
}
}
}
out.sort_by(f64::total_cmp);
out.dedup();
out
}
const WORST_SPANS: usize = 4;
const WORST_SPAN_SEEDS: usize = 7;
fn legacy_worst_span_seeds(
evaluate_edge: &dyn Fn(f64) -> Result<Vec3, String>,
surface: &NurbsSurface,
pcurve: &NurbsCurve,
bar: f64,
extra_probes: &[f64],
) -> Result<Vec<f64>, String> {
let [q0, q1] = pcurve.domain()?;
let mut knots: Vec<f64> = pcurve.knots.iter().copied().filter(|k| *k >= q0 && *k <= q1).collect();
knots.dedup();
let locals: Vec<f64> = [0.25, 0.5, 0.75]
.into_iter()
.chain((1..=TRACKING_ACCEPTANCE_POINTS).map(|index| index as f64 / (TRACKING_ACCEPTANCE_POINTS + 1) as f64))
.collect();
let mut over: Vec<(f64, f64, f64)> = Vec::new();
for span in knots.windows(2).filter(|w| w[1] > w[0]) {
let mut worst = 0.0_f64;
let inside = extra_probes.iter().copied().filter(|f| *f > span[0] && *f < span[1]);
for fraction in locals.iter().map(|local| span[0] + (span[1] - span[0]) * local).chain(inside) {
let uv = pcurve.evaluate(fraction)?;
let deviation = surface.evaluate_extended(uv.x, uv.y)?.sub(evaluate_edge(fraction)?).length();
if !deviation.is_finite() {
return Err(format!("worst-span read: non-finite deviation at fraction {fraction}"));
}
worst = worst.max(deviation);
}
if worst > bar {
over.push((worst, span[0], span[1]));
}
}
over.sort_by(|a, b| b.0.total_cmp(&a.0).then(a.1.total_cmp(&b.1)));
over.truncate(WORST_SPANS);
Ok(over
.into_iter()
.flat_map(|(_, lo, hi)| (1..=WORST_SPAN_SEEDS).map(move |index| lo + (hi - lo) * index as f64 / (WORST_SPAN_SEEDS + 1) as f64))
.collect())
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
enum ChallengerTrigger {
Deviation,
Tracking,
}
fn challenger_trigger(residual: f64, off_surface: f64, ask: f64, tracking: impl FnOnce() -> Option<f64>) -> Option<ChallengerTrigger> {
if residual > ask + off_surface {
return Some(ChallengerTrigger::Deviation);
}
if !(off_surface > ask) {
return None;
}
match tracking() {
Some(value) if value.is_finite() && value > ask => Some(ChallengerTrigger::Tracking),
_ => None,
}
}
#[allow(clippy::too_many_arguments)]
fn end_span_challenger(
surface: &NurbsSurface,
curve: &NurbsCurve,
evaluate_edge: &dyn Fn(f64) -> Result<Vec3, String>,
edge_start: f64,
edge_end: f64,
forward: bool,
breaks: &[f64],
ask: f64,
base_samples: usize,
refinement_rounds: usize,
parameter_cap: usize,
legacy: PcurveFit,
) -> Result<PcurveFit, String> {
if !(legacy.report.residual > ask + legacy.report.off_surface) {
return Ok(legacy);
}
let _feet = FootMemoScope::open(surface);
let Ok(end_knots) = native_end_knot_fractions(curve, edge_start, edge_end, forward, &legacy.curve) else { return Ok(legacy) };
let edge_end_probes = edge_end_span_fractions(curve, edge_start, edge_end, forward);
let Ok(mut fixed) = native_probe_fractions(&[&legacy.curve]) else { return Ok(legacy) };
fixed.extend(edge_end_probes.iter().copied());
let (low, high) = (edge_start.min(edge_end), edge_start.max(edge_end));
let mut edge_knots: Vec<f64> = curve.knots.iter().copied().filter(|k| *k >= low && *k <= high).collect();
edge_knots.push(low);
edge_knots.push(high);
edge_knots.sort_by(f64::total_cmp);
edge_knots.dedup();
let to_fraction = |t: f64| {
let along = (t - edge_start) / (edge_end - edge_start);
if forward { along } else { 1.0 - along }
};
for span in edge_knots.windows(2).filter(|w| w[1] > w[0]) {
for local in [0.25, 0.5, 0.75] {
fixed.push(to_fraction(span[0] + (span[1] - span[0]) * local));
}
}
fixed.extend(edge_knots.iter().map(|&t| to_fraction(t)));
fixed.extend(end_knots.iter().copied());
fixed.extend(legacy.curve.knots.iter().copied());
fixed.retain(|f| f.is_finite() && (0.0..=1.0).contains(f));
fixed.sort_by(f64::total_cmp);
fixed.dedup();
let trigger = challenger_trigger(legacy.report.residual, legacy.report.off_surface, ask, || {
common_station_read(surface, evaluate_edge, &legacy.curve, &legacy.curve, &fixed).ok().map(|((tracking, _), _)| tracking)
});
let Some(trigger) = trigger else { return Ok(legacy) };
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) };
if trigger == ChallengerTrigger::Deviation && end_knots.is_empty() && worst_seeds.is_empty() {
return Ok(legacy);
}
let mut stations: Vec<f64> = breaks.iter().copied().chain(end_knots.iter().copied()).chain(worst_seeds.iter().copied()).collect();
stations.sort_by(f64::total_cmp);
stations.dedup();
let initial = base_samples.max(1).checked_add(1).and_then(|count| count.checked_add(stations.len()));
if initial.is_none_or(|count| count > parameter_cap) {
return Ok(legacy);
}
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 {
return Ok(legacy);
};
if !(candidate.report.residual.is_finite() && candidate.report.off_surface.is_finite() && candidate.report.clamped_excursion.is_finite() && candidate.report.clamped_distance.is_finite()) {
return Ok(legacy);
}
let Ok(mut probes) = native_probe_fractions(&[&candidate.curve]) else { return Ok(legacy) };
probes.extend(fixed.iter().copied());
probes.extend(candidate.curve.knots.iter().copied());
probes.retain(|f| f.is_finite() && (0.0..=1.0).contains(f));
probes.sort_by(f64::total_cmp);
probes.dedup();
let readings = common_station_read_with_excess(surface, evaluate_edge, &legacy.curve, &candidate.curve, &probes);
let accepted = matches!(&readings, Ok((old, new)) if floor_admits(*old, *new));
if station_fit_tracing() {
eprintln!(
"STATION-FIT end-span challenger: trigger={trigger:?} end_knots={} worst_span_seeds={} edge_end_probes={} legacy={:?}/{:e} candidate={:?}/{:e} common={readings:?} decision={}",
end_knots.len(), worst_seeds.len(), edge_end_probes.len(), legacy.report.exit, legacy.report.residual, candidate.report.exit, candidate.report.residual,
if accepted { "candidate" } else { "legacy" }
);
}
Ok(if accepted { candidate } else { legacy })
}
#[allow(clippy::too_many_arguments)]
pub fn build_pcurve_on_surface_range_dense(
surface: &NurbsSurface,
curve: &NurbsCurve,
edge_start: f64,
edge_end: f64,
forward: bool,
tolerance: f64,
base_samples: usize,
refinement_rounds: usize,
parameter_cap: usize,
) -> Result<NurbsCurve, String> {
accept_fit(fit_pcurve_on_surface_range_dense(
surface,
curve,
edge_start,
edge_end,
forward,
tolerance,
base_samples,
refinement_rounds,
parameter_cap,
)?)
}
pub(crate) fn range_breaks(
curve: &NurbsCurve,
edge_start: f64,
edge_end: f64,
forward: bool,
) -> Vec<f64> {
let mut fractions = Vec::new();
let span = edge_end - edge_start;
if !(span.abs() > 0.0) {
return fractions;
}
let (low, high) = (edge_start.min(edge_end), edge_start.max(edge_end));
let mut index = 0;
while index < curve.knots.len() {
let value = curve.knots[index];
let run = curve.knots[index..]
.iter()
.take_while(|knot| **knot == value)
.count();
if value > low && value < high && run >= curve.degree.max(1) {
let along = (value - edge_start) / span;
fractions.push(if forward { along } else { 1.0 - along });
}
index += run;
}
fractions.sort_by(f64::total_cmp);
fractions
}
#[allow(clippy::too_many_arguments)]
pub fn fit_pcurve_on_surface_stations(
surface: &NurbsSurface,
stations: &dyn Fn(f64) -> Result<Vec3, String>,
breaks: &[f64],
tolerance: f64,
base_samples: usize,
refinement_rounds: usize,
parameter_cap: usize,
) -> Result<PcurveFit, String> {
fit_station_pcurve(
surface, stations, breaks, &[], tolerance.max(PCURVE_REFINEMENT_TOLERANCE),
base_samples, refinement_rounds, parameter_cap, SPAN_FLOOR,
)
}
pub(crate) fn analytic_station_pcurve(
surface: &NurbsSurface,
stations: &dyn Fn(f64) -> Result<Vec3, String>,
tolerance: f64,
) -> Result<NurbsCurve, String> {
if surface.analytic().is_none() {
return Err("analytic pcurve requires an analytic carrier".into());
}
let mut breaks = Vec::new();
for _ in 0..4 {
let fit = fit_station_pcurve(surface, stations, &breaks, &[], tolerance, 64, 64, 8192, 1e-10)?;
if fit.report.residual > tolerance || fit.report.off_surface > tolerance {
return Err(format!(
"analytic pcurve construction missed its contract: {:?}",
fit.report
));
}
let mut failed = Vec::new();
for pair in fit.curve.knots.windows(2) {
if pair[1] <= pair[0] {
continue;
}
for local in [
0.06943184420297371,
0.33000947820757187,
0.6699905217924281,
0.9305681557970262,
] {
let t = pair[0] + (pair[1] - pair[0]) * local;
let uv = fit.curve.evaluate(t)?;
if surface
.evaluate_extended(uv.x, uv.y)?
.sub(stations(t)?)
.length()
> tolerance
{
failed.push(t);
}
}
}
if failed.is_empty() {
return Ok(fit.curve);
}
if breaks.len() + failed.len() > 8192 {
break;
}
breaks.extend(failed);
breaks.sort_by(f64::total_cmp);
breaks.dedup();
}
Err("analytic pcurve failed independent knot-span witnesses".into())
}
#[allow(clippy::too_many_arguments)]
fn fit_station_pcurve(
surface: &NurbsSurface,
stations: &dyn Fn(f64) -> Result<Vec3, String>,
breaks: &[f64],
corners: &[f64],
tolerance: f64,
base_samples: usize,
refinement_rounds: usize,
parameter_cap: usize,
span_floor: f64,
) -> Result<PcurveFit, String> {
fit_station_pcurve_mode(surface, stations, breaks, corners, tolerance, base_samples, refinement_rounds, parameter_cap, span_floor, false, None, &[])
}
#[allow(clippy::too_many_arguments)]
fn fit_station_pcurve_mode(
surface: &NurbsSurface,
stations: &dyn Fn(f64) -> Result<Vec3, String>,
breaks: &[f64],
corners: &[f64],
tolerance: f64,
base_samples: usize,
refinement_rounds: usize,
parameter_cap: usize,
span_floor: f64,
track_projection: bool,
reference: Option<&NurbsCurve>,
verify: &[f64],
) -> Result<PcurveFit, String> {
let domains = if track_projection { Some(surface_domains(surface)?) } else { None };
let tracking_of = |represented: Vec3, edge_point: Vec3, uv: Vec3, fraction: f64| -> Result<(f64, [f64; 2], f64), String> {
let (domain_u, domain_v) = domains.ok_or_else(|| "station tracking: legacy mode".to_string())?;
let finite = |p: Vec3| p.x.is_finite() && p.y.is_finite() && p.z.is_finite();
let reference_seed = match reference {
Some(curve) => curve.evaluate(fraction).ok().and_then(|seed| memo_seeded_foot(surface, edge_point, seed.x, seed.y)),
None => None,
};
let foot = common_foot(
memo_global_foot(surface, edge_point),
reference_seed,
memo_seeded_foot(surface, edge_point, uv.x, uv.y),
domain_u,
domain_v,
)
.ok_or_else(|| "station tracking: no admitted foot".to_string())?;
let tracking = represented.sub(foot.point).length();
if !(finite(represented) && tracking.is_finite()) {
return Err("station tracking: non-finite reading".into());
}
Ok((tracking, [foot.u, foot.v], foot.distance))
};
let mut tracking_unmet = false;
let evaluate_edge = stations;
let base_samples = base_samples.max(1);
let mut parameters = (0..=base_samples)
.map(|index| index as f64 / base_samples as f64)
.collect::<Vec<_>>();
let mut joins = Vec::with_capacity(corners.len());
for &fraction in breaks {
if !(fraction > 0.0 && fraction < 1.0) {
continue;
}
let corner = corners.contains(&fraction);
let at = parameters.partition_point(|parameter| *parameter < fraction);
let near_left = at > 0 && fraction - parameters[at - 1] <= span_floor;
let near_right = at < parameters.len() && parameters[at] - fraction <= span_floor;
if near_left || near_right {
if corner {
joins.push(if near_right { parameters[at] } else { parameters[at - 1] });
}
continue;
}
parameters.insert(at, fraction);
if corner {
joins.push(fraction);
}
}
let mut edge_points = parameters
.iter()
.map(|fraction| evaluate_edge(*fraction))
.collect::<Result<Vec<_>, _>>()?;
let mut off_surface = 0.0_f64;
let mut raw = Vec::with_capacity(edge_points.len());
let mut gaps = Vec::with_capacity(edge_points.len());
for point in &edge_points {
let (parameter, gap) = invert_checked(surface, *point)?;
off_surface = off_surface.max(gap);
raw.push(parameter);
gaps.push(gap);
}
repair_branch_jumps(surface, &edge_points, &mut raw, tolerance)?;
let (mut pcurve, mut excursion, mut distance) =
build_interpolant_joined(surface, &raw, ¶meters, &joins)?;
let mut cap = parameter_cap.max(parameters.len());
let mut rounds = refinement_rounds;
let mut raised = false;
loop {
let mut exit = PcurveFitExit::RoundBudget;
let mut converged_max = None;
let mut tracking_met = false;
for _ in 0..rounds {
if parameters.len() >= cap {
exit = PcurveFitExit::SampleCeiling;
break;
}
let target = tolerance;
let mut candidates = Vec::new();
let mut round_max = 0.0_f64;
let mut truncated = false;
let mut skipped_narrow = false;
let worst_first = worst_first();
'spans: for index in 0..parameters.len() - 1 {
if parameters[index + 1] - parameters[index] < span_floor {
skipped_narrow = true;
continue;
}
for local in [0.25, 0.5, 0.75] {
if !worst_first && parameters.len() + candidates.len() >= cap {
truncated = true;
break 'spans;
}
let fraction =
parameters[index] + (parameters[index + 1] - parameters[index]) * local;
let uv = pcurve.evaluate(fraction)?;
let represented = surface.evaluate_extended(uv.x, uv.y)?;
let edge_point = evaluate_edge(fraction)?;
let deviation = represented.sub(edge_point).length();
let (reading, foot) = if track_projection {
let (tracking, foot_uv, foot_gap) = tracking_of(represented, edge_point, uv, fraction)?;
(tracking, Some((foot_uv, foot_gap)))
} else {
(deviation, None)
};
round_max = round_max.max(reading);
if reading <= target {
continue;
}
candidates.push((index, fraction, edge_point, uv, reading, foot));
}
}
let mut verify_blocked = false;
if track_projection && candidates.is_empty() && !truncated && !skipped_narrow {
for fraction in verification_fractions(&pcurve, verify)? {
let index = parameters.partition_point(|parameter| *parameter <= fraction).saturating_sub(1).min(parameters.len() - 2);
let uv = pcurve.evaluate(fraction)?;
let represented = surface.evaluate_extended(uv.x, uv.y)?;
let edge_point = evaluate_edge(fraction)?;
let (tracking, foot_uv, foot_gap) = tracking_of(represented, edge_point, uv, fraction)?;
round_max = round_max.max(tracking);
if tracking <= target {
continue;
}
if fraction - parameters[index] <= span_floor || parameters[index + 1] - fraction <= span_floor {
verify_blocked = true;
continue;
}
if let Some(last) = candidates.last_mut() {
if last.0 == index && fraction - last.1 <= span_floor {
if tracking > last.4 {
*last = (index, fraction, edge_point, uv, tracking, Some((foot_uv, foot_gap)));
}
continue;
}
}
candidates.push((index, fraction, edge_point, uv, tracking, Some((foot_uv, foot_gap))));
}
}
tracking_unmet = track_projection && round_max > target;
let room = cap.saturating_sub(parameters.len());
if candidates.len() > room {
truncated = true;
let mut order: Vec<usize> = (0..candidates.len()).collect();
order.sort_by(|&a, &b| candidates[b].4.total_cmp(&candidates[a].4).then(a.cmp(&b)));
order.truncate(room);
order.sort_unstable();
candidates = order.into_iter().map(|index| candidates[index]).collect();
}
let mut inserts = Vec::with_capacity(candidates.len());
for (index, fraction, edge_point, uv, _, foot) in candidates {
let (parameter, gap) = match foot {
Some(placed) => placed,
None => invert_near(surface, edge_point, [uv.x, uv.y], gaps[index].max(gaps[index + 1]))?,
};
inserts.push((index + 1, fraction, edge_point, parameter, gap));
}
if station_fit_tracing() {
eprintln!(
"STATION-FIT round: samples={} target={target:.3e} round_max={round_max:.3e} inserts={} truncated={truncated}{}",
parameters.len(),
inserts.len(),
if track_projection { " mode=tracking" } else { "" }
);
}
if inserts.is_empty() {
exit = if truncated {
PcurveFitExit::SampleCeiling
} else if skipped_narrow {
PcurveFitExit::SpanFloor
} else if track_projection {
tracking_met = !verify_blocked;
PcurveFitExit::Stalled
} else {
converged_max = Some(round_max);
PcurveFitExit::Converged
};
break;
}
for (index, fraction, edge_point, parameter, gap) in inserts.into_iter().rev() {
parameters.insert(index, fraction);
edge_points.insert(index, edge_point);
raw.insert(index, parameter);
gaps.insert(index, gap);
off_surface = off_surface.max(gap);
}
repair_branch_jumps(surface, &edge_points, &mut raw, tolerance)?;
let rebuilt = build_interpolant_joined(surface, &raw, ¶meters, &joins)?;
pcurve = rebuilt.0;
excursion = rebuilt.1;
distance = rebuilt.2;
if truncated {
exit = PcurveFitExit::SampleCeiling;
break;
}
}
let residual = match converged_max {
Some(measured) => measured,
None => {
station_residual(surface, evaluate_edge, &pcurve, ¶meters, tolerance, &mut off_surface)?
}
};
if station_fit_tracing() {
eprintln!(
"STATION-FIT pass raised={raised} exit={exit:?} samples={} residual={residual:.3e} off_surface={off_surface:.3e}",
parameters.len()
);
if residual > tolerance + off_surface && (exit == PcurveFitExit::Converged || raised) {
let (mut worst, mut at) = (0.0f64, 0usize);
for (index, span) in parameters.windows(2).enumerate() {
let fraction = 0.5 * (span[0] + span[1]);
let uv = pcurve.evaluate(fraction)?;
let deviation = surface.evaluate_extended(uv.x, uv.y)?.sub(evaluate_edge(fraction)?).length();
if deviation > worst {
worst = deviation;
at = index;
}
}
let ([u0, u1], [v0, v1]) = surface_domains(surface)?;
let (closed_u, closed_v) = surface_closedness(surface)?;
eprintln!(
"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 {:?}",
at + 1,
surface.degree_u,
surface.degree_v,
surface.control_points.len(),
surface.control_points[0].len(),
surface.analytic().map(|_| "yes").unwrap_or("no")
);
{
let fraction = 0.5 * (parameters[at] + parameters[at + 1]);
let uv = pcurve.evaluate(fraction)?;
let image = surface.evaluate_extended(uv.x, uv.y)?;
let station = evaluate_edge(fraction)?;
let foot = project_point_to_surface(surface, station)?;
let seeded = project_point_to_surface_seeded(surface, station, raw[at][0], raw[at][1])?;
eprintln!(
" 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})",
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
);
}
let lo = at.saturating_sub(3);
let hi = (at + 4).min(parameters.len() - 1);
for index in lo..=hi {
eprintln!(
" station {index}: fraction {:.6} uv ({:.6}, {:.6}) point ({:.4}, {:.4}, {:.4})",
parameters[index], raw[index][0], raw[index][1], edge_points[index].x, edge_points[index].y, edge_points[index].z
);
}
}
}
if !track_projection && exit == PcurveFitExit::SpanFloor && residual <= tolerance + off_surface {
exit = PcurveFitExit::Converged;
}
if tracking_met && residual <= tolerance {
exit = PcurveFitExit::Converged;
}
if exit != PcurveFitExit::Converged
&& !raised
&& (residual > tolerance + off_surface || tracking_unmet)
&& cap < PCURVE_RAISED_SAMPLES
{
raised = true;
cap = PCURVE_RAISED_SAMPLES;
rounds = RAISED_ROUNDS;
continue;
}
return Ok(PcurveFit {
curve: pcurve,
report: PcurveFitReport {
residual,
floor: tolerance,
samples: parameters.len(),
exit,
off_surface,
raised,
clamped_excursion: excursion,
clamped_distance: distance,
},
});
}
}
pub fn build_pcurve_on_surface_stations(
surface: &NurbsSurface,
stations: &dyn Fn(f64) -> Result<Vec3, String>,
breaks: &[f64],
tolerance: f64,
base_samples: usize,
refinement_rounds: usize,
parameter_cap: usize,
) -> Result<NurbsCurve, String> {
accept_fit(fit_pcurve_on_surface_stations(
surface,
stations,
breaks,
tolerance,
base_samples,
refinement_rounds,
parameter_cap,
)?)
}
fn station_residual(
surface: &NurbsSurface,
stations: &dyn Fn(f64) -> Result<Vec3, String>,
pcurve: &NurbsCurve,
parameters: &[f64],
tolerance: f64,
off_surface: &mut f64,
) -> Result<f64, String> {
let mut worst = 0.0_f64;
let mut read = |fraction: f64| -> Result<(), String> {
let uv = pcurve.evaluate(fraction)?;
let represented = surface.evaluate_extended(uv.x, uv.y)?;
let station = stations(fraction)?;
let deviation = represented.sub(station).length();
worst = worst.max(deviation);
if deviation > tolerance + *off_surface {
*off_surface = off_surface.max(invert_checked(surface, station)?.1);
}
Ok(())
};
for span in parameters.windows(2) {
for local in [0.25, 0.5, 0.75] {
read(span[0] + (span[1] - span[0]) * local)?;
}
}
Ok(worst)
}