1use crate::analytic_surface::circumcenter;
2use crate::mass_properties::{face_area, face_volume_contribution, parameter_space_area};
3use crate::topology::{BrepSolid, CoedgeRecord, EdgeRecord, FaceRecord, LoopRecord};
4use crate::{
5 build_pcurve_on_surface, make_line, make_plane, make_revolution, KnotVector, NurbsCurve,
6 NurbsSurface, Vec3, Vec4,
7};
8use crate::{KernelRefusal, KernelStage, OrRefuse, RefusalClass};
9use rustc_hash::{FxHashMap as HashMap, FxHashSet as HashSet};
10
11fn controls_match(first: Vec4, second: Vec4, tolerance: f64) -> bool {
12 (first.x - second.x).abs() <= tolerance
13 && (first.y - second.y).abs() <= tolerance
14 && (first.z - second.z).abs() <= tolerance
15 && (first.w - second.w).abs() <= tolerance
16}
17
18pub(crate) fn same_surface(first: &NurbsSurface, second: &NurbsSurface, tolerance: f64) -> bool {
24 first.degree_u == second.degree_u
25 && first.degree_v == second.degree_v
26 && first.knots_u.len() == second.knots_u.len()
27 && first.knots_v.len() == second.knots_v.len()
28 && first.control_points.len() == second.control_points.len()
29 && first
30 .control_points
31 .iter()
32 .zip(&second.control_points)
33 .all(|(a, b)| {
34 a.len() == b.len()
35 && a.iter()
36 .zip(b)
37 .all(|(a, b)| controls_match(*a, *b, tolerance))
38 })
39 && first
40 .knots_u
41 .iter()
42 .zip(&second.knots_u)
43 .all(|(a, b)| (a - b).abs() <= tolerance)
44 && first
45 .knots_v
46 .iter()
47 .zip(&second.knots_v)
48 .all(|(a, b)| (a - b).abs() <= tolerance)
49}
50
51fn surface_domains(surface: &NurbsSurface) -> Result<([f64; 2], [f64; 2]), KernelRefusal> {
52 Ok((
53 KnotVector::new(surface.knots_u.clone(), surface.degree_u)
54 .or_refuse(KernelStage::Sew, "new")?
55 .domain(),
56 KnotVector::new(surface.knots_v.clone(), surface.degree_v)
57 .or_refuse(KernelStage::Sew, "new")?
58 .domain(),
59 ))
60}
61
62fn outward_normal(face: &FaceRecord) -> Result<Vec3, KernelRefusal> {
63 let (u, v) = surface_domains(&face.surface)?;
64 let normal = face
65 .surface
66 .normal((u[0] + u[1]) / 2.0, (v[0] + v[1]) / 2.0)
67 .or_refuse(KernelStage::Sew, "healing.face_merge")?;
68 Ok(if face.same_sense {
69 normal
70 } else {
71 normal.scale(-1.0)
72 })
73}
74
75fn planar_support(
76 face: &FaceRecord,
77 tolerance: f64,
78) -> Result<Option<(Vec3, Vec3)>, KernelRefusal> {
79 let (u, v) = surface_domains(&face.surface)?;
80 let midpoint_u = (u[0] + u[1]) / 2.0;
81 let midpoint_v = (v[0] + v[1]) / 2.0;
82 let origin = face
83 .surface
84 .evaluate(midpoint_u, midpoint_v)
85 .or_refuse(KernelStage::Sew, "evaluate")?;
86 let normal = face
87 .surface
88 .normal(midpoint_u, midpoint_v)
89 .or_refuse(KernelStage::Sew, "normal")?;
90 let controls = face
91 .surface
92 .control_points
93 .iter()
94 .flatten()
95 .map(|control| control.point())
96 .collect::<Result<Vec<_>, _>>()
97 .or_refuse(KernelStage::Sew, "healing.face_merge")?;
98 let scale = controls
99 .iter()
100 .map(|point| point.sub(origin).length())
101 .fold(1.0f64, f64::max);
102 let plane_tolerance = (tolerance * 100.0).max(1e-7) * scale;
103 if controls
104 .iter()
105 .all(|point| point.sub(origin).dot(normal).abs() <= plane_tolerance)
106 {
107 Ok(Some((origin, normal)))
108 } else {
109 Ok(None)
110 }
111}
112
113fn coplanar_with_same_outward_normal(
114 first: &FaceRecord,
115 second: &FaceRecord,
116 tolerance: f64,
117) -> Result<bool, KernelRefusal> {
118 let Some((first_origin, first_geometric_normal)) = planar_support(first, tolerance)? else {
119 return Ok(false);
120 };
121 let Some((_, second_geometric_normal)) = planar_support(second, tolerance)? else {
122 return Ok(false);
123 };
124 if first_geometric_normal.dot(second_geometric_normal).abs() < 1.0 - 1e-7 {
125 return Ok(false);
126 }
127 let first_normal = outward_normal(first)?;
128 let second_normal = outward_normal(second)?;
129 if first_normal.dot(second_normal) < 1.0 - 1e-7 {
130 return Ok(false);
131 }
132 let (second_u, second_v) = surface_domains(&second.surface)?;
133 let plane_tolerance = (tolerance * 100.0)
148 .max(1e-6)
149 .min(crate::tolerance::assembler_weld(tolerance));
150 for u in second_u {
151 for v in second_v {
152 if second
153 .surface
154 .evaluate(u, v)
155 .or_refuse(KernelStage::Sew, "evaluate")?
156 .sub(first_origin)
157 .dot(first_normal)
158 .abs()
159 > plane_tolerance
160 {
161 return Ok(false);
162 }
163 }
164 }
165 Ok(true)
166}
167
168fn arc_circle_support(
172 curve: &NurbsCurve,
173 tolerance: f64,
174) -> Result<Option<(Vec3, Vec3, f64)>, KernelRefusal> {
175 let [t0, t1] = curve.domain().or_refuse(KernelStage::Sew, "domain")?;
176 let samples = (0..=8)
177 .map(|index| curve.evaluate(t0 + (t1 - t0) * index as f64 / 8.0))
178 .collect::<Result<Vec<_>, _>>()
179 .or_refuse(KernelStage::Sew, "healing.face_merge")?;
180 let Some(center) = circumcenter(samples[0], samples[2], samples[5])
184 .or_else(|| circumcenter(samples[0], samples[4], samples[8]))
185 .or_else(|| circumcenter(samples[1], samples[4], samples[7]))
186 else {
187 return Ok(None);
188 };
189 let radius = samples[0].sub(center).length();
190 if radius <= tolerance {
191 return Ok(None);
192 }
193 let normal = match samples[2]
194 .sub(samples[0])
195 .cross(samples[5].sub(samples[0]))
196 .normalized()
197 .or_else(|_| {
198 samples[4]
199 .sub(samples[0])
200 .cross(samples[8].sub(samples[0]))
201 .normalized()
202 }) {
203 Ok(normal) => normal,
204 Err(_) => return Ok(None),
205 };
206 let band = tolerance.max(1e-9 * radius);
207 for sample in &samples {
208 let delta = sample.sub(center);
209 if (delta.length() - radius).abs() > band || delta.dot(normal).abs() > band {
210 if std::env::var("BREP_DEBUG_MERGE").is_ok() {
211 eprintln!(
212 " arc reject: radius={radius} dr={} dplane={} band={band}",
213 (delta.length() - radius).abs(),
214 delta.dot(normal).abs()
215 );
216 }
217 return Ok(None);
218 }
219 }
220 Ok(Some((center, normal, radius)))
221}
222
223struct CylinderSupport {
224 origin: Vec3,
225 axis: Vec3,
226 radius: f64,
227 outward_radial_sign: f64,
230}
231
232fn ruled_cylinder_support(
237 face: &FaceRecord,
238 tolerance: f64,
239) -> Result<Option<CylinderSupport>, KernelRefusal> {
240 let surface = &face.surface;
241 let debug = std::env::var("BREP_DEBUG_MERGE").is_ok();
242 let (arc_first, columns) = match (surface.degree_u, surface.degree_v) {
243 (2, 1) => (true, surface.control_points[0].len()),
244 (1, 2) => (false, surface.control_points.len()),
245 _ => {
246 if debug {
247 eprintln!(
248 " support face {}: degrees ({},{}) not ruled-arc",
249 face.id, surface.degree_u, surface.degree_v
250 );
251 }
252 return Ok(None);
253 }
254 };
255 let last = columns - 1;
259 let iso_curve = |side: usize| -> Result<NurbsCurve, KernelRefusal> {
260 let controls = if arc_first {
261 surface
262 .control_points
263 .iter()
264 .map(|row| row[side])
265 .collect::<Vec<_>>()
266 } else {
267 surface.control_points[side].clone()
268 };
269 let knots = if arc_first {
270 surface.knots_u.clone()
271 } else {
272 surface.knots_v.clone()
273 };
274 NurbsCurve::new(2, knots, controls).or_refuse(KernelStage::Sew, "NurbsCurve::new")
275 };
276 let scale = surface
277 .control_points
278 .iter()
279 .flatten()
280 .map(|point| point.point().map(|p| p.length()).unwrap_or(0.0))
281 .fold(1.0f64, f64::max);
282 let circle_tolerance = (tolerance * 100.0).max(1e-7 * scale);
283 let Some((center0, normal0, radius0)) = arc_circle_support(&iso_curve(0)?, circle_tolerance)?
284 else {
285 if debug {
286 eprintln!(" support face {}: first iso not circular", face.id);
287 }
288 return Ok(None);
289 };
290 let Some((center1, normal1, radius1)) =
291 arc_circle_support(&iso_curve(last)?, circle_tolerance)?
292 else {
293 if debug {
294 eprintln!(" support face {}: last iso not circular", face.id);
295 }
296 return Ok(None);
297 };
298 if (radius0 - radius1).abs() > circle_tolerance {
299 if debug {
300 eprintln!(
301 " support face {}: radii differ {} vs {}",
302 face.id, radius0, radius1
303 );
304 }
305 return Ok(None);
306 }
307 let axial = center1.sub(center0);
308 if axial.length() <= circle_tolerance {
309 if debug {
310 eprintln!(" support face {}: zero axial extent", face.id);
311 }
312 return Ok(None);
313 }
314 let axis = axial
315 .normalized()
316 .or_refuse(KernelStage::Sew, "normalized")?;
317 if axis.dot(normal0).abs() < 1.0 - 1e-7 || axis.dot(normal1).abs() < 1.0 - 1e-7 {
318 if debug {
319 eprintln!(
320 " support face {}: arc planes not perpendicular to axis",
321 face.id
322 );
323 }
324 return Ok(None);
325 }
326 let outward = outward_normal(face)?;
327 let (u, v) = surface_domains(surface)?;
328 let midpoint = surface
329 .evaluate((u[0] + u[1]) / 2.0, (v[0] + v[1]) / 2.0)
330 .or_refuse(KernelStage::Sew, "healing.face_merge")?;
331 let foot = center0.add(axis.scale(midpoint.sub(center0).dot(axis)));
332 let radial = match midpoint.sub(foot).normalized() {
333 Ok(radial) => radial,
334 Err(_) => return Ok(None),
335 };
336 let alignment = outward.dot(radial);
337 if alignment.abs() < 0.9 {
338 if debug {
339 eprintln!(
340 " support face {}: outward not radial ({alignment})",
341 face.id
342 );
343 }
344 return Ok(None);
345 }
346 Ok(Some(CylinderSupport {
347 origin: center0,
348 axis,
349 radius: radius0,
350 outward_radial_sign: alignment.signum(),
351 }))
352}
353
354fn cosurface_cylinder_pair(
355 first: &FaceRecord,
356 second: &FaceRecord,
357 tolerance: f64,
358) -> Result<Option<CylinderSupport>, KernelRefusal> {
359 let debug = std::env::var("BREP_DEBUG_MERGE").is_ok();
360 let Some(support_a) = ruled_cylinder_support(first, tolerance)? else {
361 if debug {
362 eprintln!(
363 "merge {}x{}: first not a ruled cylinder",
364 first.id, second.id
365 );
366 }
367 return Ok(None);
368 };
369 let Some(support_b) = ruled_cylinder_support(second, tolerance)? else {
370 if debug {
371 eprintln!(
372 "merge {}x{}: second not a ruled cylinder",
373 first.id, second.id
374 );
375 }
376 return Ok(None);
377 };
378 let scale = 1.0f64
379 .max(support_a.origin.length())
380 .max(support_b.origin.length())
381 .max(support_a.radius);
382 let band = (tolerance * 100.0).max(1e-7 * scale);
383 if support_a.axis.dot(support_b.axis).abs() < 1.0 - 1e-7
384 || (support_a.radius - support_b.radius).abs() > band
385 || support_a.outward_radial_sign != support_b.outward_radial_sign
386 {
387 if debug {
388 eprintln!(
389 "merge {}x{}: axis/radius/sign mismatch dot={} dr={} signs=({},{})",
390 first.id,
391 second.id,
392 support_a.axis.dot(support_b.axis),
393 (support_a.radius - support_b.radius).abs(),
394 support_a.outward_radial_sign,
395 support_b.outward_radial_sign
396 );
397 }
398 return Ok(None);
399 }
400 let offset = support_b.origin.sub(support_a.origin);
401 let perpendicular = offset.sub(support_a.axis.scale(offset.dot(support_a.axis)));
402 if perpendicular.length() > band {
403 if debug {
404 eprintln!(
405 "merge {}x{}: axes offset {}",
406 first.id,
407 second.id,
408 perpendicular.length()
409 );
410 }
411 return Ok(None);
412 }
413 if debug {
414 eprintln!(
415 "merge {}x{}: MATCH r={} axis=({:.4},{:.4},{:.4})",
416 first.id,
417 second.id,
418 support_a.radius,
419 support_a.axis.x,
420 support_a.axis.y,
421 support_a.axis.z
422 );
423 }
424 Ok(Some(support_a))
425}
426
427struct ExtrusionSupport {
428 base: NurbsCurve,
430 direction: Vec3,
432 interval: [f64; 2],
434}
435
436fn ruled_extrusion_support(
442 face: &FaceRecord,
443 tolerance: f64,
444) -> Result<Option<ExtrusionSupport>, KernelRefusal> {
445 let surface = &face.surface;
446 if planar_support(face, tolerance)?.is_some() {
449 return Ok(None);
450 }
451 let profile_first = if surface.degree_v == 1 && surface.degree_u >= 1 {
452 true
453 } else if surface.degree_u == 1 && surface.degree_v >= 1 {
454 false
455 } else {
456 return Ok(None);
457 };
458 let (profile_count, linear_count) = if profile_first {
459 (
460 surface.control_points.len(),
461 surface.control_points[0].len(),
462 )
463 } else {
464 (
465 surface.control_points[0].len(),
466 surface.control_points.len(),
467 )
468 };
469 if linear_count < 2 {
470 return Ok(None);
471 }
472 let control = |profile_index: usize, linear_index: usize| -> Vec4 {
473 if profile_first {
474 surface.control_points[profile_index][linear_index]
475 } else {
476 surface.control_points[linear_index][profile_index]
477 }
478 };
479 let scale = surface
480 .control_points
481 .iter()
482 .flatten()
483 .map(|point| point.point().map(|p| p.length()).unwrap_or(0.0))
484 .fold(1.0f64, f64::max);
485 let band = (tolerance * 100.0).max(1e-7 * scale);
486 let mut translation: Option<Vec3> = None;
487 for profile_index in 0..profile_count {
488 let first = control(profile_index, 0);
489 let last = control(profile_index, linear_count - 1);
490 if (first.w - last.w).abs() > 1e-9 * first.w.abs().max(1.0) {
491 return Ok(None);
492 }
493 let step = last
494 .point()
495 .or_refuse(KernelStage::Sew, "point")?
496 .sub(first.point().or_refuse(KernelStage::Sew, "point")?);
497 if let Some(reference) = translation {
498 if step.sub(reference).length() > band {
499 return Ok(None);
500 }
501 } else {
502 translation = Some(step);
503 }
504 let start = first.point().or_refuse(KernelStage::Sew, "point")?;
505 for linear_index in 1..linear_count - 1 {
506 let middle = control(profile_index, linear_index);
507 if (middle.w - first.w).abs() > 1e-9 * first.w.abs().max(1.0) {
508 return Ok(None);
509 }
510 let offset = middle
511 .point()
512 .or_refuse(KernelStage::Sew, "point")?
513 .sub(start);
514 let along = offset.dot(step) / step.dot(step).max(1e-30);
515 if offset.sub(step.scale(along)).length() > band
516 || !(-1e-9..=1.0 + 1e-9).contains(&along)
517 {
518 return Ok(None);
519 }
520 }
521 }
522 let translation = translation.ok_or_else(|| {
523 KernelRefusal::internal(
524 KernelStage::Sew,
525 "face_merge",
526 "extrusion support: empty net",
527 )
528 })?;
529 if translation.length() <= band {
530 return Ok(None);
531 }
532 let direction = translation
533 .normalized()
534 .or_refuse(KernelStage::Sew, "normalized")?;
535 let base_controls = (0..profile_count).map(|index| control(index, 0)).collect();
536 let base_knots = if profile_first {
537 surface.knots_u.clone()
538 } else {
539 surface.knots_v.clone()
540 };
541 let base_degree = if profile_first {
542 surface.degree_u
543 } else {
544 surface.degree_v
545 };
546 let base = NurbsCurve::new(base_degree, base_knots, base_controls)
547 .or_refuse(KernelStage::Sew, "new")?;
548 let [t0, t1] = base.domain().or_refuse(KernelStage::Sew, "domain")?;
549 let mut axial = [f64::INFINITY, f64::NEG_INFINITY];
550 for index in 0..=8 {
551 let z = base
552 .evaluate(t0 + (t1 - t0) * index as f64 / 8.0)
553 .or_refuse(KernelStage::Sew, "evaluate")?
554 .dot(direction);
555 axial[0] = axial[0].min(z);
556 axial[1] = axial[1].max(z);
557 }
558 if axial[1] - axial[0] > band {
559 return Ok(None);
562 }
563 let start = (axial[0] + axial[1]) / 2.0;
564 Ok(Some(ExtrusionSupport {
565 base,
566 direction,
567 interval: [start, start + translation.length()],
568 }))
569}
570
571fn perpendicular_profile(curve: &NurbsCurve, direction: Vec3) -> Result<NurbsCurve, KernelRefusal> {
572 let controls = curve
573 .control_points
574 .iter()
575 .map(|control| {
576 let point = control.point().or_refuse(KernelStage::Sew, "point")?;
577 Ok(Vec4::from_point(
578 point.sub(direction.scale(point.dot(direction))),
579 control.w,
580 ))
581 })
582 .collect::<Result<Vec<_>, KernelRefusal>>()?;
583 NurbsCurve::new(curve.degree, curve.knots.clone(), controls)
584 .or_refuse(KernelStage::Sew, "NurbsCurve::new")
585}
586
587fn curves_coincide(
588 first: &NurbsCurve,
589 second: &NurbsCurve,
590 band: f64,
591) -> Result<bool, KernelRefusal> {
592 for (from, to) in [(first, second), (second, first)] {
593 let [t0, t1] = from.domain().or_refuse(KernelStage::Sew, "domain")?;
594 for index in 0..=8 {
595 let point = from
596 .evaluate(t0 + (t1 - t0) * index as f64 / 8.0)
597 .or_refuse(KernelStage::Sew, "evaluate")?;
598 let projection = match crate::project_point_to_curve(to, point) {
599 Ok(projection) => projection,
600 Err(_) => return Ok(false),
601 };
602 if projection.distance > band {
603 return Ok(false);
604 }
605 }
606 }
607 Ok(true)
608}
609
610fn coextrusion_pair(
613 older: &FaceRecord,
614 newer: &FaceRecord,
615 tolerance: f64,
616) -> Result<Option<(ExtrusionSupport, [f64; 2])>, KernelRefusal> {
617 let debug = std::env::var("BREP_DEBUG_MERGE").is_ok();
618 let Some(support_a) = ruled_extrusion_support(older, tolerance)? else {
619 return Ok(None);
620 };
621 let Some(support_b) = ruled_extrusion_support(newer, tolerance)? else {
622 return Ok(None);
623 };
624 let alignment = support_a.direction.dot(support_b.direction);
625 if alignment.abs() < 1.0 - 1e-9 {
626 if debug {
627 eprintln!(
628 "coextrusion {}x{}: directions differ (dot {alignment})",
629 older.id, newer.id
630 );
631 }
632 return Ok(None);
633 }
634 let scale = 1.0f64
635 .max(support_a.interval[1].abs())
636 .max(support_b.interval[1].abs());
637 let band = (tolerance * 100.0).max(1e-7 * scale);
638 let profile_a = perpendicular_profile(&support_a.base, support_a.direction)?;
639 let profile_b = perpendicular_profile(&support_b.base, support_a.direction)?;
640 if !curves_coincide(&profile_a, &profile_b, band)? {
641 if debug {
642 eprintln!("coextrusion {}x{}: profiles differ", older.id, newer.id);
643 }
644 return Ok(None);
645 }
646 let interval_b = if alignment < 0.0 {
649 [-support_b.interval[1], -support_b.interval[0]]
650 } else {
651 support_b.interval
652 };
653 if interval_b[0] > support_a.interval[1] + band || support_a.interval[0] > interval_b[1] + band
654 {
655 if debug {
656 eprintln!(
657 "coextrusion {}x{}: axial gap {:?} vs {:?}",
658 older.id, newer.id, support_a.interval, interval_b
659 );
660 }
661 return Ok(None);
662 }
663 let union = [
664 support_a.interval[0].min(interval_b[0]),
665 support_a.interval[1].max(interval_b[1]),
666 ];
667 Ok(Some((support_a, union)))
668}
669
670fn trimmed_curve(curve: &NurbsCurve, t0: f64, t1: f64) -> Result<NurbsCurve, KernelRefusal> {
671 let [start, end] = curve.domain().or_refuse(KernelStage::Sew, "domain")?;
672 let epsilon = (1e-9 * (end - start)).max(2e-9);
673 let mut result = curve.clone();
674 if t0 > start + epsilon && t0 < end - epsilon {
675 result = result.split(t0).or_refuse(KernelStage::Sew, "split")?.1;
676 }
677 let domain = result.domain().or_refuse(KernelStage::Sew, "domain")?;
678 if t1 < domain[1] - epsilon && t1 > domain[0] + epsilon {
679 result = result.split(t1).or_refuse(KernelStage::Sew, "split")?.0;
680 } else if std::env::var("BREP_DEBUG_SUBRANGE").is_ok() && t1 < domain[1] - epsilon {
681 eprintln!("abnormal subrange skip in face_merge trimmed");
682 }
683 Ok(result)
684}
685
686fn axial_hull(curve: &NurbsCurve, support: &CylinderSupport) -> [f64; 2] {
694 let origin_axial = support.origin.dot(support.axis);
695 let mut range = [f64::INFINITY, f64::NEG_INFINITY];
696 for point in &curve.control_points {
697 let axial = Vec3::new(point.x / point.w, point.y / point.w, point.z / point.w)
698 .dot(support.axis)
699 - origin_axial;
700 range[0] = range[0].min(axial);
701 range[1] = range[1].max(axial);
702 }
703 range
704}
705
706struct AffinePlaneChart {
709 origin: Vec3,
710 du: Vec3,
711 dv: Vec3,
712 u0: f64,
713 v0: f64,
714}
715
716fn affine_plane_chart(surface: &NurbsSurface) -> Option<AffinePlaneChart> {
717 if surface.degree_u != 1 || surface.degree_v != 1
718 || surface.control_points.len() != 2
719 || surface.control_points.iter().any(|row| row.len() != 2)
720 || surface.knots_u.len() != 4 || surface.knots_v.len() != 4
721 { return None; }
722 let ku = &surface.knots_u;
723 let kv = &surface.knots_v;
724 if ku[0] != ku[1] || ku[2] != ku[3] || kv[0] != kv[1] || kv[2] != kv[3]
725 || ku[2] <= ku[1] || kv[2] <= kv[1]
726 { return None; }
727 let weight = surface.control_points[0][0].w;
728 if !weight.is_finite() || weight.abs() <= 1e-300
729 || surface.control_points.iter().flatten().any(|point| point.w != weight)
730 { return None; }
731 let p00 = surface.control_points[0][0].point().ok()?;
732 let p10 = surface.control_points[1][0].point().ok()?;
733 let p01 = surface.control_points[0][1].point().ok()?;
734 let p11 = surface.control_points[1][1].point().ok()?;
735 let u = p10.sub(p00);
736 let v = p01.sub(p00);
737 let scale = u.length().max(v.length()).max(1.0);
738 if p11.sub(p10).sub(v).length() > 1e-12 * scale { return None; }
739 let du = u.scale(1.0 / (ku[2] - ku[1]));
740 let dv = v.scale(1.0 / (kv[2] - kv[1]));
741 let determinant = du.dot(du) * dv.dot(dv) - du.dot(dv).powi(2);
742 if !determinant.is_finite() || determinant <= 1e-12 * du.dot(du) * dv.dot(dv) {
743 return None;
744 }
745 Some(AffinePlaneChart { origin: p00, du, dv, u0: ku[1], v0: kv[1] })
746}
747
748fn transfer_affine_planar_pcurve(
753 source: &NurbsSurface,
754 target: &NurbsSurface,
755 curve: &NurbsCurve,
756 tolerance: f64,
757) -> Option<NurbsCurve> {
758 let source = affine_plane_chart(source)?;
759 let target = affine_plane_chart(target)?;
760 let uu = target.du.dot(target.du);
761 let uv = target.du.dot(target.dv);
762 let vv = target.dv.dot(target.dv);
763 let determinant = uu * vv - uv * uv;
764 let mut transferred = curve.clone();
765 for control in &mut transferred.control_points {
766 if !control.w.is_finite() || control.w.abs() <= 1e-300 { return None; }
767 let point = source.origin
768 .add(source.du.scale(control.x / control.w - source.u0))
769 .add(source.dv.scale(control.y / control.w - source.v0));
770 let relative = point.sub(target.origin);
771 let a = relative.dot(target.du);
772 let b = relative.dot(target.dv);
773 let u = (a * vv - b * uv) / determinant;
774 let v = (b * uu - a * uv) / determinant;
775 let reconstructed = target.origin.add(target.du.scale(u)).add(target.dv.scale(v));
776 if !u.is_finite() || !v.is_finite()
777 || reconstructed.sub(point).length() > tolerance.max(1e-12)
778 { return None; }
779 control.x = (target.u0 + u) * control.w;
780 control.y = (target.v0 + v) * control.w;
781 control.z = 0.0;
782 }
783 Some(transferred)
784}
785
786fn transfer_planar_loops(
787 target: &NurbsSurface,
788 loops: &[LoopRecord],
789 older: &FaceRecord,
790 newer: &FaceRecord,
791 tolerance: f64,
792) -> Option<Vec<LoopRecord>> {
793 let mut transferred = loops.to_vec();
794 for loop_record in &mut transferred {
795 for coedge in &mut loop_record.coedges {
796 let source = [older, newer].into_iter().find(|face| {
797 face.loops.iter().flat_map(|lp| &lp.coedges)
798 .any(|original| original.id == coedge.id && original.edge_id == coedge.edge_id)
799 })?;
800 coedge.pcurve = transfer_affine_planar_pcurve(
801 &source.surface, target, &coedge.pcurve, tolerance,
802 )?;
803 }
804 }
805 Some(transferred)
806}
807
808fn reproject_loops(
809 surface: &NurbsSurface,
810 loops: Vec<LoopRecord>,
811 edges: &HashMap<u64, &EdgeRecord>,
812) -> Result<Vec<LoopRecord>, KernelRefusal> {
813 let mut projected_loops = Vec::new();
814 for (loop_index, loop_record) in loops.into_iter().enumerate() {
815 let mut projected = Vec::new();
816 for mut coedge in loop_record.coedges {
817 let edge = edges[&coedge.edge_id];
818 let mut curve = trimmed_curve(&edge.curve, edge.t0, edge.t1)?;
819 if !coedge.forward {
820 curve = curve.reversed().or_refuse(KernelStage::Sew, "reversed")?;
821 }
822 coedge.pcurve = build_pcurve_on_surface(surface, &curve)
823 .or_refuse(KernelStage::Sew, "build_pcurve_on_surface")?;
824 projected.push(coedge);
825 }
826 projected_loops.push(LoopRecord {
827 id: loop_index as u64 + 1,
828 coedges: projected,
829 });
830 }
831 Ok(projected_loops)
832}
833
834fn traversal_vertices(edge: &EdgeRecord, coedge: &CoedgeRecord) -> (u64, u64) {
835 if coedge.forward {
836 (edge.start_vertex_id, edge.end_vertex_id)
837 } else {
838 (edge.end_vertex_id, edge.start_vertex_id)
839 }
840}
841
842struct SharedParameterSpace<'a> {
846 surface: &'a NurbsSurface,
847 weld: f64,
849}
850
851impl SharedParameterSpace<'_> {
852 fn coincide(&self, first: Vec3, second: Vec3) -> bool {
853 let band = crate::classification::surface_uv_band(self.surface, first.x, first.y, self.weld);
854 (first.x - second.x).abs() <= band && (first.y - second.y).abs() <= band
855 }
856}
857
858fn pcurve_stations(coedge: &CoedgeRecord) -> Option<[Vec3; 3]> {
861 let [t0, t1] = coedge.pcurve.domain().ok()?;
862 Some([
863 coedge.pcurve.evaluate(t0).ok()?,
864 coedge.pcurve.evaluate((t0 + t1) / 2.0).ok()?,
865 coedge.pcurve.evaluate(t1).ok()?,
866 ])
867}
868
869fn dissolve_slits(
876 remaining: &mut Vec<CoedgeRecord>,
877 edges: &HashMap<u64, &EdgeRecord>,
878 space: &SharedParameterSpace,
879) {
880 let mut uses = HashMap::<u64, Vec<usize>>::default();
881 for (index, coedge) in remaining.iter().enumerate() {
882 uses.entry(coedge.edge_id).or_default().push(index);
883 }
884 let slits = uses
885 .iter()
886 .filter(|(edge_id, indices)| {
887 if indices.len() != 2 || edges[*edge_id].degenerate {
888 return false;
889 }
890 let (first, second) = (&remaining[indices[0]], &remaining[indices[1]]);
891 if first.forward == second.forward {
892 return false;
893 }
894 let (Some(first), Some(second)) = (pcurve_stations(first), pcurve_stations(second)) else {
895 return false;
896 };
897 space.coincide(first[0], second[2])
898 && space.coincide(first[1], second[1])
899 && space.coincide(first[2], second[0])
900 })
901 .map(|(edge_id, _)| *edge_id)
902 .collect::<HashSet<_>>();
903 remaining.retain(|coedge| !slits.contains(&coedge.edge_id));
904}
905
906fn walk_cycles(
918 mut remaining: Vec<CoedgeRecord>,
919 edges: &HashMap<u64, &EdgeRecord>,
920 space: Option<&SharedParameterSpace>,
921) -> Option<Vec<LoopRecord>> {
922 let maximum_cycle_length = remaining.len();
923 let mut loops = Vec::new();
924 while !remaining.is_empty() {
925 let first = remaining.remove(0);
926 let (start, mut end) = traversal_vertices(edges[&first.edge_id], &first);
927 let mut cycle = vec![first];
928 loop {
929 let leaving = remaining
930 .iter()
931 .enumerate()
932 .filter_map(|(index, coedge)| {
933 (traversal_vertices(edges[&coedge.edge_id], coedge).0 == end).then_some(index)
934 })
935 .collect::<Vec<_>>();
936 let closes = end == start;
937 let successor = match (leaving.as_slice(), closes) {
938 ([], true) => None,
939 ([only], false) => Some(*only),
940 ([], false) => return None,
941 _ => {
942 let space = space?;
943 let here = pcurve_stations(cycle.last()?)?[2];
944 let closing = closes && space.coincide(here, pcurve_stations(&cycle[0])?[0]);
945 let mut continuing = Vec::new();
946 for index in leaving {
947 if space.coincide(here, pcurve_stations(&remaining[index])?[0]) {
948 continuing.push(index);
949 }
950 }
951 match (continuing.as_slice(), closing) {
952 ([], true) => None,
953 ([only], false) => Some(*only),
954 _ => return None,
955 }
956 }
957 };
958 let Some(index) = successor else {
959 break;
960 };
961 let next = remaining.remove(index);
962 end = traversal_vertices(edges[&next.edge_id], &next).1;
963 cycle.push(next);
964 if cycle.len() > maximum_cycle_length {
965 return None;
966 }
967 }
968 let mut counts = HashMap::<u64, usize>::default();
971 for coedge in &cycle {
972 *counts.entry(coedge.edge_id).or_default() += 1;
973 }
974 if counts.values().all(|count| *count == 2) {
975 return None;
976 }
977 loops.push(LoopRecord {
978 id: loops.len() as u64 + 1,
979 coedges: cycle,
980 });
981 }
982 Some(loops)
983}
984
985pub(crate) fn faces_are_cosurface(
997 first: &FaceRecord,
998 second: &FaceRecord,
999 tolerance: f64,
1000) -> Result<bool, KernelRefusal> {
1001 if first.same_sense == second.same_sense
1002 && same_surface(&first.surface, &second.surface, tolerance)
1003 {
1004 return Ok(true);
1005 }
1006 if coplanar_with_same_outward_normal(first, second, tolerance)? {
1007 return Ok(true);
1008 }
1009 if cosurface_cylinder_pair(first, second, tolerance)?.is_some() {
1010 return Ok(true);
1011 }
1012 Ok(coextrusion_pair(first, second, tolerance)?.is_some())
1013}
1014
1015fn opposed_planar_trims_agree(
1021 older: &FaceRecord,
1022 first: &CoedgeRecord,
1023 newer: &FaceRecord,
1024 second: &CoedgeRecord,
1025 tolerance: f64,
1026) -> bool {
1027 let Ok(reverse) = second.pcurve.reversed() else {
1028 return false;
1029 };
1030 let curve = &first.pcurve;
1031 if curve.degree != reverse.degree || curve.control_points.len() != reverse.control_points.len()
1032 {
1033 return false;
1034 }
1035 let linear_polygon = |c: &NurbsCurve| {
1036 c.degree == 1
1037 && c.knots.len() == c.control_points.len() + 2
1038 && c.knots[0] == c.knots[1]
1039 && c.knots[c.knots.len() - 1] == c.knots[c.knots.len() - 2]
1040 && c.knots[1..c.knots.len() - 1]
1041 .windows(2)
1042 .all(|k| k[1] > k[0])
1043 };
1044 let polygon = linear_polygon(curve) && linear_polygon(&reverse);
1045 if !polygon && curve.knots != reverse.knots {
1046 return false;
1047 }
1048 curve
1049 .control_points
1050 .iter()
1051 .zip(&reverse.control_points)
1052 .all(|(a, b)| {
1053 if !a.w.is_finite()
1054 || !b.w.is_finite()
1055 || a.w <= 0.0
1056 || b.w <= 0.0
1057 || (!polygon && a.w != b.w)
1058 {
1059 return false;
1060 }
1061 let (Ok(a), Ok(b)) = (a.point(), b.point()) else {
1062 return false;
1063 };
1064 let (Ok(a), Ok(b)) = (
1065 older.surface.evaluate_extended(a.x, a.y),
1066 newer.surface.evaluate_extended(b.x, b.y),
1067 ) else {
1068 return false;
1069 };
1070 a.sub(b).length() <= tolerance
1071 })
1072}
1073
1074macro_rules! fall_through {
1077 ($older:expr, $newer:expr, $label:lifetime) => {{
1078 if std::env::var("BREP_DEBUG_MERGE").is_ok() {
1079 eprintln!(
1080 "merge {}x{}: lane left at face_merge.rs:{}",
1081 $older.id,
1082 $newer.id,
1083 line!()
1084 );
1085 }
1086 break $label;
1087 }};
1088}
1089
1090macro_rules! decline {
1096 ($older:expr, $newer:expr) => {{
1097 if std::env::var("BREP_DEBUG_MERGE").is_ok() {
1098 eprintln!(
1099 "merge {}x{}: declined at face_merge.rs:{}",
1100 $older.id,
1101 $newer.id,
1102 line!()
1103 );
1104 }
1105 return Ok(None);
1106 }};
1107}
1108
1109fn try_merge_pair(
1110 older: &FaceRecord,
1111 newer: &FaceRecord,
1112 edges: &HashMap<u64, &EdgeRecord>,
1113 tolerance: f64,
1114 same_carrier_area_tolerance_ratio: f64,
1115) -> Result<Option<FaceRecord>, KernelRefusal> {
1116 let same_carrier = older.same_sense == newer.same_sense
1117 && same_surface(&older.surface, &newer.surface, tolerance);
1118 let cancel_planar_fold = older.same_sense != newer.same_sense
1122 && older.loops.len() == 1
1123 && newer.loops.len() == 1
1124 && same_surface(&older.surface, &newer.surface, tolerance)
1125 && older
1126 .surface
1127 .is_affine()
1128 .or_refuse(KernelStage::Sew, "is_affine")?
1129 && newer
1130 .surface
1131 .is_affine()
1132 .or_refuse(KernelStage::Sew, "is_affine")?;
1133 let coplanar_planar =
1134 !same_carrier && coplanar_with_same_outward_normal(older, newer, tolerance)?;
1135 let cosurface_cylinder = if !same_carrier && !coplanar_planar {
1136 cosurface_cylinder_pair(older, newer, tolerance)?
1137 } else {
1138 None
1139 };
1140 let cosurface_extrusion = if !same_carrier && !coplanar_planar && cosurface_cylinder.is_none() {
1141 coextrusion_pair(older, newer, tolerance)?
1142 } else {
1143 None
1144 };
1145 let older_coedges = older
1146 .loops
1147 .iter()
1148 .flat_map(|loop_record| &loop_record.coedges)
1149 .collect::<Vec<_>>();
1150 let newer_coedges = newer
1151 .loops
1152 .iter()
1153 .flat_map(|loop_record| &loop_record.coedges)
1154 .collect::<Vec<_>>();
1155 let space = (same_carrier || cancel_planar_fold).then(|| SharedParameterSpace {
1156 surface: &older.surface,
1157 weld: crate::tolerance::assembler_weld(tolerance),
1158 });
1159 let mut shared_older = HashSet::default();
1160 let mut shared_newer = HashSet::default();
1161 let mut shared_edges = HashSet::default();
1162 for first in &older_coedges {
1171 if edges[&first.edge_id].degenerate {
1172 continue;
1173 }
1174 for second in &newer_coedges {
1175 if first.edge_id != second.edge_id {
1176 continue;
1177 }
1178 if first.forward == second.forward {
1179 decline!(older, newer);
1180 }
1181 if cancel_planar_fold
1182 && !opposed_planar_trims_agree(older, first, newer, second, tolerance)
1183 {
1184 decline!(older, newer);
1185 }
1186 if same_carrier && !cancel_planar_fold {
1187 if let (Some(space), Some(here), Some(there)) =
1188 (&space, pcurve_stations(first), pcurve_stations(second))
1189 {
1190 let retraced = space.coincide(here[0], there[2])
1191 && space.coincide(here[1], there[1])
1192 && space.coincide(here[2], there[0]);
1193 if !retraced {
1194 continue;
1195 }
1196 }
1197 }
1198 shared_older.insert(first.id);
1199 shared_newer.insert(second.id);
1200 shared_edges.insert(first.edge_id);
1201 }
1202 }
1203 if shared_older.is_empty() || shared_older.len() != shared_newer.len() {
1204 decline!(older, newer);
1205 }
1206 if cancel_planar_fold && shared_older.len() < 2 {
1207 decline!(older, newer);
1208 }
1209 if !same_carrier
1210 && !cancel_planar_fold
1211 && !coplanar_planar
1212 && cosurface_cylinder.is_none()
1213 && cosurface_extrusion.is_none()
1214 {
1215 decline!(older, newer);
1216 }
1217 let mut remaining = older_coedges
1218 .into_iter()
1219 .filter(|coedge| {
1220 !shared_older.contains(&coedge.id)
1221 && !(coplanar_planar && edges[&coedge.edge_id].degenerate)
1222 })
1223 .chain(newer_coedges.into_iter().filter(|coedge| {
1224 !shared_newer.contains(&coedge.id)
1225 && !(coplanar_planar && edges[&coedge.edge_id].degenerate)
1226 }))
1227 .cloned()
1228 .collect::<Vec<_>>();
1229 if cancel_planar_fold {
1230 let mut uses = HashMap::<u64, Vec<&CoedgeRecord>>::default();
1235 for coedge in &remaining {
1236 uses.entry(coedge.edge_id).or_default().push(coedge);
1237 }
1238 let mut slits = HashSet::default();
1239 for (id, uses) in uses {
1240 if uses.len() == 2
1241 && !edges[&id].degenerate
1242 && uses[0].forward != uses[1].forward
1243 && opposed_planar_trims_agree(older, uses[0], older, uses[1], tolerance)
1244 {
1245 slits.insert(id);
1246 }
1247 }
1248 remaining.retain(|coedge| !slits.contains(&coedge.edge_id));
1249 } else if let Some(space) = &space {
1250 dissolve_slits(&mut remaining, edges, space);
1251 }
1252 let Some(mut loops) = walk_cycles(remaining, edges, space.as_ref()) else {
1253 if let Some(support) = &cosurface_cylinder {
1258 if let Some(merged) =
1259 merge_cylinder_full_turn(older, newer, edges, tolerance, support, &shared_edges)?
1260 {
1261 return Ok(Some(merged));
1262 }
1263 }
1264 decline!(older, newer);
1265 };
1266 if loops.iter().any(|loop_record| {
1267 loop_record
1268 .coedges
1269 .iter()
1270 .all(|coedge| edges[&coedge.edge_id].degenerate)
1271 }) {
1272 decline!(older, newer);
1273 }
1274 if loops.is_empty() {
1275 decline!(older, newer);
1276 }
1277 loops.sort_by(|first, second| {
1278 let area = |loop_record: &LoopRecord| {
1279 parameter_space_area(&FaceRecord {
1280 id: older.id,
1281 surface: older.surface.clone(),
1282 same_sense: older.same_sense,
1283 loops: vec![loop_record.clone()],
1284 name: None,
1285 })
1286 .map(f64::abs)
1287 };
1288 match (area(first), area(second)) {
1289 (Ok(a), Ok(b)) => b.total_cmp(&a),
1290 _ => std::cmp::Ordering::Equal,
1291 }
1292 });
1293 if same_carrier || cancel_planar_fold {
1294 if cancel_planar_fold && loops.len() != 1 {
1295 decline!(older, newer);
1296 }
1297 let expected = parameter_space_area(older)
1298 .or_refuse(KernelStage::Sew, "parameter_space_area")?
1299 + parameter_space_area(newer).or_refuse(KernelStage::Sew, "parameter_space_area")?;
1300 if cancel_planar_fold && expected.abs() <= tolerance * tolerance {
1301 decline!(older, newer);
1302 }
1303 let merged = FaceRecord {
1304 id: older.id,
1305 surface: older.surface.clone(),
1306 same_sense: if cancel_planar_fold {
1307 expected > 0.0
1308 } else {
1309 older.same_sense
1310 },
1311 loops,
1312 name: older.name.clone(),
1313 };
1314
1315 let actual =
1316 parameter_space_area(&merged).or_refuse(KernelStage::Sew, "parameter_space_area")?;
1317 let area_ratio = if cancel_planar_fold {
1318 same_carrier_area_tolerance_ratio.min(1e-7)
1319 } else {
1320 same_carrier_area_tolerance_ratio
1321 };
1322 let area_tolerance = 1e-9f64.max(expected.abs() * area_ratio);
1323 if (actual - expected).abs() > area_tolerance
1324 || (actual.abs() > 1e-12 && actual.is_sign_positive() != merged.same_sense)
1325 {
1326 decline!(older, newer);
1327 }
1328 return Ok(Some(merged));
1329 }
1330
1331 if let Some(support) = &cosurface_cylinder {
1332 'partial_turn: {
1338 let x_reference = {
1342 let seed = loops
1343 .iter()
1344 .flat_map(|loop_record| &loop_record.coedges)
1345 .find_map(|coedge| {
1346 let edge = edges[&coedge.edge_id];
1347 edge.curve.evaluate(edge.t0).ok()
1348 })
1349 .ok_or_else(|| {
1350 KernelRefusal::internal(
1351 KernelStage::Sew,
1352 "face_merge",
1353 "cylinder merge: no boundary sample",
1354 )
1355 })?;
1356 let delta = seed.sub(support.origin);
1357 let radial = delta.sub(support.axis.scale(delta.dot(support.axis)));
1358 match radial.normalized() {
1359 Ok(radial) => radial,
1360 Err(_) => fall_through!(older, newer, 'partial_turn),
1361 }
1362 };
1363 let y_reference = support.axis.cross(x_reference);
1364 let mut angles = Vec::new();
1365 let mut axial_range = [f64::INFINITY, f64::NEG_INFINITY];
1366 for coedge in loops.iter().flat_map(|loop_record| &loop_record.coedges) {
1367 let edge = edges[&coedge.edge_id];
1368 let curve = trimmed_curve(&edge.curve, edge.t0, edge.t1)?;
1369 let [c0, c1] = curve.domain().or_refuse(KernelStage::Sew, "domain")?;
1370 let hull = axial_hull(&curve, support);
1371 axial_range[0] = axial_range[0].min(hull[0]);
1372 axial_range[1] = axial_range[1].max(hull[1]);
1373 for index in 0..=8 {
1374 let point = curve
1375 .evaluate(c0 + (c1 - c0) * index as f64 / 8.0)
1376 .or_refuse(KernelStage::Sew, "evaluate")?;
1377 let delta = point.sub(support.origin);
1378 let axial = delta.dot(support.axis);
1379 let radial = delta.sub(support.axis.scale(axial));
1380 if radial.length() <= support.radius * 1e-6 {
1381 continue;
1382 }
1383 let mut angle = radial.dot(y_reference).atan2(radial.dot(x_reference));
1384 if angle < 0.0 {
1385 angle += std::f64::consts::TAU;
1386 }
1387 angles.push(angle);
1388 }
1389 }
1390 if angles.len() < 3 || axial_range[1] - axial_range[0] <= tolerance {
1391 fall_through!(older, newer, 'partial_turn);
1392 }
1393 angles.sort_by(f64::total_cmp);
1394 let mut gap_start = angles.len() - 1;
1395 let mut largest_gap = angles[0] + std::f64::consts::TAU - angles[angles.len() - 1];
1396 for index in 0..angles.len() - 1 {
1397 let gap = angles[index + 1] - angles[index];
1398 if gap > largest_gap {
1399 largest_gap = gap;
1400 gap_start = index;
1401 }
1402 }
1403 let span = std::f64::consts::TAU - largest_gap;
1404 if span <= tolerance || span >= std::f64::consts::TAU - 1e-6 {
1405 fall_through!(older, newer, 'partial_turn);
1406 }
1407 let start_angle = angles[(gap_start + 1) % angles.len()];
1408 let start_direction = x_reference
1409 .scale(start_angle.cos())
1410 .add(y_reference.scale(start_angle.sin()));
1411 let generatrix = make_line(
1412 support
1413 .origin
1414 .add(support.axis.scale(axial_range[0]))
1415 .add(start_direction.scale(support.radius)),
1416 support
1417 .origin
1418 .add(support.axis.scale(axial_range[1]))
1419 .add(start_direction.scale(support.radius)),
1420 )
1421 .or_refuse(KernelStage::Sew, "healing.face_merge")?;
1422 let surface = make_revolution(support.origin, support.axis, &generatrix, span)
1423 .or_refuse(KernelStage::Sew, "make_revolution")?;
1424 let (u_domain, v_domain) = surface_domains(&surface)?;
1425 let sample = surface
1426 .evaluate(
1427 (u_domain[0] + u_domain[1]) / 2.0,
1428 (v_domain[0] + v_domain[1]) / 2.0,
1429 )
1430 .or_refuse(KernelStage::Sew, "healing.face_merge")?;
1431 let geometric_normal = surface
1432 .normal(
1433 (u_domain[0] + u_domain[1]) / 2.0,
1434 (v_domain[0] + v_domain[1]) / 2.0,
1435 )
1436 .or_refuse(KernelStage::Sew, "healing.face_merge")?;
1437 let delta = sample.sub(support.origin);
1438 let radial = delta.sub(support.axis.scale(delta.dot(support.axis)));
1439 let radial = match radial.normalized() {
1440 Ok(radial) => radial,
1441 Err(_) => fall_through!(older, newer, 'partial_turn),
1442 };
1443 let same_sense = geometric_normal.dot(radial).signum() == support.outward_radial_sign;
1444 let mut projected_loops = reproject_loops(&surface, loops, edges)?;
1445 projected_loops.sort_by(|first, second| {
1446 let area = |loop_record: &LoopRecord| {
1447 parameter_space_area(&FaceRecord {
1448 id: older.id,
1449 surface: surface.clone(),
1450 same_sense,
1451 loops: vec![loop_record.clone()],
1452 name: None,
1453 })
1454 .map(f64::abs)
1455 };
1456 match (area(first), area(second)) {
1457 (Ok(a), Ok(b)) => b.total_cmp(&a),
1458 _ => std::cmp::Ordering::Equal,
1459 }
1460 });
1461 let merged = FaceRecord {
1462 id: older.id,
1463 surface,
1464 same_sense,
1465 loops: projected_loops,
1466 name: older.name.clone(),
1467 };
1468 let area =
1469 parameter_space_area(&merged).or_refuse(KernelStage::Sew, "parameter_space_area")?;
1470 if area.abs() <= tolerance * tolerance || area.is_sign_positive() != merged.same_sense {
1471 fall_through!(older, newer, 'partial_turn);
1472 }
1473 let expected = face_area(older).or_refuse(KernelStage::Sew, "face_area")?
1476 + face_area(newer).or_refuse(KernelStage::Sew, "face_area")?;
1477 let actual = face_area(&merged).or_refuse(KernelStage::Sew, "face_area")?;
1478 if (actual - expected).abs() > expected.abs().max(1e-9) * 5e-3 {
1479 fall_through!(older, newer, 'partial_turn);
1480 }
1481 return Ok(Some(merged));
1482 }
1483 if let Some(merged) =
1484 merge_cylinder_full_turn(older, newer, edges, tolerance, support, &shared_edges)?
1485 {
1486 return Ok(Some(merged));
1487 }
1488 decline!(older, newer);
1489 }
1490
1491 if let Some((support, union)) = cosurface_extrusion {
1492 let shift = support.direction.scale(union[0] - support.interval[0]);
1495 let step = support.direction.scale(union[1] - union[0]);
1496 let rows = support
1497 .base
1498 .control_points
1499 .iter()
1500 .map(|control| -> Result<Vec<Vec4>, KernelRefusal> {
1501 let point = control
1502 .point()
1503 .or_refuse(KernelStage::Sew, "point")?
1504 .add(shift);
1505 Ok(vec![
1506 Vec4::from_point(point, control.w),
1507 Vec4::from_point(point.add(step), control.w),
1508 ])
1509 })
1510 .collect::<Result<Vec<_>, _>>()?;
1511 let surface = NurbsSurface::new(
1512 support.base.degree,
1513 1,
1514 support.base.knots.clone(),
1515 vec![0.0, 0.0, 1.0, 1.0],
1516 rows,
1517 )
1518 .or_refuse(KernelStage::Sew, "healing.face_merge")?;
1519 let (older_u, older_v) = surface_domains(&older.surface)?;
1520 let older_mid = older
1521 .surface
1522 .evaluate(
1523 (older_u[0] + older_u[1]) / 2.0,
1524 (older_v[0] + older_v[1]) / 2.0,
1525 )
1526 .or_refuse(KernelStage::Sew, "healing.face_merge")?;
1527 let projection = crate::project_point_to_surface(&surface, older_mid)
1528 .or_refuse(KernelStage::Sew, "project_point_to_surface")?;
1529 let carrier_normal = surface
1530 .normal(projection.u, projection.v)
1531 .or_refuse(KernelStage::Sew, "normal")?;
1532 let same_sense = carrier_normal.dot(outward_normal(older)?) > 0.0;
1533 let mut projected_loops = reproject_loops(&surface, loops, edges)?;
1534 projected_loops.sort_by(|first, second| {
1535 let area = |loop_record: &LoopRecord| {
1536 parameter_space_area(&FaceRecord {
1537 id: older.id,
1538 surface: surface.clone(),
1539 same_sense,
1540 loops: vec![loop_record.clone()],
1541 name: None,
1542 })
1543 .map(f64::abs)
1544 };
1545 match (area(first), area(second)) {
1546 (Ok(a), Ok(b)) => b.total_cmp(&a),
1547 _ => std::cmp::Ordering::Equal,
1548 }
1549 });
1550 let merged = FaceRecord {
1551 id: older.id,
1552 surface,
1553 same_sense,
1554 loops: projected_loops,
1555 name: older.name.clone(),
1556 };
1557 let area =
1558 parameter_space_area(&merged).or_refuse(KernelStage::Sew, "parameter_space_area")?;
1559 if area.abs() <= tolerance * tolerance || area.is_sign_positive() != merged.same_sense {
1560 decline!(older, newer);
1561 }
1562 let expected = face_area(older).or_refuse(KernelStage::Sew, "face_area")?
1563 + face_area(newer).or_refuse(KernelStage::Sew, "face_area")?;
1564 let actual = face_area(&merged).or_refuse(KernelStage::Sew, "face_area")?;
1565 if (actual - expected).abs() > expected.abs().max(1e-9) * 5e-3 {
1566 if std::env::var("BREP_DEBUG_MERGE").is_ok() {
1567 eprintln!(
1568 "coextrusion {}x{}: area mismatch {actual} vs {expected}",
1569 older.id, newer.id
1570 );
1571 }
1572 decline!(older, newer);
1573 }
1574 return Ok(Some(merged));
1575 }
1576
1577 let (u_domain, v_domain) = surface_domains(&older.surface)?;
1578 let origin = older
1579 .surface
1580 .evaluate(u_domain[0], v_domain[0])
1581 .or_refuse(KernelStage::Sew, "evaluate")?;
1582 let derivatives = older
1583 .surface
1584 .derivatives(
1585 (u_domain[0] + u_domain[1]) / 2.0,
1586 (v_domain[0] + v_domain[1]) / 2.0,
1587 1,
1588 )
1589 .or_refuse(KernelStage::Sew, "healing.face_merge")?;
1590 let u_axis = derivatives[1][0]
1591 .normalized()
1592 .or_refuse(KernelStage::Sew, "normalized")?;
1593 let geometric_normal = derivatives[1][0]
1594 .cross(derivatives[0][1])
1595 .normalized()
1596 .or_refuse(KernelStage::Sew, "normalized")?;
1597 let v_axis = geometric_normal
1598 .cross(u_axis)
1599 .normalized()
1600 .or_refuse(KernelStage::Sew, "normalized")?;
1601 let mut bounds_u = [f64::INFINITY, f64::NEG_INFINITY];
1602 let mut bounds_v = [f64::INFINITY, f64::NEG_INFINITY];
1603 for coedge in loops.iter().flat_map(|loop_record| &loop_record.coedges) {
1604 let edge = edges[&coedge.edge_id];
1605 let curve = trimmed_curve(&edge.curve, edge.t0, edge.t1)?;
1606 for control in &curve.control_points {
1607 let relative = control
1608 .point()
1609 .or_refuse(KernelStage::Sew, "point")?
1610 .sub(origin);
1611 let u = relative.dot(u_axis);
1612 let v = relative.dot(v_axis);
1613 bounds_u[0] = bounds_u[0].min(u);
1614 bounds_u[1] = bounds_u[1].max(u);
1615 bounds_v[0] = bounds_v[0].min(v);
1616 bounds_v[1] = bounds_v[1].max(v);
1617 }
1618 }
1619 let extent_u = bounds_u[1] - bounds_u[0];
1620 let extent_v = bounds_v[1] - bounds_v[0];
1621 if extent_u <= tolerance || extent_v <= tolerance {
1622 decline!(older, newer);
1623 }
1624 let surface_origin = origin
1625 .add(u_axis.scale(bounds_u[0]))
1626 .add(v_axis.scale(bounds_v[0]));
1627 let surface = make_plane(surface_origin, u_axis, v_axis, extent_u, extent_v)
1628 .or_refuse(KernelStage::Sew, "make_plane")?;
1629 let mut projected_loops = match transfer_planar_loops(&surface, &loops, older, newer, tolerance)
1630 {
1631 Some(transferred) => transferred,
1632 None => reproject_loops(&surface, loops, edges)?,
1633 };
1634 projected_loops.sort_by(|first, second| {
1635 let area = |loop_record: &LoopRecord| {
1636 parameter_space_area(&FaceRecord {
1637 id: older.id,
1638 surface: surface.clone(),
1639 same_sense: older.same_sense,
1640 loops: vec![loop_record.clone()],
1641 name: None,
1642 })
1643 .map(f64::abs)
1644 };
1645 match (area(first), area(second)) {
1646 (Ok(a), Ok(b)) => b.total_cmp(&a),
1647 _ => std::cmp::Ordering::Equal,
1648 }
1649 });
1650 let merged = FaceRecord {
1651 id: older.id,
1652 surface,
1653 same_sense: older.same_sense,
1654 loops: projected_loops,
1655 name: older.name.clone(),
1656 };
1657 let area = parameter_space_area(&merged).or_refuse(KernelStage::Sew, "parameter_space_area")?;
1658 if area.abs() <= tolerance * tolerance || area.is_sign_positive() != merged.same_sense {
1659 decline!(older, newer);
1660 }
1661 Ok(Some(merged))
1662}
1663
1664fn cylinder_angle(
1667 support: &CylinderSupport,
1668 x_reference: Vec3,
1669 y_reference: Vec3,
1670 point: Vec3,
1671) -> Option<f64> {
1672 let delta = point.sub(support.origin);
1673 let radial = delta.sub(support.axis.scale(delta.dot(support.axis)));
1674 if radial.length() <= support.radius * 1e-6 {
1675 return None;
1676 }
1677 let mut angle = radial.dot(y_reference).atan2(radial.dot(x_reference));
1678 if angle < 0.0 {
1679 angle += std::f64::consts::TAU;
1680 }
1681 if angle >= std::f64::consts::TAU {
1684 angle = 0.0;
1685 }
1686 Some(angle)
1687}
1688
1689fn angle_difference(from: f64, to: f64) -> f64 {
1691 let turn = (to - from).rem_euclid(std::f64::consts::TAU);
1692 if turn > std::f64::consts::PI {
1693 turn - std::f64::consts::TAU
1694 } else {
1695 turn
1696 }
1697}
1698
1699fn merge_cylinder_full_turn(
1732 older: &FaceRecord,
1733 newer: &FaceRecord,
1734 edges: &HashMap<u64, &EdgeRecord>,
1735 tolerance: f64,
1736 support: &CylinderSupport,
1737 shared_edges: &HashSet<u64>,
1738) -> Result<Option<FaceRecord>, KernelRefusal> {
1739 let debug = std::env::var("BREP_DEBUG_MERGE").is_ok();
1740 if std::env::var("BREP_FULL_TURN_MERGE").as_deref() == Ok("0") {
1742 return Ok(None);
1743 }
1744 let uses = [older, newer]
1748 .iter()
1749 .enumerate()
1750 .flat_map(|(side, face)| {
1751 face.loops
1752 .iter()
1753 .flat_map(|loop_record| &loop_record.coedges)
1754 .filter(|coedge| !edges[&coedge.edge_id].degenerate)
1755 .map(move |coedge| (side, coedge.clone()))
1756 })
1757 .collect::<Vec<_>>();
1758 let Some(x_reference) = uses.iter().find_map(|(_, coedge)| {
1759 let edge = edges[&coedge.edge_id];
1760 let seed = edge.curve.evaluate(edge.t0).ok()?;
1761 let delta = seed.sub(support.origin);
1762 let radial = delta.sub(support.axis.scale(delta.dot(support.axis)));
1763 radial.normalized().ok()
1764 }) else {
1765 return Ok(None);
1766 };
1767 let y_reference = support.axis.cross(x_reference);
1768 let scale = 1.0f64.max(support.origin.length()).max(support.radius);
1769 let band = (tolerance * 100.0).max(1e-7 * scale);
1770 let angular_band = band / support.radius;
1771
1772 struct Station {
1775 axial: f64,
1776 angle: Option<f64>,
1777 }
1778 let station = |point: Vec3| Station {
1779 axial: point.sub(support.origin).dot(support.axis),
1780 angle: cylinder_angle(support, x_reference, y_reference, point),
1781 };
1782 let mut axial_range = [f64::INFINITY, f64::NEG_INFINITY];
1783 let mut samples = Vec::with_capacity(uses.len());
1784 let mut bbox_lo = Vec3::new(f64::INFINITY, f64::INFINITY, f64::INFINITY);
1785 let mut bbox_hi = Vec3::new(f64::NEG_INFINITY, f64::NEG_INFINITY, f64::NEG_INFINITY);
1786 let mut perimeter = 0.0f64;
1789 for (_, coedge) in &uses {
1790 let edge = edges[&coedge.edge_id];
1791 let curve = trimmed_curve(&edge.curve, edge.t0, edge.t1)?;
1792 let [c0, c1] = curve.domain().or_refuse(KernelStage::Sew, "domain")?;
1793 let hull = axial_hull(&curve, support);
1794 axial_range[0] = axial_range[0].min(hull[0]);
1795 axial_range[1] = axial_range[1].max(hull[1]);
1796 perimeter += crate::mass_properties::edge_arc_length(edge).unwrap_or(0.0);
1797 let mut stations = Vec::with_capacity(9);
1798 for index in 0..=8 {
1799 let point = curve
1800 .evaluate(c0 + (c1 - c0) * index as f64 / 8.0)
1801 .or_refuse(KernelStage::Sew, "evaluate")?;
1802 bbox_lo = Vec3::new(bbox_lo.x.min(point.x), bbox_lo.y.min(point.y), bbox_lo.z.min(point.z));
1803 bbox_hi = Vec3::new(bbox_hi.x.max(point.x), bbox_hi.y.max(point.y), bbox_hi.z.max(point.z));
1804 stations.push(station(point));
1805 }
1806 samples.push(stations);
1807 }
1808 if axial_range[1] - axial_range[0] <= tolerance {
1809 return Ok(None);
1810 }
1811 let axial_angle = |stations: &[Station]| -> Option<f64> {
1814 let first = stations.first()?.angle?;
1815 stations
1816 .iter()
1817 .all(|station| {
1818 station
1819 .angle
1820 .is_some_and(|angle| angle_difference(first, angle).abs() <= angular_band)
1821 })
1822 .then_some(first)
1823 };
1824 let mut use_count = HashMap::<u64, usize>::default();
1825 for (_, coedge) in &uses {
1826 *use_count.entry(coedge.edge_id).or_default() += 1;
1827 }
1828 let mut candidates: Vec<(u8, f64)> = Vec::new();
1832 for (index, (side, coedge)) in uses.iter().enumerate() {
1833 if use_count.get(&coedge.edge_id).copied() != Some(2) {
1834 continue;
1835 }
1836 let Some(theta) = axial_angle(&samples[index]) else {
1837 continue;
1838 };
1839 let own_seam = uses
1840 .iter()
1841 .any(|(other_side, other)| {
1842 other.edge_id == coedge.edge_id
1843 && other.id != coedge.id
1844 && other_side == side
1845 && other.forward != coedge.forward
1846 });
1847 let rank = if own_seam { 0 } else { 1 };
1848 if !candidates
1849 .iter()
1850 .any(|(_, known)| angle_difference(*known, theta).abs() <= angular_band)
1851 {
1852 candidates.push((rank, theta));
1853 } else if let Some(known) = candidates
1854 .iter_mut()
1855 .find(|(_, known)| angle_difference(*known, theta).abs() <= angular_band)
1856 {
1857 known.0 = known.0.min(rank);
1858 }
1859 }
1860 candidates.sort_by(|a, b| a.0.cmp(&b.0).then(a.1.total_cmp(&b.1)));
1861 if debug {
1862 eprintln!(
1863 "merge {}x{}: full-turn lane, {} seam candidate(s) {:?}",
1864 older.id,
1865 newer.id,
1866 candidates.len(),
1867 candidates
1868 );
1869 }
1870 candidates.retain(|(rank, _)| *rank == 0);
1874 if candidates.is_empty() {
1875 if debug {
1876 eprintln!(
1877 "merge {}x{}: full-turn lane: no face wraps the turn by itself, the halves stay apart",
1878 older.id, newer.id
1879 );
1880 }
1881 return Ok(None);
1882 }
1883 let weld = crate::tolerance::assembler_weld(tolerance);
1884 let pcurve_limit = crate::KernelTolerances::for_scale(scale, 1e-7)
1889 .pcurve_acceptance(bbox_hi.sub(bbox_lo).length());
1890 let expected_area = face_area(older).or_refuse(KernelStage::Sew, "face_area")?
1891 + face_area(newer).or_refuse(KernelStage::Sew, "face_area")?;
1892 let expected_term = face_volume_contribution(older)
1893 .or_refuse(KernelStage::Sew, "face_volume_contribution")?
1894 + face_volume_contribution(newer).or_refuse(KernelStage::Sew, "face_volume_contribution")?;
1895
1896 'candidate: for (_, theta) in candidates {
1897 let on_seam = |index: usize| {
1898 axial_angle(&samples[index])
1899 .is_some_and(|angle| angle_difference(theta, angle).abs() <= angular_band)
1900 };
1901 let start_direction = x_reference
1903 .scale(theta.cos())
1904 .add(y_reference.scale(theta.sin()));
1905 let generatrix = make_line(
1906 support
1907 .origin
1908 .add(support.axis.scale(axial_range[0]))
1909 .add(start_direction.scale(support.radius)),
1910 support
1911 .origin
1912 .add(support.axis.scale(axial_range[1]))
1913 .add(start_direction.scale(support.radius)),
1914 )
1915 .or_refuse(KernelStage::Sew, "healing.face_merge")?;
1916 let surface = make_revolution(
1917 support.origin,
1918 support.axis,
1919 &generatrix,
1920 std::f64::consts::TAU,
1921 )
1922 .or_refuse(KernelStage::Sew, "make_revolution")?;
1923 let (u_domain, v_domain) = surface_domains(&surface)?;
1924 let (u_mid, v_mid) = (
1925 (u_domain[0] + u_domain[1]) / 2.0,
1926 (v_domain[0] + v_domain[1]) / 2.0,
1927 );
1928 let sample = surface
1929 .evaluate(u_mid, v_mid)
1930 .or_refuse(KernelStage::Sew, "healing.face_merge")?;
1931 let geometric_normal = surface
1932 .normal(u_mid, v_mid)
1933 .or_refuse(KernelStage::Sew, "healing.face_merge")?;
1934 let delta = sample.sub(support.origin);
1935 let radial = delta.sub(support.axis.scale(delta.dot(support.axis)));
1936 let Ok(radial) = radial.normalized() else {
1937 continue;
1938 };
1939 let same_sense = geometric_normal.dot(radial).signum() == support.outward_radial_sign;
1940 let v_of = |axial: f64| {
1941 v_domain[0]
1942 + (axial - axial_range[0]) / (axial_range[1] - axial_range[0])
1943 * (v_domain[1] - v_domain[0])
1944 };
1945
1946 let mut remaining = Vec::new();
1949 for (index, (_, coedge)) in uses.iter().enumerate() {
1950 let seam_line = on_seam(index);
1951 if shared_edges.contains(&coedge.edge_id) && !seam_line {
1952 continue;
1953 }
1954 let edge = edges[&coedge.edge_id];
1955 let mut coedge = coedge.clone();
1956 let mut curve = trimmed_curve(&edge.curve, edge.t0, edge.t1)?;
1957 if !coedge.forward {
1958 curve = curve.reversed().or_refuse(KernelStage::Sew, "reversed")?;
1959 }
1960 if seam_line {
1961 let [c0, c1] = curve.domain().or_refuse(KernelStage::Sew, "domain")?;
1967 let start = curve.evaluate(c0).or_refuse(KernelStage::Sew, "evaluate")?;
1968 let end = curve.evaluate(c1).or_refuse(KernelStage::Sew, "evaluate")?;
1969 let rising = end.sub(start).dot(support.axis) > 0.0;
1970 let far_side = rising == same_sense;
1971 let u = if far_side { u_domain[1] } else { u_domain[0] };
1972 let origin_axial = support.origin.dot(support.axis);
1980 let control_points = curve
1981 .control_points
1982 .iter()
1983 .map(|point| {
1984 let w = point.w;
1985 let axial = Vec3::new(point.x / w, point.y / w, point.z / w)
1986 .dot(support.axis)
1987 - origin_axial;
1988 Vec4 { x: u * w, y: v_of(axial) * w, z: 0.0, w }
1989 })
1990 .collect();
1991 coedge.pcurve = NurbsCurve::new(curve.degree, curve.knots.clone(), control_points)
1992 .or_refuse(KernelStage::Sew, "NurbsCurve::new")?;
1993 } else {
1994 let fit = match crate::fit_pcurve_on_surface(&surface, &curve) {
2001 Ok(fit) => fit,
2002 Err(_) => continue 'candidate,
2003 };
2004 if fit.report.off_surface > band || fit.report.residual > band {
2005 if debug {
2006 eprintln!(
2007 "merge {}x{}: full-turn seam {theta:.4}: edge {} stands {:.3e} off the carrier, fit residual {:.3e} (band {band:.3e})",
2008 older.id, newer.id, coedge.edge_id, fit.report.off_surface, fit.report.residual
2009 );
2010 }
2011 continue 'candidate;
2012 }
2013 coedge.pcurve = fit.curve;
2014 }
2015 remaining.push(coedge);
2016 }
2017 let space = SharedParameterSpace { surface: &surface, weld };
2018 dissolve_slits(&mut remaining, edges, &space);
2019 if debug {
2020 for coedge in &remaining {
2021 let stations = pcurve_stations(coedge)
2022 .map(|[a, m, b]| format!("({:.4},{:.4})->({:.4},{:.4})->({:.4},{:.4})", a.x, a.y, m.x, m.y, b.x, b.y))
2023 .unwrap_or_default();
2024 eprintln!(
2025 " seam {theta:.4} use coedge {} edge {} fwd={} shared={} same_sense={same_sense} uv {stations}",
2026 coedge.id,
2027 coedge.edge_id,
2028 coedge.forward,
2029 shared_edges.contains(&coedge.edge_id)
2030 );
2031 }
2032 }
2033 let Some(mut loops) = walk_cycles(remaining, edges, Some(&space)) else {
2034 if debug {
2035 eprintln!(
2036 "merge {}x{}: full-turn seam {theta:.4}: walk undetermined",
2037 older.id, newer.id
2038 );
2039 }
2040 continue;
2041 };
2042 if loops.is_empty() {
2043 continue;
2044 }
2045 let closed = loops.iter().all(|loop_record| {
2052 let count = loop_record.coedges.len();
2053 (0..count).all(|index| {
2054 let next = &loop_record.coedges[(index + 1) % count];
2055 match (
2056 pcurve_stations(&loop_record.coedges[index]),
2057 pcurve_stations(next),
2058 ) {
2059 (Some(here), Some(there)) => space.coincide(here[2], there[0]),
2060 _ => false,
2061 }
2062 })
2063 });
2064 if !closed {
2065 if debug {
2066 eprintln!(
2067 "merge {}x{}: full-turn seam {theta:.4}: a loop is open in parameter space",
2068 older.id, newer.id
2069 );
2070 }
2071 continue;
2072 }
2073 if debug {
2074 for loop_record in &loops {
2075 eprintln!(
2076 " seam {theta:.4} loop {:?}",
2077 loop_record.coedges.iter().map(|c| (c.edge_id, c.forward)).collect::<Vec<_>>()
2078 );
2079 }
2080 }
2081 loops.sort_by(|first, second| {
2082 let area = |loop_record: &LoopRecord| {
2083 parameter_space_area(&FaceRecord {
2084 id: older.id,
2085 surface: surface.clone(),
2086 same_sense,
2087 loops: vec![loop_record.clone()],
2088 name: None,
2089 })
2090 .map(f64::abs)
2091 };
2092 match (area(first), area(second)) {
2093 (Ok(a), Ok(b)) => b.total_cmp(&a),
2094 _ => std::cmp::Ordering::Equal,
2095 }
2096 });
2097 let merged = FaceRecord {
2098 id: older.id,
2099 surface,
2100 same_sense,
2101 loops,
2102 name: older.name.clone(),
2103 };
2104 let mut worst_trim = 0.0f64;
2109 for coedge in merged.loops.iter().flat_map(|loop_record| &loop_record.coedges) {
2110 let edge = edges[&coedge.edge_id];
2111 let error = crate::topology::coedge_error_floored(
2112 &merged.surface,
2113 &coedge.pcurve,
2114 &edge.curve,
2115 edge,
2116 coedge.forward,
2117 pcurve_limit,
2118 )
2119 .unwrap_or(f64::INFINITY);
2120 worst_trim = worst_trim.max(error);
2121 }
2122 if worst_trim > pcurve_limit {
2123 if debug {
2124 eprintln!(
2125 "merge {}x{}: full-turn seam {theta:.4}: a trim is {worst_trim:.6} off its edge (limit {pcurve_limit:.6})",
2126 older.id, newer.id
2127 );
2128 }
2129 continue;
2130 }
2131 let area =
2132 parameter_space_area(&merged).or_refuse(KernelStage::Sew, "parameter_space_area")?;
2133 if area.abs() <= tolerance * tolerance || area.is_sign_positive() != merged.same_sense {
2134 if debug {
2135 eprintln!(
2136 "merge {}x{}: full-turn seam {theta:.4}: parameter area {area:.3e} vs same_sense {same_sense}",
2137 older.id, newer.id
2138 );
2139 }
2140 continue;
2141 }
2142 let actual = face_area(&merged).or_refuse(KernelStage::Sew, "face_area")?;
2151 let area_bar = band * perimeter + 1e-9 * expected_area.abs();
2152 if (actual - expected_area).abs() > area_bar {
2153 if debug {
2154 eprintln!(
2155 "merge {}x{}: full-turn seam {theta:.4}: area {actual:.9} vs expected {expected_area:.9} (bar {area_bar:.3e})",
2156 older.id, newer.id
2157 );
2158 }
2159 continue;
2160 }
2161 let actual_term =
2162 face_volume_contribution(&merged).or_refuse(KernelStage::Sew, "face_volume_contribution")?;
2163 let reach = bbox_lo.length().max(bbox_hi.length());
2164 let term_bar = band * perimeter * reach / 3.0 + 1e-9 * expected_term.abs().max(expected_area.abs());
2165 if (actual_term - expected_term).abs() > term_bar {
2166 if debug {
2167 eprintln!(
2168 "merge {}x{}: full-turn seam {theta:.4}: volume term {actual_term:.9} vs expected {expected_term:.9} (bar {term_bar:.3e})",
2169 older.id, newer.id
2170 );
2171 }
2172 continue;
2173 }
2174 if debug {
2175 eprintln!(
2176 "merge {}x{}: full-turn MERGE at seam {theta:.4}, {} loop(s); area {actual:.9} vs {expected_area:.9} (bar {area_bar:.3e}), volume term {actual_term:.9} vs {expected_term:.9} (bar {term_bar:.3e})",
2177 older.id,
2178 newer.id,
2179 merged.loops.len()
2180 );
2181 }
2182 return Ok(Some(merged));
2183 }
2184 Ok(None)
2185}
2186
2187
2188fn try_merge_connected_group(
2189 faces: &[FaceRecord],
2190 edges: &HashMap<u64, &EdgeRecord>,
2191 tolerance: f64,
2192 same_carrier_area_tolerance_ratio: f64,
2193 keep_unmerged: &[String],
2194) -> Result<Option<(Vec<usize>, FaceRecord)>, KernelRefusal> {
2195 for seed in 0..faces.len() {
2196 if face_is_pinned(&faces[seed], keep_unmerged) {
2198 continue;
2199 }
2200 let mut component = [seed].into_iter().collect::<HashSet<_>>();
2201 loop {
2202 let mut changed = false;
2203 for candidate in 0..faces.len() {
2204 if component.contains(&candidate)
2205 || face_is_pinned(&faces[candidate], keep_unmerged)
2206 || faces[candidate].same_sense != faces[seed].same_sense
2207 || !same_surface(&faces[candidate].surface, &faces[seed].surface, 1e-7)
2208 {
2209 continue;
2210 }
2211 let candidate_uses = faces[candidate]
2212 .loops
2213 .iter()
2214 .flat_map(|loop_record| &loop_record.coedges);
2215 let adjacent = candidate_uses.into_iter().any(|candidate_use| {
2216 !edges[&candidate_use.edge_id].degenerate
2217 && component.iter().any(|member| {
2218 faces[*member]
2219 .loops
2220 .iter()
2221 .flat_map(|loop_record| &loop_record.coedges)
2222 .any(|member_use| {
2223 member_use.edge_id == candidate_use.edge_id
2224 && member_use.forward != candidate_use.forward
2225 })
2226 })
2227 });
2228 if adjacent {
2229 component.insert(candidate);
2230 changed = true;
2231 }
2232 }
2233 if !changed {
2234 break;
2235 }
2236 }
2237 if component.len() < 2 {
2238 continue;
2239 }
2240
2241 let mut uses_by_edge = HashMap::<u64, Vec<CoedgeRecord>>::default();
2242 for index in &component {
2243 for coedge in faces[*index]
2244 .loops
2245 .iter()
2246 .flat_map(|loop_record| &loop_record.coedges)
2247 {
2248 uses_by_edge
2249 .entry(coedge.edge_id)
2250 .or_default()
2251 .push(coedge.clone());
2252 }
2253 }
2254 if uses_by_edge.values().any(|uses| uses.len() > 2) {
2255 continue;
2256 }
2257 let internal = uses_by_edge
2258 .iter()
2259 .filter_map(|(edge_id, uses)| {
2260 (uses.len() == 2
2261 && !edges[edge_id].degenerate
2262 && uses[0].forward != uses[1].forward)
2263 .then_some(*edge_id)
2264 })
2265 .collect::<HashSet<_>>();
2266 let remaining = uses_by_edge
2267 .into_iter()
2268 .filter(|(edge_id, _)| !internal.contains(edge_id))
2269 .flat_map(|(_, uses)| uses)
2270 .collect::<Vec<_>>();
2271 let space = SharedParameterSpace {
2272 surface: &faces[seed].surface,
2273 weld: crate::tolerance::assembler_weld(tolerance),
2274 };
2275 let Some(mut loops) = walk_cycles(remaining, edges, Some(&space)) else {
2276 continue;
2277 };
2278 if loops.is_empty() {
2279 continue;
2280 }
2281 loops.sort_by(|first, second| {
2282 let area = |loop_record: &LoopRecord| {
2283 parameter_space_area(&FaceRecord {
2284 id: faces[seed].id,
2285 surface: faces[seed].surface.clone(),
2286 same_sense: faces[seed].same_sense,
2287 loops: vec![loop_record.clone()],
2288 name: None,
2289 })
2290 .map(f64::abs)
2291 };
2292 match (area(first), area(second)) {
2293 (Ok(a), Ok(b)) => b.total_cmp(&a),
2294 _ => std::cmp::Ordering::Equal,
2295 }
2296 });
2297 let merged = FaceRecord {
2298 id: faces[seed].id,
2299 surface: faces[seed].surface.clone(),
2300 same_sense: faces[seed].same_sense,
2301 loops,
2302 name: faces[seed].name.clone(),
2303 };
2304 let expected = component
2305 .iter()
2306 .map(|index| parameter_space_area(&faces[*index]))
2307 .collect::<Result<Vec<_>, _>>()
2308 .or_refuse(KernelStage::Sew, "healing.face_merge")?
2309 .into_iter()
2310 .sum::<f64>();
2311 let actual =
2312 parameter_space_area(&merged).or_refuse(KernelStage::Sew, "parameter_space_area")?;
2313 let area_tolerance = 1e-9f64.max(expected.abs() * same_carrier_area_tolerance_ratio);
2314 if (actual - expected).abs() > area_tolerance
2315 || (actual.abs() > 1e-12 && actual.is_sign_positive() != merged.same_sense)
2316 {
2317 continue;
2318 }
2319 let mut indices = component.into_iter().collect::<Vec<_>>();
2320 indices.sort_unstable();
2321 return Ok(Some((indices, merged)));
2322 }
2323 Ok(None)
2324}
2325
2326fn face_is_pinned(face: &FaceRecord, keep_unmerged: &[String]) -> bool {
2331 match &face.name {
2332 Some(name) => keep_unmerged
2333 .iter()
2334 .any(|needle| name.contains(needle.as_str())),
2335 None => false,
2336 }
2337}
2338
2339struct PairMerger<'a> {
2353 slots: Vec<Option<FaceRecord>>,
2354 pinned: Vec<bool>,
2355 edges: &'a HashMap<u64, &'a EdgeRecord>,
2356 uses: HashMap<u64, Vec<usize>>,
2358 candidates: std::collections::BTreeSet<(usize, usize)>,
2360 merged_ids: Vec<u64>,
2362}
2363
2364impl<'a> PairMerger<'a> {
2365 fn new(
2366 faces: Vec<FaceRecord>,
2367 edges: &'a HashMap<u64, &'a EdgeRecord>,
2368 keep_unmerged: &[String],
2369 ) -> Self {
2370 let pinned = faces
2371 .iter()
2372 .map(|face| face_is_pinned(face, keep_unmerged))
2373 .collect::<Vec<_>>();
2374 let mut merger = Self {
2375 slots: faces.into_iter().map(Some).collect(),
2376 pinned,
2377 edges,
2378 uses: HashMap::default(),
2379 candidates: std::collections::BTreeSet::new(),
2380 merged_ids: Vec::new(),
2381 };
2382 for slot in 0..merger.slots.len() {
2383 merger.index_slot(slot);
2384 }
2385 merger
2386 }
2387
2388 fn slot_edge_ids(&self, slot: usize) -> Vec<u64> {
2389 let Some(face) = &self.slots[slot] else {
2390 return Vec::new();
2391 };
2392 let mut ids = face
2393 .loops
2394 .iter()
2395 .flat_map(|loop_record| &loop_record.coedges)
2396 .map(|coedge| coedge.edge_id)
2397 .filter(|edge_id| !self.edges[edge_id].degenerate)
2398 .collect::<Vec<_>>();
2399 ids.sort_unstable();
2400 ids.dedup();
2401 ids
2402 }
2403
2404 fn index_slot(&mut self, slot: usize) {
2407 for edge_id in self.slot_edge_ids(slot) {
2408 let users = self.uses.entry(edge_id).or_default();
2409 for &other in users.iter() {
2410 if other != slot && !self.pinned[other] && !self.pinned[slot] {
2411 self.candidates.insert((other.min(slot), other.max(slot)));
2412 }
2413 }
2414 users.push(slot);
2415 }
2416 }
2417
2418 fn unindex_slot(&mut self, slot: usize) {
2419 for edge_id in self.slot_edge_ids(slot) {
2420 if let Some(users) = self.uses.get_mut(&edge_id) {
2421 users.retain(|user| *user != slot);
2422 }
2423 }
2424 self.candidates
2425 .retain(|(lower, higher)| *lower != slot && *higher != slot);
2426 }
2427
2428 fn run(
2430 &mut self,
2431 budget: usize,
2432 tolerance: f64,
2433 same_carrier_area_tolerance_ratio: f64,
2434 ) -> Result<usize, KernelRefusal> {
2435 let mut merged_count = 0;
2436 while merged_count < budget {
2437 let Some(&(lower, higher)) = self.candidates.iter().next() else {
2438 break;
2439 };
2440 self.candidates.remove(&(lower, higher));
2441 let (Some(older), Some(newer)) = (&self.slots[lower], &self.slots[higher]) else {
2442 continue;
2443 };
2444 let Some(merged) = try_merge_pair(
2445 older,
2446 newer,
2447 self.edges,
2448 tolerance,
2449 same_carrier_area_tolerance_ratio,
2450 )?
2451 else {
2452 continue;
2453 };
2454 self.unindex_slot(higher);
2455 self.unindex_slot(lower);
2456 self.slots[higher] = None;
2457 self.merged_ids.push(merged.id);
2458 self.slots[lower] = Some(merged);
2459 self.index_slot(lower);
2460 merged_count += 1;
2461 }
2462 Ok(merged_count)
2463 }
2464
2465 fn into_faces(self) -> Vec<FaceRecord> {
2466 self.slots.into_iter().flatten().collect()
2467 }
2468}
2469
2470fn merge_same_surface_faces_impl(
2475 solid: &BrepSolid,
2476 tolerance: f64,
2477 validate: bool,
2478 same_carrier_area_tolerance_ratio: f64,
2479 keep_unmerged: &[String],
2480 validation_scope: Option<&HashSet<u64>>,
2481) -> Result<BrepSolid, KernelRefusal> {
2482 let mut result = solid.clone();
2483 let mut merged_ids: Vec<u64> = Vec::new();
2484 let edges = result
2487 .edges
2488 .iter()
2489 .map(|edge| (edge.id, edge))
2490 .collect::<HashMap<_, _>>();
2491 for shell in &mut result.shells {
2492 loop {
2493 if !validate {
2494 if let Some((indices, merged)) = try_merge_connected_group(
2495 &shell.faces,
2496 &edges,
2497 tolerance,
2498 same_carrier_area_tolerance_ratio,
2499 keep_unmerged,
2500 )? {
2501 let first = indices[0];
2502 shell.faces[first] = merged;
2503 for index in indices.into_iter().skip(1).rev() {
2504 shell.faces.remove(index);
2505 }
2506 continue;
2507 }
2508 }
2509 let budget = if validate { usize::MAX } else { 1 };
2513 let mut merger = PairMerger::new(
2514 std::mem::take(&mut shell.faces),
2515 &edges,
2516 keep_unmerged,
2517 );
2518 let merged = merger.run(budget, tolerance, same_carrier_area_tolerance_ratio);
2519 merged_ids.extend(merger.merged_ids.iter().copied());
2520 shell.faces = merger.into_faces();
2521 if merged? == 0 || validate {
2522 break;
2523 }
2524 }
2525 }
2526 let validation_scope = validation_scope.map(|scope| {
2529 let mut scope = scope.clone();
2530 scope.extend(merged_ids);
2531 scope
2532 });
2533 finish_merge(solid, result, validate, validation_scope.as_ref())
2534}
2535
2536pub(crate) fn absorb_faces_into_carriers(
2548 solid: &BrepSolid,
2549 tolerance: f64,
2550 absorbed: &HashSet<u64>,
2551) -> Result<BrepSolid, KernelRefusal> {
2552 let mut result = solid.clone();
2553 let edges = result
2554 .edges
2555 .iter()
2556 .map(|edge| (edge.id, edge))
2557 .collect::<HashMap<_, _>>();
2558 let edge_ids = |face: &FaceRecord| -> HashSet<u64> {
2559 face.loops
2560 .iter()
2561 .flat_map(|loop_record| &loop_record.coedges)
2562 .map(|coedge| coedge.edge_id)
2563 .filter(|edge_id| !edges[edge_id].degenerate)
2564 .collect()
2565 };
2566 for shell in &mut result.shells {
2567 'merge: loop {
2568 for inner in 0..shell.faces.len() {
2569 if !absorbed.contains(&shell.faces[inner].id) {
2570 continue;
2571 }
2572 let inner_edges = edge_ids(&shell.faces[inner]);
2573 for outer in 0..shell.faces.len() {
2574 if outer == inner
2575 || absorbed.contains(&shell.faces[outer].id)
2576 || edge_ids(&shell.faces[outer]).is_disjoint(&inner_edges)
2577 {
2578 continue;
2579 }
2580 let Some(merged) =
2581 try_merge_pair(&shell.faces[outer], &shell.faces[inner], &edges, tolerance, 1e-7)?
2582 else {
2583 continue;
2584 };
2585 shell.faces[outer] = merged;
2586 shell.faces.remove(inner);
2587 continue 'merge;
2588 }
2589 }
2590 break;
2591 }
2592 }
2593 finish_merge(solid, result, true, None)
2594}
2595
2596fn finish_merge(
2599 solid: &BrepSolid,
2600 mut result: BrepSolid,
2601 validate: bool,
2602 validation_scope: Option<&HashSet<u64>>,
2603) -> Result<BrepSolid, KernelRefusal> {
2604 let used_edges = result
2605 .shells
2606 .iter()
2607 .flat_map(|shell| &shell.faces)
2608 .flat_map(|face| &face.loops)
2609 .flat_map(|loop_record| &loop_record.coedges)
2610 .map(|coedge| coedge.edge_id)
2611 .collect::<HashSet<_>>();
2612 result.edges.retain(|edge| used_edges.contains(&edge.id));
2613 let used_vertices = result
2614 .edges
2615 .iter()
2616 .flat_map(|edge| [edge.start_vertex_id, edge.end_vertex_id])
2617 .collect::<HashSet<_>>();
2618 result
2619 .vertices
2620 .retain(|vertex| used_vertices.contains(&vertex.id));
2621 if !validate {
2622 return Ok(result);
2623 }
2624 if std::env::var("BREP_DEBUG_MERGE").is_ok() {
2625 let entry_faces: i64 = solid.shells.iter().map(|s| s.faces.len() as i64).sum();
2626 let entry_holes: i64 = solid
2627 .shells
2628 .iter()
2629 .flat_map(|s| &s.faces)
2630 .map(|f| f.loops.len().saturating_sub(1) as i64)
2631 .sum();
2632 let entry_edges = solid.edges.iter().filter(|e| !e.degenerate).count() as i64;
2633 let entry_used: std::collections::HashSet<u64> = solid
2634 .shells
2635 .iter()
2636 .flat_map(|s| &s.faces)
2637 .flat_map(|f| &f.loops)
2638 .flat_map(|l| &l.coedges)
2639 .map(|c| c.edge_id)
2640 .collect();
2641 eprintln!(
2642 "merge entry census: V={} E={entry_edges} (coedge-referenced {}) F={entry_faces} H={entry_holes} S={} stored_genus={}",
2643 solid.vertices.len(),
2644 entry_used.len(),
2645 solid.shells.len(),
2646 solid.genus
2647 );
2648 }
2649 let face_count = result
2650 .shells
2651 .iter()
2652 .map(|shell| shell.faces.len() as i64)
2653 .sum::<i64>();
2654 let hole_count = result.bounding_hole_count();
2655 let edge_count = result.edges.iter().filter(|edge| !edge.degenerate).count() as i64;
2656 let live_vertices: std::collections::HashSet<u64> = result
2662 .edges
2663 .iter()
2664 .filter(|edge| !edge.degenerate)
2665 .flat_map(|edge| [edge.start_vertex_id, edge.end_vertex_id])
2666 .collect();
2667 let vertex_count = result
2668 .vertices
2669 .iter()
2670 .filter(|vertex| live_vertices.contains(&vertex.id))
2671 .count() as i64;
2672 let euler = vertex_count - edge_count + face_count - hole_count;
2673 let numerator = result.shells.len() as i64 * 2 - euler;
2674 let has_degenerate = result.edges.iter().any(|edge| edge.degenerate);
2682 if numerator < 0 || numerator % 2 != 0 {
2683 if std::env::var("BREP_DEBUG_MERGE").is_ok() {
2684 eprintln!(
2685 "merge euler reject: V={vertex_count} E={edge_count} F={face_count} H={hole_count} S={} euler={euler} numerator={numerator} degenerate={has_degenerate}",
2686 result.shells.len()
2687 );
2688 }
2689 if !has_degenerate
2690 || std::env::var("BREP_MERGE_DEGENERATE_EULER_STRICT").as_deref() == Ok("1")
2691 {
2692 return Err(KernelRefusal::new(
2693 RefusalClass::NonIntegralGenus {
2694 shells: result.shells.len() as u32,
2695 euler: euler as i64,
2696 },
2697 KernelStage::Validate,
2698 "merge_same_surface_faces produced non-integral genus",
2699 ));
2700 }
2701 } else {
2702 result.genus = numerator / 2;
2703 }
2704 let issues = match validation_scope {
2705 Some(scope) => result.validate_scoped(scope),
2706 None => result.validate(),
2707 };
2708 if !issues.is_empty() {
2709 return Err(KernelRefusal::new(
2710 RefusalClass::DegenerateArrangement {
2711 open_edges: 0,
2712 issues: issues.len() as u32,
2713 },
2714 KernelStage::Validate,
2715 format!("merge_same_surface_faces produced invalid topology: {issues:?}"),
2716 ));
2717 }
2718 Ok(result)
2719}
2720
2721pub fn merge_same_surface_faces(
2722 solid: &BrepSolid,
2723 tolerance: f64,
2724) -> Result<BrepSolid, KernelRefusal> {
2725 merge_same_surface_faces_impl(solid, tolerance, true, 1e-7, &[], None)
2726}
2727
2728pub fn merge_same_surface_faces_scoped(
2737 solid: &BrepSolid,
2738 tolerance: f64,
2739 keep_unmerged: &[String],
2740 scope: &HashSet<u64>,
2741) -> Result<BrepSolid, KernelRefusal> {
2742 merge_same_surface_faces_impl(solid, tolerance, true, 1e-7, keep_unmerged, Some(scope))
2743}
2744
2745pub fn merge_same_surface_faces_excluding(
2751 solid: &BrepSolid,
2752 tolerance: f64,
2753 keep_unmerged: &[String],
2754) -> Result<BrepSolid, KernelRefusal> {
2755 merge_same_surface_faces_impl(solid, tolerance, true, 1e-7, keep_unmerged, None)
2756}
2757
2758pub(crate) fn merge_same_surface_faces_open(
2759 solid: &BrepSolid,
2760 tolerance: f64,
2761) -> Result<BrepSolid, KernelRefusal> {
2762 merge_same_surface_faces_impl(solid, tolerance, false, 5e-3, &[], None)
2763}
2764