Another project
1use std::collections::{BTreeMap, BTreeSet};
2
3use bone_kernel::{
4 Arc2, BrepError, Circle2, Curve2Kind, ExtrudeProfile, Line2, ProfileDefect, ProfileEdge,
5 ProfileLoop,
6};
7use bone_types::{Plane3, Point2, SketchEntityId, Tolerance};
8
9use crate::sketch::{ArcData, CircleData, LineData, Sketch, SketchEntity};
10
11const PROFILE_TOLERANCE: Tolerance = Tolerance::new(1.0e-9);
12
13pub(crate) fn build_profile(sketch: &Sketch) -> Result<ExtrudeProfile, BrepError> {
14 let plane = Plane3::from(sketch.plane());
15 let circles = circle_loops(sketch)?;
16 let chains = chain_loops(sketch)?;
17 let loops = circles.into_iter().chain(chains).collect();
18 Ok(ExtrudeProfile::new(plane, loops))
19}
20
21fn defect(reason: ProfileDefect) -> BrepError {
22 BrepError::InvalidProfile { reason }
23}
24
25fn point_at(sketch: &Sketch, id: SketchEntityId) -> Point2 {
26 let Some(SketchEntity::Point(point)) = sketch.entities().get(id) else {
27 unreachable!("Sketch validation guarantees entity references resolve to points");
28 };
29 point.at()
30}
31
32fn circle_loops(sketch: &Sketch) -> Result<Vec<ProfileLoop>, BrepError> {
33 sketch
34 .entity_order()
35 .iter()
36 .filter_map(|id| match sketch.entities().get(*id) {
37 Some(SketchEntity::Circle(circle)) if !circle.for_construction() => {
38 Some((*id, *circle))
39 }
40 _ => None,
41 })
42 .map(|(id, circle)| circle_loop(sketch, id, circle))
43 .collect()
44}
45
46fn circle_loop(
47 sketch: &Sketch,
48 id: SketchEntityId,
49 circle: CircleData,
50) -> Result<ProfileLoop, BrepError> {
51 let center = point_at(sketch, circle.center());
52 let disk = Circle2::new(center, circle.radius(), PROFILE_TOLERANCE)
53 .map_err(|_| defect(ProfileDefect::ZeroArea))?;
54 Ok(ProfileLoop::Closed {
55 curve: Curve2Kind::Circle(disk),
56 curve_entity: id,
57 })
58}
59
60#[derive(Copy, Clone)]
61enum EdgeCurve {
62 Line(Line2),
63 Arc(Arc2),
64}
65
66impl EdgeCurve {
67 fn into_kind(self) -> Curve2Kind {
68 match self {
69 Self::Line(line) => Curve2Kind::Line(line),
70 Self::Arc(arc) => Curve2Kind::Arc(arc),
71 }
72 }
73
74 fn reversed(self) -> Result<Self, BrepError> {
75 match self {
76 Self::Line(line) => Line2::new(line.end(), line.start(), PROFILE_TOLERANCE)
77 .map(Self::Line)
78 .map_err(|_| defect(ProfileDefect::ZeroArea)),
79 Self::Arc(arc) => Arc2::new(
80 arc.center(),
81 arc.radius(),
82 arc.start_angle() + arc.sweep_angle(),
83 -arc.sweep_angle(),
84 PROFILE_TOLERANCE,
85 )
86 .map(Self::Arc)
87 .map_err(|_| defect(ProfileDefect::ZeroArea)),
88 }
89 }
90}
91
92#[derive(Copy, Clone)]
93struct RawEdge {
94 entity: SketchEntityId,
95 from: SketchEntityId,
96 to: SketchEntityId,
97 curve: EdgeCurve,
98}
99
100impl RawEdge {
101 fn other(self, point: SketchEntityId) -> SketchEntityId {
102 debug_assert!(
103 point == self.from || point == self.to,
104 "other() requires a vertex of this edge"
105 );
106 if point == self.from {
107 self.to
108 } else {
109 self.from
110 }
111 }
112
113 fn oriented(self, start: SketchEntityId) -> Result<Curve2Kind, BrepError> {
114 if start == self.from {
115 Ok(self.curve.into_kind())
116 } else {
117 self.curve.reversed().map(EdgeCurve::into_kind)
118 }
119 }
120}
121
122fn raw_edges(sketch: &Sketch) -> Result<Vec<RawEdge>, BrepError> {
123 sketch
124 .entity_order()
125 .iter()
126 .filter_map(|id| match sketch.entities().get(*id) {
127 Some(SketchEntity::Line(line)) if !line.for_construction() => {
128 Some(line_edge(sketch, *id, *line))
129 }
130 Some(SketchEntity::Arc(arc)) if !arc.for_construction() => {
131 Some(arc_edge(sketch, *id, *arc))
132 }
133 _ => None,
134 })
135 .collect()
136}
137
138fn line_edge(sketch: &Sketch, id: SketchEntityId, line: LineData) -> Result<RawEdge, BrepError> {
139 let start = point_at(sketch, line.a());
140 let end = point_at(sketch, line.b());
141 let segment =
142 Line2::new(start, end, PROFILE_TOLERANCE).map_err(|_| defect(ProfileDefect::ZeroArea))?;
143 Ok(RawEdge {
144 entity: id,
145 from: line.a(),
146 to: line.b(),
147 curve: EdgeCurve::Line(segment),
148 })
149}
150
151fn arc_edge(sketch: &Sketch, id: SketchEntityId, arc: ArcData) -> Result<RawEdge, BrepError> {
152 let center = point_at(sketch, arc.center());
153 let start = point_at(sketch, arc.start());
154 let end = point_at(sketch, arc.end());
155 let curve = Arc2::from_center_start_end(center, start, end, PROFILE_TOLERANCE)
156 .map_err(|_| defect(ProfileDefect::ZeroArea))?;
157 Ok(RawEdge {
158 entity: id,
159 from: arc.start(),
160 to: arc.end(),
161 curve: EdgeCurve::Arc(curve),
162 })
163}
164
165type Incidence = BTreeMap<SketchEntityId, [usize; 2]>;
166
167fn chain_loops(sketch: &Sketch) -> Result<Vec<ProfileLoop>, BrepError> {
168 let edges = raw_edges(sketch)?;
169 if edges.is_empty() {
170 return Ok(Vec::new());
171 }
172 let incidence = incidence(&edges)?;
173 walk_all(&edges, &incidence)
174}
175
176fn incidence(edges: &[RawEdge]) -> Result<Incidence, BrepError> {
177 let grouped: BTreeMap<SketchEntityId, Vec<usize>> =
178 edges
179 .iter()
180 .enumerate()
181 .fold(BTreeMap::new(), |mut acc, (index, edge)| {
182 acc.entry(edge.from).or_default().push(index);
183 acc.entry(edge.to).or_default().push(index);
184 acc
185 });
186 grouped
187 .into_iter()
188 .map(|(point, indices)| match indices.as_slice() {
189 [a, b] => Ok((point, [*a, *b])),
190 [_] => Err(defect(ProfileDefect::OpenLoop)),
191 _ => Err(defect(ProfileDefect::BranchingVertex)),
192 })
193 .collect()
194}
195
196fn other_edge(
197 incidence: &Incidence,
198 point: SketchEntityId,
199 current: usize,
200) -> Result<usize, BrepError> {
201 match incidence.get(&point) {
202 Some(&[a, b]) if a == current => Ok(b),
203 Some(&[a, b]) if b == current => Ok(a),
204 _ => Err(defect(ProfileDefect::OpenLoop)),
205 }
206}
207
208#[derive(Copy, Clone)]
209struct Step {
210 edge: usize,
211 from: SketchEntityId,
212}
213
214fn walk_all(edges: &[RawEdge], incidence: &Incidence) -> Result<Vec<ProfileLoop>, BrepError> {
215 let (_, loops) = (0..edges.len()).try_fold(
216 (BTreeSet::<usize>::new(), Vec::<ProfileLoop>::new()),
217 |(visited, mut loops), start| {
218 if visited.contains(&start) {
219 return Ok((visited, loops));
220 }
221 let steps = walk_cycle(edges, incidence, start)?;
222 let next_visited = steps.iter().fold(visited, |mut acc, step| {
223 acc.insert(step.edge);
224 acc
225 });
226 let profile_edges = steps
227 .iter()
228 .map(|step| {
229 let edge = edges[step.edge];
230 Ok(ProfileEdge::new(
231 edge.oriented(step.from)?,
232 edge.entity,
233 step.from,
234 ))
235 })
236 .collect::<Result<Vec<_>, BrepError>>()?;
237 loops.push(ProfileLoop::Open(profile_edges));
238 Ok((next_visited, loops))
239 },
240 )?;
241 Ok(loops)
242}
243
244enum Walk {
245 Going {
246 edge: usize,
247 from: SketchEntityId,
248 steps: Vec<Step>,
249 },
250 Closed(Vec<Step>),
251}
252
253fn walk_cycle(
254 edges: &[RawEdge],
255 incidence: &Incidence,
256 start: usize,
257) -> Result<Vec<Step>, BrepError> {
258 let origin = edges[start].from;
259 let walk = (0..edges.len()).try_fold(
260 Walk::Going {
261 edge: start,
262 from: origin,
263 steps: Vec::new(),
264 },
265 |state, _| match state {
266 Walk::Closed(steps) => Ok(Walk::Closed(steps)),
267 Walk::Going {
268 edge,
269 from,
270 mut steps,
271 } => {
272 let next_point = edges[edge].other(from);
273 steps.push(Step { edge, from });
274 if next_point == origin {
275 Ok(Walk::Closed(steps))
276 } else {
277 let next_edge = other_edge(incidence, next_point, edge)?;
278 Ok(Walk::Going {
279 edge: next_edge,
280 from: next_point,
281 steps,
282 })
283 }
284 }
285 },
286 )?;
287 match walk {
288 Walk::Closed(steps) => Ok(steps),
289 Walk::Going { .. } => Err(defect(ProfileDefect::OpenLoop)),
290 }
291}
292
293#[cfg(test)]
294mod tests {
295 use super::build_profile;
296 use crate::sketch::{EditOutcome, Sketch, SketchEdit, SketchEntity};
297 use bone_kernel::{
298 BrepError, BrepSolid, Curve2Kind, ExtrudeDirection, ExtrudeEndCondition, ExtrudeFeature,
299 ExtrudeSense, MergeResult, ProfileDefect, ProfileLoop, evaluate_extrude,
300 };
301 use bone_types::{
302 FeatureId, Length, Point2, Point3, PositiveLength, SketchEntityId, SketchId,
303 SketchPlaneBasis, Tolerance, UnitVec3, millimeter,
304 };
305 use slotmap::{Key, KeyData};
306
307 const TOL: Tolerance = Tolerance::new(1e-9);
308
309 fn plane() -> SketchPlaneBasis {
310 let Ok(basis) = SketchPlaneBasis::new(
311 Point3::origin(),
312 UnitVec3::x_axis(),
313 UnitVec3::y_axis(),
314 TOL,
315 ) else {
316 panic!("xy plane is orthonormal");
317 };
318 basis
319 }
320
321 fn feature_id(idx: u32) -> FeatureId {
322 FeatureId::from(KeyData::from_ffi((1u64 << 32) | u64::from(idx)))
323 }
324
325 fn point(sketch: Sketch, x: f64, y: f64) -> (Sketch, SketchEntityId) {
326 let Ok((next, EditOutcome::Entity(id))) = sketch.apply(SketchEdit::AddEntity(
327 SketchEntity::point(Point2::from_mm(x, y)),
328 )) else {
329 panic!("add point");
330 };
331 (next, id)
332 }
333
334 fn line(
335 sketch: Sketch,
336 a: SketchEntityId,
337 b: SketchEntityId,
338 construction: bool,
339 ) -> (Sketch, SketchEntityId) {
340 let Ok((next, EditOutcome::Entity(id))) = sketch.apply(SketchEdit::AddEntity(
341 SketchEntity::line(a, b, construction),
342 )) else {
343 panic!("add line");
344 };
345 (next, id)
346 }
347
348 fn arc(
349 sketch: Sketch,
350 center: SketchEntityId,
351 start: SketchEntityId,
352 end: SketchEntityId,
353 ) -> (Sketch, SketchEntityId) {
354 let Ok((next, EditOutcome::Entity(id))) = sketch.apply(SketchEdit::AddEntity(
355 SketchEntity::arc(center, start, end, false),
356 )) else {
357 panic!("add arc");
358 };
359 (next, id)
360 }
361
362 fn circle(sketch: Sketch, center: SketchEntityId, radius_mm: f64) -> (Sketch, SketchEntityId) {
363 let Ok((next, EditOutcome::Entity(id))) = sketch.apply(SketchEdit::AddEntity(
364 SketchEntity::circle(center, Length::new::<millimeter>(radius_mm), false),
365 )) else {
366 panic!("add circle");
367 };
368 (next, id)
369 }
370
371 fn blind(depth_mm: f64) -> ExtrudeFeature {
372 let Ok(depth) = PositiveLength::new(Length::new::<millimeter>(depth_mm)) else {
373 panic!("{depth_mm} mm is positive");
374 };
375 ExtrudeFeature {
376 sketch: SketchId::null(),
377 direction: ExtrudeDirection::Normal {
378 sense: ExtrudeSense::Forward,
379 },
380 end_condition: ExtrudeEndCondition::Blind { depth },
381 draft: None,
382 thin_wall: None,
383 merge_result: MergeResult::Merge,
384 }
385 }
386
387 fn extrude(sketch: &Sketch) -> Result<BrepSolid, BrepError> {
388 let profile = build_profile(sketch)?;
389 evaluate_extrude(feature_id(1), &profile, &blind(4.0))
390 }
391
392 fn corners(sketch: Sketch) -> (Sketch, [SketchEntityId; 4]) {
393 let (sketch, p0) = point(sketch, 0.0, 0.0);
394 let (sketch, p1) = point(sketch, 10.0, 0.0);
395 let (sketch, p2) = point(sketch, 10.0, 5.0);
396 let (sketch, p3) = point(sketch, 0.0, 5.0);
397 (sketch, [p0, p1, p2, p3])
398 }
399
400 #[test]
401 fn rectangle_builds_one_quad_loop() {
402 let (sketch, [p0, p1, p2, p3]) = corners(Sketch::new(plane()));
403 let (sketch, l0) = line(sketch, p0, p1, false);
404 let (sketch, l1) = line(sketch, p1, p2, false);
405 let (sketch, l2) = line(sketch, p2, p3, false);
406 let (sketch, l3) = line(sketch, p3, p0, false);
407
408 let Ok(profile) = build_profile(&sketch) else {
409 panic!("rectangle is a buildable profile");
410 };
411 let [single] = profile.loops() else {
412 panic!("rectangle is one loop");
413 };
414 let ProfileLoop::Open(edges) = single else {
415 panic!("a line loop is open");
416 };
417 assert_eq!(edges.len(), 4);
418 let entities: Vec<SketchEntityId> = edges.iter().map(|edge| edge.curve_entity()).collect();
419 assert_eq!(entities, vec![l0, l1, l2, l3]);
420 let walk_corners: Vec<SketchEntityId> = edges.iter().map(|edge| edge.corner()).collect();
421 assert_eq!(walk_corners, vec![p0, p1, p2, p3]);
422 assert!(
423 edges
424 .iter()
425 .all(|edge| matches!(edge.curve(), Curve2Kind::Line(_)))
426 );
427 }
428
429 #[test]
430 fn rectangle_extrudes_to_closed_solid() {
431 let (sketch, [p0, p1, p2, p3]) = corners(Sketch::new(plane()));
432 let (sketch, _) = line(sketch, p0, p1, false);
433 let (sketch, _) = line(sketch, p1, p2, false);
434 let (sketch, _) = line(sketch, p2, p3, false);
435 let (sketch, _) = line(sketch, p3, p0, false);
436 let Ok(solid) = extrude(&sketch) else {
437 panic!("rectangle extrudes");
438 };
439 assert_eq!(solid.iter_faces().count(), 6);
440 assert!(solid.validate(TOL).is_ok());
441 }
442
443 #[test]
444 fn mixed_edge_orientation_still_assembles() {
445 let (sketch, [p0, p1, p2, p3]) = corners(Sketch::new(plane()));
446 let (sketch, _) = line(sketch, p0, p1, false);
447 let (sketch, _) = line(sketch, p2, p1, false);
448 let (sketch, _) = line(sketch, p2, p3, false);
449 let (sketch, _) = line(sketch, p0, p3, false);
450 let Ok(solid) = extrude(&sketch) else {
451 panic!("the walk reverses backwards edges");
452 };
453 assert_eq!(solid.iter_faces().count(), 6);
454 assert!(solid.validate(TOL).is_ok());
455 }
456
457 #[test]
458 fn circle_builds_one_closed_loop() {
459 let (sketch, center) = point(Sketch::new(plane()), 0.0, 0.0);
460 let (sketch, disk) = circle(sketch, center, 5.0);
461 let Ok(profile) = build_profile(&sketch) else {
462 panic!("circle is a buildable profile");
463 };
464 let [
465 ProfileLoop::Closed {
466 curve_entity,
467 curve,
468 },
469 ] = profile.loops()
470 else {
471 panic!("a circle is one closed loop");
472 };
473 assert_eq!(*curve_entity, disk);
474 assert!(matches!(curve, Curve2Kind::Circle(_)));
475 let Ok(solid) = extrude(&sketch) else {
476 panic!("circle extrudes");
477 };
478 assert!(solid.validate(TOL).is_ok());
479 }
480
481 #[test]
482 fn arc_and_chord_assemble_into_a_half_disk() {
483 let (sketch, center) = point(Sketch::new(plane()), 0.0, 0.0);
484 let (sketch, start) = point(sketch, -5.0, 0.0);
485 let (sketch, end) = point(sketch, 5.0, 0.0);
486 let (sketch, arc_id) = arc(sketch, center, start, end);
487 let (sketch, _) = line(sketch, end, start, false);
488
489 let Ok(profile) = build_profile(&sketch) else {
490 panic!("arc plus chord is buildable");
491 };
492 let [ProfileLoop::Open(edges)] = profile.loops() else {
493 panic!("half disk is one open loop");
494 };
495 assert_eq!(edges.len(), 2);
496 let Some(Curve2Kind::Arc(forward)) = edges
497 .iter()
498 .find(|edge| edge.curve_entity() == arc_id)
499 .map(|edge| edge.curve())
500 else {
501 panic!("arc edge present in the loop");
502 };
503 assert!(
504 forward.sweep_rad() > 0.0 && (forward.sweep_rad() - core::f64::consts::PI).abs() < 1e-9,
505 "forward ordering sweeps ccw through the bottom semicircle"
506 );
507 let Ok(solid) = extrude(&sketch) else {
508 panic!("half disk extrudes");
509 };
510 assert!(solid.validate(TOL).is_ok());
511 }
512
513 #[test]
514 fn reversed_arc_assembles_like_the_forward_arc() {
515 let (sketch, center) = point(Sketch::new(plane()), 0.0, 0.0);
516 let (sketch, start) = point(sketch, -5.0, 0.0);
517 let (sketch, end) = point(sketch, 5.0, 0.0);
518 let (sketch, _) = line(sketch, start, end, false);
519 let (sketch, arc_id) = arc(sketch, center, start, end);
520
521 let Ok(profile) = build_profile(&sketch) else {
522 panic!("arc plus chord is buildable in either order");
523 };
524 let [ProfileLoop::Open(edges)] = profile.loops() else {
525 panic!("half disk is one open loop");
526 };
527 let Some(Curve2Kind::Arc(reversed)) = edges
528 .iter()
529 .find(|edge| edge.curve_entity() == arc_id)
530 .map(|edge| edge.curve())
531 else {
532 panic!("arc edge present in the loop");
533 };
534 assert!(
535 reversed.sweep_rad() < 0.0,
536 "chord-first ordering makes the walk traverse the arc backward"
537 );
538 let Ok(solid) = extrude(&sketch) else {
539 panic!("reversed-arc half disk extrudes");
540 };
541 assert!(solid.validate(TOL).is_ok());
542 }
543
544 #[test]
545 fn branching_vertex_is_distinct_from_open_loop() {
546 let (sketch, [p0, p1, p2, p3]) = corners(Sketch::new(plane()));
547 let (sketch, _) = line(sketch, p0, p1, false);
548 let (sketch, _) = line(sketch, p1, p2, false);
549 let (sketch, _) = line(sketch, p2, p3, false);
550 let (sketch, _) = line(sketch, p3, p0, false);
551 let (sketch, _) = line(sketch, p0, p2, false);
552 assert!(matches!(
553 build_profile(&sketch),
554 Err(BrepError::InvalidProfile {
555 reason: ProfileDefect::BranchingVertex
556 })
557 ));
558 }
559
560 #[test]
561 fn open_chain_is_rejected() {
562 let (sketch, [p0, p1, p2, p3]) = corners(Sketch::new(plane()));
563 let (sketch, _) = line(sketch, p0, p1, false);
564 let (sketch, _) = line(sketch, p1, p2, false);
565 let (sketch, _) = line(sketch, p2, p3, false);
566 assert!(matches!(
567 build_profile(&sketch),
568 Err(BrepError::InvalidProfile {
569 reason: ProfileDefect::OpenLoop
570 })
571 ));
572 }
573
574 #[test]
575 fn construction_geometry_is_excluded() {
576 let (sketch, [p0, p1, p2, p3]) = corners(Sketch::new(plane()));
577 let (sketch, _) = line(sketch, p0, p1, false);
578 let (sketch, _) = line(sketch, p1, p2, false);
579 let (sketch, _) = line(sketch, p2, p3, false);
580 let (sketch, _) = line(sketch, p3, p0, false);
581 let (sketch, diag_a) = point(sketch, 0.0, 0.0);
582 let (sketch, diag_b) = point(sketch, 10.0, 5.0);
583 let (sketch, _) = line(sketch, diag_a, diag_b, true);
584
585 let Ok(profile) = build_profile(&sketch) else {
586 panic!("construction line does not break the profile");
587 };
588 assert_eq!(profile.loops().len(), 1);
589 }
590
591 #[test]
592 fn nested_line_loops_extrude_to_a_tube() {
593 let (sketch, [o0, o1, o2, o3]) = corners(Sketch::new(plane()));
594 let (sketch, _) = line(sketch, o0, o1, false);
595 let (sketch, _) = line(sketch, o1, o2, false);
596 let (sketch, _) = line(sketch, o2, o3, false);
597 let (sketch, _) = line(sketch, o3, o0, false);
598 let (sketch, i0) = point(sketch, 3.0, 1.0);
599 let (sketch, i1) = point(sketch, 7.0, 1.0);
600 let (sketch, i2) = point(sketch, 7.0, 4.0);
601 let (sketch, i3) = point(sketch, 3.0, 4.0);
602 let (sketch, _) = line(sketch, i0, i1, false);
603 let (sketch, _) = line(sketch, i1, i2, false);
604 let (sketch, _) = line(sketch, i2, i3, false);
605 let (sketch, _) = line(sketch, i3, i0, false);
606
607 let Ok(profile) = build_profile(&sketch) else {
608 panic!("rectangle with a rectangular hole is buildable");
609 };
610 assert_eq!(profile.loops().len(), 2);
611 assert!(
612 profile
613 .loops()
614 .iter()
615 .all(|loop_| matches!(loop_, ProfileLoop::Open(edges) if edges.len() == 4))
616 );
617 let Ok(solid) = extrude(&sketch) else {
618 panic!("nested loops extrude to a tube");
619 };
620 assert!(solid.validate(TOL).is_ok());
621 assert_eq!(solid.iter_faces().count(), 10);
622 }
623}