1use crate::{KernelRefusal, KernelStage, OrRefuse};
2use crate::fit::{solve_dense, solve_dense_shared};
3use crate::topology::{BrepSolid, CoedgeRecord, EdgeRecord, FaceRecord, LoopRecord, VertexRecord};
4use crate::{
5 interpolate_curve, measure_edge_against_pcurve_image,
6 measure_surface_fit_against_pointwise_offset, offset_construction_band, solid_model_scale,
7 vertex_endpoint_gap, vertex_tolerance_from_edges, KnotVector, MeasuredTolerance, NurbsCurve,
8 NurbsSurface, OffsetEvaluator, OffsetNormal, Vec2, Vec3, Vec4,
9};
10use rustc_hash::FxHashMap as HashMap;
11use serde::Serialize;
12
13fn domains(surface: &NurbsSurface) -> Result<([f64; 2], [f64; 2]), KernelRefusal> {
14 Ok((
15 KnotVector::new(surface.knots_u.clone(), surface.degree_u).or_refuse(KernelStage::Refine, "new")?.domain(),
16 KnotVector::new(surface.knots_v.clone(), surface.degree_v).or_refuse(KernelStage::Refine, "new")?.domain(),
17 ))
18}
19
20fn stable_face_normal(face: &FaceRecord, u: f64, v: f64) -> Result<Vec3, KernelRefusal> {
24 OffsetEvaluator::new(
25 "offset_surface",
26 &face.surface,
27 OffsetNormal::FaceStable {
28 same_sense: face.same_sense,
29 },
30 )
31 .normal(u, v)
32 .or_refuse(KernelStage::Refine, "normal")
33}
34
35fn greville_parameters(knots: &KnotVector) -> Vec<f64> {
36 let mut parameters = (0..knots.control_point_count())
37 .map(|index| {
38 knots.knots[index + 1..=index + knots.degree]
39 .iter()
40 .sum::<f64>()
41 / knots.degree as f64
42 })
43 .collect::<Vec<_>>();
44 let domain = knots.domain();
45 parameters[0] = domain[0];
46 *parameters.last_mut().unwrap() = domain[1];
47 parameters
48}
49
50fn collocation_matrix(knots: &KnotVector, parameters: &[f64], weights: &[f64]) -> Vec<Vec<f64>> {
54 parameters
55 .iter()
56 .map(|parameter| {
57 let mut row = vec![0.0; knots.control_point_count()];
58 let span = knots.find_span(*parameter);
59 for (offset, value) in knots
60 .basis_functions(span, *parameter)
61 .into_iter()
62 .enumerate()
63 {
64 let index = span - knots.degree + offset;
65 row[index] = value * weights[index];
66 }
67 let denominator: f64 = row.iter().sum();
68 if denominator.abs() > 0.0 {
69 for value in &mut row {
70 *value /= denominator;
71 }
72 }
73 row
74 })
75 .collect()
76}
77
78fn separable_weights(weights: &[Vec<f64>]) -> Option<(Vec<f64>, Vec<f64>)> {
82 let first_row = weights.first()?;
83 let anchor = *first_row.first()?;
84 if anchor.abs() <= 1e-12 {
85 return None;
86 }
87 let a: Vec<f64> = weights.iter().map(|row| row[0]).collect();
88 let b: Vec<f64> = first_row.iter().map(|w| w / anchor).collect();
89 for (i, row) in weights.iter().enumerate() {
90 for (j, &w) in row.iter().enumerate() {
91 if (w - a[i] * b[j]).abs() > 1e-10 * (1.0 + w.abs()) {
92 return None;
93 }
94 }
95 }
96 Some((a, b))
97}
98
99fn interpolate_tensor(
105 knot_u: &KnotVector,
106 knot_v: &KnotVector,
107 parameters_u: &[f64],
108 parameters_v: &[f64],
109 samples: &[Vec<Vec3>],
110 weights: &[Vec<f64>],
111) -> Result<Vec<Vec<Vec4>>, KernelRefusal> {
112 let count_u = parameters_u.len();
113 let count_v = parameters_v.len();
114 if let Some((weights_u, weights_v)) = separable_weights(weights) {
115 let matrix_u = collocation_matrix(knot_u, parameters_u, &weights_u);
116 let matrix_v = collocation_matrix(knot_v, parameters_v, &weights_v);
117 let mut intermediate = vec![vec![Vec3::default(); count_v]; count_u];
124 for column in 0..count_v {
125 let side = |axis: fn(Vec3) -> f64| samples.iter().map(|row| axis(row[column])).collect::<Vec<_>>();
126 let [x, y, z] = solve_dense_shared(matrix_u.clone(), [side(|point| point.x), side(|point| point.y), side(|point| point.z)])
127 .or_refuse(KernelStage::Refine, "solve_axis")?;
128 for row in 0..count_u {
129 intermediate[row][column] = Vec3::new(x[row], y[row], z[row]);
130 }
131 }
132 let mut controls = vec![vec![Vec4::from_point(Vec3::default(), 1.0); count_v]; count_u];
133 for row in 0..count_u {
134 let side = |axis: fn(Vec3) -> f64| intermediate[row].iter().copied().map(axis).collect::<Vec<_>>();
135 let [x, y, z] = solve_dense_shared(matrix_v.clone(), [side(|point| point.x), side(|point| point.y), side(|point| point.z)])
136 .or_refuse(KernelStage::Refine, "solve_axis")?;
137 for column in 0..count_v {
138 controls[row][column] = Vec4::from_point(
139 Vec3::new(x[column], y[column], z[column]),
140 weights[row][column],
141 );
142 }
143 }
144 return Ok(controls);
145 }
146
147 let unknowns = count_u * count_v;
150 let mut matrix = vec![vec![0.0; unknowns]; unknowns];
151 for (k, &u) in parameters_u.iter().enumerate() {
152 let span_u = knot_u.find_span(u);
153 let basis_u = knot_u.basis_functions(span_u, u);
154 for (l, &v) in parameters_v.iter().enumerate() {
155 let span_v = knot_v.find_span(v);
156 let basis_v = knot_v.basis_functions(span_v, v);
157 let row = &mut matrix[k * count_v + l];
158 let mut denominator = 0.0;
159 for (du, value_u) in basis_u.iter().enumerate() {
160 let i = span_u - knot_u.degree + du;
161 for (dv, value_v) in basis_v.iter().enumerate() {
162 let j = span_v - knot_v.degree + dv;
163 let entry = value_u * value_v * weights[i][j];
164 row[i * count_v + j] = entry;
165 denominator += entry;
166 }
167 }
168 if denominator.abs() > 0.0 {
169 for value in row.iter_mut() {
170 *value /= denominator;
171 }
172 }
173 }
174 }
175 let solve_axis = |axis: fn(Vec3) -> f64| {
176 solve_dense(
177 matrix.clone(),
178 samples
179 .iter()
180 .flat_map(|row| row.iter().copied().map(axis))
181 .collect(),
182 )
183 };
184 let x = solve_axis(|point| point.x).or_refuse(KernelStage::Refine, "solve_axis")?;
185 let y = solve_axis(|point| point.y).or_refuse(KernelStage::Refine, "solve_axis")?;
186 let z = solve_axis(|point| point.z).or_refuse(KernelStage::Refine, "solve_axis")?;
187 let mut controls = vec![vec![Vec4::from_point(Vec3::default(), 1.0); count_v]; count_u];
188 for row in 0..count_u {
189 for column in 0..count_v {
190 let index = row * count_v + column;
191 controls[row][column] = Vec4::from_point(
192 Vec3::new(x[index], y[index], z[index]),
193 weights[row][column],
194 );
195 }
196 }
197 Ok(controls)
198}
199
200#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
210pub enum OffsetSurfaceLane {
211 Affine,
215 Analytic,
221 #[default]
225 Fit,
226 Reparameterised,
232}
233
234#[derive(Clone, Debug)]
237pub struct MeasuredOffsetSurface {
238 pub surface: NurbsSurface,
239 pub lane: OffsetSurfaceLane,
240 pub fit: Option<MeasuredTolerance>,
248}
249
250#[derive(Clone, Copy, Debug, PartialEq)]
262pub struct CarrierExtension {
263 pub u_min: f64,
264 pub u_max: f64,
265 pub v_min: f64,
266 pub v_max: f64,
267}
268
269impl CarrierExtension {
270 pub const NONE: CarrierExtension = CarrierExtension {
271 u_min: 0.0,
272 u_max: 0.0,
273 v_min: 0.0,
274 v_max: 0.0,
275 };
276
277 pub fn uniform(amount: f64) -> CarrierExtension {
278 CarrierExtension {
279 u_min: amount,
280 u_max: amount,
281 v_min: amount,
282 v_max: amount,
283 }
284 }
285
286 pub fn is_active(&self) -> bool {
287 self.u_min > 0.0 || self.u_max > 0.0 || self.v_min > 0.0 || self.v_max > 0.0
288 }
289
290 fn extends_v(&self) -> bool {
291 self.v_min > 0.0 || self.v_max > 0.0
292 }
293}
294
295const EXACT_TRIM_BOX_DEFAULT: bool = true;
304
305fn exact_trim_box_on() -> bool {
306 switch!(live "BREP_OFFSET_EXACT_TRIM_BOX", EXACT_TRIM_BOX_DEFAULT)
307}
308
309
310const TRIM_EXTREME_STEPS: usize = 64;
314
315fn refine_trim_extreme(
324 pcurve: &NurbsCurve,
325 samples: &[(f64, Vec3)],
326 axis: usize,
327 sign: f64,
328) -> Result<f64, KernelRefusal> {
329 let read = |uv: Vec3| sign * if axis == 0 { uv.x } else { uv.y };
330 let at = |parameter: f64| -> Result<f64, KernelRefusal> {
331 Ok(read(pcurve.evaluate(parameter).or_refuse(KernelStage::Refine, "evaluate")?))
332 };
333 let best = (0..samples.len())
334 .max_by(|&a, &b| read(samples[a].1).total_cmp(&read(samples[b].1)))
335 .expect("a pcurve has samples");
336 let mut found = read(samples[best].1);
337 let (mut a, mut b) = (samples[best.saturating_sub(1)].0, samples[(best + 1).min(samples.len() - 1)].0);
338 const GOLDEN: f64 = 0.618_033_988_749_894_9;
339 let mut c = b - GOLDEN * (b - a);
340 let mut d = a + GOLDEN * (b - a);
341 let (mut fc, mut fd) = (at(c)?, at(d)?);
342 for _ in 0..TRIM_EXTREME_STEPS {
343 found = found.max(fc).max(fd);
344 if fc >= fd {
345 (b, d, fd) = (d, c, fc);
346 c = b - GOLDEN * (b - a);
347 fc = at(c)?;
348 } else {
349 (a, c, fc) = (c, d, fd);
350 d = a + GOLDEN * (b - a);
351 fd = at(d)?;
352 }
353 }
354 Ok(sign * found.max(fc).max(fd))
355}
356
357fn trim_domain_fractions(
362 face: &FaceRecord,
363 [u0, u1]: [f64; 2],
364 [v0, v1]: [f64; 2],
365) -> Result<([f64; 2], [f64; 2]), KernelRefusal> {
366 let mut low = Vec2 {
367 x: f64::INFINITY,
368 y: f64::INFINITY,
369 };
370 let mut high = Vec2 {
371 x: f64::NEG_INFINITY,
372 y: f64::NEG_INFINITY,
373 };
374 for coedge in face
375 .loops
376 .iter()
377 .flat_map(|loop_record| &loop_record.coedges)
378 {
379 let [p0, p1] = coedge.pcurve.domain().or_refuse(KernelStage::Refine, "domain")?;
380 let mut samples = Vec::with_capacity(25);
381 for sample in 0..=24 {
382 let parameter = p0 + (p1 - p0) * sample as f64 / 24.0;
383 let uv = coedge
384 .pcurve
385 .evaluate(parameter).or_refuse(KernelStage::Refine, "evaluate")?;
386 low.x = low.x.min(uv.x);
387 low.y = low.y.min(uv.y);
388 high.x = high.x.max(uv.x);
389 high.y = high.y.max(uv.y);
390 samples.push((parameter, uv));
391 }
392 if coedge.pcurve.degree > 1 && exact_trim_box_on() {
393 low.x = low.x.min(refine_trim_extreme(&coedge.pcurve, &samples, 0, -1.0)?);
394 high.x = high.x.max(refine_trim_extreme(&coedge.pcurve, &samples, 0, 1.0)?);
395 low.y = low.y.min(refine_trim_extreme(&coedge.pcurve, &samples, 1, -1.0)?);
396 high.y = high.y.max(refine_trim_extreme(&coedge.pcurve, &samples, 1, 1.0)?);
397 }
398 }
399 let fraction = |value: f64, start: f64, end: f64| {
400 let span = end - start;
401 if span.abs() <= f64::EPSILON || !value.is_finite() {
402 return None;
403 }
404 Some(((value - start) / span).clamp(0.0, 1.0))
405 };
406 let u = match (fraction(low.x, u0, u1), fraction(high.x, u0, u1)) {
407 (Some(a), Some(b)) if b - a > 1e-6 => [a, b],
408 _ => [0.0, 1.0],
409 };
410 let v = match (fraction(low.y, v0, v1), fraction(high.y, v0, v1)) {
411 (Some(a), Some(b)) if b - a > 1e-6 => [a, b],
412 _ => [0.0, 1.0],
413 };
414 Ok((u, v))
415}
416
417fn domain_end_moves(grow_min: f64, grow_max: f64, [ta, tb]: [f64; 2]) -> (f64, f64) {
427 let span = tb - ta;
428 if span <= 1e-6 {
429 return (grow_min, grow_max);
430 }
431 let rate = (grow_min + grow_max) / span;
432 let back = grow_min + ta * rate;
433 let forward = (1.0 - ta) * rate - grow_min;
434 (back.max(0.0), forward.max(0.0))
435}
436
437pub fn offset_surface(
441 face: &FaceRecord,
442 distance: f64,
443 planar_extension: f64,
444) -> Result<NurbsSurface, KernelRefusal> {
445 offset_surface_with_lane(face, distance, &CarrierExtension::uniform(planar_extension))
446 .map(|(surface, _)| surface)
447}
448
449thread_local! {
450 static IMPORT_OFFSET_PRECISION: std::cell::Cell<bool> = const { std::cell::Cell::new(false) };
451}
452
453pub(crate) fn offset_surface_for_import(face: &FaceRecord, distance: f64) -> Result<NurbsSurface, KernelRefusal> {
459 if face.surface.analytic().is_some() || face.surface.is_affine().or_refuse(KernelStage::Refine, "is_affine")? {
460 return offset_surface(face, distance, 0.0);
461 }
462 let source = &face.surface;
463 let mut rows = Vec::new();
464 let mut knots_v = source.knots_v.clone();
465 for row in &source.control_points {
466 let curve = NurbsCurve::new(source.degree_v, source.knots_v.clone(), row.clone()).or_refuse(KernelStage::Refine, "new")?;
467 let raised = crate::coons::compat::elevate_degree(&curve, source.degree_v.max(5)).or_refuse(KernelStage::Refine, "elevate_degree")?;
468 knots_v = raised.knots.clone();
469 rows.push(raised.control_points);
470 }
471 let mut columns = Vec::new();
472 let mut knots_u = source.knots_u.clone();
473 for column in 0..rows[0].len() {
474 let curve = NurbsCurve::new(source.degree_u, source.knots_u.clone(), rows.iter().map(|row| row[column]).collect()).or_refuse(KernelStage::Refine, "new")?;
475 let raised = crate::coons::compat::elevate_degree(&curve, source.degree_u.max(5)).or_refuse(KernelStage::Refine, "elevate_degree")?;
476 knots_u = raised.knots.clone();
477 columns.push(raised.control_points);
478 }
479 let controls = (0..columns[0].len()).map(|row| columns.iter().map(|column| column[row]).collect()).collect();
480 let mut elevated = face.clone();
481 elevated.surface = NurbsSurface::new(source.degree_u.max(5), source.degree_v.max(5), knots_u, knots_v, controls).or_refuse(KernelStage::Refine, "new")?;
482 let interior = |knots: &[f64], degree: usize| {
486 let low = knots[degree];
487 let high = knots[knots.len() - degree - 1];
488 let mut values: Vec<f64> = knots.iter().copied().filter(|k| *k > low && *k < high).collect();
489 values.dedup();
490 values
491 };
492 elevated.surface = insert_offset_fit_knots(&elevated.surface,
493 &interior(&source.knots_u, source.degree_u),
494 &interior(&source.knots_v, source.degree_v))?;
495 struct Restore(bool);
496 impl Drop for Restore {
497 fn drop(&mut self) { IMPORT_OFFSET_PRECISION.with(|state| state.set(self.0)); }
498 }
499 let _restore = Restore(IMPORT_OFFSET_PRECISION.with(|state| state.replace(true)));
500 offset_surface(&elevated, distance, 0.0)
501}
502
503pub fn offset_surface_measured(
512 face: &FaceRecord,
513 distance: f64,
514 planar_extension: f64,
515 band: f64,
516) -> Result<MeasuredOffsetSurface, KernelRefusal> {
517 offset_surface_measured_sided(
518 face,
519 distance,
520 &CarrierExtension::uniform(planar_extension),
521 band,
522 )
523}
524
525pub fn offset_surface_measured_sided(
527 face: &FaceRecord,
528 distance: f64,
529 extension: &CarrierExtension,
530 band: f64,
531) -> Result<MeasuredOffsetSurface, KernelRefusal> {
532 offset_surface_measured_sided_mode(face, distance, extension, band,
533 std::env::var("BREP_OFFSET_SPHERE_READING").map_or(true, |v| v != "0" && v != "off"))
534}
535
536fn offset_surface_measured_sided_mode(
537 face: &FaceRecord, distance: f64, extension: &CarrierExtension, band: f64, reuse: bool,
538) -> Result<MeasuredOffsetSurface, KernelRefusal> {
539 let mut sphere_reading = None;
540 let (surface, lane, extended) = offset_surface_constructed(face, distance, extension, &mut sphere_reading)?;
541 let fit = match lane {
542 OffsetSurfaceLane::Affine => Some(MeasuredTolerance::exact(band)),
543 OffsetSurfaceLane::Analytic if reuse && sphere_reading.is_some() => {
548 if crate::profile::profile_enabled() {
552 profile_line!("offset.sphere_reading.profile reused=1");
553 }
554 Some(MeasuredTolerance::new(sphere_reading.unwrap(), band))
555 }
556 OffsetSurfaceLane::Analytic | OffsetSurfaceLane::Fit => {
557 Some(measure_surface_fit_against_pointwise_offset(
558 extended.as_ref().unwrap_or(&face.surface),
559 face.same_sense,
560 &surface,
561 distance,
562 band,
563 )?)
564 }
565 OffsetSurfaceLane::Reparameterised => None,
566 };
567 Ok(MeasuredOffsetSurface { surface, lane, fit })
568}
569
570fn sphere_offset_surface(face: &FaceRecord, distance: f64, reading: &mut Option<f64>) -> Result<Option<NurbsSurface>, KernelRefusal> {
599 if std::env::var_os("BREP_NO_ANALYTIC_OFFSET").is_some() {
603 return Ok(None);
604 }
605 let source = &face.surface;
606 let Some((centre, radius)) = source.analytic().and_then(|shape| shape.sphere_geometry()) else {
607 return Ok(None);
608 };
609 let ([u0, u1], [v0, v1]) = domains(source)?;
610 let Ok(sample) = OffsetEvaluator::new(
617 "offset_surface",
618 source,
619 OffsetNormal::FaceStable {
620 same_sense: face.same_sense,
621 },
622 )
623 .at((u0 + u1) / 2.0, (v0 + v1) / 2.0, -distance)
624 else {
625 return Ok(None);
626 };
627 let source_radial = sample.source.sub(centre);
628 let offset_radial = sample.point.sub(centre);
629 let offset_radius = offset_radial.length();
630 let scale = radius.max(1.0);
631 if radius <= 1e-12
632 || offset_radius <= 1e-9 * scale
633 || offset_radial.dot(source_radial) <= 0.0
636 || ((offset_radius - radius).abs() - distance.abs()).abs() > 1e-9 * scale
639 {
640 return Ok(None);
641 }
642 let factor = offset_radius / radius;
643 let Ok(controls) = source
646 .control_points
647 .iter()
648 .map(|row| {
649 row.iter()
650 .map(|control| {
651 Ok(Vec4::from_point(
652 centre.add(control.point().or_refuse(KernelStage::Refine, "point")?.sub(centre).scale(factor)),
653 control.w,
654 ))
655 })
656 .collect::<Result<Vec<_>, KernelRefusal>>()
657 })
658 .collect::<Result<Vec<Vec<_>>, KernelRefusal>>()
659 else {
660 return Ok(None);
661 };
662 let Ok(surface) = NurbsSurface::new(
663 source.degree_u,
664 source.degree_v,
665 source.knots_u.clone(),
666 source.knots_v.clone(),
667 controls,
668 ) else {
669 return Ok(None);
670 };
671 match crate::offset_measure::sphere_fit_reading(
675 source,
676 face.same_sense,
677 &surface,
678 distance,
679 1e-9 * scale,
680 ) {
681 Ok(measured) if measured.within_band() => {
682 *reading = Some(measured.deviation());
683 Ok(Some(surface))
684 },
685 _ => Ok(None),
686 }
687}
688
689fn revolved_arc_offset_surface(
722 face: &FaceRecord,
723 distance: f64,
724) -> Result<Option<NurbsSurface>, KernelRefusal> {
725 if std::env::var_os("BREP_NO_ANALYTIC_OFFSET").is_some() {
726 return Ok(None);
727 }
728 let source = &face.surface;
729 match source.analytic() {
730 Some(crate::AnalyticSurface::Revolution { .. } | crate::AnalyticSurface::Torus { .. }) => {}
731 _ => return Ok(None),
732 }
733 let rows = &source.control_points;
734 let Some(first_row) = rows.first() else {
735 return Ok(None);
736 };
737 if rows.iter().flatten().any(|control| !(control.w > 0.0)) {
738 return Ok(None);
739 }
740 let Ok(generatrix) = NurbsCurve::new(source.degree_v, source.knots_v.clone(), first_row.clone())
741 else {
742 return Ok(None);
743 };
744 let [t0, t1] = generatrix.domain().or_refuse(KernelStage::Refine, "domain")?;
745 let at = |fraction: f64| generatrix.evaluate(t0 + (t1 - t0) * fraction);
746 let (a, b, e) = (at(0.0).or_refuse(KernelStage::Refine, "at")?, at(1.0 / 3.0).or_refuse(KernelStage::Refine, "at")?, at(2.0 / 3.0).or_refuse(KernelStage::Refine, "at")?);
748 let (ab, ae) = (b.sub(a), e.sub(a));
749 let normal = ab.cross(ae);
750 let normal_length_squared = normal.dot(normal);
751 let Some(centre) = crate::circumcenter(a, b, e) else { return Ok(None); };
752 let radius = a.sub(centre).length();
753 let scale = (centre.length() + radius).max(1.0);
754 let band = 1e-9 * scale;
755 let unit_normal = normal.scale(1.0 / normal_length_squared.sqrt());
756 let samples = 16 * generatrix.control_points.len();
757 for index in 0..=samples {
758 let point = at(index as f64 / samples as f64).or_refuse(KernelStage::Refine, "at")?;
759 let radial = point.sub(centre);
760 if (radial.length() - radius).abs() > band || radial.dot(unit_normal).abs() > band {
761 return Ok(None);
762 }
763 }
764 let controls = first_row
767 .iter()
768 .map(|control| control.point().or_refuse(KernelStage::Refine, "point"))
769 .collect::<Result<Vec<_>, KernelRefusal>>()?;
770 let origin = controls[0];
771 let mut best = (0usize, 0usize, 0.0f64);
772 for first in 1..controls.len() {
773 for second in first + 1..controls.len() {
774 let area = controls[first]
775 .sub(origin)
776 .cross(controls[second].sub(origin))
777 .length();
778 if area > best.2 {
779 best = (first, second, area);
780 }
781 }
782 }
783 let (first, second, area) = best;
784 if area <= 1e-9 * scale * scale {
785 return Ok(None);
786 }
787 let (along_first, along_second) = (controls[first].sub(origin), controls[second].sub(origin));
788 let offset_from_origin = centre.sub(origin);
789 let (g11, g12, g22) = (
790 along_first.dot(along_first),
791 along_first.dot(along_second),
792 along_second.dot(along_second),
793 );
794 let determinant = g11 * g22 - g12 * g12;
795 let (r1, r2) = (along_first.dot(offset_from_origin), along_second.dot(offset_from_origin));
796 let s = (r1 * g22 - r2 * g12) / determinant;
797 let t = (r2 * g11 - r1 * g12) / determinant;
798 if origin
799 .add(along_first.scale(s))
800 .add(along_second.scale(t))
801 .sub(centre)
802 .length()
803 > band
804 {
805 return Ok(None);
806 }
807 let ([u0, _], [v0, v1]) = domains(source)?;
810 let Ok(sample) = OffsetEvaluator::new(
811 "offset_surface",
812 source,
813 OffsetNormal::FaceStable {
814 same_sense: face.same_sense,
815 },
816 )
817 .at(u0, (v0 + v1) / 2.0, -distance)
818 else {
819 return Ok(None);
820 };
821 let source_radial = sample.source.sub(centre);
822 let offset_radial = sample.point.sub(centre);
823 let offset_radius = offset_radial.length();
824 if (source_radial.length() - radius).abs() > band
825 || offset_radius <= band
826 || offset_radial.dot(source_radial) <= 0.0
827 || ((offset_radius - radius).abs() - distance.abs()).abs() > band
828 {
829 return Ok(None);
830 }
831 let factor = offset_radius / radius;
832 let Ok(offset_rows) = rows
833 .iter()
834 .map(|row| {
835 let points = row.iter().map(|control| control.point().or_refuse(KernelStage::Refine, "point")).collect::<Result<Vec<_>, KernelRefusal>>()?;
836 let row_origin = points[0];
837 let row_centre = row_origin
838 .add(points[first].sub(row_origin).scale(s))
839 .add(points[second].sub(row_origin).scale(t));
840 Ok(points
841 .iter()
842 .zip(row)
843 .map(|(point, control)| {
844 Vec4::from_point(row_centre.add(point.sub(row_centre).scale(factor)), control.w)
845 })
846 .collect::<Vec<_>>())
847 })
848 .collect::<Result<Vec<Vec<_>>, KernelRefusal>>()
849 else {
850 return Ok(None);
851 };
852 let Ok(surface) = NurbsSurface::new(
853 source.degree_u,
854 source.degree_v,
855 source.knots_u.clone(),
856 source.knots_v.clone(),
857 offset_rows,
858 ) else {
859 return Ok(None);
860 };
861 match measure_surface_fit_against_pointwise_offset(
862 source,
863 face.same_sense,
864 &surface,
865 distance,
866 band,
867 ) {
868 Ok(measured) if measured.within_band() => Ok(Some(surface)),
869 _ => Ok(None),
870 }
871}
872
873pub(crate) fn exact_cylinder_offsets_on() -> bool {
878 switch!("BREP_OFFSET_EXACT_CYLINDER", true)
879}
880
881
882pub(crate) fn cylinder_offset_factor(
889 surface: &NurbsSurface,
890 same_sense: bool,
891 distance: f64,
892) -> Result<Option<(Vec3, Vec3, f64, f64)>, KernelRefusal> {
893 if std::env::var_os("BREP_NO_ANALYTIC_OFFSET").is_some() {
894 return Ok(None);
895 }
896 let Some(crate::AnalyticSurface::RuledRevolution { frame, rho0, rho1, height }) = surface.analytic() else {
897 return Ok(None);
898 };
899 let radius = 0.5 * (rho0 + rho1);
900 if !(radius > 0.0) || (rho0 - rho1).abs() > 1e-9 * radius.max(1.0) {
901 return Ok(None);
902 }
903 let Ok(axis) = frame.axis.normalized() else {
904 return Ok(None);
905 };
906 let origin = frame.origin;
907 let band = 1e-9 * (origin.length() + radius + height.abs()).max(1.0);
908 let perpendicular = |point: Vec3| {
909 let along = point.sub(origin);
910 along.sub(axis.scale(along.dot(axis)))
911 };
912 let [u0, u1] = surface.domain_u().or_refuse(KernelStage::Refine, "domain_u")?;
913 let [v0, v1] = surface.domain_v().or_refuse(KernelStage::Refine, "domain_v")?;
914 let Ok(sample) = OffsetEvaluator::new("offset_surface", surface, OffsetNormal::FaceStable { same_sense })
915 .at((u0 + u1) * 0.5, (v0 + v1) * 0.5, -distance)
916 else {
917 return Ok(None);
918 };
919 let (source_radial, offset_radial) = (perpendicular(sample.source), perpendicular(sample.point));
920 let offset_radius = offset_radial.length();
921 if (source_radial.length() - radius).abs() > band
922 || offset_radius <= band
923 || offset_radial.dot(source_radial) <= 0.0
924 || ((offset_radius - radius).abs() - distance.abs()).abs() > band
925 || sample.point.sub(sample.source).dot(axis).abs() > band
926 {
927 return Ok(None);
928 }
929 Ok(Some((origin, axis, radius, offset_radius / radius)))
930}
931
932fn cylinder_offset_surface(
945 reference: &NurbsSurface,
946 same_sense: bool,
947 distance: f64,
948) -> Result<Option<NurbsSurface>, KernelRefusal> {
949 let Some((origin, axis, radius, factor)) = cylinder_offset_factor(reference, same_sense, distance)? else {
950 return Ok(None);
951 };
952 if reference.control_points.iter().flatten().any(|control| !(control.w > 0.0)) {
953 return Ok(None);
954 }
955 let Ok(rows) = reference
956 .control_points
957 .iter()
958 .map(|row| {
959 row.iter()
960 .map(|control| {
961 let point = control.point()?;
962 let foot = origin.add(axis.scale(point.sub(origin).dot(axis)));
963 Ok(Vec4::from_point(foot.add(point.sub(foot).scale(factor)), control.w))
964 })
965 .collect::<Result<Vec<_>, String>>()
966 })
967 .collect::<Result<Vec<Vec<_>>, String>>()
968 else {
969 return Ok(None);
970 };
971 let Ok(surface) = NurbsSurface::new(
972 reference.degree_u,
973 reference.degree_v,
974 reference.knots_u.clone(),
975 reference.knots_v.clone(),
976 rows,
977 ) else {
978 return Ok(None);
979 };
980 let band = 1e-9 * (origin.length() + radius * factor.max(1.0)).max(1.0);
986 let evaluator = OffsetEvaluator::new("offset_surface", reference, OffsetNormal::FaceStable { same_sense });
987 let [u0, u1] = reference.domain_u().or_refuse(KernelStage::Refine, "domain_u")?;
988 let [v0, v1] = reference.domain_v().or_refuse(KernelStage::Refine, "domain_v")?;
989 for i in 0..=4 {
990 for j in 0..=2 {
991 let (u, v) = (u0 + (u1 - u0) * i as f64 / 4.0, v0 + (v1 - v0) * j as f64 / 2.0);
992 let (Ok(want), Ok(got)) = (evaluator.at(u, v, -distance), surface.evaluate(u, v)) else {
993 return Ok(None);
994 };
995 if !(want.point.sub(got).length() <= band) {
996 return Ok(None);
997 }
998 }
999 }
1000 Ok(Some(surface))
1001}
1002
1003pub(crate) fn offset_surface_with_lane(
1004 face: &FaceRecord,
1005 distance: f64,
1006 extension: &CarrierExtension,
1007) -> Result<(NurbsSurface, OffsetSurfaceLane), KernelRefusal> {
1008 offset_surface_constructed(face, distance, extension, &mut None).map(|(surface, lane, _)| (surface, lane))
1009}
1010
1011pub(crate) fn transpose_offset_surface(surface: &NurbsSurface) -> Result<NurbsSurface, KernelRefusal> {
1015 let controls = (0..surface.control_points[0].len())
1016 .map(|column| surface.control_points.iter().map(|row| row[column]).collect())
1017 .collect();
1018 NurbsSurface::new(surface.degree_v, surface.degree_u, surface.knots_v.clone(),
1019 surface.knots_u.clone(), controls).or_refuse(KernelStage::Refine, "offset_transpose")
1020}
1021
1022pub(crate) fn apex_end_reach_enabled() -> bool {
1025 switch!("BREP_OFFSET_APEX_END_REACH", true)
1026}
1027
1028
1029fn offset_surface_constructed(
1030 face: &FaceRecord,
1031 distance: f64,
1032 extension: &CarrierExtension,
1033 sphere_reading: &mut Option<f64>,
1034) -> Result<(NurbsSurface, OffsetSurfaceLane, Option<NurbsSurface>), KernelRefusal> {
1035 let source = &face.surface;
1036 let extension_active = extension.is_active();
1037 let normalize_ruling = std::env::var("BREP_OFFSET_FIT_RESIDUAL").as_deref() != Ok("0")
1043 && source.degree_u == 1 && source.control_points.len() == 2;
1044 let normalize_sphere = std::env::var("BREP_OFFSET_FOLD_CHART").as_deref() != Ok("0")
1045 && source.degree_u == 2 && source.degree_v == 2 && source.analytic().is_none();
1046 if normalize_ruling || normalize_sphere {
1047 let transposed = transpose_offset_surface(source)?;
1048 let ruled = normalize_ruling && matches!(transposed.analytic(), Some(crate::AnalyticSurface::RuledRevolution { .. }));
1049 let spherical = normalize_sphere && transposed.analytic().and_then(|shape| shape.sphere_geometry()).is_some();
1050 if ruled || spherical {
1051 let mut turned = face.clone();
1052 turned.surface = transposed;
1053 turned.same_sense = !turned.same_sense;
1054 for coedge in turned.loops.iter_mut().flat_map(|lp| &mut lp.coedges) {
1055 let controls = coedge.pcurve.control_points.iter().map(|point| {
1056 let mut swapped = *point;
1057 std::mem::swap(&mut swapped.x, &mut swapped.y);
1058 swapped
1059 }).collect();
1060 coedge.pcurve = NurbsCurve::new(coedge.pcurve.degree,
1061 coedge.pcurve.knots.clone(), controls).or_refuse(KernelStage::Refine, "offset_transpose_pcurve")?;
1062 }
1063 let turned_extension = CarrierExtension {
1064 u_min: extension.v_min, u_max: extension.v_max,
1065 v_min: extension.u_min, v_max: extension.u_max,
1066 };
1067 let (surface, lane, extended) = offset_surface_constructed(&turned, distance, &turned_extension, &mut None)?;
1068 return Ok((transpose_offset_surface(&surface)?, lane,
1069 extended.as_ref().map(transpose_offset_surface).transpose()?));
1070 }
1071 }
1072 if source.is_affine().or_refuse(KernelStage::Refine, "is_affine")? {
1073 let ([u0, u1], [v0, v1]) = domains(source)?;
1074 let normal = stable_face_normal(face, (u0 + u1) / 2.0, (v0 + v1) / 2.0)?;
1075 let shift = normal.scale(-distance);
1076 let mut points = source
1077 .control_points
1078 .iter()
1079 .map(|row| {
1080 row.iter()
1081 .map(|control| Ok(control.point().or_refuse(KernelStage::Refine, "point")?.add(shift)))
1082 .collect::<Result<Vec<_>, KernelRefusal>>()
1083 })
1084 .collect::<Result<Vec<_>, KernelRefusal>>()?;
1085 if extension_active {
1086 let p00 = points[0][0];
1087 let p01 = points[0][1];
1088 let p10 = points[1][0];
1089 let direction_u = p10.sub(p00).normalized().or_refuse(KernelStage::Refine, "normalized")?;
1090 let direction_v = p01.sub(p00).normalized().or_refuse(KernelStage::Refine, "normalized")?;
1091 let (trim_u, trim_v) = trim_domain_fractions(face, [u0, u1], [v0, v1])?;
1097 let (back_u, forward_u) = domain_end_moves(extension.u_min, extension.u_max, trim_u);
1098 let (back_v, forward_v) = domain_end_moves(extension.v_min, extension.v_max, trim_v);
1099 points[0][0] = p00
1100 .sub(direction_u.scale(back_u))
1101 .sub(direction_v.scale(back_v));
1102 points[0][1] = p01
1103 .sub(direction_u.scale(back_u))
1104 .add(direction_v.scale(forward_v));
1105 points[1][0] = p10
1106 .add(direction_u.scale(forward_u))
1107 .sub(direction_v.scale(back_v));
1108 points[1][1] = points[1][1]
1109 .add(direction_u.scale(forward_u))
1110 .add(direction_v.scale(forward_v));
1111 }
1112 let controls = points
1113 .into_iter()
1114 .enumerate()
1115 .map(|(row, points)| {
1116 points
1117 .into_iter()
1118 .enumerate()
1119 .map(|(column, point)| {
1120 Vec4::from_point(point, source.control_points[row][column].w)
1121 })
1122 .collect()
1123 })
1124 .collect();
1125 let lane = if extension_active {
1129 OffsetSurfaceLane::Reparameterised
1130 } else {
1131 OffsetSurfaceLane::Affine
1132 };
1133 return Ok((
1134 NurbsSurface::new(
1135 source.degree_u,
1136 source.degree_v,
1137 source.knots_u.clone(),
1138 source.knots_v.clone(),
1139 controls,
1140 ).or_refuse(KernelStage::Refine, "new")?,
1141 lane,
1142 None,
1143 ));
1144 }
1145
1146 if let Some(surface) = sphere_offset_surface(face, distance, sphere_reading)? {
1156 return Ok((surface, OffsetSurfaceLane::Analytic, None));
1157 }
1158 if let Some(surface) = revolved_arc_offset_surface(face, distance)? {
1161 return Ok((surface, OffsetSurfaceLane::Analytic, None));
1162 }
1163
1164 let knot_u = KnotVector::new(source.knots_u.clone(), source.degree_u).or_refuse(KernelStage::Refine, "new")?;
1165 let knot_v = KnotVector::new(source.knots_v.clone(), source.degree_v).or_refuse(KernelStage::Refine, "new")?;
1166 let parameters_u = greville_parameters(&knot_u);
1167 let parameters_v = greville_parameters(&knot_v);
1168 let evaluator = OffsetEvaluator::new(
1174 "offset_surface",
1175 source,
1176 OffsetNormal::FaceStable {
1177 same_sense: face.same_sense,
1178 },
1179 );
1180 let mut samples = Vec::new();
1181 for &u in ¶meters_u {
1182 let mut row = Vec::new();
1183 for &v in ¶meters_v {
1184 row.push(evaluator.at(u, v, -distance).or_refuse(KernelStage::Refine, "at")?.point);
1185 }
1186 samples.push(row);
1187 }
1188 let mut reparameterised = false;
1203 let mut extended_source: Option<NurbsSurface> = None;
1204 if parameters_v.len() == 2 && parameters_u.len() >= 2 {
1211 let centroid = |column: usize| {
1212 let mut sum = Vec3::default();
1213 for row in &samples {
1214 sum = sum.add(row[column]);
1215 }
1216 sum.scale(1.0 / samples.len() as f64)
1217 };
1218 let near_centroid = centroid(0);
1219 let far_centroid = centroid(1);
1220 let mut inverted = true;
1221 let mut pinch_fraction = 0.0f64;
1222 let mut near_mean = 0.0f64;
1223 let mut far_mean = 0.0f64;
1224 for row in &samples {
1225 let near_radial = row[0].sub(near_centroid);
1226 let far_radial = row[1].sub(far_centroid);
1227 let near_len = near_radial.length();
1228 let far_len = far_radial.length();
1229 if near_len <= 1e-9 || far_len <= 1e-9 {
1230 inverted = false;
1231 break;
1232 }
1233 if near_radial.dot(far_radial) >= 0.0 {
1234 inverted = false;
1235 break;
1236 }
1237 pinch_fraction += near_len / (near_len + far_len) / samples.len() as f64;
1238 near_mean += near_len / samples.len() as f64;
1239 far_mean += far_len / samples.len() as f64;
1240 }
1241 if inverted {
1242 let retrim_far = match pinch_side_by_source(source, ¶meters_u, ¶meters_v, &samples, near_centroid, far_centroid)? {
1243 Some(far) => far,
1244 None => far_mean <= near_mean,
1245 };
1246 let (_, trim_v) = trim_domain_fractions(face, knot_u.domain(), knot_v.domain())?;
1270 let trim_reaches_the_pinch = if retrim_far {
1271 trim_v[1] > pinch_fraction + 1e-9
1272 } else {
1273 trim_v[0] < pinch_fraction - 1e-9
1274 };
1275 if trim_reaches_the_pinch {
1276 reparameterised = true;
1279 for row in &mut samples {
1280 let near = row[0];
1281 let far = row[1];
1282 let pinch = near.add(far.sub(near).scale(pinch_fraction));
1283 if retrim_far {
1284 row[1] = pinch;
1285 } else {
1286 row[0] = pinch;
1287 }
1288 }
1289 }
1290 }
1291 if extension.extends_v() && !inverted {
1311 let apex_end_reach = apex_end_reach_enabled();
1320 let mut min_ruling = f64::MAX;
1321 let mut back_allowance = f64::MAX;
1322 let mut forward_allowance = f64::MAX;
1323 let mut extendable = true;
1324 for row in &samples {
1325 let ruling = row[1].sub(row[0]);
1326 let length = ruling.length();
1327 min_ruling = min_ruling.min(length);
1328 let near_radial = row[0].sub(near_centroid).length();
1332 let far_radial = row[1].sub(far_centroid).length();
1333 if (far_radial - near_radial).abs() > 1e-9 {
1334 let apex_at = near_radial / (near_radial - far_radial);
1335 if apex_end_reach && apex_at.abs() <= 1e-9 {
1336 back_allowance = 0.0;
1337 continue;
1338 }
1339 if apex_end_reach && (apex_at - 1.0).abs() <= 1e-9 {
1340 forward_allowance = 0.0;
1341 continue;
1342 }
1343 if (-1e-9..=1.0 + 1e-9).contains(&apex_at) {
1344 extendable = false;
1346 break;
1347 }
1348 if apex_at < 0.0 {
1349 back_allowance = back_allowance.min(0.9 * -apex_at);
1350 } else {
1351 forward_allowance = forward_allowance.min(0.9 * (apex_at - 1.0));
1352 }
1353 }
1354 }
1355 let mut source_back = f64::MAX;
1363 let mut source_forward = f64::MAX;
1364 if extendable {
1365 let source_centroid = |column: usize| {
1366 let mut sum = Vec3::default();
1367 for row in &source.control_points {
1368 if let Ok(point) = row[column].point() {
1369 sum = sum.add(point);
1370 }
1371 }
1372 sum.scale(1.0 / source.control_points.len() as f64)
1373 };
1374 let (near_source, far_source) = (source_centroid(0), source_centroid(1));
1375 for row in &source.control_points {
1376 let (near, far) = (row[0].point().or_refuse(KernelStage::Refine, "point")?, row[1].point().or_refuse(KernelStage::Refine, "point")?);
1377 let near_radial = near.sub(near_source).length();
1378 let far_radial = far.sub(far_source).length();
1379 if (far_radial - near_radial).abs() > 1e-9 {
1380 let apex_at = near_radial / (near_radial - far_radial);
1381 if apex_end_reach && apex_at.abs() <= 1e-9 {
1382 source_back = 0.0;
1383 continue;
1384 }
1385 if apex_end_reach && (apex_at - 1.0).abs() <= 1e-9 {
1386 source_forward = 0.0;
1387 continue;
1388 }
1389 if (-1e-9..=1.0 + 1e-9).contains(&apex_at) {
1390 extendable = false;
1391 break;
1392 }
1393 if apex_at < 0.0 {
1394 source_back = source_back.min(0.9 * -apex_at);
1395 } else {
1396 source_forward = source_forward.min(0.9 * (apex_at - 1.0));
1397 }
1398 }
1399 }
1400 }
1401 let (back_allowance, forward_allowance) =
1402 (back_allowance.min(source_back), forward_allowance.min(source_forward));
1403 if extendable && min_ruling > 1e-9 {
1404 let (_, trim_v) = trim_domain_fractions(face, knot_u.domain(), knot_v.domain())?;
1411 let (back_world, forward_world) =
1412 domain_end_moves(extension.v_min, extension.v_max, trim_v);
1413 let (requested_back, requested_forward) = (back_world / min_ruling, forward_world / min_ruling);
1414 let apex_end = analytic_offset_apex(source, &samples, offset_fit_contract(source)).and_then(
1426 |(at, apex)| {
1427 if at > 1.0 && at - 1.0 <= requested_forward && at - 1.0 <= source_forward {
1428 Some((false, at - 1.0, apex))
1429 } else if at < 0.0 && -at <= requested_back && -at <= source_back {
1430 Some((true, -at, apex))
1431 } else {
1432 None
1433 }
1434 },
1435 );
1436 let back = match apex_end {
1437 Some((true, reach, _)) => reach,
1438 _ => requested_back.min(back_allowance),
1439 };
1440 let forward = match apex_end {
1441 Some((false, reach, _)) => reach,
1442 _ => requested_forward.min(forward_allowance),
1443 };
1444 let stretched = samples
1445 .iter()
1446 .map(|row| {
1447 let ruling = row[1].sub(row[0]);
1448 let (near, far) = (row[0].sub(ruling.scale(back)), row[1].add(ruling.scale(forward)));
1449 match apex_end {
1450 Some((true, _, apex)) => vec![apex, far],
1451 Some((false, _, apex)) => vec![near, apex],
1452 None => vec![near, far],
1453 }
1454 })
1455 .collect::<Vec<_>>();
1456 let extended = extend_along_rulings(source, back, forward)?;
1457 let extended_offsets = OffsetEvaluator::new(
1458 "offset_surface",
1459 &extended,
1460 OffsetNormal::FaceStable {
1461 same_sense: face.same_sense,
1462 },
1463 );
1464 let [v0, v1] = knot_v.domain();
1465 let mut developability = 0.0f64;
1466 for (row, &u) in stretched.iter().zip(¶meters_u) {
1467 for fraction in [0.0, 0.5, 1.0] {
1468 let exact = extended_offsets.at(u, v0 + (v1 - v0) * fraction, -distance).or_refuse(KernelStage::Refine, "at")?.point;
1469 let along = row[0].add(row[1].sub(row[0]).scale(fraction));
1470 developability = developability.max(exact.sub(along).length());
1471 }
1472 }
1473 let contract = offset_fit_contract(source);
1474 let stretch_kept = developability <= contract;
1475 samples = if stretch_kept {
1476 stretched
1477 } else {
1478 parameters_u
1479 .iter()
1480 .map(|&u| {
1481 parameters_v
1482 .iter()
1483 .map(|&v| Ok(extended_offsets.at(u, v, -distance).or_refuse(KernelStage::Refine, "at")?.point))
1484 .collect::<Result<Vec<_>, KernelRefusal>>()
1485 })
1486 .collect::<Result<Vec<_>, KernelRefusal>>()?
1487 };
1488 if let Ok(path) = std::env::var("BREP_OFFSET_FIT_TRACE") {
1489 use std::io::Write;
1490 let line = format!(
1491 "extension deg=({},{}) net=({},{}) d={distance:.6} back={back:.6} forward={forward:.6} \
1492 developability={developability:.3e} contract={contract:.3e} lane={} thread={} args={}\n",
1493 source.degree_u,
1494 source.degree_v,
1495 source.control_points.len(),
1496 source.control_points[0].len(),
1497 if stretch_kept { "stretch" } else { "pointwise" },
1498 std::thread::current().name().unwrap_or("-"),
1499 std::env::args().skip(1).collect::<Vec<_>>().join(" "),
1500 );
1501 if let Ok(mut file) = std::fs::OpenOptions::new().create(true).append(true).open(path) {
1502 let _ = file.write_all(line.as_bytes());
1503 }
1504 }
1505 extended_source = Some(extended);
1506 }
1507 }
1508 }
1509 let reference = extended_source.as_ref().unwrap_or(source);
1510 if !reparameterised && exact_cylinder_offsets_on() {
1516 if let Some(surface) = cylinder_offset_surface(reference, face.same_sense, distance)? {
1517 return Ok((surface, OffsetSurfaceLane::Analytic, extended_source));
1518 }
1519 }
1520 let weights = reference
1521 .control_points
1522 .iter()
1523 .map(|row| row.iter().map(|point| point.w).collect::<Vec<_>>())
1524 .collect::<Vec<_>>();
1525 let fitted = NurbsSurface::new(
1526 source.degree_u,
1527 source.degree_v,
1528 source.knots_u.clone(),
1529 source.knots_v.clone(),
1530 interpolate_tensor(
1531 &knot_u,
1532 &knot_v,
1533 ¶meters_u,
1534 ¶meters_v,
1535 &samples,
1536 &weights,
1537 )?,
1538 ).or_refuse(KernelStage::Refine, "new")?;
1539 if reparameterised {
1540 return Ok((fitted, OffsetSurfaceLane::Reparameterised, None));
1541 }
1542 let reference_offsets = OffsetEvaluator::new(
1543 "offset_surface",
1544 reference,
1545 OffsetNormal::FaceStable {
1546 same_sense: face.same_sense,
1547 },
1548 );
1549 Ok((
1550 refine_offset_fit(reference, &reference_offsets, distance, fitted)?,
1551 OffsetSurfaceLane::Fit,
1552 extended_source,
1553 ))
1554}
1555
1556
1557fn analytic_offset_apex(source: &NurbsSurface, samples: &[Vec<Vec3>], contract: f64) -> Option<(f64, Vec3)> {
1566 let Some(crate::AnalyticSurface::RuledRevolution { frame, .. }) = crate::analytic_surface::recognize(source) else {
1567 return None;
1568 };
1569 let radial = |point: Vec3| {
1570 let offset = point.sub(frame.origin);
1571 offset.sub(frame.axis.scale(offset.dot(frame.axis)))
1572 };
1573 let mut crossings = Vec::with_capacity(samples.len());
1574 for row in samples {
1575 let (near, far) = (radial(row[0]), radial(row[1]));
1576 let step = far.sub(near);
1577 let at = -near.dot(step) / step.dot(step);
1578 if !at.is_finite() {
1579 return None;
1580 }
1581 crossings.push((at, row[0].add(row[1].sub(row[0]).scale(at))));
1582 }
1583 let count = crossings.len() as f64;
1586 let at = crossings.iter().map(|(at, _)| at).sum::<f64>() / count;
1587 let first = crossings.first()?.1;
1588 let spread = crossings.iter().fold(Vec3::default(), |sum, (_, point)| sum.add(point.sub(first)));
1589 let centre = first.add(spread.scale(1.0 / count));
1590 let apex = frame.origin.add(frame.axis.scale(centre.sub(frame.origin).dot(frame.axis)));
1591 crossings
1594 .iter()
1595 .all(|(_, point)| radial(*point).length() <= contract && point.sub(apex).length() <= contract)
1596 .then_some((at, apex))
1597}
1598
1599fn extend_along_rulings(surface: &NurbsSurface, back: f64, forward: f64) -> Result<NurbsSurface, KernelRefusal> {
1606 let rows = surface
1607 .control_points
1608 .iter()
1609 .map(|row| {
1610 let step = row[1].add(row[0].scale(-1.0));
1611 vec![row[0].add(step.scale(-back)), row[1].add(step.scale(forward))]
1612 })
1613 .collect::<Vec<_>>();
1614 if rows.iter().flatten().any(|point| point.w <= 1e-12) {
1615 return Err(KernelRefusal::unsupported(KernelStage::Refine, "offset_ruled_extension_weight", format!(
1616 "offset_surface: extending a ruled face by ({back:.6}, {forward:.6}) of its rulings \
1617 carries a weight through zero; the extended face is not this surface"
1618 )));
1619 }
1620 NurbsSurface::new(surface.degree_u, 1, surface.knots_u.clone(), surface.knots_v.clone(), rows)
1621 .or_refuse(KernelStage::Refine, "new")
1622}
1623
1624fn offset_fit_contract(source: &NurbsSurface) -> f64 {
1627 let scale = crate::model_scale(
1628 source
1629 .control_points
1630 .iter()
1631 .flatten()
1632 .filter_map(|point| point.point().ok()),
1633 );
1634 crate::KernelTolerances::for_scale(scale, 1e-7).intersection_fit
1635}
1636
1637const OFFSET_FIT_REFINEMENTS: usize = 6;
1639
1640const OFFSET_FIT_MAX_CONTROLS_SEPARABLE: usize = 16_384;
1643const OFFSET_FIT_MAX_CONTROLS_TENSOR: usize = 900;
1644
1645#[derive(Clone, Debug)]
1650struct OffsetFitDeviation {
1651 along_u: f64,
1652 along_v: f64,
1653 between: f64,
1654 u_sites: Vec<(f64, f64)>,
1655 v_sites: Vec<(f64, f64)>,
1656 between_uv: (f64, f64),
1657}
1658
1659impl OffsetFitDeviation {
1660 fn worst(&self) -> f64 {
1661 self.along_u.max(self.along_v).max(self.between)
1662 }
1663
1664 fn refinement_sites(&self, bar: f64) -> (Vec<f64>, Vec<f64>) {
1665 let mut u = self.u_sites.iter().filter(|(_, miss)| *miss > bar)
1666 .map(|(parameter, _)| *parameter).collect::<Vec<_>>();
1667 let mut v = self.v_sites.iter().filter(|(_, miss)| *miss > bar)
1668 .map(|(parameter, _)| *parameter).collect::<Vec<_>>();
1669 if u.is_empty() && v.is_empty() && self.between > bar {
1670 u.push(self.between_uv.0);
1671 v.push(self.between_uv.1);
1672 }
1673 (u, v)
1674 }
1675}
1676
1677fn greville_midpoints(parameters: &[f64]) -> Vec<f64> {
1678 parameters
1679 .windows(2)
1680 .filter(|pair| pair[1] - pair[0] > 1e-12)
1681 .map(|pair| 0.5 * (pair[0] + pair[1]))
1682 .collect()
1683}
1684
1685fn offset_fit_deviation(
1686 fitted: &NurbsSurface,
1687 evaluator: &OffsetEvaluator,
1688 distance: f64,
1689) -> Result<OffsetFitDeviation, KernelRefusal> {
1690 let parameters_u = greville_parameters(&KnotVector::new(fitted.knots_u.clone(), fitted.degree_u).or_refuse(KernelStage::Refine, "new")?);
1691 let parameters_v = greville_parameters(&KnotVector::new(fitted.knots_v.clone(), fitted.degree_v).or_refuse(KernelStage::Refine, "new")?);
1692 let (middle_u, middle_v) = (greville_midpoints(¶meters_u), greville_midpoints(¶meters_v));
1693 let residual_locus = std::env::var("BREP_OFFSET_FIT_RESIDUAL").as_deref() != Ok("0");
1694 let gap = |u: f64, v: f64| -> Result<f64, KernelRefusal> {
1695 Ok(fitted.evaluate(u, v).or_refuse(KernelStage::Refine, "evaluate")?.sub(evaluator.at(u, v, -distance).or_refuse(KernelStage::Refine, "at")?.point).length())
1696 };
1697 let mut deviation = OffsetFitDeviation {
1698 along_u: 0.0,
1699 along_v: 0.0,
1700 between: 0.0,
1701 u_sites: Vec::new(),
1702 v_sites: if residual_locus { middle_v.iter().map(|&v| (v, 0.0)).collect() } else { Vec::new() },
1703 between_uv: (0.0, 0.0),
1704 };
1705 for &u in &middle_u {
1706 let mut along = 0.0f64;
1707 for &v in ¶meters_v {
1708 let miss = gap(u, v)?;
1709 along = along.max(miss);
1710 deviation.along_u = deviation.along_u.max(miss);
1711 }
1712 if residual_locus { deviation.u_sites.push((u, along)); }
1713 for &v in &middle_v {
1714 let miss = gap(u, v)?;
1715 if miss > deviation.between { deviation.between_uv = (u, v); }
1716 deviation.between = deviation.between.max(miss);
1717 }
1718 }
1719 for &u in ¶meters_u {
1720 for (index, &v) in middle_v.iter().enumerate() {
1721 let miss = gap(u, v)?;
1722 deviation.along_v = deviation.along_v.max(miss);
1723 if residual_locus { deviation.v_sites[index].1 = deviation.v_sites[index].1.max(miss); }
1724 }
1725 }
1726 Ok(deviation)
1727}
1728
1729fn raise_linear_directions(
1739 surface: &NurbsSurface,
1740 in_u: bool,
1741 in_v: bool,
1742) -> Result<Option<NurbsSurface>, KernelRefusal> {
1743 fn raise(knots: &[f64], row: &[Vec4]) -> Option<(Vec<f64>, Vec<Vec4>)> {
1744 let count = row.len();
1746 if knots.len() != count + 2 {
1747 return None;
1748 }
1749 let breaks = &knots[1..=count];
1750 if breaks.windows(2).any(|pair| pair[1] - pair[0] <= 1e-12) {
1751 return None;
1752 }
1753 let mut raised_knots = vec![breaks[0]; 4];
1754 for &interior in &breaks[1..count - 1] {
1755 raised_knots.extend([interior; 3]);
1756 }
1757 raised_knots.extend([breaks[count - 1]; 4]);
1758 let mut points = Vec::with_capacity(3 * (count - 1) + 1);
1759 for pair in row.windows(2) {
1760 let step = pair[1].add(pair[0].scale(-1.0));
1761 points.push(pair[0]);
1762 points.push(pair[0].add(step.scale(1.0 / 3.0)));
1763 points.push(pair[0].add(step.scale(2.0 / 3.0)));
1764 }
1765 points.push(row[count - 1]);
1766 Some((raised_knots, points))
1767 }
1768 let mut knots_u = surface.knots_u.clone();
1769 let mut knots_v = surface.knots_v.clone();
1770 let mut degree_u = surface.degree_u;
1771 let mut degree_v = surface.degree_v;
1772 let mut net = surface.control_points.clone();
1773 if in_v {
1774 if degree_v != 1 {
1775 return Ok(None);
1776 }
1777 let mut rows = Vec::with_capacity(net.len());
1778 for row in &net {
1779 let Some((knots, points)) = raise(&surface.knots_v, row) else {
1780 return Ok(None);
1781 };
1782 knots_v = knots;
1783 rows.push(points);
1784 }
1785 net = rows;
1786 degree_v = 3;
1787 }
1788 if in_u {
1789 if degree_u != 1 {
1790 return Ok(None);
1791 }
1792 let count_v = net[0].len();
1793 let mut columns = Vec::with_capacity(count_v);
1794 for column in 0..count_v {
1795 let row = net.iter().map(|row| row[column]).collect::<Vec<_>>();
1796 let Some((knots, points)) = raise(&surface.knots_u, &row) else {
1797 return Ok(None);
1798 };
1799 knots_u = knots;
1800 columns.push(points);
1801 }
1802 let count_u = columns[0].len();
1803 net = (0..count_u)
1804 .map(|row| columns.iter().map(|column| column[row]).collect())
1805 .collect();
1806 degree_u = 3;
1807 }
1808 Ok(Some(NurbsSurface::new(degree_u, degree_v, knots_u, knots_v, net).or_refuse(KernelStage::Refine, "new")?))
1809}
1810
1811fn halve_knot_spans(surface: &NurbsSurface, in_u: bool, in_v: bool) -> Result<NurbsSurface, KernelRefusal> {
1815 fn midpoints(knots: &[f64], degree: usize) -> Vec<f64> {
1816 let last = knots.len() - 1 - degree;
1817 knots[degree..=last]
1818 .windows(2)
1819 .filter(|pair| pair[1] - pair[0] > 1e-12)
1820 .map(|pair| 0.5 * (pair[0] + pair[1]))
1821 .collect()
1822 }
1823 insert_offset_fit_knots(surface,
1824 &if in_u { midpoints(&surface.knots_u, surface.degree_u) } else { Vec::new() },
1825 &if in_v { midpoints(&surface.knots_v, surface.degree_v) } else { Vec::new() })
1826}
1827
1828fn insert_offset_fit_knots(surface: &NurbsSurface, u: &[f64], v: &[f64]) -> Result<NurbsSurface, KernelRefusal> {
1833 let refine = |degree: usize, knots: &[f64], net: Vec<Vec<Vec4>>, inserted: &[f64]| -> Result<(Vec<f64>, Vec<Vec<Vec4>>), KernelRefusal> {
1834 let mut inserted = inserted.to_vec();
1835 inserted.sort_by(f64::total_cmp);
1836 inserted.dedup_by(|a, b| (*a - *b).abs() <= 1e-12);
1837 inserted.retain(|parameter| knots.iter().filter(|knot| (**knot - *parameter).abs() <= 1e-12).count() < degree);
1838 let mut refined_knots = knots.to_vec();
1839 let mut rows = Vec::with_capacity(net.len());
1840 for row in net {
1841 let mut curve = NurbsCurve::new(degree, knots.to_vec(), row).or_refuse(KernelStage::Refine, "new")?;
1842 for ¶meter in &inserted {
1843 curve = curve.insert_knot(parameter, 1).or_refuse(KernelStage::Refine, "insert_knot")?;
1844 }
1845 refined_knots = curve.knots.clone();
1846 rows.push(curve.control_points);
1847 }
1848 Ok((refined_knots, rows))
1849 };
1850 let mut knots_u = surface.knots_u.clone();
1851 let mut knots_v = surface.knots_v.clone();
1852 let mut net = surface.control_points.clone();
1853 if !v.is_empty() {
1854 let (knots, rows) = refine(surface.degree_v, &knots_v, net, v)?;
1855 knots_v = knots;
1856 net = rows;
1857 }
1858 if !u.is_empty() {
1859 let count_v = net[0].len();
1861 let columns = (0..count_v)
1862 .map(|column| net.iter().map(|row| row[column]).collect::<Vec<_>>())
1863 .collect::<Vec<_>>();
1864 let (knots, refined) = refine(surface.degree_u, &knots_u, columns, u)?;
1865 knots_u = knots;
1866 let count_u = refined[0].len();
1867 net = (0..count_u)
1868 .map(|row| refined.iter().map(|column| column[row]).collect())
1869 .collect();
1870 }
1871 NurbsSurface::new(surface.degree_u, surface.degree_v, knots_u, knots_v, net).or_refuse(KernelStage::Refine, "new")
1872}
1873
1874fn refine_offset_fit(
1910 source: &NurbsSurface,
1911 evaluator: &OffsetEvaluator,
1912 distance: f64,
1913 fitted: NurbsSurface,
1914) -> Result<NurbsSurface, KernelRefusal> {
1915 let scale = crate::model_scale(
1916 source
1917 .control_points
1918 .iter()
1919 .flatten()
1920 .filter_map(|point| point.point().ok()),
1921 );
1922 let bar = crate::KernelTolerances::for_scale(scale, 1e-7).intersection_fit;
1923 let bar = if IMPORT_OFFSET_PRECISION.with(std::cell::Cell::get) { bar.min(1e-9) } else { bar };
1924 let trace = std::env::var("BREP_OFFSET_FIT_TRACE").ok();
1925 let started = web_time::Instant::now();
1926 let enabled = std::env::var("BREP_OFFSET_FIT_REFINE").as_deref() != Ok("0");
1927 let Ok(initial) = offset_fit_deviation(&fitted, evaluator, distance) else {
1928 return Ok(fitted);
1929 };
1930 let mut best = fitted;
1931 let mut best_deviation = initial.clone();
1932 let mut refined_source = source.clone();
1933 let mut rounds = 0usize;
1934 let mut residual_mode = false;
1935 let mut stop = "under bar";
1936 if enabled {
1937 while best_deviation.worst() > bar {
1938 if rounds == OFFSET_FIT_REFINEMENTS {
1939 stop = "refinement limit";
1940 break;
1941 }
1942 let (along_u, along_v) = (best_deviation.along_u > bar, best_deviation.along_v > bar);
1943 let (in_u, in_v) = if along_u || along_v {
1944 (along_u, along_v)
1945 } else {
1946 (true, true)
1947 };
1948 let (raise_u, raise_v) = (in_u && refined_source.degree_u == 1, in_v && refined_source.degree_v == 1);
1949 let raised = if raise_u || raise_v {
1950 raise_linear_directions(&refined_source, raise_u, raise_v)?
1951 } else {
1952 None
1953 };
1954 let (halve_u, halve_v) = match raised {
1955 Some(_) => (in_u && !raise_u, in_v && !raise_v),
1956 None => (in_u, in_v),
1957 };
1958 let raised = raised.unwrap_or_else(|| refined_source.clone());
1959 let candidate_source = if halve_u || halve_v {
1960 if residual_mode {
1961 let (u, v) = best_deviation.refinement_sites(bar);
1962 insert_offset_fit_knots(&raised,
1963 if halve_u { &u } else { &[] }, if halve_v { &v } else { &[] })?
1964 } else {
1965 halve_knot_spans(&raised, halve_u, halve_v)?
1966 }
1967 } else {
1968 raised
1969 };
1970 let weights = candidate_source
1971 .control_points
1972 .iter()
1973 .map(|row| row.iter().map(|point| point.w).collect::<Vec<_>>())
1974 .collect::<Vec<_>>();
1975 let controls = weights.len() * weights[0].len();
1976 let ceiling = if separable_weights(&weights).is_some() {
1977 OFFSET_FIT_MAX_CONTROLS_SEPARABLE
1978 } else {
1979 OFFSET_FIT_MAX_CONTROLS_TENSOR
1980 };
1981 if controls > ceiling {
1982 stop = "net ceiling";
1983 break;
1984 }
1985 let knot_u = KnotVector::new(candidate_source.knots_u.clone(), candidate_source.degree_u).or_refuse(KernelStage::Refine, "new")?;
1986 let knot_v = KnotVector::new(candidate_source.knots_v.clone(), candidate_source.degree_v).or_refuse(KernelStage::Refine, "new")?;
1987 let parameters_u = greville_parameters(&knot_u);
1988 let parameters_v = greville_parameters(&knot_v);
1989 let samples = parameters_u
1990 .iter()
1991 .map(|&u| {
1992 parameters_v
1993 .iter()
1994 .map(|&v| Ok(evaluator.at(u, v, -distance).or_refuse(KernelStage::Refine, "at")?.point))
1995 .collect::<Result<Vec<_>, KernelRefusal>>()
1996 })
1997 .collect::<Result<Vec<_>, KernelRefusal>>();
1998 let Ok(samples) = samples else {
1999 stop = "unevaluable sample";
2000 break;
2001 };
2002 let candidate = NurbsSurface::new(
2003 candidate_source.degree_u,
2004 candidate_source.degree_v,
2005 candidate_source.knots_u.clone(),
2006 candidate_source.knots_v.clone(),
2007 interpolate_tensor(&knot_u, &knot_v, ¶meters_u, ¶meters_v, &samples, &weights)?,
2008 ).or_refuse(KernelStage::Refine, "new")?;
2009 let Ok(deviation) = offset_fit_deviation(&candidate, evaluator, distance) else {
2010 stop = "unmeasurable round";
2011 break;
2012 };
2013 rounds += 1;
2014 if deviation.worst() >= best_deviation.worst() {
2015 let first_quadratic_split = rounds == 1
2022 && ((halve_u && source.degree_u == 2 && source.knots_u.len() == 6)
2023 || (halve_v && source.degree_v == 2 && source.knots_v.len() == 6));
2024 if first_quadratic_split {
2025 refined_source = candidate_source;
2026 continue;
2027 }
2028 if !residual_mode && best_deviation.worst() > offset_construction_band(scale)
2033 && std::env::var("BREP_OFFSET_FIT_RESIDUAL").as_deref() != Ok("0")
2034 {
2035 residual_mode = true;
2036 continue;
2037 }
2038 stop = "stopped improving";
2039 break;
2040 }
2041 best = candidate;
2042 best_deviation = deviation;
2043 refined_source = candidate_source;
2044 }
2045 } else if best_deviation.worst() > bar {
2046 stop = "refinement disabled";
2047 }
2048 let band = offset_construction_band(scale);
2053 let refused = enabled && best_deviation.worst() > band;
2054 if let Some(path) = trace {
2055 use std::io::Write;
2056 let caller = std::env::args().skip(1).collect::<Vec<_>>().join(" ");
2057 let thread = std::thread::current().name().unwrap_or("-").to_string();
2058 let line = format!(
2059 "fit deg=({},{}) net=({},{})->({},{}) d={distance:.6} scale={scale:.4} bar={bar:.3e} \
2060 initial=(u {:.3e}, v {:.3e}, uv {:.3e}) final={:.3e} rounds={rounds} stop={stop} \
2061 refused={refused} seconds={:.4} thread={thread} args={caller}\n",
2062 source.degree_u,
2063 source.degree_v,
2064 source.control_points.len(),
2065 source.control_points[0].len(),
2066 best.control_points.len(),
2067 best.control_points[0].len(),
2068 initial.along_u,
2069 initial.along_v,
2070 initial.between,
2071 best_deviation.worst(),
2072 started.elapsed().as_secs_f64(),
2073 );
2074 if let Ok(mut file) = std::fs::OpenOptions::new().create(true).append(true).open(path) {
2075 let _ = file.write_all(line.as_bytes());
2076 }
2077 }
2078 if refused {
2079 return Err(KernelRefusal::non_convergence(KernelStage::Refine, "offset_carrier_fit", format!(
2080 "offset_surface: the fitted offset carrier stays {:.3e} off its pointwise offset at \
2081 distance {distance} after {rounds} refinement round(s) ({stop}), past the offset \
2082 construction band {band:.3e}",
2083 best_deviation.worst()
2084 )));
2085 }
2086 Ok(best)
2087}
2088
2089pub(crate) fn unify_offset_sheet_bases(
2099 first: &NurbsSurface,
2100 second: &NurbsSurface,
2101) -> Result<(NurbsSurface, NurbsSurface), KernelRefusal> {
2102 fn raise_to(surface: &NurbsSurface, degree_u: usize, degree_v: usize) -> Result<NurbsSurface, KernelRefusal> {
2103 let raise_u = surface.degree_u == 1 && degree_u == 3;
2104 let raise_v = surface.degree_v == 1 && degree_v == 3;
2105 if !raise_u && !raise_v {
2106 return Ok(surface.clone());
2107 }
2108 raise_linear_directions(surface, raise_u, raise_v)?
2109 .ok_or_else(|| {
2110 KernelRefusal::internal(
2111 KernelStage::Refine,
2112 "offset_raise_linear",
2113 "offset sheets: a linear direction could not be raised",
2114 )
2115 })
2116 }
2117 let degree_u = first.degree_u.max(second.degree_u);
2118 let degree_v = first.degree_v.max(second.degree_v);
2119 let mut first = raise_to(first, degree_u, degree_v)?;
2120 let mut second = raise_to(second, degree_u, degree_v)?;
2121 if first.degree_u != second.degree_u || first.degree_v != second.degree_v {
2122 return Err(KernelRefusal::internal(KernelStage::Refine, "offset_common_basis", format!(
2123 "offset sheets: degrees ({},{}) and ({},{}) have no common basis",
2124 first.degree_u, first.degree_v, second.degree_u, second.degree_v
2125 )));
2126 }
2127 fn missing(from: &[f64], into: &[f64]) -> Vec<f64> {
2129 let mut extra = Vec::new();
2130 let mut index = 0usize;
2131 for &knot in from {
2132 while index < into.len() && into[index] < knot - 1e-12 {
2133 index += 1;
2134 }
2135 if index < into.len() && (into[index] - knot).abs() <= 1e-12 {
2136 index += 1;
2137 } else {
2138 extra.push(knot);
2139 }
2140 }
2141 extra
2142 }
2143 fn insert(surface: &NurbsSurface, knots: &[f64], along_u: bool) -> Result<NurbsSurface, KernelRefusal> {
2144 if knots.is_empty() {
2145 return Ok(surface.clone());
2146 }
2147 let (degree, vector) = if along_u {
2148 (surface.degree_u, &surface.knots_u)
2149 } else {
2150 (surface.degree_v, &surface.knots_v)
2151 };
2152 let lines = if along_u {
2153 (0..surface.control_points[0].len())
2154 .map(|column| surface.control_points.iter().map(|row| row[column]).collect::<Vec<_>>())
2155 .collect::<Vec<_>>()
2156 } else {
2157 surface.control_points.clone()
2158 };
2159 let mut refined_knots = vector.clone();
2160 let mut refined = Vec::with_capacity(lines.len());
2161 for line in lines {
2162 let mut curve = NurbsCurve::new(degree, vector.clone(), line).or_refuse(KernelStage::Refine, "new")?;
2163 for &knot in knots {
2164 curve = curve.insert_knot(knot, 1).or_refuse(KernelStage::Refine, "insert_knot")?;
2165 }
2166 refined_knots = curve.knots.clone();
2167 refined.push(curve.control_points);
2168 }
2169 let net = if along_u {
2170 (0..refined[0].len())
2171 .map(|row| refined.iter().map(|column| column[row]).collect())
2172 .collect()
2173 } else {
2174 refined
2175 };
2176 let (knots_u, knots_v) = if along_u {
2177 (refined_knots, surface.knots_v.clone())
2178 } else {
2179 (surface.knots_u.clone(), refined_knots)
2180 };
2181 NurbsSurface::new(surface.degree_u, surface.degree_v, knots_u, knots_v, net).or_refuse(KernelStage::Refine, "new")
2182 }
2183 let (to_first_u, to_second_u) = (
2184 missing(&second.knots_u, &first.knots_u),
2185 missing(&first.knots_u, &second.knots_u),
2186 );
2187 first = insert(&first, &to_first_u, true)?;
2188 second = insert(&second, &to_second_u, true)?;
2189 let (to_first_v, to_second_v) = (
2190 missing(&second.knots_v, &first.knots_v),
2191 missing(&first.knots_v, &second.knots_v),
2192 );
2193 first = insert(&first, &to_first_v, false)?;
2194 second = insert(&second, &to_second_v, false)?;
2195 Ok((first, second))
2196}
2197
2198fn carrier_edge_curve(
2220 surface: &NurbsSurface,
2221 pcurve: &NurbsCurve,
2222 points: &[Vec3],
2223 parameters: &[f64],
2224 fit_tolerance: f64,
2225) -> Result<(NurbsCurve, f64, f64), KernelRefusal> {
2226 if affine_image_trusted() && surface.is_affine().or_refuse(KernelStage::Refine, "is_affine")? {
2234 let [q0, q1] = pcurve.domain().or_refuse(KernelStage::Refine, "domain")?;
2235 if (q1 - q0).is_finite() && (q1 - q0).abs() > 0.0 {
2236 let curve = crate::image_curve::affine_image_curve(surface, pcurve).or_refuse(KernelStage::Refine, "affine_image_curve")?;
2237 return Ok((curve, q0, q1));
2238 }
2239 }
2240 let image = if env_read!("BREP_CARRIER_POLYLINE").as_deref() == Some("1") {
2241 Err("BREP_CARRIER_POLYLINE set".to_string())
2242 } else {
2243 crate::image_curve::image_curve(surface, pcurve, fit_tolerance, "offset_face_carrier")
2244 };
2245 match image {
2246 Ok(image) if image.t0 <= image.t1 => Ok((image.curve, image.t0, image.t1)),
2247 Ok(image) => {
2248 let [start, end] = image.curve.domain().or_refuse(KernelStage::Refine, "domain")?;
2251 let curve = image.curve.reversed().or_refuse(KernelStage::Refine, "reversed")?;
2252 Ok((curve, start + end - image.t0, start + end - image.t1))
2253 }
2254 Err(_) => {
2255 let curve = interpolate_curve(points, 1, parameters).or_refuse(KernelStage::Refine, "interpolate_curve")?;
2256 let [t0, t1] = curve.domain().or_refuse(KernelStage::Refine, "domain")?;
2257 Ok((curve, t0, t1))
2258 }
2259 }
2260}
2261
2262fn affine_image_trusted() -> bool {
2263 switch!("BREP_CARRIER_AFFINE_IMAGE", true)
2264}
2265
2266
2267fn lazy_carrier_trace(
2275 surface: &NurbsSurface,
2276 pcurve: &NurbsCurve,
2277 collapse_tolerance: f64,
2278 fit_tolerance: f64,
2279) -> Option<(Vec<Vec3>, (NurbsCurve, f64, f64))> {
2280 if !switch!("BREP_OFFSET_LAZY_CARRIER_TRACE", true) {
2281 return None;
2282 }
2283 if pcurve.degree == 1 && pcurve.control_points.len() == 2 {
2286 let (a, b) = (pcurve.control_points[0], pcurve.control_points[1]);
2287 if (surface.degree_u <= 1 && surface.degree_v <= 1)
2288 || (a.w == b.w && a.y == b.y && surface.degree_u <= 1)
2289 || (a.w == b.w && a.x == b.x && surface.degree_v <= 1)
2290 {
2291 return None;
2292 }
2293 }
2294 fn knots_ok(knots: &[f64], degree: usize, count: usize) -> bool {
2295 degree <= 3 && count <= 64
2296 && KnotVector::new(knots.to_vec(), degree).ok().is_some_and(|k| k.control_point_count() == count)
2297 && knots.iter().all(|k| k.is_finite() && k.abs() <= 1e6)
2298 && knots.windows(2).all(|k| k[0] == k[1] || k[1] - k[0] >= 1e-6)
2299 }
2300 let bounded = |p: &Vec4| (1e-3..=1e3).contains(&p.w)
2301 && [p.x, p.y, p.z].iter().all(|x| x.is_finite() && x.abs() <= 1e12);
2302 let columns = surface.control_points.first()?.len();
2303 if !knots_ok(&surface.knots_u, surface.degree_u, surface.control_points.len())
2304 || !knots_ok(&surface.knots_v, surface.degree_v, columns)
2305 || surface.control_points.iter().any(|row| row.len() != columns || row.iter().any(|p| !bounded(p)))
2306 || !knots_ok(&pcurve.knots, pcurve.degree, pcurve.control_points.len())
2307 || pcurve.control_points.iter().any(|p| !bounded(p))
2308 {
2309 return None;
2310 }
2311 let ([u0, u1], [v0, v1]) = (surface.domain_u().ok()?, surface.domain_v().ok()?);
2312 let uv = pcurve.control_points.iter().map(|p| p.point().ok()).collect::<Option<Vec<_>>>()?;
2313 if uv.iter().any(|p| p.x < u0 || p.x > u1 || p.y < v0 || p.y > v1) {
2314 return None;
2315 }
2316 if !surface.is_affine().ok()? && !uv.iter().all(|p| p.x == uv[0].x) && !uv.iter().all(|p| p.y == uv[0].y) {
2318 return None;
2319 }
2320 let [start, end] = pcurve.domain().ok()?;
2321 let evaluate = |fraction: f64| {
2322 let uv = pcurve.evaluate(start + (end - start) * fraction).ok()?;
2323 surface.evaluate(uv.x, uv.y).ok()
2324 };
2325 let first = evaluate(0.0)?;
2326 let last = evaluate(1.0)?;
2327 let samples = [evaluate(0.25)?, evaluate(0.5)?, evaluate(0.75)?];
2328 let deviation = samples.iter().enumerate().map(|(index, point)| {
2329 point.sub(first.add(last.sub(first).scale((index + 1) as f64 * 0.25))).length()
2330 }).fold(0.0, f64::max);
2331 if last.sub(first).length() <= collapse_tolerance
2332 && !(deviation > 5e-4 && samples[1].sub(first).length() > collapse_tolerance)
2333 {
2334 return None;
2335 }
2336 let image = carrier_edge_curve(surface, pcurve, &[], &[], fit_tolerance).ok()?;
2339 Some((vec![first, samples[1], last], image))
2340}
2341
2342fn mapped_pcurve_polyline(
2343 surface: &NurbsSurface,
2344 pcurve: &NurbsCurve,
2345 degenerate: bool,
2346) -> Result<(Vec<Vec3>, Vec<f64>), KernelRefusal> {
2347 let [start, end] = pcurve.domain().or_refuse(KernelStage::Refine, "domain")?;
2348 let evaluate = |fraction: f64| -> Result<Vec3, KernelRefusal> {
2349 let uv = pcurve.evaluate(start + (end - start) * fraction).or_refuse(KernelStage::Refine, "evaluate")?;
2350 surface.evaluate(uv.x, uv.y).or_refuse(KernelStage::Refine, "evaluate")
2351 };
2352 let first = evaluate(0.0)?;
2353 let last = evaluate(1.0)?;
2354 if degenerate {
2355 return Ok((vec![first, last], vec![0.0, 1.0]));
2356 }
2357 fn append(
2358 evaluate: &impl Fn(f64) -> Result<Vec3, KernelRefusal>,
2359 a_fraction: f64,
2360 a: Vec3,
2361 b_fraction: f64,
2362 b: Vec3,
2363 depth: usize,
2364 parameters: &mut Vec<f64>,
2365 points: &mut Vec<Vec3>,
2366 ) -> Result<(), KernelRefusal> {
2367 let fractions =
2368 [0.25, 0.5, 0.75].map(|local| a_fraction + (b_fraction - a_fraction) * local);
2369 let samples = fractions
2370 .map(evaluate)
2371 .into_iter()
2372 .collect::<Result<Vec<_>, KernelRefusal>>()?;
2373 let deviation = samples
2374 .iter()
2375 .enumerate()
2376 .map(|(index, point)| {
2377 point
2378 .sub(a.add(b.sub(a).scale((index + 1) as f64 * 0.25)))
2379 .length()
2380 })
2381 .fold(0.0, f64::max);
2382 if deviation <= 5e-4 || depth >= 10 {
2383 parameters.push(b_fraction);
2384 points.push(b);
2385 return Ok(());
2386 }
2387 append(
2388 evaluate,
2389 a_fraction,
2390 a,
2391 fractions[1],
2392 samples[1],
2393 depth + 1,
2394 parameters,
2395 points,
2396 )?;
2397 append(
2398 evaluate,
2399 fractions[1],
2400 samples[1],
2401 b_fraction,
2402 b,
2403 depth + 1,
2404 parameters,
2405 points,
2406 )
2407 }
2408 let mut parameters = vec![0.0];
2409 let mut points = vec![first];
2410 append(
2411 &evaluate,
2412 0.0,
2413 first,
2414 1.0,
2415 last,
2416 0,
2417 &mut parameters,
2418 &mut points,
2419 )?;
2420 Ok((points, parameters))
2421}
2422
2423#[derive(Clone, Debug)]
2437pub struct CarrierDeviation {
2438 pub band: f64,
2441 pub lane: OffsetSurfaceLane,
2443 pub surface: Option<MeasuredTolerance>,
2445 pub edges: Vec<(u64, MeasuredTolerance)>,
2450 pub vertices: Vec<(u64, f64)>,
2454}
2455
2456impl CarrierDeviation {
2457 pub fn worst(&self) -> Option<MeasuredTolerance> {
2460 MeasuredTolerance::worst(
2461 self.surface
2462 .into_iter()
2463 .chain(self.edges.iter().map(|(_, measured)| *measured))
2464 .chain(
2465 self.vertices
2466 .iter()
2467 .map(|(_, gap)| MeasuredTolerance::new(*gap, self.band)),
2468 ),
2469 )
2470 }
2471
2472 pub fn exceedances(&self) -> Vec<String> {
2475 let mut out = Vec::new();
2476 if let Some(surface) = self.surface {
2477 if surface.exceeds_band() {
2478 out.push(format!("carrier surface fit {}", surface.describe()));
2479 }
2480 }
2481 for (id, measured) in &self.edges {
2482 if measured.exceeds_band() {
2483 out.push(format!("edge {id} {}", measured.describe()));
2484 }
2485 }
2486 for (id, gap) in &self.vertices {
2487 let measured = MeasuredTolerance::new(*gap, self.band);
2488 if measured.exceeds_band() {
2489 out.push(format!("vertex {id} {}", measured.describe()));
2490 }
2491 }
2492 out
2493 }
2494}
2495
2496#[derive(Clone, Debug, Serialize)]
2497pub struct OffsetFaceCarrier {
2498 pub vertices: Vec<VertexRecord>,
2499 pub edges: Vec<EdgeRecord>,
2500 pub face: FaceRecord,
2501 #[serde(skip)]
2509 pub deviation: Option<CarrierDeviation>,
2510 #[serde(skip)]
2514 pub lane: OffsetSurfaceLane,
2515}
2516
2517fn claim_vertex_image(
2528 source_id: u64,
2529 point: Vec3,
2530 split: f64,
2531 vertex_images: &mut HashMap<u64, Vec<u64>>,
2532 vertices: &mut Vec<VertexRecord>,
2533 next_id: &mut u64,
2534) -> u64 {
2535 if let Some(ids) = vertex_images.get(&source_id) {
2536 let near = ids.iter().copied().find(|id| {
2537 vertices
2538 .iter()
2539 .find(|vertex| vertex.id == *id)
2540 .is_some_and(|vertex| vertex.point.sub(point).length() <= split)
2541 });
2542 if let Some(id) = near {
2543 return id;
2544 }
2545 }
2546 let id = *next_id;
2547 *next_id += 1;
2548 vertices.push(VertexRecord { id, point });
2549 vertex_images.entry(source_id).or_default().push(id);
2550 id
2551}
2552
2553pub fn offset_face_carrier(
2554 solid: &BrepSolid,
2555 face_id: u64,
2556 distance: f64,
2557 planar_extension: f64,
2558) -> Result<OffsetFaceCarrier, KernelRefusal> {
2559 offset_face_carrier_impl(
2560 solid,
2561 face_id,
2562 distance,
2563 &CarrierExtension::uniform(planar_extension),
2564 false,
2565 )
2566}
2567
2568fn pinch_side_by_source_enabled() -> bool {
2583 switch!("BREP_OFFSET_PINCH_SIDE_BY_SOURCE", true)
2584}
2585
2586fn pinch_side_by_source(
2587 source: &NurbsSurface,
2588 parameters_u: &[f64],
2589 parameters_v: &[f64],
2590 samples: &[Vec<Vec3>],
2591 near_centroid: Vec3,
2592 far_centroid: Vec3,
2593) -> Result<Option<bool>, KernelRefusal> {
2594 if !pinch_side_by_source_enabled() || parameters_v.len() != 2 {
2595 return Ok(None);
2596 }
2597 let mut source_rows = [Vec::new(), Vec::new()];
2598 for &u in parameters_u {
2599 for (end, &v) in parameters_v.iter().enumerate() {
2600 source_rows[end].push(source.evaluate(u, v).or_refuse(KernelStage::Refine, "evaluate")?);
2601 }
2602 }
2603 let centroid = |row: &[Vec3]| row.iter().fold(Vec3::default(), |sum, p| sum.add(*p)).scale(1.0 / row.len() as f64);
2604 let spread = |row: &[Vec3]| {
2605 let middle = centroid(row);
2606 row.iter().map(|p| p.sub(middle).length()).fold(0.0f64, f64::max)
2607 };
2608 let reference = if spread(&source_rows[0]) >= spread(&source_rows[1]) { 0 } else { 1 };
2609 let reference_centroid = centroid(&source_rows[reference]);
2610 let (mut near_sign, mut far_sign) = (0.0f64, 0.0f64);
2611 for (k, row) in samples.iter().enumerate() {
2612 let radial = source_rows[reference][k].sub(reference_centroid);
2613 near_sign += row[0].sub(near_centroid).dot(radial);
2614 far_sign += row[1].sub(far_centroid).dot(radial);
2615 }
2616 Ok(match (near_sign > 0.0, far_sign > 0.0) {
2617 (true, false) => Some(true),
2618 (false, true) => Some(false),
2619 _ => None,
2620 })
2621}
2622
2623pub fn offset_face_carrier_sided(
2624 solid: &BrepSolid,
2625 face_id: u64,
2626 distance: f64,
2627 extension: &CarrierExtension,
2628) -> Result<OffsetFaceCarrier, KernelRefusal> {
2629 offset_face_carrier_impl(solid, face_id, distance, extension, false)
2630}
2631
2632pub fn offset_face_carrier_measured(
2652 solid: &BrepSolid,
2653 face_id: u64,
2654 distance: f64,
2655 planar_extension: f64,
2656) -> Result<OffsetFaceCarrier, KernelRefusal> {
2657 offset_face_carrier_impl(
2658 solid,
2659 face_id,
2660 distance,
2661 &CarrierExtension::uniform(planar_extension),
2662 true,
2663 )
2664}
2665
2666fn measure_carrier(
2677 surface: &NurbsSurface,
2678 vertices: &[VertexRecord],
2679 edges: &[EdgeRecord],
2680 loops: &[LoopRecord],
2681 lane: OffsetSurfaceLane,
2682 surface_fit: Option<MeasuredTolerance>,
2683 band: f64,
2684) -> Result<CarrierDeviation, KernelRefusal> {
2685 let edge_by_id: HashMap<u64, &EdgeRecord> = edges.iter().map(|edge| (edge.id, edge)).collect();
2686 let mut per_edge: HashMap<u64, MeasuredTolerance> = HashMap::default();
2690 for loop_record in loops {
2691 for coedge in &loop_record.coedges {
2692 let Some(edge) = edge_by_id.get(&coedge.edge_id) else {
2693 continue;
2694 };
2695 let measured = measure_edge_against_pcurve_image(
2696 surface,
2697 &coedge.pcurve,
2698 edge,
2699 coedge.forward,
2700 band,
2701 )?;
2702 per_edge
2703 .entry(edge.id)
2704 .and_modify(|existing| *existing = existing.worse_of(measured))
2705 .or_insert(measured);
2706 }
2707 }
2708
2709 let mut measured_edges: Vec<(u64, MeasuredTolerance)> = per_edge.into_iter().collect();
2710 measured_edges.sort_by_key(|(id, _)| *id);
2711 let deviation_of: HashMap<u64, f64> = measured_edges
2712 .iter()
2713 .map(|(id, measured)| (*id, measured.deviation()))
2714 .collect();
2715
2716 let mut ends_at: HashMap<u64, Vec<(&EdgeRecord, f64)>> = HashMap::default();
2720 for edge in edges {
2721 ends_at
2722 .entry(edge.start_vertex_id)
2723 .or_default()
2724 .push((edge, edge.t0));
2725 ends_at
2726 .entry(edge.end_vertex_id)
2727 .or_default()
2728 .push((edge, edge.t1));
2729 }
2730
2731 let mut measured_vertices = Vec::with_capacity(vertices.len());
2732 for vertex in vertices {
2733 let mut gaps = Vec::new();
2734 let mut incident = Vec::new();
2735 for (edge, parameter) in ends_at.get(&vertex.id).into_iter().flatten() {
2736 gaps.push(vertex_endpoint_gap(
2737 vertex.point,
2738 edge.curve.evaluate(*parameter).or_refuse(KernelStage::Refine, "evaluate")?,
2739 ));
2740 incident.push(deviation_of.get(&edge.id).copied().unwrap_or(0.0));
2741 }
2742 measured_vertices.push((vertex.id, vertex_tolerance_from_edges(gaps, incident)));
2743 }
2744
2745 Ok(CarrierDeviation {
2746 band,
2747 lane,
2748 surface: surface_fit,
2749 edges: measured_edges,
2750 vertices: measured_vertices,
2751 })
2752}
2753
2754fn offset_face_carrier_impl(
2755 solid: &BrepSolid,
2756 face_id: u64,
2757 distance: f64,
2758 extension: &CarrierExtension,
2759 measure: bool,
2760) -> Result<OffsetFaceCarrier, KernelRefusal> {
2761 let source = solid
2762 .shells
2763 .iter()
2764 .flat_map(|shell| &shell.faces)
2765 .find(|face| face.id == face_id)
2766 .ok_or_else(|| format!("offset_face_carrier: missing face {face_id}")).or_refuse(KernelStage::Refine, "offset_missing_face")?;
2767 let band = offset_construction_band(solid_model_scale(solid));
2775 let fit_tolerance =
2782 crate::KernelTolerances::for_scale(solid_model_scale(solid), 1e-7).intersection_fit;
2783 let (surface, lane, surface_fit) = if measure {
2784 let measured = offset_surface_measured_sided(source, distance, extension, band)?;
2785 (measured.surface, measured.lane, measured.fit)
2786 } else {
2787 let (surface, lane) = offset_surface_with_lane(source, distance, extension)?;
2788 (surface, lane, None)
2789 };
2790 let source_edges = solid
2791 .edges
2792 .iter()
2793 .map(|edge| (edge.id, edge))
2794 .collect::<HashMap<_, _>>();
2795 let source_vertices = solid
2796 .vertices
2797 .iter()
2798 .map(|vertex| (vertex.id, vertex))
2799 .collect::<HashMap<_, _>>();
2800 let mut vertices = Vec::new();
2801 let mut vertex_images = HashMap::default();
2802 let vertex_split = (distance.abs() * 0.1).max(band);
2806 let mut edges = Vec::new();
2807 let mut edge_images = HashMap::default();
2808 let mut loops = Vec::new();
2809 let mut next_id = 1u64;
2810
2811 for source_loop in &source.loops {
2812 let mut coedges = Vec::new();
2813 for source_coedge in &source_loop.coedges {
2814 let source_edge = source_edges
2815 .get(&source_coedge.edge_id)
2816 .ok_or_else(|| "offset_face_carrier: missing source edge".to_string()).or_refuse(KernelStage::Refine, "offset_missing_edge")?;
2817 let (source_start, source_end) = if source_coedge.forward {
2818 (source_edge.start_vertex_id, source_edge.end_vertex_id)
2819 } else {
2820 (source_edge.end_vertex_id, source_edge.start_vertex_id)
2821 };
2822 if !source_vertices.contains_key(&source_start)
2823 || !source_vertices.contains_key(&source_end)
2824 {
2825 return Err(KernelRefusal::internal(KernelStage::Refine, "offset_missing_vertex", "offset_face_carrier: missing source vertex"));
2826 }
2827 let collapse_tolerance = 1e-6f64.max(distance.abs() * 1e-2);
2845 let (points, parameters, exact_image) = match lazy_carrier_trace(
2846 &surface, &source_coedge.pcurve, collapse_tolerance, fit_tolerance,
2847 ) {
2848 Some((points, image)) => (points, Vec::new(), Some(image)),
2849 None => {
2850 let (points, parameters) = mapped_pcurve_polyline(&surface, &source_coedge.pcurve, false)?;
2851 (points, parameters, None)
2852 }
2853 };
2854 let image_collapsed = points
2855 .iter()
2856 .all(|point| point.sub(points[0]).length() <= collapse_tolerance);
2857 let (edge_id, forward) =
2858 if let Some((edge_id, edge_start_vertex_id, creator_forward)) =
2859 edge_images.get(&source_edge.id)
2860 {
2861 if source_start == source_end {
2862 (*edge_id, source_coedge.forward == *creator_forward)
2885 } else {
2886 (
2889 *edge_id,
2890 vertex_images
2891 .get(&source_start)
2892 .is_some_and(|ids: &Vec<u64>| ids.contains(edge_start_vertex_id)),
2893 )
2894 }
2895 } else {
2896 let (curve, t0, t1) = if image_collapsed {
2897 let curve = NurbsCurve::new(
2898 1,
2899 vec![0.0, 0.0, 1.0, 1.0],
2900 vec![
2901 Vec4::from_point(points[0], 1.0),
2902 Vec4::from_point(points[0], 1.0),
2903 ],
2904 ).or_refuse(KernelStage::Refine, "new")?;
2905 (curve, 0.0, 1.0)
2906 } else if let Some(image) = exact_image {
2907 image
2908 } else {
2909 carrier_edge_curve(
2910 &surface,
2911 &source_coedge.pcurve,
2912 &points,
2913 ¶meters,
2914 fit_tolerance,
2915 )?
2916 };
2917 let start_vertex_id = claim_vertex_image(
2918 source_start,
2919 points[0],
2920 vertex_split,
2921 &mut vertex_images,
2922 &mut vertices,
2923 &mut next_id,
2924 );
2925 let end_vertex_id = claim_vertex_image(
2926 source_end,
2927 points[points.len() - 1],
2928 vertex_split,
2929 &mut vertex_images,
2930 &mut vertices,
2931 &mut next_id,
2932 );
2933 let id = next_id;
2934 next_id += 1;
2935 edges.push(EdgeRecord {
2936 id,
2937 curve,
2938 t0,
2939 t1,
2940 start_vertex_id,
2941 end_vertex_id,
2942 degenerate: image_collapsed,
2956 name: source_edge
2960 .name
2961 .as_ref()
2962 .map(|name| format!("{name}_Offset")),
2963 });
2964 edge_images.insert(
2965 source_edge.id,
2966 (id, start_vertex_id, source_coedge.forward),
2967 );
2968 (id, true)
2969 };
2970 let id = next_id;
2971 next_id += 1;
2972 coedges.push(CoedgeRecord {
2973 id,
2974 edge_id,
2975 forward,
2976 pcurve: source_coedge.pcurve.clone(),
2977 });
2978 }
2979 let id = next_id;
2980 next_id += 1;
2981 loops.push(LoopRecord { id, coedges });
2982 }
2983 let deviation = if measure {
2984 Some(measure_carrier(
2985 &surface,
2986 &vertices,
2987 &edges,
2988 &loops,
2989 lane,
2990 surface_fit,
2991 band,
2992 )?)
2993 } else {
2994 None
2995 };
2996 Ok(OffsetFaceCarrier {
2997 vertices,
2998 edges,
2999 face: FaceRecord {
3000 id: next_id,
3001 surface,
3002 same_sense: source.same_sense,
3003 loops,
3004 name: source.name.as_ref().map(|name| format!("{name}_Offset")),
3005 },
3006 deviation,
3007 lane,
3008 })
3009}
3010
3011
3012
3013
3014