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
449pub fn offset_surface_measured(
458 face: &FaceRecord,
459 distance: f64,
460 planar_extension: f64,
461 band: f64,
462) -> Result<MeasuredOffsetSurface, KernelRefusal> {
463 offset_surface_measured_sided(
464 face,
465 distance,
466 &CarrierExtension::uniform(planar_extension),
467 band,
468 )
469}
470
471pub fn offset_surface_measured_sided(
473 face: &FaceRecord,
474 distance: f64,
475 extension: &CarrierExtension,
476 band: f64,
477) -> Result<MeasuredOffsetSurface, KernelRefusal> {
478 offset_surface_measured_sided_mode(face, distance, extension, band,
479 std::env::var("BREP_OFFSET_SPHERE_READING").map_or(true, |v| v != "0" && v != "off"))
480}
481
482fn offset_surface_measured_sided_mode(
483 face: &FaceRecord, distance: f64, extension: &CarrierExtension, band: f64, reuse: bool,
484) -> Result<MeasuredOffsetSurface, KernelRefusal> {
485 let mut sphere_reading = None;
486 let (surface, lane, extended) = offset_surface_constructed(face, distance, extension, &mut sphere_reading)?;
487 let fit = match lane {
488 OffsetSurfaceLane::Affine => Some(MeasuredTolerance::exact(band)),
489 OffsetSurfaceLane::Analytic if reuse && sphere_reading.is_some() => {
494 if crate::profile::profile_enabled() {
498 profile_line!("offset.sphere_reading.profile reused=1");
499 }
500 Some(MeasuredTolerance::new(sphere_reading.unwrap(), band))
501 }
502 OffsetSurfaceLane::Analytic | OffsetSurfaceLane::Fit => {
503 Some(measure_surface_fit_against_pointwise_offset(
504 extended.as_ref().unwrap_or(&face.surface),
505 face.same_sense,
506 &surface,
507 distance,
508 band,
509 )?)
510 }
511 OffsetSurfaceLane::Reparameterised => None,
512 };
513 Ok(MeasuredOffsetSurface { surface, lane, fit })
514}
515
516fn sphere_offset_surface(face: &FaceRecord, distance: f64, reading: &mut Option<f64>) -> Result<Option<NurbsSurface>, KernelRefusal> {
545 if std::env::var_os("BREP_NO_ANALYTIC_OFFSET").is_some() {
549 return Ok(None);
550 }
551 let source = &face.surface;
552 let Some((centre, radius)) = source.analytic().and_then(|shape| shape.sphere_geometry()) else {
553 return Ok(None);
554 };
555 let ([u0, u1], [v0, v1]) = domains(source)?;
556 let Ok(sample) = OffsetEvaluator::new(
563 "offset_surface",
564 source,
565 OffsetNormal::FaceStable {
566 same_sense: face.same_sense,
567 },
568 )
569 .at((u0 + u1) / 2.0, (v0 + v1) / 2.0, -distance)
570 else {
571 return Ok(None);
572 };
573 let source_radial = sample.source.sub(centre);
574 let offset_radial = sample.point.sub(centre);
575 let offset_radius = offset_radial.length();
576 let scale = radius.max(1.0);
577 if radius <= 1e-12
578 || offset_radius <= 1e-9 * scale
579 || offset_radial.dot(source_radial) <= 0.0
582 || ((offset_radius - radius).abs() - distance.abs()).abs() > 1e-9 * scale
585 {
586 return Ok(None);
587 }
588 let factor = offset_radius / radius;
589 let Ok(controls) = source
592 .control_points
593 .iter()
594 .map(|row| {
595 row.iter()
596 .map(|control| {
597 Ok(Vec4::from_point(
598 centre.add(control.point().or_refuse(KernelStage::Refine, "point")?.sub(centre).scale(factor)),
599 control.w,
600 ))
601 })
602 .collect::<Result<Vec<_>, KernelRefusal>>()
603 })
604 .collect::<Result<Vec<Vec<_>>, KernelRefusal>>()
605 else {
606 return Ok(None);
607 };
608 let Ok(surface) = NurbsSurface::new(
609 source.degree_u,
610 source.degree_v,
611 source.knots_u.clone(),
612 source.knots_v.clone(),
613 controls,
614 ) else {
615 return Ok(None);
616 };
617 match crate::offset_measure::sphere_fit_reading(
621 source,
622 face.same_sense,
623 &surface,
624 distance,
625 1e-9 * scale,
626 ) {
627 Ok(measured) if measured.within_band() => {
628 *reading = Some(measured.deviation());
629 Ok(Some(surface))
630 },
631 _ => Ok(None),
632 }
633}
634
635fn revolved_arc_offset_surface(
668 face: &FaceRecord,
669 distance: f64,
670) -> Result<Option<NurbsSurface>, KernelRefusal> {
671 if std::env::var_os("BREP_NO_ANALYTIC_OFFSET").is_some() {
672 return Ok(None);
673 }
674 let source = &face.surface;
675 match source.analytic() {
676 Some(crate::AnalyticSurface::Revolution { .. } | crate::AnalyticSurface::Torus { .. }) => {}
677 _ => return Ok(None),
678 }
679 let rows = &source.control_points;
680 let Some(first_row) = rows.first() else {
681 return Ok(None);
682 };
683 if rows.iter().flatten().any(|control| !(control.w > 0.0)) {
684 return Ok(None);
685 }
686 let Ok(generatrix) = NurbsCurve::new(source.degree_v, source.knots_v.clone(), first_row.clone())
687 else {
688 return Ok(None);
689 };
690 let [t0, t1] = generatrix.domain().or_refuse(KernelStage::Refine, "domain")?;
691 let at = |fraction: f64| generatrix.evaluate(t0 + (t1 - t0) * fraction);
692 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")?);
694 let (ab, ae) = (b.sub(a), e.sub(a));
695 let normal = ab.cross(ae);
696 let normal_length_squared = normal.dot(normal);
697 let Some(centre) = crate::circumcenter(a, b, e) else { return Ok(None); };
698 let radius = a.sub(centre).length();
699 let scale = (centre.length() + radius).max(1.0);
700 let band = 1e-9 * scale;
701 let unit_normal = normal.scale(1.0 / normal_length_squared.sqrt());
702 let samples = 16 * generatrix.control_points.len();
703 for index in 0..=samples {
704 let point = at(index as f64 / samples as f64).or_refuse(KernelStage::Refine, "at")?;
705 let radial = point.sub(centre);
706 if (radial.length() - radius).abs() > band || radial.dot(unit_normal).abs() > band {
707 return Ok(None);
708 }
709 }
710 let controls = first_row
713 .iter()
714 .map(|control| control.point().or_refuse(KernelStage::Refine, "point"))
715 .collect::<Result<Vec<_>, KernelRefusal>>()?;
716 let origin = controls[0];
717 let mut best = (0usize, 0usize, 0.0f64);
718 for first in 1..controls.len() {
719 for second in first + 1..controls.len() {
720 let area = controls[first]
721 .sub(origin)
722 .cross(controls[second].sub(origin))
723 .length();
724 if area > best.2 {
725 best = (first, second, area);
726 }
727 }
728 }
729 let (first, second, area) = best;
730 if area <= 1e-9 * scale * scale {
731 return Ok(None);
732 }
733 let (along_first, along_second) = (controls[first].sub(origin), controls[second].sub(origin));
734 let offset_from_origin = centre.sub(origin);
735 let (g11, g12, g22) = (
736 along_first.dot(along_first),
737 along_first.dot(along_second),
738 along_second.dot(along_second),
739 );
740 let determinant = g11 * g22 - g12 * g12;
741 let (r1, r2) = (along_first.dot(offset_from_origin), along_second.dot(offset_from_origin));
742 let s = (r1 * g22 - r2 * g12) / determinant;
743 let t = (r2 * g11 - r1 * g12) / determinant;
744 if origin
745 .add(along_first.scale(s))
746 .add(along_second.scale(t))
747 .sub(centre)
748 .length()
749 > band
750 {
751 return Ok(None);
752 }
753 let ([u0, _], [v0, v1]) = domains(source)?;
756 let Ok(sample) = OffsetEvaluator::new(
757 "offset_surface",
758 source,
759 OffsetNormal::FaceStable {
760 same_sense: face.same_sense,
761 },
762 )
763 .at(u0, (v0 + v1) / 2.0, -distance)
764 else {
765 return Ok(None);
766 };
767 let source_radial = sample.source.sub(centre);
768 let offset_radial = sample.point.sub(centre);
769 let offset_radius = offset_radial.length();
770 if (source_radial.length() - radius).abs() > band
771 || offset_radius <= band
772 || offset_radial.dot(source_radial) <= 0.0
773 || ((offset_radius - radius).abs() - distance.abs()).abs() > band
774 {
775 return Ok(None);
776 }
777 let factor = offset_radius / radius;
778 let Ok(offset_rows) = rows
779 .iter()
780 .map(|row| {
781 let points = row.iter().map(|control| control.point().or_refuse(KernelStage::Refine, "point")).collect::<Result<Vec<_>, KernelRefusal>>()?;
782 let row_origin = points[0];
783 let row_centre = row_origin
784 .add(points[first].sub(row_origin).scale(s))
785 .add(points[second].sub(row_origin).scale(t));
786 Ok(points
787 .iter()
788 .zip(row)
789 .map(|(point, control)| {
790 Vec4::from_point(row_centre.add(point.sub(row_centre).scale(factor)), control.w)
791 })
792 .collect::<Vec<_>>())
793 })
794 .collect::<Result<Vec<Vec<_>>, KernelRefusal>>()
795 else {
796 return Ok(None);
797 };
798 let Ok(surface) = NurbsSurface::new(
799 source.degree_u,
800 source.degree_v,
801 source.knots_u.clone(),
802 source.knots_v.clone(),
803 offset_rows,
804 ) else {
805 return Ok(None);
806 };
807 match measure_surface_fit_against_pointwise_offset(
808 source,
809 face.same_sense,
810 &surface,
811 distance,
812 band,
813 ) {
814 Ok(measured) if measured.within_band() => Ok(Some(surface)),
815 _ => Ok(None),
816 }
817}
818
819pub(crate) fn exact_cylinder_offsets_on() -> bool {
824 switch!("BREP_OFFSET_EXACT_CYLINDER", true)
825}
826
827
828pub(crate) fn cylinder_offset_factor(
835 surface: &NurbsSurface,
836 same_sense: bool,
837 distance: f64,
838) -> Result<Option<(Vec3, Vec3, f64, f64)>, KernelRefusal> {
839 if std::env::var_os("BREP_NO_ANALYTIC_OFFSET").is_some() {
840 return Ok(None);
841 }
842 let Some(crate::AnalyticSurface::RuledRevolution { frame, rho0, rho1, height }) = surface.analytic() else {
843 return Ok(None);
844 };
845 let radius = 0.5 * (rho0 + rho1);
846 if !(radius > 0.0) || (rho0 - rho1).abs() > 1e-9 * radius.max(1.0) {
847 return Ok(None);
848 }
849 let Ok(axis) = frame.axis.normalized() else {
850 return Ok(None);
851 };
852 let origin = frame.origin;
853 let band = 1e-9 * (origin.length() + radius + height.abs()).max(1.0);
854 let perpendicular = |point: Vec3| {
855 let along = point.sub(origin);
856 along.sub(axis.scale(along.dot(axis)))
857 };
858 let [u0, u1] = surface.domain_u().or_refuse(KernelStage::Refine, "domain_u")?;
859 let [v0, v1] = surface.domain_v().or_refuse(KernelStage::Refine, "domain_v")?;
860 let Ok(sample) = OffsetEvaluator::new("offset_surface", surface, OffsetNormal::FaceStable { same_sense })
861 .at((u0 + u1) * 0.5, (v0 + v1) * 0.5, -distance)
862 else {
863 return Ok(None);
864 };
865 let (source_radial, offset_radial) = (perpendicular(sample.source), perpendicular(sample.point));
866 let offset_radius = offset_radial.length();
867 if (source_radial.length() - radius).abs() > band
868 || offset_radius <= band
869 || offset_radial.dot(source_radial) <= 0.0
870 || ((offset_radius - radius).abs() - distance.abs()).abs() > band
871 || sample.point.sub(sample.source).dot(axis).abs() > band
872 {
873 return Ok(None);
874 }
875 Ok(Some((origin, axis, radius, offset_radius / radius)))
876}
877
878fn cylinder_offset_surface(
891 reference: &NurbsSurface,
892 same_sense: bool,
893 distance: f64,
894) -> Result<Option<NurbsSurface>, KernelRefusal> {
895 let Some((origin, axis, radius, factor)) = cylinder_offset_factor(reference, same_sense, distance)? else {
896 return Ok(None);
897 };
898 if reference.control_points.iter().flatten().any(|control| !(control.w > 0.0)) {
899 return Ok(None);
900 }
901 let Ok(rows) = reference
902 .control_points
903 .iter()
904 .map(|row| {
905 row.iter()
906 .map(|control| {
907 let point = control.point()?;
908 let foot = origin.add(axis.scale(point.sub(origin).dot(axis)));
909 Ok(Vec4::from_point(foot.add(point.sub(foot).scale(factor)), control.w))
910 })
911 .collect::<Result<Vec<_>, String>>()
912 })
913 .collect::<Result<Vec<Vec<_>>, String>>()
914 else {
915 return Ok(None);
916 };
917 let Ok(surface) = NurbsSurface::new(
918 reference.degree_u,
919 reference.degree_v,
920 reference.knots_u.clone(),
921 reference.knots_v.clone(),
922 rows,
923 ) else {
924 return Ok(None);
925 };
926 let band = 1e-9 * (origin.length() + radius * factor.max(1.0)).max(1.0);
932 let evaluator = OffsetEvaluator::new("offset_surface", reference, OffsetNormal::FaceStable { same_sense });
933 let [u0, u1] = reference.domain_u().or_refuse(KernelStage::Refine, "domain_u")?;
934 let [v0, v1] = reference.domain_v().or_refuse(KernelStage::Refine, "domain_v")?;
935 for i in 0..=4 {
936 for j in 0..=2 {
937 let (u, v) = (u0 + (u1 - u0) * i as f64 / 4.0, v0 + (v1 - v0) * j as f64 / 2.0);
938 let (Ok(want), Ok(got)) = (evaluator.at(u, v, -distance), surface.evaluate(u, v)) else {
939 return Ok(None);
940 };
941 if !(want.point.sub(got).length() <= band) {
942 return Ok(None);
943 }
944 }
945 }
946 Ok(Some(surface))
947}
948
949pub(crate) fn offset_surface_with_lane(
950 face: &FaceRecord,
951 distance: f64,
952 extension: &CarrierExtension,
953) -> Result<(NurbsSurface, OffsetSurfaceLane), KernelRefusal> {
954 offset_surface_constructed(face, distance, extension, &mut None).map(|(surface, lane, _)| (surface, lane))
955}
956
957pub(crate) fn transpose_offset_surface(surface: &NurbsSurface) -> Result<NurbsSurface, KernelRefusal> {
961 let controls = (0..surface.control_points[0].len())
962 .map(|column| surface.control_points.iter().map(|row| row[column]).collect())
963 .collect();
964 NurbsSurface::new(surface.degree_v, surface.degree_u, surface.knots_v.clone(),
965 surface.knots_u.clone(), controls).or_refuse(KernelStage::Refine, "offset_transpose")
966}
967
968pub(crate) fn apex_end_reach_enabled() -> bool {
971 switch!("BREP_OFFSET_APEX_END_REACH", true)
972}
973
974
975fn offset_surface_constructed(
976 face: &FaceRecord,
977 distance: f64,
978 extension: &CarrierExtension,
979 sphere_reading: &mut Option<f64>,
980) -> Result<(NurbsSurface, OffsetSurfaceLane, Option<NurbsSurface>), KernelRefusal> {
981 let source = &face.surface;
982 let extension_active = extension.is_active();
983 let normalize_ruling = std::env::var("BREP_OFFSET_FIT_RESIDUAL").as_deref() != Ok("0")
989 && source.degree_u == 1 && source.control_points.len() == 2;
990 let normalize_sphere = std::env::var("BREP_OFFSET_FOLD_CHART").as_deref() != Ok("0")
991 && source.degree_u == 2 && source.degree_v == 2 && source.analytic().is_none();
992 if normalize_ruling || normalize_sphere {
993 let transposed = transpose_offset_surface(source)?;
994 let ruled = normalize_ruling && matches!(transposed.analytic(), Some(crate::AnalyticSurface::RuledRevolution { .. }));
995 let spherical = normalize_sphere && transposed.analytic().and_then(|shape| shape.sphere_geometry()).is_some();
996 if ruled || spherical {
997 let mut turned = face.clone();
998 turned.surface = transposed;
999 turned.same_sense = !turned.same_sense;
1000 for coedge in turned.loops.iter_mut().flat_map(|lp| &mut lp.coedges) {
1001 let controls = coedge.pcurve.control_points.iter().map(|point| {
1002 let mut swapped = *point;
1003 std::mem::swap(&mut swapped.x, &mut swapped.y);
1004 swapped
1005 }).collect();
1006 coedge.pcurve = NurbsCurve::new(coedge.pcurve.degree,
1007 coedge.pcurve.knots.clone(), controls).or_refuse(KernelStage::Refine, "offset_transpose_pcurve")?;
1008 }
1009 let turned_extension = CarrierExtension {
1010 u_min: extension.v_min, u_max: extension.v_max,
1011 v_min: extension.u_min, v_max: extension.u_max,
1012 };
1013 let (surface, lane, extended) = offset_surface_constructed(&turned, distance, &turned_extension, &mut None)?;
1014 return Ok((transpose_offset_surface(&surface)?, lane,
1015 extended.as_ref().map(transpose_offset_surface).transpose()?));
1016 }
1017 }
1018 if source.is_affine().or_refuse(KernelStage::Refine, "is_affine")? {
1019 let ([u0, u1], [v0, v1]) = domains(source)?;
1020 let normal = stable_face_normal(face, (u0 + u1) / 2.0, (v0 + v1) / 2.0)?;
1021 let shift = normal.scale(-distance);
1022 let mut points = source
1023 .control_points
1024 .iter()
1025 .map(|row| {
1026 row.iter()
1027 .map(|control| Ok(control.point().or_refuse(KernelStage::Refine, "point")?.add(shift)))
1028 .collect::<Result<Vec<_>, KernelRefusal>>()
1029 })
1030 .collect::<Result<Vec<_>, KernelRefusal>>()?;
1031 if extension_active {
1032 let p00 = points[0][0];
1033 let p01 = points[0][1];
1034 let p10 = points[1][0];
1035 let direction_u = p10.sub(p00).normalized().or_refuse(KernelStage::Refine, "normalized")?;
1036 let direction_v = p01.sub(p00).normalized().or_refuse(KernelStage::Refine, "normalized")?;
1037 let (trim_u, trim_v) = trim_domain_fractions(face, [u0, u1], [v0, v1])?;
1043 let (back_u, forward_u) = domain_end_moves(extension.u_min, extension.u_max, trim_u);
1044 let (back_v, forward_v) = domain_end_moves(extension.v_min, extension.v_max, trim_v);
1045 points[0][0] = p00
1046 .sub(direction_u.scale(back_u))
1047 .sub(direction_v.scale(back_v));
1048 points[0][1] = p01
1049 .sub(direction_u.scale(back_u))
1050 .add(direction_v.scale(forward_v));
1051 points[1][0] = p10
1052 .add(direction_u.scale(forward_u))
1053 .sub(direction_v.scale(back_v));
1054 points[1][1] = points[1][1]
1055 .add(direction_u.scale(forward_u))
1056 .add(direction_v.scale(forward_v));
1057 }
1058 let controls = points
1059 .into_iter()
1060 .enumerate()
1061 .map(|(row, points)| {
1062 points
1063 .into_iter()
1064 .enumerate()
1065 .map(|(column, point)| {
1066 Vec4::from_point(point, source.control_points[row][column].w)
1067 })
1068 .collect()
1069 })
1070 .collect();
1071 let lane = if extension_active {
1075 OffsetSurfaceLane::Reparameterised
1076 } else {
1077 OffsetSurfaceLane::Affine
1078 };
1079 return Ok((
1080 NurbsSurface::new(
1081 source.degree_u,
1082 source.degree_v,
1083 source.knots_u.clone(),
1084 source.knots_v.clone(),
1085 controls,
1086 ).or_refuse(KernelStage::Refine, "new")?,
1087 lane,
1088 None,
1089 ));
1090 }
1091
1092 if let Some(surface) = sphere_offset_surface(face, distance, sphere_reading)? {
1102 return Ok((surface, OffsetSurfaceLane::Analytic, None));
1103 }
1104 if let Some(surface) = revolved_arc_offset_surface(face, distance)? {
1107 return Ok((surface, OffsetSurfaceLane::Analytic, None));
1108 }
1109
1110 let knot_u = KnotVector::new(source.knots_u.clone(), source.degree_u).or_refuse(KernelStage::Refine, "new")?;
1111 let knot_v = KnotVector::new(source.knots_v.clone(), source.degree_v).or_refuse(KernelStage::Refine, "new")?;
1112 let parameters_u = greville_parameters(&knot_u);
1113 let parameters_v = greville_parameters(&knot_v);
1114 let evaluator = OffsetEvaluator::new(
1120 "offset_surface",
1121 source,
1122 OffsetNormal::FaceStable {
1123 same_sense: face.same_sense,
1124 },
1125 );
1126 let mut samples = Vec::new();
1127 for &u in ¶meters_u {
1128 let mut row = Vec::new();
1129 for &v in ¶meters_v {
1130 row.push(evaluator.at(u, v, -distance).or_refuse(KernelStage::Refine, "at")?.point);
1131 }
1132 samples.push(row);
1133 }
1134 let mut reparameterised = false;
1149 let mut extended_source: Option<NurbsSurface> = None;
1150 if parameters_v.len() == 2 && parameters_u.len() >= 2 {
1157 let centroid = |column: usize| {
1158 let mut sum = Vec3::default();
1159 for row in &samples {
1160 sum = sum.add(row[column]);
1161 }
1162 sum.scale(1.0 / samples.len() as f64)
1163 };
1164 let near_centroid = centroid(0);
1165 let far_centroid = centroid(1);
1166 let mut inverted = true;
1167 let mut pinch_fraction = 0.0f64;
1168 let mut near_mean = 0.0f64;
1169 let mut far_mean = 0.0f64;
1170 for row in &samples {
1171 let near_radial = row[0].sub(near_centroid);
1172 let far_radial = row[1].sub(far_centroid);
1173 let near_len = near_radial.length();
1174 let far_len = far_radial.length();
1175 if near_len <= 1e-9 || far_len <= 1e-9 {
1176 inverted = false;
1177 break;
1178 }
1179 if near_radial.dot(far_radial) >= 0.0 {
1180 inverted = false;
1181 break;
1182 }
1183 pinch_fraction += near_len / (near_len + far_len) / samples.len() as f64;
1184 near_mean += near_len / samples.len() as f64;
1185 far_mean += far_len / samples.len() as f64;
1186 }
1187 if inverted {
1188 let retrim_far = match pinch_side_by_source(source, ¶meters_u, ¶meters_v, &samples, near_centroid, far_centroid)? {
1189 Some(far) => far,
1190 None => far_mean <= near_mean,
1191 };
1192 let (_, trim_v) = trim_domain_fractions(face, knot_u.domain(), knot_v.domain())?;
1216 let trim_reaches_the_pinch = if retrim_far {
1217 trim_v[1] > pinch_fraction + 1e-9
1218 } else {
1219 trim_v[0] < pinch_fraction - 1e-9
1220 };
1221 if trim_reaches_the_pinch {
1222 reparameterised = true;
1225 for row in &mut samples {
1226 let near = row[0];
1227 let far = row[1];
1228 let pinch = near.add(far.sub(near).scale(pinch_fraction));
1229 if retrim_far {
1230 row[1] = pinch;
1231 } else {
1232 row[0] = pinch;
1233 }
1234 }
1235 }
1236 }
1237 if extension.extends_v() && !inverted {
1257 let apex_end_reach = apex_end_reach_enabled();
1266 let mut min_ruling = f64::MAX;
1267 let mut back_allowance = f64::MAX;
1268 let mut forward_allowance = f64::MAX;
1269 let mut extendable = true;
1270 for row in &samples {
1271 let ruling = row[1].sub(row[0]);
1272 let length = ruling.length();
1273 min_ruling = min_ruling.min(length);
1274 let near_radial = row[0].sub(near_centroid).length();
1278 let far_radial = row[1].sub(far_centroid).length();
1279 if (far_radial - near_radial).abs() > 1e-9 {
1280 let apex_at = near_radial / (near_radial - far_radial);
1281 if apex_end_reach && apex_at.abs() <= 1e-9 {
1282 back_allowance = 0.0;
1283 continue;
1284 }
1285 if apex_end_reach && (apex_at - 1.0).abs() <= 1e-9 {
1286 forward_allowance = 0.0;
1287 continue;
1288 }
1289 if (-1e-9..=1.0 + 1e-9).contains(&apex_at) {
1290 extendable = false;
1292 break;
1293 }
1294 if apex_at < 0.0 {
1295 back_allowance = back_allowance.min(0.9 * -apex_at);
1296 } else {
1297 forward_allowance = forward_allowance.min(0.9 * (apex_at - 1.0));
1298 }
1299 }
1300 }
1301 let mut source_back = f64::MAX;
1309 let mut source_forward = f64::MAX;
1310 if extendable {
1311 let source_centroid = |column: usize| {
1312 let mut sum = Vec3::default();
1313 for row in &source.control_points {
1314 if let Ok(point) = row[column].point() {
1315 sum = sum.add(point);
1316 }
1317 }
1318 sum.scale(1.0 / source.control_points.len() as f64)
1319 };
1320 let (near_source, far_source) = (source_centroid(0), source_centroid(1));
1321 for row in &source.control_points {
1322 let (near, far) = (row[0].point().or_refuse(KernelStage::Refine, "point")?, row[1].point().or_refuse(KernelStage::Refine, "point")?);
1323 let near_radial = near.sub(near_source).length();
1324 let far_radial = far.sub(far_source).length();
1325 if (far_radial - near_radial).abs() > 1e-9 {
1326 let apex_at = near_radial / (near_radial - far_radial);
1327 if apex_end_reach && apex_at.abs() <= 1e-9 {
1328 source_back = 0.0;
1329 continue;
1330 }
1331 if apex_end_reach && (apex_at - 1.0).abs() <= 1e-9 {
1332 source_forward = 0.0;
1333 continue;
1334 }
1335 if (-1e-9..=1.0 + 1e-9).contains(&apex_at) {
1336 extendable = false;
1337 break;
1338 }
1339 if apex_at < 0.0 {
1340 source_back = source_back.min(0.9 * -apex_at);
1341 } else {
1342 source_forward = source_forward.min(0.9 * (apex_at - 1.0));
1343 }
1344 }
1345 }
1346 }
1347 let (back_allowance, forward_allowance) =
1348 (back_allowance.min(source_back), forward_allowance.min(source_forward));
1349 if extendable && min_ruling > 1e-9 {
1350 let (_, trim_v) = trim_domain_fractions(face, knot_u.domain(), knot_v.domain())?;
1357 let (back_world, forward_world) =
1358 domain_end_moves(extension.v_min, extension.v_max, trim_v);
1359 let (requested_back, requested_forward) = (back_world / min_ruling, forward_world / min_ruling);
1360 let apex_end = analytic_offset_apex(source, &samples, offset_fit_contract(source)).and_then(
1372 |(at, apex)| {
1373 if at > 1.0 && at - 1.0 <= requested_forward && at - 1.0 <= source_forward {
1374 Some((false, at - 1.0, apex))
1375 } else if at < 0.0 && -at <= requested_back && -at <= source_back {
1376 Some((true, -at, apex))
1377 } else {
1378 None
1379 }
1380 },
1381 );
1382 let back = match apex_end {
1383 Some((true, reach, _)) => reach,
1384 _ => requested_back.min(back_allowance),
1385 };
1386 let forward = match apex_end {
1387 Some((false, reach, _)) => reach,
1388 _ => requested_forward.min(forward_allowance),
1389 };
1390 let stretched = samples
1391 .iter()
1392 .map(|row| {
1393 let ruling = row[1].sub(row[0]);
1394 let (near, far) = (row[0].sub(ruling.scale(back)), row[1].add(ruling.scale(forward)));
1395 match apex_end {
1396 Some((true, _, apex)) => vec![apex, far],
1397 Some((false, _, apex)) => vec![near, apex],
1398 None => vec![near, far],
1399 }
1400 })
1401 .collect::<Vec<_>>();
1402 let extended = extend_along_rulings(source, back, forward)?;
1403 let extended_offsets = OffsetEvaluator::new(
1404 "offset_surface",
1405 &extended,
1406 OffsetNormal::FaceStable {
1407 same_sense: face.same_sense,
1408 },
1409 );
1410 let [v0, v1] = knot_v.domain();
1411 let mut developability = 0.0f64;
1412 for (row, &u) in stretched.iter().zip(¶meters_u) {
1413 for fraction in [0.0, 0.5, 1.0] {
1414 let exact = extended_offsets.at(u, v0 + (v1 - v0) * fraction, -distance).or_refuse(KernelStage::Refine, "at")?.point;
1415 let along = row[0].add(row[1].sub(row[0]).scale(fraction));
1416 developability = developability.max(exact.sub(along).length());
1417 }
1418 }
1419 let contract = offset_fit_contract(source);
1420 let stretch_kept = developability <= contract;
1421 samples = if stretch_kept {
1422 stretched
1423 } else {
1424 parameters_u
1425 .iter()
1426 .map(|&u| {
1427 parameters_v
1428 .iter()
1429 .map(|&v| Ok(extended_offsets.at(u, v, -distance).or_refuse(KernelStage::Refine, "at")?.point))
1430 .collect::<Result<Vec<_>, KernelRefusal>>()
1431 })
1432 .collect::<Result<Vec<_>, KernelRefusal>>()?
1433 };
1434 if let Ok(path) = std::env::var("BREP_OFFSET_FIT_TRACE") {
1435 use std::io::Write;
1436 let line = format!(
1437 "extension deg=({},{}) net=({},{}) d={distance:.6} back={back:.6} forward={forward:.6} \
1438 developability={developability:.3e} contract={contract:.3e} lane={} thread={} args={}\n",
1439 source.degree_u,
1440 source.degree_v,
1441 source.control_points.len(),
1442 source.control_points[0].len(),
1443 if stretch_kept { "stretch" } else { "pointwise" },
1444 std::thread::current().name().unwrap_or("-"),
1445 std::env::args().skip(1).collect::<Vec<_>>().join(" "),
1446 );
1447 if let Ok(mut file) = std::fs::OpenOptions::new().create(true).append(true).open(path) {
1448 let _ = file.write_all(line.as_bytes());
1449 }
1450 }
1451 extended_source = Some(extended);
1452 }
1453 }
1454 }
1455 let reference = extended_source.as_ref().unwrap_or(source);
1456 if !reparameterised && exact_cylinder_offsets_on() {
1462 if let Some(surface) = cylinder_offset_surface(reference, face.same_sense, distance)? {
1463 return Ok((surface, OffsetSurfaceLane::Analytic, extended_source));
1464 }
1465 }
1466 let weights = reference
1467 .control_points
1468 .iter()
1469 .map(|row| row.iter().map(|point| point.w).collect::<Vec<_>>())
1470 .collect::<Vec<_>>();
1471 let fitted = NurbsSurface::new(
1472 source.degree_u,
1473 source.degree_v,
1474 source.knots_u.clone(),
1475 source.knots_v.clone(),
1476 interpolate_tensor(
1477 &knot_u,
1478 &knot_v,
1479 ¶meters_u,
1480 ¶meters_v,
1481 &samples,
1482 &weights,
1483 )?,
1484 ).or_refuse(KernelStage::Refine, "new")?;
1485 if reparameterised {
1486 return Ok((fitted, OffsetSurfaceLane::Reparameterised, None));
1487 }
1488 let reference_offsets = OffsetEvaluator::new(
1489 "offset_surface",
1490 reference,
1491 OffsetNormal::FaceStable {
1492 same_sense: face.same_sense,
1493 },
1494 );
1495 Ok((
1496 refine_offset_fit(reference, &reference_offsets, distance, fitted)?,
1497 OffsetSurfaceLane::Fit,
1498 extended_source,
1499 ))
1500}
1501
1502
1503fn analytic_offset_apex(source: &NurbsSurface, samples: &[Vec<Vec3>], contract: f64) -> Option<(f64, Vec3)> {
1512 let Some(crate::AnalyticSurface::RuledRevolution { frame, .. }) = crate::analytic_surface::recognize(source) else {
1513 return None;
1514 };
1515 let radial = |point: Vec3| {
1516 let offset = point.sub(frame.origin);
1517 offset.sub(frame.axis.scale(offset.dot(frame.axis)))
1518 };
1519 let mut crossings = Vec::with_capacity(samples.len());
1520 for row in samples {
1521 let (near, far) = (radial(row[0]), radial(row[1]));
1522 let step = far.sub(near);
1523 let at = -near.dot(step) / step.dot(step);
1524 if !at.is_finite() {
1525 return None;
1526 }
1527 crossings.push((at, row[0].add(row[1].sub(row[0]).scale(at))));
1528 }
1529 let count = crossings.len() as f64;
1532 let at = crossings.iter().map(|(at, _)| at).sum::<f64>() / count;
1533 let first = crossings.first()?.1;
1534 let spread = crossings.iter().fold(Vec3::default(), |sum, (_, point)| sum.add(point.sub(first)));
1535 let centre = first.add(spread.scale(1.0 / count));
1536 let apex = frame.origin.add(frame.axis.scale(centre.sub(frame.origin).dot(frame.axis)));
1537 crossings
1540 .iter()
1541 .all(|(_, point)| radial(*point).length() <= contract && point.sub(apex).length() <= contract)
1542 .then_some((at, apex))
1543}
1544
1545fn extend_along_rulings(surface: &NurbsSurface, back: f64, forward: f64) -> Result<NurbsSurface, KernelRefusal> {
1552 let rows = surface
1553 .control_points
1554 .iter()
1555 .map(|row| {
1556 let step = row[1].add(row[0].scale(-1.0));
1557 vec![row[0].add(step.scale(-back)), row[1].add(step.scale(forward))]
1558 })
1559 .collect::<Vec<_>>();
1560 if rows.iter().flatten().any(|point| point.w <= 1e-12) {
1561 return Err(KernelRefusal::unsupported(KernelStage::Refine, "offset_ruled_extension_weight", format!(
1562 "offset_surface: extending a ruled face by ({back:.6}, {forward:.6}) of its rulings \
1563 carries a weight through zero; the extended face is not this surface"
1564 )));
1565 }
1566 NurbsSurface::new(surface.degree_u, 1, surface.knots_u.clone(), surface.knots_v.clone(), rows)
1567 .or_refuse(KernelStage::Refine, "new")
1568}
1569
1570fn offset_fit_contract(source: &NurbsSurface) -> f64 {
1573 let scale = crate::model_scale(
1574 source
1575 .control_points
1576 .iter()
1577 .flatten()
1578 .filter_map(|point| point.point().ok()),
1579 );
1580 crate::KernelTolerances::for_scale(scale, 1e-7).intersection_fit
1581}
1582
1583const OFFSET_FIT_REFINEMENTS: usize = 6;
1585
1586const OFFSET_FIT_MAX_CONTROLS_SEPARABLE: usize = 16_384;
1589const OFFSET_FIT_MAX_CONTROLS_TENSOR: usize = 900;
1590
1591#[derive(Clone, Debug)]
1596struct OffsetFitDeviation {
1597 along_u: f64,
1598 along_v: f64,
1599 between: f64,
1600 u_sites: Vec<(f64, f64)>,
1601 v_sites: Vec<(f64, f64)>,
1602 between_uv: (f64, f64),
1603}
1604
1605impl OffsetFitDeviation {
1606 fn worst(&self) -> f64 {
1607 self.along_u.max(self.along_v).max(self.between)
1608 }
1609
1610 fn refinement_sites(&self, bar: f64) -> (Vec<f64>, Vec<f64>) {
1611 let mut u = self.u_sites.iter().filter(|(_, miss)| *miss > bar)
1612 .map(|(parameter, _)| *parameter).collect::<Vec<_>>();
1613 let mut v = self.v_sites.iter().filter(|(_, miss)| *miss > bar)
1614 .map(|(parameter, _)| *parameter).collect::<Vec<_>>();
1615 if u.is_empty() && v.is_empty() && self.between > bar {
1616 u.push(self.between_uv.0);
1617 v.push(self.between_uv.1);
1618 }
1619 (u, v)
1620 }
1621}
1622
1623fn greville_midpoints(parameters: &[f64]) -> Vec<f64> {
1624 parameters
1625 .windows(2)
1626 .filter(|pair| pair[1] - pair[0] > 1e-12)
1627 .map(|pair| 0.5 * (pair[0] + pair[1]))
1628 .collect()
1629}
1630
1631fn offset_fit_deviation(
1632 fitted: &NurbsSurface,
1633 evaluator: &OffsetEvaluator,
1634 distance: f64,
1635) -> Result<OffsetFitDeviation, KernelRefusal> {
1636 let parameters_u = greville_parameters(&KnotVector::new(fitted.knots_u.clone(), fitted.degree_u).or_refuse(KernelStage::Refine, "new")?);
1637 let parameters_v = greville_parameters(&KnotVector::new(fitted.knots_v.clone(), fitted.degree_v).or_refuse(KernelStage::Refine, "new")?);
1638 let (middle_u, middle_v) = (greville_midpoints(¶meters_u), greville_midpoints(¶meters_v));
1639 let residual_locus = std::env::var("BREP_OFFSET_FIT_RESIDUAL").as_deref() != Ok("0");
1640 let gap = |u: f64, v: f64| -> Result<f64, KernelRefusal> {
1641 Ok(fitted.evaluate(u, v).or_refuse(KernelStage::Refine, "evaluate")?.sub(evaluator.at(u, v, -distance).or_refuse(KernelStage::Refine, "at")?.point).length())
1642 };
1643 let mut deviation = OffsetFitDeviation {
1644 along_u: 0.0,
1645 along_v: 0.0,
1646 between: 0.0,
1647 u_sites: Vec::new(),
1648 v_sites: if residual_locus { middle_v.iter().map(|&v| (v, 0.0)).collect() } else { Vec::new() },
1649 between_uv: (0.0, 0.0),
1650 };
1651 for &u in &middle_u {
1652 let mut along = 0.0f64;
1653 for &v in ¶meters_v {
1654 let miss = gap(u, v)?;
1655 along = along.max(miss);
1656 deviation.along_u = deviation.along_u.max(miss);
1657 }
1658 if residual_locus { deviation.u_sites.push((u, along)); }
1659 for &v in &middle_v {
1660 let miss = gap(u, v)?;
1661 if miss > deviation.between { deviation.between_uv = (u, v); }
1662 deviation.between = deviation.between.max(miss);
1663 }
1664 }
1665 for &u in ¶meters_u {
1666 for (index, &v) in middle_v.iter().enumerate() {
1667 let miss = gap(u, v)?;
1668 deviation.along_v = deviation.along_v.max(miss);
1669 if residual_locus { deviation.v_sites[index].1 = deviation.v_sites[index].1.max(miss); }
1670 }
1671 }
1672 Ok(deviation)
1673}
1674
1675fn raise_linear_directions(
1685 surface: &NurbsSurface,
1686 in_u: bool,
1687 in_v: bool,
1688) -> Result<Option<NurbsSurface>, KernelRefusal> {
1689 fn raise(knots: &[f64], row: &[Vec4]) -> Option<(Vec<f64>, Vec<Vec4>)> {
1690 let count = row.len();
1692 if knots.len() != count + 2 {
1693 return None;
1694 }
1695 let breaks = &knots[1..=count];
1696 if breaks.windows(2).any(|pair| pair[1] - pair[0] <= 1e-12) {
1697 return None;
1698 }
1699 let mut raised_knots = vec![breaks[0]; 4];
1700 for &interior in &breaks[1..count - 1] {
1701 raised_knots.extend([interior; 3]);
1702 }
1703 raised_knots.extend([breaks[count - 1]; 4]);
1704 let mut points = Vec::with_capacity(3 * (count - 1) + 1);
1705 for pair in row.windows(2) {
1706 let step = pair[1].add(pair[0].scale(-1.0));
1707 points.push(pair[0]);
1708 points.push(pair[0].add(step.scale(1.0 / 3.0)));
1709 points.push(pair[0].add(step.scale(2.0 / 3.0)));
1710 }
1711 points.push(row[count - 1]);
1712 Some((raised_knots, points))
1713 }
1714 let mut knots_u = surface.knots_u.clone();
1715 let mut knots_v = surface.knots_v.clone();
1716 let mut degree_u = surface.degree_u;
1717 let mut degree_v = surface.degree_v;
1718 let mut net = surface.control_points.clone();
1719 if in_v {
1720 if degree_v != 1 {
1721 return Ok(None);
1722 }
1723 let mut rows = Vec::with_capacity(net.len());
1724 for row in &net {
1725 let Some((knots, points)) = raise(&surface.knots_v, row) else {
1726 return Ok(None);
1727 };
1728 knots_v = knots;
1729 rows.push(points);
1730 }
1731 net = rows;
1732 degree_v = 3;
1733 }
1734 if in_u {
1735 if degree_u != 1 {
1736 return Ok(None);
1737 }
1738 let count_v = net[0].len();
1739 let mut columns = Vec::with_capacity(count_v);
1740 for column in 0..count_v {
1741 let row = net.iter().map(|row| row[column]).collect::<Vec<_>>();
1742 let Some((knots, points)) = raise(&surface.knots_u, &row) else {
1743 return Ok(None);
1744 };
1745 knots_u = knots;
1746 columns.push(points);
1747 }
1748 let count_u = columns[0].len();
1749 net = (0..count_u)
1750 .map(|row| columns.iter().map(|column| column[row]).collect())
1751 .collect();
1752 degree_u = 3;
1753 }
1754 Ok(Some(NurbsSurface::new(degree_u, degree_v, knots_u, knots_v, net).or_refuse(KernelStage::Refine, "new")?))
1755}
1756
1757fn halve_knot_spans(surface: &NurbsSurface, in_u: bool, in_v: bool) -> Result<NurbsSurface, KernelRefusal> {
1761 fn midpoints(knots: &[f64], degree: usize) -> Vec<f64> {
1762 let last = knots.len() - 1 - degree;
1763 knots[degree..=last]
1764 .windows(2)
1765 .filter(|pair| pair[1] - pair[0] > 1e-12)
1766 .map(|pair| 0.5 * (pair[0] + pair[1]))
1767 .collect()
1768 }
1769 insert_offset_fit_knots(surface,
1770 &if in_u { midpoints(&surface.knots_u, surface.degree_u) } else { Vec::new() },
1771 &if in_v { midpoints(&surface.knots_v, surface.degree_v) } else { Vec::new() })
1772}
1773
1774fn insert_offset_fit_knots(surface: &NurbsSurface, u: &[f64], v: &[f64]) -> Result<NurbsSurface, KernelRefusal> {
1779 let refine = |degree: usize, knots: &[f64], net: Vec<Vec<Vec4>>, inserted: &[f64]| -> Result<(Vec<f64>, Vec<Vec<Vec4>>), KernelRefusal> {
1780 let mut inserted = inserted.to_vec();
1781 inserted.sort_by(f64::total_cmp);
1782 inserted.dedup_by(|a, b| (*a - *b).abs() <= 1e-12);
1783 inserted.retain(|parameter| knots.iter().filter(|knot| (**knot - *parameter).abs() <= 1e-12).count() < degree);
1784 let mut refined_knots = knots.to_vec();
1785 let mut rows = Vec::with_capacity(net.len());
1786 for row in net {
1787 let mut curve = NurbsCurve::new(degree, knots.to_vec(), row).or_refuse(KernelStage::Refine, "new")?;
1788 for ¶meter in &inserted {
1789 curve = curve.insert_knot(parameter, 1).or_refuse(KernelStage::Refine, "insert_knot")?;
1790 }
1791 refined_knots = curve.knots.clone();
1792 rows.push(curve.control_points);
1793 }
1794 Ok((refined_knots, rows))
1795 };
1796 let mut knots_u = surface.knots_u.clone();
1797 let mut knots_v = surface.knots_v.clone();
1798 let mut net = surface.control_points.clone();
1799 if !v.is_empty() {
1800 let (knots, rows) = refine(surface.degree_v, &knots_v, net, v)?;
1801 knots_v = knots;
1802 net = rows;
1803 }
1804 if !u.is_empty() {
1805 let count_v = net[0].len();
1807 let columns = (0..count_v)
1808 .map(|column| net.iter().map(|row| row[column]).collect::<Vec<_>>())
1809 .collect::<Vec<_>>();
1810 let (knots, refined) = refine(surface.degree_u, &knots_u, columns, u)?;
1811 knots_u = knots;
1812 let count_u = refined[0].len();
1813 net = (0..count_u)
1814 .map(|row| refined.iter().map(|column| column[row]).collect())
1815 .collect();
1816 }
1817 NurbsSurface::new(surface.degree_u, surface.degree_v, knots_u, knots_v, net).or_refuse(KernelStage::Refine, "new")
1818}
1819
1820fn refine_offset_fit(
1856 source: &NurbsSurface,
1857 evaluator: &OffsetEvaluator,
1858 distance: f64,
1859 fitted: NurbsSurface,
1860) -> Result<NurbsSurface, KernelRefusal> {
1861 let scale = crate::model_scale(
1862 source
1863 .control_points
1864 .iter()
1865 .flatten()
1866 .filter_map(|point| point.point().ok()),
1867 );
1868 let bar = crate::KernelTolerances::for_scale(scale, 1e-7).intersection_fit;
1869 let trace = std::env::var("BREP_OFFSET_FIT_TRACE").ok();
1870 let started = web_time::Instant::now();
1871 let enabled = std::env::var("BREP_OFFSET_FIT_REFINE").as_deref() != Ok("0");
1872 let Ok(initial) = offset_fit_deviation(&fitted, evaluator, distance) else {
1873 return Ok(fitted);
1874 };
1875 let mut best = fitted;
1876 let mut best_deviation = initial.clone();
1877 let mut refined_source = source.clone();
1878 let mut rounds = 0usize;
1879 let mut residual_mode = false;
1880 let mut stop = "under bar";
1881 if enabled {
1882 while best_deviation.worst() > bar {
1883 if rounds == OFFSET_FIT_REFINEMENTS {
1884 stop = "refinement limit";
1885 break;
1886 }
1887 let (along_u, along_v) = (best_deviation.along_u > bar, best_deviation.along_v > bar);
1888 let (in_u, in_v) = if along_u || along_v {
1889 (along_u, along_v)
1890 } else {
1891 (true, true)
1892 };
1893 let (raise_u, raise_v) = (in_u && refined_source.degree_u == 1, in_v && refined_source.degree_v == 1);
1894 let raised = if raise_u || raise_v {
1895 raise_linear_directions(&refined_source, raise_u, raise_v)?
1896 } else {
1897 None
1898 };
1899 let (halve_u, halve_v) = match raised {
1900 Some(_) => (in_u && !raise_u, in_v && !raise_v),
1901 None => (in_u, in_v),
1902 };
1903 let raised = raised.unwrap_or_else(|| refined_source.clone());
1904 let candidate_source = if halve_u || halve_v {
1905 if residual_mode {
1906 let (u, v) = best_deviation.refinement_sites(bar);
1907 insert_offset_fit_knots(&raised,
1908 if halve_u { &u } else { &[] }, if halve_v { &v } else { &[] })?
1909 } else {
1910 halve_knot_spans(&raised, halve_u, halve_v)?
1911 }
1912 } else {
1913 raised
1914 };
1915 let weights = candidate_source
1916 .control_points
1917 .iter()
1918 .map(|row| row.iter().map(|point| point.w).collect::<Vec<_>>())
1919 .collect::<Vec<_>>();
1920 let controls = weights.len() * weights[0].len();
1921 let ceiling = if separable_weights(&weights).is_some() {
1922 OFFSET_FIT_MAX_CONTROLS_SEPARABLE
1923 } else {
1924 OFFSET_FIT_MAX_CONTROLS_TENSOR
1925 };
1926 if controls > ceiling {
1927 stop = "net ceiling";
1928 break;
1929 }
1930 let knot_u = KnotVector::new(candidate_source.knots_u.clone(), candidate_source.degree_u).or_refuse(KernelStage::Refine, "new")?;
1931 let knot_v = KnotVector::new(candidate_source.knots_v.clone(), candidate_source.degree_v).or_refuse(KernelStage::Refine, "new")?;
1932 let parameters_u = greville_parameters(&knot_u);
1933 let parameters_v = greville_parameters(&knot_v);
1934 let samples = parameters_u
1935 .iter()
1936 .map(|&u| {
1937 parameters_v
1938 .iter()
1939 .map(|&v| Ok(evaluator.at(u, v, -distance).or_refuse(KernelStage::Refine, "at")?.point))
1940 .collect::<Result<Vec<_>, KernelRefusal>>()
1941 })
1942 .collect::<Result<Vec<_>, KernelRefusal>>();
1943 let Ok(samples) = samples else {
1944 stop = "unevaluable sample";
1945 break;
1946 };
1947 let candidate = NurbsSurface::new(
1948 candidate_source.degree_u,
1949 candidate_source.degree_v,
1950 candidate_source.knots_u.clone(),
1951 candidate_source.knots_v.clone(),
1952 interpolate_tensor(&knot_u, &knot_v, ¶meters_u, ¶meters_v, &samples, &weights)?,
1953 ).or_refuse(KernelStage::Refine, "new")?;
1954 let Ok(deviation) = offset_fit_deviation(&candidate, evaluator, distance) else {
1955 stop = "unmeasurable round";
1956 break;
1957 };
1958 rounds += 1;
1959 if deviation.worst() >= best_deviation.worst() {
1960 let first_quadratic_split = rounds == 1
1967 && ((halve_u && source.degree_u == 2 && source.knots_u.len() == 6)
1968 || (halve_v && source.degree_v == 2 && source.knots_v.len() == 6));
1969 if first_quadratic_split {
1970 refined_source = candidate_source;
1971 continue;
1972 }
1973 if !residual_mode && best_deviation.worst() > offset_construction_band(scale)
1978 && std::env::var("BREP_OFFSET_FIT_RESIDUAL").as_deref() != Ok("0")
1979 {
1980 residual_mode = true;
1981 continue;
1982 }
1983 stop = "stopped improving";
1984 break;
1985 }
1986 best = candidate;
1987 best_deviation = deviation;
1988 refined_source = candidate_source;
1989 }
1990 } else if best_deviation.worst() > bar {
1991 stop = "refinement disabled";
1992 }
1993 let band = offset_construction_band(scale);
1998 let refused = enabled && best_deviation.worst() > band;
1999 if let Some(path) = trace {
2000 use std::io::Write;
2001 let caller = std::env::args().skip(1).collect::<Vec<_>>().join(" ");
2002 let thread = std::thread::current().name().unwrap_or("-").to_string();
2003 let line = format!(
2004 "fit deg=({},{}) net=({},{})->({},{}) d={distance:.6} scale={scale:.4} bar={bar:.3e} \
2005 initial=(u {:.3e}, v {:.3e}, uv {:.3e}) final={:.3e} rounds={rounds} stop={stop} \
2006 refused={refused} seconds={:.4} thread={thread} args={caller}\n",
2007 source.degree_u,
2008 source.degree_v,
2009 source.control_points.len(),
2010 source.control_points[0].len(),
2011 best.control_points.len(),
2012 best.control_points[0].len(),
2013 initial.along_u,
2014 initial.along_v,
2015 initial.between,
2016 best_deviation.worst(),
2017 started.elapsed().as_secs_f64(),
2018 );
2019 if let Ok(mut file) = std::fs::OpenOptions::new().create(true).append(true).open(path) {
2020 let _ = file.write_all(line.as_bytes());
2021 }
2022 }
2023 if refused {
2024 return Err(KernelRefusal::non_convergence(KernelStage::Refine, "offset_carrier_fit", format!(
2025 "offset_surface: the fitted offset carrier stays {:.3e} off its pointwise offset at \
2026 distance {distance} after {rounds} refinement round(s) ({stop}), past the offset \
2027 construction band {band:.3e}",
2028 best_deviation.worst()
2029 )));
2030 }
2031 Ok(best)
2032}
2033
2034pub(crate) fn unify_offset_sheet_bases(
2044 first: &NurbsSurface,
2045 second: &NurbsSurface,
2046) -> Result<(NurbsSurface, NurbsSurface), KernelRefusal> {
2047 fn raise_to(surface: &NurbsSurface, degree_u: usize, degree_v: usize) -> Result<NurbsSurface, KernelRefusal> {
2048 let raise_u = surface.degree_u == 1 && degree_u == 3;
2049 let raise_v = surface.degree_v == 1 && degree_v == 3;
2050 if !raise_u && !raise_v {
2051 return Ok(surface.clone());
2052 }
2053 raise_linear_directions(surface, raise_u, raise_v)?
2054 .ok_or_else(|| {
2055 KernelRefusal::internal(
2056 KernelStage::Refine,
2057 "offset_raise_linear",
2058 "offset sheets: a linear direction could not be raised",
2059 )
2060 })
2061 }
2062 let degree_u = first.degree_u.max(second.degree_u);
2063 let degree_v = first.degree_v.max(second.degree_v);
2064 let mut first = raise_to(first, degree_u, degree_v)?;
2065 let mut second = raise_to(second, degree_u, degree_v)?;
2066 if first.degree_u != second.degree_u || first.degree_v != second.degree_v {
2067 return Err(KernelRefusal::internal(KernelStage::Refine, "offset_common_basis", format!(
2068 "offset sheets: degrees ({},{}) and ({},{}) have no common basis",
2069 first.degree_u, first.degree_v, second.degree_u, second.degree_v
2070 )));
2071 }
2072 fn missing(from: &[f64], into: &[f64]) -> Vec<f64> {
2074 let mut extra = Vec::new();
2075 let mut index = 0usize;
2076 for &knot in from {
2077 while index < into.len() && into[index] < knot - 1e-12 {
2078 index += 1;
2079 }
2080 if index < into.len() && (into[index] - knot).abs() <= 1e-12 {
2081 index += 1;
2082 } else {
2083 extra.push(knot);
2084 }
2085 }
2086 extra
2087 }
2088 fn insert(surface: &NurbsSurface, knots: &[f64], along_u: bool) -> Result<NurbsSurface, KernelRefusal> {
2089 if knots.is_empty() {
2090 return Ok(surface.clone());
2091 }
2092 let (degree, vector) = if along_u {
2093 (surface.degree_u, &surface.knots_u)
2094 } else {
2095 (surface.degree_v, &surface.knots_v)
2096 };
2097 let lines = if along_u {
2098 (0..surface.control_points[0].len())
2099 .map(|column| surface.control_points.iter().map(|row| row[column]).collect::<Vec<_>>())
2100 .collect::<Vec<_>>()
2101 } else {
2102 surface.control_points.clone()
2103 };
2104 let mut refined_knots = vector.clone();
2105 let mut refined = Vec::with_capacity(lines.len());
2106 for line in lines {
2107 let mut curve = NurbsCurve::new(degree, vector.clone(), line).or_refuse(KernelStage::Refine, "new")?;
2108 for &knot in knots {
2109 curve = curve.insert_knot(knot, 1).or_refuse(KernelStage::Refine, "insert_knot")?;
2110 }
2111 refined_knots = curve.knots.clone();
2112 refined.push(curve.control_points);
2113 }
2114 let net = if along_u {
2115 (0..refined[0].len())
2116 .map(|row| refined.iter().map(|column| column[row]).collect())
2117 .collect()
2118 } else {
2119 refined
2120 };
2121 let (knots_u, knots_v) = if along_u {
2122 (refined_knots, surface.knots_v.clone())
2123 } else {
2124 (surface.knots_u.clone(), refined_knots)
2125 };
2126 NurbsSurface::new(surface.degree_u, surface.degree_v, knots_u, knots_v, net).or_refuse(KernelStage::Refine, "new")
2127 }
2128 let (to_first_u, to_second_u) = (
2129 missing(&second.knots_u, &first.knots_u),
2130 missing(&first.knots_u, &second.knots_u),
2131 );
2132 first = insert(&first, &to_first_u, true)?;
2133 second = insert(&second, &to_second_u, true)?;
2134 let (to_first_v, to_second_v) = (
2135 missing(&second.knots_v, &first.knots_v),
2136 missing(&first.knots_v, &second.knots_v),
2137 );
2138 first = insert(&first, &to_first_v, false)?;
2139 second = insert(&second, &to_second_v, false)?;
2140 Ok((first, second))
2141}
2142
2143fn carrier_edge_curve(
2165 surface: &NurbsSurface,
2166 pcurve: &NurbsCurve,
2167 points: &[Vec3],
2168 parameters: &[f64],
2169 fit_tolerance: f64,
2170) -> Result<(NurbsCurve, f64, f64), KernelRefusal> {
2171 if affine_image_trusted() && surface.is_affine().or_refuse(KernelStage::Refine, "is_affine")? {
2179 let [q0, q1] = pcurve.domain().or_refuse(KernelStage::Refine, "domain")?;
2180 if (q1 - q0).is_finite() && (q1 - q0).abs() > 0.0 {
2181 let curve = crate::image_curve::affine_image_curve(surface, pcurve).or_refuse(KernelStage::Refine, "affine_image_curve")?;
2182 return Ok((curve, q0, q1));
2183 }
2184 }
2185 let image = if env_read!("BREP_CARRIER_POLYLINE").as_deref() == Some("1") {
2186 Err("BREP_CARRIER_POLYLINE set".to_string())
2187 } else {
2188 crate::image_curve::image_curve(surface, pcurve, fit_tolerance, "offset_face_carrier")
2189 };
2190 match image {
2191 Ok(image) if image.t0 <= image.t1 => Ok((image.curve, image.t0, image.t1)),
2192 Ok(image) => {
2193 let [start, end] = image.curve.domain().or_refuse(KernelStage::Refine, "domain")?;
2196 let curve = image.curve.reversed().or_refuse(KernelStage::Refine, "reversed")?;
2197 Ok((curve, start + end - image.t0, start + end - image.t1))
2198 }
2199 Err(_) => {
2200 let curve = interpolate_curve(points, 1, parameters).or_refuse(KernelStage::Refine, "interpolate_curve")?;
2201 let [t0, t1] = curve.domain().or_refuse(KernelStage::Refine, "domain")?;
2202 Ok((curve, t0, t1))
2203 }
2204 }
2205}
2206
2207fn affine_image_trusted() -> bool {
2208 switch!("BREP_CARRIER_AFFINE_IMAGE", true)
2209}
2210
2211
2212fn lazy_carrier_trace(
2220 surface: &NurbsSurface,
2221 pcurve: &NurbsCurve,
2222 collapse_tolerance: f64,
2223 fit_tolerance: f64,
2224) -> Option<(Vec<Vec3>, (NurbsCurve, f64, f64))> {
2225 if !switch!("BREP_OFFSET_LAZY_CARRIER_TRACE", true) {
2226 return None;
2227 }
2228 if pcurve.degree == 1 && pcurve.control_points.len() == 2 {
2231 let (a, b) = (pcurve.control_points[0], pcurve.control_points[1]);
2232 if (surface.degree_u <= 1 && surface.degree_v <= 1)
2233 || (a.w == b.w && a.y == b.y && surface.degree_u <= 1)
2234 || (a.w == b.w && a.x == b.x && surface.degree_v <= 1)
2235 {
2236 return None;
2237 }
2238 }
2239 fn knots_ok(knots: &[f64], degree: usize, count: usize) -> bool {
2240 degree <= 3 && count <= 64
2241 && KnotVector::new(knots.to_vec(), degree).ok().is_some_and(|k| k.control_point_count() == count)
2242 && knots.iter().all(|k| k.is_finite() && k.abs() <= 1e6)
2243 && knots.windows(2).all(|k| k[0] == k[1] || k[1] - k[0] >= 1e-6)
2244 }
2245 let bounded = |p: &Vec4| (1e-3..=1e3).contains(&p.w)
2246 && [p.x, p.y, p.z].iter().all(|x| x.is_finite() && x.abs() <= 1e12);
2247 let columns = surface.control_points.first()?.len();
2248 if !knots_ok(&surface.knots_u, surface.degree_u, surface.control_points.len())
2249 || !knots_ok(&surface.knots_v, surface.degree_v, columns)
2250 || surface.control_points.iter().any(|row| row.len() != columns || row.iter().any(|p| !bounded(p)))
2251 || !knots_ok(&pcurve.knots, pcurve.degree, pcurve.control_points.len())
2252 || pcurve.control_points.iter().any(|p| !bounded(p))
2253 {
2254 return None;
2255 }
2256 let ([u0, u1], [v0, v1]) = (surface.domain_u().ok()?, surface.domain_v().ok()?);
2257 let uv = pcurve.control_points.iter().map(|p| p.point().ok()).collect::<Option<Vec<_>>>()?;
2258 if uv.iter().any(|p| p.x < u0 || p.x > u1 || p.y < v0 || p.y > v1) {
2259 return None;
2260 }
2261 if !surface.is_affine().ok()? && !uv.iter().all(|p| p.x == uv[0].x) && !uv.iter().all(|p| p.y == uv[0].y) {
2263 return None;
2264 }
2265 let [start, end] = pcurve.domain().ok()?;
2266 let evaluate = |fraction: f64| {
2267 let uv = pcurve.evaluate(start + (end - start) * fraction).ok()?;
2268 surface.evaluate(uv.x, uv.y).ok()
2269 };
2270 let first = evaluate(0.0)?;
2271 let last = evaluate(1.0)?;
2272 let samples = [evaluate(0.25)?, evaluate(0.5)?, evaluate(0.75)?];
2273 let deviation = samples.iter().enumerate().map(|(index, point)| {
2274 point.sub(first.add(last.sub(first).scale((index + 1) as f64 * 0.25))).length()
2275 }).fold(0.0, f64::max);
2276 if last.sub(first).length() <= collapse_tolerance
2277 && !(deviation > 5e-4 && samples[1].sub(first).length() > collapse_tolerance)
2278 {
2279 return None;
2280 }
2281 let image = carrier_edge_curve(surface, pcurve, &[], &[], fit_tolerance).ok()?;
2284 Some((vec![first, samples[1], last], image))
2285}
2286
2287fn mapped_pcurve_polyline(
2288 surface: &NurbsSurface,
2289 pcurve: &NurbsCurve,
2290 degenerate: bool,
2291) -> Result<(Vec<Vec3>, Vec<f64>), KernelRefusal> {
2292 let [start, end] = pcurve.domain().or_refuse(KernelStage::Refine, "domain")?;
2293 let evaluate = |fraction: f64| -> Result<Vec3, KernelRefusal> {
2294 let uv = pcurve.evaluate(start + (end - start) * fraction).or_refuse(KernelStage::Refine, "evaluate")?;
2295 surface.evaluate(uv.x, uv.y).or_refuse(KernelStage::Refine, "evaluate")
2296 };
2297 let first = evaluate(0.0)?;
2298 let last = evaluate(1.0)?;
2299 if degenerate {
2300 return Ok((vec![first, last], vec![0.0, 1.0]));
2301 }
2302 fn append(
2303 evaluate: &impl Fn(f64) -> Result<Vec3, KernelRefusal>,
2304 a_fraction: f64,
2305 a: Vec3,
2306 b_fraction: f64,
2307 b: Vec3,
2308 depth: usize,
2309 parameters: &mut Vec<f64>,
2310 points: &mut Vec<Vec3>,
2311 ) -> Result<(), KernelRefusal> {
2312 let fractions =
2313 [0.25, 0.5, 0.75].map(|local| a_fraction + (b_fraction - a_fraction) * local);
2314 let samples = fractions
2315 .map(evaluate)
2316 .into_iter()
2317 .collect::<Result<Vec<_>, KernelRefusal>>()?;
2318 let deviation = samples
2319 .iter()
2320 .enumerate()
2321 .map(|(index, point)| {
2322 point
2323 .sub(a.add(b.sub(a).scale((index + 1) as f64 * 0.25)))
2324 .length()
2325 })
2326 .fold(0.0, f64::max);
2327 if deviation <= 5e-4 || depth >= 10 {
2328 parameters.push(b_fraction);
2329 points.push(b);
2330 return Ok(());
2331 }
2332 append(
2333 evaluate,
2334 a_fraction,
2335 a,
2336 fractions[1],
2337 samples[1],
2338 depth + 1,
2339 parameters,
2340 points,
2341 )?;
2342 append(
2343 evaluate,
2344 fractions[1],
2345 samples[1],
2346 b_fraction,
2347 b,
2348 depth + 1,
2349 parameters,
2350 points,
2351 )
2352 }
2353 let mut parameters = vec![0.0];
2354 let mut points = vec![first];
2355 append(
2356 &evaluate,
2357 0.0,
2358 first,
2359 1.0,
2360 last,
2361 0,
2362 &mut parameters,
2363 &mut points,
2364 )?;
2365 Ok((points, parameters))
2366}
2367
2368#[derive(Clone, Debug)]
2382pub struct CarrierDeviation {
2383 pub band: f64,
2386 pub lane: OffsetSurfaceLane,
2388 pub surface: Option<MeasuredTolerance>,
2390 pub edges: Vec<(u64, MeasuredTolerance)>,
2395 pub vertices: Vec<(u64, f64)>,
2399}
2400
2401impl CarrierDeviation {
2402 pub fn worst(&self) -> Option<MeasuredTolerance> {
2405 MeasuredTolerance::worst(
2406 self.surface
2407 .into_iter()
2408 .chain(self.edges.iter().map(|(_, measured)| *measured))
2409 .chain(
2410 self.vertices
2411 .iter()
2412 .map(|(_, gap)| MeasuredTolerance::new(*gap, self.band)),
2413 ),
2414 )
2415 }
2416
2417 pub fn exceedances(&self) -> Vec<String> {
2420 let mut out = Vec::new();
2421 if let Some(surface) = self.surface {
2422 if surface.exceeds_band() {
2423 out.push(format!("carrier surface fit {}", surface.describe()));
2424 }
2425 }
2426 for (id, measured) in &self.edges {
2427 if measured.exceeds_band() {
2428 out.push(format!("edge {id} {}", measured.describe()));
2429 }
2430 }
2431 for (id, gap) in &self.vertices {
2432 let measured = MeasuredTolerance::new(*gap, self.band);
2433 if measured.exceeds_band() {
2434 out.push(format!("vertex {id} {}", measured.describe()));
2435 }
2436 }
2437 out
2438 }
2439}
2440
2441#[derive(Clone, Debug, Serialize)]
2442pub struct OffsetFaceCarrier {
2443 pub vertices: Vec<VertexRecord>,
2444 pub edges: Vec<EdgeRecord>,
2445 pub face: FaceRecord,
2446 #[serde(skip)]
2454 pub deviation: Option<CarrierDeviation>,
2455 #[serde(skip)]
2459 pub lane: OffsetSurfaceLane,
2460}
2461
2462fn claim_vertex_image(
2473 source_id: u64,
2474 point: Vec3,
2475 split: f64,
2476 vertex_images: &mut HashMap<u64, Vec<u64>>,
2477 vertices: &mut Vec<VertexRecord>,
2478 next_id: &mut u64,
2479) -> u64 {
2480 if let Some(ids) = vertex_images.get(&source_id) {
2481 let near = ids.iter().copied().find(|id| {
2482 vertices
2483 .iter()
2484 .find(|vertex| vertex.id == *id)
2485 .is_some_and(|vertex| vertex.point.sub(point).length() <= split)
2486 });
2487 if let Some(id) = near {
2488 return id;
2489 }
2490 }
2491 let id = *next_id;
2492 *next_id += 1;
2493 vertices.push(VertexRecord { id, point });
2494 vertex_images.entry(source_id).or_default().push(id);
2495 id
2496}
2497
2498pub fn offset_face_carrier(
2499 solid: &BrepSolid,
2500 face_id: u64,
2501 distance: f64,
2502 planar_extension: f64,
2503) -> Result<OffsetFaceCarrier, KernelRefusal> {
2504 offset_face_carrier_impl(
2505 solid,
2506 face_id,
2507 distance,
2508 &CarrierExtension::uniform(planar_extension),
2509 false,
2510 )
2511}
2512
2513fn pinch_side_by_source_enabled() -> bool {
2528 switch!("BREP_OFFSET_PINCH_SIDE_BY_SOURCE", true)
2529}
2530
2531fn pinch_side_by_source(
2532 source: &NurbsSurface,
2533 parameters_u: &[f64],
2534 parameters_v: &[f64],
2535 samples: &[Vec<Vec3>],
2536 near_centroid: Vec3,
2537 far_centroid: Vec3,
2538) -> Result<Option<bool>, KernelRefusal> {
2539 if !pinch_side_by_source_enabled() || parameters_v.len() != 2 {
2540 return Ok(None);
2541 }
2542 let mut source_rows = [Vec::new(), Vec::new()];
2543 for &u in parameters_u {
2544 for (end, &v) in parameters_v.iter().enumerate() {
2545 source_rows[end].push(source.evaluate(u, v).or_refuse(KernelStage::Refine, "evaluate")?);
2546 }
2547 }
2548 let centroid = |row: &[Vec3]| row.iter().fold(Vec3::default(), |sum, p| sum.add(*p)).scale(1.0 / row.len() as f64);
2549 let spread = |row: &[Vec3]| {
2550 let middle = centroid(row);
2551 row.iter().map(|p| p.sub(middle).length()).fold(0.0f64, f64::max)
2552 };
2553 let reference = if spread(&source_rows[0]) >= spread(&source_rows[1]) { 0 } else { 1 };
2554 let reference_centroid = centroid(&source_rows[reference]);
2555 let (mut near_sign, mut far_sign) = (0.0f64, 0.0f64);
2556 for (k, row) in samples.iter().enumerate() {
2557 let radial = source_rows[reference][k].sub(reference_centroid);
2558 near_sign += row[0].sub(near_centroid).dot(radial);
2559 far_sign += row[1].sub(far_centroid).dot(radial);
2560 }
2561 Ok(match (near_sign > 0.0, far_sign > 0.0) {
2562 (true, false) => Some(true),
2563 (false, true) => Some(false),
2564 _ => None,
2565 })
2566}
2567
2568pub fn offset_face_carrier_sided(
2569 solid: &BrepSolid,
2570 face_id: u64,
2571 distance: f64,
2572 extension: &CarrierExtension,
2573) -> Result<OffsetFaceCarrier, KernelRefusal> {
2574 offset_face_carrier_impl(solid, face_id, distance, extension, false)
2575}
2576
2577pub fn offset_face_carrier_measured(
2597 solid: &BrepSolid,
2598 face_id: u64,
2599 distance: f64,
2600 planar_extension: f64,
2601) -> Result<OffsetFaceCarrier, KernelRefusal> {
2602 offset_face_carrier_impl(
2603 solid,
2604 face_id,
2605 distance,
2606 &CarrierExtension::uniform(planar_extension),
2607 true,
2608 )
2609}
2610
2611fn measure_carrier(
2622 surface: &NurbsSurface,
2623 vertices: &[VertexRecord],
2624 edges: &[EdgeRecord],
2625 loops: &[LoopRecord],
2626 lane: OffsetSurfaceLane,
2627 surface_fit: Option<MeasuredTolerance>,
2628 band: f64,
2629) -> Result<CarrierDeviation, KernelRefusal> {
2630 let edge_by_id: HashMap<u64, &EdgeRecord> = edges.iter().map(|edge| (edge.id, edge)).collect();
2631 let mut per_edge: HashMap<u64, MeasuredTolerance> = HashMap::default();
2635 for loop_record in loops {
2636 for coedge in &loop_record.coedges {
2637 let Some(edge) = edge_by_id.get(&coedge.edge_id) else {
2638 continue;
2639 };
2640 let measured = measure_edge_against_pcurve_image(
2641 surface,
2642 &coedge.pcurve,
2643 edge,
2644 coedge.forward,
2645 band,
2646 )?;
2647 per_edge
2648 .entry(edge.id)
2649 .and_modify(|existing| *existing = existing.worse_of(measured))
2650 .or_insert(measured);
2651 }
2652 }
2653
2654 let mut measured_edges: Vec<(u64, MeasuredTolerance)> = per_edge.into_iter().collect();
2655 measured_edges.sort_by_key(|(id, _)| *id);
2656 let deviation_of: HashMap<u64, f64> = measured_edges
2657 .iter()
2658 .map(|(id, measured)| (*id, measured.deviation()))
2659 .collect();
2660
2661 let mut ends_at: HashMap<u64, Vec<(&EdgeRecord, f64)>> = HashMap::default();
2665 for edge in edges {
2666 ends_at
2667 .entry(edge.start_vertex_id)
2668 .or_default()
2669 .push((edge, edge.t0));
2670 ends_at
2671 .entry(edge.end_vertex_id)
2672 .or_default()
2673 .push((edge, edge.t1));
2674 }
2675
2676 let mut measured_vertices = Vec::with_capacity(vertices.len());
2677 for vertex in vertices {
2678 let mut gaps = Vec::new();
2679 let mut incident = Vec::new();
2680 for (edge, parameter) in ends_at.get(&vertex.id).into_iter().flatten() {
2681 gaps.push(vertex_endpoint_gap(
2682 vertex.point,
2683 edge.curve.evaluate(*parameter).or_refuse(KernelStage::Refine, "evaluate")?,
2684 ));
2685 incident.push(deviation_of.get(&edge.id).copied().unwrap_or(0.0));
2686 }
2687 measured_vertices.push((vertex.id, vertex_tolerance_from_edges(gaps, incident)));
2688 }
2689
2690 Ok(CarrierDeviation {
2691 band,
2692 lane,
2693 surface: surface_fit,
2694 edges: measured_edges,
2695 vertices: measured_vertices,
2696 })
2697}
2698
2699fn offset_face_carrier_impl(
2700 solid: &BrepSolid,
2701 face_id: u64,
2702 distance: f64,
2703 extension: &CarrierExtension,
2704 measure: bool,
2705) -> Result<OffsetFaceCarrier, KernelRefusal> {
2706 let source = solid
2707 .shells
2708 .iter()
2709 .flat_map(|shell| &shell.faces)
2710 .find(|face| face.id == face_id)
2711 .ok_or_else(|| format!("offset_face_carrier: missing face {face_id}")).or_refuse(KernelStage::Refine, "offset_missing_face")?;
2712 let band = offset_construction_band(solid_model_scale(solid));
2720 let fit_tolerance =
2727 crate::KernelTolerances::for_scale(solid_model_scale(solid), 1e-7).intersection_fit;
2728 let (surface, lane, surface_fit) = if measure {
2729 let measured = offset_surface_measured_sided(source, distance, extension, band)?;
2730 (measured.surface, measured.lane, measured.fit)
2731 } else {
2732 let (surface, lane) = offset_surface_with_lane(source, distance, extension)?;
2733 (surface, lane, None)
2734 };
2735 let source_edges = solid
2736 .edges
2737 .iter()
2738 .map(|edge| (edge.id, edge))
2739 .collect::<HashMap<_, _>>();
2740 let source_vertices = solid
2741 .vertices
2742 .iter()
2743 .map(|vertex| (vertex.id, vertex))
2744 .collect::<HashMap<_, _>>();
2745 let mut vertices = Vec::new();
2746 let mut vertex_images = HashMap::default();
2747 let vertex_split = (distance.abs() * 0.1).max(band);
2751 let mut edges = Vec::new();
2752 let mut edge_images = HashMap::default();
2753 let mut loops = Vec::new();
2754 let mut next_id = 1u64;
2755
2756 for source_loop in &source.loops {
2757 let mut coedges = Vec::new();
2758 for source_coedge in &source_loop.coedges {
2759 let source_edge = source_edges
2760 .get(&source_coedge.edge_id)
2761 .ok_or_else(|| "offset_face_carrier: missing source edge".to_string()).or_refuse(KernelStage::Refine, "offset_missing_edge")?;
2762 let (source_start, source_end) = if source_coedge.forward {
2763 (source_edge.start_vertex_id, source_edge.end_vertex_id)
2764 } else {
2765 (source_edge.end_vertex_id, source_edge.start_vertex_id)
2766 };
2767 if !source_vertices.contains_key(&source_start)
2768 || !source_vertices.contains_key(&source_end)
2769 {
2770 return Err(KernelRefusal::internal(KernelStage::Refine, "offset_missing_vertex", "offset_face_carrier: missing source vertex"));
2771 }
2772 let collapse_tolerance = 1e-6f64.max(distance.abs() * 1e-2);
2790 let (points, parameters, exact_image) = match lazy_carrier_trace(
2791 &surface, &source_coedge.pcurve, collapse_tolerance, fit_tolerance,
2792 ) {
2793 Some((points, image)) => (points, Vec::new(), Some(image)),
2794 None => {
2795 let (points, parameters) = mapped_pcurve_polyline(&surface, &source_coedge.pcurve, false)?;
2796 (points, parameters, None)
2797 }
2798 };
2799 let image_collapsed = points
2800 .iter()
2801 .all(|point| point.sub(points[0]).length() <= collapse_tolerance);
2802 let (edge_id, forward) =
2803 if let Some((edge_id, edge_start_vertex_id, creator_forward)) =
2804 edge_images.get(&source_edge.id)
2805 {
2806 if source_start == source_end {
2807 (*edge_id, source_coedge.forward == *creator_forward)
2830 } else {
2831 (
2834 *edge_id,
2835 vertex_images
2836 .get(&source_start)
2837 .is_some_and(|ids: &Vec<u64>| ids.contains(edge_start_vertex_id)),
2838 )
2839 }
2840 } else {
2841 let (curve, t0, t1) = if image_collapsed {
2842 let curve = NurbsCurve::new(
2843 1,
2844 vec![0.0, 0.0, 1.0, 1.0],
2845 vec![
2846 Vec4::from_point(points[0], 1.0),
2847 Vec4::from_point(points[0], 1.0),
2848 ],
2849 ).or_refuse(KernelStage::Refine, "new")?;
2850 (curve, 0.0, 1.0)
2851 } else if let Some(image) = exact_image {
2852 image
2853 } else {
2854 carrier_edge_curve(
2855 &surface,
2856 &source_coedge.pcurve,
2857 &points,
2858 ¶meters,
2859 fit_tolerance,
2860 )?
2861 };
2862 let start_vertex_id = claim_vertex_image(
2863 source_start,
2864 points[0],
2865 vertex_split,
2866 &mut vertex_images,
2867 &mut vertices,
2868 &mut next_id,
2869 );
2870 let end_vertex_id = claim_vertex_image(
2871 source_end,
2872 points[points.len() - 1],
2873 vertex_split,
2874 &mut vertex_images,
2875 &mut vertices,
2876 &mut next_id,
2877 );
2878 let id = next_id;
2879 next_id += 1;
2880 edges.push(EdgeRecord {
2881 id,
2882 curve,
2883 t0,
2884 t1,
2885 start_vertex_id,
2886 end_vertex_id,
2887 degenerate: image_collapsed,
2901 name: source_edge
2905 .name
2906 .as_ref()
2907 .map(|name| format!("{name}_Offset")),
2908 });
2909 edge_images.insert(
2910 source_edge.id,
2911 (id, start_vertex_id, source_coedge.forward),
2912 );
2913 (id, true)
2914 };
2915 let id = next_id;
2916 next_id += 1;
2917 coedges.push(CoedgeRecord {
2918 id,
2919 edge_id,
2920 forward,
2921 pcurve: source_coedge.pcurve.clone(),
2922 });
2923 }
2924 let id = next_id;
2925 next_id += 1;
2926 loops.push(LoopRecord { id, coedges });
2927 }
2928 let deviation = if measure {
2929 Some(measure_carrier(
2930 &surface,
2931 &vertices,
2932 &edges,
2933 &loops,
2934 lane,
2935 surface_fit,
2936 band,
2937 )?)
2938 } else {
2939 None
2940 };
2941 Ok(OffsetFaceCarrier {
2942 vertices,
2943 edges,
2944 face: FaceRecord {
2945 id: next_id,
2946 surface,
2947 same_sense: source.same_sense,
2948 loops,
2949 name: source.name.as_ref().map(|name| format!("{name}_Offset")),
2950 },
2951 deviation,
2952 lane,
2953 })
2954}
2955
2956
2957
2958
2959