1use crate::{KernelRefusal, KernelStage, OrRefuse};
2use crate::fit::solve_dense;
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];
118 for column in 0..count_v {
119 let solve_axis = |axis: fn(Vec3) -> f64| {
120 solve_dense(
121 matrix_u.clone(),
122 samples.iter().map(|row| axis(row[column])).collect(),
123 )
124 };
125 let x = solve_axis(|point| point.x).or_refuse(KernelStage::Refine, "solve_axis")?;
126 let y = solve_axis(|point| point.y).or_refuse(KernelStage::Refine, "solve_axis")?;
127 let z = solve_axis(|point| point.z).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 solve_axis = |axis: fn(Vec3) -> f64| {
135 solve_dense(
136 matrix_v.clone(),
137 intermediate[row].iter().copied().map(axis).collect(),
138 )
139 };
140 let x = solve_axis(|point| point.x).or_refuse(KernelStage::Refine, "solve_axis")?;
141 let y = solve_axis(|point| point.y).or_refuse(KernelStage::Refine, "solve_axis")?;
142 let z = solve_axis(|point| point.z).or_refuse(KernelStage::Refine, "solve_axis")?;
143 for column in 0..count_v {
144 controls[row][column] = Vec4::from_point(
145 Vec3::new(x[column], y[column], z[column]),
146 weights[row][column],
147 );
148 }
149 }
150 return Ok(controls);
151 }
152
153 let unknowns = count_u * count_v;
156 let mut matrix = vec![vec![0.0; unknowns]; unknowns];
157 for (k, &u) in parameters_u.iter().enumerate() {
158 let span_u = knot_u.find_span(u);
159 let basis_u = knot_u.basis_functions(span_u, u);
160 for (l, &v) in parameters_v.iter().enumerate() {
161 let span_v = knot_v.find_span(v);
162 let basis_v = knot_v.basis_functions(span_v, v);
163 let row = &mut matrix[k * count_v + l];
164 let mut denominator = 0.0;
165 for (du, value_u) in basis_u.iter().enumerate() {
166 let i = span_u - knot_u.degree + du;
167 for (dv, value_v) in basis_v.iter().enumerate() {
168 let j = span_v - knot_v.degree + dv;
169 let entry = value_u * value_v * weights[i][j];
170 row[i * count_v + j] = entry;
171 denominator += entry;
172 }
173 }
174 if denominator.abs() > 0.0 {
175 for value in row.iter_mut() {
176 *value /= denominator;
177 }
178 }
179 }
180 }
181 let solve_axis = |axis: fn(Vec3) -> f64| {
182 solve_dense(
183 matrix.clone(),
184 samples
185 .iter()
186 .flat_map(|row| row.iter().copied().map(axis))
187 .collect(),
188 )
189 };
190 let x = solve_axis(|point| point.x).or_refuse(KernelStage::Refine, "solve_axis")?;
191 let y = solve_axis(|point| point.y).or_refuse(KernelStage::Refine, "solve_axis")?;
192 let z = solve_axis(|point| point.z).or_refuse(KernelStage::Refine, "solve_axis")?;
193 let mut controls = vec![vec![Vec4::from_point(Vec3::default(), 1.0); count_v]; count_u];
194 for row in 0..count_u {
195 for column in 0..count_v {
196 let index = row * count_v + column;
197 controls[row][column] = Vec4::from_point(
198 Vec3::new(x[index], y[index], z[index]),
199 weights[row][column],
200 );
201 }
202 }
203 Ok(controls)
204}
205
206#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
216pub enum OffsetSurfaceLane {
217 Affine,
221 Analytic,
227 #[default]
231 Fit,
232 Reparameterised,
238}
239
240#[derive(Clone, Debug)]
243pub struct MeasuredOffsetSurface {
244 pub surface: NurbsSurface,
245 pub lane: OffsetSurfaceLane,
246 pub fit: Option<MeasuredTolerance>,
254}
255
256#[derive(Clone, Copy, Debug, PartialEq)]
268pub struct CarrierExtension {
269 pub u_min: f64,
270 pub u_max: f64,
271 pub v_min: f64,
272 pub v_max: f64,
273}
274
275impl CarrierExtension {
276 pub const NONE: CarrierExtension = CarrierExtension {
277 u_min: 0.0,
278 u_max: 0.0,
279 v_min: 0.0,
280 v_max: 0.0,
281 };
282
283 pub fn uniform(amount: f64) -> CarrierExtension {
284 CarrierExtension {
285 u_min: amount,
286 u_max: amount,
287 v_min: amount,
288 v_max: amount,
289 }
290 }
291
292 pub fn is_active(&self) -> bool {
293 self.u_min > 0.0 || self.u_max > 0.0 || self.v_min > 0.0 || self.v_max > 0.0
294 }
295
296 fn extends_v(&self) -> bool {
297 self.v_min > 0.0 || self.v_max > 0.0
298 }
299}
300
301const EXACT_TRIM_BOX_DEFAULT: bool = true;
310
311fn exact_trim_box_on() -> bool {
312 switch!(live "BREP_OFFSET_EXACT_TRIM_BOX", EXACT_TRIM_BOX_DEFAULT)
313}
314
315
316const TRIM_EXTREME_STEPS: usize = 64;
320
321fn refine_trim_extreme(
330 pcurve: &NurbsCurve,
331 samples: &[(f64, Vec3)],
332 axis: usize,
333 sign: f64,
334) -> Result<f64, KernelRefusal> {
335 let read = |uv: Vec3| sign * if axis == 0 { uv.x } else { uv.y };
336 let at = |parameter: f64| -> Result<f64, KernelRefusal> {
337 Ok(read(pcurve.evaluate(parameter).or_refuse(KernelStage::Refine, "evaluate")?))
338 };
339 let best = (0..samples.len())
340 .max_by(|&a, &b| read(samples[a].1).total_cmp(&read(samples[b].1)))
341 .expect("a pcurve has samples");
342 let mut found = read(samples[best].1);
343 let (mut a, mut b) = (samples[best.saturating_sub(1)].0, samples[(best + 1).min(samples.len() - 1)].0);
344 const GOLDEN: f64 = 0.618_033_988_749_894_9;
345 let mut c = b - GOLDEN * (b - a);
346 let mut d = a + GOLDEN * (b - a);
347 let (mut fc, mut fd) = (at(c)?, at(d)?);
348 for _ in 0..TRIM_EXTREME_STEPS {
349 found = found.max(fc).max(fd);
350 if fc >= fd {
351 (b, d, fd) = (d, c, fc);
352 c = b - GOLDEN * (b - a);
353 fc = at(c)?;
354 } else {
355 (a, c, fc) = (c, d, fd);
356 d = a + GOLDEN * (b - a);
357 fd = at(d)?;
358 }
359 }
360 Ok(sign * found.max(fc).max(fd))
361}
362
363fn trim_domain_fractions(
368 face: &FaceRecord,
369 [u0, u1]: [f64; 2],
370 [v0, v1]: [f64; 2],
371) -> Result<([f64; 2], [f64; 2]), KernelRefusal> {
372 let mut low = Vec2 {
373 x: f64::INFINITY,
374 y: f64::INFINITY,
375 };
376 let mut high = Vec2 {
377 x: f64::NEG_INFINITY,
378 y: f64::NEG_INFINITY,
379 };
380 for coedge in face
381 .loops
382 .iter()
383 .flat_map(|loop_record| &loop_record.coedges)
384 {
385 let [p0, p1] = coedge.pcurve.domain().or_refuse(KernelStage::Refine, "domain")?;
386 let mut samples = Vec::with_capacity(25);
387 for sample in 0..=24 {
388 let parameter = p0 + (p1 - p0) * sample as f64 / 24.0;
389 let uv = coedge
390 .pcurve
391 .evaluate(parameter).or_refuse(KernelStage::Refine, "evaluate")?;
392 low.x = low.x.min(uv.x);
393 low.y = low.y.min(uv.y);
394 high.x = high.x.max(uv.x);
395 high.y = high.y.max(uv.y);
396 samples.push((parameter, uv));
397 }
398 if coedge.pcurve.degree > 1 && exact_trim_box_on() {
399 low.x = low.x.min(refine_trim_extreme(&coedge.pcurve, &samples, 0, -1.0)?);
400 high.x = high.x.max(refine_trim_extreme(&coedge.pcurve, &samples, 0, 1.0)?);
401 low.y = low.y.min(refine_trim_extreme(&coedge.pcurve, &samples, 1, -1.0)?);
402 high.y = high.y.max(refine_trim_extreme(&coedge.pcurve, &samples, 1, 1.0)?);
403 }
404 }
405 let fraction = |value: f64, start: f64, end: f64| {
406 let span = end - start;
407 if span.abs() <= f64::EPSILON || !value.is_finite() {
408 return None;
409 }
410 Some(((value - start) / span).clamp(0.0, 1.0))
411 };
412 let u = match (fraction(low.x, u0, u1), fraction(high.x, u0, u1)) {
413 (Some(a), Some(b)) if b - a > 1e-6 => [a, b],
414 _ => [0.0, 1.0],
415 };
416 let v = match (fraction(low.y, v0, v1), fraction(high.y, v0, v1)) {
417 (Some(a), Some(b)) if b - a > 1e-6 => [a, b],
418 _ => [0.0, 1.0],
419 };
420 Ok((u, v))
421}
422
423fn domain_end_moves(grow_min: f64, grow_max: f64, [ta, tb]: [f64; 2]) -> (f64, f64) {
433 let span = tb - ta;
434 if span <= 1e-6 {
435 return (grow_min, grow_max);
436 }
437 let rate = (grow_min + grow_max) / span;
438 let back = grow_min + ta * rate;
439 let forward = (1.0 - ta) * rate - grow_min;
440 (back.max(0.0), forward.max(0.0))
441}
442
443pub fn offset_surface(
447 face: &FaceRecord,
448 distance: f64,
449 planar_extension: f64,
450) -> Result<NurbsSurface, KernelRefusal> {
451 offset_surface_with_lane(face, distance, &CarrierExtension::uniform(planar_extension))
452 .map(|(surface, _)| surface)
453}
454
455pub fn offset_surface_measured(
464 face: &FaceRecord,
465 distance: f64,
466 planar_extension: f64,
467 band: f64,
468) -> Result<MeasuredOffsetSurface, KernelRefusal> {
469 offset_surface_measured_sided(
470 face,
471 distance,
472 &CarrierExtension::uniform(planar_extension),
473 band,
474 )
475}
476
477pub fn offset_surface_measured_sided(
479 face: &FaceRecord,
480 distance: f64,
481 extension: &CarrierExtension,
482 band: f64,
483) -> Result<MeasuredOffsetSurface, KernelRefusal> {
484 offset_surface_measured_sided_mode(face, distance, extension, band,
485 std::env::var("BREP_OFFSET_SPHERE_READING").map_or(true, |v| v != "0" && v != "off"))
486}
487
488fn offset_surface_measured_sided_mode(
489 face: &FaceRecord, distance: f64, extension: &CarrierExtension, band: f64, reuse: bool,
490) -> Result<MeasuredOffsetSurface, KernelRefusal> {
491 let mut sphere_reading = None;
492 let (surface, lane, extended) = offset_surface_constructed(face, distance, extension, &mut sphere_reading)?;
493 let fit = match lane {
494 OffsetSurfaceLane::Affine => Some(MeasuredTolerance::exact(band)),
495 OffsetSurfaceLane::Analytic if reuse && sphere_reading.is_some() => {
500 if crate::profile::profile_enabled() {
504 profile_line!("offset.sphere_reading.profile reused=1");
505 }
506 Some(MeasuredTolerance::new(sphere_reading.unwrap(), band))
507 }
508 OffsetSurfaceLane::Analytic | OffsetSurfaceLane::Fit => {
509 Some(measure_surface_fit_against_pointwise_offset(
510 extended.as_ref().unwrap_or(&face.surface),
511 face.same_sense,
512 &surface,
513 distance,
514 band,
515 )?)
516 }
517 OffsetSurfaceLane::Reparameterised => None,
518 };
519 Ok(MeasuredOffsetSurface { surface, lane, fit })
520}
521
522fn sphere_offset_surface(face: &FaceRecord, distance: f64, reading: &mut Option<f64>) -> Result<Option<NurbsSurface>, KernelRefusal> {
551 if std::env::var_os("BREP_NO_ANALYTIC_OFFSET").is_some() {
555 return Ok(None);
556 }
557 let source = &face.surface;
558 let Some((centre, radius)) = source.analytic().and_then(|shape| shape.sphere_geometry()) else {
559 return Ok(None);
560 };
561 let ([u0, u1], [v0, v1]) = domains(source)?;
562 let Ok(sample) = OffsetEvaluator::new(
569 "offset_surface",
570 source,
571 OffsetNormal::FaceStable {
572 same_sense: face.same_sense,
573 },
574 )
575 .at((u0 + u1) / 2.0, (v0 + v1) / 2.0, -distance)
576 else {
577 return Ok(None);
578 };
579 let source_radial = sample.source.sub(centre);
580 let offset_radial = sample.point.sub(centre);
581 let offset_radius = offset_radial.length();
582 let scale = radius.max(1.0);
583 if radius <= 1e-12
584 || offset_radius <= 1e-9 * scale
585 || offset_radial.dot(source_radial) <= 0.0
588 || ((offset_radius - radius).abs() - distance.abs()).abs() > 1e-9 * scale
591 {
592 return Ok(None);
593 }
594 let factor = offset_radius / radius;
595 let Ok(controls) = source
598 .control_points
599 .iter()
600 .map(|row| {
601 row.iter()
602 .map(|control| {
603 Ok(Vec4::from_point(
604 centre.add(control.point().or_refuse(KernelStage::Refine, "point")?.sub(centre).scale(factor)),
605 control.w,
606 ))
607 })
608 .collect::<Result<Vec<_>, KernelRefusal>>()
609 })
610 .collect::<Result<Vec<Vec<_>>, KernelRefusal>>()
611 else {
612 return Ok(None);
613 };
614 let Ok(surface) = NurbsSurface::new(
615 source.degree_u,
616 source.degree_v,
617 source.knots_u.clone(),
618 source.knots_v.clone(),
619 controls,
620 ) else {
621 return Ok(None);
622 };
623 match crate::offset_measure::sphere_fit_reading(
627 source,
628 face.same_sense,
629 &surface,
630 distance,
631 1e-9 * scale,
632 ) {
633 Ok(measured) if measured.within_band() => {
634 *reading = Some(measured.deviation());
635 Ok(Some(surface))
636 },
637 _ => Ok(None),
638 }
639}
640
641fn revolved_arc_offset_surface(
674 face: &FaceRecord,
675 distance: f64,
676) -> Result<Option<NurbsSurface>, KernelRefusal> {
677 if std::env::var_os("BREP_NO_ANALYTIC_OFFSET").is_some() {
678 return Ok(None);
679 }
680 let source = &face.surface;
681 match source.analytic() {
682 Some(crate::AnalyticSurface::Revolution { .. } | crate::AnalyticSurface::Torus { .. }) => {}
683 _ => return Ok(None),
684 }
685 let rows = &source.control_points;
686 let Some(first_row) = rows.first() else {
687 return Ok(None);
688 };
689 if rows.iter().flatten().any(|control| !(control.w > 0.0)) {
690 return Ok(None);
691 }
692 let Ok(generatrix) = NurbsCurve::new(source.degree_v, source.knots_v.clone(), first_row.clone())
693 else {
694 return Ok(None);
695 };
696 let [t0, t1] = generatrix.domain().or_refuse(KernelStage::Refine, "domain")?;
697 let at = |fraction: f64| generatrix.evaluate(t0 + (t1 - t0) * fraction);
698 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")?);
700 let (ab, ae) = (b.sub(a), e.sub(a));
701 let normal = ab.cross(ae);
702 let normal_length_squared = normal.dot(normal);
703 let Some(centre) = crate::circumcenter(a, b, e) else { return Ok(None); };
704 let radius = a.sub(centre).length();
705 let scale = (centre.length() + radius).max(1.0);
706 let band = 1e-9 * scale;
707 let unit_normal = normal.scale(1.0 / normal_length_squared.sqrt());
708 let samples = 16 * generatrix.control_points.len();
709 for index in 0..=samples {
710 let point = at(index as f64 / samples as f64).or_refuse(KernelStage::Refine, "at")?;
711 let radial = point.sub(centre);
712 if (radial.length() - radius).abs() > band || radial.dot(unit_normal).abs() > band {
713 return Ok(None);
714 }
715 }
716 let controls = first_row
719 .iter()
720 .map(|control| control.point().or_refuse(KernelStage::Refine, "point"))
721 .collect::<Result<Vec<_>, KernelRefusal>>()?;
722 let origin = controls[0];
723 let mut best = (0usize, 0usize, 0.0f64);
724 for first in 1..controls.len() {
725 for second in first + 1..controls.len() {
726 let area = controls[first]
727 .sub(origin)
728 .cross(controls[second].sub(origin))
729 .length();
730 if area > best.2 {
731 best = (first, second, area);
732 }
733 }
734 }
735 let (first, second, area) = best;
736 if area <= 1e-9 * scale * scale {
737 return Ok(None);
738 }
739 let (along_first, along_second) = (controls[first].sub(origin), controls[second].sub(origin));
740 let offset_from_origin = centre.sub(origin);
741 let (g11, g12, g22) = (
742 along_first.dot(along_first),
743 along_first.dot(along_second),
744 along_second.dot(along_second),
745 );
746 let determinant = g11 * g22 - g12 * g12;
747 let (r1, r2) = (along_first.dot(offset_from_origin), along_second.dot(offset_from_origin));
748 let s = (r1 * g22 - r2 * g12) / determinant;
749 let t = (r2 * g11 - r1 * g12) / determinant;
750 if origin
751 .add(along_first.scale(s))
752 .add(along_second.scale(t))
753 .sub(centre)
754 .length()
755 > band
756 {
757 return Ok(None);
758 }
759 let ([u0, _], [v0, v1]) = domains(source)?;
762 let Ok(sample) = OffsetEvaluator::new(
763 "offset_surface",
764 source,
765 OffsetNormal::FaceStable {
766 same_sense: face.same_sense,
767 },
768 )
769 .at(u0, (v0 + v1) / 2.0, -distance)
770 else {
771 return Ok(None);
772 };
773 let source_radial = sample.source.sub(centre);
774 let offset_radial = sample.point.sub(centre);
775 let offset_radius = offset_radial.length();
776 if (source_radial.length() - radius).abs() > band
777 || offset_radius <= band
778 || offset_radial.dot(source_radial) <= 0.0
779 || ((offset_radius - radius).abs() - distance.abs()).abs() > band
780 {
781 return Ok(None);
782 }
783 let factor = offset_radius / radius;
784 let Ok(offset_rows) = rows
785 .iter()
786 .map(|row| {
787 let points = row.iter().map(|control| control.point().or_refuse(KernelStage::Refine, "point")).collect::<Result<Vec<_>, KernelRefusal>>()?;
788 let row_origin = points[0];
789 let row_centre = row_origin
790 .add(points[first].sub(row_origin).scale(s))
791 .add(points[second].sub(row_origin).scale(t));
792 Ok(points
793 .iter()
794 .zip(row)
795 .map(|(point, control)| {
796 Vec4::from_point(row_centre.add(point.sub(row_centre).scale(factor)), control.w)
797 })
798 .collect::<Vec<_>>())
799 })
800 .collect::<Result<Vec<Vec<_>>, KernelRefusal>>()
801 else {
802 return Ok(None);
803 };
804 let Ok(surface) = NurbsSurface::new(
805 source.degree_u,
806 source.degree_v,
807 source.knots_u.clone(),
808 source.knots_v.clone(),
809 offset_rows,
810 ) else {
811 return Ok(None);
812 };
813 match measure_surface_fit_against_pointwise_offset(
814 source,
815 face.same_sense,
816 &surface,
817 distance,
818 band,
819 ) {
820 Ok(measured) if measured.within_band() => Ok(Some(surface)),
821 _ => Ok(None),
822 }
823}
824
825pub(crate) fn exact_cylinder_offsets_on() -> bool {
830 switch!("BREP_OFFSET_EXACT_CYLINDER", true)
831}
832
833
834pub(crate) fn cylinder_offset_factor(
841 surface: &NurbsSurface,
842 same_sense: bool,
843 distance: f64,
844) -> Result<Option<(Vec3, Vec3, f64, f64)>, KernelRefusal> {
845 if std::env::var_os("BREP_NO_ANALYTIC_OFFSET").is_some() {
846 return Ok(None);
847 }
848 let Some(crate::AnalyticSurface::RuledRevolution { frame, rho0, rho1, height }) = surface.analytic() else {
849 return Ok(None);
850 };
851 let radius = 0.5 * (rho0 + rho1);
852 if !(radius > 0.0) || (rho0 - rho1).abs() > 1e-9 * radius.max(1.0) {
853 return Ok(None);
854 }
855 let Ok(axis) = frame.axis.normalized() else {
856 return Ok(None);
857 };
858 let origin = frame.origin;
859 let band = 1e-9 * (origin.length() + radius + height.abs()).max(1.0);
860 let perpendicular = |point: Vec3| {
861 let along = point.sub(origin);
862 along.sub(axis.scale(along.dot(axis)))
863 };
864 let [u0, u1] = surface.domain_u().or_refuse(KernelStage::Refine, "domain_u")?;
865 let [v0, v1] = surface.domain_v().or_refuse(KernelStage::Refine, "domain_v")?;
866 let Ok(sample) = OffsetEvaluator::new("offset_surface", surface, OffsetNormal::FaceStable { same_sense })
867 .at((u0 + u1) * 0.5, (v0 + v1) * 0.5, -distance)
868 else {
869 return Ok(None);
870 };
871 let (source_radial, offset_radial) = (perpendicular(sample.source), perpendicular(sample.point));
872 let offset_radius = offset_radial.length();
873 if (source_radial.length() - radius).abs() > band
874 || offset_radius <= band
875 || offset_radial.dot(source_radial) <= 0.0
876 || ((offset_radius - radius).abs() - distance.abs()).abs() > band
877 || sample.point.sub(sample.source).dot(axis).abs() > band
878 {
879 return Ok(None);
880 }
881 Ok(Some((origin, axis, radius, offset_radius / radius)))
882}
883
884fn cylinder_offset_surface(
897 reference: &NurbsSurface,
898 same_sense: bool,
899 distance: f64,
900) -> Result<Option<NurbsSurface>, KernelRefusal> {
901 let Some((origin, axis, radius, factor)) = cylinder_offset_factor(reference, same_sense, distance)? else {
902 return Ok(None);
903 };
904 if reference.control_points.iter().flatten().any(|control| !(control.w > 0.0)) {
905 return Ok(None);
906 }
907 let Ok(rows) = reference
908 .control_points
909 .iter()
910 .map(|row| {
911 row.iter()
912 .map(|control| {
913 let point = control.point()?;
914 let foot = origin.add(axis.scale(point.sub(origin).dot(axis)));
915 Ok(Vec4::from_point(foot.add(point.sub(foot).scale(factor)), control.w))
916 })
917 .collect::<Result<Vec<_>, String>>()
918 })
919 .collect::<Result<Vec<Vec<_>>, String>>()
920 else {
921 return Ok(None);
922 };
923 let Ok(surface) = NurbsSurface::new(
924 reference.degree_u,
925 reference.degree_v,
926 reference.knots_u.clone(),
927 reference.knots_v.clone(),
928 rows,
929 ) else {
930 return Ok(None);
931 };
932 let band = 1e-9 * (origin.length() + radius * factor.max(1.0)).max(1.0);
938 let evaluator = OffsetEvaluator::new("offset_surface", reference, OffsetNormal::FaceStable { same_sense });
939 let [u0, u1] = reference.domain_u().or_refuse(KernelStage::Refine, "domain_u")?;
940 let [v0, v1] = reference.domain_v().or_refuse(KernelStage::Refine, "domain_v")?;
941 for i in 0..=4 {
942 for j in 0..=2 {
943 let (u, v) = (u0 + (u1 - u0) * i as f64 / 4.0, v0 + (v1 - v0) * j as f64 / 2.0);
944 let (Ok(want), Ok(got)) = (evaluator.at(u, v, -distance), surface.evaluate(u, v)) else {
945 return Ok(None);
946 };
947 if !(want.point.sub(got).length() <= band) {
948 return Ok(None);
949 }
950 }
951 }
952 Ok(Some(surface))
953}
954
955pub(crate) fn offset_surface_with_lane(
956 face: &FaceRecord,
957 distance: f64,
958 extension: &CarrierExtension,
959) -> Result<(NurbsSurface, OffsetSurfaceLane), KernelRefusal> {
960 offset_surface_constructed(face, distance, extension, &mut None).map(|(surface, lane, _)| (surface, lane))
961}
962
963pub(crate) fn transpose_offset_surface(surface: &NurbsSurface) -> Result<NurbsSurface, KernelRefusal> {
967 let controls = (0..surface.control_points[0].len())
968 .map(|column| surface.control_points.iter().map(|row| row[column]).collect())
969 .collect();
970 NurbsSurface::new(surface.degree_v, surface.degree_u, surface.knots_v.clone(),
971 surface.knots_u.clone(), controls).or_refuse(KernelStage::Refine, "offset_transpose")
972}
973
974pub(crate) fn apex_end_reach_enabled() -> bool {
977 switch!("BREP_OFFSET_APEX_END_REACH", true)
978}
979
980
981fn offset_surface_constructed(
982 face: &FaceRecord,
983 distance: f64,
984 extension: &CarrierExtension,
985 sphere_reading: &mut Option<f64>,
986) -> Result<(NurbsSurface, OffsetSurfaceLane, Option<NurbsSurface>), KernelRefusal> {
987 let source = &face.surface;
988 let extension_active = extension.is_active();
989 let normalize_ruling = std::env::var("BREP_OFFSET_FIT_RESIDUAL").as_deref() != Ok("0")
995 && source.degree_u == 1 && source.control_points.len() == 2;
996 let normalize_sphere = std::env::var("BREP_OFFSET_FOLD_CHART").as_deref() != Ok("0")
997 && source.degree_u == 2 && source.degree_v == 2 && source.analytic().is_none();
998 if normalize_ruling || normalize_sphere {
999 let transposed = transpose_offset_surface(source)?;
1000 let ruled = normalize_ruling && matches!(transposed.analytic(), Some(crate::AnalyticSurface::RuledRevolution { .. }));
1001 let spherical = normalize_sphere && transposed.analytic().and_then(|shape| shape.sphere_geometry()).is_some();
1002 if ruled || spherical {
1003 let mut turned = face.clone();
1004 turned.surface = transposed;
1005 turned.same_sense = !turned.same_sense;
1006 for coedge in turned.loops.iter_mut().flat_map(|lp| &mut lp.coedges) {
1007 let controls = coedge.pcurve.control_points.iter().map(|point| {
1008 let mut swapped = *point;
1009 std::mem::swap(&mut swapped.x, &mut swapped.y);
1010 swapped
1011 }).collect();
1012 coedge.pcurve = NurbsCurve::new(coedge.pcurve.degree,
1013 coedge.pcurve.knots.clone(), controls).or_refuse(KernelStage::Refine, "offset_transpose_pcurve")?;
1014 }
1015 let turned_extension = CarrierExtension {
1016 u_min: extension.v_min, u_max: extension.v_max,
1017 v_min: extension.u_min, v_max: extension.u_max,
1018 };
1019 let (surface, lane, extended) = offset_surface_constructed(&turned, distance, &turned_extension, &mut None)?;
1020 return Ok((transpose_offset_surface(&surface)?, lane,
1021 extended.as_ref().map(transpose_offset_surface).transpose()?));
1022 }
1023 }
1024 if source.is_affine().or_refuse(KernelStage::Refine, "is_affine")? {
1025 let ([u0, u1], [v0, v1]) = domains(source)?;
1026 let normal = stable_face_normal(face, (u0 + u1) / 2.0, (v0 + v1) / 2.0)?;
1027 let shift = normal.scale(-distance);
1028 let mut points = source
1029 .control_points
1030 .iter()
1031 .map(|row| {
1032 row.iter()
1033 .map(|control| Ok(control.point().or_refuse(KernelStage::Refine, "point")?.add(shift)))
1034 .collect::<Result<Vec<_>, KernelRefusal>>()
1035 })
1036 .collect::<Result<Vec<_>, KernelRefusal>>()?;
1037 if extension_active {
1038 let p00 = points[0][0];
1039 let p01 = points[0][1];
1040 let p10 = points[1][0];
1041 let direction_u = p10.sub(p00).normalized().or_refuse(KernelStage::Refine, "normalized")?;
1042 let direction_v = p01.sub(p00).normalized().or_refuse(KernelStage::Refine, "normalized")?;
1043 let (trim_u, trim_v) = trim_domain_fractions(face, [u0, u1], [v0, v1])?;
1049 let (back_u, forward_u) = domain_end_moves(extension.u_min, extension.u_max, trim_u);
1050 let (back_v, forward_v) = domain_end_moves(extension.v_min, extension.v_max, trim_v);
1051 points[0][0] = p00
1052 .sub(direction_u.scale(back_u))
1053 .sub(direction_v.scale(back_v));
1054 points[0][1] = p01
1055 .sub(direction_u.scale(back_u))
1056 .add(direction_v.scale(forward_v));
1057 points[1][0] = p10
1058 .add(direction_u.scale(forward_u))
1059 .sub(direction_v.scale(back_v));
1060 points[1][1] = points[1][1]
1061 .add(direction_u.scale(forward_u))
1062 .add(direction_v.scale(forward_v));
1063 }
1064 let controls = points
1065 .into_iter()
1066 .enumerate()
1067 .map(|(row, points)| {
1068 points
1069 .into_iter()
1070 .enumerate()
1071 .map(|(column, point)| {
1072 Vec4::from_point(point, source.control_points[row][column].w)
1073 })
1074 .collect()
1075 })
1076 .collect();
1077 let lane = if extension_active {
1081 OffsetSurfaceLane::Reparameterised
1082 } else {
1083 OffsetSurfaceLane::Affine
1084 };
1085 return Ok((
1086 NurbsSurface::new(
1087 source.degree_u,
1088 source.degree_v,
1089 source.knots_u.clone(),
1090 source.knots_v.clone(),
1091 controls,
1092 ).or_refuse(KernelStage::Refine, "new")?,
1093 lane,
1094 None,
1095 ));
1096 }
1097
1098 if let Some(surface) = sphere_offset_surface(face, distance, sphere_reading)? {
1108 return Ok((surface, OffsetSurfaceLane::Analytic, None));
1109 }
1110 if let Some(surface) = revolved_arc_offset_surface(face, distance)? {
1113 return Ok((surface, OffsetSurfaceLane::Analytic, None));
1114 }
1115
1116 let knot_u = KnotVector::new(source.knots_u.clone(), source.degree_u).or_refuse(KernelStage::Refine, "new")?;
1117 let knot_v = KnotVector::new(source.knots_v.clone(), source.degree_v).or_refuse(KernelStage::Refine, "new")?;
1118 let parameters_u = greville_parameters(&knot_u);
1119 let parameters_v = greville_parameters(&knot_v);
1120 let evaluator = OffsetEvaluator::new(
1126 "offset_surface",
1127 source,
1128 OffsetNormal::FaceStable {
1129 same_sense: face.same_sense,
1130 },
1131 );
1132 let mut samples = Vec::new();
1133 for &u in ¶meters_u {
1134 let mut row = Vec::new();
1135 for &v in ¶meters_v {
1136 row.push(evaluator.at(u, v, -distance).or_refuse(KernelStage::Refine, "at")?.point);
1137 }
1138 samples.push(row);
1139 }
1140 let mut reparameterised = false;
1155 let mut extended_source: Option<NurbsSurface> = None;
1156 if parameters_v.len() == 2 && parameters_u.len() >= 2 {
1163 let centroid = |column: usize| {
1164 let mut sum = Vec3::default();
1165 for row in &samples {
1166 sum = sum.add(row[column]);
1167 }
1168 sum.scale(1.0 / samples.len() as f64)
1169 };
1170 let near_centroid = centroid(0);
1171 let far_centroid = centroid(1);
1172 let mut inverted = true;
1173 let mut pinch_fraction = 0.0f64;
1174 let mut near_mean = 0.0f64;
1175 let mut far_mean = 0.0f64;
1176 for row in &samples {
1177 let near_radial = row[0].sub(near_centroid);
1178 let far_radial = row[1].sub(far_centroid);
1179 let near_len = near_radial.length();
1180 let far_len = far_radial.length();
1181 if near_len <= 1e-9 || far_len <= 1e-9 {
1182 inverted = false;
1183 break;
1184 }
1185 if near_radial.dot(far_radial) >= 0.0 {
1186 inverted = false;
1187 break;
1188 }
1189 pinch_fraction += near_len / (near_len + far_len) / samples.len() as f64;
1190 near_mean += near_len / samples.len() as f64;
1191 far_mean += far_len / samples.len() as f64;
1192 }
1193 if inverted {
1194 let retrim_far = far_mean <= near_mean;
1195 let (_, trim_v) = trim_domain_fractions(face, knot_u.domain(), knot_v.domain())?;
1219 let trim_reaches_the_pinch = if retrim_far {
1220 trim_v[1] > pinch_fraction + 1e-9
1221 } else {
1222 trim_v[0] < pinch_fraction - 1e-9
1223 };
1224 if trim_reaches_the_pinch {
1225 reparameterised = true;
1228 for row in &mut samples {
1229 let near = row[0];
1230 let far = row[1];
1231 let pinch = near.add(far.sub(near).scale(pinch_fraction));
1232 if retrim_far {
1233 row[1] = pinch;
1234 } else {
1235 row[0] = pinch;
1236 }
1237 }
1238 }
1239 }
1240 if extension.extends_v() && !inverted {
1260 let apex_end_reach = apex_end_reach_enabled();
1269 let mut min_ruling = f64::MAX;
1270 let mut back_allowance = f64::MAX;
1271 let mut forward_allowance = f64::MAX;
1272 let mut extendable = true;
1273 for row in &samples {
1274 let ruling = row[1].sub(row[0]);
1275 let length = ruling.length();
1276 min_ruling = min_ruling.min(length);
1277 let near_radial = row[0].sub(near_centroid).length();
1281 let far_radial = row[1].sub(far_centroid).length();
1282 if (far_radial - near_radial).abs() > 1e-9 {
1283 let apex_at = near_radial / (near_radial - far_radial);
1284 if apex_end_reach && apex_at.abs() <= 1e-9 {
1285 back_allowance = 0.0;
1286 continue;
1287 }
1288 if apex_end_reach && (apex_at - 1.0).abs() <= 1e-9 {
1289 forward_allowance = 0.0;
1290 continue;
1291 }
1292 if (-1e-9..=1.0 + 1e-9).contains(&apex_at) {
1293 extendable = false;
1295 break;
1296 }
1297 if apex_at < 0.0 {
1298 back_allowance = back_allowance.min(0.9 * -apex_at);
1299 } else {
1300 forward_allowance = forward_allowance.min(0.9 * (apex_at - 1.0));
1301 }
1302 }
1303 }
1304 let mut source_back = f64::MAX;
1312 let mut source_forward = f64::MAX;
1313 if extendable {
1314 let source_centroid = |column: usize| {
1315 let mut sum = Vec3::default();
1316 for row in &source.control_points {
1317 if let Ok(point) = row[column].point() {
1318 sum = sum.add(point);
1319 }
1320 }
1321 sum.scale(1.0 / source.control_points.len() as f64)
1322 };
1323 let (near_source, far_source) = (source_centroid(0), source_centroid(1));
1324 for row in &source.control_points {
1325 let (near, far) = (row[0].point().or_refuse(KernelStage::Refine, "point")?, row[1].point().or_refuse(KernelStage::Refine, "point")?);
1326 let near_radial = near.sub(near_source).length();
1327 let far_radial = far.sub(far_source).length();
1328 if (far_radial - near_radial).abs() > 1e-9 {
1329 let apex_at = near_radial / (near_radial - far_radial);
1330 if apex_end_reach && apex_at.abs() <= 1e-9 {
1331 source_back = 0.0;
1332 continue;
1333 }
1334 if apex_end_reach && (apex_at - 1.0).abs() <= 1e-9 {
1335 source_forward = 0.0;
1336 continue;
1337 }
1338 if (-1e-9..=1.0 + 1e-9).contains(&apex_at) {
1339 extendable = false;
1340 break;
1341 }
1342 if apex_at < 0.0 {
1343 source_back = source_back.min(0.9 * -apex_at);
1344 } else {
1345 source_forward = source_forward.min(0.9 * (apex_at - 1.0));
1346 }
1347 }
1348 }
1349 }
1350 let (back_allowance, forward_allowance) =
1351 (back_allowance.min(source_back), forward_allowance.min(source_forward));
1352 if extendable && min_ruling > 1e-9 {
1353 let (_, trim_v) = trim_domain_fractions(face, knot_u.domain(), knot_v.domain())?;
1360 let (back_world, forward_world) =
1361 domain_end_moves(extension.v_min, extension.v_max, trim_v);
1362 let (requested_back, requested_forward) = (back_world / min_ruling, forward_world / min_ruling);
1363 let apex_end = analytic_offset_apex(source, &samples, offset_fit_contract(source)).and_then(
1375 |(at, apex)| {
1376 if at > 1.0 && at - 1.0 <= requested_forward && at - 1.0 <= source_forward {
1377 Some((false, at - 1.0, apex))
1378 } else if at < 0.0 && -at <= requested_back && -at <= source_back {
1379 Some((true, -at, apex))
1380 } else {
1381 None
1382 }
1383 },
1384 );
1385 let back = match apex_end {
1386 Some((true, reach, _)) => reach,
1387 _ => requested_back.min(back_allowance),
1388 };
1389 let forward = match apex_end {
1390 Some((false, reach, _)) => reach,
1391 _ => requested_forward.min(forward_allowance),
1392 };
1393 let stretched = samples
1394 .iter()
1395 .map(|row| {
1396 let ruling = row[1].sub(row[0]);
1397 let (near, far) = (row[0].sub(ruling.scale(back)), row[1].add(ruling.scale(forward)));
1398 match apex_end {
1399 Some((true, _, apex)) => vec![apex, far],
1400 Some((false, _, apex)) => vec![near, apex],
1401 None => vec![near, far],
1402 }
1403 })
1404 .collect::<Vec<_>>();
1405 let extended = extend_along_rulings(source, back, forward)?;
1406 let extended_offsets = OffsetEvaluator::new(
1407 "offset_surface",
1408 &extended,
1409 OffsetNormal::FaceStable {
1410 same_sense: face.same_sense,
1411 },
1412 );
1413 let [v0, v1] = knot_v.domain();
1414 let mut developability = 0.0f64;
1415 for (row, &u) in stretched.iter().zip(¶meters_u) {
1416 for fraction in [0.0, 0.5, 1.0] {
1417 let exact = extended_offsets.at(u, v0 + (v1 - v0) * fraction, -distance).or_refuse(KernelStage::Refine, "at")?.point;
1418 let along = row[0].add(row[1].sub(row[0]).scale(fraction));
1419 developability = developability.max(exact.sub(along).length());
1420 }
1421 }
1422 let contract = offset_fit_contract(source);
1423 let stretch_kept = developability <= contract;
1424 samples = if stretch_kept {
1425 stretched
1426 } else {
1427 parameters_u
1428 .iter()
1429 .map(|&u| {
1430 parameters_v
1431 .iter()
1432 .map(|&v| Ok(extended_offsets.at(u, v, -distance).or_refuse(KernelStage::Refine, "at")?.point))
1433 .collect::<Result<Vec<_>, KernelRefusal>>()
1434 })
1435 .collect::<Result<Vec<_>, KernelRefusal>>()?
1436 };
1437 if let Ok(path) = std::env::var("BREP_OFFSET_FIT_TRACE") {
1438 use std::io::Write;
1439 let line = format!(
1440 "extension deg=({},{}) net=({},{}) d={distance:.6} back={back:.6} forward={forward:.6} \
1441 developability={developability:.3e} contract={contract:.3e} lane={} thread={} args={}\n",
1442 source.degree_u,
1443 source.degree_v,
1444 source.control_points.len(),
1445 source.control_points[0].len(),
1446 if stretch_kept { "stretch" } else { "pointwise" },
1447 std::thread::current().name().unwrap_or("-"),
1448 std::env::args().skip(1).collect::<Vec<_>>().join(" "),
1449 );
1450 if let Ok(mut file) = std::fs::OpenOptions::new().create(true).append(true).open(path) {
1451 let _ = file.write_all(line.as_bytes());
1452 }
1453 }
1454 extended_source = Some(extended);
1455 }
1456 }
1457 }
1458 let reference = extended_source.as_ref().unwrap_or(source);
1459 if !reparameterised && exact_cylinder_offsets_on() {
1465 if let Some(surface) = cylinder_offset_surface(reference, face.same_sense, distance)? {
1466 return Ok((surface, OffsetSurfaceLane::Analytic, extended_source));
1467 }
1468 }
1469 let weights = reference
1470 .control_points
1471 .iter()
1472 .map(|row| row.iter().map(|point| point.w).collect::<Vec<_>>())
1473 .collect::<Vec<_>>();
1474 let fitted = NurbsSurface::new(
1475 source.degree_u,
1476 source.degree_v,
1477 source.knots_u.clone(),
1478 source.knots_v.clone(),
1479 interpolate_tensor(
1480 &knot_u,
1481 &knot_v,
1482 ¶meters_u,
1483 ¶meters_v,
1484 &samples,
1485 &weights,
1486 )?,
1487 ).or_refuse(KernelStage::Refine, "new")?;
1488 if reparameterised {
1489 return Ok((fitted, OffsetSurfaceLane::Reparameterised, None));
1490 }
1491 let reference_offsets = OffsetEvaluator::new(
1492 "offset_surface",
1493 reference,
1494 OffsetNormal::FaceStable {
1495 same_sense: face.same_sense,
1496 },
1497 );
1498 Ok((
1499 refine_offset_fit(reference, &reference_offsets, distance, fitted)?,
1500 OffsetSurfaceLane::Fit,
1501 extended_source,
1502 ))
1503}
1504
1505
1506fn analytic_offset_apex(source: &NurbsSurface, samples: &[Vec<Vec3>], contract: f64) -> Option<(f64, Vec3)> {
1515 let Some(crate::AnalyticSurface::RuledRevolution { frame, .. }) = crate::analytic_surface::recognize(source) else {
1516 return None;
1517 };
1518 let radial = |point: Vec3| {
1519 let offset = point.sub(frame.origin);
1520 offset.sub(frame.axis.scale(offset.dot(frame.axis)))
1521 };
1522 let mut crossings = Vec::with_capacity(samples.len());
1523 for row in samples {
1524 let (near, far) = (radial(row[0]), radial(row[1]));
1525 let step = far.sub(near);
1526 let at = -near.dot(step) / step.dot(step);
1527 if !at.is_finite() {
1528 return None;
1529 }
1530 crossings.push((at, row[0].add(row[1].sub(row[0]).scale(at))));
1531 }
1532 let count = crossings.len() as f64;
1535 let at = crossings.iter().map(|(at, _)| at).sum::<f64>() / count;
1536 let first = crossings.first()?.1;
1537 let spread = crossings.iter().fold(Vec3::default(), |sum, (_, point)| sum.add(point.sub(first)));
1538 let centre = first.add(spread.scale(1.0 / count));
1539 let apex = frame.origin.add(frame.axis.scale(centre.sub(frame.origin).dot(frame.axis)));
1540 crossings
1543 .iter()
1544 .all(|(_, point)| radial(*point).length() <= contract && point.sub(apex).length() <= contract)
1545 .then_some((at, apex))
1546}
1547
1548fn extend_along_rulings(surface: &NurbsSurface, back: f64, forward: f64) -> Result<NurbsSurface, KernelRefusal> {
1555 let rows = surface
1556 .control_points
1557 .iter()
1558 .map(|row| {
1559 let step = row[1].add(row[0].scale(-1.0));
1560 vec![row[0].add(step.scale(-back)), row[1].add(step.scale(forward))]
1561 })
1562 .collect::<Vec<_>>();
1563 if rows.iter().flatten().any(|point| point.w <= 1e-12) {
1564 return Err(KernelRefusal::unsupported(KernelStage::Refine, "offset_ruled_extension_weight", format!(
1565 "offset_surface: extending a ruled face by ({back:.6}, {forward:.6}) of its rulings \
1566 carries a weight through zero; the extended face is not this surface"
1567 )));
1568 }
1569 NurbsSurface::new(surface.degree_u, 1, surface.knots_u.clone(), surface.knots_v.clone(), rows)
1570 .or_refuse(KernelStage::Refine, "new")
1571}
1572
1573fn offset_fit_contract(source: &NurbsSurface) -> f64 {
1576 let scale = crate::model_scale(
1577 source
1578 .control_points
1579 .iter()
1580 .flatten()
1581 .filter_map(|point| point.point().ok()),
1582 );
1583 crate::KernelTolerances::for_scale(scale, 1e-7).intersection_fit
1584}
1585
1586const OFFSET_FIT_REFINEMENTS: usize = 6;
1588
1589const OFFSET_FIT_MAX_CONTROLS_SEPARABLE: usize = 16_384;
1592const OFFSET_FIT_MAX_CONTROLS_TENSOR: usize = 900;
1593
1594#[derive(Clone, Debug)]
1599struct OffsetFitDeviation {
1600 along_u: f64,
1601 along_v: f64,
1602 between: f64,
1603 u_sites: Vec<(f64, f64)>,
1604 v_sites: Vec<(f64, f64)>,
1605 between_uv: (f64, f64),
1606}
1607
1608impl OffsetFitDeviation {
1609 fn worst(&self) -> f64 {
1610 self.along_u.max(self.along_v).max(self.between)
1611 }
1612
1613 fn refinement_sites(&self, bar: f64) -> (Vec<f64>, Vec<f64>) {
1614 let mut u = self.u_sites.iter().filter(|(_, miss)| *miss > bar)
1615 .map(|(parameter, _)| *parameter).collect::<Vec<_>>();
1616 let mut v = self.v_sites.iter().filter(|(_, miss)| *miss > bar)
1617 .map(|(parameter, _)| *parameter).collect::<Vec<_>>();
1618 if u.is_empty() && v.is_empty() && self.between > bar {
1619 u.push(self.between_uv.0);
1620 v.push(self.between_uv.1);
1621 }
1622 (u, v)
1623 }
1624}
1625
1626fn greville_midpoints(parameters: &[f64]) -> Vec<f64> {
1627 parameters
1628 .windows(2)
1629 .filter(|pair| pair[1] - pair[0] > 1e-12)
1630 .map(|pair| 0.5 * (pair[0] + pair[1]))
1631 .collect()
1632}
1633
1634fn offset_fit_deviation(
1635 fitted: &NurbsSurface,
1636 evaluator: &OffsetEvaluator,
1637 distance: f64,
1638) -> Result<OffsetFitDeviation, KernelRefusal> {
1639 let parameters_u = greville_parameters(&KnotVector::new(fitted.knots_u.clone(), fitted.degree_u).or_refuse(KernelStage::Refine, "new")?);
1640 let parameters_v = greville_parameters(&KnotVector::new(fitted.knots_v.clone(), fitted.degree_v).or_refuse(KernelStage::Refine, "new")?);
1641 let (middle_u, middle_v) = (greville_midpoints(¶meters_u), greville_midpoints(¶meters_v));
1642 let residual_locus = std::env::var("BREP_OFFSET_FIT_RESIDUAL").as_deref() != Ok("0");
1643 let gap = |u: f64, v: f64| -> Result<f64, KernelRefusal> {
1644 Ok(fitted.evaluate(u, v).or_refuse(KernelStage::Refine, "evaluate")?.sub(evaluator.at(u, v, -distance).or_refuse(KernelStage::Refine, "at")?.point).length())
1645 };
1646 let mut deviation = OffsetFitDeviation {
1647 along_u: 0.0,
1648 along_v: 0.0,
1649 between: 0.0,
1650 u_sites: Vec::new(),
1651 v_sites: if residual_locus { middle_v.iter().map(|&v| (v, 0.0)).collect() } else { Vec::new() },
1652 between_uv: (0.0, 0.0),
1653 };
1654 for &u in &middle_u {
1655 let mut along = 0.0f64;
1656 for &v in ¶meters_v {
1657 let miss = gap(u, v)?;
1658 along = along.max(miss);
1659 deviation.along_u = deviation.along_u.max(miss);
1660 }
1661 if residual_locus { deviation.u_sites.push((u, along)); }
1662 for &v in &middle_v {
1663 let miss = gap(u, v)?;
1664 if miss > deviation.between { deviation.between_uv = (u, v); }
1665 deviation.between = deviation.between.max(miss);
1666 }
1667 }
1668 for &u in ¶meters_u {
1669 for (index, &v) in middle_v.iter().enumerate() {
1670 let miss = gap(u, v)?;
1671 deviation.along_v = deviation.along_v.max(miss);
1672 if residual_locus { deviation.v_sites[index].1 = deviation.v_sites[index].1.max(miss); }
1673 }
1674 }
1675 Ok(deviation)
1676}
1677
1678fn raise_linear_directions(
1688 surface: &NurbsSurface,
1689 in_u: bool,
1690 in_v: bool,
1691) -> Result<Option<NurbsSurface>, KernelRefusal> {
1692 fn raise(knots: &[f64], row: &[Vec4]) -> Option<(Vec<f64>, Vec<Vec4>)> {
1693 let count = row.len();
1695 if knots.len() != count + 2 {
1696 return None;
1697 }
1698 let breaks = &knots[1..=count];
1699 if breaks.windows(2).any(|pair| pair[1] - pair[0] <= 1e-12) {
1700 return None;
1701 }
1702 let mut raised_knots = vec![breaks[0]; 4];
1703 for &interior in &breaks[1..count - 1] {
1704 raised_knots.extend([interior; 3]);
1705 }
1706 raised_knots.extend([breaks[count - 1]; 4]);
1707 let mut points = Vec::with_capacity(3 * (count - 1) + 1);
1708 for pair in row.windows(2) {
1709 let step = pair[1].add(pair[0].scale(-1.0));
1710 points.push(pair[0]);
1711 points.push(pair[0].add(step.scale(1.0 / 3.0)));
1712 points.push(pair[0].add(step.scale(2.0 / 3.0)));
1713 }
1714 points.push(row[count - 1]);
1715 Some((raised_knots, points))
1716 }
1717 let mut knots_u = surface.knots_u.clone();
1718 let mut knots_v = surface.knots_v.clone();
1719 let mut degree_u = surface.degree_u;
1720 let mut degree_v = surface.degree_v;
1721 let mut net = surface.control_points.clone();
1722 if in_v {
1723 if degree_v != 1 {
1724 return Ok(None);
1725 }
1726 let mut rows = Vec::with_capacity(net.len());
1727 for row in &net {
1728 let Some((knots, points)) = raise(&surface.knots_v, row) else {
1729 return Ok(None);
1730 };
1731 knots_v = knots;
1732 rows.push(points);
1733 }
1734 net = rows;
1735 degree_v = 3;
1736 }
1737 if in_u {
1738 if degree_u != 1 {
1739 return Ok(None);
1740 }
1741 let count_v = net[0].len();
1742 let mut columns = Vec::with_capacity(count_v);
1743 for column in 0..count_v {
1744 let row = net.iter().map(|row| row[column]).collect::<Vec<_>>();
1745 let Some((knots, points)) = raise(&surface.knots_u, &row) else {
1746 return Ok(None);
1747 };
1748 knots_u = knots;
1749 columns.push(points);
1750 }
1751 let count_u = columns[0].len();
1752 net = (0..count_u)
1753 .map(|row| columns.iter().map(|column| column[row]).collect())
1754 .collect();
1755 degree_u = 3;
1756 }
1757 Ok(Some(NurbsSurface::new(degree_u, degree_v, knots_u, knots_v, net).or_refuse(KernelStage::Refine, "new")?))
1758}
1759
1760fn halve_knot_spans(surface: &NurbsSurface, in_u: bool, in_v: bool) -> Result<NurbsSurface, KernelRefusal> {
1764 fn midpoints(knots: &[f64], degree: usize) -> Vec<f64> {
1765 let last = knots.len() - 1 - degree;
1766 knots[degree..=last]
1767 .windows(2)
1768 .filter(|pair| pair[1] - pair[0] > 1e-12)
1769 .map(|pair| 0.5 * (pair[0] + pair[1]))
1770 .collect()
1771 }
1772 insert_offset_fit_knots(surface,
1773 &if in_u { midpoints(&surface.knots_u, surface.degree_u) } else { Vec::new() },
1774 &if in_v { midpoints(&surface.knots_v, surface.degree_v) } else { Vec::new() })
1775}
1776
1777fn insert_offset_fit_knots(surface: &NurbsSurface, u: &[f64], v: &[f64]) -> Result<NurbsSurface, KernelRefusal> {
1782 let refine = |degree: usize, knots: &[f64], net: Vec<Vec<Vec4>>, inserted: &[f64]| -> Result<(Vec<f64>, Vec<Vec<Vec4>>), KernelRefusal> {
1783 let mut inserted = inserted.to_vec();
1784 inserted.sort_by(f64::total_cmp);
1785 inserted.dedup_by(|a, b| (*a - *b).abs() <= 1e-12);
1786 inserted.retain(|parameter| knots.iter().filter(|knot| (**knot - *parameter).abs() <= 1e-12).count() < degree);
1787 let mut refined_knots = knots.to_vec();
1788 let mut rows = Vec::with_capacity(net.len());
1789 for row in net {
1790 let mut curve = NurbsCurve::new(degree, knots.to_vec(), row).or_refuse(KernelStage::Refine, "new")?;
1791 for ¶meter in &inserted {
1792 curve = curve.insert_knot(parameter, 1).or_refuse(KernelStage::Refine, "insert_knot")?;
1793 }
1794 refined_knots = curve.knots.clone();
1795 rows.push(curve.control_points);
1796 }
1797 Ok((refined_knots, rows))
1798 };
1799 let mut knots_u = surface.knots_u.clone();
1800 let mut knots_v = surface.knots_v.clone();
1801 let mut net = surface.control_points.clone();
1802 if !v.is_empty() {
1803 let (knots, rows) = refine(surface.degree_v, &knots_v, net, v)?;
1804 knots_v = knots;
1805 net = rows;
1806 }
1807 if !u.is_empty() {
1808 let count_v = net[0].len();
1810 let columns = (0..count_v)
1811 .map(|column| net.iter().map(|row| row[column]).collect::<Vec<_>>())
1812 .collect::<Vec<_>>();
1813 let (knots, refined) = refine(surface.degree_u, &knots_u, columns, u)?;
1814 knots_u = knots;
1815 let count_u = refined[0].len();
1816 net = (0..count_u)
1817 .map(|row| refined.iter().map(|column| column[row]).collect())
1818 .collect();
1819 }
1820 NurbsSurface::new(surface.degree_u, surface.degree_v, knots_u, knots_v, net).or_refuse(KernelStage::Refine, "new")
1821}
1822
1823fn refine_offset_fit(
1859 source: &NurbsSurface,
1860 evaluator: &OffsetEvaluator,
1861 distance: f64,
1862 fitted: NurbsSurface,
1863) -> Result<NurbsSurface, KernelRefusal> {
1864 let scale = crate::model_scale(
1865 source
1866 .control_points
1867 .iter()
1868 .flatten()
1869 .filter_map(|point| point.point().ok()),
1870 );
1871 let bar = crate::KernelTolerances::for_scale(scale, 1e-7).intersection_fit;
1872 let trace = std::env::var("BREP_OFFSET_FIT_TRACE").ok();
1873 let started = web_time::Instant::now();
1874 let enabled = std::env::var("BREP_OFFSET_FIT_REFINE").as_deref() != Ok("0");
1875 let Ok(initial) = offset_fit_deviation(&fitted, evaluator, distance) else {
1876 return Ok(fitted);
1877 };
1878 let mut best = fitted;
1879 let mut best_deviation = initial.clone();
1880 let mut refined_source = source.clone();
1881 let mut rounds = 0usize;
1882 let mut residual_mode = false;
1883 let mut stop = "under bar";
1884 if enabled {
1885 while best_deviation.worst() > bar {
1886 if rounds == OFFSET_FIT_REFINEMENTS {
1887 stop = "refinement limit";
1888 break;
1889 }
1890 let (along_u, along_v) = (best_deviation.along_u > bar, best_deviation.along_v > bar);
1891 let (in_u, in_v) = if along_u || along_v {
1892 (along_u, along_v)
1893 } else {
1894 (true, true)
1895 };
1896 let (raise_u, raise_v) = (in_u && refined_source.degree_u == 1, in_v && refined_source.degree_v == 1);
1897 let raised = if raise_u || raise_v {
1898 raise_linear_directions(&refined_source, raise_u, raise_v)?
1899 } else {
1900 None
1901 };
1902 let (halve_u, halve_v) = match raised {
1903 Some(_) => (in_u && !raise_u, in_v && !raise_v),
1904 None => (in_u, in_v),
1905 };
1906 let raised = raised.unwrap_or_else(|| refined_source.clone());
1907 let candidate_source = if halve_u || halve_v {
1908 if residual_mode {
1909 let (u, v) = best_deviation.refinement_sites(bar);
1910 insert_offset_fit_knots(&raised,
1911 if halve_u { &u } else { &[] }, if halve_v { &v } else { &[] })?
1912 } else {
1913 halve_knot_spans(&raised, halve_u, halve_v)?
1914 }
1915 } else {
1916 raised
1917 };
1918 let weights = candidate_source
1919 .control_points
1920 .iter()
1921 .map(|row| row.iter().map(|point| point.w).collect::<Vec<_>>())
1922 .collect::<Vec<_>>();
1923 let controls = weights.len() * weights[0].len();
1924 let ceiling = if separable_weights(&weights).is_some() {
1925 OFFSET_FIT_MAX_CONTROLS_SEPARABLE
1926 } else {
1927 OFFSET_FIT_MAX_CONTROLS_TENSOR
1928 };
1929 if controls > ceiling {
1930 stop = "net ceiling";
1931 break;
1932 }
1933 let knot_u = KnotVector::new(candidate_source.knots_u.clone(), candidate_source.degree_u).or_refuse(KernelStage::Refine, "new")?;
1934 let knot_v = KnotVector::new(candidate_source.knots_v.clone(), candidate_source.degree_v).or_refuse(KernelStage::Refine, "new")?;
1935 let parameters_u = greville_parameters(&knot_u);
1936 let parameters_v = greville_parameters(&knot_v);
1937 let samples = parameters_u
1938 .iter()
1939 .map(|&u| {
1940 parameters_v
1941 .iter()
1942 .map(|&v| Ok(evaluator.at(u, v, -distance).or_refuse(KernelStage::Refine, "at")?.point))
1943 .collect::<Result<Vec<_>, KernelRefusal>>()
1944 })
1945 .collect::<Result<Vec<_>, KernelRefusal>>();
1946 let Ok(samples) = samples else {
1947 stop = "unevaluable sample";
1948 break;
1949 };
1950 let candidate = NurbsSurface::new(
1951 candidate_source.degree_u,
1952 candidate_source.degree_v,
1953 candidate_source.knots_u.clone(),
1954 candidate_source.knots_v.clone(),
1955 interpolate_tensor(&knot_u, &knot_v, ¶meters_u, ¶meters_v, &samples, &weights)?,
1956 ).or_refuse(KernelStage::Refine, "new")?;
1957 let Ok(deviation) = offset_fit_deviation(&candidate, evaluator, distance) else {
1958 stop = "unmeasurable round";
1959 break;
1960 };
1961 rounds += 1;
1962 if deviation.worst() >= best_deviation.worst() {
1963 let first_quadratic_split = rounds == 1
1970 && ((halve_u && source.degree_u == 2 && source.knots_u.len() == 6)
1971 || (halve_v && source.degree_v == 2 && source.knots_v.len() == 6));
1972 if first_quadratic_split {
1973 refined_source = candidate_source;
1974 continue;
1975 }
1976 if !residual_mode && best_deviation.worst() > offset_construction_band(scale)
1981 && std::env::var("BREP_OFFSET_FIT_RESIDUAL").as_deref() != Ok("0")
1982 {
1983 residual_mode = true;
1984 continue;
1985 }
1986 stop = "stopped improving";
1987 break;
1988 }
1989 best = candidate;
1990 best_deviation = deviation;
1991 refined_source = candidate_source;
1992 }
1993 } else if best_deviation.worst() > bar {
1994 stop = "refinement disabled";
1995 }
1996 let band = offset_construction_band(scale);
2001 let refused = enabled && best_deviation.worst() > band;
2002 if let Some(path) = trace {
2003 use std::io::Write;
2004 let caller = std::env::args().skip(1).collect::<Vec<_>>().join(" ");
2005 let thread = std::thread::current().name().unwrap_or("-").to_string();
2006 let line = format!(
2007 "fit deg=({},{}) net=({},{})->({},{}) d={distance:.6} scale={scale:.4} bar={bar:.3e} \
2008 initial=(u {:.3e}, v {:.3e}, uv {:.3e}) final={:.3e} rounds={rounds} stop={stop} \
2009 refused={refused} seconds={:.4} thread={thread} args={caller}\n",
2010 source.degree_u,
2011 source.degree_v,
2012 source.control_points.len(),
2013 source.control_points[0].len(),
2014 best.control_points.len(),
2015 best.control_points[0].len(),
2016 initial.along_u,
2017 initial.along_v,
2018 initial.between,
2019 best_deviation.worst(),
2020 started.elapsed().as_secs_f64(),
2021 );
2022 if let Ok(mut file) = std::fs::OpenOptions::new().create(true).append(true).open(path) {
2023 let _ = file.write_all(line.as_bytes());
2024 }
2025 }
2026 if refused {
2027 return Err(KernelRefusal::non_convergence(KernelStage::Refine, "offset_carrier_fit", format!(
2028 "offset_surface: the fitted offset carrier stays {:.3e} off its pointwise offset at \
2029 distance {distance} after {rounds} refinement round(s) ({stop}), past the offset \
2030 construction band {band:.3e}",
2031 best_deviation.worst()
2032 )));
2033 }
2034 Ok(best)
2035}
2036
2037pub(crate) fn unify_offset_sheet_bases(
2047 first: &NurbsSurface,
2048 second: &NurbsSurface,
2049) -> Result<(NurbsSurface, NurbsSurface), KernelRefusal> {
2050 fn raise_to(surface: &NurbsSurface, degree_u: usize, degree_v: usize) -> Result<NurbsSurface, KernelRefusal> {
2051 let raise_u = surface.degree_u == 1 && degree_u == 3;
2052 let raise_v = surface.degree_v == 1 && degree_v == 3;
2053 if !raise_u && !raise_v {
2054 return Ok(surface.clone());
2055 }
2056 raise_linear_directions(surface, raise_u, raise_v)?
2057 .ok_or_else(|| {
2058 KernelRefusal::internal(
2059 KernelStage::Refine,
2060 "offset_raise_linear",
2061 "offset sheets: a linear direction could not be raised",
2062 )
2063 })
2064 }
2065 let degree_u = first.degree_u.max(second.degree_u);
2066 let degree_v = first.degree_v.max(second.degree_v);
2067 let mut first = raise_to(first, degree_u, degree_v)?;
2068 let mut second = raise_to(second, degree_u, degree_v)?;
2069 if first.degree_u != second.degree_u || first.degree_v != second.degree_v {
2070 return Err(KernelRefusal::internal(KernelStage::Refine, "offset_common_basis", format!(
2071 "offset sheets: degrees ({},{}) and ({},{}) have no common basis",
2072 first.degree_u, first.degree_v, second.degree_u, second.degree_v
2073 )));
2074 }
2075 fn missing(from: &[f64], into: &[f64]) -> Vec<f64> {
2077 let mut extra = Vec::new();
2078 let mut index = 0usize;
2079 for &knot in from {
2080 while index < into.len() && into[index] < knot - 1e-12 {
2081 index += 1;
2082 }
2083 if index < into.len() && (into[index] - knot).abs() <= 1e-12 {
2084 index += 1;
2085 } else {
2086 extra.push(knot);
2087 }
2088 }
2089 extra
2090 }
2091 fn insert(surface: &NurbsSurface, knots: &[f64], along_u: bool) -> Result<NurbsSurface, KernelRefusal> {
2092 if knots.is_empty() {
2093 return Ok(surface.clone());
2094 }
2095 let (degree, vector) = if along_u {
2096 (surface.degree_u, &surface.knots_u)
2097 } else {
2098 (surface.degree_v, &surface.knots_v)
2099 };
2100 let lines = if along_u {
2101 (0..surface.control_points[0].len())
2102 .map(|column| surface.control_points.iter().map(|row| row[column]).collect::<Vec<_>>())
2103 .collect::<Vec<_>>()
2104 } else {
2105 surface.control_points.clone()
2106 };
2107 let mut refined_knots = vector.clone();
2108 let mut refined = Vec::with_capacity(lines.len());
2109 for line in lines {
2110 let mut curve = NurbsCurve::new(degree, vector.clone(), line).or_refuse(KernelStage::Refine, "new")?;
2111 for &knot in knots {
2112 curve = curve.insert_knot(knot, 1).or_refuse(KernelStage::Refine, "insert_knot")?;
2113 }
2114 refined_knots = curve.knots.clone();
2115 refined.push(curve.control_points);
2116 }
2117 let net = if along_u {
2118 (0..refined[0].len())
2119 .map(|row| refined.iter().map(|column| column[row]).collect())
2120 .collect()
2121 } else {
2122 refined
2123 };
2124 let (knots_u, knots_v) = if along_u {
2125 (refined_knots, surface.knots_v.clone())
2126 } else {
2127 (surface.knots_u.clone(), refined_knots)
2128 };
2129 NurbsSurface::new(surface.degree_u, surface.degree_v, knots_u, knots_v, net).or_refuse(KernelStage::Refine, "new")
2130 }
2131 let (to_first_u, to_second_u) = (
2132 missing(&second.knots_u, &first.knots_u),
2133 missing(&first.knots_u, &second.knots_u),
2134 );
2135 first = insert(&first, &to_first_u, true)?;
2136 second = insert(&second, &to_second_u, true)?;
2137 let (to_first_v, to_second_v) = (
2138 missing(&second.knots_v, &first.knots_v),
2139 missing(&first.knots_v, &second.knots_v),
2140 );
2141 first = insert(&first, &to_first_v, false)?;
2142 second = insert(&second, &to_second_v, false)?;
2143 Ok((first, second))
2144}
2145
2146fn carrier_edge_curve(
2168 surface: &NurbsSurface,
2169 pcurve: &NurbsCurve,
2170 points: &[Vec3],
2171 parameters: &[f64],
2172 fit_tolerance: f64,
2173) -> Result<(NurbsCurve, f64, f64), KernelRefusal> {
2174 if affine_image_trusted() && surface.is_affine().or_refuse(KernelStage::Refine, "is_affine")? {
2182 let [q0, q1] = pcurve.domain().or_refuse(KernelStage::Refine, "domain")?;
2183 if (q1 - q0).is_finite() && (q1 - q0).abs() > 0.0 {
2184 let curve = crate::image_curve::affine_image_curve(surface, pcurve).or_refuse(KernelStage::Refine, "affine_image_curve")?;
2185 return Ok((curve, q0, q1));
2186 }
2187 }
2188 let image = if env_read!("BREP_CARRIER_POLYLINE").as_deref() == Some("1") {
2189 Err("BREP_CARRIER_POLYLINE set".to_string())
2190 } else {
2191 crate::image_curve::image_curve(surface, pcurve, fit_tolerance, "offset_face_carrier")
2192 };
2193 match image {
2194 Ok(image) if image.t0 <= image.t1 => Ok((image.curve, image.t0, image.t1)),
2195 Ok(image) => {
2196 let [start, end] = image.curve.domain().or_refuse(KernelStage::Refine, "domain")?;
2199 let curve = image.curve.reversed().or_refuse(KernelStage::Refine, "reversed")?;
2200 Ok((curve, start + end - image.t0, start + end - image.t1))
2201 }
2202 Err(_) => {
2203 let curve = interpolate_curve(points, 1, parameters).or_refuse(KernelStage::Refine, "interpolate_curve")?;
2204 let [t0, t1] = curve.domain().or_refuse(KernelStage::Refine, "domain")?;
2205 Ok((curve, t0, t1))
2206 }
2207 }
2208}
2209
2210fn affine_image_trusted() -> bool {
2211 switch!("BREP_CARRIER_AFFINE_IMAGE", true)
2212}
2213
2214
2215fn lazy_carrier_trace(
2223 surface: &NurbsSurface,
2224 pcurve: &NurbsCurve,
2225 collapse_tolerance: f64,
2226 fit_tolerance: f64,
2227) -> Option<(Vec<Vec3>, (NurbsCurve, f64, f64))> {
2228 if !switch!("BREP_OFFSET_LAZY_CARRIER_TRACE", true) {
2229 return None;
2230 }
2231 if pcurve.degree == 1 && pcurve.control_points.len() == 2 {
2234 let (a, b) = (pcurve.control_points[0], pcurve.control_points[1]);
2235 if (surface.degree_u <= 1 && surface.degree_v <= 1)
2236 || (a.w == b.w && a.y == b.y && surface.degree_u <= 1)
2237 || (a.w == b.w && a.x == b.x && surface.degree_v <= 1)
2238 {
2239 return None;
2240 }
2241 }
2242 fn knots_ok(knots: &[f64], degree: usize, count: usize) -> bool {
2243 degree <= 3 && count <= 64
2244 && KnotVector::new(knots.to_vec(), degree).ok().is_some_and(|k| k.control_point_count() == count)
2245 && knots.iter().all(|k| k.is_finite() && k.abs() <= 1e6)
2246 && knots.windows(2).all(|k| k[0] == k[1] || k[1] - k[0] >= 1e-6)
2247 }
2248 let bounded = |p: &Vec4| (1e-3..=1e3).contains(&p.w)
2249 && [p.x, p.y, p.z].iter().all(|x| x.is_finite() && x.abs() <= 1e12);
2250 let columns = surface.control_points.first()?.len();
2251 if !knots_ok(&surface.knots_u, surface.degree_u, surface.control_points.len())
2252 || !knots_ok(&surface.knots_v, surface.degree_v, columns)
2253 || surface.control_points.iter().any(|row| row.len() != columns || row.iter().any(|p| !bounded(p)))
2254 || !knots_ok(&pcurve.knots, pcurve.degree, pcurve.control_points.len())
2255 || pcurve.control_points.iter().any(|p| !bounded(p))
2256 {
2257 return None;
2258 }
2259 let ([u0, u1], [v0, v1]) = (surface.domain_u().ok()?, surface.domain_v().ok()?);
2260 let uv = pcurve.control_points.iter().map(|p| p.point().ok()).collect::<Option<Vec<_>>>()?;
2261 if uv.iter().any(|p| p.x < u0 || p.x > u1 || p.y < v0 || p.y > v1) {
2262 return None;
2263 }
2264 if !surface.is_affine().ok()? && !uv.iter().all(|p| p.x == uv[0].x) && !uv.iter().all(|p| p.y == uv[0].y) {
2266 return None;
2267 }
2268 let [start, end] = pcurve.domain().ok()?;
2269 let evaluate = |fraction: f64| {
2270 let uv = pcurve.evaluate(start + (end - start) * fraction).ok()?;
2271 surface.evaluate(uv.x, uv.y).ok()
2272 };
2273 let first = evaluate(0.0)?;
2274 let last = evaluate(1.0)?;
2275 let samples = [evaluate(0.25)?, evaluate(0.5)?, evaluate(0.75)?];
2276 let deviation = samples.iter().enumerate().map(|(index, point)| {
2277 point.sub(first.add(last.sub(first).scale((index + 1) as f64 * 0.25))).length()
2278 }).fold(0.0, f64::max);
2279 if last.sub(first).length() <= collapse_tolerance
2280 && !(deviation > 5e-4 && samples[1].sub(first).length() > collapse_tolerance)
2281 {
2282 return None;
2283 }
2284 let image = carrier_edge_curve(surface, pcurve, &[], &[], fit_tolerance).ok()?;
2287 Some((vec![first, samples[1], last], image))
2288}
2289
2290fn mapped_pcurve_polyline(
2291 surface: &NurbsSurface,
2292 pcurve: &NurbsCurve,
2293 degenerate: bool,
2294) -> Result<(Vec<Vec3>, Vec<f64>), KernelRefusal> {
2295 let [start, end] = pcurve.domain().or_refuse(KernelStage::Refine, "domain")?;
2296 let evaluate = |fraction: f64| -> Result<Vec3, KernelRefusal> {
2297 let uv = pcurve.evaluate(start + (end - start) * fraction).or_refuse(KernelStage::Refine, "evaluate")?;
2298 surface.evaluate(uv.x, uv.y).or_refuse(KernelStage::Refine, "evaluate")
2299 };
2300 let first = evaluate(0.0)?;
2301 let last = evaluate(1.0)?;
2302 if degenerate {
2303 return Ok((vec![first, last], vec![0.0, 1.0]));
2304 }
2305 fn append(
2306 evaluate: &impl Fn(f64) -> Result<Vec3, KernelRefusal>,
2307 a_fraction: f64,
2308 a: Vec3,
2309 b_fraction: f64,
2310 b: Vec3,
2311 depth: usize,
2312 parameters: &mut Vec<f64>,
2313 points: &mut Vec<Vec3>,
2314 ) -> Result<(), KernelRefusal> {
2315 let fractions =
2316 [0.25, 0.5, 0.75].map(|local| a_fraction + (b_fraction - a_fraction) * local);
2317 let samples = fractions
2318 .map(evaluate)
2319 .into_iter()
2320 .collect::<Result<Vec<_>, KernelRefusal>>()?;
2321 let deviation = samples
2322 .iter()
2323 .enumerate()
2324 .map(|(index, point)| {
2325 point
2326 .sub(a.add(b.sub(a).scale((index + 1) as f64 * 0.25)))
2327 .length()
2328 })
2329 .fold(0.0, f64::max);
2330 if deviation <= 5e-4 || depth >= 10 {
2331 parameters.push(b_fraction);
2332 points.push(b);
2333 return Ok(());
2334 }
2335 append(
2336 evaluate,
2337 a_fraction,
2338 a,
2339 fractions[1],
2340 samples[1],
2341 depth + 1,
2342 parameters,
2343 points,
2344 )?;
2345 append(
2346 evaluate,
2347 fractions[1],
2348 samples[1],
2349 b_fraction,
2350 b,
2351 depth + 1,
2352 parameters,
2353 points,
2354 )
2355 }
2356 let mut parameters = vec![0.0];
2357 let mut points = vec![first];
2358 append(
2359 &evaluate,
2360 0.0,
2361 first,
2362 1.0,
2363 last,
2364 0,
2365 &mut parameters,
2366 &mut points,
2367 )?;
2368 Ok((points, parameters))
2369}
2370
2371#[derive(Clone, Debug)]
2385pub struct CarrierDeviation {
2386 pub band: f64,
2389 pub lane: OffsetSurfaceLane,
2391 pub surface: Option<MeasuredTolerance>,
2393 pub edges: Vec<(u64, MeasuredTolerance)>,
2398 pub vertices: Vec<(u64, f64)>,
2402}
2403
2404impl CarrierDeviation {
2405 pub fn worst(&self) -> Option<MeasuredTolerance> {
2408 MeasuredTolerance::worst(
2409 self.surface
2410 .into_iter()
2411 .chain(self.edges.iter().map(|(_, measured)| *measured))
2412 .chain(
2413 self.vertices
2414 .iter()
2415 .map(|(_, gap)| MeasuredTolerance::new(*gap, self.band)),
2416 ),
2417 )
2418 }
2419
2420 pub fn exceedances(&self) -> Vec<String> {
2423 let mut out = Vec::new();
2424 if let Some(surface) = self.surface {
2425 if surface.exceeds_band() {
2426 out.push(format!("carrier surface fit {}", surface.describe()));
2427 }
2428 }
2429 for (id, measured) in &self.edges {
2430 if measured.exceeds_band() {
2431 out.push(format!("edge {id} {}", measured.describe()));
2432 }
2433 }
2434 for (id, gap) in &self.vertices {
2435 let measured = MeasuredTolerance::new(*gap, self.band);
2436 if measured.exceeds_band() {
2437 out.push(format!("vertex {id} {}", measured.describe()));
2438 }
2439 }
2440 out
2441 }
2442}
2443
2444#[derive(Clone, Debug, Serialize)]
2445pub struct OffsetFaceCarrier {
2446 pub vertices: Vec<VertexRecord>,
2447 pub edges: Vec<EdgeRecord>,
2448 pub face: FaceRecord,
2449 #[serde(skip)]
2457 pub deviation: Option<CarrierDeviation>,
2458 #[serde(skip)]
2462 pub lane: OffsetSurfaceLane,
2463}
2464
2465fn claim_vertex_image(
2476 source_id: u64,
2477 point: Vec3,
2478 split: f64,
2479 vertex_images: &mut HashMap<u64, Vec<u64>>,
2480 vertices: &mut Vec<VertexRecord>,
2481 next_id: &mut u64,
2482) -> u64 {
2483 if let Some(ids) = vertex_images.get(&source_id) {
2484 let near = ids.iter().copied().find(|id| {
2485 vertices
2486 .iter()
2487 .find(|vertex| vertex.id == *id)
2488 .is_some_and(|vertex| vertex.point.sub(point).length() <= split)
2489 });
2490 if let Some(id) = near {
2491 return id;
2492 }
2493 }
2494 let id = *next_id;
2495 *next_id += 1;
2496 vertices.push(VertexRecord { id, point });
2497 vertex_images.entry(source_id).or_default().push(id);
2498 id
2499}
2500
2501pub fn offset_face_carrier(
2502 solid: &BrepSolid,
2503 face_id: u64,
2504 distance: f64,
2505 planar_extension: f64,
2506) -> Result<OffsetFaceCarrier, KernelRefusal> {
2507 offset_face_carrier_impl(
2508 solid,
2509 face_id,
2510 distance,
2511 &CarrierExtension::uniform(planar_extension),
2512 false,
2513 )
2514}
2515
2516pub fn offset_face_carrier_sided(
2518 solid: &BrepSolid,
2519 face_id: u64,
2520 distance: f64,
2521 extension: &CarrierExtension,
2522) -> Result<OffsetFaceCarrier, KernelRefusal> {
2523 offset_face_carrier_impl(solid, face_id, distance, extension, false)
2524}
2525
2526pub fn offset_face_carrier_measured(
2546 solid: &BrepSolid,
2547 face_id: u64,
2548 distance: f64,
2549 planar_extension: f64,
2550) -> Result<OffsetFaceCarrier, KernelRefusal> {
2551 offset_face_carrier_impl(
2552 solid,
2553 face_id,
2554 distance,
2555 &CarrierExtension::uniform(planar_extension),
2556 true,
2557 )
2558}
2559
2560fn measure_carrier(
2571 surface: &NurbsSurface,
2572 vertices: &[VertexRecord],
2573 edges: &[EdgeRecord],
2574 loops: &[LoopRecord],
2575 lane: OffsetSurfaceLane,
2576 surface_fit: Option<MeasuredTolerance>,
2577 band: f64,
2578) -> Result<CarrierDeviation, KernelRefusal> {
2579 let edge_by_id: HashMap<u64, &EdgeRecord> = edges.iter().map(|edge| (edge.id, edge)).collect();
2580 let mut per_edge: HashMap<u64, MeasuredTolerance> = HashMap::default();
2584 for loop_record in loops {
2585 for coedge in &loop_record.coedges {
2586 let Some(edge) = edge_by_id.get(&coedge.edge_id) else {
2587 continue;
2588 };
2589 let measured = measure_edge_against_pcurve_image(
2590 surface,
2591 &coedge.pcurve,
2592 edge,
2593 coedge.forward,
2594 band,
2595 )?;
2596 per_edge
2597 .entry(edge.id)
2598 .and_modify(|existing| *existing = existing.worse_of(measured))
2599 .or_insert(measured);
2600 }
2601 }
2602
2603 let mut measured_edges: Vec<(u64, MeasuredTolerance)> = per_edge.into_iter().collect();
2604 measured_edges.sort_by_key(|(id, _)| *id);
2605 let deviation_of: HashMap<u64, f64> = measured_edges
2606 .iter()
2607 .map(|(id, measured)| (*id, measured.deviation()))
2608 .collect();
2609
2610 let mut ends_at: HashMap<u64, Vec<(&EdgeRecord, f64)>> = HashMap::default();
2614 for edge in edges {
2615 ends_at
2616 .entry(edge.start_vertex_id)
2617 .or_default()
2618 .push((edge, edge.t0));
2619 ends_at
2620 .entry(edge.end_vertex_id)
2621 .or_default()
2622 .push((edge, edge.t1));
2623 }
2624
2625 let mut measured_vertices = Vec::with_capacity(vertices.len());
2626 for vertex in vertices {
2627 let mut gaps = Vec::new();
2628 let mut incident = Vec::new();
2629 for (edge, parameter) in ends_at.get(&vertex.id).into_iter().flatten() {
2630 gaps.push(vertex_endpoint_gap(
2631 vertex.point,
2632 edge.curve.evaluate(*parameter).or_refuse(KernelStage::Refine, "evaluate")?,
2633 ));
2634 incident.push(deviation_of.get(&edge.id).copied().unwrap_or(0.0));
2635 }
2636 measured_vertices.push((vertex.id, vertex_tolerance_from_edges(gaps, incident)));
2637 }
2638
2639 Ok(CarrierDeviation {
2640 band,
2641 lane,
2642 surface: surface_fit,
2643 edges: measured_edges,
2644 vertices: measured_vertices,
2645 })
2646}
2647
2648fn offset_face_carrier_impl(
2649 solid: &BrepSolid,
2650 face_id: u64,
2651 distance: f64,
2652 extension: &CarrierExtension,
2653 measure: bool,
2654) -> Result<OffsetFaceCarrier, KernelRefusal> {
2655 let source = solid
2656 .shells
2657 .iter()
2658 .flat_map(|shell| &shell.faces)
2659 .find(|face| face.id == face_id)
2660 .ok_or_else(|| format!("offset_face_carrier: missing face {face_id}")).or_refuse(KernelStage::Refine, "offset_missing_face")?;
2661 let band = offset_construction_band(solid_model_scale(solid));
2669 let fit_tolerance =
2676 crate::KernelTolerances::for_scale(solid_model_scale(solid), 1e-7).intersection_fit;
2677 let (surface, lane, surface_fit) = if measure {
2678 let measured = offset_surface_measured_sided(source, distance, extension, band)?;
2679 (measured.surface, measured.lane, measured.fit)
2680 } else {
2681 let (surface, lane) = offset_surface_with_lane(source, distance, extension)?;
2682 (surface, lane, None)
2683 };
2684 let source_edges = solid
2685 .edges
2686 .iter()
2687 .map(|edge| (edge.id, edge))
2688 .collect::<HashMap<_, _>>();
2689 let source_vertices = solid
2690 .vertices
2691 .iter()
2692 .map(|vertex| (vertex.id, vertex))
2693 .collect::<HashMap<_, _>>();
2694 let mut vertices = Vec::new();
2695 let mut vertex_images = HashMap::default();
2696 let vertex_split = (distance.abs() * 0.1).max(band);
2700 let mut edges = Vec::new();
2701 let mut edge_images = HashMap::default();
2702 let mut loops = Vec::new();
2703 let mut next_id = 1u64;
2704
2705 for source_loop in &source.loops {
2706 let mut coedges = Vec::new();
2707 for source_coedge in &source_loop.coedges {
2708 let source_edge = source_edges
2709 .get(&source_coedge.edge_id)
2710 .ok_or_else(|| "offset_face_carrier: missing source edge".to_string()).or_refuse(KernelStage::Refine, "offset_missing_edge")?;
2711 let (source_start, source_end) = if source_coedge.forward {
2712 (source_edge.start_vertex_id, source_edge.end_vertex_id)
2713 } else {
2714 (source_edge.end_vertex_id, source_edge.start_vertex_id)
2715 };
2716 if !source_vertices.contains_key(&source_start)
2717 || !source_vertices.contains_key(&source_end)
2718 {
2719 return Err(KernelRefusal::internal(KernelStage::Refine, "offset_missing_vertex", "offset_face_carrier: missing source vertex"));
2720 }
2721 let collapse_tolerance = 1e-6f64.max(distance.abs() * 1e-2);
2739 let (points, parameters, exact_image) = match lazy_carrier_trace(
2740 &surface, &source_coedge.pcurve, collapse_tolerance, fit_tolerance,
2741 ) {
2742 Some((points, image)) => (points, Vec::new(), Some(image)),
2743 None => {
2744 let (points, parameters) = mapped_pcurve_polyline(&surface, &source_coedge.pcurve, false)?;
2745 (points, parameters, None)
2746 }
2747 };
2748 let image_collapsed = points
2749 .iter()
2750 .all(|point| point.sub(points[0]).length() <= collapse_tolerance);
2751 let (edge_id, forward) =
2752 if let Some((edge_id, edge_start_vertex_id, creator_forward)) =
2753 edge_images.get(&source_edge.id)
2754 {
2755 if source_start == source_end {
2756 (*edge_id, source_coedge.forward == *creator_forward)
2779 } else {
2780 (
2783 *edge_id,
2784 vertex_images
2785 .get(&source_start)
2786 .is_some_and(|ids: &Vec<u64>| ids.contains(edge_start_vertex_id)),
2787 )
2788 }
2789 } else {
2790 let (curve, t0, t1) = if image_collapsed {
2791 let curve = NurbsCurve::new(
2792 1,
2793 vec![0.0, 0.0, 1.0, 1.0],
2794 vec![
2795 Vec4::from_point(points[0], 1.0),
2796 Vec4::from_point(points[0], 1.0),
2797 ],
2798 ).or_refuse(KernelStage::Refine, "new")?;
2799 (curve, 0.0, 1.0)
2800 } else if let Some(image) = exact_image {
2801 image
2802 } else {
2803 carrier_edge_curve(
2804 &surface,
2805 &source_coedge.pcurve,
2806 &points,
2807 ¶meters,
2808 fit_tolerance,
2809 )?
2810 };
2811 let start_vertex_id = claim_vertex_image(
2812 source_start,
2813 points[0],
2814 vertex_split,
2815 &mut vertex_images,
2816 &mut vertices,
2817 &mut next_id,
2818 );
2819 let end_vertex_id = claim_vertex_image(
2820 source_end,
2821 points[points.len() - 1],
2822 vertex_split,
2823 &mut vertex_images,
2824 &mut vertices,
2825 &mut next_id,
2826 );
2827 let id = next_id;
2828 next_id += 1;
2829 edges.push(EdgeRecord {
2830 id,
2831 curve,
2832 t0,
2833 t1,
2834 start_vertex_id,
2835 end_vertex_id,
2836 degenerate: image_collapsed,
2850 name: source_edge
2854 .name
2855 .as_ref()
2856 .map(|name| format!("{name}_Offset")),
2857 });
2858 edge_images.insert(
2859 source_edge.id,
2860 (id, start_vertex_id, source_coedge.forward),
2861 );
2862 (id, true)
2863 };
2864 let id = next_id;
2865 next_id += 1;
2866 coedges.push(CoedgeRecord {
2867 id,
2868 edge_id,
2869 forward,
2870 pcurve: source_coedge.pcurve.clone(),
2871 });
2872 }
2873 let id = next_id;
2874 next_id += 1;
2875 loops.push(LoopRecord { id, coedges });
2876 }
2877 let deviation = if measure {
2878 Some(measure_carrier(
2879 &surface,
2880 &vertices,
2881 &edges,
2882 &loops,
2883 lane,
2884 surface_fit,
2885 band,
2886 )?)
2887 } else {
2888 None
2889 };
2890 Ok(OffsetFaceCarrier {
2891 vertices,
2892 edges,
2893 face: FaceRecord {
2894 id: next_id,
2895 surface,
2896 same_sense: source.same_sense,
2897 loops,
2898 name: source.name.as_ref().map(|name| format!("{name}_Offset")),
2899 },
2900 deviation,
2901 lane,
2902 })
2903}
2904
2905
2906
2907