SolidCraft: an open-source parametric 3D CAD application built in pure Rust. Desktop, web, and automation through MCP.
//! Where a face's sampled boundary crosses itself: chords of its loops, in the face's
//! parameters, that cross another chord of the face although the curves they stand for do not
//! (two curves running closer together than their chords sag).
use solidcraft_geom::tess::EvalSurface;
use super::seam;
use super::uv;
/// Two chords cross only where each one's ends lie strictly either side of the other, by more
/// than this fraction of the product of their lengths (a chord ending on another, as at a
/// shared vertex or along a seam's two uses a period apart, is not a crossing).
const STRADDLE: f64 = 1e-10;
/// One chord of a loop, or a copy of it whole periods along.
struct Chord {
/// The chord's place in the face: its loop and its first node.
at: (usize, usize),
a: [f64; 2],
b: [f64; 2],
}
impl Chord {
fn lo(&self, d: usize) -> f64 {
self.a[d].min(self.b[d])
}
fn hi(&self, d: usize) -> f64 {
self.a[d].max(self.b[d])
}
}
/// The chords (loop, first node) of `loops` that cross another chord of the face, in its loop or
/// another, each once and in order. On a closed surface the boundary crosses itself where any
/// copies of two chords, whole periods apart, cross; chords ending on a pole, where the
/// parameter along the pole is free, are left out. Adjacent chords of a loop share a node and
/// never cross. `reach`: how near a pole a node is taken as one (see [`uv::degenerate_within`]).
pub(crate) fn crossing(s: &EvalSurface, reach: f64, loops: &[seam::Loop]) -> Vec<(usize, usize)> {
let dom = uv::domain(s);
let pole = |q: [f64; 2]| (0..2).any(|d| uv::degenerate_within(s, &dom, q, d, reach));
let mut chords: Vec<Chord> = Vec::new();
for (li, l) in loops.iter().enumerate() {
let n = l.uv.len();
if n < 3 {
continue;
}
for k in 0..n {
let (Some(&a), Some(&b)) = (l.uv.get(k), l.uv.get((k + 1) % n)) else { continue };
if !(a.iter().chain(&b).all(|x| x.is_finite())) || pole(a) || pole(b) {
continue;
}
// The loop's closing chord of a loop that winds round the surface ends at the copy of
// its first node nearest its last; every chord then starts in one period.
let (mut a, mut b) = (a, b);
for d in 0..2 {
let Some(per) = dom.period[d] else { continue };
b[d] = uv::unwrap(b[d], a[d], Some(per));
let back = (a[d].min(b[d]) / per).floor() * per;
a[d] -= back;
b[d] -= back;
}
chords.push(Chord { at: (li, k), a, b });
}
}
// With every chord starting in one period, two chords' copies can only cross where one of
// them is moved a period along at most: each chord also as its copies a period along.
for d in 0..2 {
let Some(per) = dom.period[d] else { continue };
let along: Vec<Chord> = chords
.iter()
.map(|c| {
let (mut a, mut b) = (c.a, c.b);
a[d] += per;
b[d] += per;
Chord { at: c.at, a, b }
})
.collect();
chords.extend(along);
}
let adjacent = |p: (usize, usize), q: (usize, usize)| {
let n = loops.get(p.0).map_or(0, |l| l.uv.len());
p == q || (p.0 == q.0 && ((p.1 + 1) % n == q.1 || (q.1 + 1) % n == p.1))
};
// Sweep along u: only chords whose u ranges overlap can cross.
chords.sort_by(|x, y| x.lo(0).total_cmp(&y.lo(0)));
let mut out: Vec<(usize, usize)> = Vec::new();
for (i, x) in chords.iter().enumerate() {
for y in chords.iter().skip(i + 1) {
if y.lo(0) > x.hi(0) {
break;
}
if y.lo(1) > x.hi(1) || x.lo(1) > y.hi(1) || adjacent(x.at, y.at) {
continue;
}
if cross(x.a, x.b, y.a, y.b) {
out.push(x.at);
out.push(y.at);
}
// A node of one chord lying on the other (inside it, not at its ends) is no crossing,
// but no triangulation can keep both as constraints either: where two curves leave a
// vertex they touch at along one tangent (a circle touching another from inside), the
// inner one's node can fall on the outer one's chord (with the outer chord twice the
// inner, exactly so but for the next order). The chord the node lies on is halved.
// (Not where the two chords run along one line: a seam's two uses, a period apart,
// lie on each other as copies.)
if !along(x.a, x.b, y.a, y.b) && [y.a, y.b].iter().any(|q| on(x.a, x.b, *q)) {
out.push(x.at);
}
if !along(y.a, y.b, x.a, x.b) && [x.a, x.b].iter().any(|q| on(y.a, y.b, *q)) {
out.push(y.at);
}
}
}
out.sort_unstable();
out.dedup();
out
}
/// Whether `q` lies on the segment `ab` within [`STRADDLE`] (of the segment's squared length,
/// off its line) strictly between its ends (not at either, by the same measure along it).
fn on(a: [f64; 2], b: [f64; 2], q: [f64; 2]) -> bool {
let (dx, dy) = (b[0] - a[0], b[1] - a[1]);
let len2 = dx * dx + dy * dy;
if !(len2 > 0.0) {
return false;
}
let (qx, qy) = (q[0] - a[0], q[1] - a[1]);
let off = (dx * qy - dy * qx).abs();
let along = (dx * qx + dy * qy) / len2;
off <= 1e3 * STRADDLE * len2 && along > 1e-6 && along < 1.0 - 1e-6
}
/// Whether `c` and `d` both lie on the line of `ab` (within [`on`]'s measure).
fn along(a: [f64; 2], b: [f64; 2], c: [f64; 2], d: [f64; 2]) -> bool {
let (dx, dy) = (b[0] - a[0], b[1] - a[1]);
let len2 = dx * dx + dy * dy;
let off = |q: [f64; 2]| (dx * (q[1] - a[1]) - dy * (q[0] - a[0])).abs();
len2 > 0.0 && off(c) <= 1e3 * STRADDLE * len2 && off(d) <= 1e3 * STRADDLE * len2
}
/// Whether the segments `ab` and `cd` cross: each one's ends strictly either side of the other.
fn cross(a: [f64; 2], b: [f64; 2], c: [f64; 2], d: [f64; 2]) -> bool {
let orient = |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]);
let len = |p: [f64; 2], q: [f64; 2]| (q[0] - p[0]).hypot(q[1] - p[1]);
let eps = STRADDLE * len(a, b) * len(c, d);
let side = |o: f64| {
if o > eps {
1
} else if o < -eps {
-1
} else {
0
}
};
let (s1, s2, s3, s4) = (side(orient(a, b, c)), side(orient(a, b, d)), side(orient(c, d, a)), side(orient(c, d, b)));
s1 * s2 < 0 && s3 * s4 < 0
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn crossing_chords_are_found_and_touching_ones_are_not() {
assert!(cross([0.0, 0.0], [2.0, 2.0], [0.0, 2.0], [2.0, 0.0]));
// Ending on the other, sharing an end, collinear: no crossing.
assert!(!cross([0.0, 0.0], [2.0, 0.0], [1.0, 0.0], [1.0, 1.0]));
assert!(!cross([0.0, 0.0], [2.0, 0.0], [2.0, 0.0], [3.0, 1.0]));
assert!(!cross([0.0, 0.0], [2.0, 0.0], [1.0, 0.0], [3.0, 0.0]));
}
}