brep_kernel/geometry/

projection.rs

use crate::curve::interior_knots;
use crate::{NurbsCurve, NurbsSurface, Vec3, Vec4};
use serde::Serialize;

const EPSILON: f64 = crate::tolerance::FP_FLOOR;
const LINEAR_TOLERANCE: f64 = crate::tolerance::DEFAULT_MODEL;
const MAX_NEWTON_ITERATIONS: usize = 50;

#[derive(Clone, Copy, Debug, Serialize)]
pub struct CurveProjection {
    pub u: f64,
    pub point: Vec3,
    pub distance: f64,
}

#[derive(Clone, Copy, Debug, Serialize)]
pub struct SurfaceProjection {
    pub u: f64,
    pub v: f64,
    pub point: Vec3,
    pub distance: f64,
}

pub(crate) fn fit_parameter(value: f64, minimum: f64, maximum: f64, closed: bool) -> f64 {
    if closed {
        let period = maximum - minimum;
        (value - minimum).rem_euclid(period) + minimum
    } else {
        value.clamp(minimum, maximum)
    }
}

/// Escape hatch for tamper-verification: `BREP_PROJECTION_WITNESS=0` restores
/// the pre-2026-09-14 answer — the Newton walk from the nearest seed and
/// nothing else — so a fixture that depends on the rescue can be shown to
/// depend on it. Read once; the projector is called about a million times in
/// one boolean.
fn witness_rescue_enabled() -> bool {
    switch!("BREP_PROJECTION_WITNESS", true)
}

/// Squared distance from `point` to the SEGMENT `a`-`b`.
///
/// The seed sweep's consecutive samples are the segments of a polyline that
/// approximates the curve, and this is how far that polyline passes from the
/// query — the witness the rescue below reads.
fn point_segment_distance_squared(point: Vec3, a: Vec3, b: Vec3) -> f64 {
    point.distance_to_segment_squared(a, b)
}

/// One Newton refinement of the foot parameter, seeded at `seed`.
///
/// `best_u` / `best_distance_squared` carry the best answer found SO FAR and
/// every iterate is compared against them, so a run that diverges or stalls can
/// only leave the answer where it was. The returned parameter is where the
/// iteration exited, which the caller still has to evaluate: the stall branch
/// takes its last step without evaluating it.
#[allow(clippy::too_many_arguments)]
fn curve_newton(
    curve: &NurbsCurve,
    point: Vec3,
    seed: f64,
    start: f64,
    end: f64,
    closed: bool,
    best_u: &mut f64,
    best_distance_squared: &mut f64,
) -> Result<f64, String> {
    let (last, nearest, squared) = curve_foot_newton_state(curve, point, seed, [start, end],
        CurveFootPolicy {
            domain: if closed { FootDomain::Wrap } else { FootDomain::Clamp },
            iterations: MAX_NEWTON_ITERATIONS,
            slope_guard: EPSILON,
            step_limit: (end - start) / 4.0,
            parameter_tolerance: 1e-15 * (end - start),
            mode: FootMode::Witness,
        })?;
    if squared < *best_distance_squared {
        *best_distance_squared = squared;
        *best_u = nearest;
    }
    Ok(last)
}

/// The parameter in `[low, high]` nearest `point`, by golden-section search on
/// the SQUARED distance.
///
/// Reads no derivative, so it is the one lane that still works where the
/// tangent vanishes, and it can never return a point farther than the bracket's
/// own ends. It assumes ONE minimum inside the bracket — true of a seed
/// interval, which is one sample step of a single knot span wide.
fn bracketed_nearest(curve: &NurbsCurve, point: Vec3, low: f64, high: f64) -> Result<f64, String> {
    // 1/φ. 64 contractions take a bracket to 2.5e-14 of its width, below the
    // parameter resolution the Newton polish that follows needs from a seed.
    const CONTRACTION: f64 = 0.618_033_988_749_894_9;
    const CONTRACTIONS: usize = 64;
    let width = high - low;
    if !(width > 0.0) {
        return Ok(low);
    }
    let (mut low, mut high) = (low, high);
    let mut c = high - CONTRACTION * (high - low);
    let mut d = low + CONTRACTION * (high - low);
    let mut value_c = curve.evaluate(c)?.sub(point).length_squared();
    let mut value_d = curve.evaluate(d)?.sub(point).length_squared();
    for _ in 0..CONTRACTIONS {
        if high - low <= 1e-15 * width {
            break;
        }
        if value_c < value_d {
            high = d;
            d = c;
            value_d = value_c;
            c = high - CONTRACTION * (high - low);
            value_c = curve.evaluate(c)?.sub(point).length_squared();
        } else {
            low = c;
            c = d;
            value_c = value_d;
            d = low + CONTRACTION * (high - low);
            value_d = curve.evaluate(d)?.sub(point).length_squared();
        }
    }
    Ok((low + high) * 0.5)
}

pub fn project_point_to_curve(curve: &NurbsCurve, point: Vec3) -> Result<CurveProjection, String> {
    if projection_memo_enabled() {
        if let Some(key) = straight_projection_key(curve, point) {
            if let Some(hit) = PROJECTION_MEMO.with(|memo| memo.borrow().get(&key).copied()) {
                return Ok(hit);
            }
            let projection = project_point_to_curve_uncached(curve, point)?;
            PROJECTION_MEMO.with(|memo| {
                let mut memo = memo.borrow_mut();
                if memo.len() >= PROJECTION_MEMO_ENTRIES {
                    memo.clear();
                }
                memo.insert(key, projection);
            });
            return Ok(projection);
        }
    }
    project_point_to_curve_uncached(curve, point)
}

/// PROJECTION MEMO (lane O row 22, 2026-10-29; on by default since the batch 6
/// promotion, `BREP_PROJECTION_MEMO=0` projects every call). The projector is a pure function of the curve's net and the
/// point. On the D2 outward shells every one of its 512 calls a shell call
/// projects onto a straight two-point edge, and 209 of them repeat a call
/// already made (the section's pierces, its ambiguity reads and the endpoint
/// exchange re-project the same points; counted, cad-bot). A straight curve's
/// whole net and the point make a 16-word key compared exactly, so a hit
/// returns the very answer the projector computed.
const PROJECTION_MEMO_ENTRIES: usize = 4096;

thread_local! {
    static PROJECTION_MEMO: std::cell::RefCell<rustc_hash::FxHashMap<[u64; 16], CurveProjection>> = Default::default();
}

fn straight_projection_key(curve: &NurbsCurve, point: Vec3) -> Option<[u64; 16]> {
    if curve.degree != 1 || curve.control_points.len() != 2 || curve.knots.len() != 4 {
        return None;
    }
    let [a, b] = [curve.control_points[0], curve.control_points[1]];
    let k = &curve.knots;
    Some([
        1, k[0].to_bits(), k[1].to_bits(), k[2].to_bits(), k[3].to_bits(),
        a.x.to_bits(), a.y.to_bits(), a.z.to_bits(), a.w.to_bits(),
        b.x.to_bits(), b.y.to_bits(), b.z.to_bits(), b.w.to_bits(),
        point.x.to_bits(), point.y.to_bits(), point.z.to_bits(),
    ])
}

fn projection_memo_enabled() -> bool {
    switch!("BREP_PROJECTION_MEMO", true)
}


fn project_point_to_curve_uncached(curve: &NurbsCurve, point: Vec3) -> Result<CurveProjection, String> {
    let [start, end] = curve.domain()?;
    let mut breaks = vec![start];
    breaks.extend(interior_knots(&curve.knots, curve.degree));
    breaks.push(end);
    let samples_per_span = 4usize.max(curve.degree + 2);
    let mut best_u = start;
    let mut best_distance_squared = f64::INFINITY;
    // The sweep's FIRST sample is exactly `start` and its LAST is exactly `end`
    // (`breaks` opens at `start` and closes at `end`, and index 0 / index
    // `samples_per_span` hit a span's own ends), so closure costs no extra
    // evaluation: keep those two points and compare them.
    let mut start_point = None;
    let mut end_point = None;
    // The sampled polyline's own nearest approach, and the seed interval that
    // achieves it. Squared throughout, so the sweep pays no square root.
    let mut previous: Option<(f64, Vec3)> = None;
    let mut witness_distance_squared = f64::INFINITY;
    let mut witness_low = start;
    let mut witness_high = start;
    for pair in breaks.windows(2) {
        for index in 0..=samples_per_span {
            let parameter = pair[0] + (pair[1] - pair[0]) * index as f64 / samples_per_span as f64;
            let sample = curve.evaluate(parameter)?;
            if start_point.is_none() {
                start_point = Some(sample);
            }
            end_point = Some(sample);
            let distance_squared = sample.sub(point).length_squared();
            if distance_squared < best_distance_squared {
                best_distance_squared = distance_squared;
                best_u = parameter;
            }
            if let Some((previous_parameter, previous_sample)) = previous {
                let segment = point_segment_distance_squared(point, previous_sample, sample);
                if segment < witness_distance_squared {
                    witness_distance_squared = segment;
                    witness_low = previous_parameter;
                    witness_high = parameter;
                }
            }
            previous = Some((parameter, sample));
        }
    }
    // A closed curve's domain is PERIODIC, so Newton must wrap across the seam
    // rather than stop at it. Clamping made the projector return the seam for
    // any query whose foot sits within half a seed spacing of it: `start` and
    // `end` are the same POINT, the sweep keeps the first of equal distances and
    // so seeds at `start`, and a Newton step toward a foot just BEFORE the seam
    // is then clamped back to `start`, reads as a zero-length step, and breaks.
    // Measured on a rational-quadratic circle of radius 20: 4.796 mm out, for a
    // point taken off the curve itself. Swapping the sweep's tie-break to keep
    // the LAST equal sample does not fix this — it mirrors it, returning the
    // same 4.796 mm for queries just AFTER the seam. The surface projector has
    // always wrapped (`fit_parameter` at the `project_point_to_surface` Newton
    // step); this is the curve side catching up.
    const CLOSED_SEAM_TOLERANCE: f64 = 1e-6;
    let closed = match (start_point, end_point) {
        (Some(first), Some(last)) => first.sub(last).length() <= CLOSED_SEAM_TOLERANCE,
        _ => false,
    };

    let parameter = curve_newton(
        curve,
        point,
        best_u,
        start,
        end,
        closed,
        &mut best_u,
        &mut best_distance_squared,
    )?;
    for candidate in [start, end, parameter] {
        let distance_squared = curve.evaluate(candidate)?.sub(point).length_squared();
        if distance_squared < best_distance_squared {
            best_distance_squared = distance_squared;
            best_u = candidate;
        }
    }
    // AN ANSWER THE SEED POLYLINE REFUTES IS NOT AN ANSWER. The sweep's
    // consecutive samples are a polyline that approximates the curve, so the
    // nearest that polyline passes to the query is a witness: the curve
    // demonstrably comes about that close. When the answer is FARTHER than the
    // witness by more than a factor of two, Newton converged in the wrong basin
    // and the seed interval the witness names is where the foot really is.
    //
    // Two different defects reach here, both of them "a point ON the curve does
    // not project to its own parameter", and both measured on real geometry:
    //
    // * A STATIONARY seed. Newton is a first-order method and
    //   `f = C'(t) · (C(t) - P)` vanishes at a stationary parameter for EVERY
    //   `P`, so the iteration reads convergence there whatever the point is, and
    //   the step it would otherwise take is `-f/f''`, a second-order quantity
    //   whose sign has nothing to do with where the foot is. The 2026-09-14
    //   herringbone document is full of them: a flank pcurve is a two-span cubic
    //   whose first two control points COINCIDE (an involute's speed is
    //   `r_base * t`, so its Hermite start tangent is exactly zero), the sweep's
    //   nearest sample to a query near the start IS that cusp, and a point lying
    //   exactly on the curve at t = 0.125 answered t = 0, 2.159e-2 out in uv.
    //   That is the wrong answer `build_loop`'s partial-run rescue declined on.
    // * A seed grid coarser in ONE span than in the rest. An imported pcurve
    //   from `abc_00000013.step` carries 511 interior knots whose first span is
    //   eighty times the width of the median, and five samples per span leave
    //   its samples 4.6e-3 of uv apart — so a point on the curve at fraction
    //   0.01 read as 3.969e-3 from a DIFFERENT branch at fraction 0.99, which
    //   was genuinely nearer than any sample of its own.
    //
    // The witness refuted both by 71x and by 293000x. Every update below is a
    // strict improvement on the distance already found, so a rescue that finds
    // nothing better leaves the answer exactly where it was.
    const WITNESS_FACTOR: f64 = 2.0;
    if witness_distance_squared * (WITNESS_FACTOR * WITNESS_FACTOR) < best_distance_squared
        && witness_rescue_enabled()
    {
        let bracketed = bracketed_nearest(curve, point, witness_low, witness_high)?;
        let polished = curve_newton(
            curve,
            point,
            bracketed,
            start,
            end,
            closed,
            &mut best_u,
            &mut best_distance_squared,
        )?;
        for candidate in [bracketed, polished] {
            let distance_squared = curve.evaluate(candidate)?.sub(point).length_squared();
            if distance_squared < best_distance_squared {
                best_distance_squared = distance_squared;
                best_u = candidate;
            }
        }
    }
    let projected = curve.evaluate(best_u)?;
    Ok(CurveProjection {
        u: best_u,
        point: projected,
        distance: projected.sub(point).length(),
    })
}

fn project_linear_revolution(
    surface: &NurbsSurface,
    point: Vec3,
) -> Result<Option<SurfaceProjection>, String> {
    let rows = &surface.control_points;
    if surface.degree_u != 2
        || surface.degree_v != 1
        || rows.len() < 5
        || rows[0].len() != 2
        || !surface.closed_directions()?.0
    {
        return Ok(None);
    }
    let base = rows[0][0].point()?.add(rows[4][0].point()?).scale(0.5);
    let top = rows[0][1].point()?.add(rows[4][1].point()?).scale(0.5);
    let axis_vector = top.sub(base);
    let height = axis_vector.length();
    if height <= EPSILON {
        return Ok(None);
    }
    let axis = axis_vector.normalized()?;
    let [v0, v1] = surface.domain_v()?;
    let axial = point.sub(base).dot(axis).clamp(0.0, height);
    let v = v0 + (v1 - v0) * axial / height;
    let circle = surface.iso_curve_v(v)?;
    let projection = project_point_to_curve(&circle, point)?;
    let [u0, u1] = surface.domain_u()?;
    let u = projection.u.clamp(u0, u1);
    let projected = surface.evaluate(u, v)?;
    Ok(Some(SurfaceProjection {
        u,
        v,
        point: projected,
        distance: projected.sub(point).length(),
    }))
}

#[derive(Clone, Copy)]
struct NewtonResult {
    u: f64,
    v: f64,
    distance_squared: f64,
    converged: bool,
}

fn surface_newton(
    surface: &NurbsSurface,
    point: Vec3,
    seed_u: f64,
    seed_v: f64,
    domains: [f64; 4],
    closed_u: bool,
    closed_v: bool,
) -> Result<NewtonResult, String> {
    surface_newton_impl(surface, point, seed_u, seed_v, domains, closed_u, closed_v,
        switch!("BREP_PROJECTION_LAZY_DERIVATIVES", false), LINEAR_TOLERANCE)
}

/// Most seeded verification queries are already on the carrier. Row zero
/// uses the same basis and rational arithmetic at counts zero and two; read
/// it first, preserving the best-point and distance exit, and compute the
/// remaining derivatives only when Newton actually needs to take a step.
fn surface_newton_impl(
    surface: &NurbsSurface,
    point: Vec3,
    seed_u: f64,
    seed_v: f64,
    domains: [f64; 4],
    closed_u: bool,
    closed_v: bool,
    lazy: bool,
    linear_tolerance: f64,
) -> Result<NewtonResult, String> {
    let [u0, u1, v0, v1] = domains;
    let mut u = seed_u;
    let mut v = seed_v;
    let mut converged = false;
    let mut best = NewtonResult {
        u,
        v,
        distance_squared: surface.evaluate(u, v)?.sub(point).length_squared(),
        converged,
    };
    for iteration in 0..MAX_NEWTON_ITERATIONS {
        crate::imprint::work_profile::add(|c| c.newton_iterations += 1);
        let derivatives = surface.derivatives_small(u, v, if lazy { 0 } else { 2 })?;
        let residual = derivatives[0][0].sub(point);
        let distance_squared = residual.length_squared();
        if distance_squared < best.distance_squared {
            best.u = u;
            best.v = v;
            best.distance_squared = distance_squared;
        }
        let residual_length = distance_squared.sqrt();
        if residual_length <= linear_tolerance {
            crate::imprint::work_profile::add(|c| { c.newton_unused += 1; c.newton_unused_first += u64::from(iteration == 0); });
            converged = true;
            break;
        }
        let derivatives = if lazy { surface.derivatives_small(u, v, 2)? } else { derivatives };
        let f = derivatives[1][0].dot(residual);
        let g = derivatives[0][1].dot(residual);
        let tangent_u_length = derivatives[1][0].length();
        let tangent_v_length = derivatives[0][1].length();
        let cosine_u = if tangent_u_length * residual_length <= EPSILON {
            0.0
        } else {
            f.abs() / (tangent_u_length * residual_length)
        };
        let cosine_v = if tangent_v_length * residual_length <= EPSILON {
            0.0
        } else {
            g.abs() / (tangent_v_length * residual_length)
        };
        if cosine_u <= 1e-10 && cosine_v <= 1e-10 {
            converged = true;
            break;
        }
        let j00 = derivatives[2][0].dot(residual) + derivatives[1][0].length_squared();
        let j01 = derivatives[1][1].dot(residual) + derivatives[1][0].dot(derivatives[0][1]);
        let j11 = derivatives[0][2].dot(residual) + derivatives[0][1].length_squared();
        let determinant = j00 * j11 - j01 * j01;
        if determinant.abs() <= EPSILON {
            break;
        }
        let mut du = (-f * j11 + g * j01) / determinant;
        let mut dv = (-g * j00 + f * j01) / determinant;
        du = du.clamp(-(u1 - u0) / 4.0, (u1 - u0) / 4.0);
        dv = dv.clamp(-(v1 - v0) / 4.0, (v1 - v0) / 4.0);
        let next_u = fit_parameter(u + du, u0, u1, closed_u);
        let next_v = fit_parameter(v + dv, v0, v1, closed_v);
        let stalled =
            (next_u - u).abs() <= 1e-15 * (u1 - u0) && (next_v - v).abs() <= 1e-15 * (v1 - v0);
        u = next_u;
        v = next_v;
        if stalled {
            break;
        }
    }
    let final_distance_squared = surface.evaluate(u, v)?.sub(point).length_squared();
    if final_distance_squared < best.distance_squared {
        best.u = u;
        best.v = v;
        best.distance_squared = final_distance_squared;
    }
    best.converged = converged;
    Ok(best)
}

/// Refine an existing branch foot for precision trim construction. The normal
/// projector's distance exit is an on-carrier admission test, not a bound on
/// tangential placement suitable for interpolating a more accurate trim.
pub(crate) fn refine_trim_foot(
    surface: &NurbsSurface, point: Vec3, foot: SurfaceProjection,
) -> Result<SurfaceProjection, String> {
    let [u0, u1] = surface.domain_u()?;
    let [v0, v1] = surface.domain_v()?;
    let (cu, cv) = surface.closed_directions()?;
    let result = surface_newton_impl(surface, point, foot.u, foot.v,
        [u0, u1, v0, v1], cu, cv, false, 1e-11)?;
    let projected = surface.evaluate(result.u, result.v)?;
    Ok(SurfaceProjection { u: result.u, v: result.v, point: projected,
        distance: projected.sub(point).length() })
}

/// The point of `surface` nearest `point`, over the surface's whole domain.
///
/// Analytic carriers answer in closed form; every other surface goes through
/// `project_point_to_surface_general`, which says what it guarantees.
/// `#[track_caller]` names the call site in the `BREP_PROJECTION_AUDIT` log.
#[track_caller]
pub fn project_point_to_surface(
    surface: &NurbsSurface,
    point: Vec3,
) -> Result<SurfaceProjection, String> {
    crate::imprint::work_profile::add(|c| c.projection_global += 1);
    let _lap = crate::projection_profile::Lap::enter(crate::projection_profile::LANE_PROJECT, surface);
    // Recognized analytic carriers (plane / cylinder / cone / sphere /
    // torus) have exact closed-form projections in the surface's own
    // rational parameterization — skip grid seeding and Newton entirely.
    if let Some(analytic) = surface.analytic() {
        if let Some(projection) = analytic.project(surface, point) {
            return Ok(projection);
        }
    }
    if let Some(ellipsoid) = surface.affine_sphere() {
        if let Some(projection) = ellipsoid.project(surface, point) {
            return Ok(projection);
        }
    }
    project_point_to_surface_general(surface, point)
}

/// Project a point onto a surface starting Newton from an explicit `(u, v)`
/// guess, WITHOUT the global grid seed. This is a footpoint refiner for
/// continuity-preserving curve-on-surface tracing: seeding each edge sample
/// from its neighbour's parameters keeps the fit on ONE branch of a surface
/// that folds back over the small trimmed patch, where an independent global
/// search would snap to whichever fold is momentarily closest and tear the
/// pcurve into a self-crossing zig-zag. The caller compares the returned
/// `distance` against the global answer and only adopts this result when it is
/// geometrically just as valid, so a bad seed can never make a fit worse.
pub fn project_point_to_surface_seeded(
    surface: &NurbsSurface,
    point: Vec3,
    seed_u: f64,
    seed_v: f64,
) -> Result<SurfaceProjection, String> {
    crate::imprint::work_profile::add(|c| c.projection_seeded += 1);
    let _wall = crate::wall_profile::Scope::enter(crate::wall_profile::SEEDED);
    let _lap = crate::projection_profile::Lap::enter(crate::projection_profile::LANE_SEEDED, surface);
    // An ellipsoid's foot is unique off its medial axis: the closed form IS
    // the branch answer, as it is for the analytic carriers at the seeded
    // entry (`project_point_to_surface_from_seed`).
    if let Some(ellipsoid) = surface.affine_sphere() {
        if let Some(projection) = ellipsoid.project(surface, point) {
            return Ok(projection);
        }
    }
    let [u0, u1] = surface.domain_u()?;
    let [v0, v1] = surface.domain_v()?;
    let (closed_u, closed_v) = surface.closed_directions()?;
    let result = surface_newton(
        surface,
        point,
        seed_u,
        seed_v,
        [u0, u1, v0, v1],
        closed_u,
        closed_v,
    )?;
    let projected = surface.evaluate(result.u, result.v)?;
    Ok(SurfaceProjection {
        u: result.u,
        v: result.v,
        point: projected,
        distance: projected.sub(point).length(),
    })
}

/// The foot of `point` on the branch of `seed`: the closed form on an analytic
/// carrier, otherwise Newton from the caller's own `(u, v)`
/// ([`project_point_to_surface_seeded`]), WITHOUT the global search.
///
/// **Which callers.** One that already holds a foot on this surface from a
/// geometrically adjacent query and whose output needs continuity with it: a
/// pcurve's previous sample, a march's previous station, a Newton's previous
/// iterate. [`project_point_to_surface`] answers a different question — where
/// on the WHOLE surface the point is nearest — and on a carrier that comes back
/// near itself, or for an off-surface query about as far from two sheets, that
/// answer is a foot on another branch: a pcurve sample on the wrong sheet, an
/// iterate that jumps. A caller with no such foot (a vertex, a probe, the first
/// station) asks the nearest-point question and calls the projector.
///
/// **An analytic carrier** answers in closed form, as the projector does. Its
/// only places with two equally valid feet are its seam, its poles and its focal
/// set (axis, centre, tube circle), and the closed form answers those exactly as
/// the nearest-point query always has; no march on one changes.
///
/// **What it does not promise.** It is a local answer: its distance is an upper
/// bound, and a Newton that stalls returns its best iterate without saying so.
/// Every caller keeps its own on-surface check.
///
/// **Instruments**, each read once. `BREP_PROJECTION_FROM_SEED=0` returns
/// [`project_point_to_surface`]'s answer at every caller (the reading before
/// 2026-09-15, for a same-binary A/B); `BREP_PROJECTION_FROM_SEED_SITES=<a,b,…>`
/// keeps the seeded answer only at the call sites whose `file:line` contains
/// one of the substrings. Under `BREP_PROJECTION_AUDIT=<dir>` every query whose
/// seeded foot lies farther than the on-surface floor from the nearest point's
/// foot appends one line to `<dir>/projection-seed-audit-<pid>.tsv`. That
/// comparand is the nearest-point projector under the same caller, so its own
/// replacements land in `projection-audit-<pid>.tsv` at this site's line: they
/// are the audit's, not an answer the caller took.
#[track_caller]
pub(crate) fn project_point_to_surface_from_seed(
    surface: &NurbsSurface,
    point: Vec3,
    seed: [f64; 2],
) -> Result<SurfaceProjection, String> {
    crate::imprint::work_profile::add(|c| c.projection_from_seed += 1);
    let _wall = crate::wall_profile::Scope::enter(crate::wall_profile::SEEDED);
    let _lap = crate::projection_profile::Lap::enter(crate::projection_profile::LANE_FROM_SEED, surface);
    if let Some(analytic) = surface.analytic() {
        if let Some(projection) = analytic.project(surface, point) {
            return Ok(projection);
        }
    }
    if let Some(ellipsoid) = surface.affine_sphere() {
        if let Some(projection) = ellipsoid.project(surface, point) {
            return Ok(projection);
        }
    }
    let caller = std::panic::Location::caller();
    if !seeded_answer_admitted(caller) {
        return project_point_to_surface_general(surface, point);
    }
    let seeded = project_point_to_surface_seeded(surface, point, seed[0], seed[1])?;
    if seed_audit_enabled() {
        let nearest = project_point_to_surface_general(surface, point)?;
        if seeded.point.sub(nearest.point).length() > LINEAR_TOLERANCE {
            seed_audit_record(caller, surface, seed, &seeded, &nearest);
        }
    }
    Ok(seeded)
}

/// `BREP_PROJECTION_FROM_SEED=0` / `BREP_PROJECTION_FROM_SEED_SITES`: see
/// [`project_point_to_surface_from_seed`].
fn seeded_answer_admitted(caller: &std::panic::Location<'_>) -> bool {
    static SITES: std::sync::OnceLock<Option<Option<Vec<String>>>> = std::sync::OnceLock::new();
    let sites = SITES.get_or_init(|| {
        if std::env::var("BREP_PROJECTION_FROM_SEED").as_deref() == Ok("0") {
            return None;
        }
        Some(std::env::var("BREP_PROJECTION_FROM_SEED_SITES").ok().map(|value| {
            value.split(',').map(str::to_string).filter(|site| !site.is_empty()).collect()
        }))
    });
    match sites {
        None => false,
        Some(None) => true,
        Some(Some(only)) => {
            let location = format!("{}:{}", caller.file(), caller.line());
            only.iter().any(|site| location.contains(site.as_str()))
        }
    }
}

fn seed_audit_enabled() -> bool {
    debug_flag!("BREP_PROJECTION_AUDIT")
}

/// One line per seeded answer whose foot is not the nearest point's: the call
/// site, both distances, the seed, both feet's `(u, v)`, the separation of the
/// two feet and the surface's shape.
fn seed_audit_record(
    caller: &std::panic::Location<'_>,
    surface: &NurbsSurface,
    seed: [f64; 2],
    seeded: &SurfaceProjection,
    nearest: &SurfaceProjection,
) {
    use std::io::Write;
    static SINK: std::sync::OnceLock<Option<std::sync::Mutex<std::fs::File>>> =
        std::sync::OnceLock::new();
    let sink = SINK.get_or_init(|| {
        let directory = std::env::var_os("BREP_PROJECTION_AUDIT")?;
        let path = std::path::Path::new(&directory)
            .join(format!("projection-seed-audit-{}.tsv", std::process::id()));
        std::fs::OpenOptions::new()
            .create(true)
            .append(true)
            .open(path)
            .ok()
            .map(std::sync::Mutex::new)
    });
    if let Some(file) = sink {
        if let Ok(mut file) = file.lock() {
            let _ = writeln!(
                file,
                "{}:{}\t{:.6e}\t{:.6e}\t{:.9}\t{:.9}\t{:.9}\t{:.9}\t{:.9}\t{:.9}\t{:.6e}\t{}x{} cp {}x{}",
                caller.file(),
                caller.line(),
                seeded.distance,
                nearest.distance,
                seed[0],
                seed[1],
                seeded.u,
                seeded.v,
                nearest.u,
                nearest.v,
                seeded.point.sub(nearest.point).length(),
                surface.degree_u,
                surface.degree_v,
                surface.control_points.len(),
                surface.control_points.first().map(Vec::len).unwrap_or(0),
            );
        }
    }
}

/// The Newton seed grid for general projection: (u, v, point) samples over
/// every knot span. A pure function of the surface, cached on it — building
/// the grid costs hundreds of evaluations and projection is the hottest
/// entry point in the kernel.
fn projection_seed_grid(surface: &NurbsSurface) -> Result<&SampleGrid, String> {
    if let Some(grid) = surface.projection_grid.get() {
        return Ok(grid);
    }
    let [u0, u1] = surface.domain_u()?;
    let [v0, v1] = surface.domain_v()?;
    let (closed_u, closed_v) = surface.closed_directions()?;
    let mut breaks_u = vec![u0];
    breaks_u.extend(interior_knots(&surface.knots_u, surface.degree_u));
    breaks_u.push(u1);
    let mut breaks_v = vec![v0];
    breaks_v.extend(interior_knots(&surface.knots_v, surface.degree_v));
    breaks_v.push(v1);
    let samples_u = if closed_u {
        8usize.max(surface.degree_u * 4)
    } else {
        3usize.max(surface.degree_u + 1)
    };
    let samples_v = if closed_v {
        8usize.max(surface.degree_v * 4)
    } else {
        3usize.max(surface.degree_v + 1)
    };
    let mut grid = Vec::new();
    for u_pair in breaks_u.windows(2) {
        for v_pair in breaks_v.windows(2) {
            for i in 0..=samples_u {
                for j in 0..=samples_v {
                    let u = u_pair[0] + (u_pair[1] - u_pair[0]) * i as f64 / samples_u as f64;
                    let v = v_pair[0] + (v_pair[1] - v_pair[0]) * j as f64 / samples_v as f64;
                    grid.push((u, v, surface.evaluate(u, v)?));
                }
            }
        }
    }
    Ok(surface.projection_grid.get_or_init(|| SampleGrid::new(grid)))
}

/// The dense fallback grid for degenerate general projection: (u, v, point)
/// over a `(count_u+1) × (count_v+1)` lattice with `count_u/count_v` derived
/// from the surface's knot spans. A pure function of the surface, cached on
/// it — on metre-unit-mm parts the degenerate fallback fires ~1.7M times and
/// each re-evaluated all ~561 lattice points; caching them makes the argmin a
/// pure distance scan over reused points (bit-identical seed).
fn projection_dense_grid(surface: &NurbsSurface) -> Result<&SampleGrid, String> {
    if let Some(grid) = surface.projection_dense_grid.get() {
        return Ok(grid);
    }
    let [u0, u1] = surface.domain_u()?;
    let [v0, v1] = surface.domain_v()?;
    let mut breaks_u = vec![u0];
    breaks_u.extend(interior_knots(&surface.knots_u, surface.degree_u));
    breaks_u.push(u1);
    let mut breaks_v = vec![v0];
    breaks_v.extend(interior_knots(&surface.knots_v, surface.degree_v));
    breaks_v.push(v1);
    let count_u = 32usize.max((breaks_u.len() - 1) * 8);
    let count_v = 16usize.max((breaks_v.len() - 1) * 8);
    let mut grid = Vec::with_capacity((count_u + 1) * (count_v + 1));
    for i in 0..=count_u {
        for j in 0..=count_v {
            let u = u0 + (u1 - u0) * i as f64 / count_u as f64;
            let v = v0 + (v1 - v0) * j as f64 / count_v as f64;
            grid.push((u, v, surface.evaluate(u, v)?));
        }
    }
    Ok(surface.projection_dense_grid.get_or_init(|| SampleGrid::with_tree(grid)))
}

/// Samples per block of a [`SampleGrid`].
const SAMPLE_BLOCK: usize = 32;

/// Runs per group: the scan's second level, a box over [`GROUP_BLOCKS`]
/// consecutive runs ([`SampleGrid::groups`]).
const GROUP_BLOCKS: usize = 32;

/// A cached `(u, v, point)` sample grid, with the axis-aligned box of each run
/// of [`SAMPLE_BLOCK`] consecutive samples, so the nearest-sample scan
/// ([`nearest_sample`]) skips a run none of whose samples can beat the answer
/// it holds.
#[derive(Clone, Debug)]
pub(crate) struct SampleGrid {
    samples: Vec<(f64, f64, Vec3)>,
    blocks: Vec<SampleBlock>,
    /// The union box of each [`GROUP_BLOCKS`] consecutive runs, prunable only
    /// when every run in it is. A union box's floor is at most each of its
    /// runs' floors as computed (the box faces are the runs' own, and the gap
    /// to a face farther out is no larger, IEEE rounding being monotone).
    groups: Vec<SampleBlock>,
    /// The box tree over the runs ([`nearest_sample_tree`]): `tree[0]` boxes
    /// each [`TREE_FANOUT`] consecutive runs, `tree[k]` each [`TREE_FANOUT`]
    /// consecutive boxes of `tree[k - 1]`, up to a single root. Built only by
    /// [`SampleGrid::with_tree`] (the dense grid), and empty when the grid has
    /// at most one group of runs.
    tree: Vec<Vec<SampleBlock>>,
}

/// Children per node of [`SampleGrid::tree`].
const TREE_FANOUT: usize = 4;

/// The union box of consecutive boxes, prunable only when each of them is.
fn union_boxes(boxes: &[SampleBlock]) -> Vec<SampleBlock> {
    boxes
        .chunks(TREE_FANOUT)
        .map(|chunk| {
            let mut union = chunk[0];
            for block in chunk {
                union.low = Vec3::new(union.low.x.min(block.low.x), union.low.y.min(block.low.y), union.low.z.min(block.low.z));
                union.high = Vec3::new(union.high.x.max(block.high.x), union.high.y.max(block.high.y), union.high.z.max(block.high.z));
                union.prunable &= block.prunable;
            }
            union
        })
        .collect()
}

/// One run's box. `prunable` is false when a sample has a non-finite
/// coordinate: the box says nothing about it, and the run is always scanned.
#[derive(Clone, Copy, Debug)]
struct SampleBlock {
    low: Vec3,
    high: Vec3,
    prunable: bool,
}

impl SampleGrid {
    fn new(samples: Vec<(f64, f64, Vec3)>) -> Self {
        let blocks = samples
            .chunks(SAMPLE_BLOCK)
            .map(|chunk| {
                let mut low = chunk[0].2;
                let mut high = low;
                let mut prunable = true;
                for &(_, _, p) in chunk {
                    prunable &= p.x.is_finite() && p.y.is_finite() && p.z.is_finite();
                    low = Vec3::new(low.x.min(p.x), low.y.min(p.y), low.z.min(p.z));
                    high = Vec3::new(high.x.max(p.x), high.y.max(p.y), high.z.max(p.z));
                }
                SampleBlock { low, high, prunable }
            })
            .collect::<Vec<_>>();
        let groups = blocks
            .chunks(GROUP_BLOCKS)
            .map(|chunk| {
                let mut group = chunk[0];
                for block in chunk {
                    group.low = Vec3::new(group.low.x.min(block.low.x), group.low.y.min(block.low.y), group.low.z.min(block.low.z));
                    group.high = Vec3::new(group.high.x.max(block.high.x), group.high.y.max(block.high.y), group.high.z.max(block.high.z));
                    group.prunable &= block.prunable;
                }
                group
            })
            .collect();
        Self { samples, blocks, groups, tree: Vec::new() }
    }

    /// The grid with its box tree, for a scan that starts from a held answer
    /// (the dense fallback after a Newton): there the tree reads few floors.
    /// A scan from no answer reads its bound from a greedy descent, which on a
    /// surface whose boxes mostly hold the point lands on an arbitrary run;
    /// ABC 00027566's seed scans took 75 s through the tree against 44 s
    /// through the groups, so the seed grid keeps the groups.
    fn with_tree(samples: Vec<(f64, f64, Vec3)>) -> Self {
        let mut grid = Self::new(samples);
        if grid.blocks.len() > GROUP_BLOCKS {
            grid.tree.push(union_boxes(&grid.blocks));
            while grid.tree.last().is_some_and(|level| level.len() > 1) {
                let next = union_boxes(grid.tree.last().unwrap());
                grid.tree.push(next);
            }
        }
        grid
    }
}

impl SampleBlock {
    /// A floor on `sample.sub(point).length_squared()` over the run's samples,
    /// as COMPUTED, not only as real numbers: per axis the gap from `point` to
    /// the box is the same subtraction against the box face, and IEEE rounding
    /// is monotone, so `|fl(s - p)| >= fl(face - p)`; squaring and the same
    /// left-to-right sum of non-negative terms keep the order (`Vec3::dot`
    /// has no fused multiply-add). A NaN `point` reads gaps of 0 and every
    /// distance is NaN, which no scan takes, so skipping changes nothing.
    fn lower_bound(&self, point: Vec3) -> f64 {
        let gap = |p: f64, low: f64, high: f64| {
            if p < low {
                low - p
            } else if p > high {
                p - high
            } else {
                0.0
            }
        };
        let x = gap(point.x, self.low.x, self.high.x);
        let y = gap(point.y, self.low.y, self.high.y);
        let z = gap(point.z, self.low.z, self.high.z);
        x * x + y * y + z * z
    }
}

/// `BREP_PROJECTION_PRUNED_SCAN=0` scans every sample, as before 2026-11-10,
/// for a same-binary A/B. Read once per process.
fn pruned_scan() -> bool {
    switch!("BREP_PROJECTION_PRUNED_SCAN", true)
}

/// Replace `best` with the grid's nearest sample when that is strictly nearer,
/// the first such in scan order: the bits of the linear scan, which this was
/// until 2026-11-10. A run is skipped only when its box's floor is not below
/// the distance held, so none of its samples could have replaced it (the
/// strict `<`), or lies above the bound read first ([`bound_first_scan`]),
/// and the runs are visited in scan order. ABC 00027566's
/// 166-span rational faces take the dense fallback on 71% of their pcurve
/// probes (the first Newton not converged), each scanning 22.7k samples: 9.1 s
/// of a face's 11.5 s of local answers.
fn nearest_sample(grid: &SampleGrid, point: Vec3, best: &mut NewtonResult) {
    if !grid.tree.is_empty() && scan_tree() && pruned_scan() && bound_first_scan() {
        nearest_sample_tree(grid, point, best);
        return;
    }
    nearest_sample_with(grid, point, best, pruned_scan(), bound_first_scan());
}

/// `BREP_PROJECTION_SCAN_TREE=0` scans through the two levels of groups and
/// runs alone, as before 2026-11-11, for a same-binary A/B. Read once per
/// process.
///
/// With it on, a grid built with a tree ([`SampleGrid::with_tree`]: the dense
/// grid, when it has more than one group) is scanned through
/// [`SampleGrid::tree`]. ABC 00027566's dense fallback on its 166-span faces
/// passed 52 of 287 group boxes per call (a group is a strip across the
/// surface, and many strips' boxes hold a point on it) and then read 1680 run
/// floors to scan 0.65 runs, never improving the answer it held: 26 s of floors
/// at one pcurve site.
fn scan_tree() -> bool {
    switch!("BREP_PROJECTION_SCAN_TREE", true)
}

/// `BREP_PROJECTION_SCAN_HINT=0` reads the bound from the descent alone, as
/// before 2026-11-11, for a same-binary A/B. Read once per process.
///
/// With it on, a bound-first scan also reads the run that held the answer of
/// the last scan of the same grid on this thread. Consecutive queries are
/// mostly neighbours (a pcurve's probes): ABC 00027566's busiest pcurve site
/// found its answer in the previous answer's run on 98.8% of seed scans, while
/// the descent's run held it on 40%; with the hint the bound is the answer on
/// 99.4% and the seed scans there fell from 43.6 s to 18.4 s.
fn scan_hint() -> bool {
    switch!("BREP_PROJECTION_SCAN_HINT", true)
}

const HINT_SLOTS: usize = 8;

thread_local! {
    /// Direct-mapped by grid address: (grid samples address, run of its last answer).
    static SCAN_HINTS: std::cell::Cell<[(usize, usize); HINT_SLOTS]> =
        const { std::cell::Cell::new([(0, usize::MAX); HINT_SLOTS]) };
}

fn hint_slot(grid: &SampleGrid) -> (usize, usize) {
    let address = grid.samples.as_ptr() as usize;
    (address, (address >> 4) % HINT_SLOTS)
}

/// The bound lowered by the hinted run's samples. The hint is only a run
/// index: it is range-checked and read from the grid in hand, so a stale one
/// (another grid at a reused address) costs time, never bits. It lowers the
/// BOUND alone, never the answer held: each value it can take is a real
/// sample distance, at least the grid's least distance `m`, which is all the
/// bound-first argument asks of it.
fn hinted_bound(grid: &SampleGrid, point: Vec3, mut bound: f64) -> f64 {
    if !scan_hint() {
        return bound;
    }
    let (address, slot) = hint_slot(grid);
    let (held, run) = SCAN_HINTS.with(|hints| hints.get()[slot]);
    if held != address || run >= grid.blocks.len() || !grid.blocks[run].prunable {
        return bound;
    }
    let start = run * SAMPLE_BLOCK;
    let end = (start + SAMPLE_BLOCK).min(grid.samples.len());
    for &(_, _, sample) in &grid.samples[start..end] {
        let distance_squared = sample.sub(point).length_squared();
        if distance_squared < bound {
            bound = distance_squared;
        }
    }
    bound
}

/// Remember the run that last improved the answer of a scan of `grid`.
fn remember_hint(grid: &SampleGrid, run: Option<usize>) {
    if let Some(run) = run.filter(|_| scan_hint()) {
        let (address, slot) = hint_slot(grid);
        SCAN_HINTS.with(|hints| {
            let mut all = hints.get();
            all[slot] = (address, run);
            hints.set(all);
        });
    }
}

/// [`nearest_sample_with`]'s bound-first scan over the box tree: the bound is
/// read from the run reached by descending from the root through the child of
/// lowest floor (a real sample distance, or the incoming one, so never below
/// the grid's least distance `m`), then the tree is visited depth first in
/// scan order, skipping a box whose floor is at or above the distance held or
/// strictly above the bound. A union box's floor is at most each of its
/// children's as computed (the box faces are theirs, and IEEE rounding is
/// monotone), so a box is skipped only when every run under it would have
/// been, and the runs that are read are read in scan order: the bits of the
/// linear scan, by the argument [`nearest_sample_with`] gives for its groups.
fn nearest_sample_tree(grid: &SampleGrid, point: Vec3, best: &mut NewtonResult) {
    let top = grid.tree.len() - 1;
    let mut bound = best.distance_squared;
    // Descend: at each level the child of lowest floor among the prunable ones.
    let mut node = 0usize;
    let mut reached = true;
    for level in (0..=top).rev() {
        let children = |count: usize| node * TREE_FANOUT..((node + 1) * TREE_FANOUT).min(count);
        let below = if level == 0 { &grid.blocks } else { &grid.tree[level - 1] };
        match lowest_floor(below, children(below.len()), point) {
            Some(child) => node = child,
            None => {
                reached = false;
                break;
            }
        }
    }
    if reached {
        let start = node * SAMPLE_BLOCK;
        let end = (start + SAMPLE_BLOCK).min(grid.samples.len());
        for &(_, _, sample) in &grid.samples[start..end] {
            let distance_squared = sample.sub(point).length_squared();
            if distance_squared < bound {
                bound = distance_squared;
            }
        }
    }
    let bound = hinted_bound(grid, point, bound);
    let skip = |box_: &SampleBlock, held: f64| {
        if !box_.prunable {
            return false;
        }
        let floor = box_.lower_bound(point);
        floor >= held || floor > bound
    };
    let mut answer_run = None;
    // Depth first in scan order: (level, index), level 0 of the stack meaning a run.
    let mut stack: Vec<(usize, usize)> = Vec::with_capacity(TREE_FANOUT * (top + 2));
    stack.push((top + 1, 0));
    while let Some((level, index)) = stack.pop() {
        if level == 0 {
            if skip(&grid.blocks[index], best.distance_squared) {
                continue;
            }
            let start = index * SAMPLE_BLOCK;
            let end = (start + SAMPLE_BLOCK).min(grid.samples.len());
            let held = best.distance_squared;
            scan_run(&grid.samples[start..end], point, best);
            if best.distance_squared < held {
                answer_run = Some(index);
            }
            continue;
        }
        if skip(&grid.tree[level - 1][index], best.distance_squared) {
            continue;
        }
        let count = if level == 1 { grid.blocks.len() } else { grid.tree[level - 2].len() };
        let children = index * TREE_FANOUT..((index + 1) * TREE_FANOUT).min(count);
        // Pushed last-first so they pop in scan order.
        for child in children.rev() {
            stack.push((level - 1, child));
        }
    }
    remember_hint(grid, answer_run);
}

/// `BREP_PROJECTION_BOUND_FIRST=0` prunes against the distance held alone, as
/// on 2026-11-10 before this pass, for a same-binary A/B. Read once per
/// process.
///
/// With it on, the runs are boxed again in groups of [`GROUP_BLOCKS`]. The scan
/// first reads the run of lowest floor inside the group of lowest floor and
/// takes the nearest of its samples as a BOUND, then visits the groups and
/// their runs in scan order, skipping any whose floor is at or above the
/// distance held or strictly above that bound. The runs alone started the seed
/// scan from no answer (its incoming distance is infinite), so every run ahead
/// of the nearest sample was read before the held distance fell, and every
/// scan computed one floor per run: on ABC 00027566 the seed
/// scans averaged 63k samples (361 s over 5M calls) and the dense ones 180k
/// (167 s over 3.5M), while a bound over the runs alone cut the first to 190 s
/// but doubled the second to 311 s with its extra pass of floors.
fn bound_first_scan() -> bool {
    switch!("BREP_PROJECTION_BOUND_FIRST", true)
}

/// The scan behind [`nearest_sample`]. With `bound_first`, the bound is the
/// smaller of the incoming distance and one real sample distance, so it is
/// never below the grid's least distance `m`. The first sample at `m` lies in
/// a run whose floor is at most `m`, hence not above the bound and not at or
/// above the distance held when the scan reaches it (every sample before it is
/// strictly farther than `m`): that run is read and the sample taken, as the
/// linear scan takes it, and nothing after it is strictly nearer. A run whose
/// floor is above the bound holds no sample at `m`. The bound pass reads only
/// prunable runs, and updates on a strict `<`, so a NaN never enters it.
fn nearest_sample_with(grid: &SampleGrid, point: Vec3, best: &mut NewtonResult, pruned: bool, bound_first: bool) {
    if !(pruned && bound_first) {
        for (block, chunk) in grid.blocks.iter().zip(grid.samples.chunks(SAMPLE_BLOCK)) {
            if pruned && block.prunable && block.lower_bound(point) >= best.distance_squared {
                continue;
            }
            scan_run(chunk, point, best);
        }
        return;
    }
    // The bound: one real sample distance (or the incoming one), from the run
    // of lowest floor inside the group of lowest floor.
    let mut bound = best.distance_squared;
    let lowest_group = lowest_floor(&grid.groups, 0..grid.groups.len(), point);
    if let Some(group) = lowest_group {
        let runs = group * GROUP_BLOCKS..((group + 1) * GROUP_BLOCKS).min(grid.blocks.len());
        if let Some(run) = lowest_floor(&grid.blocks, runs, point) {
            let start = run * SAMPLE_BLOCK;
            let end = (start + SAMPLE_BLOCK).min(grid.samples.len());
            for &(_, _, sample) in &grid.samples[start..end] {
                let distance_squared = sample.sub(point).length_squared();
                if distance_squared < bound {
                    bound = distance_squared;
                }
            }
        }
    }
    let bound = hinted_bound(grid, point, bound);
    let skip = |box_: &SampleBlock, held: f64| {
        if !box_.prunable {
            return false;
        }
        let floor = box_.lower_bound(point);
        floor >= held || floor > bound
    };
    let mut answer_run = None;
    for (group_index, group) in grid.groups.iter().enumerate() {
        if skip(group, best.distance_squared) {
            continue;
        }
        let first = group_index * GROUP_BLOCKS;
        let last = (first + GROUP_BLOCKS).min(grid.blocks.len());
        for run in first..last {
            if skip(&grid.blocks[run], best.distance_squared) {
                continue;
            }
            let start = run * SAMPLE_BLOCK;
            let end = (start + SAMPLE_BLOCK).min(grid.samples.len());
            let held = best.distance_squared;
            scan_run(&grid.samples[start..end], point, best);
            if best.distance_squared < held {
                answer_run = Some(run);
            }
        }
    }
    remember_hint(grid, answer_run);
}

/// The linear scan of one run: strict `<`, so the first of equal samples
/// stands.
fn scan_run(run: &[(f64, f64, Vec3)], point: Vec3, best: &mut NewtonResult) {
    for &(u, v, sample) in run {
        let distance_squared = sample.sub(point).length_squared();
        if distance_squared < best.distance_squared {
            best.u = u;
            best.v = v;
            best.distance_squared = distance_squared;
        }
    }
}

/// The index, within `range`, of the prunable box of least floor (the first
/// on a tie), or None when none is prunable.
fn lowest_floor(boxes: &[SampleBlock], range: std::ops::Range<usize>, point: Vec3) -> Option<usize> {
    let mut lowest: Option<(usize, f64)> = None;
    for index in range {
        let box_ = &boxes[index];
        if !box_.prunable {
            continue;
        }
        let floor = box_.lower_bound(point);
        if lowest.is_none_or(|(_, held)| floor < held) {
            lowest = Some((index, floor));
        }
    }
    lowest.map(|(index, _)| index)
}

// Boundary-ring cache geometry: 4 sides × 22 exponents × 33 indices. The scan
// positions depend only on the surface domain and these fixed integers, so the
// evaluated points are a pure function of the surface and cacheable.
const RING_EXPONENTS: usize = 22;
const RING_INDICES: usize = 33; // index 0..=32

#[inline]
fn ring_slot(side: usize, exponent_index: usize, index: usize) -> usize {
    (side * RING_EXPONENTS + exponent_index) * RING_INDICES + index
}

/// The boundary-ring sample points for the degenerate projection fallback,
/// flattened by `ring_slot(side, exponent-1, index)`. Sides: 0 = v-low
/// (`v = v0 + (v1-v0)·offset`), 1 = v-high (`v1 - (v1-v0)·offset`), 2 = u-low
/// (`u0 + (u1-u0)·offset`), 3 = u-high (`u1 - (u1-u0)·offset`), where
/// `offset = 1/2^exponent`. A pure function of the surface, cached on it — the
/// fallback's boundary ring re-evaluated these on every one of ~1.7M calls.
fn projection_ring_grid(surface: &NurbsSurface) -> Result<&[Vec3], String> {
    if let Some(grid) = surface.projection_ring_grid.get() {
        return Ok(grid);
    }
    let [u0, u1] = surface.domain_u()?;
    let [v0, v1] = surface.domain_v()?;
    let mut grid = vec![Vec3::default(); 4 * RING_EXPONENTS * RING_INDICES];
    for exponent in 1..=RING_EXPONENTS as i32 {
        let offset = 1.0 / 2f64.powi(exponent);
        let e = exponent as usize - 1;
        let v_lo = v0 + (v1 - v0) * offset;
        let v_hi = v1 - (v1 - v0) * offset;
        let u_lo = u0 + (u1 - u0) * offset;
        let u_hi = u1 - (u1 - u0) * offset;
        for index in 0..=32 {
            let u = u0 + (u1 - u0) * index as f64 / 32.0;
            grid[ring_slot(0, e, index as usize)] = surface.evaluate(u, v_lo)?;
            grid[ring_slot(1, e, index as usize)] = surface.evaluate(u, v_hi)?;
        }
        for index in 0..=32 {
            let v = v0 + (v1 - v0) * index as f64 / 32.0;
            grid[ring_slot(2, e, index as usize)] = surface.evaluate(u_lo, v)?;
            grid[ring_slot(3, e, index as usize)] = surface.evaluate(u_hi, v)?;
        }
    }
    Ok(surface.projection_ring_grid.get_or_init(|| grid))
}

/// The LOCAL answer: Newton from the seed grid's single nearest sample (or the
/// linear-revolution foot), with the degenerate-parameterization fallbacks.
///
/// This is the whole of what the general projector returned before
/// 2026-09-14, and it is a local minimum, not the minimum: on a general patch
/// nearly closed in one direction the nearest sample can sit on the far end,
/// and Newton converges there (abc_00000026's thread flanks, 2.16e-2 .. 4.1e-2
/// against a true 1e-13). [`project_point_to_surface_general`] runs it first
/// and keeps its answer wherever no other basin beats it.
fn nearest_seed_answer(
    surface: &NurbsSurface,
    point: Vec3,
    [u0, u1, v0, v1]: [f64; 4],
    closed_u: bool,
    closed_v: bool,
) -> Result<NewtonResult, String> {
    let mut best = NewtonResult {
        u: u0,
        v: v0,
        distance_squared: f64::INFINITY,
        converged: false,
    };
    nearest_sample(projection_seed_grid(surface)?, point, &mut best);
    if let Some(revolution) = project_linear_revolution(surface, point)? {
        if revolution.distance * revolution.distance < best.distance_squared {
            best.u = revolution.u;
            best.v = revolution.v;
            best.distance_squared = revolution.distance * revolution.distance;
        }
    }
    let first_newton = surface_newton(
        surface,
        point,
        best.u,
        best.v,
        [u0, u1, v0, v1],
        closed_u,
        closed_v,
    )?;
    if first_newton.distance_squared < best.distance_squared {
        best = first_newton;
    }
    let (_, su, sv) = surface.deriv1(best.u, best.v)?;
    let degenerate = su.cross(sv).length() <= 1e-5 * (1.0 + su.length() + sv.length());
    if degenerate || !first_newton.converged {
        let mut grid = best;
        nearest_sample(projection_dense_grid(surface)?, point, &mut grid);
        if grid.distance_squared < best.distance_squared {
            best = grid;
        }
        let polished = surface_newton(
            surface,
            point,
            grid.u,
            grid.v,
            [u0, u1, v0, v1],
            closed_u,
            closed_v,
        )?;
        if polished.distance_squared < best.distance_squared {
            best = polished;
        }

        let (_, su, sv) = surface.deriv1(best.u, best.v)?;
        if su.cross(sv).length() <= 1e-5 * (1.0 + su.length() + sv.length()) {
            let ring_grid = projection_ring_grid(surface)?;
            let mut ring = best;
            // Read the pre-evaluated ring points at the exact same parameter
            // positions the live scans used (side/exponent/index → `ring_slot`),
            // preserving scan order and argmin tie-breaking for bit-identity.
            let scan = |side: usize,
                        exponent_index: usize,
                        along_u: bool,
                        fixed: f64,
                        candidate: &mut NewtonResult| {
                for index in 0..=32 {
                    let moving = if along_u {
                        u0 + (u1 - u0) * index as f64 / 32.0
                    } else {
                        v0 + (v1 - v0) * index as f64 / 32.0
                    };
                    let (u, v) = if along_u {
                        (moving, fixed)
                    } else {
                        (fixed, moving)
                    };
                    let distance_squared = ring_grid
                        [ring_slot(side, exponent_index, index as usize)]
                    .sub(point)
                    .length_squared();
                    if distance_squared < candidate.distance_squared {
                        candidate.u = u;
                        candidate.v = v;
                        candidate.distance_squared = distance_squared;
                    }
                }
            };
            for exponent in 1..=22 {
                let offset = 1.0 / 2f64.powi(exponent);
                let e = exponent as usize - 1;
                if (best.v - v0).abs() <= (v1 - v0) * 0.02 {
                    scan(0, e, true, v0 + (v1 - v0) * offset, &mut ring);
                }
                if (best.v - v1).abs() <= (v1 - v0) * 0.02 {
                    scan(1, e, true, v1 - (v1 - v0) * offset, &mut ring);
                }
                if (best.u - u0).abs() <= (u1 - u0) * 0.02 {
                    scan(2, e, false, u0 + (u1 - u0) * offset, &mut ring);
                }
                if (best.u - u1).abs() <= (u1 - u0) * 0.02 {
                    scan(3, e, false, u1 - (u1 - u0) * offset, &mut ring);
                }
            }
            if ring.distance_squared < best.distance_squared {
                best = ring;
            }
            let polished = surface_newton(
                surface,
                point,
                ring.u,
                ring.v,
                [u0, u1, v0, v1],
                closed_u,
                closed_v,
            )?;
            if polished.distance_squared < best.distance_squared {
                best = polished;
            }
        }
    }
    Ok(best)
}

/// Escape hatch for A/B measurement: `BREP_PROJECTION_GLOBAL=0` returns the
/// local answer alone ([`nearest_seed_answer`], the pre-2026-09-14 projector),
/// so a population run can be repeated with and without the global stage from
/// one binary. Read once.
fn global_stage_enabled() -> bool {
    switch!("BREP_PROJECTION_GLOBAL", true)
}

/// `BREP_PROJECTION_GLOBAL_SITES=<a,b,…>`: the global stage's answer is kept
/// only for call sites whose `file:line` contains one of the comma-separated
/// substrings, and the local answer is returned everywhere else — so a result
/// that moves can be attributed to the call site that moved it.
/// `BREP_PROJECTION_GLOBAL_EXCEPT=<a,b,…>` is the complement: every site but
/// those. Unset: every site. Read once.
/// Whether a `BREP_PROJECTION_GLOBAL_SITES`/`_EXCEPT` filter is set, i.e.
/// whether [`project_point_to_surface`]'s answer can depend on its call site.
pub(crate) fn global_site_filter_active() -> bool {
    // Read once per process, like the site lists `global_answer_admitted`
    // reads: the common reader asks this for every probe (two `getenv` calls,
    // ~3.7% of the elephant's B12 prefix on the production sampler,
    // 2026-11-02), and nothing sets these variables after start-up.
    static ACTIVE: std::sync::OnceLock<bool> = std::sync::OnceLock::new();
    *ACTIVE.get_or_init(|| {
        std::env::var_os("BREP_PROJECTION_GLOBAL_SITES").is_some() || std::env::var_os("BREP_PROJECTION_GLOBAL_EXCEPT").is_some()
    })
}

fn global_answer_admitted(caller: &std::panic::Location<'_>) -> bool {
    fn list(name: &str) -> Option<Vec<String>> {
        std::env::var(name)
            .ok()
            .map(|value| value.split(',').map(str::to_string).filter(|site| !site.is_empty()).collect())
    }
    static SITES: std::sync::OnceLock<(Option<Vec<String>>, Option<Vec<String>>)> =
        std::sync::OnceLock::new();
    let (only, except) = SITES.get_or_init(|| {
        (list("BREP_PROJECTION_GLOBAL_SITES"), list("BREP_PROJECTION_GLOBAL_EXCEPT"))
    });
    if only.is_none() && except.is_none() {
        return true;
    }
    let location = format!("{}:{}", caller.file(), caller.line());
    let named = |sites: &Vec<String>| sites.iter().any(|site| location.contains(site.as_str()));
    only.as_ref().is_none_or(named) && !except.as_ref().is_some_and(named)
}

/// `BREP_PROJECTION_AUDIT=<dir>`: every query on which the global stage
/// replaces the local answer appends one tab-separated line to
/// `<dir>/projection-audit-<pid>.tsv` — the call site, the local and the
/// global distance, both feet's `(u, v)` and the surface's shape. Per process,
/// because the case gate forks a child per case and loses its stderr.
fn audit_record(caller: &std::panic::Location<'_>, surface: &NurbsSurface, local: &NewtonResult, global: &NewtonResult) {
    use std::io::Write;
    static SINK: std::sync::OnceLock<Option<std::sync::Mutex<std::fs::File>>> =
        std::sync::OnceLock::new();
    let sink = SINK.get_or_init(|| {
        let directory = std::env::var_os("BREP_PROJECTION_AUDIT")?;
        let path = std::path::Path::new(&directory)
            .join(format!("projection-audit-{}.tsv", std::process::id()));
        std::fs::OpenOptions::new()
            .create(true)
            .append(true)
            .open(path)
            .ok()
            .map(std::sync::Mutex::new)
    });
    if let Some(file) = sink {
        if let Ok(mut file) = file.lock() {
            let _ = writeln!(
                file,
                "{}:{}\t{:.6e}\t{:.6e}\t{:.9}\t{:.9}\t{:.9}\t{:.9}\t{}x{} cp {}x{}",
                caller.file(),
                caller.line(),
                local.distance_squared.sqrt(),
                global.distance_squared.sqrt(),
                local.u,
                local.v,
                global.u,
                global.v,
                surface.degree_u,
                surface.degree_v,
                surface.control_points.len(),
                surface.control_points.first().map(Vec::len).unwrap_or(0),
            );
        }
    }
}

/// The point of a general surface nearest `point`: the least local minimum of
/// the distance over the surface's whole domain.
///
/// **What it does.** First the local answer ([`nearest_seed_answer`]: Newton
/// from the nearest seed-grid sample, with its degenerate fallbacks — the whole
/// projector before 2026-09-14). Then the global stage ([`global_minimum`]):
/// the domain is cut into the cells of the projection lattice (every knot span
/// sampled `max(3, degree + 1)` times in an open direction and
/// `max(8, 4 × degree)` times in a closed one — the seed grid's own density),
/// and each cell is enclosed in a box built from the control points of the
/// surface REFINED to that cell. A NURBS patch with positive weights lies in
/// the convex hull of the control points that support it, so the distance from
/// the query to a cell's box is a rigorous LOWER bound on the distance to every
/// surface point of the cell. Every cell whose bound is below the best answer
/// so far is a candidate basin, and is refined by a descent confined to the
/// cell ([`confined_descent`]: Newton where the Hessian is positive definite,
/// the metric-scaled gradient where it is not, halved until the distance does
/// not rise, so it can end at a minimum but not at a saddle or a maximum),
/// seeded at the cell's nearest lattice node and continued over the domain
/// when the cell's least point is on its edge. The least answer wins. A closed
/// direction's seam is not special: the lattice spans the whole period, the
/// cells on either side of the seam are ordinary cells, and the continuation
/// wraps.
///
/// **What is guaranteed.**
/// * The answer is a point ON the surface, so its distance never under-reads.
/// * Every cell that could hold a point nearer than the answer by more than the
///   resolution has been descended in, unless it already held a verified
///   minimum: a cell left out was excluded by its hull bound, which cannot
///   over-read. [`GlobalStats::hull_lower_bound`] is that certificate: the
///   true distance lies in `[hull_lower_bound, answer]`, always.
/// * **The one step not certified in general: one basin in the cell that holds
///   the least minimum.** A descent finds the basin of its seed. A second basin
///   in any OTHER cell costs nothing — that cell's better basin is still no
///   nearer than the least minimum — but a second local minimum in the cell
///   holding the least minimum can catch the descent seeded at that cell's
///   nearest lattice node, and the least minimum is missed by at most
///   `answer − hull_lower_bound`. That takes a query past the focal distance of
///   part of the cell (farther than its radius of normal curvature on the
///   query's side, where the distance's Hessian `G − d·II` stops being positive
///   definite) or a cell whose image turns back toward the query. A descent that
///   runs out of iterations without a verified minimum fails the same way, with
///   the same bound. Seeding every corner of every candidate cell was measured
///   and changed no answer on the bench.
/// * **Certified on the analytic carriers** — the sphere, torus, cylinder and
///   cone, each a revolution of a circle or a line, and the plane. A lattice cell
///   there is an (azimuth × generatrix) rectangle under half a turn wide. In the
///   cell holding the least minimum the azimuthal derivative of the squared
///   distance, `2 ρ(v) ρ_P sin(λ − λ_P)`, vanishes only on the query's own
///   meridian, and moving toward that meridian lowers the distance from every
///   other point of the cell, so each local minimum over the cell is a local
///   minimum of the planar distance from the query's meridian image to the
///   generatrix over the cell's `v` range — exactly one on a circle arc under
///   half a turn or on a segment. At the focal sets (the axis, the sphere's
///   centre, the tube's centre circle) the minimum is a continuum of equal
///   distances and every foot is right. A general profile of revolution and a
///   general patch are not certified.
/// * Where the local answer is already the least minimum, it is returned
///   unchanged, bit for bit: the global stage replaces it only with a point
///   nearer by more than the resolution.
///
/// **The two numbers it reads.** The *on-surface floor* is `LINEAR_TOLERANCE`,
/// INHERITED unchanged: it is the local Newton's own stopping residual, and a
/// local answer within it of the query is on the surface and nothing is
/// searched. The *resolution* is the one new number, and it is the surface's
/// own: `(degree_u + 1)(degree_v + 1) · ε · scale`, `scale` the largest
/// control-point coordinate magnitude — the rounding of one evaluation, which
/// sums that many terms of that size. Every box is grown by it, and no
/// improvement finer than it is taken.
///
/// **What it costs.** A query settled by the floor costs what the local answer
/// always cost. Any other query builds the cell enclosure once per surface (one
/// knot refinement of the net to the lattice, cached on the surface beside the
/// seed grid), walks a bounding-sphere tree over the cells, and runs one
/// descent per candidate cell the hull bound does not exclude.
#[track_caller]
pub(crate) fn project_point_to_surface_general(
    surface: &NurbsSurface,
    point: Vec3,
) -> Result<SurfaceProjection, String> {
    let _lap = crate::projection_profile::Lap::enter(crate::projection_profile::LANE_GENERAL, surface);
    let [u0, u1] = surface.domain_u()?;
    let [v0, v1] = surface.domain_v()?;
    let (closed_u, closed_v) = surface.closed_directions()?;
    let local = nearest_seed_answer(surface, point, [u0, u1, v0, v1], closed_u, closed_v)?;
    let mut best = local;
    if global_stage_enabled() {
        global_minimum(
            surface,
            point,
            [u0, u1, v0, v1],
            (closed_u, closed_v),
            &mut best,
            &mut GlobalStats::default(),
        )?;
        if best.u != local.u || best.v != local.v {
            let caller = std::panic::Location::caller();
            if global_answer_admitted(caller) {
                audit_record(caller, surface, &local, &best);
            } else {
                best = local;
            }
        }
    }
    let projected = surface.evaluate(best.u, best.v)?;
    Ok(SurfaceProjection {
        u: best.u,
        v: best.v,
        point: projected,
        distance: projected.sub(point).length(),
    })
}

/// The single-seed inversion by itself: the closed form on an analytic
/// carrier, otherwise [`nearest_seed_answer`] — Newton from the seed grid's
/// nearest sample, WITHOUT the global stage. Its distance is an upper bound and
/// its foot a local minimum. It is not a nearest-point query: it exists for a
/// caller that asks a question ABOUT that inversion, and there is one —
/// `joint_branch_pcurves` (`io/step_import/builder/rims.rs`) offers a loop the
/// joint branch only when this inversion alternates between branches along it,
/// which it does on a carrier that comes back within one seed-grid spacing of
/// itself (`abc_00000026`'s nearly closed thread flanks).
pub(crate) fn project_point_to_surface_from_nearest_seed(
    surface: &NurbsSurface,
    point: Vec3,
) -> Result<SurfaceProjection, String> {
    let _lap = crate::projection_profile::Lap::enter(crate::projection_profile::LANE_FROM_NEAREST_SEED, surface);
    if let Some(analytic) = surface.analytic() {
        if let Some(projection) = analytic.project(surface, point) {
            return Ok(projection);
        }
    }
    if let Some(ellipsoid) = surface.affine_sphere() {
        if let Some(projection) = ellipsoid.project(surface, point) {
            return Ok(projection);
        }
    }
    let [u0, u1] = surface.domain_u()?;
    let [v0, v1] = surface.domain_v()?;
    let (closed_u, closed_v) = surface.closed_directions()?;
    let local = nearest_seed_answer(surface, point, [u0, u1, v0, v1], closed_u, closed_v)?;
    let projected = surface.evaluate(local.u, local.v)?;
    Ok(SurfaceProjection {
        u: local.u,
        v: local.v,
        point: projected,
        distance: projected.sub(point).length(),
    })
}

/// Both answers for one query, and what the global stage did — the bench's
/// seam (`examples/projector_bench.rs`). Not for kernel callers.
#[doc(hidden)]
pub fn project_point_to_surface_general_lanes(
    surface: &NurbsSurface,
    point: Vec3,
    run_global: bool,
) -> Result<(SurfaceProjection, GlobalStats), String> {
    let [u0, u1] = surface.domain_u()?;
    let [v0, v1] = surface.domain_v()?;
    let (closed_u, closed_v) = surface.closed_directions()?;
    let mut best = nearest_seed_answer(surface, point, [u0, u1, v0, v1], closed_u, closed_v)?;
    let mut stats = GlobalStats::default();
    if run_global {
        global_minimum(surface, point, [u0, u1, v0, v1], (closed_u, closed_v), &mut best, &mut stats)?;
    }
    let projected = surface.evaluate(best.u, best.v)?;
    Ok((
        SurfaceProjection {
            u: best.u,
            v: best.v,
            point: projected,
            distance: projected.sub(point).length(),
        },
        stats,
    ))
}

/// How many basins the cells of one query hold — the bench's measure of the
/// global stage's one uncertified step (see [`project_point_to_surface_general`]).
#[doc(hidden)]
#[derive(Clone, Debug, Default)]
pub struct BasinCensus {
    /// Cells whose hull bound is below the answer's distance: every cell the
    /// global stage could have descended in.
    pub cells: usize,
    /// Descents run: one from each corner of those cells and one from the middle.
    pub descents: usize,
    /// Descents that stopped without a verified minimum.
    pub unconverged: usize,
    /// Cells where two verified minima differ in distance by more than `bar`.
    /// Distances within the on-surface floor count as equal: the descent stops
    /// there, so two feet under it are one foot polished to different depths.
    pub cells_with_two_basins: usize,
    /// Of those, cells whose rectangle holds the least foot any descent found:
    /// the only cells where a second basin can cost the answer anything.
    pub foot_cells_with_two_basins: usize,
    /// The least distance any descent reached, and where.
    pub least: f64,
    pub least_uv: (f64, f64),
    /// Every descent in a two-basin cell that holds the least foot: the cell,
    /// its rectangle, the seed, where it stopped, its distance, and whether that
    /// is a verified minimum.
    pub foot_cell_descents: Vec<(usize, [f64; 4], (f64, f64), (f64, f64), f64, bool)>,
}

/// Descend in every cell whose hull bound is below `answer_distance` from each
/// of its corners and its middle, and count the cells whose verified minima
/// disagree by more than `bar`. For the bench only: it costs five descents per
/// cell, which the projector itself was measured not to need.
#[doc(hidden)]
pub fn project_point_to_surface_basin_census(
    surface: &NurbsSurface,
    point: Vec3,
    answer_distance: f64,
    bar: f64,
) -> Result<BasinCensus, String> {
    let mut census = BasinCensus {
        least: f64::INFINITY,
        ..BasinCensus::default()
    };
    let Some(cells) = projection_cells(surface)? else {
        return Ok(census);
    };
    let columns = cells.vs.len() - 1;
    let mut spreads: Vec<(usize, f64)> = Vec::new();
    let mut runs: Vec<(usize, [f64; 4], (f64, f64), (f64, f64), f64, bool)> = Vec::new();
    for (cell, cell_box) in cells.boxes.iter().enumerate() {
        if cell_box.lower_bound(point) >= answer_distance {
            continue;
        }
        census.cells += 1;
        let (row, column) = (cell / columns, cell % columns);
        let rectangle = [cells.us[row], cells.us[row + 1], cells.vs[column], cells.vs[column + 1]];
        let middle = ((rectangle[0] + rectangle[1]) * 0.5, (rectangle[2] + rectangle[3]) * 0.5);
        let (mut low, mut high) = (f64::INFINITY, f64::NEG_INFINITY);
        for seed in [
            (rectangle[0], rectangle[2]),
            (rectangle[1], rectangle[2]),
            (rectangle[0], rectangle[3]),
            (rectangle[1], rectangle[3]),
            middle,
        ] {
            census.descents += 1;
            let (found, _) = confined_descent(surface, point, seed, rectangle, (false, false))?;
            let distance = found.distance_squared.sqrt();
            runs.push((cell, rectangle, seed, (found.u, found.v), distance, found.converged));
            if distance < census.least {
                census.least = distance;
                census.least_uv = (found.u, found.v);
            }
            if !found.converged {
                census.unconverged += 1;
                continue;
            }
            low = low.min(distance.max(LINEAR_TOLERANCE));
            high = high.max(distance.max(LINEAR_TOLERANCE));
        }
        if high - low > bar {
            spreads.push((cell, high - low));
        }
    }
    census.cells_with_two_basins = spreads.len();
    let (u, v) = census.least_uv;
    let foot_cells: Vec<usize> = spreads
        .iter()
        .map(|&(cell, _)| cell)
        .filter(|&cell| {
            let (row, column) = (cell / columns, cell % columns);
            cells.us[row] <= u && u <= cells.us[row + 1] && cells.vs[column] <= v && v <= cells.vs[column + 1]
        })
        .collect();
    census.foot_cells_with_two_basins = foot_cells.len();
    census.foot_cell_descents = runs.into_iter().filter(|run| foot_cells.contains(&run.0)).collect();
    Ok(census)
}

/// What the global stage did on one query.
#[doc(hidden)]
#[derive(Clone, Copy, Debug, Default)]
pub struct GlobalStats {
    /// The local answer was within the on-surface floor; nothing searched.
    pub settled_by_floor: bool,
    /// Cells whose hull bound admitted them.
    pub candidates: usize,
    /// Confined Newtons run (candidates not already holding a converged foot).
    pub refinements: usize,
    /// Continuations across the domain from a cell edge.
    pub continuations: usize,
    /// The global stage replaced the local answer.
    pub replaced: bool,
    /// The least hull bound over every cell — the true distance is never
    /// below it (0 when the floor settled the query).
    pub hull_lower_bound: f64,
}

/// One lattice cell's enclosure: an oriented box around the control points
/// that support the cell, in an orthonormal frame fitted to the cell.
#[derive(Clone, Debug)]
struct CellBox {
    axes: [Vec3; 3],
    low: [f64; 3],
    high: [f64; 3],
}

impl CellBox {
    /// Distance from `point` to the box: a lower bound on the distance to
    /// every surface point of the cell.
    fn lower_bound(&self, point: Vec3) -> f64 {
        let mut squared = 0.0;
        for axis in 0..3 {
            let coordinate = point.dot(self.axes[axis]);
            let excess = (self.low[axis] - coordinate).max(coordinate - self.high[axis]).max(0.0);
            squared += excess * excess;
        }
        squared.sqrt()
    }
}

/// A node of the bounding-sphere tree over the cells. A leaf names its cell;
/// an internal node its two children.
#[derive(Clone, Copy, Debug)]
struct CellTreeNode {
    centre: Vec3,
    radius: f64,
    children: Option<(u32, u32)>,
    cell: u32,
}

/// The cached enclosure of every projection lattice cell (see
/// [`project_point_to_surface_general`]).
#[derive(Clone, Debug)]
pub(crate) struct ProjectionCells {
    us: Vec<f64>,
    vs: Vec<f64>,
    /// `us.len() × vs.len()` lattice points, row-major in u.
    nodes: Vec<Vec3>,
    /// `(us.len() - 1) × (vs.len() - 1)` cells, row-major in u.
    boxes: Vec<CellBox>,
    /// The tree's root is the LAST node.
    tree: Vec<CellTreeNode>,
    /// One box per tree node: a leaf's is its cell's box, an internal node's
    /// holds both children's boxes grown by `node_margin` on every side (see
    /// [`hull_candidates`]). Empty when the surface has no usable scale.
    node_boxes: Vec<CellBox>,
    /// The growth of each internal node's box over its children's.
    node_margin: f64,
    /// The largest control-point coordinate magnitude.
    scale: f64,
    resolution: f64,
}

/// The projection lattice's parameters along one direction: every knot span
/// cut into `samples` equal pieces, the seed grid's density, shared span ends
/// listed once.
fn lattice_parameters(knots: &[f64], degree: usize, closed: bool) -> Vec<f64> {
    let [start, end] = crate::curve::knot_domain(knots, degree);
    let samples = if closed {
        8usize.max(degree * 4)
    } else {
        3usize.max(degree + 1)
    };
    let mut breaks = vec![start];
    breaks.extend(interior_knots(knots, degree));
    breaks.push(end);
    let mut parameters = Vec::with_capacity((breaks.len() - 1) * samples + 1);
    for pair in breaks.windows(2) {
        for index in 0..samples {
            parameters.push(pair[0] + (pair[1] - pair[0]) * index as f64 / samples as f64);
        }
    }
    parameters.push(end);
    parameters
}

/// Raise every lattice parameter to full multiplicity in the knot vector, so
/// each lattice cell is one Bézier piece of the refined net.
///
/// `net[i]` is the i-th control point along the refined direction, held as a
/// row across the other direction, and every row takes the same combination.
/// Knot refinement in one pass (Piegl & Tiller, *The NURBS Book*, A5.4), in
/// homogeneous coordinates, so a rational net refines exactly and the cost is
/// linear in the refined net's size.
fn refine_to_lattice(net: &mut Vec<Vec<Vec4>>, knots: &mut Vec<f64>, degree: usize, parameters: &[f64]) {
    let p = degree;
    let n = net.len() - 1;
    let mut inserted = Vec::new();
    for &parameter in parameters {
        let multiplicity = knots.iter().filter(|&&knot| knot == parameter).count();
        for _ in multiplicity..p {
            inserted.push(parameter);
        }
    }
    if inserted.is_empty() || p == 0 {
        return;
    }
    inserted.sort_by(f64::total_cmp);
    let find_span = |parameter: f64| -> usize {
        if parameter >= knots[n + 1] {
            return n;
        }
        (knots.partition_point(|&knot| knot <= parameter) - 1).clamp(p, n)
    };
    let r = inserted.len() - 1;
    let m = n + p + 1;
    let a = find_span(inserted[0]);
    let b = find_span(inserted[r]) + 1;
    let columns = net[0].len();
    let blank = vec![
        Vec4 {
            x: 0.0,
            y: 0.0,
            z: 0.0,
            w: 0.0,
        };
        columns
    ];
    let mut refined = vec![blank; n + r + 2];
    let mut refined_knots = vec![0.0; m + r + 2];
    for j in 0..=a - p {
        refined[j] = net[j].clone();
    }
    for j in b - 1..=n {
        refined[j + r + 1] = net[j].clone();
    }
    refined_knots[..=a].copy_from_slice(&knots[..=a]);
    for j in b + p..=m {
        refined_knots[j + r + 1] = knots[j];
    }
    let mut i = b + p - 1;
    let mut k = b + p + r;
    for j in (0..=r).rev() {
        while inserted[j] <= knots[i] && i > a {
            refined[k - p - 1] = net[i - p - 1].clone();
            refined_knots[k] = knots[i];
            k -= 1;
            i -= 1;
        }
        refined[k - p - 1] = refined[k - p].clone();
        for l in 1..=p {
            let index = k - p + l;
            let numerator = refined_knots[k + l] - inserted[j];
            if numerator == 0.0 {
                refined[index - 1] = refined[index].clone();
            } else {
                let alpha = numerator / (refined_knots[k + l] - knots[i - p + l]);
                let (head, tail) = refined.split_at_mut(index);
                for (before, &here) in head[index - 1].iter_mut().zip(&tail[0]) {
                    *before = before.scale(alpha).add(here.scale(1.0 - alpha));
                }
            }
        }
        refined_knots[k] = inserted[j];
        k = k.saturating_sub(1);
    }
    *net = refined;
    *knots = refined_knots;
}

/// The control-point index range supporting the parameter interval
/// `[low, high]`: every basis function non-zero anywhere on it.
fn supporting_range(knots: &[f64], degree: usize, count: usize, low: f64, high: f64) -> (usize, usize) {
    let first_span = knots.partition_point(|&knot| knot <= low).saturating_sub(1);
    let last_span = knots.partition_point(|&knot| knot < high).saturating_sub(1);
    (
        first_span.saturating_sub(degree).min(count - 1),
        last_span.max(first_span).min(count - 1),
    )
}

fn unit_or(vector: Vec3, fallback: Vec3) -> Vec3 {
    let length = vector.length();
    if length > 0.0 && length.is_finite() {
        vector.scale(1.0 / length)
    } else {
        fallback
    }
}

fn enclosing_sphere(a: (Vec3, f64), b: (Vec3, f64)) -> (Vec3, f64) {
    let offset = b.0.sub(a.0);
    let separation = offset.length();
    if separation + b.1 <= a.1 {
        return a;
    }
    if separation + a.1 <= b.1 {
        return b;
    }
    let radius = (separation + a.1 + b.1) * 0.5;
    let centre = a.0.add(offset.scale((radius - a.1) / separation));
    (centre, radius)
}

/// What [`build_cell_tree`] reads besides the spheres: the cells' boxes and
/// the lattice points (row-major, `lattice_columns` per row) that frame each
/// internal node's box, and the margin each internal box grows by.
struct NodeBoxInputs<'a> {
    boxes: &'a [CellBox],
    nodes: &'a [Vec3],
    lattice_columns: usize,
    margin: f64,
}

/// The box of an internal node: framed like a cell's (along u, then the
/// normal of the region's lattice corners), spanning every corner of both
/// children's boxes, grown by `margin` on every side. Unbounded when a frame or
/// an extent is not finite, so it never prunes.
fn enclosing_node_box(corners: [Vec3; 4], children: [&CellBox; 2], margin: f64) -> CellBox {
    let unbounded = || CellBox {
        axes: [Vec3::new(1.0, 0.0, 0.0), Vec3::new(0.0, 1.0, 0.0), Vec3::new(0.0, 0.0, 1.0)],
        low: [f64::NEG_INFINITY; 3],
        high: [f64::INFINITY; 3],
    };
    let [c00, c10, c01, c11] = corners;
    let along_u = c10.sub(c00).add(c11.sub(c01));
    let along_v = c01.sub(c00).add(c11.sub(c10));
    let e1 = unit_or(along_u, unit_or(along_v, Vec3::new(1.0, 0.0, 0.0)));
    let Ok(fallback) = e1.perpendicular() else {
        return unbounded();
    };
    let normal = unit_or(e1.cross(along_v), fallback);
    let e2 = unit_or(normal.cross(e1), fallback);
    let e3 = e1.cross(e2);
    let axes = [e1, e2, e3];
    let mut low = [f64::INFINITY; 3];
    let mut high = [f64::NEG_INFINITY; 3];
    for child in children {
        for corner in 0..8 {
            let mut point = Vec3::default();
            for axis in 0..3 {
                let value = if corner >> axis & 1 == 0 { child.low[axis] } else { child.high[axis] };
                point = point.add(child.axes[axis].scale(value));
            }
            for axis in 0..3 {
                let coordinate = point.dot(axes[axis]);
                low[axis] = low[axis].min(coordinate);
                high[axis] = high[axis].max(coordinate);
            }
        }
    }
    for axis in 0..3 {
        low[axis] -= margin;
        high[axis] += margin;
    }
    if !low.iter().chain(high.iter()).all(|value| value.is_finite()) {
        return unbounded();
    }
    CellBox { axes, low, high }
}

fn build_cell_tree(
    tree: &mut Vec<CellTreeNode>,
    node_boxes: &mut Vec<CellBox>,
    inputs: &NodeBoxInputs<'_>,
    spheres: &[(Vec3, f64)],
    columns: usize,
    [row_low, row_high, column_low, column_high]: [usize; 4],
) -> u32 {
    if row_high - row_low == 1 && column_high - column_low == 1 {
        let cell = row_low * columns + column_low;
        node_boxes.push(inputs.boxes[cell].clone());
        tree.push(CellTreeNode {
            centre: spheres[cell].0,
            radius: spheres[cell].1,
            children: None,
            cell: cell as u32,
        });
        return (tree.len() - 1) as u32;
    }
    let (first, second) = if row_high - row_low >= column_high - column_low {
        let middle = (row_low + row_high) / 2;
        (
            [row_low, middle, column_low, column_high],
            [middle, row_high, column_low, column_high],
        )
    } else {
        let middle = (column_low + column_high) / 2;
        (
            [row_low, row_high, column_low, middle],
            [row_low, row_high, middle, column_high],
        )
    };
    let first = build_cell_tree(tree, node_boxes, inputs, spheres, columns, first);
    let second = build_cell_tree(tree, node_boxes, inputs, spheres, columns, second);
    let a = tree[first as usize];
    let b = tree[second as usize];
    let lattice = |row: usize, column: usize| inputs.nodes[row * inputs.lattice_columns + column];
    node_boxes.push(enclosing_node_box(
        [
            lattice(row_low, column_low),
            lattice(row_high, column_low),
            lattice(row_low, column_high),
            lattice(row_high, column_high),
        ],
        [&node_boxes[first as usize], &node_boxes[second as usize]],
        inputs.margin,
    ));
    // The resolution-inflated leaf spheres already absorb rounding; the merge
    // adds one more rounding of the same order, absorbed by growing the radius
    // by the larger child's own ulp.
    let (centre, radius) = enclosing_sphere((a.centre, a.radius), (b.centre, b.radius));
    tree.push(CellTreeNode {
        centre,
        radius: radius * (1.0 + 4.0 * f64::EPSILON),
        children: Some((first, second)),
        cell: u32::MAX,
    });
    (tree.len() - 1) as u32
}

fn projection_cells(surface: &NurbsSurface) -> Result<Option<&ProjectionCells>, String> {
    if let Some(cells) = surface.projection_cells.get() {
        return Ok(cells.as_ref());
    }
    let cells = build_projection_cells(surface)?;
    Ok(surface.projection_cells.get_or_init(|| cells).as_ref())
}

fn build_projection_cells(surface: &NurbsSurface) -> Result<Option<ProjectionCells>, String> {
    let (closed_u, closed_v) = surface.closed_directions()?;
    let us = lattice_parameters(&surface.knots_u, surface.degree_u, closed_u);
    let vs = lattice_parameters(&surface.knots_v, surface.degree_v, closed_v);
    if us.len() < 2 || vs.len() < 2 {
        return Ok(None);
    }
    let mut scale = 0.0f64;
    for control in surface.control_points.iter().flatten() {
        let point = control.point()?;
        scale = scale.max(point.x.abs()).max(point.y.abs()).max(point.z.abs());
    }
    let resolution =
        ((surface.degree_u + 1) * (surface.degree_v + 1)) as f64 * f64::EPSILON * scale;

    // Refine u (the net's rows), then v (its columns, as rows of the transpose).
    let mut net = surface.control_points.clone();
    let mut knots_u = surface.knots_u.clone();
    refine_to_lattice(&mut net, &mut knots_u, surface.degree_u, &us);
    let columns = net.first().map(Vec::len).unwrap_or(0);
    let mut transposed: Vec<Vec<Vec4>> =
        (0..columns).map(|column| net.iter().map(|row| row[column]).collect()).collect();
    let mut knots_v = surface.knots_v.clone();
    refine_to_lattice(&mut transposed, &mut knots_v, surface.degree_v, &vs);
    let rows = transposed.first().map(Vec::len).unwrap_or(0);
    let columns = transposed.len();
    if rows == 0 || columns == 0 {
        return Ok(None);
    }
    let mut points = vec![Vec3::default(); rows * columns];
    for (column, fibre) in transposed.iter().enumerate() {
        for (row, control) in fibre.iter().enumerate() {
            points[row * columns + column] = control.point()?;
        }
    }

    let mut nodes = Vec::with_capacity(us.len() * vs.len());
    for &u in &us {
        for &v in &vs {
            nodes.push(surface.evaluate(u, v)?);
        }
    }

    let cell_rows = us.len() - 1;
    let cell_columns = vs.len() - 1;
    let mut boxes = Vec::with_capacity(cell_rows * cell_columns);
    let mut spheres = Vec::with_capacity(cell_rows * cell_columns);
    for i in 0..cell_rows {
        let (row_low, row_high) =
            supporting_range(&knots_u, surface.degree_u, rows, us[i], us[i + 1]);
        for j in 0..cell_columns {
            let (column_low, column_high) =
                supporting_range(&knots_v, surface.degree_v, columns, vs[j], vs[j + 1]);
            let at = |row: usize, column: usize| points[row * columns + column];
            let c00 = at(row_low, column_low);
            let c10 = at(row_high, column_low);
            let c01 = at(row_low, column_high);
            let c11 = at(row_high, column_high);
            let along_u = c10.sub(c00).add(c11.sub(c01));
            let along_v = c01.sub(c00).add(c11.sub(c10));
            let e1 = unit_or(along_u, unit_or(along_v, Vec3::new(1.0, 0.0, 0.0)));
            let normal = unit_or(e1.cross(along_v), e1.perpendicular()?);
            let e2 = unit_or(normal.cross(e1), e1.perpendicular()?);
            let e3 = e1.cross(e2);
            let axes = [e1, e2, e3];
            let mut low = [f64::INFINITY; 3];
            let mut high = [f64::NEG_INFINITY; 3];
            for row in row_low..=row_high {
                for column in column_low..=column_high {
                    let point = at(row, column);
                    for axis in 0..3 {
                        let coordinate = point.dot(axes[axis]);
                        low[axis] = low[axis].min(coordinate);
                        high[axis] = high[axis].max(coordinate);
                    }
                }
            }
            for axis in 0..3 {
                low[axis] -= resolution;
                high[axis] += resolution;
            }
            let mut centre = Vec3::default();
            let mut half_diagonal_squared = 0.0;
            for axis in 0..3 {
                centre = centre.add(axes[axis].scale((low[axis] + high[axis]) * 0.5));
                let half = (high[axis] - low[axis]) * 0.5;
                half_diagonal_squared += half * half;
            }
            if !low.iter().chain(high.iter()).all(|value| value.is_finite()) {
                return Ok(None);
            }
            spheres.push((centre, half_diagonal_squared.sqrt() + resolution));
            boxes.push(CellBox { axes, low, high });
        }
    }
    let mut tree = Vec::with_capacity(2 * boxes.len());
    let mut node_boxes = Vec::with_capacity(2 * boxes.len());
    // Each internal box grows by a billionth of the surface's scale over its
    // children: far above the rounding of the corners it spans and of the
    // bound read from it, so a box that excludes a point excludes every cell
    // under it (see `hull_candidates`).
    let node_margin = NODE_BOX_MARGIN * scale;
    let inputs = NodeBoxInputs { boxes: &boxes, nodes: &nodes, lattice_columns: vs.len(), margin: node_margin };
    build_cell_tree(&mut tree, &mut node_boxes, &inputs, &spheres, cell_columns, [0, cell_rows, 0, cell_columns]);
    if !(node_margin > 0.0 && node_margin.is_finite()) {
        node_boxes = Vec::new();
    }
    Ok(Some(ProjectionCells {
        us,
        vs,
        nodes,
        boxes,
        tree,
        node_boxes,
        node_margin,
        scale,
        resolution,
    }))
}

/// First- and second-order optimality of `(u, v)` for the distance over the
/// rectangle: stationary on the coordinates the rectangle leaves free (the
/// descent's own cosine test), with a positive definite Hessian there. A
/// `periodic` direction has no edge to be pinned against: its seam is interior.
fn optimality(
    derivatives: &[[Vec3; 3]; 3],
    point: Vec3,
    (u, v): (f64, f64),
    [ua, ub, va, vb]: [f64; 4],
    periodic: (bool, bool),
) -> Optimality {
    let residual = derivatives[0][0].sub(point);
    let residual_length = residual.length();
    let su = derivatives[1][0];
    let sv = derivatives[0][1];
    let f = su.dot(residual);
    let g = sv.dot(residual);
    let metric_u = su.length_squared();
    let metric_v = sv.length_squared();
    let stationary_u = metric_u.sqrt() * residual_length <= EPSILON
        || f.abs() <= 1e-10 * metric_u.sqrt() * residual_length;
    let stationary_v = metric_v.sqrt() * residual_length <= EPSILON
        || g.abs() <= 1e-10 * metric_v.sqrt() * residual_length;
    let pinned_u = !periodic.0 && ((u <= ua && f > 0.0) || (u >= ub && f < 0.0));
    let pinned_v = !periodic.1 && ((v <= va && g > 0.0) || (v >= vb && g < 0.0));
    let j00 = derivatives[2][0].dot(residual) + metric_u;
    let j01 = derivatives[1][1].dot(residual) + su.dot(sv);
    let j11 = derivatives[0][2].dot(residual) + metric_v;
    let determinant = j00 * j11 - j01 * j01;
    let convex = match (!pinned_u, !pinned_v) {
        (true, true) => j00 > 0.0 && determinant > 0.0,
        (true, false) => j00 > 0.0,
        (false, true) => j11 > 0.0,
        (false, false) => true,
    };
    Optimality {
        residual_length,
        gradient: (f, g),
        metric: (metric_u, metric_v),
        hessian: (j00, j01, j11),
        determinant,
        pinned: (pinned_u, pinned_v),
        convex,
        minimum: residual_length <= LINEAR_TOLERANCE
            || ((stationary_u || pinned_u) && (stationary_v || pinned_v) && convex),
    }
}

struct Optimality {
    residual_length: f64,
    gradient: (f64, f64),
    metric: (f64, f64),
    hessian: (f64, f64, f64),
    determinant: f64,
    pinned: (bool, bool),
    convex: bool,
    minimum: bool,
}

fn is_verified_minimum(
    surface: &NurbsSurface,
    point: Vec3,
    at: (f64, f64),
    rectangle: [f64; 4],
    periodic: (bool, bool),
) -> Result<bool, String> {
    let derivatives = surface.derivatives_small(at.0, at.1, 2)?;
    Ok(optimality(&derivatives, point, at, rectangle, periodic).minimum)
}

/// A descent to a local minimum of the distance over the rectangle
/// `[ua, ub] × [va, vb]`, from a seed inside it.
///
/// Newton on the gradient converges to ANY critical point — a saddle or a
/// maximum as readily as a minimum — and reads convergence there, so every
/// step here must lower the distance: the Newton step where the Hessian is
/// positive definite on the free coordinates, the metric-scaled gradient step
/// where it is not, halved until the distance does not rise. A coordinate
/// pinned at the rectangle's edge by a gradient pointing out of it is held
/// there and the other takes the one-dimensional step, so a minimum ON the edge
/// converges as one (the Karush-Kuhn-Tucker point) instead of stalling.
///
/// Returns the best iterate, whether it is a verified minimum (stationary on
/// the free coordinates with a positive definite Hessian there, or within the
/// on-surface floor), and whether it lies on the rectangle's edge.
fn confined_descent(
    surface: &NurbsSurface,
    point: Vec3,
    seed: (f64, f64),
    rectangle: [f64; 4],
    periodic: (bool, bool),
) -> Result<(NewtonResult, bool), String> {
    let [ua, ub, va, vb] = rectangle;
    let mut u = fit_parameter(seed.0, ua, ub, periodic.0);
    let mut v = fit_parameter(seed.1, va, vb, periodic.1);
    let mut converged = false;
    let mut current = surface.evaluate(u, v)?.sub(point).length_squared();
    for _ in 0..MAX_NEWTON_ITERATIONS {
        let derivatives = surface.derivatives_small(u, v, 2)?;
        let state = optimality(&derivatives, point, (u, v), rectangle, periodic);
        current = state.residual_length * state.residual_length;
        if state.minimum {
            converged = true;
            break;
        }
        let (f, g) = state.gradient;
        let (metric_u, metric_v) = state.metric;
        let (j00, j01, j11) = state.hessian;
        let determinant = state.determinant;
        let (free_u, free_v) = (!state.pinned.0, !state.pinned.1);
        let (mut du, mut dv) = match (free_u, free_v) {
            (true, true) if state.convex => (
                (-f * j11 + g * j01) / determinant,
                (-g * j00 + f * j01) / determinant,
            ),
            (true, false) if state.convex => (-f / j00, 0.0),
            (false, true) if state.convex => (0.0, -g / j11),
            _ => (
                if free_u && metric_u > 0.0 { -f / metric_u } else { 0.0 },
                if free_v && metric_v > 0.0 { -g / metric_v } else { 0.0 },
            ),
        };
        if !(du.is_finite() && dv.is_finite()) || (du == 0.0 && dv == 0.0) {
            break;
        }
        let mut moved = false;
        // The step actually taken, a whole period removed across a seam.
        let taken = |next: f64, here: f64, low: f64, high: f64, wraps: bool| {
            let raw = next - here;
            if wraps {
                raw - (high - low) * (raw / (high - low)).round()
            } else {
                raw
            }
        };
        for _ in 0..40 {
            let next_u = fit_parameter(u + du, ua, ub, periodic.0);
            let next_v = fit_parameter(v + dv, va, vb, periodic.1);
            if next_u == u && next_v == v {
                break;
            }
            let trial = surface.evaluate(next_u, next_v)?.sub(point).length_squared();
            if trial <= current {
                moved = taken(next_u, u, ua, ub, periodic.0).abs() > 1e-15 * (ub - ua)
                    || taken(next_v, v, va, vb, periodic.1).abs() > 1e-15 * (vb - va);
                u = next_u;
                v = next_v;
                current = trial;
                break;
            }
            du *= 0.5;
            dv *= 0.5;
        }
        if !moved {
            break;
        }
    }
    let result = NewtonResult {
        u,
        v,
        distance_squared: current,
        converged,
    };
    let on_edge =
        (!periodic.0 && (u <= ua || u >= ub)) || (!periodic.1 && (v <= va || v >= vb));
    Ok((result, on_edge))
}

/// The growth of an internal node's box over its children's, per unit of
/// the surface's scale.
const NODE_BOX_MARGIN: f64 = 1e-9;

/// `BREP_PROJECTION_NODE_BOXES` (default on): the cell-tree walk also reads
/// each internal node's box, not only its sphere. `=0` walks on spheres alone,
/// as before. Read once.
fn node_boxes_enabled() -> bool {
    switch!("BREP_PROJECTION_NODE_BOXES", true)
}

/// The walk of the global stage: every cell whose box comes nearer `point`
/// than `bound`, with its box bound, in the walk's order, and the least bound
/// over everything the walk excluded.
///
/// A node is excluded when its sphere is no nearer than `bound`, and, with
/// `node_boxes`, when its box is not either. Cell spheres are loose on long,
/// thin cells (a 16 × 5632 lattice: about 3000 nodes visited and 200 cells
/// read per query to admit one), and an internal box is not. The box test
/// only removes subtrees whose every cell the cell test would reject, in the
/// same order, so the candidates are the same list to the bit with and
/// without it. Each internal box holds its children's boxes grown by
/// `node_margin` (`m`), and both bounds are read within `e` of their exact
/// value, `e` (below) set by the point's and the surface's magnitudes. A
/// box read at `b ≥ bound` with `b > 2e` is truly at least `b − e > 0` away,
/// so each cell box under it is truly at least `b − e + m` away and reads at
/// least `b − 2e + m ≥ bound` whenever `m ≥ 2e`; the test is skipped for a
/// point so far out that `4e > m` (beyond about 3·10⁴ scales), keeping half
/// of `m` for the rounding of the box corners themselves. Only the excluded
/// bound (the certificate in `GlobalStats::hull_lower_bound`) can differ: it
/// is still a lower bound, read from a tighter box.
fn hull_candidates(cells: &ProjectionCells, point: Vec3, bound: f64, node_boxes: bool) -> (Vec<(f64, usize)>, f64) {
    let read_error = 32.0 * f64::EPSILON * (point.x.abs() + point.y.abs() + point.z.abs() + 4.0 * cells.scale);
    let boxes = node_boxes && !cells.node_boxes.is_empty() && 4.0 * read_error <= cells.node_margin;
    let mut candidates: Vec<(f64, usize)> = Vec::new();
    let mut excluded = f64::INFINITY;
    let mut stack: Vec<u32> = Vec::with_capacity(64);
    stack.push((cells.tree.len() - 1) as u32);
    while let Some(index) = stack.pop() {
        let node = cells.tree[index as usize];
        let sphere_bound = (point.sub(node.centre).length() - node.radius).max(0.0);
        if sphere_bound >= bound {
            excluded = excluded.min(sphere_bound);
            continue;
        }
        match node.children {
            Some((first, second)) => {
                if boxes {
                    let box_bound = cells.node_boxes[index as usize].lower_bound(point);
                    if box_bound >= bound && box_bound > 2.0 * read_error {
                        excluded = excluded.min(box_bound);
                        continue;
                    }
                }
                stack.push(first);
                stack.push(second);
            }
            None => {
                let cell = node.cell as usize;
                let box_bound = cells.boxes[cell].lower_bound(point);
                if box_bound < bound {
                    candidates.push((box_bound, cell));
                } else {
                    excluded = excluded.min(box_bound);
                }
            }
        }
    }
    (candidates, excluded)
}

/// The global stage of [`project_point_to_surface_general`]: replace `best`
/// with the least local minimum over every cell the hull bound admits.
#[allow(clippy::too_many_arguments)]
fn global_minimum(
    surface: &NurbsSurface,
    point: Vec3,
    domains: [f64; 4],
    periodic: (bool, bool),
    best: &mut NewtonResult,
    stats: &mut GlobalStats,
) -> Result<(), String> {
    if best.distance_squared.sqrt() <= LINEAR_TOLERANCE {
        stats.settled_by_floor = true;
        return Ok(());
    }
    let Some(cells) = projection_cells(surface)? else {
        return Ok(());
    };
    let resolution = cells.resolution;
    let columns = cells.vs.len() - 1;
    let columns_u = cells.us.len() - 1;
    let mut bound = best.distance_squared.sqrt() - resolution;

    // Every cell whose box comes nearer than the answer; the least bound over
    // what the walk excluded is the certificate.
    let (mut candidates, excluded) = hull_candidates(cells, point, bound, node_boxes_enabled());
    stats.candidates = candidates.len();
    candidates.sort_by(|a, b| a.0.total_cmp(&b.0));
    stats.hull_lower_bound = candidates
        .first()
        .map_or(excluded, |&(least, _)| least.min(excluded));

    // Cells already holding a verified minimum need no second descent. A foot
    // names ONE cell even when it sits on a lattice line shared by up to four:
    // a neighbour can hold a better basin of its own in its interior, and it
    // was admitted precisely because its bound beat this answer. The local
    // answer is one when it passes the same test the descent applies.
    let cell_of = |u: f64, v: f64| {
        let row = (cells.us.partition_point(|&value| value <= u).max(1) - 1).min(columns_u - 1);
        let column = (cells.vs.partition_point(|&value| value <= v).max(1) - 1).min(columns - 1);
        row * columns + column
    };
    let mut settled: Vec<usize> = Vec::new();
    if is_verified_minimum(surface, point, (best.u, best.v), domains, periodic)? {
        settled.push(cell_of(best.u, best.v));
    }
    for (cell_bound, cell) in candidates {
        if cell_bound >= bound {
            break;
        }
        let row = cell / columns;
        let column = cell % columns;
        let rectangle = [
            cells.us[row],
            cells.us[row + 1],
            cells.vs[column],
            cells.vs[column + 1],
        ];
        if settled.contains(&cell) {
            continue;
        }
        let mut seed = (rectangle[0], rectangle[2]);
        let mut seed_distance = f64::INFINITY;
        for (node_row, node_column) in
            [(row, column), (row + 1, column), (row, column + 1), (row + 1, column + 1)]
        {
            let distance = cells.nodes[node_row * cells.vs.len() + node_column]
                .sub(point)
                .length_squared();
            if distance < seed_distance {
                seed_distance = distance;
                seed = (cells.us[node_row], cells.vs[node_column]);
            }
        }
        stats.refinements += 1;
        let (confined, on_edge) = confined_descent(surface, point, seed, rectangle, (false, false))?;
        let mut found = confined;
        if on_edge && confined.distance_squared.sqrt() < bound {
            // The cell's least point is on its edge and beats the answer:
            // the basin continues past the cell.
            stats.continuations += 1;
            let (continued, _) =
                confined_descent(surface, point, (confined.u, confined.v), domains, periodic)?;
            if continued.distance_squared < found.distance_squared {
                found = continued;
            }
            if continued.converged {
                settled.push(cell_of(continued.u, continued.v));
            }
        }
        if found.distance_squared.sqrt() < bound {
            *best = found;
            bound = best.distance_squared.sqrt() - resolution;
            stats.replaced = true;
            if best.distance_squared.sqrt() <= LINEAR_TOLERANCE {
                return Ok(());
            }
        }
    }
    Ok(())
}



/// Domain handling for a local foot-point Newton walk.
#[derive(Clone, Copy)]
pub(crate) enum FootDomain {
    Clamp,
    Wrap,
    Extended,
}

#[derive(Clone, Copy)]
pub(crate) struct CurveFootPolicy {
    pub domain: FootDomain,
    pub iterations: usize,
    pub slope_guard: f64,
    pub step_limit: f64,
    pub parameter_tolerance: f64,
    pub mode: FootMode,
}

/// Acceptance and convergence differ between a distance minimum and a stationary root.
#[derive(Clone, Copy)]
pub(crate) enum FootMode {
    Monotone,
    Witness,
    Stationary { positive_slope: bool, relative_step: bool },
    Backtracked,
    Planar,
}

/// Local Newton foot. Seeding and enumeration of local minima belong to the caller.
/// Returns the last parameter, best witnessed parameter, and squared distance.
fn curve_foot_newton_state(
    curve: &NurbsCurve,
    point: Vec3,
    seed: f64,
    bracket: [f64; 2],
    policy: CurveFootPolicy,
) -> Result<(f64, f64, f64), String> {
    let fit = |u| match policy.domain {
        FootDomain::Clamp => fit_parameter(u, bracket[0], bracket[1], false),
        FootDomain::Wrap => fit_parameter(u, bracket[0], bracket[1], true),
        FootDomain::Extended => u,
    };
    let extended = matches!(policy.domain, FootDomain::Extended) || matches!(policy.mode, FootMode::Backtracked);
    let planar = matches!(policy.mode, FootMode::Planar);
    let project = |p: Vec3| if planar { Vec3::new(p.x, p.y, 0.0) } else { p };
    let point = project(point);
    let distance = |u| -> Result<f64, String> {
        let p = if extended { curve.derivatives_extended(u, 0)?[0] } else { curve.evaluate(u)? };
        Ok(project(p).sub(point).length())
    };
    let monotone = matches!(policy.mode, FootMode::Monotone | FootMode::Backtracked);
    let witness = matches!(policy.mode, FootMode::Witness);
    let mut u = if witness { seed } else { fit(seed) };
    let mut nearest_u = seed;
    let mut nearest_squared = f64::INFINITY;
    let mut best = if monotone { distance(u)? } else { f64::INFINITY };
    for _ in 0..policy.iterations {
        let derivatives = if extended {
            let values = curve.derivatives_extended(u, 2)?;
            [values[0], values[1], values[2]]
        } else if matches!(policy.mode, FootMode::Stationary { .. })
            || (planar && !crate::curve::small_curve_derivatives_enabled()) {
            let values = curve.derivatives(u, 2)?;
            [values[0], values[1], values[2]]
        } else {
            curve.derivatives_small(u, 2)?
        }.map(project);
        let offset = derivatives[0].sub(point);
        let numerator = offset.dot(derivatives[1]);
        let denominator = derivatives[1].dot(derivatives[1]) + offset.dot(derivatives[2]);
        if witness {
            let squared = offset.length_squared();
            if squared < nearest_squared {
                nearest_u = u;
                nearest_squared = squared;
            }
            let residual_length = squared.sqrt();
            if residual_length <= LINEAR_TOLERANCE
                || numerator.abs() <= EPSILON + 1e-10 * derivatives[1].length() * residual_length {
                break;
            }
        }
        let singular = if planar { denominator.abs() < policy.slope_guard }
            else { denominator.abs() <= policy.slope_guard };
        if singular || (matches!(policy.mode, FootMode::Stationary { positive_slope: true, .. }) && !(denominator > 0.0)) { break; }
        let mut step = if matches!(policy.mode, FootMode::Backtracked) && !(denominator > 0.0) {
            policy.step_limit.copysign(numerator)
        } else {
            (numerator / denominator).clamp(-policy.step_limit, policy.step_limit)
        };
        let mut next = fit(u - step);
        let mut next_distance = if monotone { distance(next)? } else { f64::INFINITY };
        if matches!(policy.mode, FootMode::Backtracked) {
            for _ in 0..30 {
                if next_distance < best { break; }
                step *= 0.5;
                next = fit(u - step);
                next_distance = distance(next)?;
            }
            if !(next_distance < best) { break; }
        } else if monotone && next_distance >= best { break; }
        let moved = if planar || matches!(policy.domain, FootDomain::Extended) { step }
            else if matches!(policy.domain, FootDomain::Wrap) {
                let period = bracket[1] - bracket[0];
                let raw = next - u;
                raw - period * (raw / period).round()
            } else { next - u };
        let tolerance = if matches!(policy.mode, FootMode::Stationary { relative_step: true, .. }) {
            policy.parameter_tolerance * (1.0 + u.abs())
        } else { policy.parameter_tolerance };
        let small = if planar || matches!(policy.mode, FootMode::Backtracked) { moved.abs() < tolerance }
            else { moved.abs() <= tolerance };
        if small && matches!(policy.mode, FootMode::Monotone) { break; }
        u = next;
        best = next_distance;
        if small { break; }
    }
    if witness { return Ok((u, nearest_u, nearest_squared)); }
    if !monotone { best = distance(u)?; }
    Ok((u, u, best * best))
}

pub(crate) fn curve_foot_newton(
    curve: &NurbsCurve, point: Vec3, seed: f64, bracket: [f64; 2], policy: CurveFootPolicy,
) -> Result<(f64, f64), String> {
    let (_, nearest, squared) = curve_foot_newton_state(curve, point, seed, bracket, policy)?;
    Ok((nearest, squared))
}