surfer2 0.1.0

Headless straight-skeleton engine: a source-derived Rust port of cgalab/surfer2
Documentation
//! Endpoint keys and node union for DCEL emission.
//!
//! Arc ends are named by kinetic vertex identity (`Start` / `Stop` /
//! `TraceAt`). `TraceAt` splits the host vertex's traced ridge at the
//! landing time so a spoke shares that node — no geometric search.

use rustc_hash::FxHashMap as HashMap;

use super::sewing_map;
use crate::dcel::{Node, NodeId};
use crate::geometry::Point2;
use crate::triangulation::kinetic::{ArcEnd, ArcRecord};
use crate::triangulation::KineticTriangulation;
use crate::wavefront::vertex::VertexId;

/// Collapse a TraceAt onto Stop when the landing is this close to the ridge
/// endpoint (metres). Prevents a micro ridge piece that breaks face cycles
/// while still allowing real mid-edge TraceAt splits further from the stop.
const TRACE_AT_NEAR_STOP_EPS: f64 = 1e-3;

#[derive(Clone, Copy, PartialEq, Eq, Hash)]
pub(super) enum EndKey {
    Start(u64),
    Stop(u64),
    TraceAt { v: u64, tbits: u64 },
    Unique(u64),
}

impl EndKey {
    pub(super) fn start(v: VertexId) -> Self {
        Self::Start(slotmap_key(v))
    }
    pub(super) fn stop(v: VertexId) -> Self {
        Self::Stop(slotmap_key(v))
    }
    fn trace_at(v: VertexId, tbits: u64) -> Self {
        Self::TraceAt {
            v: slotmap_key(v),
            tbits,
        }
    }
    fn unique(tag: u64) -> Self {
        Self::Unique(tag)
    }
}

fn slotmap_key(v: VertexId) -> u64 {
    use slotmap::Key;
    v.data().as_ffi()
}

/// Union EndKeys whose positions are within `tolerance`.
///
/// Compares only spatial neighbours (cell size = tolerance). Same merge
/// predicate as the former all-pairs-in-bucket scan; bins only choose which
/// pairs are tested. Pair selection uses endpoint index order, not HashMap
/// visit order, so union topology does not depend on hasher iteration.
///
/// `tolerance` must be positive and finite (callers use footprint-extent × ε × 256).
fn union_nearby_ends(uf: &mut EndpointUf, ends: &[(EndKey, Point2)], tolerance: f64) {
    if ends.len() < 2 {
        return;
    }
    debug_assert!(tolerance > 0.0 && tolerance.is_finite());

    let inv_cell = 1.0 / tolerance;
    let cell_of = |p: Point2| -> (i64, i64) {
        (
            (p.x * inv_cell).floor() as i64,
            (p.y * inv_cell).floor() as i64,
        )
    };

    let mut bins: HashMap<(i64, i64), Vec<usize>> = sewing_map(ends.len());
    for (i, &(_, p)) in ends.iter().enumerate() {
        bins.entry(cell_of(p)).or_default().push(i);
    }

    for (i, &(key_i, p_i)) in ends.iter().enumerate() {
        let (cx, cy) = cell_of(p_i);
        for dx in -1..=1_i64 {
            for dy in -1..=1_i64 {
                let Some(js) = bins.get(&(cx + dx, cy + dy)) else {
                    continue;
                };
                for &j in js {
                    if j <= i {
                        continue;
                    }
                    if p_i.distance_to(ends[j].1) <= tolerance {
                        uf.union(key_i, ends[j].0);
                    }
                }
            }
        }
    }
}

pub(super) struct EndpointUf {
    parent: HashMap<EndKey, EndKey>,
    uniq: u64,
}

impl EndpointUf {
    pub(super) fn from_links(kt: &KineticTriangulation) -> Self {
        let n_vert = kt.vertices.len();
        let mut uf = Self {
            parent: sewing_map(n_vert.saturating_mul(4)),
            uniq: 0,
        };
        for (id, v) in &kt.vertices {
            for side in 0..2 {
                if let Some(n) = v.next_vertex[side] {
                    let nv = &kt.vertices[n];
                    if nv.prev_vertex[side] == Some(id) || nv.next_vertex[1 - side] != Some(id) {
                        uf.union(EndKey::stop(id), EndKey::start(n));
                    }
                    if nv.next_vertex[1 - side] == Some(id) {
                        uf.union(EndKey::stop(id), EndKey::stop(n));
                    }
                }
                if let Some(p) = v.prev_vertex[side] {
                    if kt.vertices[p].prev_vertex[1 - side] == Some(id) {
                        uf.union(EndKey::start(id), EndKey::start(p));
                    }
                }
            }
        }

        let extent = kt.footprint_extent();
        let tolerance = extent.max(1.0) * f64::EPSILON * 256.0;
        let mut event_ends: HashMap<u64, Vec<(EndKey, Point2)>> = sewing_map(n_vert);
        for (id, v) in &kt.vertices {
            if v.time_start.is_finite() && v.pos_start.is_finite() {
                event_ends
                    .entry(v.time_start.to_bits())
                    .or_default()
                    .push((EndKey::start(id), v.pos_start));
            }
            if let (Some(time), Some(point)) = (v.time_stop, v.pos_stop) {
                if time.is_finite() && point.is_finite() {
                    event_ends
                        .entry(time.to_bits())
                        .or_default()
                        .push((EndKey::stop(id), point));
                }
            }
        }
        // Fx hasher: bucket visit order is deterministic (not SipHash-random).
        // Union partition does not depend on which time group runs first.
        for ends in event_ends.values() {
            union_nearby_ends(&mut uf, ends, tolerance);
        }
        uf
    }

    fn find(&mut self, k: EndKey) -> EndKey {
        let p = *self.parent.entry(k).or_insert(k);
        if p != k {
            let r = self.find(p);
            self.parent.insert(k, r);
            r
        } else {
            k
        }
    }

    pub(super) fn union(&mut self, a: EndKey, b: EndKey) {
        let ra = self.find(a);
        let rb = self.find(b);
        if ra != rb {
            self.parent.insert(ra, rb);
        }
    }

    fn fresh(&mut self) -> EndKey {
        self.uniq += 1;
        EndKey::unique(self.uniq)
    }
}

pub(super) fn end_key(end: ArcEnd) -> EndKey {
    match end {
        ArcEnd::Start(v) => EndKey::start(v),
        ArcEnd::Stop(v) => EndKey::stop(v),
        ArcEnd::TraceAt { vertex, time_bits } => EndKey::trace_at(vertex, time_bits),
    }
}

pub(super) fn arc_keys(arc: &ArcRecord) -> (EndKey, EndKey) {
    (
        end_key(arc.start_end),
        match arc.end_end {
            Some(e) => end_key(e),
            None => EndKey::unique(0),
        },
    )
}

pub(super) fn ensure_node(
    uf: &mut EndpointUf,
    nodes: &mut Vec<Node>,
    root_node: &mut HashMap<EndKey, u32>,
    key: EndKey,
    p: Point2,
    time: f64,
) -> NodeId {
    let key = if matches!(key, EndKey::Unique(0)) {
        uf.fresh()
    } else {
        key
    };
    let r = uf.find(key);
    if let Some(&i) = root_node.get(&r) {
        return NodeId(i);
    }
    let id = nodes.len() as u32;
    nodes.push(Node {
        point: Some(p),
        time,
        is_infinite: false,
    });
    root_node.insert(r, id);
    NodeId(id)
}

/// Split traced ridges through every `TraceAt` landing on the same vertex.
/// Also returns identity unions for omitted zero-length pieces (same vertex).
pub(super) fn expand_arcs(arcs: &[ArcRecord]) -> (Vec<ArcRecord>, Vec<(EndKey, EndKey)>) {
    let mut hits: HashMap<u64, Vec<(u64, Point2)>> = sewing_map(arcs.len());
    for a in arcs {
        if let Some(ArcEnd::TraceAt { vertex, time_bits }) = a.end_end {
            if let Some(p) = a.end {
                hits.entry(slotmap_key(vertex))
                    .or_default()
                    .push((time_bits, p));
            }
        }
    }
    for list in hits.values_mut() {
        list.sort_by(|(a, _), (b, _)| f64::from_bits(*a).total_cmp(&f64::from_bits(*b)));
        list.dedup_by_key(|(t, _)| *t);
    }

    let mut out = Vec::with_capacity(arcs.len());
    let mut unions = Vec::new();
    for a in arcs {
        if let Some(v) = a.traced_vertex() {
            if let Some(hs) = hits.get(&slotmap_key(v)) {
                if !hs.is_empty() {
                    let (pieces, u) = split_traced(a, v, hs);
                    out.extend(pieces);
                    unions.extend(u);
                    continue;
                }
            }
        }
        out.push(a.clone());
    }
    (out, unions)
}

fn split_traced(
    arc: &ArcRecord,
    v: VertexId,
    hits: &[(u64, Point2)],
) -> (Vec<ArcRecord>, Vec<(EndKey, EndKey)>) {
    let t0 = arc.start_time;
    let t0b = t0.to_bits();
    let mut pts: Vec<(ArcEnd, f64, Point2)> = vec![(ArcEnd::Start(v), t0, arc.start)];

    match (arc.end, arc.end_time) {
        (Some(end), Some(et)) => {
            let etb = et.to_bits();
            let mut extra = Vec::new();
            for &(tb, p) in hits {
                let t = f64::from_bits(tb);
                if tb == t0b {
                    extra.push((
                        end_key(ArcEnd::TraceAt {
                            vertex: v,
                            time_bits: tb,
                        }),
                        EndKey::start(v),
                    ));
                    continue;
                }
                if tb == etb {
                    extra.push((
                        end_key(ArcEnd::TraceAt {
                            vertex: v,
                            time_bits: tb,
                        }),
                        EndKey::stop(v),
                    ));
                    continue;
                }
                // Near-degenerate TraceAt just before Stop: share the stop
                // node instead of emitting a micro ridge piece. Real mid-edge
                // landings stay metres from the endpoint on GIS inputs.
                if t > t0 && t < et && p.distance_to(end) <= TRACE_AT_NEAR_STOP_EPS {
                    extra.push((
                        end_key(ArcEnd::TraceAt {
                            vertex: v,
                            time_bits: tb,
                        }),
                        EndKey::stop(v),
                    ));
                    continue;
                }
                if t > t0 && t < et {
                    pts.push((
                        ArcEnd::TraceAt {
                            vertex: v,
                            time_bits: tb,
                        },
                        t,
                        p,
                    ));
                }
            }
            pts.push((ArcEnd::Stop(v), et, end));
            let (pieces, u) = pieces_between(arc, &pts);
            extra.extend(u);
            (pieces, extra)
        }
        _ => {
            for &(tb, p) in hits {
                let t = f64::from_bits(tb);
                if tb == t0b || t <= t0 {
                    continue;
                }
                pts.push((
                    ArcEnd::TraceAt {
                        vertex: v,
                        time_bits: tb,
                    },
                    t,
                    p,
                ));
            }
            if pts.len() == 1 {
                return (vec![arc.clone()], Vec::new());
            }
            let (mut out, unions) = pieces_between(arc, &pts);
            if let Some(&(id, t, p)) = pts.last() {
                let mut ray = arc.clone();
                ray.start = p;
                ray.end = None;
                ray.start_time = t;
                ray.end_time = None;
                ray.start_end = id;
                ray.end_end = None;
                out.push(ray);
            }
            if out.is_empty() {
                (vec![arc.clone()], unions)
            } else {
                (out, unions)
            }
        }
    }
}

fn pieces_between(
    arc: &ArcRecord,
    pts: &[(ArcEnd, f64, Point2)],
) -> (Vec<ArcRecord>, Vec<(EndKey, EndKey)>) {
    let mut out = Vec::new();
    let mut unions = Vec::new();
    for w in pts.windows(2) {
        let (id0, t0, p0) = w[0];
        let (id1, t1, p1) = w[1];
        if !(p0.distance_to(p1) > 0.0) {
            unions.push((end_key(id0), end_key(id1)));
            continue;
        }
        let mut piece = arc.clone();
        piece.start = p0;
        piece.end = Some(p1);
        piece.start_time = t0;
        piece.end_time = Some(t1);
        piece.start_end = id0;
        piece.end_end = Some(id1);
        out.push(piece);
    }
    if out.is_empty() && pts.len() <= 2 {
        (vec![arc.clone()], unions)
    } else {
        (out, unions)
    }
}