BREP_render 0.4.0

//! Insert spline anchors by de Casteljau subdivision without changing the curve.
//!
//! Sketch splines are chained cubic Béziers with `3n + 1` point IDs and anchors
//! at indices 0, 3, 6, … . Splitting `P0 P1 P2 P3` at parameter `t` gives:
//!
//! ```text
//! A = lerp(P0,P1,t)  B = lerp(P1,P2,t)  C = lerp(P2,P3,t)
//! D = lerp(A,B,t)    E = lerp(B,C,t)    S = lerp(D,E,t)
//! ```
//!
//! The resulting polygon `P0, A, D, S, E, C, P3` preserves the `3n + 1` invariant.
//! `P0` and `P3` keep their IDs; `P1` and `P2` are reused for `A` and `C` so their
//! constraints survive. Their endpoint tangent directions are unchanged. Only
//! `D`, `S`, and `E` receive new IDs.
//!
//! The new anchor and its handles are collinear (`S = lerp(D,E,t)`), satisfying
//! the solver's implicit G1 join constraint before the next solve.

use serde_json::Value;

use super::doc::{id_key, SketchDoc, SketchPoint};

/// Per-span sampling resolution used to locate the click along a spline — the same
/// 64 the overlay tessellator draws a span with, so "where the curve looks like it
/// is" and "where the click lands on it" agree. The chord projection inside each
/// sample interval recovers the parameter to far better than the sample spacing.
const SPAN_SAMPLES: usize = 64;

/// Refuse a subdivision within this much of either end of the clicked SPAN (in that
/// span's own `0..1` parameter). Splitting at the very end mints a zero-length span,
/// which is a degenerate control polygon, not a refinement. In practice the
/// point-priority rule in [`insert_anchor`] catches these clicks first — an anchor is
/// a point, and points win the pick — so this is the backstop for the sliver between
/// the two radii.
const MIN_SPAN_PARAM: f64 = 1e-3;

/// Whether `geom_type` names a spline. Mirrors the kernel solver's
/// `is_spline_geometry_type`: `"bezier"` is what the tools author, `"spline"` is the
/// accepted alias. Defined here rather than imported because the sketch module is
/// deliberately kernel-free.
pub fn is_spline_type(geom_type: &str) -> bool {
    geom_type == "bezier" || geom_type == "spline"
}

/// The ids [`insert_anchor`] minted: the new on-curve `anchor` and the two off-curve
/// handles flanking it (`before` precedes it in the polygon, `after` follows it). The
/// caller decides what to hang on them — the tool draws each anchor's handle guides.
#[derive(Clone, Debug)]
pub struct InsertedAnchor {
    /// The new on-curve anchor (`S`).
    pub anchor: Value,
    /// The handle immediately BEFORE the anchor (`D`) — it ends the first half-span.
    pub before: Value,
    /// The handle immediately AFTER the anchor (`E`) — it starts the second half-span.
    pub after: Value,
}

/// Insert an anchor into the spline under the plane click `(u, v)`, or `None` when
/// the click should mean something else. Shape-preserving: the curve through the
/// grown control polygon is the curve that was there before.
///
/// The picking rules, in order:
/// * A POINT within `radius` wins — the whole sketcher gives points priority over
///   geometry, and a click on an anchor or handle would split at a span end anyway.
/// * Otherwise the nearest SPLINE within `radius` is the target. Only splines are
///   candidates, deliberately: the bezier tool hangs a dashed construction guide off
///   each end handle, and on a shallow spline (near-collinear handles) those guides
///   hug the curve along its whole length. Ranking all geometry together would let a
///   spline's own guides shadow it and make the very splines a user most wants to
///   refine the ones that cannot be refined.
/// * The clicked span must have four DISTINCT ids and the click must land clear of
///   the span's ends ([`MIN_SPAN_PARAM`]) — a cusp built by repeating an id cannot be
///   subdivided without corrupting the other role, and a split at a span end is
///   degenerate.
///
/// Does NOT solve, refresh or record undo — the engine wrapper owns that.
pub fn insert_anchor(doc: &mut SketchDoc, u: f64, v: f64, radius: f64) -> Option<InsertedAnchor> {
    // Points win the pick, exactly as they do for hover, select, drag and trim — the
    // sketcher has ONE priority rule and a spline click does not get to break it.
    if doc
        .points
        .iter()
        .any(|p| (p.x - u).hypot(p.y - v) <= radius)
    {
        return None;
    }

    let (geo_id, span, t) = nearest_spline_span(doc, u, v, radius)?;
    if !(MIN_SPAN_PARAM..=1.0 - MIN_SPAN_PARAM).contains(&t) {
        return None;
    }

    // Resolve the clicked span's four ids + coordinates BEFORE any mutation: the
    // splice below shifts every id after the split point.
    let ids = {
        let geo = doc.geometry(&geo_id)?;
        let i0 = span * 3;
        [
            geo.points.get(i0)?.clone(),
            geo.points.get(i0 + 1)?.clone(),
            geo.points.get(i0 + 2)?.clone(),
            geo.points.get(i0 + 3)?.clone(),
        ]
    };
    let keys: Vec<String> = ids.iter().map(id_key).collect();
    for i in 0..keys.len() {
        for j in (i + 1)..keys.len() {
            if keys[i] == keys[j] {
                return None; // a repeated id plays two roles — subdividing would corrupt one.
            }
        }
    }
    let controls = span_controls(doc, &ids)?;

    // de Casteljau at `t` — the two halves' control polygons.
    let [p0, p1, p2, p3] = controls;
    let a = lerp(p0, p1, t);
    let b = lerp(p1, p2, t);
    let c = lerp(p2, p3, t);
    let d = lerp(a, b, t);
    let e = lerp(b, c, t);
    let s = lerp(d, e, t);

    // The old handles slide inward onto the new half-spans' outer handles, keeping
    // their ids (and everything constrained to them) attached to the same curve ends.
    // Both resolved a moment ago through `span_controls`, so neither move can miss.
    move_point(doc, &ids[1], a)?;
    move_point(doc, &ids[2], c)?;
    // Minted in polygon order so the ids read left-to-right along the curve.
    let d_id = add_point(doc, d);
    let s_id = add_point(doc, s);
    let e_id = add_point(doc, e);

    // `P0 A | P3` → `P0 A D S E C P3`: the three new ids go between the two reused
    // handles, i.e. right after slot `i0 + 1`.
    let geo = doc.geometry_mut(&geo_id)?;
    let at = span * 3 + 2;
    geo.points
        .splice(at..at, [d_id.clone(), s_id.clone(), e_id.clone()]);

    Some(InsertedAnchor { anchor: s_id, before: d_id, after: e_id })
}

/// The `(geometry id, span index, span parameter)` of the point nearest `(u, v)` over
/// every spline in `doc`, or `None` when none passes within `radius`. Splines whose
/// control count violates `3n + 1` are skipped — they are corrupt, not pickable.
fn nearest_spline_span(doc: &SketchDoc, u: f64, v: f64, radius: f64) -> Option<(Value, usize, f64)> {
    let mut best: Option<(f64, Value, usize, f64)> = None;
    for geo in &doc.geometries {
        if !is_spline_type(&geo.geom_type) {
            continue;
        }
        let ids = &geo.points;
        if ids.len() < 4 || (ids.len() - 1) % 3 != 0 {
            continue;
        }
        for span in 0..(ids.len() - 1) / 3 {
            let i0 = span * 3;
            let Some(controls) = span_controls(
                doc,
                &[
                    ids[i0].clone(),
                    ids[i0 + 1].clone(),
                    ids[i0 + 2].clone(),
                    ids[i0 + 3].clone(),
                ],
            ) else {
                continue;
            };
            let (dist, t) = closest_on_span(&controls, u, v);
            if dist <= radius && best.as_ref().map_or(true, |(bd, ..)| dist < *bd) {
                best = Some((dist, geo.id.clone(), span, t));
            }
        }
    }
    best.map(|(_, id, span, t)| (id, span, t))
}

/// The `(distance, parameter)` of the point on one cubic span nearest `(u, v)`.
/// Sampled at [`SPAN_SAMPLES`] chords, then the click is projected onto the winning
/// chord — the same sampled-polyline treatment trim gives a curve, and accurate to
/// the chord's sagitta (well under a pixel at overlay resolution).
fn closest_on_span(controls: &[[f64; 2]; 4], u: f64, v: f64) -> (f64, f64) {
    let mut prev = eval_cubic(controls, 0.0);
    let mut best = ((u - prev[0]).hypot(v - prev[1]), 0.0);
    for i in 1..=SPAN_SAMPLES {
        let t1 = i as f64 / SPAN_SAMPLES as f64;
        let next = eval_cubic(controls, t1);
        let (dx, dy) = (next[0] - prev[0], next[1] - prev[1]);
        let len2 = (dx * dx + dy * dy).max(1e-24);
        let s = (((u - prev[0]) * dx + (v - prev[1]) * dy) / len2).clamp(0.0, 1.0);
        let dist = (u - (prev[0] + dx * s)).hypot(v - (prev[1] + dy * s));
        if dist < best.0 {
            let t0 = (i - 1) as f64 / SPAN_SAMPLES as f64;
            best = (dist, t0 + (t1 - t0) * s);
        }
        prev = next;
    }
    best
}

/// Evaluate the cubic Bernstein sum over one span's four control points.
fn eval_cubic(controls: &[[f64; 2]; 4], t: f64) -> [f64; 2] {
    let mt = 1.0 - t;
    let (w0, w1, w2, w3) = (
        mt * mt * mt,
        3.0 * mt * mt * t,
        3.0 * mt * t * t,
        t * t * t,
    );
    [
        w0 * controls[0][0] + w1 * controls[1][0] + w2 * controls[2][0] + w3 * controls[3][0],
        w0 * controls[0][1] + w1 * controls[1][1] + w2 * controls[2][1] + w3 * controls[3][1],
    ]
}

/// Resolve four control-point ids to coordinates, or `None` if any is missing.
fn span_controls(doc: &SketchDoc, ids: &[Value; 4]) -> Option<[[f64; 2]; 4]> {
    let mut out = [[0.0; 2]; 4];
    for (slot, id) in ids.iter().enumerate() {
        let p = doc.point(id)?;
        out[slot] = [p.x, p.y];
    }
    Some(out)
}

fn lerp(a: [f64; 2], b: [f64; 2], t: f64) -> [f64; 2] {
    [a[0] + (b[0] - a[0]) * t, a[1] + (b[1] - a[1]) * t]
}

/// Move an existing point to `(x, y)`, or `None` if it vanished.
fn move_point(doc: &mut SketchDoc, id: &Value, at: [f64; 2]) -> Option<()> {
    let p = doc.point_mut(id)?;
    p.x = at[0];
    p.y = at[1];
    Some(())
}

/// Mint a fresh free point at `at` and return its id. Never snaps to a neighbour
/// (unlike [`SketchDoc::snap_or_add_point`]): a subdivision's three new control points
/// are new roles in the polygon even when they land on top of something.
fn add_point(doc: &mut SketchDoc, at: [f64; 2]) -> Value {
    let id = doc.next_point_id();
    doc.points.push(SketchPoint {
        id: id.clone(),
        x: at[0],
        y: at[1],
        fixed: false,
        construction: false,
        external_reference: false,
    });
    id
}

// ---------------------------------------------------------------------------
// Test-only geometry readers.
//
// Shared by this module's unit tests AND the engine-level tool tests
// (`engine_state::sketch_mode_tests`), so "the curve did not move" is measured by
// ONE implementation in both places — analytically, against the control polygons,
// never through a sampled polyline (whose chord gaps run to ~1e-2 at any sane sample
// count and would swallow the deviation these tests exist to catch).
// ---------------------------------------------------------------------------

// BREP private tests: 8360fe604281cd06

// BREP private tests: b40cd642f4b341ee

// BREP private tests: 5a6b3d99d14c62a9

// BREP private tests: 9ac11503e8609a46

// BREP private tests: a5baf30ebf9e5422

// BREP private tests: 7fbeaa6fd1a895f6