Another project
1use std::collections::HashMap;
2use std::collections::HashSet;
3
4use bone_types::{
5 BrepEdgeId, BrepFaceId, BrepLoopId, BrepShellId, BrepVertexId, CreaseAngle, EdgeLabel,
6 EdgeRole, FaceFingerprint, FaceLabel, Parameter, Plane3, Point3, SideKind, SketchEntityId,
7 SketchPlaneBasis, Tolerance, UnitVec3, VertexLabel, VertexRole,
8};
9use slotmap::{Key, SlotMap};
10use truck_modeling::{
11 BoundedCurve, Edge, EdgeID, FaceID, ParameterDivision1D, ParametricCurve, ParametricSurface3D,
12 SPHint2D, SearchNearestParameter, Shell, Solid, Surface, VertexID,
13};
14
15use super::convert::{point_from_truck, try_unit_from_truck};
16use super::edges::{EdgeCurve3, crease_from_normals, line_between};
17use super::{BrepEdge, BrepError, BrepFace, BrepLoop, BrepShell, BrepSolid, BrepVertex, LabelKind};
18use crate::curve3::Curve3;
19
20#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
21pub(crate) struct BoundaryIndex(usize);
22
23#[derive(Clone, Copy, Debug)]
24pub(crate) struct EdgeArenaHandle(usize);
25
26#[derive(Clone)]
27pub(crate) struct Arena {
28 solid: Solid,
29 edges: Vec<Edge>,
30 face_index: HashMap<FaceID, BrepFaceId>,
31}
32
33impl Arena {
34 pub(crate) fn boundary(&self, index: BoundaryIndex) -> &Shell {
35 &self.solid.boundaries()[index.0]
36 }
37
38 pub(crate) fn edge(&self, handle: EdgeArenaHandle) -> &Edge {
39 &self.edges[handle.0]
40 }
41
42 pub(crate) fn solid(&self) -> &Solid {
43 &self.solid
44 }
45
46 pub(crate) fn face_index(&self) -> &HashMap<FaceID, BrepFaceId> {
47 &self.face_index
48 }
49
50 pub(crate) fn truck_face(&self, target: BrepFaceId) -> Option<&truck_modeling::Face> {
51 let face_id = self
52 .face_index
53 .iter()
54 .find_map(|(id, brep)| (*brep == target).then_some(*id))?;
55 self.solid.face_iter().find(|face| face.id() == face_id)
56 }
57}
58
59const FACE_PLANE_TOLERANCE: Tolerance = Tolerance::new(1.0e-9);
60
61pub(crate) fn face_plane_basis(face: &truck_modeling::Face) -> Option<SketchPlaneBasis> {
62 let Surface::Plane(plane) = face.surface() else {
63 return None;
64 };
65 let origin = point_from_truck(plane.origin());
66 let x = try_unit_from_truck(plane.u_axis(), FACE_PLANE_TOLERANCE)?;
67 let normal = try_unit_from_truck(plane.normal(), FACE_PLANE_TOLERANCE)?;
68 let outward = if face.orientation() {
69 normal
70 } else {
71 normal.reversed()
72 };
73 let y = outward.cross(x, FACE_PLANE_TOLERANCE).ok()?;
74 SketchPlaneBasis::new(origin, x, y, FACE_PLANE_TOLERANCE).ok()
75}
76
77pub(crate) fn face_fingerprint(face: &truck_modeling::Face) -> Option<FaceFingerprint> {
78 let basis = face_plane_basis(face)?;
79 Some(FaceFingerprint {
80 plane: Plane3::from(basis),
81 centroid: point_from_truck(super::persist::face_centroid(face)),
82 })
83}
84
85const LENGTH_DIVISION_TOLERANCE: Tolerance = Tolerance::new(1.0e-4);
86
87pub(crate) fn edge_points(edge: &Edge) -> Vec<truck_modeling::Point3> {
88 let curve = edge.curve();
89 let (_, points) =
90 curve.parameter_division(curve.range_tuple(), LENGTH_DIVISION_TOLERANCE.value());
91 points
92}
93
94pub(crate) fn edge_length(edge: &Edge) -> f64 {
95 edge_points(edge)
96 .windows(2)
97 .map(|pair| {
98 let span = pair[1] - pair[0];
99 span.x.hypot(span.y).hypot(span.z)
100 })
101 .sum()
102}
103
104pub(crate) struct SolidLabeling {
105 pub(crate) faces: HashMap<FaceID, FaceLabel>,
106 pub(crate) edges: HashMap<EdgeID, EdgeLabel>,
107 pub(crate) vertices: HashMap<VertexID, VertexLabel>,
108 pub(crate) closed_curves: HashSet<SketchEntityId>,
109 pub(crate) edge_curves: HashMap<EdgeID, EdgeCurve3>,
110}
111
112fn suppressed_edge(label: EdgeLabel, closed: &HashSet<SketchEntityId>) -> bool {
113 matches!(label.role, EdgeRole::SideEdge { from, side: SideKind::Seam } if !closed.contains(&from))
114}
115
116fn suppressed_vertex(label: VertexLabel, closed: &HashSet<SketchEntityId>) -> bool {
117 matches!(
118 label.role,
119 VertexRole::StartCapVertex { from, side: SideKind::Seam }
120 | VertexRole::EndCapVertex { from, side: SideKind::Seam }
121 if !closed.contains(&from)
122 )
123}
124
125pub(crate) fn assemble(solid: Solid, labeling: &SolidLabeling) -> Result<BrepSolid, BrepError> {
126 let vertices = build_vertices(&solid, labeling)?;
127 let truck_faces: HashMap<FaceID, truck_modeling::Face> = solid
128 .boundaries()
129 .iter()
130 .flat_map(Shell::face_iter)
131 .map(|face| (face.id(), face.clone()))
132 .collect();
133 let truck_face_adj = gather_truck_face_adjacency(&solid);
134 let edges = build_edges(
135 &solid,
136 labeling,
137 &vertices.by_truck,
138 &vertices.positions,
139 &truck_face_adj,
140 &truck_faces,
141 )?;
142 let faces = build_faces(&solid, labeling, &edges)?;
143
144 let shell_order = ordered_by(&faces.shells, |shell| shell.boundary_index);
145 let face_order = ordered_by(&faces.faces, BrepFace::label);
146 let edge_order = ordered_by(&edges.map, BrepEdge::label);
147 let vertex_order = ordered_by(&vertices.map, BrepVertex::label);
148 let loop_order: Vec<BrepLoopId> = face_order
149 .iter()
150 .flat_map(|face_id| faces.faces[*face_id].loops().iter().copied())
151 .collect();
152
153 let reattach = super::persist::capture(&solid, labeling)?;
154
155 Ok(BrepSolid {
156 arena: Arena {
157 solid,
158 edges: edges.arena,
159 face_index: faces.face_index,
160 },
161 shells: faces.shells,
162 faces: faces.faces,
163 loops: faces.loops,
164 edges: edges.map,
165 vertices: vertices.map,
166 shell_order,
167 face_order,
168 loop_order,
169 edge_order,
170 vertex_order,
171 reattach,
172 })
173}
174
175fn gather_truck_face_adjacency(solid: &Solid) -> HashMap<EdgeID, Vec<FaceID>> {
176 solid.boundaries().iter().flat_map(Shell::face_iter).fold(
177 HashMap::<EdgeID, Vec<FaceID>>::new(),
178 |mut adj, face| {
179 face.boundaries().iter().for_each(|wire| {
180 wire.edge_iter().for_each(|edge| {
181 adj.entry(edge.id()).or_default().push(face.id());
182 });
183 });
184 adj
185 },
186 )
187}
188
189fn ordered_by<K: Key, V, T: Ord>(map: &SlotMap<K, V>, key: impl Fn(&V) -> T) -> Vec<K> {
190 let mut keys: Vec<K> = map.keys().collect();
191 keys.sort_by_cached_key(|k| key(&map[*k]));
192 keys
193}
194
195struct VertexTable {
196 map: SlotMap<BrepVertexId, BrepVertex>,
197 by_truck: HashMap<VertexID, BrepVertexId>,
198 positions: HashMap<BrepVertexId, Point3>,
199}
200
201fn build_vertices(solid: &Solid, labeling: &SolidLabeling) -> Result<VertexTable, BrepError> {
202 let (map, _by_label, by_truck, positions) = solid.vertex_iter().try_fold(
203 (
204 SlotMap::with_key(),
205 HashMap::<VertexLabel, BrepVertexId>::new(),
206 HashMap::<VertexID, BrepVertexId>::new(),
207 HashMap::<BrepVertexId, Point3>::new(),
208 ),
209 |(mut map, mut by_label, mut by_truck, mut positions), vertex| {
210 if by_truck.contains_key(&vertex.id()) {
211 return Ok::<_, BrepError>((map, by_label, by_truck, positions));
212 }
213 let label = *labeling
214 .vertices
215 .get(&vertex.id())
216 .ok_or(BrepError::MissingLabel {
217 kind: LabelKind::Vertex,
218 })?;
219 if suppressed_vertex(label, &labeling.closed_curves) {
220 return Ok((map, by_label, by_truck, positions));
221 }
222 let position = point_from_truck(vertex.point());
223 let brep_id = by_label.get(&label).copied().unwrap_or_else(|| {
224 let id = map.insert_with_key(|id| BrepVertex {
225 id,
226 label,
227 position,
228 });
229 by_label.insert(label, id);
230 id
231 });
232 by_truck.insert(vertex.id(), brep_id);
233 positions.entry(brep_id).or_insert(position);
234 Ok((map, by_label, by_truck, positions))
235 },
236 )?;
237 Ok(VertexTable {
238 map,
239 by_truck,
240 positions,
241 })
242}
243
244struct EdgeTable {
245 map: SlotMap<BrepEdgeId, BrepEdge>,
246 by_truck: HashMap<EdgeID, BrepEdgeId>,
247 arena: Vec<Edge>,
248}
249
250struct EdgeAccum {
251 handles: Vec<EdgeArenaHandle>,
252 incident: Vec<BrepVertexId>,
253 analytic: Option<EdgeCurve3>,
254}
255
256fn build_edges(
257 solid: &Solid,
258 labeling: &SolidLabeling,
259 vertex_dedup: &HashMap<VertexID, BrepVertexId>,
260 vertex_positions: &HashMap<BrepVertexId, Point3>,
261 truck_face_adj: &HashMap<EdgeID, Vec<FaceID>>,
262 truck_faces: &HashMap<FaceID, truck_modeling::Face>,
263) -> Result<EdgeTable, BrepError> {
264 let (accum, arena, truck_label) = solid.edge_iter().try_fold(
265 (
266 HashMap::<EdgeLabel, EdgeAccum>::new(),
267 Vec::<Edge>::new(),
268 HashMap::<EdgeID, EdgeLabel>::new(),
269 ),
270 |(mut accum, mut arena, mut truck_label), edge| {
271 if truck_label.contains_key(&edge.id()) {
272 return Ok::<_, BrepError>((accum, arena, truck_label));
273 }
274 let label = *labeling
275 .edges
276 .get(&edge.id())
277 .ok_or(BrepError::MissingLabel {
278 kind: LabelKind::Edge,
279 })?;
280 if suppressed_edge(label, &labeling.closed_curves) {
281 return Ok((accum, arena, truck_label));
282 }
283 let handle = EdgeArenaHandle(arena.len());
284 arena.push(edge.clone());
285 let accumulator = accum.entry(label).or_insert_with(|| EdgeAccum {
286 handles: Vec::new(),
287 incident: Vec::new(),
288 analytic: None,
289 });
290 accumulator.handles.push(handle);
291 if accumulator.analytic.is_none() {
292 accumulator.analytic = labeling.edge_curves.get(&edge.id()).cloned();
293 }
294 [edge.front().id(), edge.back().id()]
295 .into_iter()
296 .filter_map(|truck_vertex| vertex_dedup.get(&truck_vertex).copied())
297 .for_each(|brep_vertex| accumulator.incident.push(brep_vertex));
298 truck_label.insert(edge.id(), label);
299 Ok((accum, arena, truck_label))
300 },
301 )?;
302
303 let mut ordered_edges: Vec<(EdgeLabel, EdgeAccum)> = accum.into_iter().collect();
304 ordered_edges.sort_by_key(|(label, _)| *label);
305 let (map, label_to_id) = ordered_edges.into_iter().fold(
306 (SlotMap::with_key(), HashMap::<EdgeLabel, BrepEdgeId>::new()),
307 |(mut map, mut label_to_id), (label, slot)| {
308 let primary = &arena[slot.handles[0].0];
309 let curve = resolve_curve(slot.analytic, primary);
310 let vertices = ordered_endpoints(&slot.incident, &curve, vertex_positions);
311 let crease = compute_crease(truck_face_adj.get(&primary.id()), truck_faces, primary);
312 let id = map.insert_with_key(|id| BrepEdge {
313 id,
314 label,
315 handles: slot.handles,
316 vertices,
317 curve,
318 crease,
319 });
320 label_to_id.insert(label, id);
321 (map, label_to_id)
322 },
323 );
324
325 let by_truck = truck_label
326 .into_iter()
327 .map(|(truck_id, label)| (truck_id, label_to_id[&label]))
328 .collect();
329
330 Ok(EdgeTable {
331 map,
332 by_truck,
333 arena,
334 })
335}
336
337fn resolve_curve(analytic: Option<EdgeCurve3>, primary: &Edge) -> EdgeCurve3 {
338 analytic.unwrap_or_else(|| {
339 let front = point_from_truck(primary.absolute_front().point());
340 let back = point_from_truck(primary.absolute_back().point());
341 line_between(front, back)
342 })
343}
344
345fn compute_crease(
346 adjacent: Option<&Vec<FaceID>>,
347 truck_faces: &HashMap<FaceID, truck_modeling::Face>,
348 edge: &Edge,
349) -> CreaseAngle {
350 let Some(face_ids) = adjacent else {
351 return CreaseAngle::FLAT;
352 };
353 let midpoint = edge_midpoint(edge);
354 let normals: Vec<UnitVec3> = face_ids
355 .iter()
356 .filter_map(|face_id| truck_faces.get(face_id))
357 .filter_map(|face| face_normal_at(face, midpoint))
358 .collect();
359 match normals.as_slice() {
360 [n1, n2] => crease_from_normals(*n1, *n2),
361 _ => CreaseAngle::FLAT,
362 }
363}
364
365fn edge_midpoint(edge: &Edge) -> truck_modeling::Point3 {
366 let curve = edge.curve();
367 let (t0, t1) = curve.range_tuple();
368 curve.subs(f64::midpoint(t0, t1))
369}
370
371fn face_normal_at(face: &truck_modeling::Face, point: truck_modeling::Point3) -> Option<UnitVec3> {
372 let surface = face.surface();
373 let (u, v) = surface.search_nearest_parameter(point, SPHint2D::None, 20)?;
374 let mut normal = surface.normal(u, v);
375 if !face.orientation() {
376 normal = -normal;
377 }
378 try_unit_from_truck(normal, Tolerance::new(1.0e-9))
379}
380
381fn ordered_endpoints(
382 incident: &[BrepVertexId],
383 curve: &EdgeCurve3,
384 vertex_positions: &HashMap<BrepVertexId, Point3>,
385) -> [BrepVertexId; 2] {
386 let counts = incident.iter().fold(
387 HashMap::<BrepVertexId, usize>::new(),
388 |mut counts, vertex| {
389 *counts.entry(*vertex).or_insert(0) += 1;
390 counts
391 },
392 );
393 let mut odd: Vec<BrepVertexId> = counts
394 .iter()
395 .filter_map(|(vertex, count)| (*count % 2 == 1).then_some(*vertex))
396 .collect();
397 odd.sort_unstable();
398 if let [a, b] = odd.as_slice() {
399 let start = curve.evaluate(Parameter::new(0.0));
400 let a_dist = vertex_positions
401 .get(a)
402 .map_or(f64::INFINITY, |pos| squared_distance(*pos, start));
403 let b_dist = vertex_positions
404 .get(b)
405 .map_or(f64::INFINITY, |pos| squared_distance(*pos, start));
406 if a_dist <= b_dist { [*a, *b] } else { [*b, *a] }
407 } else {
408 let representative = counts
409 .keys()
410 .copied()
411 .min()
412 .or_else(|| vertex_positions.keys().copied().min())
413 .unwrap_or_default();
414 [representative, representative]
415 }
416}
417
418fn squared_distance(a: Point3, b: Point3) -> f64 {
419 let (ax, ay, az) = a.coords_mm();
420 let (bx, by, bz) = b.coords_mm();
421 let dx = ax - bx;
422 let dy = ay - by;
423 let dz = az - bz;
424 dx * dx + dy * dy + dz * dz
425}
426
427struct FaceTable {
428 faces: SlotMap<BrepFaceId, BrepFace>,
429 loops: SlotMap<BrepLoopId, BrepLoop>,
430 shells: SlotMap<BrepShellId, BrepShell>,
431 face_index: HashMap<FaceID, BrepFaceId>,
432}
433
434#[derive(Default)]
435struct Gathered {
436 adjacency: HashMap<EdgeID, Vec<FaceLabel>>,
437 patches: HashMap<FaceLabel, Vec<Vec<Vec<EdgeID>>>>,
438 shell_members: Vec<Vec<FaceLabel>>,
439 face_to_label: Vec<(FaceID, FaceLabel)>,
440}
441
442fn build_faces(
443 solid: &Solid,
444 labeling: &SolidLabeling,
445 edges: &EdgeTable,
446) -> Result<FaceTable, BrepError> {
447 let Gathered {
448 adjacency,
449 patches,
450 shell_members,
451 face_to_label,
452 } = gather_faces(solid, labeling)?;
453
454 let mut ordered_patches: Vec<(FaceLabel, Vec<Vec<Vec<EdgeID>>>)> =
455 patches.into_iter().collect();
456 ordered_patches.sort_by_key(|(label, _)| *label);
457 let (faces, loops, label_to_face) = ordered_patches.into_iter().fold(
458 (
459 SlotMap::with_key(),
460 SlotMap::with_key(),
461 HashMap::<FaceLabel, BrepFaceId>::new(),
462 ),
463 |(mut faces, mut loops, mut label_to_face), (label, patch_list)| {
464 let loop_ids = face_loops(&patch_list, label, &adjacency, edges, &mut loops);
465 let id = faces.insert_with_key(|id| BrepFace {
466 id,
467 label,
468 loops: loop_ids,
469 });
470 label_to_face.insert(label, id);
471 (faces, loops, label_to_face)
472 },
473 );
474
475 let shells = shell_members.into_iter().enumerate().fold(
476 SlotMap::with_key(),
477 |mut shells, (boundary, members)| {
478 let face_ids = dedup_preserving(members)
479 .into_iter()
480 .map(|label| label_to_face[&label])
481 .collect();
482 shells.insert_with_key(|id| BrepShell {
483 id,
484 boundary_index: BoundaryIndex(boundary),
485 faces: face_ids,
486 });
487 shells
488 },
489 );
490
491 let face_index = face_to_label
492 .into_iter()
493 .map(|(face_id, label)| (face_id, label_to_face[&label]))
494 .collect();
495
496 Ok(FaceTable {
497 faces,
498 loops,
499 shells,
500 face_index,
501 })
502}
503
504fn gather_faces(solid: &Solid, labeling: &SolidLabeling) -> Result<Gathered, BrepError> {
505 solid
506 .boundaries()
507 .iter()
508 .try_fold(Gathered::default(), |mut gathered, shell| {
509 let members = shell
510 .face_iter()
511 .map(|face| {
512 let label = *labeling
513 .faces
514 .get(&face.id())
515 .ok_or(BrepError::MissingLabel {
516 kind: LabelKind::Face,
517 })?;
518 let wires: Vec<Vec<EdgeID>> = face
519 .boundaries()
520 .iter()
521 .map(|wire| wire.edge_iter().map(Edge::id).collect())
522 .collect();
523 wires.iter().flatten().for_each(|edge_id| {
524 gathered.adjacency.entry(*edge_id).or_default().push(label);
525 });
526 gathered.patches.entry(label).or_default().push(wires);
527 gathered.face_to_label.push((face.id(), label));
528 Ok::<FaceLabel, BrepError>(label)
529 })
530 .collect::<Result<Vec<_>, _>>()?;
531 gathered.shell_members.push(members);
532 Ok(gathered)
533 })
534}
535
536fn face_loops(
537 patches: &[Vec<Vec<EdgeID>>],
538 label: FaceLabel,
539 adjacency: &HashMap<EdgeID, Vec<FaceLabel>>,
540 edges: &EdgeTable,
541 loops: &mut SlotMap<BrepLoopId, BrepLoop>,
542) -> Vec<BrepLoopId> {
543 if let [single] = patches {
544 single
545 .iter()
546 .filter_map(|wire| {
547 let loop_edges =
548 dedup_cycle(wire.iter().map(|edge_id| edges.by_truck[edge_id]).collect());
549 (!loop_edges.is_empty()).then(|| {
550 loops.insert_with_key(|id| BrepLoop {
551 id,
552 edges: loop_edges,
553 })
554 })
555 })
556 .collect()
557 } else {
558 let mut seen = HashSet::new();
559 let boundary: Vec<BrepEdgeId> = patches
560 .iter()
561 .flatten()
562 .flatten()
563 .filter(|edge_id| !internal_to_group(adjacency, **edge_id, label))
564 .filter_map(|edge_id| {
565 let brep_id = edges.by_truck[edge_id];
566 seen.insert(brep_id).then_some(brep_id)
567 })
568 .collect();
569 chain_loops(boundary, &edges.map)
570 .into_iter()
571 .map(|loop_edges| {
572 loops.insert_with_key(|id| BrepLoop {
573 id,
574 edges: loop_edges,
575 })
576 })
577 .collect()
578 }
579}
580
581fn internal_to_group(
582 adjacency: &HashMap<EdgeID, Vec<FaceLabel>>,
583 edge_id: EdgeID,
584 label: FaceLabel,
585) -> bool {
586 adjacency
587 .get(&edge_id)
588 .is_some_and(|adjacent| adjacent.len() == 2 && adjacent.iter().all(|other| *other == label))
589}
590
591fn chain_loops(
592 boundary: Vec<BrepEdgeId>,
593 edges: &SlotMap<BrepEdgeId, BrepEdge>,
594) -> Vec<Vec<BrepEdgeId>> {
595 let mut sorted = boundary;
596 sorted.sort_by_key(|edge| edges[*edge].label());
597 let (closed, open): (Vec<BrepEdgeId>, Vec<BrepEdgeId>) = sorted
598 .into_iter()
599 .partition(|edge| edges[*edge].vertices()[0] == edges[*edge].vertices()[1]);
600 let closed_loops = closed.into_iter().map(|edge| vec![edge]);
601 closed_loops.chain(walk_open(open, edges)).collect()
602}
603
604fn walk_open(open: Vec<BrepEdgeId>, edges: &SlotMap<BrepEdgeId, BrepEdge>) -> Vec<Vec<BrepEdgeId>> {
605 let mut remaining = open;
606 std::iter::from_fn(move || {
607 let first = (!remaining.is_empty()).then(|| remaining.remove(0))?;
608 let start = edges[first].vertices()[0];
609 let next = edges[first].vertices()[1];
610 Some(extend_loop(next, start, &mut remaining, edges, vec![first]))
611 })
612 .collect()
613}
614
615fn extend_loop(
616 current: BrepVertexId,
617 start: BrepVertexId,
618 remaining: &mut Vec<BrepEdgeId>,
619 edges: &SlotMap<BrepEdgeId, BrepEdge>,
620 acc: Vec<BrepEdgeId>,
621) -> Vec<BrepEdgeId> {
622 if current == start {
623 return acc;
624 }
625 match remaining
626 .iter()
627 .position(|edge| edges[*edge].vertices().contains(¤t))
628 {
629 None => acc,
630 Some(position) => {
631 let edge = remaining.remove(position);
632 let ends = edges[edge].vertices();
633 let next = if ends[0] == current { ends[1] } else { ends[0] };
634 extend_loop(
635 next,
636 start,
637 remaining,
638 edges,
639 acc.into_iter().chain(std::iter::once(edge)).collect(),
640 )
641 }
642 }
643}
644
645fn dedup_cycle(ids: Vec<BrepEdgeId>) -> Vec<BrepEdgeId> {
646 let mut out = ids.into_iter().fold(Vec::new(), |mut acc, id| {
647 if acc.last() != Some(&id) {
648 acc.push(id);
649 }
650 acc
651 });
652 if out.len() > 1 && out.first() == out.last() {
653 out.pop();
654 }
655 out
656}
657
658fn dedup_preserving(labels: Vec<FaceLabel>) -> Vec<FaceLabel> {
659 let mut seen = HashSet::new();
660 labels
661 .into_iter()
662 .filter(|label| seen.insert(*label))
663 .collect()
664}