Files
Brett Lawson b7efc29dbc Sweep along a path with corners: join the runs' pieces in a balanced union, roughly halving dense polyline sweeps (#14451) (#15097)
* Sweep: claim the product side of #14451 (dense polyline paths)

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_01SdcgEtwSrdwZxqTQp5MfnU

* Sweep along a path with corners: join the runs' pieces in a balanced union (#14451)

A sweep along a path with corners unioned each run's piece onto the body
built so far, so every union took in the growing body: along a densely
sampled polyline (181 points, 180 runs) that is 16,289 pieces' worth of
union operands, growing with the square of the points. The pieces are now
joined neighbours first in a balanced tree of the same union (1,380 for
180 runs). The solid is the same point set; each union is still
Brep::boolean with its tolerance growth.

Tests: a 33-point rail-along-polyline sweep counts the union operands
(160, against 527 joined one by one) and checks the analytic volume; a
unit test checks union_tree joins only neighbours.

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_01SdcgEtwSrdwZxqTQp5MfnU

* Sweep corner union: keep union_tree private to smlib_sweeps.rs, with its unit test in the file (#14451)

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_01SdcgEtwSrdwZxqTQp5MfnU

---------

Co-authored-by: Claude Opus 5.5 <noreply@anthropic.com>
2026-11-11 21:41:13 +00:00

220 lines
11 KiB
Rust
Raw Permalink Blame History

This file contains ambiguous Unicode characters
This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.
//! Guide rails on path sweeps (issue #771), checked against analytic solids: a rail that closes
//! in on the path scales a circle into a cone frustum, a stretching rail widens a square one way
//! only, a helical rail twists a square, a rail parallel to a curved path (an arc or a polyline)
//! keeps the section, two rails carry a line between them; and rails the sweep cannot follow are
//! refused.
#![allow(clippy::unwrap_used, clippy::expect_used, clippy::panic)]
use solidcraft_geom::prelude::*;
use std::f64::consts::PI;
use solidcore_record::{Loop2, Plane, Region2, Seg2, Vec2, Vec3};
use crate::{PathSeg, RailFit, SweepControl, measure, sweep_path_with, sweep_with};
fn circle(r: f64) -> Region2 {
Region2 { outer: Loop2::circle(Vec2::ZERO, r), holes: Vec::new() }
}
fn square(h: f64) -> Region2 {
Region2 { outer: Loop2::polygon(&[Vec2::new(-h, -h), Vec2::new(h, -h), Vec2::new(h, h), Vec2::new(-h, h)]), holes: Vec::new() }
}
/// The Z axis from 0 to 40.
fn up() -> Vec<Vec3> {
vec![Vec3::ZERO, Vec3::new(0.0, 0.0, 40.0)]
}
fn railed(rails: Vec<Vec<Vec3>>, fit: RailFit) -> SweepControl {
SweepControl { rails, rail_fit: fit, ..SweepControl::default() }
}
fn close(a: f64, b: f64, rel: f64) -> bool {
(a - b).abs() <= rel * b.abs()
}
/// A rail from the circle's edge at radius 10 in to radius 5 at the top scales the circle into
/// a frustum: volume πh(R² + Rr + r²)/3, lateral area π(R + r) times the slant height.
#[test]
fn a_rail_closing_in_scales_a_circle_into_a_frustum() {
let rail = vec![Vec3::new(10.0, 0.0, 0.0), Vec3::new(5.0, 0.0, 40.0)];
let b = sweep_path_with(&Plane::XY, &circle(10.0), &up(), &railed(vec![rail], RailFit::Scale)).unwrap();
let m = measure(&b).unwrap();
let volume = PI * 40.0 / 3.0 * (100.0 + 50.0 + 25.0);
let area = PI * 15.0 * (40.0f64 * 40.0 + 25.0).sqrt() + PI * 100.0 + PI * 25.0;
assert!(close(m.volume, volume, 2e-3), "volume {} vs {volume}", m.volume);
assert!(close(m.area, area, 2e-3), "area {} vs {area}", m.area);
assert!(close(m.bbox.max.z, 40.0, 1e-9), "{:?}", m.bbox);
}
/// A stretching rail from x = 5 out to x = 10 doubles the square's width along X by the top and
/// leaves its depth along Y: sections 10 × 10k with k = 1 + z/40, volume 100 · 40 · 1.5.
#[test]
fn a_stretching_rail_widens_a_square_one_way() {
let rail = vec![Vec3::new(5.0, 0.0, 0.0), Vec3::new(10.0, 0.0, 40.0)];
let b = sweep_path_with(&Plane::XY, &square(5.0), &up(), &railed(vec![rail], RailFit::Stretch)).unwrap();
let m = measure(&b).unwrap();
assert!(close(m.volume, 6000.0, 1e-3), "volume {}", m.volume);
assert!((m.bbox.max.x - 10.0).abs() < 1e-3 && (m.bbox.min.x + 10.0).abs() < 1e-3, "{:?}", m.bbox);
assert!((m.bbox.max.y - 5.0).abs() < 1e-3 && (m.bbox.min.y + 5.0).abs() < 1e-3, "{:?}", m.bbox);
}
/// The same rail scaling evenly: the square grows both ways, sections 100k², volume
/// 100 ∫ (1 + z/40)² dz = 100 · 40 · 7/3.
#[test]
fn a_scaling_rail_grows_a_square_both_ways() {
let rail = vec![Vec3::new(5.0, 0.0, 0.0), Vec3::new(10.0, 0.0, 40.0)];
let b = sweep_path_with(&Plane::XY, &square(5.0), &up(), &railed(vec![rail], RailFit::Scale)).unwrap();
let m = measure(&b).unwrap();
let volume = 100.0 * 40.0 * 7.0 / 3.0;
assert!(close(m.volume, volume, 2e-3), "volume {} vs {volume}", m.volume);
assert!((m.bbox.max.y - 10.0).abs() < 1e-3, "{:?}", m.bbox);
}
/// A helical rail from the square's corner, a quarter turn about the path at the corner's
/// radius, twists the square a quarter turn: the volume stays 4000, halfway up the corners stand
/// on the axes (the box reaches 5√2), and at the top the corner is at (−5, 5).
#[test]
fn a_helical_rail_twists_a_square() {
let r = 50f64.sqrt();
let rail: Vec<Vec3> = (0..=200)
.map(|i| {
let u = i as f64 / 200.0;
let a = PI / 4.0 + u * PI / 2.0;
Vec3::new(r * a.cos(), r * a.sin(), 40.0 * u)
})
.collect();
let b = sweep_path_with(&Plane::XY, &square(5.0), &up(), &railed(vec![rail], RailFit::Scale)).unwrap();
let m = measure(&b).unwrap();
assert!(close(m.volume, 4000.0, 2e-3), "volume {}", m.volume);
assert!((m.bbox.max.x - r).abs() < 0.05 && (m.bbox.max.y - r).abs() < 0.05, "{:?}", m.bbox);
// The edge running up from the corner (5, 5) ends a quarter turn on, at (−5, 5).
let edges = b.edges(0.01).unwrap();
let ends = |e: &crate::EdgeInfo| (e.points.first().copied().unwrap(), e.points.last().copied().unwrap());
let joins = |p: Vec3, q: Vec3| {
edges.iter().any(|e| {
let (a, b) = ends(e);
(a.dist(p) < 1e-3 && b.dist(q) < 1e-3) || (a.dist(q) < 1e-3 && b.dist(p) < 1e-3)
})
};
assert!(joins(Vec3::new(5.0, 5.0, 0.0), Vec3::new(-5.0, 5.0, 40.0)), "{:?}", edges.iter().map(ends).collect::<Vec<_>>());
assert!(!joins(Vec3::new(5.0, 5.0, 0.0), Vec3::new(5.0, 5.0, 40.0)));
}
/// Along a quarter circle of radius 30 (one arc segment), a rail keeping 5 mm out from the path
/// (the circle's outer point, on a quarter circle of radius 35) leaves the circle as it is: a
/// quarter torus, volume πr² · R · π/2 (Pappus).
#[test]
fn a_parallel_rail_along_a_curved_path_keeps_the_section() {
let path = [PathSeg::Arc { a: Vec3::ZERO, center: Vec3::new(30.0, 0.0, 0.0), axis: Vec3::new(0.0, 1.0, 0.0), angle: PI / 2.0 }];
let rail: Vec<Vec3> = (0..=180)
.map(|i| {
let a = PI / 2.0 * i as f64 / 180.0;
Vec3::new(30.0 - 35.0 * a.cos(), 0.0, 35.0 * a.sin())
})
.collect();
let b = sweep_with(&Plane::XY, &circle(5.0), &path, &railed(vec![rail], RailFit::Scale)).unwrap();
let m = measure(&b).unwrap();
let volume = PI * 25.0 * 30.0 * PI / 2.0;
assert!(close(m.volume, volume, 1e-6), "volume {} vs {volume}", m.volume);
}
/// The same quarter circles as 9-point polylines: the path mitres its 7 corners and the rail
/// turns with it. The profile drawn square to the start meets the first chord tilted by half a
/// step d/2, and each run carries that section as it is, so the runs are oblique cylinders whose
/// sections parallel to the profile are the r5 circle (the rail stays 5 mm out in those planes):
/// volume πr² · L · cos(d/2) over the polyline's length L.
#[test]
fn a_parallel_rail_along_a_polyline_turns_with_its_corners() {
let n = 8;
let arc = |radius: f64| -> Vec<Vec3> {
(0..=n)
.map(|i| {
let a = PI / 2.0 * f64::from(i) / f64::from(n);
Vec3::new(30.0 - radius * a.cos(), 0.0, radius * a.sin())
})
.collect()
};
let b = sweep_path_with(&Plane::XY, &circle(5.0), &arc(30.0), &railed(vec![arc(35.0)], RailFit::Scale)).unwrap();
let m = measure(&b).unwrap();
let d = PI / 2.0 / f64::from(n);
let length = f64::from(n) * 60.0 * (d / 2.0).sin();
let volume = PI * 25.0 * length * (d / 2.0).cos();
assert!(close(m.volume, volume, 1e-6), "volume {} vs {volume}", m.volume);
}
/// A densely sampled polyline (#14451): 33 points, 32 runs, 31 mitres. The runs' pieces are
/// unioned in a balanced tree, so each takes part in at most ⌈log2 32⌉ = 5 unions (160 pieces'
/// worth of union operands in all, where unioning each onto the body so far takes in
/// 2 + 3 + … + 32 = 527 and grows with the square of the points), and the solid is the same
/// oblique cylinders: volume πr² · L · cos(d/2).
#[test]
fn a_rail_along_a_dense_polyline_joins_its_runs_in_a_balanced_union() {
let n = 32;
let arc = |radius: f64| -> Vec<Vec3> {
(0..=n)
.map(|i| {
let a = PI / 2.0 * f64::from(i) / f64::from(n);
Vec3::new(30.0 - radius * a.cos(), 0.0, radius * a.sin())
})
.collect()
};
crate::smlib_sweeps::UNION_LOAD.with(|l| l.set(0));
let b = sweep_path_with(&Plane::XY, &circle(5.0), &arc(30.0), &railed(vec![arc(35.0)], RailFit::Scale)).unwrap();
let load = crate::smlib_sweeps::UNION_LOAD.with(std::cell::Cell::get);
assert_eq!(load, 32 * 5, "union operands, in runs' pieces");
let m = measure(&b).unwrap();
let d = PI / 2.0 / f64::from(n);
let length = f64::from(n) * 60.0 * (d / 2.0).sin();
let volume = PI * 25.0 * length * (d / 2.0).cos();
assert!(close(m.volume, volume, 1e-6), "volume {} vs {volume}", m.volume);
}
/// Two rails bulging apart along arcs (radius 25 about (∓5, 0, 20), through x = ±10 at z = 0
/// and z = 40) carry a line between them: the sheet lies in the XZ plane between the arcs, area
/// 2(a√(R² − a²) + R² asin(a/R)) − 400 with a = 20.
#[test]
fn two_rails_carry_a_line_between_arcs() {
let arc = |side: f64| -> Vec<Vec3> {
(0..=400)
.map(|i| {
let z = 40.0 * i as f64 / 400.0;
let x = -5.0 + (625.0 - (z - 20.0) * (z - 20.0)).sqrt();
Vec3::new(side * x, 0.0, z)
})
.collect()
};
let line = vec![vec![Seg2::Line { a: Vec2::new(-10.0, 0.0), b: Vec2::new(10.0, 0.0) }]];
for fit in [RailFit::Scale, RailFit::Stretch] {
let ctl = railed(vec![arc(-1.0), arc(1.0)], fit);
let b = crate::sweep_sheet_points_with(&Plane::XY, &line, &up(), &ctl).unwrap();
let m = measure(&b).unwrap();
let area = 2.0 * (20.0 * 15.0 + 625.0 * (0.8f64).asin()) - 400.0;
assert!(close(m.area, area, 1e-3), "{fit:?}: area {} vs {area}", m.area);
assert!(m.bbox.min.y.abs() < 1e-6 && m.bbox.max.y.abs() < 1e-6, "{fit:?}: {:?}", m.bbox);
}
}
/// Rails the sweep cannot follow are refused with a reason, never a panic: three rails, a rail
/// with a bad point, a rail with a twist or scale besides, a rail starting on the path, a rail
/// that stops short, a straight rail along a path with a corner (a rail must turn with the path
/// at its corners).
#[test]
fn rails_the_sweep_cannot_follow_are_refused() {
let rail = vec![Vec3::new(10.0, 0.0, 0.0), Vec3::new(5.0, 0.0, 40.0)];
let refuse = |ctl: SweepControl, path: &[Vec3], why: &str| {
let e = sweep_path_with(&Plane::XY, &circle(10.0), path, &ctl).map(|_| ()).unwrap_err().to_string();
assert!(e.contains(why), "expected `{why}` in `{e}`");
};
refuse(railed(vec![rail.clone(); 3], RailFit::Scale), &up(), "one or two guide rails");
refuse(railed(vec![vec![Vec3::ZERO, Vec3::new(f64::NAN, 0.0, 1.0)]], RailFit::Scale), &up(), "finite points");
refuse(SweepControl { twist: 1.0, ..railed(vec![rail.clone()], RailFit::Scale) }, &up(), "leave the orientation");
refuse(SweepControl { scale: 2.0, ..railed(vec![rail.clone()], RailFit::Scale) }, &up(), "leave the orientation");
refuse(railed(vec![vec![Vec3::ZERO, Vec3::new(5.0, 0.0, 40.0)]], RailFit::Scale), &up(), "starts on the path");
refuse(railed(vec![vec![Vec3::new(10.0, 0.0, 0.0), Vec3::new(8.0, 0.0, 20.0)]], RailFit::Scale), &up(), "whole length");
refuse(railed(vec![rail.clone(), rail.clone()], RailFit::Scale), &up(), "start at the same point");
let bent = vec![Vec3::ZERO, Vec3::new(0.0, 0.0, 20.0), Vec3::new(20.0, 0.0, 20.0)];
refuse(railed(vec![vec![Vec3::new(10.0, 0.0, 0.0), Vec3::new(10.0, 0.0, 30.0)]], RailFit::Scale), &bent, "the guide rails have to turn with it");
}