SolidCraft: an open-source parametric 3D CAD application built in pure Rust. Desktop, web, and automation through MCP.
//! Exact orthographic hidden lines for placed portable B-rep bodies (Drawing W06a, #2455;
//! plan #860). Edges and face silhouettes are projected from their exact curves, split where
//! their projections cross, and each piece is classified by rays toward the viewer against the
//! trimmed faces. Every piece is visible, hidden or explicitly uncertain; nothing is guessed.
//!
//! Supported: planes, and cylinders, cones, spheres and tori whether stored as analytic records,
//! rigidly placed revolutions of lines and circles or spline patches (recognised to 1e-9 relative
//! and then trimmed and intersected in their own chart). Other spline and rigidly placed revolution
//! faces are freeform:
//! unless [`Options::freeform`] is set they are listed in [`Drawing::unsupported`], their
//! silhouettes are not drawn and anything they could hide is reported uncertain.
//!
//! Work is done in a frame centred on the scene, so results do not drift for parts far from the
//! origin. Output curves are `Seg2` pieces in screen millimetres with the accuracy vocabulary of
//! [`crate::section`]. See `docs/drawing-hlr.md` for the contract and its measured limits.
pub(crate) mod curve;
mod silhouette;
pub(crate) mod surface;
mod trim;
use crate::prelude::*;
use serde::Serialize;
use crate::section::CurveAccuracy;
use curve::{C3, as_circle};
use solidcore_record::brep::Brep;
use solidcore_record::{Seg2, Vec2, Vec3};
use surface::{Analytic, Hit, S3};
use trim::Trim;
#[derive(Debug, thiserror::Error)]
pub enum HlrError {
#[error("not supported yet: {0}")]
Unsupported(&'static str),
#[error("hidden lines: {0} budget exceeded")]
Budget(&'static str),
#[error("hidden lines: cancelled")]
Cancelled,
#[error("hidden lines: invalid {0}")]
Invalid(&'static str),
}
/// An orthographic view: `d` is the direction of sight; screen coordinates are `(p.x, p.y)`.
#[derive(Clone, Copy, Debug)]
pub struct View {
pub x: Vec3,
pub y: Vec3,
pub d: Vec3,
}
impl View {
pub fn new(d: Vec3, up: Vec3) -> Result<View, HlrError> {
let d = d.normalized().ok_or(HlrError::Invalid("view direction"))?;
let x = d.cross(up).normalized().ok_or(HlrError::Invalid("view up direction"))?;
Ok(View { x, y: x.cross(d), d })
}
pub fn screen(&self, p: Vec3) -> [f64; 2] {
[p.dot(self.x), p.dot(self.y)]
}
}
/// One placed body: `world = rotation * local + translation`, rotation columns given.
#[derive(Clone, Copy, Debug)]
pub struct Placement {
pub body: usize,
pub rotation: [Vec3; 3],
pub translation: Vec3,
}
impl Placement {
fn apply(&self, p: Vec3) -> Vec3 {
let [a, b, c] = self.rotation;
a * p.x + b * p.y + c * p.z + self.translation
}
fn local_dir(&self, v: Vec3) -> Vec3 {
let [a, b, c] = self.rotation;
Vec3::new(a.dot(v), b.dot(v), c.dot(v))
}
fn local(&self, p: Vec3) -> Vec3 {
self.local_dir(p - self.translation)
}
fn rigid(&self) -> bool {
let [a, b, c] = self.rotation;
[a, b, c].iter().all(|v| v.is_finite() && (v.len() - 1.).abs() < 1e-9)
&& a.dot(b).abs() < 1e-9
&& a.dot(c).abs() < 1e-9
&& b.dot(c).abs() < 1e-9
&& (a.cross(b).dot(c) - 1.).abs() < 1e-9
&& self.translation.is_finite()
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize)]
#[serde(rename_all = "snake_case")]
pub enum EdgeKind {
Sharp,
/// Between two faces that meet tangentially (or lie on one surface).
Tangent,
/// Used twice by one face, or between two faces of one analytic surface (a patch boundary).
Seam,
}
struct EdgeData {
curve: C3,
acc: CurveAccuracy,
faces: Vec<usize>,
kind: EdgeKind,
}
struct FaceData {
surface: S3,
analytic: Analytic,
/// Faces of this body on the same quadric or torus (patches of one surface), itself included.
group: Vec<usize>,
trim: Trim,
lo: Vec3,
hi: Vec3,
/// Neither a plane nor a recognised quadric or torus.
freeform: bool,
}
/// A body prepared once and shared by all of its placements.
pub struct Prepared {
edges: Vec<EdgeData>,
faces: Vec<FaceData>,
/// The body's records are kept moved by `-offset` (to its own centre), so its coordinates
/// stay small wherever it was modelled; placements add it back.
offset: Vec3,
lo: Vec3,
hi: Vec3,
pub report: PrepareReport,
}
#[derive(Clone, Debug, Default, Serialize)]
pub struct PrepareReport {
pub faces: usize,
pub edges: usize,
/// Face counts by recognised surface: plane, cylinder, cone, sphere, torus, other.
pub surfaces: std::collections::BTreeMap<String, usize>,
/// Edge counts by record kind and recognition, e.g. `rational_spline/circle`.
pub curves: std::collections::BTreeMap<String, usize>,
pub tangent_edges: usize,
pub seam_edges: usize,
/// Faces whose trim could not be classified, with the reason.
pub unsupported_trims: Vec<(usize, String)>,
/// Largest distance between a boundary curve and the chords used for trimming (mm).
pub max_trim_chord: f64,
/// Faces outside the supported subset (see [`Options::freeform`]).
pub freeform_faces: Vec<usize>,
}
/// Whether two recognised surfaces are the same quadric or torus (planes never: coplanar
/// faces of a split are real edges in the record, and are drawn).
fn same_analytic(a: &Analytic, b: &Analytic, tol: f64) -> bool {
let close = |x: Vec3, y: Vec3, scale: f64| x.dist(y) <= tol * (1. + scale);
let on_axis = |p: Vec3, q: Vec3, a: Vec3, scale: f64| (q - p).cross(a).len() <= tol * (1. + scale);
match (a, b) {
(Analytic::Cylinder { p, a, r }, Analytic::Cylinder { p: q, a: b, r: s }) => {
(r - s).abs() <= tol * r && a.cross(*b).len() <= tol && on_axis(*p, *q, *a, *r)
}
(Analytic::Cone { apex, a, half }, Analytic::Cone { apex: b_apex, a: b, half: h }) => {
// The axes by their angle, as for cylinders and tori (a dot product would compare
// its square).
(half - h).abs() <= tol && a.cross(*b).len() <= tol && a.dot(*b) > 0. && close(*apex, *b_apex, apex.len())
}
(Analytic::Sphere { c, r }, Analytic::Sphere { c: d, r: s }) => (r - s).abs() <= tol * r && close(*c, *d, *r),
(Analytic::Torus { c, a, major, minor }, Analytic::Torus { c: d, a: b, major: m, minor: n }) => {
(major - m).abs() <= tol * major && (minor - n).abs() <= tol * major && a.cross(*b).len() <= tol && close(*c, *d, *major)
}
_ => false,
}
}
fn analytic_name(a: &Analytic) -> &'static str {
match a {
Analytic::Plane => "plane",
Analytic::Cylinder { .. } => "cylinder",
Analytic::Cone { .. } => "cone",
Analytic::Sphere { .. } => "sphere",
Analytic::Torus { .. } => "torus",
Analytic::Other => "other",
}
}
pub fn prepare(b: &Brep, opts: &Options) -> Result<Prepared, HlrError> {
prepare_cancellable(b, opts, &|| false)
}
/// [`prepare`], polling `cancel` between edges, faces and surface comparisons; when it returns
/// true the call ends with `HlrError::Cancelled`.
pub fn prepare_cancellable(b: &Brep, opts: &Options, cancel: &dyn Fn() -> bool) -> Result<Prepared, HlrError> {
if !(1..=MAX_TRIM_SAMPLES).contains(&opts.trim_samples) {
return Err(HlrError::Invalid("trim samples"));
}
crate::brep::check::validate(b).map_err(|_| HlrError::Invalid("portable B-rep"))?;
// Work on the body moved to its own centre: rounding in ray and inversion formulas grows
// with the coordinates, and a part may be modelled far from the origin (W05a finding 7).
let offset = anchor(b);
let moved = shifted(b, offset);
let b = &moved;
let mut edges = Vec::new();
let mut faces = Vec::new();
let mut report = PrepareReport::default();
let mut curves = Vec::with_capacity(b.edges.len());
for (ei, e) in b.edges.iter().enumerate() {
if ei % 256 == 0 && cancel() {
return Err(HlrError::Cancelled);
}
let (c, acc) = C3::of_edge(e)?;
let record = match &e.curve {
solidcore_record::brep::Curve::Line { .. } => "line",
solidcore_record::brep::Curve::Circle { .. } => "circle_arc",
solidcore_record::brep::Curve::Ellipse { .. } => "ellipse_arc",
solidcore_record::brep::Curve::Polyline { .. } => "polyline",
solidcore_record::brep::Curve::Spline { .. } => "spline",
solidcore_record::brep::Curve::RationalSpline { .. } => "rational_spline",
// Only one with a spline to follow gets here: what was an `intersection` record.
solidcore_record::brep::Curve::SurfaceIntersection { .. } => "intersection",
};
let shape = if matches!(c, C3::Line { .. }) {
"line"
} else if as_circle(&c, 1e-9).is_some() {
"circle"
} else {
"other"
};
*report.curves.entry(format!("{record}/{shape}")).or_insert(0) += 1;
curves.push((c, acc));
}
let local_curves: Vec<C3> = curves.iter().map(|(c, _)| c.clone()).collect();
let mut users: Vec<Vec<usize>> = vec![Vec::new(); b.edges.len()];
// Faces and edges by their numbers in the record. Validation puts every face in a shell; its
// loops are stored the same whichever side a shell uses, and hidden lines look at both, so the
// shells' orientation does not come into it (a face two shells share is one face). An edge no
// face uses (a wire) is drawn like any other.
for (fi, f) in b.faces.iter().enumerate() {
if cancel() {
return Err(HlrError::Cancelled);
}
let mut surface = S3::of_face(f)?;
// A flat spline patch is a plane: trimmed and intersected as one.
if let Some(plane) = surface.flat(1e-9) {
surface = plane;
}
let analytic = surface.analytic(1e-9);
// Trim and intersect recognised spline surfaces in their own analytic chart.
if matches!(surface, S3::Nurbs(_)) {
let axis = match analytic {
Analytic::Cylinder { p, a, .. } => Some((p, a)),
Analytic::Cone { apex, a, .. } => Some((apex, a)),
_ => None,
};
let mut h = [0., 0.];
if let Some((p, a)) = axis {
let along = trim::uses(f).filter_map(|u| local_curves.get(u.edge as usize)).flat_map(|c| {
let [t0, t1] = c.domain();
(0..=64).map(move |i| c.at(t0 + (t1 - t0) * i as f64 / 64.))
});
let (lo, hi) = along.fold((f64::MAX, f64::MIN), |(lo, hi), q| ((q - p).dot(a).min(lo), (q - p).dot(a).max(hi)));
// Generous: the chart only has to contain the face; the trim bounds it exactly.
let pad = 0.01 * (hi - lo).abs() + 1e-6;
h = [lo - pad, hi + pad];
}
let toward = match analytic {
Analytic::Sphere { c, .. } => {
let pts: Vec<Vec3> = trim::uses(f)
.filter_map(|u| local_curves.get(u.edge as usize))
.map(|c| c.at(0.5 * (c.domain()[0] + c.domain()[1])))
.collect();
let n = pts.len().max(1) as f64;
pts.iter().fold(Vec3::ZERO, |acc, p| acc + *p) / n - c
}
_ => Vec3::ZERO,
};
if let Some(chart) = S3::from_analytic(&analytic, h, toward) {
surface = chart;
}
}
*report.surfaces.entry(analytic_name(&analytic).to_string()).or_insert(0) += 1;
let trim = trim::build(f, &local_curves, &surface, opts.trim_samples);
if let Some(why) = trim.unsupported {
report.unsupported_trims.push((fi, why.to_string()));
}
report.max_trim_chord = report.max_trim_chord.max(trim.chord_error);
let (mut lo, mut hi) = (trim.lo, trim.hi);
// Curved faces can bulge past their boundary: bound them by the whole surface's
// guaranteed box (spline hull, turned profile), clipped to nothing tighter.
if !matches!(surface, S3::Plane { .. })
&& let Some((blo, bhi)) = surface.bound()
{
lo = lo.min(blo);
hi = hi.max(bhi);
}
// Every face is padded, planes too: a plane record and its edges may disagree by
// rounding, and a box flat along the normal would cull the plane's own hit. Rounding
// grows with where the body was modelled (its offset), not with the face's size.
let pad = (hi - lo).len() * 1e-6 + 1e-12 * offset.x.abs().max(offset.y.abs()).max(offset.z.abs());
lo -= Vec3::new(pad, pad, pad);
hi += Vec3::new(pad, pad, pad);
for u in trim::uses(f) {
if let Some(list) = users.get_mut(u.edge as usize) {
list.push(fi);
}
}
let freeform = matches!(analytic, Analytic::Other);
if freeform {
report.freeform_faces.push(fi);
}
faces.push(FaceData { surface, analytic, group: Vec::new(), trim, lo, hi, freeform });
}
for (ei, (c, acc)) in curves.into_iter().enumerate() {
let list = users.get(ei).cloned().unwrap_or_default();
let mut distinct = list.clone();
distinct.sort_unstable();
distinct.dedup();
let kind = if list.len() >= 2 && distinct.len() == 1 {
EdgeKind::Seam
} else if let [f1, f2] = distinct.as_slice() {
let [t0, t1] = c.domain();
let normals_parallel = [0.25, 0.5, 0.75].iter().all(|k| {
let m = c.at(t0 + (t1 - t0) * k);
let n = |f: usize| faces.get(f).and_then(|fd: &FaceData| fd.surface.inverse(m, None).and_then(|uv| fd.surface.normal(uv)));
n(*f1).zip(n(*f2)).is_some_and(|(a, b)| a.cross(b).len() < 1e-6)
});
let same_surface = match (faces.get(*f1).map(|f: &FaceData| f.analytic), faces.get(*f2).map(|f: &FaceData| f.analytic)) {
(Some(a), Some(b)) => same_analytic(&a, &b, 1e-9),
_ => false,
};
if same_surface {
EdgeKind::Seam
} else if normals_parallel {
EdgeKind::Tangent
} else {
EdgeKind::Sharp
}
} else {
EdgeKind::Sharp
};
match kind {
EdgeKind::Tangent => report.tangent_edges += 1,
EdgeKind::Seam => report.seam_edges += 1,
EdgeKind::Sharp => {}
}
edges.push(EdgeData { curve: c, acc, faces: list, kind });
}
// Faces on one quadric or torus. Only surfaces of one kind whose size (radius, half angle,
// major radius) agrees to the tolerance can match, so each face is compared with the faces
// in its window of the sorted sizes, not with every face.
let size = |a: &Analytic| match a {
Analytic::Cylinder { r, .. } => Some((0u8, *r)),
Analytic::Cone { half, .. } => Some((1, *half)),
Analytic::Sphere { r, .. } => Some((2, *r)),
Analytic::Torus { major, .. } => Some((3, *major)),
Analytic::Plane | Analytic::Other => None,
};
let analytics: Vec<Analytic> = faces.iter().map(|f| f.analytic).collect();
let mut sorted: Vec<(u8, f64, usize)> = analytics.iter().enumerate().filter_map(|(j, a)| size(a).map(|(k, v)| (k, v, j))).collect();
sorted.sort_by(|a, b| a.0.cmp(&b.0).then(a.1.total_cmp(&b.1)));
let mut compared = 0usize;
for (i, f) in faces.iter_mut().enumerate() {
if i % 256 == 0 && cancel() {
return Err(HlrError::Cancelled);
}
let mut group = vec![i];
if let Some((kind, v)) = size(&f.analytic) {
// Wider than any match allows: same_analytic takes sizes within 1e-9 of the size
// (relative for lengths, absolute for the half angle).
let reach = 2e-9 * v.abs().max(1.);
let first = sorted.partition_point(|c| c.0 < kind || (c.0 == kind && c.1 < v - reach));
for (_, _, j) in sorted.get(first..).unwrap_or_default().iter().take_while(|c| c.0 == kind && c.1 <= v + reach) {
compared += 1;
if compared > 50_000_000 {
return Err(HlrError::Budget("surface group"));
}
if compared.is_multiple_of(65536) && cancel() {
return Err(HlrError::Cancelled);
}
if *j != i && analytics.get(*j).is_some_and(|b| same_analytic(&f.analytic, b, 1e-9)) {
group.push(*j);
}
}
}
group.sort_unstable();
f.group = group;
}
report.faces = faces.len();
report.edges = edges.len();
let (lo, hi) =
faces.iter().fold((Vec3::new(f64::MAX, f64::MAX, f64::MAX), Vec3::new(f64::MIN, f64::MIN, f64::MIN)), |(a, b), f| (a.min(f.lo), b.max(f.hi)));
if faces.is_empty() || !lo.is_finite() || !hi.is_finite() {
return Err(HlrError::Invalid("empty or unbounded body"));
}
Ok(Prepared { edges, faces, offset, lo, hi, report })
}
/// The centre of the body's vertices' box (a validated body has vertices: every face has an edge
/// loop, every other shell an edge or a vertex).
fn anchor(b: &Brep) -> Vec3 {
let mut pts = b.vertices.iter().map(|v| Vec3::new(v.point[0], v.point[1], v.point[2]));
let Some(first) = pts.next() else { return Vec3::ZERO };
let (lo, hi) = pts.fold((first, first), |(lo, hi), p| (lo.min(p), hi.max(p)));
let c = (lo + hi) * 0.5;
if c.is_finite() { c } else { Vec3::ZERO }
}
/// The body's records with every position moved by `-d`: points, control points and NURBS forms,
/// a placed revolution through its matrix; regions, parameters and pcurves as they are.
fn shifted(b: &Brep, d: Vec3) -> Brep {
crate::brep::placement::moved(
b,
&crate::brep::placement::Rigid { rotation: [[1., 0., 0.], [0., 1., 0.], [0., 0., 1.]], translation: [-d.x, -d.y, -d.z] },
)
}
#[derive(Clone, Copy, Debug)]
pub struct Options {
/// Draw edges between tangent faces (seams are never drawn).
pub tangent_edges: bool,
/// Also handle freeform faces: contoured silhouettes and seeded ray tests, slow and
/// ill-conditioned where a face is seen nearly edge-on (W05a finding 6). Off by default.
pub freeform: bool,
/// Boundary samples per curve piece when trimming faces, 1 to [`MAX_TRIM_SAMPLES`].
pub trim_samples: usize,
pub max_tracks: usize,
pub max_rays: usize,
}
impl Default for Options {
fn default() -> Self {
Options { tangent_edges: true, freeform: false, trim_samples: 256, max_tracks: 200_000, max_rays: 20_000_000 }
}
}
/// Largest [`Options::trim_samples`].
pub const MAX_TRIM_SAMPLES: usize = 4096;
/// Largest coordinate of a placed body in the scene, in millimetres: the bound `geom::section`
/// and `geom::brep` put on stored numbers. Beyond it the scene's size, and every tolerance
/// taken from it, would lose its meaning or overflow.
pub const MAX_COORDINATE: f64 = 1e12;
#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize)]
#[serde(rename_all = "snake_case")]
pub enum Visibility {
Visible,
Hidden,
Uncertain,
}
#[derive(Clone, Copy, Debug, PartialEq, Serialize)]
#[serde(tag = "kind", rename_all = "snake_case")]
pub enum Source {
Edge {
edge: usize,
tangent: bool,
},
/// The silhouette of the faces on one surface; `face` is the first of them.
Silhouette {
face: usize,
},
}
#[derive(Clone, Debug, Serialize)]
pub struct Piece {
/// Parameter range on the source curve.
pub t: [f64; 2],
pub visibility: Visibility,
/// Drawn by another piece: a hidden or uncertain piece lying on a visible one (hidden lines
/// never show through visible ones), or a duplicate of a visible or hidden piece.
pub covered: bool,
/// The piece on screen (millimetres): lines and conic arcs where the projection is exact,
/// chords otherwise.
pub geometry: Vec<Seg2>,
pub accuracy: CurveAccuracy,
/// Exact points along the piece, joined by `geometry`'s chords where it is sampled.
#[serde(skip)]
points: Vec<[f64; 2]>,
/// Largest distance between the projected curve and the chords joining `points`.
#[serde(skip)]
sag: f64,
}
#[derive(Clone, Debug, Serialize)]
pub struct Line {
/// Index into the scene's placements.
pub placement: usize,
pub source: Source,
pub pieces: Vec<Piece>,
}
/// A face left out of the supported subset, and why.
#[derive(Clone, Debug, PartialEq, Serialize)]
pub struct Unsupported {
pub placement: usize,
pub face: usize,
pub reason: &'static str,
}
#[derive(Clone, Debug, Default, Serialize)]
pub struct Stats {
pub tracks: usize,
pub silhouettes: usize,
pub crossings: usize,
pub pieces: usize,
pub uncertain_pieces: usize,
/// Uncertain pieces not covered by a coincident visible piece.
pub uncertain_uncovered: usize,
pub covered_pieces: usize,
/// Visibility changes found inside a piece by sampling, i.e. not at a computed crossing.
pub unexpected_transitions: usize,
pub rays: usize,
pub surface_ray_tests: usize,
/// Milliseconds per phase: curves and silhouettes, crossings, classification, coverage.
/// Zero where the platform has no clock (`wasm32-unknown-unknown`).
pub phase_ms: [f64; 4],
}
#[derive(Clone, Debug, Default, Serialize)]
pub struct Drawing {
pub lines: Vec<Line>,
/// Faces outside the supported subset: their silhouettes are missing and what they could
/// hide is uncertain.
pub unsupported: Vec<Unsupported>,
pub stats: Stats,
}
enum TrackCurve<'a> {
Edge(&'a C3),
Owned(C3),
}
struct Track<'a> {
placement: usize,
curve: TrackCurve<'a>,
range: [f64; 2],
source: Source,
acc: CurveAccuracy,
own: Vec<usize>,
/// Own-face hits closer than this are the curve's own surface: a sampled silhouette's
/// chord lies up to its deviation inside the surface, and a ray tangent there leaves it
/// again after about sqrt(2 * radius * deviation).
own_eps: f64,
samples: Vec<(f64, [f64; 2])>,
/// Per sample chord: the distance of the exact projected curve from it at its middle.
sags: Vec<f64>,
splits: Vec<f64>,
}
impl Track<'_> {
fn c3(&self) -> &C3 {
match &self.curve {
TrackCurve::Edge(c) => c,
TrackCurve::Owned(c) => c,
}
}
}
struct Ctx<'a> {
defs: &'a [Prepared],
scene: &'a [Placement],
view: View,
eps_own: f64,
eps_other: f64,
scale: f64,
/// World boxes of placements, screen min/max and depth min.
boxes: Vec<([f64; 2], [f64; 2], f64)>,
rays: std::cell::Cell<usize>,
surface_tests: std::cell::Cell<usize>,
transitions: std::cell::Cell<usize>,
max_rays: usize,
freeform: bool,
cancel: &'a dyn Fn() -> bool,
}
fn context<'a>(defs: &'a [Prepared], scene: &'a [Placement], view: &View, opts: &Options, cancel: &'a dyn Fn() -> bool) -> Result<Ctx<'a>, HlrError> {
let mut boxes = Vec::with_capacity(scene.len());
let (mut wlo, mut whi) = (Vec3::new(f64::MAX, f64::MAX, f64::MAX), Vec3::new(f64::MIN, f64::MIN, f64::MIN));
for p in scene {
if !p.rigid() {
return Err(HlrError::Invalid("placement (not a rotation and translation)"));
}
let def = defs.get(p.body).ok_or(HlrError::Invalid("placement body index"))?;
let (mut slo, mut shi, mut dmin) = ([f64::MAX; 2], [f64::MIN; 2], f64::MAX);
for k in 0..8 {
let c = Vec3::new(
if k & 1 == 0 { def.lo.x } else { def.hi.x },
if k & 2 == 0 { def.lo.y } else { def.hi.y },
if k & 4 == 0 { def.lo.z } else { def.hi.z },
);
let w = p.apply(c);
wlo = wlo.min(w);
whi = whi.max(w);
let s = view.screen(w);
slo = [slo[0].min(s[0]), slo[1].min(s[1])];
shi = [shi[0].max(s[0]), shi[1].max(s[1])];
dmin = dmin.min(w.dot(view.d));
}
boxes.push((slo, shi, dmin));
}
let scale = if scene.is_empty() { 1. } else { (whi - wlo).len().max(1e-6) };
Ok(Ctx {
defs,
scene,
view: *view,
eps_own: 1e-6 * scale,
// Hits on other bodies closer than rounding are ignored, the rest up to eps_own are
// uncertain: the work is done in a frame at the scene's centre, so rounding is about
// 1e-16 of the coordinates, far below 1e-12 of the scene.
eps_other: 1e-12 * scale,
scale,
boxes,
rays: std::cell::Cell::new(0),
surface_tests: std::cell::Cell::new(0),
transitions: std::cell::Cell::new(0),
max_rays: opts.max_rays,
freeform: opts.freeform,
cancel,
})
}
pub fn hidden_lines(defs: &[Prepared], scene: &[Placement], view: &View, opts: &Options, cancel: &dyn Fn() -> bool) -> Result<Drawing, HlrError> {
// Work in a frame centred on the scene: coordinates stay small, so rounding does not grow
// with the distance from the origin (W05a finding 7). Results are shifted back at the end.
let origin = scene_centre(defs, scene)?;
// Each body's own offset (see `Prepared`) joins its placement here.
let local: Vec<Placement> =
scene.iter().map(|p| Placement { translation: p.apply(defs.get(p.body).map_or(Vec3::ZERO, |d| d.offset)) - origin, ..*p }).collect();
let scene = local.as_slice();
let shift = view.screen(origin);
let ctx = context(defs, scene, view, opts, cancel)?;
let scale = ctx.scale;
let mut stats = Stats::default();
let mut unsupported = Vec::new();
let clock = Clock::start();
// 1. Tracks: drawable edges and trimmed silhouettes of every placement.
let mut tracks: Vec<Track> = Vec::new();
for (pi, p) in scene.iter().enumerate() {
if cancel() {
return Err(HlrError::Cancelled);
}
let Some(def) = defs.get(p.body) else { continue };
// A body's records were rounded where it was modelled: a plane may stand an ulp of
// those coordinates off its edges, which matters for a part far smaller than its
// distance from the origin.
let far = 1e-14 * def.offset.x.abs().max(def.offset.y.abs()).max(def.offset.z.abs());
for (ei, e) in def.edges.iter().enumerate() {
if e.kind == EdgeKind::Seam || (e.kind == EdgeKind::Tangent && !opts.tangent_edges) {
continue;
}
tracks.push(Track {
placement: pi,
curve: TrackCurve::Edge(&e.curve),
range: e.curve.domain(),
source: Source::Edge { edge: ei, tangent: e.kind == EdgeKind::Tangent },
acc: e.acc,
own: e.faces.clone(),
// Skip the ray's own start on its faces: rounding grows with the coordinates
// (1e-9 of the scene), the margin with the faces themselves (1e-6 of their
// size), never with the whole scene, so small parts in large scenes keep their
// self-occlusion.
own_eps: {
let size = e.faces.iter().filter_map(|f| def.faces.get(*f)).map(|f| (f.hi - f.lo).len()).fold(0., f64::max);
let base = (1e-9 * ctx.scale).max(1e-6 * size).max(far);
match e.acc {
CurveAccuracy::Bounded { max_deviation_mm: tol } => base.max(10. * tol),
_ => base,
}
},
samples: Vec::new(),
sags: Vec::new(),
splits: Vec::new(),
});
}
let dl = p.local_dir(view.d);
let supported = |f: &FaceData| !(f.freeform && !opts.freeform) && f.trim.unsupported.is_none();
// Faces on one surface (a sphere in two halves, say) share their silhouettes, keyed by
// the set's first face: one curve along their seams, not one per face.
let mut sets: std::collections::BTreeMap<usize, Vec<usize>> = std::collections::BTreeMap::new();
for (fi, f) in def.faces.iter().enumerate() {
if f.freeform && !opts.freeform {
unsupported.push(Unsupported { placement: pi, face: fi, reason: "freeform face" });
continue;
}
if let Some(reason) = f.trim.unsupported {
unsupported.push(Unsupported { placement: pi, face: fi, reason });
continue;
}
if matches!(f.analytic, Analytic::Plane) {
continue;
}
// The set's silhouette is traced on its first face's surface, so a face joins only
// when its recognised surface is that one to rounding (1e-13); recognition groups
// surfaces more loosely (1e-9), and two surfaces that close can still differ inside
// the faces (two spherical caps through one circle).
let first = f.group.iter().copied().filter(|j| def.faces.get(*j).is_some_and(supported)).min().unwrap_or(fi);
let fits = def.faces.get(first).is_some_and(|l| same_analytic(&l.analytic, &f.analytic, 1e-13));
sets.entry(if fits { first } else { fi }).or_default().push(fi);
}
for (fi, members) in sets {
let Some(f) = def.faces.get(fi) else { continue };
let parts: Vec<(&S3, &Trim)> = members.iter().filter_map(|j| def.faces.get(*j)).map(|m| (&m.surface, &m.trim)).collect();
let size = members.iter().filter_map(|j| def.faces.get(*j)).map(|m| (m.hi - m.lo).len()).fold(0., f64::max);
let mut sils = Vec::new();
silhouette::silhouettes(&parts, f.analytic, dl, &mut sils);
for s in sils {
for r in &s.ranges {
stats.silhouettes += 1;
tracks.push(Track {
placement: pi,
curve: TrackCurve::Owned(s.curve.clone()),
range: *r,
source: Source::Silhouette { face: fi },
acc: s.acc,
own: f.group.clone(),
own_eps: match s.acc {
CurveAccuracy::Sampled { max_sample_deviation_mm: dev } => {
(1e-9 * ctx.scale).max(1e-6 * size).max(far).max(2. * (2. * size * dev).sqrt())
}
_ => (1e-9 * ctx.scale).max(1e-6 * size).max(far),
},
samples: Vec::new(),
sags: Vec::new(),
splits: Vec::new(),
});
}
}
}
if tracks.len() > opts.max_tracks {
return Err(HlrError::Budget("curve"));
}
}
stats.tracks = tracks.len();
// 2. Screen samples.
for (ti, t) in tracks.iter_mut().enumerate() {
if ti % 64 == 0 && cancel() {
return Err(HlrError::Cancelled);
}
let Some(p) = scene.get(t.placement) else { continue };
let c = t.c3();
let mut ts: Vec<f64> = c.breaks().into_iter().filter(|x| *x > t.range[0] && *x < t.range[1]).collect();
ts.push(t.range[0]);
ts.push(t.range[1]);
ts.sort_by(f64::total_cmp);
let per = match c {
C3::Line { .. } => 1,
C3::Polyline(_) => 1,
_ => 32,
};
let mut params = Vec::new();
for w in ts.windows(2) {
let (Some(a), Some(b)) = (w.first(), w.get(1)) else { continue };
for i in 0..per {
params.push(a + (b - a) * i as f64 / per as f64);
}
}
params.push(t.range[1]);
let screen = |x: f64| view.screen(p.apply(c.at(x)));
let mut samples: Vec<(f64, [f64; 2])> = params.into_iter().map(|x| (x, screen(x))).collect();
// Halve chords of exact curves until their sag on screen is within the target, so
// chords stand for the curve closely enough for coincidence and crossing tests.
if !matches!(c, C3::Line { .. } | C3::Polyline(_)) {
let target = 1e-7 * scale.max(1.);
for _ in 0..12 {
let mut next = Vec::with_capacity(samples.len() * 2);
let mut split = false;
for w in samples.windows(2) {
let (Some(a), Some(b)) = (w.first(), w.get(1)) else { continue };
next.push(*a);
let m = 0.5 * (a.0 + b.0);
let q = screen(m);
// A spline's piece is held by its control points' hull: a parameterisation
// racing between samples cannot hide a swerve from the chord.
let hull =
c.hull([a.0, b.0]).map_or(0., |h| h.iter().map(|x| point_segment(view.screen(p.apply(*x)), a.1, b.1)).fold(0., f64::max));
if point_segment(q, a.1, b.1).max(hull) > target && next.len() < 1 << 16 {
next.push((m, q));
split = true;
}
}
if let Some(last) = samples.last() {
next.push(*last);
}
samples = next;
if !split {
break;
}
}
}
// Chord sag on screen: exact for lines, measured at the middle for curves; a sampled
// silhouette's chords stand for the true curve to within its measured deviation.
// A fitted source record stands for the true curve to within its bound.
let fitted = match t.acc {
CurveAccuracy::Bounded { max_deviation_mm: tol } => tol,
_ => 0.,
};
let sags = samples
.windows(2)
.map(|w| {
fitted
+ match (c, w.first(), w.get(1)) {
(C3::Line { .. }, _, _) => 0.,
(C3::Polyline(_), _, _) => match t.acc {
CurveAccuracy::Sampled { max_sample_deviation_mm: dev } => dev,
_ => 0.,
},
(_, Some(a), Some(b)) => {
let hull = c
.hull([a.0, b.0])
.map_or(0., |h| h.iter().map(|x| point_segment(view.screen(p.apply(*x)), a.1, b.1)).fold(0., f64::max));
point_segment(view.screen(p.apply(c.at(0.5 * (a.0 + b.0)))), a.1, b.1).max(hull)
}
_ => 0.,
}
})
.collect();
t.samples = samples;
t.sags = sags;
}
stats.phase_ms[0] = clock.lap();
// 3. Crossings between projected curves (and each curve with itself).
stats.crossings = crossings(&mut tracks, &ctx)?;
// Faces left out (freeform or with an unsupported trim) draw no silhouettes to cut at, so
// the curves are cut where they cross each such face's screen box instead, and below a
// piece inside a box and behind its nearest point is uncertain: it may be hidden.
let shadows = ShadowIndex::new(shadow_boxes(defs, scene, view, &unsupported))?;
let mut near = Vec::new();
let mut checks = 0usize;
for (ti, t) in tracks.iter_mut().enumerate() {
if shadows.list.is_empty() {
break;
}
if ti % 64 == 0 && cancel() {
return Err(HlrError::Cancelled);
}
let Some(pl) = scene.get(t.placement) else { continue };
let mut cuts = Vec::new();
for w in t.samples.windows(2) {
let (Some(a), Some(b)) = (w.first(), w.get(1)) else { continue };
// The curve's own screen box between the two samples: it can reach past the chord,
// across it or along it (a view along an arc's plane folds it back on itself).
let (lo, hi) = screen_box(t.c3(), [a.0, b.0], pl, view);
shadows.query(lo, hi, &mut near);
checks = checks.saturating_add(near.len());
if checks > 500_000_000 {
return Err(HlrError::Budget("shadow"));
}
for sh in near.iter().filter_map(|k| shadows.list.get(*k)) {
for (k, edge) in [(0usize, sh.lo[0]), (0, sh.hi[0]), (1, sh.lo[1]), (1, sh.hi[1])] {
let (u, v) = (a.1[k], b.1[k]);
if (u - edge) * (v - edge) < 0. {
// Where the curve itself crosses the side, not its chord.
let side = |x: f64| view.screen(pl.apply(t.c3().at(x))).get(k).copied().unwrap_or(0.) - edge;
let (mut lo, mut hi) = (a.0, b.0);
for _ in 0..60 {
let mid = 0.5 * (lo + hi);
if (side(mid) < 0.) == (u - edge < 0.) {
lo = mid;
} else {
hi = mid;
}
}
cuts.push(0.5 * (lo + hi));
}
}
// A curve that enters the box where its chord does not: its stretch becomes a
// piece of its own, judged below.
if overlaps(lo, hi, sh) && box_gap(a.1, b.1, sh.lo, sh.hi) > 0. {
cuts.push(a.0);
cuts.push(b.0);
}
}
}
t.splits.extend(cuts);
}
stats.phase_ms[1] = clock.lap();
// 4. Classify pieces between splits.
let mut lines = Vec::with_capacity(tracks.len());
for (ti, t) in tracks.iter().enumerate() {
if ti % 64 == 0 && cancel() {
return Err(HlrError::Cancelled);
}
let c = t.c3();
let mut cuts = t.splits.clone();
cuts.push(t.range[0]);
cuts.push(t.range[1]);
cuts.retain(|x| *x >= t.range[0] && *x <= t.range[1]);
cuts.sort_by(f64::total_cmp);
let span = t.range[1] - t.range[0];
// Cuts merge when their parameters and their points are both close: nearby parameters
// alone do not tell (a knot span narrower than 1e-10 of the range can carry most of a
// circle), nor do equal points (a closed curve's two ends).
cuts.dedup_by(|a, b| *a == *b || ((*a - *b).abs() <= 1e-10 * span && c.at(*a).dist(c.at(*b)) <= 1e-9 * scale.max(1.)));
let mut pieces: Vec<Piece> = Vec::new();
for w in cuts.windows(2) {
let (Some(&a), Some(&b)) = (w.first(), w.get(1)) else { continue };
for (r, vis) in classify_range(t, a, b, &ctx)? {
let vis = if vis == Visibility::Visible && in_shadow(t, r, scene, view, &shadows) { Visibility::Uncertain } else { vis };
match pieces.last_mut() {
Some(last) if last.visibility == vis && (last.t[1] - r[0]).abs() <= 1e-12 * span.max(1e-300) => last.t[1] = r[1],
_ => pieces.push(Piece {
t: r,
visibility: vis,
covered: false,
geometry: Vec::new(),
accuracy: t.acc,
points: Vec::new(),
sag: 0.,
}),
}
}
}
let p = scene.get(t.placement).ok_or(HlrError::Invalid("placement"))?;
for piece in &mut pieces {
let mut pts = vec![view.screen(p.apply(c.at(piece.t[0])))];
pts.extend(t.samples.iter().filter(|(x, _)| *x > piece.t[0] && *x < piece.t[1]).map(|(_, s)| *s));
pts.push(view.screen(p.apply(c.at(piece.t[1]))));
piece.points = pts;
piece.sag = t
.samples
.windows(2)
.zip(&t.sags)
.filter(|(w, _)| w.get(1).is_some_and(|b| b.0 > piece.t[0]) && w.first().is_some_and(|a| a.0 < piece.t[1]))
.map(|(_, sag)| *sag)
.fold(0., f64::max);
}
stats.pieces += pieces.len();
stats.uncertain_pieces += pieces.iter().filter(|p| p.visibility == Visibility::Uncertain).count();
lines.push(Line { placement: t.placement, source: t.source, pieces });
}
stats.phase_ms[2] = clock.lap();
// Coverage is checked every 1e-4 of the scene (5 um to 0.5 mm): a gap narrower than that
// in a coincident line is not seen.
cover(&mut lines, 1e-7 + 1e-9 * scale, (1e-4 * scale).clamp(0.005, 0.5), cancel)?;
stats.phase_ms[3] = clock.lap();
for p in lines.iter().flat_map(|l| l.pieces.iter()) {
stats.covered_pieces += usize::from(p.covered);
stats.uncertain_uncovered += usize::from(p.visibility == Visibility::Uncertain && !p.covered);
}
stats.rays = ctx.rays.get();
stats.surface_ray_tests = ctx.surface_tests.get();
stats.unexpected_transitions = ctx.transitions.get();
// Output geometry, back in the caller's frame.
let shifted = |q: [f64; 2]| [q[0] + shift[0], q[1] + shift[1]];
for (l, t) in lines.iter_mut().zip(&tracks) {
let p = scene.get(t.placement).ok_or(HlrError::Invalid("placement"))?;
for piece in &mut l.pieces {
let (geometry, accuracy) = piece_geometry(t, piece, p, view);
piece.geometry = geometry.into_iter().map(|g| shift_seg(g, shift)).collect();
piece.accuracy = accuracy;
piece.points = piece.points.iter().map(|q| shifted(*q)).collect();
}
}
Ok(Drawing { lines, unsupported, stats })
}
/// The centre of the placed bodies' boxes, after checking the placements.
/// A left-out face's screen box and the depth of its nearest corner.
struct Shadow {
lo: [f64; 2],
hi: [f64; 2],
near: f64,
}
fn shadow_boxes(defs: &[Prepared], scene: &[Placement], view: &View, left_out: &[Unsupported]) -> Vec<Shadow> {
let mut out = Vec::new();
for u in left_out {
let Some(p) = scene.get(u.placement) else { continue };
let Some(f) = defs.get(p.body).and_then(|d| d.faces.get(u.face)) else { continue };
let (mut lo, mut hi, mut near) = ([f64::MAX; 2], [f64::MIN; 2], f64::MAX);
for k in 0..8 {
let c = Vec3::new(
if k & 1 == 0 { f.lo.x } else { f.hi.x },
if k & 2 == 0 { f.lo.y } else { f.hi.y },
if k & 4 == 0 { f.lo.z } else { f.hi.z },
);
let w = p.apply(c);
let s = view.screen(w);
lo = [lo[0].min(s[0]), lo[1].min(s[1])];
hi = [hi[0].max(s[0]), hi[1].max(s[1])];
near = near.min(w.dot(view.d));
}
out.push(Shadow { lo, hi, near });
}
out
}
/// Whether the piece `r` of a track may lie behind a left-out face, its own faces included (a
/// curled face can hide its own edge closer than the own-face margin).
fn in_shadow(t: &Track, r: [f64; 2], scene: &[Placement], view: &View, shadows: &ShadowIndex) -> bool {
if shadows.list.is_empty() {
return false;
}
let Some(p) = scene.get(t.placement) else { return false };
let c = t.c3();
// The piece is cut at the boxes' sides and where its curve enters a box between samples:
// it is in a box when its own screen box overlaps it and, for a piece holding samples, its
// middle or one of those samples lies in it (its ends may sit on the side it was cut at).
// Then it is in the shadow when its depth can pass the face's nearest point anywhere along
// it: the bound comes from the curve itself (its control points' hull, an arc's reach),
// not from samples, which a dip in depth that the screen does not show could fall between.
let (lo, hi) = screen_box(c, r, p, view);
let mut near = Vec::new();
shadows.query(lo, hi, &mut near);
if near.is_empty() {
return false;
}
let inner: Vec<[f64; 2]> = t.samples.iter().filter(|q| q.0 > r[0] && q.0 < r[1]).map(|q| q.1).collect();
let mid = view.screen(p.apply(c.at(0.5 * (r[0] + r[1]))));
let deepest = depth_bound(c, r, p, view.d);
near.iter().filter_map(|k| shadows.list.get(*k)).any(|sh| {
let within = |s: &[f64; 2]| s[0] >= sh.lo[0] && s[0] <= sh.hi[0] && s[1] >= sh.lo[1] && s[1] <= sh.hi[1];
deepest > sh.near && overlaps(lo, hi, sh) && (inner.is_empty() || within(&mid) || inner.iter().any(within))
})
}
/// Whether the box `lo hi` and a shadow's box share some area.
fn overlaps(lo: [f64; 2], hi: [f64; 2], sh: &Shadow) -> bool {
lo[0] < sh.hi[0] && hi[0] > sh.lo[0] && lo[1] < sh.hi[1] && hi[1] > sh.lo[1]
}
/// The screen box of the curve's part `r` placed by `p`: a line's ends, an arc's ends and its
/// extremes along each screen axis, the projected control points a spline's part depends on
/// (they hold it), a polyline's vertices.
fn screen_box(c: &C3, r: [f64; 2], p: &Placement, view: &View) -> ([f64; 2], [f64; 2]) {
let s = |q: Vec3| view.screen(p.apply(q));
let mut pts = vec![s(c.at(r[0])), s(c.at(r[1]))];
match c {
C3::Line { .. } => {}
C3::Arc { x, y, r: rad, .. } => {
// On screen: centre + U cos t + V sin t; each axis peaks where tan t = V_k / U_k.
let lin = |w: Vec3| view.screen(p.apply(w) - p.translation);
let (u, v) = (lin(*x * rad[0]), lin(*y * rad[1]));
for k in 0..2 {
let (Some(&uk), Some(&vk)) = (u.get(k), v.get(k)) else { continue };
// The peaks at base + k pi from the first one past the part's start, wherever
// its angles are counted from.
let (base, pi) = (vk.atan2(uk), std::f64::consts::PI);
let first = ((r[0] - base) / pi).ceil();
for k in 0..8 {
let t = base + (first + k as f64) * pi;
if t >= r[1] {
break;
}
if t > r[0] {
pts.push(s(c.at(t)));
}
}
}
}
C3::Spline { degree, knots, points, .. } => match c.hull(r) {
Some(h) => pts.extend(h.into_iter().map(s)),
None => pts.extend(
points
.iter()
.enumerate()
.filter(|(i, h)| h[3] > 0. && knots.get(*i).zip(knots.get(i + degree + 1)).is_some_and(|(lo, hi)| *lo < r[1] && *hi > r[0]))
.map(|(_, h)| s(Vec3::new(h[0] / h[3], h[1] / h[3], h[2] / h[3]))),
),
},
C3::Polyline(v) => pts.extend(v.iter().enumerate().filter(|(i, _)| (*i as f64) > r[0] && (*i as f64) < r[1]).map(|(_, q)| s(*q))),
}
let lo = pts.iter().fold([f64::MAX; 2], |m, q| [m[0].min(q[0]), m[1].min(q[1])]);
let hi = pts.iter().fold([f64::MIN; 2], |m, q| [m[0].max(q[0]), m[1].max(q[1])]);
(lo, hi)
}
/// Left-out faces' boxes on a uniform screen grid, so a curve meets only those near it.
struct ShadowIndex {
list: Vec<Shadow>,
lo: [f64; 2],
hi: [f64; 2],
cell: [f64; 2],
n: usize,
buckets: Vec<Vec<usize>>,
}
impl ShadowIndex {
fn new(list: Vec<Shadow>) -> Result<ShadowIndex, HlrError> {
let (mut lo, mut hi) = ([f64::MAX; 2], [f64::MIN; 2]);
for sh in &list {
lo = [lo[0].min(sh.lo[0]), lo[1].min(sh.lo[1])];
hi = [hi[0].max(sh.hi[0]), hi[1].max(sh.hi[1])];
}
let n = ((list.len() as f64).sqrt().ceil() as usize).clamp(1, 1024);
let cell = [((hi[0] - lo[0]) / n as f64).max(1e-12), ((hi[1] - lo[1]) / n as f64).max(1e-12)];
let mut index = ShadowIndex { list: Vec::new(), lo, hi, cell, n, buckets: vec![Vec::new(); n * n] };
let mut entries = 0usize;
for (k, sh) in list.iter().enumerate() {
let (a, b) = (index.cell_of(sh.lo), index.cell_of(sh.hi));
entries = entries.saturating_add((b[0] - a[0] + 1).saturating_mul(b[1] - a[1] + 1));
if entries > 50_000_000 {
return Err(HlrError::Budget("shadow grid"));
}
for y in a[1]..=b[1] {
for x in a[0]..=b[0] {
if let Some(bucket) = index.buckets.get_mut(y * n + x) {
bucket.push(k);
}
}
}
}
index.list = list;
Ok(index)
}
fn cell_of(&self, p: [f64; 2]) -> [usize; 2] {
let f = |k: usize| (((p[k] - self.lo[k]) / self.cell[k]).floor().clamp(0., (self.n - 1) as f64)) as usize;
[f(0), f(1)]
}
/// The boxes in the cells the box `lo hi` touches, each once.
fn query(&self, lo: [f64; 2], hi: [f64; 2], out: &mut Vec<usize>) {
out.clear();
if self.list.is_empty() || hi[0] < self.lo[0] || hi[1] < self.lo[1] || lo[0] > self.hi[0] || lo[1] > self.hi[1] {
return;
}
let (a, b) = (self.cell_of(lo), self.cell_of(hi));
for y in a[1]..=b[1] {
for x in a[0]..=b[0] {
if let Some(bucket) = self.buckets.get(y * self.n + x) {
out.extend_from_slice(bucket);
}
}
}
out.sort_unstable();
out.dedup();
}
}
/// An upper bound of the depth along `d` of the curve's part `r` placed by `p`: a line's ends,
/// an arc's centre plus its reach, the projected control points a spline's part depends on
/// (its weights are positive, so the part lies in their hull), a polyline's vertices.
fn depth_bound(c: &C3, r: [f64; 2], p: &Placement, d: Vec3) -> f64 {
let depth = |q: Vec3| p.apply(q).dot(d);
match c {
C3::Line { .. } => depth(c.at(r[0])).max(depth(c.at(r[1]))),
C3::Arc { o, x, y, r: rad, .. } => {
let dl = p.local_dir(d);
depth(*o) + (rad[0] * x.dot(dl)).hypot(rad[1] * y.dot(dl))
}
C3::Spline { degree, knots, points, .. } => match c.hull(r) {
Some(h) => h.into_iter().map(depth).fold(f64::MIN, f64::max),
None => points
.iter()
.enumerate()
.filter(|(i, h)| h[3] > 0. && knots.get(*i).zip(knots.get(i + degree + 1)).is_some_and(|(lo, hi)| *lo < r[1] && *hi > r[0]))
.map(|(_, h)| depth(Vec3::new(h[0] / h[3], h[1] / h[3], h[2] / h[3])))
.fold(f64::MIN, f64::max),
}
.max(depth(c.at(r[0])))
.max(depth(c.at(r[1]))),
C3::Polyline(pts) => pts
.iter()
.enumerate()
.filter(|(i, _)| (*i as f64) > r[0] && (*i as f64) < r[1])
.map(|(_, q)| depth(*q))
.fold(depth(c.at(r[0])).max(depth(c.at(r[1]))), f64::max),
}
}
/// Distance between the segment `a b` and the box `lo hi` (zero when they meet).
fn box_gap(a: [f64; 2], b: [f64; 2], lo: [f64; 2], hi: [f64; 2]) -> f64 {
let inside = |p: [f64; 2]| p[0] >= lo[0] && p[0] <= hi[0] && p[1] >= lo[1] && p[1] <= hi[1];
if inside(a) || inside(b) {
return 0.;
}
let corners = [[lo[0], lo[1]], [hi[0], lo[1]], [hi[0], hi[1]], [lo[0], hi[1]]];
let crosses = (0..4).any(|k| {
let (Some(c), Some(d)) = (corners.get(k), corners.get((k + 1) % 4)) else { return false };
let side = |p: [f64; 2], q: [f64; 2], r: [f64; 2]| (q[0] - p[0]) * (r[1] - p[1]) - (q[1] - p[1]) * (r[0] - p[0]);
side(a, b, *c) * side(a, b, *d) <= 0. && side(*c, *d, a) * side(*c, *d, b) <= 0.
});
if crosses {
return 0.;
}
let to_box = |p: [f64; 2]| {
let dx = (lo[0] - p[0]).max(p[0] - hi[0]).max(0.);
let dy = (lo[1] - p[1]).max(p[1] - hi[1]).max(0.);
dx.hypot(dy)
};
let corner_gap = corners.iter().map(|q| point_segment(*q, a, b)).fold(f64::MAX, f64::min);
to_box(a).min(to_box(b)).min(corner_gap)
}
fn scene_centre(defs: &[Prepared], scene: &[Placement]) -> Result<Vec3, HlrError> {
let (mut lo, mut hi) = (Vec3::new(f64::MAX, f64::MAX, f64::MAX), Vec3::new(f64::MIN, f64::MIN, f64::MIN));
for p in scene {
if !p.rigid() {
return Err(HlrError::Invalid("placement (not a rotation and translation)"));
}
let def = defs.get(p.body).ok_or(HlrError::Invalid("placement body index"))?;
for k in 0..8 {
let c = Vec3::new(
if k & 1 == 0 { def.lo.x } else { def.hi.x },
if k & 2 == 0 { def.lo.y } else { def.hi.y },
if k & 4 == 0 { def.lo.z } else { def.hi.z },
);
let w = p.apply(c + def.offset);
if !(w.x.abs() <= MAX_COORDINATE && w.y.abs() <= MAX_COORDINATE && w.z.abs() <= MAX_COORDINATE) {
return Err(HlrError::Invalid("scene extent"));
}
lo = lo.min(w);
hi = hi.max(w);
}
}
let c = if scene.is_empty() { Vec3::ZERO } else { (lo + hi) * 0.5 };
if c.is_finite() { Ok(c) } else { Err(HlrError::Invalid("scene extent")) }
}
fn shift_seg(g: Seg2, d: [f64; 2]) -> Seg2 {
let m = |v: Vec2| Vec2::new(v.x + d[0], v.y + d[1]);
match g {
Seg2::Line { a, b } => Seg2::Line { a: m(a), b: m(b) },
Seg2::Arc { center, radius, start, sweep } => Seg2::Arc { center: m(center), radius, start, sweep },
Seg2::Cubic { p0, p1, p2, p3 } => Seg2::Cubic { p0: m(p0), p1: m(p1), p2: m(p2), p3: m(p3) },
Seg2::Conic { a, apex, b, w } => Seg2::Conic { a: m(a), apex: m(apex), b: m(b), w },
Seg2::Bezier { n, p } => Seg2::Bezier { n, p: p.map(m) },
}
}
/// A piece's screen geometry: a line for a straight source, exact conic arcs for a circle or
/// ellipse (an orthographic projection is affine, so it maps them to ellipses exactly), chords
/// between its exact points otherwise.
fn piece_geometry(t: &Track, piece: &Piece, p: &Placement, view: &View) -> (Vec<Seg2>, CurveAccuracy) {
let c = t.c3();
let s = |q: Vec3| {
let v = view.screen(p.apply(q));
Vec2::new(v[0], v[1])
};
let chords = || {
let segs: Vec<Seg2> =
piece.points.windows(2).filter_map(|w| Some(Seg2::Line { a: Vec2::from(*w.first()?), b: Vec2::from(*w.get(1)?) })).collect();
(segs, CurveAccuracy::Sampled { max_sample_deviation_mm: piece.sag })
};
match c {
C3::Line { .. } if t.acc == CurveAccuracy::Analytic => {
(vec![Seg2::Line { a: s(c.at(piece.t[0])), b: s(c.at(piece.t[1])) }], CurveAccuracy::Analytic)
}
_ if t.acc == CurveAccuracy::Analytic => {
// A circle or ellipse: o + u cos(a) + v sin(a), sampled at the piece's angles.
let frame = match c {
C3::Arc { o, x, y, r, .. } => Some((*o, *x * r[0], *y * r[1], true)),
_ => as_circle(c, 1e-9).and_then(|(centre, normal, r)| {
let e1 = (c.at(t.range[0]) - centre).normalized()?;
Some((centre, e1 * r, normal.cross(e1) * r, false))
}),
};
let Some((o, u, v, param_is_angle)) = frame else { return chords() };
let angle = |x: f64| {
if param_is_angle {
return x;
}
let w = c.at(x) - o;
w.dot(v).atan2(w.dot(u))
};
// The angle turned from the piece's start to its end: the way it turns, certified
// all along it (C3::turn_sign; a piece that turns back, or one that cannot be
// certified, is drawn as chords), and its end angles fix the turn, however unevenly
// it is parameterised. A whole closed edge turns a full circle.
let (a0, a1) = if param_is_angle {
(piece.t[0], piece.t[1])
} else {
let tau = std::f64::consts::TAU;
let wrap = |d: f64| (d + std::f64::consts::PI).rem_euclid(tau) - std::f64::consts::PI;
let (t0, t1) = (piece.t[0], piece.t[1]);
let span = (t.range[1] - t.range[0]).abs();
let a0 = angle(t0);
let ends = angle(t1) - a0;
let dir = match c.turn_sign([t0, t1], o, u, v) {
Some(d) if d != 0. => d,
// It does not turn at all: a point-like piece, unless its ends differ.
Some(_) if wrap(ends).abs() <= 1e-9 => 1.,
_ => return chords(),
};
let mut turn = (dir * ends).rem_euclid(tau);
let whole =
t0 <= t.range[0] + 1e-12 * span && t1 >= t.range[1] - 1e-12 * span && c.at(t.range[0]).dist(c.at(t.range[1])) <= 1e-9 * u.len();
if whole && (turn < 1e-9 || turn > tau - 1e-9) {
turn = tau;
}
(a0, a0 + dir * turn)
};
let pieces = ((a1 - a0).abs() / std::f64::consts::FRAC_PI_2).ceil().max(1.) as usize;
let at = |a: f64| o + u * a.cos() + v * a.sin();
let mut out = Vec::with_capacity(pieces);
for k in 0..pieces {
let (b0, b1) = (a0 + (a1 - a0) * k as f64 / pieces as f64, a0 + (a1 - a0) * (k + 1) as f64 / pieces as f64);
let (m, h) = (0.5 * (b0 + b1), 0.5 * (b1 - b0));
let w = h.cos();
if w <= 1e-12 {
return chords();
}
out.push(Seg2::Conic { a: s(at(b0)), apex: s(o + (u * m.cos() + v * m.sin()) / w), b: s(at(b1)), w });
}
(out, CurveAccuracy::Analytic)
}
_ => chords(),
}
}
/// Finds where projected tracks cross or touch and records the split parameters on both.
fn crossings(tracks: &mut [Track], ctx: &Ctx) -> Result<usize, HlrError> {
struct Seg {
track: usize,
i: usize,
a: [f64; 2],
b: [f64; 2],
sag: f64,
/// The grid cells it was put in: first and last column and row.
cells: [usize; 4],
}
let mut segs = Vec::new();
// Where each track's segments start in `segs`.
let mut first_seg = Vec::with_capacity(tracks.len());
let (mut lo, mut hi) = ([f64::MAX; 2], [f64::MIN; 2]);
for (ti, t) in tracks.iter().enumerate() {
first_seg.push(segs.len());
for (i, w) in t.samples.windows(2).enumerate() {
let (Some(a), Some(b)) = (w.first(), w.get(1)) else { continue };
for p in [a.1, b.1] {
lo = [lo[0].min(p[0]), lo[1].min(p[1])];
hi = [hi[0].max(p[0]), hi[1].max(p[1])];
}
segs.push(Seg { track: ti, i, a: a.1, b: b.1, sag: t.sags.get(i).copied().unwrap_or(0.), cells: [0; 4] });
}
}
if segs.is_empty() {
return Ok(0);
}
let n = ((segs.len() as f64).sqrt().ceil() as usize).clamp(1, 512);
let cell = [((hi[0] - lo[0]) / n as f64).max(1e-12), ((hi[1] - lo[1]) / n as f64).max(1e-12)];
let idx = |p: [f64; 2]| -> (usize, usize) {
(((p[0] - lo[0]) / cell[0]).floor().clamp(0., (n - 1) as f64) as usize, ((p[1] - lo[1]) / cell[1]).floor().clamp(0., (n - 1) as f64) as usize)
};
let mut grid: Vec<Vec<usize>> = vec![Vec::new(); n * n];
let mut entries = 0usize;
for (si, s) in segs.iter_mut().enumerate() {
if si % 65536 == 0 && (ctx.cancel)() {
return Err(HlrError::Cancelled);
}
let g = s.sag + 1e-9 * ctx.scale;
let (a, b) = (idx([s.a[0].min(s.b[0]) - g, s.a[1].min(s.b[1]) - g]), idx([s.a[0].max(s.b[0]) + g, s.a[1].max(s.b[1]) + g]));
entries = entries.saturating_add((b.0 - a.0 + 1).saturating_mul(b.1 - a.1 + 1));
if entries > 50_000_000 {
return Err(HlrError::Budget("crossing grid"));
}
s.cells = [a.0, a.1, b.0, b.1];
for y in a.1..=b.1 {
for x in a.0..=b.0 {
if let Some(c) = grid.get_mut(y * n + x) {
c.push(si);
}
}
}
}
// A pair of segments is visited once per cell they share, so the number of visits is
// known before the search starts, and no set of pairs already met has to be kept.
let pairs = grid.iter().fold(0usize, |n, c| n.saturating_add(c.len().saturating_mul(c.len().saturating_sub(1)) / 2));
if pairs > 500_000_000 {
return Err(HlrError::Budget("crossing pair"));
}
let tol = 1e-9 * ctx.scale;
let mut found = Vec::new();
let mut visits = 0usize;
// Two chords that lie on each other end to end, to rounding.
let coincide = |s: &Seg, t: &Seg| {
[point_segment(s.a, t.a, t.b), point_segment(s.b, t.a, t.b), point_segment(t.a, s.a, s.b), point_segment(t.b, s.a, s.b)]
.iter()
.all(|d| *d <= tol)
};
// The segment of the same track on the other side of a segment's end `f` (0 or 1).
let across = |s: &Seg, f: f64| -> Option<&Seg> {
let i = if f == 1. { s.i + 1 } else { s.i.checked_sub(1)? };
segs.get(first_seg.get(s.track)? + i).filter(|n| n.track == s.track && n.i == i)
};
// Two curves that coincide meet at every sample point they share, chord ends touching. Such
// a meeting is no crossing when the curves also coincide on both sides of it; where a
// coincident run starts or ends, one side differs and the meeting is kept.
// The end (0 or 1) of a segment that fraction `f` along it lies at, to rounding.
let end_at = |s: &Seg, f: f64| {
let len = (s.b[0] - s.a[0]).hypot(s.b[1] - s.a[1]);
if f * len <= tol {
Some(0.)
} else if (1. - f) * len <= tol {
Some(1.)
} else {
None
}
};
let shared_point = |s: &Seg, t: &Seg, (u, v): (f64, f64)| {
end_at(s, u)
.zip(end_at(t, v))
.and_then(|(fu, fv)| across(s, fu).zip(across(t, fv)))
.is_some_and(|(s2, t2)| coincide(s, t2) && coincide(s2, t))
};
// Screen points of a segment's exact curve, `k` pieces (one for lines and polylines).
let sub = |track: usize, i: usize, k: usize| -> Vec<[f64; 2]> {
let Some(tr) = tracks.get(track) else { return Vec::new() };
let (Some(a), Some(b)) = (tr.samples.get(i), tr.samples.get(i + 1)) else { return Vec::new() };
let Some(p) = ctx.scene.get(tr.placement) else { return Vec::new() };
let k = if matches!(tr.c3(), C3::Line { .. } | C3::Polyline(_)) { 1 } else { k };
(0..=k).map(|j| ctx.view.screen(p.apply(tr.c3().at(a.0 + (b.0 - a.0) * j as f64 / k as f64)))).collect()
};
for (c, cellv) in grid.iter().enumerate() {
let (x, y) = (c % n, c / n);
for (k, &i) in cellv.iter().enumerate() {
for &j in cellv.iter().skip(k + 1) {
visits += 1;
if visits.is_multiple_of(65536) && (ctx.cancel)() {
return Err(HlrError::Cancelled);
}
let (Some(s), Some(t)) = (segs.get(i), segs.get(j)) else { continue };
// A pair sharing several cells is intersected in the first of them only.
if s.cells[0].max(t.cells[0]) != x || s.cells[1].max(t.cells[1]) != y {
continue;
}
if s.track == t.track && s.i.abs_diff(t.i) <= 1 {
continue;
}
let straight = |k: usize| tracks.get(k).is_some_and(|tr| matches!(tr.c3(), C3::Line { .. }));
let overlaps = straight(s.track) && straight(t.track);
let hits = seg_hits(s.a, s.b, t.a, t.b, tol, overlaps);
let reach = s.sag + t.sag + tol;
// Chords of two curves that lie on each other end to end, to rounding (one curve
// projected again, aligned holes seen along their axes), cross only within that
// rounding, everywhere and nowhere in particular: visibility changes where such a
// run starts or ends, which chords that only partly overlap find. Intersecting
// their fine pieces is wasted work. Chords merely within each other's sag are not
// skipped: the curves between them can still cross.
let coincident = s.track != t.track && s.sag + t.sag > 0. && coincide(s, t);
if coincident {
continue;
}
if hits.is_empty() && s.sag + t.sag > 0. && seg_gap(s.a, s.b, t.a, t.b) <= reach {
// The chords miss but the curves may not: two crossings close together can
// lie within one chord's sag. Intersect finer pieces of the exact curves.
let (ps, pt) = (sub(s.track, s.i, 16), sub(t.track, t.i, 16));
let (ns, nt) = (ps.len().saturating_sub(1).max(1) as f64, pt.len().saturating_sub(1).max(1) as f64);
for (x, w) in ps.windows(2).enumerate() {
for (y, z) in pt.windows(2).enumerate() {
let (Some(a), Some(b), Some(c), Some(d)) = (w.first(), w.get(1), z.first(), z.get(1)) else { continue };
for (u, v) in seg_hits(*a, *b, *c, *d, tol, false) {
found.push((s.track, s.i, (x as f64 + u) / ns, t.track, t.i, (y as f64 + v) / nt));
}
}
}
} else {
let curved = s.track != t.track && s.sag + t.sag > 0.;
for (u, v) in hits {
if !(curved && shared_point(s, t, (u, v))) {
found.push((s.track, s.i, u, t.track, t.i, v));
}
}
}
if found.len() > 50_000_000 {
return Err(HlrError::Budget("crossing"));
}
}
}
}
// Curves that nearly coincide in projection (two fitted copies of one intersection, say)
// cross each other again and again within their tolerance; visibility changes only where
// the coincidence starts or ends, so such a pair keeps only its outermost crossings.
let mut by_pair: std::collections::BTreeMap<(usize, usize), Vec<(usize, usize, f64, usize, usize, f64)>> = std::collections::BTreeMap::new();
for c in found {
by_pair.entry((c.0.min(c.3), c.0.max(c.3))).or_default().push(c);
}
let mut found = Vec::new();
for (_, mut list) in by_pair {
if list.len() > 8 {
list.sort_by(|a, b| (a.1 as f64 + a.2).total_cmp(&(b.1 as f64 + b.2)));
// Collapse only when the curves stay within their sag of each other between every
// pair of consecutive crossings (one curve seen twice); a curve that weaves across
// another keeps all its crossings.
let together = list.windows(2).all(|w| {
let (Some(x), Some(y)) = (w.first(), w.get(1)) else { return false };
let (Some(ta), Some(tb)) = (tracks.get(x.0), tracks.get(x.3)) else { return false };
let mid = 0.5 * (sample_param(tracks, x.0, x.1, x.2) + sample_param(tracks, y.0, y.1, y.2));
let Some(pa) = ctx.scene.get(ta.placement) else { return false };
let q = ctx.view.screen(pa.apply(ta.c3().at(mid)));
let sag = |t: &Track| t.sags.iter().fold(0., |m: f64, v| m.max(*v));
let reach = 4. * (sag(ta) + sag(tb)) + tol;
// Only the other curve's chords between its two crossings (and one either side).
let (j0, j1) = (x.4.min(y.4).saturating_sub(1), x.4.max(y.4) + 2);
tb.samples.get(j0..j1.min(tb.samples.len())).is_some_and(|run| {
run.windows(2).any(|w| match (w.first(), w.get(1)) {
(Some(a), Some(b)) => point_segment(q, a.1, b.1) <= reach,
_ => false,
})
})
});
if together {
let (Some(first), Some(last)) = (list.first().copied(), list.last().copied()) else { continue };
list = vec![first, last];
}
}
found.extend(list);
}
let count = found.len();
for (ta, ia, u, tb, ib, v) in found {
let pa = sample_param(tracks, ta, ia, u);
let pb = sample_param(tracks, tb, ib, v);
let (pa, pb) = refine(tracks, ctx, ta, pa, tb, pb);
if let Some(t) = tracks.get_mut(ta) {
t.splits.push(pa);
}
if let Some(t) = tracks.get_mut(tb) {
t.splits.push(pb);
}
}
Ok(count)
}
fn sample_param(tracks: &[Track], t: usize, i: usize, f: f64) -> f64 {
let Some(tr) = tracks.get(t) else { return 0. };
match (tr.samples.get(i), tr.samples.get(i + 1)) {
(Some(a), Some(b)) => a.0 + (b.0 - a.0) * f,
_ => tr.range[0],
}
}
/// Newton refinement of a crossing on the exact projected curves; keeps the linear estimate
/// when the curves are tangent or the iteration leaves the curves' ranges.
fn refine(tracks: &[Track], ctx: &Ctx, ta: usize, sa: f64, tb: usize, sb: f64) -> (f64, f64) {
let (Some(a), Some(b)) = (tracks.get(ta), tracks.get(tb)) else { return (sa, sb) };
let (Some(pa), Some(pb)) = (ctx.scene.get(a.placement), ctx.scene.get(b.placement)) else { return (sa, sb) };
if matches!(a.c3(), C3::Polyline(_)) || matches!(b.c3(), C3::Polyline(_)) {
return (sa, sb);
}
let fa = |s: f64| ctx.view.screen(pa.apply(a.c3().at(s)));
let fb = |s: f64| ctx.view.screen(pb.apply(b.c3().at(s)));
let da = |s: f64| ctx.view.screen(pa.apply(a.c3().d1(s)) - pa.translation);
let db = |s: f64| ctx.view.screen(pb.apply(b.c3().d1(s)) - pb.translation);
let (mut s, mut t) = (sa, sb);
for _ in 0..30 {
let (p, q) = (fa(s), fb(t));
let f = [p[0] - q[0], p[1] - q[1]];
let (ja, jb) = (da(s), db(t));
// [ja, -jb] [ds, dt]^T = -f
let det = ja[0] * (-jb[1]) - (-jb[0]) * ja[1];
if det.abs() <= 1e-14 * (1. + ja[0].abs() + ja[1].abs()) * (1. + jb[0].abs() + jb[1].abs()) {
return (sa, sb);
}
let ds = (-f[0] * (-jb[1]) - (-jb[0]) * (-f[1])) / det;
let dt = (ja[0] * (-f[1]) - (-f[0]) * ja[1]) / det;
s += ds;
t += dt;
if ds.abs() + dt.abs() <= 1e-15 * (1. + s.abs() + t.abs()) {
break;
}
}
let ok = |x: f64, r: [f64; 2]| x.is_finite() && x >= r[0] - 1e-12 * (r[1] - r[0]) && x <= r[1] + 1e-12 * (r[1] - r[0]);
let close = (s - sa).abs() <= 0.5 * (a.range[1] - a.range[0]) && (t - sb).abs() <= 0.5 * (b.range[1] - b.range[0]);
if ok(s, a.range) && ok(t, b.range) && close { (s.clamp(a.range[0], a.range[1]), t.clamp(b.range[0], b.range[1])) } else { (sa, sb) }
}
/// Marks hidden and uncertain pieces lying within `tol` of a visible piece of another line.
fn cover(lines: &mut [Line], tol: f64, step: f64, cancel: &dyn Fn() -> bool) -> Result<(), HlrError> {
// Chords of visible and hidden pieces, keyed by (line, piece) so a piece never covers
// itself; another piece of the same line may (a circle seen edge-on folds over itself).
// `tol` is the base; each chord adds its own sag, each query point the sag of its chord.
let mut segs: Vec<((usize, usize), Visibility, [f64; 2], [f64; 2], f64)> = Vec::new();
for (li, l) in lines.iter().enumerate() {
for (pi, p) in l.pieces.iter().enumerate().filter(|(_, p)| p.visibility != Visibility::Uncertain) {
segs.extend(p.points.windows(2).filter_map(|w| Some(((li, pi), p.visibility, *w.first()?, *w.get(1)?, p.sag))));
}
}
let reach = segs.iter().map(|s| s.4).fold(0., f64::max) * 2. + tol;
if segs.is_empty() {
return Ok(());
}
// Bucket the chords on a grid of cells at least `tol` wide.
let (mut lo, mut hi) = ([f64::MAX; 2], [f64::MIN; 2]);
for (_, _, a, b, _) in &segs {
for p in [a, b] {
lo = [lo[0].min(p[0]), lo[1].min(p[1])];
hi = [hi[0].max(p[0]), hi[1].max(p[1])];
}
}
let n = ((segs.len() as f64).sqrt().ceil() as usize).clamp(1, 1024);
let cell = [((hi[0] - lo[0]) / n as f64).max(reach), ((hi[1] - lo[1]) / n as f64).max(reach)];
let at = |x: f64, k: usize| (((x - lo[k]) / cell[k]).floor().max(0.) as usize).min(n - 1);
let mut grid: Vec<Vec<usize>> = vec![Vec::new(); n * n];
for (i, (_, _, a, b, _)) in segs.iter().enumerate() {
for y in at(a[1].min(b[1]) - reach, 1)..=at(a[1].max(b[1]) + reach, 1) {
for x in at(a[0].min(b[0]) - reach, 0)..=at(a[0].max(b[0]) + reach, 0) {
if let Some(c) = grid.get_mut(y * n + x) {
c.push(i);
}
}
}
}
// Which coincident pieces hide a piece: visible ones hide hidden and uncertain pieces;
// a duplicate of a visible or hidden piece on an earlier line is dropped.
let hides = |key: (usize, usize), own: Visibility, other: (usize, usize), state: Visibility| {
other != key
&& match (own, state) {
(Visibility::Hidden | Visibility::Uncertain, Visibility::Visible) => true,
(Visibility::Visible, Visibility::Visible) | (Visibility::Hidden, Visibility::Hidden) => other.0 < key.0,
_ => false,
}
};
let checks = std::cell::Cell::new(0usize);
let near = |key: (usize, usize), own: Visibility, q: [f64; 2], slack: f64| {
checks.set(checks.get() + 1);
let Some(bucket) = grid.get(at(q[1], 1) * n + at(q[0], 0)) else { return false };
bucket
.iter()
.filter_map(|i| segs.get(*i))
.any(|(k, state, a, b, sag)| hides(key, own, *k, *state) && point_segment(q, *a, *b) <= tol + sag + slack)
};
for (li, l) in lines.iter_mut().enumerate() {
for (pi, p) in l.pieces.iter_mut().enumerate() {
// Points along every chord at most `step` apart (a coincident line may cover a long
// chord's ends and middle yet leave gaps between them). Points between the exact
// ones lie on the chord, up to the piece's sag from its curve.
let mut covered = !p.points.is_empty();
if checks.get() > 200_000_000 {
return Err(HlrError::Budget("coverage"));
}
if pi % 16 == 0 && cancel() {
return Err(HlrError::Cancelled);
}
for w in p.points.windows(2) {
let (Some(a), Some(b)) = (w.first(), w.get(1)) else { continue };
let k = ((a[0] - b[0]).hypot(a[1] - b[1]) / step).ceil().clamp(1., 1e6) as usize;
covered = covered
&& (0..=k).all(|j| {
let f = j as f64 / k as f64;
// The piece's own representation error (chord sag, fitted bound) applies
// to every point it is checked at.
let slack = p.sag;
near((li, pi), p.visibility, [a[0] + (b[0] - a[0]) * f, a[1] + (b[1] - a[1]) * f], slack)
});
if !covered {
break;
}
}
if let [q] = p.points.as_slice() {
covered = near((li, pi), p.visibility, *q, p.sag);
}
p.covered = covered;
}
}
Ok(())
}
fn point_segment(q: [f64; 2], a: [f64; 2], b: [f64; 2]) -> f64 {
let (ex, ey) = (b[0] - a[0], b[1] - a[1]);
let l2 = ex * ex + ey * ey;
let t = if l2 > 0. { (((q[0] - a[0]) * ex + (q[1] - a[1]) * ey) / l2).clamp(0., 1.) } else { 0. };
(a[0] + t * ex - q[0]).hypot(a[1] + t * ey - q[1])
}
/// Smallest distance between two screen segments that do not cross.
fn seg_gap(a: [f64; 2], b: [f64; 2], c: [f64; 2], d: [f64; 2]) -> f64 {
point_segment(a, c, d).min(point_segment(b, c, d)).min(point_segment(c, a, b)).min(point_segment(d, a, b))
}
/// Intersections of two screen segments, touching included: fractions along each.
fn seg_hits(a: [f64; 2], b: [f64; 2], c: [f64; 2], d: [f64; 2], tol: f64, overlaps: bool) -> Vec<(f64, f64)> {
let r = [b[0] - a[0], b[1] - a[1]];
let s = [d[0] - c[0], d[1] - c[1]];
let den = r[0] * s[1] - r[1] * s[0];
let w = [c[0] - a[0], c[1] - a[1]];
let (rl, sl) = ((r[0] * r[0] + r[1] * r[1]).sqrt(), (s[0] * s[0] + s[1] * s[1]).sqrt());
if rl <= 0. || sl <= 0. {
return Vec::new();
}
if den.abs() > 1e-12 * rl * sl {
let u = (w[0] * s[1] - w[1] * s[0]) / den;
let v = (w[0] * r[1] - w[1] * r[0]) / den;
let (tu, tv) = (tol / rl, tol / sl);
if u >= -tu && u <= 1. + tu && v >= -tv && v <= 1. + tv {
return vec![(u.clamp(0., 1.), v.clamp(0., 1.))];
}
return Vec::new();
}
// Parallel: overlapping collinear lines split at each other's endpoints. Sampled curves
// that coincide are skipped: their chords overlap everywhere and would split at every sample.
let dist = (w[0] * r[1] - w[1] * r[0]).abs() / rl;
if dist > tol || !overlaps {
return Vec::new();
}
let along = |p: [f64; 2]| ((p[0] - a[0]) * r[0] + (p[1] - a[1]) * r[1]) / (rl * rl);
let back = |p: [f64; 2]| ((p[0] - c[0]) * s[0] + (p[1] - c[1]) * s[1]) / (sl * sl);
let mut out = Vec::new();
for (p, on_cd) in [(c, true), (d, true), (a, false), (b, false)] {
let (u, v) = if on_cd { (along(p), if p == c { 0. } else { 1. }) } else { (if p == a { 0. } else { 1. }, back(p)) };
if (0. ..=1.).contains(&u) && (0. ..=1.).contains(&v) {
out.push((u, v));
}
}
out
}
/// States at a few interior points, with transitions located by bisection.
fn classify_range(t: &Track, a: f64, b: f64, ctx: &Ctx) -> Result<Vec<([f64; 2], Visibility)>, HlrError> {
let fr = [0.1, 0.3, 0.5, 0.7, 0.9];
let xs: Vec<f64> = fr.iter().map(|f| a + (b - a) * f).collect();
let mut states = Vec::with_capacity(xs.len());
for x in &xs {
states.push(classify(t, *x, ctx)?);
}
let mut out: Vec<([f64; 2], Visibility)> = Vec::new();
let mut start = a;
for k in 0..xs.len() {
let (Some(&s), Some(&x)) = (states.get(k), xs.get(k)) else { continue };
if let (Some(&next), Some(&nx)) = (states.get(k + 1), xs.get(k + 1)) {
if next != s {
ctx.transitions.set(ctx.transitions.get() + 1);
let (mut lo, mut hi) = (x, nx);
for _ in 0..40 {
let mid = 0.5 * (lo + hi);
if classify(t, mid, ctx)? == s {
lo = mid;
} else {
hi = mid;
}
}
let cut = 0.5 * (lo + hi);
out.push(([start, cut], s));
start = cut;
}
} else {
out.push(([start, b], s));
}
let _ = x;
}
Ok(out)
}
fn classify(t: &Track, x: f64, ctx: &Ctx) -> Result<Visibility, HlrError> {
let n = ctx.rays.get() + 1;
ctx.rays.set(n);
if n > ctx.max_rays {
return Err(HlrError::Budget("ray"));
}
if n.is_multiple_of(1024) && (ctx.cancel)() {
return Err(HlrError::Cancelled);
}
let own = ctx.scene.get(t.placement).ok_or(HlrError::Invalid("placement"))?;
Ok(classify_point(ctx, t.placement, &t.own, t.own_eps, own.apply(t.c3().at(x))))
}
/// Visibility of a world point on placement `placement` lying on its faces `own`.
fn classify_point(ctx: &Ctx, placement: usize, own: &[usize], own_eps: f64, world: Vec3) -> Visibility {
let screen = ctx.view.screen(world);
let depth = world.dot(ctx.view.d);
let toward = -ctx.view.d;
let mut uncertain = false;
let mut hits: Vec<Hit> = Vec::new();
for (qi, q) in ctx.scene.iter().enumerate() {
let Some((slo, shi, dmin)) = ctx.boxes.get(qi) else { continue };
let pad = ctx.eps_other;
if screen[0] < slo[0] - pad || screen[0] > shi[0] + pad || screen[1] < slo[1] - pad || screen[1] > shi[1] + pad || *dmin > depth {
continue;
}
let Some(def) = ctx.defs.get(q.body) else { continue };
let (p0, dl) = (q.local(world), q.local_dir(toward));
for (fi, f) in def.faces.iter().enumerate() {
let is_own = qi == placement && own.contains(&fi);
let Some([l0, l1]) = slab(p0, dl, f.lo, f.hi) else { continue };
let eps = if is_own { own_eps } else { ctx.eps_other };
let range = [l0.max(eps), l1];
if !(range[1] >= range[0]) {
continue;
}
ctx.surface_tests.set(ctx.surface_tests.get() + 1);
hits.clear();
f.surface.ray_as(&f.analytic, p0, dl, range, &mut hits);
for h in &hits {
let p = f.surface.point(h.uv);
let tol = 2. * f.trim.chord_error + 1e-7 * (f.hi - f.lo).len();
// A hit on the boundary is uncertain on either side of it, so the parity test is
// left out there: its cost grows with the boundary around the hit, all of a
// circle when bodies in line along the view meet each other on their circles.
if f.trim.near(p, tol) {
uncertain = true;
continue;
}
match f.trim.contains(h.uv) {
None => uncertain = true,
Some(inside) => {
// An unsupported freeform face never hides anything for certain.
let unsure = f.freeform && !ctx.freeform;
if inside && (unsure || h.grazing || (!is_own && h.lam < ctx.eps_own)) {
uncertain = true;
} else if inside {
return Visibility::Hidden;
}
}
}
}
}
}
if uncertain { Visibility::Uncertain } else { Visibility::Visible }
}
/// Phase timing where a clock exists.
struct Clock {
#[cfg(not(all(target_arch = "wasm32", target_os = "unknown")))]
last: std::cell::Cell<std::time::Instant>,
}
impl Clock {
fn start() -> Clock {
Clock {
#[cfg(not(all(target_arch = "wasm32", target_os = "unknown")))]
last: std::cell::Cell::new(std::time::Instant::now()),
}
}
fn lap(&self) -> f64 {
#[cfg(not(all(target_arch = "wasm32", target_os = "unknown")))]
{
let now = std::time::Instant::now();
let ms = now.duration_since(self.last.get()).as_secs_f64() * 1e3;
self.last.set(now);
ms
}
#[cfg(all(target_arch = "wasm32", target_os = "unknown"))]
0.
}
}
/// Ray parameter range inside an axis-aligned box.
fn slab(p: Vec3, d: Vec3, lo: Vec3, hi: Vec3) -> Option<[f64; 2]> {
let (mut t0, mut t1) = (f64::NEG_INFINITY, f64::INFINITY);
for (o, dd, a, b) in [(p.x, d.x, lo.x, hi.x), (p.y, d.y, lo.y, hi.y), (p.z, d.z, lo.z, hi.z)] {
if dd.abs() < 1e-300 {
if o < a || o > b {
return None;
}
} else {
let (x, y) = ((a - o) / dd, (b - o) / dd);
t0 = t0.max(x.min(y));
t1 = t1.min(x.max(y));
}
}
(t1 >= t0.max(0.)).then_some([t0.max(0.), t1])
}
#[cfg(test)]
#[path = "../hlr_tests.rs"]
mod tests;