Skip to content

SolidCraft: an open-source parametric 3D CAD application built in pure Rust. Desktop, web, and automation through MCP.

14.6 KB
Raw Blame
//! Faces on a closed surface whose boundary winds around it: a cylinder face bounded by two
//! circles and no seam edge, or one trimmed by a helix that turns several times (a modelled
//! thread, as other CAD systems write them to STEP). In the surface's unwrapped parameters such
//! a face repeats every period, and its loops do not close. It is cut along a parameter line
//! (the seam it never had) into one period: every loop, and every copy of it a whole number of
//! periods along, is clipped to the strip between the line and its next copy, and the parts of
//! the two lines inside the face join the pieces into closed loops. Both lines are one curve
//! on the surface, so their nodes are made once and shared: the face stays closed across it.

use solidcore_record::Vec3;
use solidcraft_geom::tess::EvalSurface;

use super::size::Rules;

/// One loop of a face: parameters (unwrapped along the loop) and the 3D node each stands for.
#[derive(Clone, Debug, Default)]
pub(crate) struct Loop {
    pub uv: Vec<[f64; 2]>,
    pub pts: Vec<Vec3>,
}

/// Most loop copies one face may be clipped into (a helix of this many turns).
const MAX_COPIES: i64 = 2048;
/// Most nodes a cut line may get between two crossings.
const MAX_SEAM_NODES: usize = 4096;

/// How far `l` drifts along `d` going once around it (a whole number of periods for a closed
/// loop: zero unless it winds around the surface).
pub(crate) fn drift(l: &Loop, d: usize, per: f64) -> f64 {
    let (Some(first), Some(last)) = (l.uv.first(), l.uv.last()) else { return 0.0 };
    let close = super::uv::unwrap(first[d], last[d], Some(per)) - last[d];
    last[d] - first[d] + close
}

/// Whether any loop winds around the closed direction `d`.
pub(crate) fn winds(loops: &[Loop], d: usize, per: f64) -> bool {
    loops.iter().any(|l| drift(l, d, per).abs() > per * 0.5)
}

/// A point where the boundary crosses a cut line: its place along the line, its 3D point, and
/// whether the face lies above it (towards larger parameters across the line) or below.
#[derive(Clone, Copy, Debug)]
struct Crossing {
    y: f64,
    p: Vec3,
    above: bool,
}

/// A boundary run across the strip: it enters through one cut line and leaves through one.
struct Piece {
    uv: Vec<[f64; 2]>,
    pts: Vec<Vec3>,
}

/// Cut a face whose loops wind around direction `d` (period `per`) into one period. The face
/// lies left of its loops in (u, v). `None` when the loops cannot be cut cleanly (the face would
/// be unbounded along the line, or the two lines disagree); the caller then fails as before.
pub(crate) fn cut(s: &EvalSurface, loops: &[Loop], d: usize, per: f64, rules: &Rules, h: f64) -> Option<Vec<Loop>> {
    if !(per > 0.0 && per.is_finite()) || loops.is_empty() {
        return None;
    }
    // Work in (x, y) with x along the closed direction; swapping (u, v) mirrors the plane, so the
    // loops are reversed to keep the face on their left.
    let swap = d == 1;
    let local: Vec<Loop> = loops
        .iter()
        .map(|l| {
            let mut uv: Vec<[f64; 2]> = l.uv.iter().map(|q| if swap { [q[1], q[0]] } else { *q }).collect();
            let mut pts = l.pts.clone();
            if swap {
                uv.reverse();
                pts.reverse();
            }
            Loop { uv, pts }
        })
        .collect();
    let x0 = cut_position(&local, per)?;
    let x1 = x0 + per;
    let mut closed: Vec<Loop> = Vec::new();
    let mut pieces: Vec<Piece> = Vec::new();
    for l in &local {
        let n = l.uv.len();
        if n < 2 || l.pts.len() != n {
            return None;
        }
        let w = drift(l, 0, per);
        let (lo, hi) = l.uv.iter().fold((f64::MAX, f64::MIN), |(a, b), q| (a.min(q[0]), b.max(q[0])));
        if !(lo.is_finite() && hi.is_finite()) {
            return None;
        }
        if w.abs() <= per * 0.5 {
            // A closed loop: each copy along x that reaches into the strip.
            let k0 = ((x0 - hi) / per).floor() as i64;
            let k1 = ((x1 - lo) / per).ceil() as i64;
            if k1 - k0 > MAX_COPIES {
                return None;
            }
            for k in k0..=k1 {
                let shift = per * k as f64;
                let uv: Vec<[f64; 2]> = l.uv.iter().map(|q| [q[0] + shift, q[1]]).collect();
                if uv.iter().all(|q| q[0] > x0 && q[0] < x1) {
                    closed.push(Loop { uv, pts: l.pts.clone() });
                } else if uv.iter().any(|q| q[0] > x0 && q[0] < x1) || crosses(&uv, x0, x1) {
                    // Start at a node outside the strip, so every run inside is whole.
                    let start = uv.iter().position(|q| !(q[0] > x0 && q[0] < x1))?;
                    let idx: Vec<usize> = (0..=n).map(|i| (start + i) % n).collect();
                    let path: Vec<[f64; 2]> = idx.iter().filter_map(|&i| uv.get(i).copied()).collect();
                    let pts: Vec<Vec3> = idx.iter().filter_map(|&i| l.pts.get(i).copied()).collect();
                    clip(&path, &pts, x0, x1, &mut pieces);
                }
            }
        } else {
            // A loop winding around: the endless path it repeats along, over enough turns to
            // start and end outside the strip.
            let turns = (w / per).round();
            if turns.abs() != 1.0 {
                return None;
            }
            let reach = (hi - lo) / per;
            let span = (reach.ceil() as i64) + 2;
            if span > MAX_COPIES {
                return None;
            }
            // Copies j with lo + j·w ≤ x1 and hi + j·w ≥ x0, plus one each side.
            let (ja, jb) = if w > 0.0 {
                (((x0 - hi) / w).floor() as i64 - 1, ((x1 - lo) / w).ceil() as i64 + 1)
            } else {
                (((x1 - lo) / w).floor() as i64 - 1, ((x0 - hi) / w).ceil() as i64 + 1)
            };
            if jb - ja > MAX_COPIES {
                return None;
            }
            let mut path = Vec::new();
            let mut pts = Vec::new();
            for j in ja..=jb {
                let shift = w * j as f64;
                path.extend(l.uv.iter().map(|q| [q[0] + shift, q[1]]));
                pts.extend(l.pts.iter().copied());
            }
            let (Some(a), Some(b)) = (path.first(), path.last()) else { return None };
            if (a[0] > x0 && a[0] < x1) || (b[0] > x0 && b[0] < x1) {
                return None;
            }
            clip(&path, &pts, x0, x1, &mut pieces);
        }
    }
    // The crossings on each line, sorted along it; both lines must see the same ones.
    let mut left: Vec<(Crossing, usize, bool)> = Vec::new();
    let mut right: Vec<(Crossing, usize, bool)> = Vec::new();
    for (i, p) in pieces.iter().enumerate() {
        let (Some(a), Some(b), Some(pa), Some(pb)) = (p.uv.first(), p.uv.last(), p.pts.first(), p.pts.last()) else { return None };
        // Entering through the left line (moving +x): the face is above; through the right
        // line (moving −x): below. Leaving through the left (−x): below; the right (+x): above.
        let enter = Crossing { y: a[1], p: *pa, above: a[0] == x0 };
        let leave = Crossing { y: b[1], p: *pb, above: b[0] == x1 };
        if a[0] == x0 {
            left.push((enter, i, true))
        } else {
            right.push((enter, i, true))
        }
        if b[0] == x0 { left.push((leave, i, false)) } else { right.push((leave, i, false)) }
    }
    left.sort_by(|a, b| a.0.y.total_cmp(&b.0.y));
    right.sort_by(|a, b| a.0.y.total_cmp(&b.0.y));
    if left.len() != right.len() || !left.len().is_multiple_of(2) {
        return None;
    }
    let scale = loops.iter().flat_map(|l| l.uv.iter()).fold(1.0f64, |m, q| m.max(q[0].abs()).max(q[1].abs()));
    for (a, b) in left.iter().zip(&right) {
        if a.0.above != b.0.above || (a.0.y - b.0.y).abs() > 1e-7 * scale {
            return None;
        }
    }
    // The same crossing on both lines is one point.
    for (a, b) in left.clone().iter().zip(right.iter_mut()) {
        b.0.y = a.0.y;
        b.0.p = a.0.p;
    }
    for (c, i, start) in left.iter().chain(&right) {
        let p = pieces.get_mut(*i)?;
        let k = if *start { 0 } else { p.uv.len().checked_sub(1)? };
        if let (Some(q), Some(pt)) = (p.uv.get_mut(k), p.pts.get_mut(k)) {
            q[1] = c.y;
            *pt = c.p;
        }
    }
    // Inside the face along each line: from a crossing with the face above to the next one
    // up (which must have it below).
    let mut links: Vec<(usize, Vec<[f64; 2]>, Vec<Vec3>, usize)> = Vec::new();
    for pair in left.chunks(2).zip(right.chunks(2)) {
        let (lp, rp) = pair;
        let (Some(la), Some(lb), Some(ra), Some(rb)) = (lp.first(), lp.get(1), rp.first(), rp.get(1)) else { return None };
        if !(la.0.above && !lb.0.above) {
            return None;
        }
        // Nodes strictly between, made once for both lines.
        let inner = seam_nodes(s, swap, x0, la.0.y, lb.0.y, rules, h)?;
        // Left line, downwards: from the piece leaving at the top to the one entering at the bottom.
        let (top_leave, bottom_enter) = (lb.1, la.1);
        let down_uv: Vec<[f64; 2]> = inner.iter().rev().map(|(y, _)| [x0, *y]).collect();
        let down_pts: Vec<Vec3> = inner.iter().rev().map(|(_, p)| *p).collect();
        if lb.2 || !la.2 {
            return None;
        }
        links.push((top_leave, down_uv, down_pts, bottom_enter));
        // Right line, upwards: from the piece leaving at the bottom to the one entering at the top.
        if ra.2 || !rb.2 {
            return None;
        }
        let up_uv: Vec<[f64; 2]> = inner.iter().map(|(y, _)| [x1, *y]).collect();
        let up_pts: Vec<Vec3> = inner.iter().map(|(_, p)| *p).collect();
        links.push((ra.1, up_uv, up_pts, rb.1));
    }
    // Chain pieces through the links into closed loops.
    let mut next: Vec<Option<usize>> = vec![None; pieces.len()];
    let mut via: Vec<Option<usize>> = vec![None; pieces.len()];
    for (li, (from, _, _, to)) in links.iter().enumerate() {
        if next.get(*from).copied().flatten().is_some() {
            return None;
        }
        *next.get_mut(*from)? = Some(*to);
        *via.get_mut(*from)? = Some(li);
    }
    let mut used = vec![false; pieces.len()];
    for start in 0..pieces.len() {
        if used.get(start).copied().unwrap_or(true) {
            continue;
        }
        let mut out = Loop::default();
        let mut at = start;
        for _ in 0..=pieces.len() {
            if *used.get(at)? {
                break;
            }
            *used.get_mut(at)? = true;
            let p = pieces.get(at)?;
            out.uv.extend(&p.uv);
            out.pts.extend(&p.pts);
            let (_, luv, lpts, _) = links.get((*via.get(at)?)?)?;
            out.uv.extend(luv);
            out.pts.extend(lpts);
            at = (*next.get(at)?)?;
        }
        if at != start {
            return None;
        }
        closed.push(out);
    }
    // Back to (u, v).
    let out: Vec<Loop> = closed
        .into_iter()
        .map(|mut l| {
            if swap {
                l.uv = l.uv.iter().rev().map(|q| [q[1], q[0]]).collect();
                l.pts.reverse();
            }
            l
        })
        .collect();
    // The face must come out with positive area (left of its loops).
    let area: f64 = out
        .iter()
        .map(|l| {
            let n = l.uv.len();
            (0..n)
                .map(|i| {
                    let (a, b) = (l.uv[i], l.uv[(i + 1) % n]);
                    a[0] * b[1] - b[0] * a[1]
                })
                .sum::<f64>()
        })
        .sum();
    (area > 0.0).then_some(out)
}

/// Where to cut: the middle of the widest gap between the loops' nodes around the period, as
/// far from any node as can be.
fn cut_position(loops: &[Loop], per: f64) -> Option<f64> {
    let mut xs: Vec<f64> = loops.iter().flat_map(|l| l.uv.iter().map(|q| q[0].rem_euclid(per))).collect();
    if xs.is_empty() {
        return None;
    }
    xs.sort_by(f64::total_cmp);
    let mut best = (0.0, f64::NEG_INFINITY);
    for (i, x) in xs.iter().enumerate() {
        let next = xs.get(i + 1).copied().unwrap_or(xs[0] + per);
        if next - x > best.1 {
            best = (0.5 * (x + next), next - x);
        }
    }
    (best.1 > 0.0).then_some(best.0)
}

/// Whether a path jumps over the strip in one segment.
fn crosses(uv: &[[f64; 2]], x0: f64, x1: f64) -> bool {
    uv.windows(2).any(|w| (w[0][0] <= x0 && w[1][0] >= x1) || (w[1][0] <= x0 && w[0][0] >= x1))
}

/// The runs of an open path (starting and ending outside the strip) inside the strip, each
/// from the point where it enters to the one where it leaves. The crossing points lie on the
/// boundary's own straight 3D segments, so the neighbouring face's edge passes through them.
fn clip(path: &[[f64; 2]], pts: &[Vec3], x0: f64, x1: f64, out: &mut Vec<Piece>) {
    let inside = |q: &[f64; 2]| q[0] > x0 && q[0] < x1;
    let mut cur: Option<Piece> = None;
    for ((a, b), (pa, pb)) in path.iter().zip(path.iter().skip(1)).zip(pts.iter().zip(pts.iter().skip(1))) {
        let at = |x: f64| {
            let t = ((x - a[0]) / (b[0] - a[0])).clamp(0.0, 1.0);
            ([x, a[1] + (b[1] - a[1]) * t], *pa + (*pb - *pa) * t)
        };
        // Lines crossed by this segment, in order along it.
        let mut hits: Vec<f64> = [x0, x1].into_iter().filter(|x| (a[0] - x) * (b[0] - x) < 0.0).collect();
        if b[0] < a[0] {
            hits.reverse();
        }
        for x in hits {
            let (q, p) = at(x);
            match cur.take() {
                Some(mut piece) => {
                    piece.uv.push(q);
                    piece.pts.push(p);
                    out.push(piece);
                }
                None => cur = Some(Piece { uv: vec![q], pts: vec![p] }),
            }
        }
        if inside(b)
            && let Some(piece) = cur.as_mut()
        {
            piece.uv.push(*b);
            piece.pts.push(*pb);
        }
    }
}

/// Nodes along the cut line between two crossings (`y0` < `y1`, ends excluded): within the
/// tolerance, the side length and the facet angle of the surface along the line.
fn seam_nodes(s: &EvalSurface, swap: bool, x: f64, y0: f64, y1: f64, rules: &Rules, h: f64) -> Option<Vec<(f64, Vec3)>> {
    let uv = |y: f64| if swap { [y, x] } else { [x, y] };
    let mut ys = vec![y0, y1];
    let mut i = 0;
    while i + 1 < ys.len() {
        let (a, b) = (ys[i], ys[i + 1]);
        if ys.len() < MAX_SEAM_NODES && !super::uv::fine_between(s, rules, h, uv(a), uv(b)) && b - a > 1e-12 * (1.0 + a.abs()) {
            ys.insert(i + 1, 0.5 * (a + b));
        } else {
            i += 1;
        }
    }
    let inner = ys.get(1..ys.len() - 1)?;
    Some(inner.iter().map(|&y| (y, s.eval(uv(y)[0], uv(y)[1]).0)).collect())
}