facett_core/engine/

source.rs

//! **The three traits** — the ONLY things that differ between a map view and a
//! graph view.
//!
//! Everything else a viewer does (cull, tessellate, place labels, composite,
//! pick) is identical whether the thing on screen is a road or a call edge. This
//! module names the difference and nothing else:
//!
//! | trait | question it answers | map answer | graph answer |
//! |---|---|---|---|
//! | [`PositionSource`] | *where is feature `id`?* | Mercator(lat, lon) | the layout's node position |
//! | [`ElevationSource`] | *how high is it?* | terrain heightfield | `0.0`, or a metric (centrality / risk) |
//! | [`Hierarchy`] | *what does "one step deeper" mean?* | the next zoom band | expand this cluster |
//!
//! ## Why `f64` world space
//! Web-Mercator at zoom 22 and a graph drilled six levels deep have the *same*
//! bug: `f32` runs out of mantissa and geometry jitters. The engine therefore
//! keeps world space in `f64` and only becomes `f32` at the **relative-to-eye**
//! split ([`super::rte`]) — one fix, both problems.
//!
//! ## Why object-safe
//! Use case 7 — *a graph drawn on geography* — needs **two different position
//! sources live in the same frame**. That is only expressible if the engine can
//! hold `&[&dyn PositionSource]`, so every method here is object-safe: no
//! generic methods, no `Self: Sized`, no associated types on the hot path.

use std::fmt::Debug;

// ─────────────────────────────────────────────────────────────────────────────
// World space
// ─────────────────────────────────────────────────────────────────────────────

/// A position in **engine world space**, always `f64`.
///
/// What one unit *means* is the [`PositionSource`]'s business: Mercator unit
/// square for a map, layout units for a graph, logical pixels for a flat
/// overlay. The engine only ever subtracts, compares and bounds them.
#[derive(Clone, Copy, Debug, Default, PartialEq)]
pub struct WorldPos {
    pub x: f64,
    pub y: f64,
    /// Filled by the [`ElevationSource`]; a [`PositionSource`] should leave it `0.0`.
    pub z: f64,
}

impl WorldPos {
    #[must_use]
    pub const fn new(x: f64, y: f64, z: f64) -> Self {
        Self { x, y, z }
    }
    #[must_use]
    pub const fn flat(x: f64, y: f64) -> Self {
        Self { x, y, z: 0.0 }
    }
    #[must_use]
    pub fn is_finite(&self) -> bool {
        self.x.is_finite() && self.y.is_finite() && self.z.is_finite()
    }
}

/// An axis-aligned world-space box — the culler's unit of work, and the only
/// thing the [`Hierarchy`] levels are really made of (a coarse level is a set of
/// bounding volumes that stand in for the fine level beneath it).
#[derive(Clone, Copy, Debug, PartialEq)]
pub struct WorldAabb {
    pub min: WorldPos,
    pub max: WorldPos,
}

impl WorldAabb {
    /// The degenerate box at a point — what a POI, a pin or a graph node has.
    #[must_use]
    pub fn point(p: WorldPos) -> Self {
        Self { min: p, max: p }
    }

    /// An empty box that absorbs correctly under [`union`](Self::union).
    #[must_use]
    pub fn empty() -> Self {
        Self {
            min: WorldPos::new(f64::INFINITY, f64::INFINITY, f64::INFINITY),
            max: WorldPos::new(f64::NEG_INFINITY, f64::NEG_INFINITY, f64::NEG_INFINITY),
        }
    }

    #[must_use]
    pub fn is_empty(&self) -> bool {
        self.min.x > self.max.x || self.min.y > self.max.y
    }

    #[must_use]
    pub fn union(self, o: Self) -> Self {
        Self {
            min: WorldPos::new(self.min.x.min(o.min.x), self.min.y.min(o.min.y), self.min.z.min(o.min.z)),
            max: WorldPos::new(self.max.x.max(o.max.x), self.max.y.max(o.max.y), self.max.z.max(o.max.z)),
        }
    }

    /// 2D overlap test — the culler's inner predicate. Z is deliberately ignored:
    /// a top-down or tilted view culls in the ground plane and lets the depth
    /// buffer sort height out.
    #[must_use]
    pub fn overlaps_2d(&self, o: &Self) -> bool {
        self.min.x <= o.max.x && self.max.x >= o.min.x && self.min.y <= o.max.y && self.max.y >= o.min.y
    }

    #[must_use]
    pub fn centre(&self) -> WorldPos {
        WorldPos::new(
            (self.min.x + self.max.x) * 0.5,
            (self.min.y + self.max.y) * 0.5,
            (self.min.z + self.max.z) * 0.5,
        )
    }
}

// ─────────────────────────────────────────────────────────────────────────────
// 1. PositionSource — Mercator | Layout | Identity
// ─────────────────────────────────────────────────────────────────────────────

/// **Where is feature `id`?**
///
/// The single seam between "this is a map" and "this is a graph". A road's
/// position comes from Mercator; a node's comes from a force layout; an overlay
/// glyph's is already in logical pixels. Downstream — culling, tessellation,
/// label collision, picking — cannot tell which it got.
pub trait PositionSource: Debug {
    /// How many features this source addresses. Ids are `0..feature_count()`.
    fn feature_count(&self) -> usize;

    /// The anchor of feature `id` in world space, `z` left at `0.0`.
    ///
    /// Out-of-range ids must return a **non-finite** position rather than
    /// panicking — a stale id from a previous frame is a normal event and the
    /// engine filters non-finite positions out before any work.
    fn position(&self, id: u32) -> WorldPos;

    /// The world-space extent of feature `id`. Point features keep the default.
    /// A road, a building footprint or a cluster hull overrides it — that box is
    /// what the culler and the [`Hierarchy`] index.
    fn bounds(&self, id: u32) -> WorldAabb {
        WorldAabb::point(self.position(id))
    }

    /// Batch projection — **the hot path**. Overriding it is how a columnar
    /// source (Arrow, a GPU-resident buffer) avoids a virtual call per feature.
    fn positions(&self, ids: &[u32], out: &mut Vec<WorldPos>) {
        out.clear();
        out.reserve(ids.len());
        out.extend(ids.iter().map(|&i| self.position(i)));
    }

    /// A **generation counter**. Bump it whenever positions move, so caches
    /// (cull index, pick index, screen grids) know to rebuild. A static source
    /// returns a constant; a live force layout returns its iteration number.
    ///
    /// This is the whole reason [`Layout`] is a distinct type from [`Identity`]:
    /// identical arithmetic, different invalidation.
    fn generation(&self) -> u64 {
        0
    }

    /// Short tag for `state_json` / diagnostics (`"mercator"`, `"layout"`, …).
    fn kind(&self) -> &'static str;
}

/// **Identity** — the position IS the coordinate. Use case 3 (the flat 2D
/// overlay) and any caller that already laid its own content out.
#[derive(Clone, Debug, Default)]
pub struct Identity {
    pts: Vec<[f64; 2]>,
}

impl Identity {
    #[must_use]
    pub fn new(pts: Vec<[f64; 2]>) -> Self {
        Self { pts }
    }
    /// From `f32` pairs — the shape every existing facett layout already has.
    #[must_use]
    pub fn from_f32(pts: &[(f32, f32)]) -> Self {
        Self { pts: pts.iter().map(|&(x, y)| [x as f64, y as f64]).collect() }
    }
}

impl PositionSource for Identity {
    fn feature_count(&self) -> usize {
        self.pts.len()
    }
    fn position(&self, id: u32) -> WorldPos {
        match self.pts.get(id as usize) {
            Some(&[x, y]) => WorldPos::flat(x, y),
            None => WorldPos::new(f64::NAN, f64::NAN, f64::NAN),
        }
    }
    fn kind(&self) -> &'static str {
        "identity"
    }
}

/// **Layout** — positions produced by a layout algorithm that keeps running
/// (force-directed, hierarchical, metro). Arithmetically identical to
/// [`Identity`]; the difference is [`generation`](PositionSource::generation),
/// which every engine-side cache keys on.
#[derive(Clone, Debug, Default)]
pub struct Layout {
    pts: Vec<[f64; 2]>,
    epoch: u64,
}

impl Layout {
    #[must_use]
    pub fn new(pts: Vec<[f64; 2]>) -> Self {
        Self { pts, epoch: 1 }
    }
    /// Replace the positions and bump the generation — the one mutation a
    /// running layout performs per iteration.
    pub fn set(&mut self, pts: Vec<[f64; 2]>) {
        self.pts = pts;
        self.epoch = self.epoch.wrapping_add(1);
    }
    pub fn set_f32(&mut self, pts: &[(f32, f32)]) {
        self.set(pts.iter().map(|&(x, y)| [x as f64, y as f64]).collect());
    }
    #[must_use]
    pub fn points(&self) -> &[[f64; 2]] {
        &self.pts
    }
}

impl PositionSource for Layout {
    fn feature_count(&self) -> usize {
        self.pts.len()
    }
    fn position(&self, id: u32) -> WorldPos {
        match self.pts.get(id as usize) {
            Some(&[x, y]) => WorldPos::flat(x, y),
            None => WorldPos::new(f64::NAN, f64::NAN, f64::NAN),
        }
    }
    fn generation(&self) -> u64 {
        self.epoch
    }
    fn kind(&self) -> &'static str {
        "layout"
    }
}

/// **Projected** — a source that pushes raw `(a, b)` pairs through a pure
/// function. This is the seam a geographic projection plugs into **without
/// `facett-core` learning what a latitude is**: `facett-geomap` supplies
/// `|lon, lat| mercator(lon, lat)` and gets a `PositionSource` back.
///
/// The function must be pure and cheap; it is called once per visible feature
/// per frame (and batched through [`PositionSource::positions`]).
pub struct Projected {
    raw: Vec<[f64; 2]>,
    project: Box<dyn Fn(f64, f64) -> (f64, f64) + Send + Sync>,
    kind: &'static str,
}

impl Debug for Projected {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        f.debug_struct("Projected").field("kind", &self.kind).field("len", &self.raw.len()).finish()
    }
}

impl Projected {
    #[must_use]
    pub fn new(
        raw: Vec<[f64; 2]>,
        kind: &'static str,
        project: impl Fn(f64, f64) -> (f64, f64) + Send + Sync + 'static,
    ) -> Self {
        Self { raw, project: Box::new(project), kind }
    }
}

impl PositionSource for Projected {
    fn feature_count(&self) -> usize {
        self.raw.len()
    }
    fn position(&self, id: u32) -> WorldPos {
        match self.raw.get(id as usize) {
            Some(&[a, b]) => {
                let (x, y) = (self.project)(a, b);
                WorldPos::flat(x, y)
            }
            None => WorldPos::new(f64::NAN, f64::NAN, f64::NAN),
        }
    }
    fn kind(&self) -> &'static str {
        self.kind
    }
}

// ─────────────────────────────────────────────────────────────────────────────
// 2. ElevationSource — terrain | flat | a metric
// ─────────────────────────────────────────────────────────────────────────────

/// **How high is feature `id`?**
///
/// `facett-map3d` is, in its entirety, one implementation of this trait: a 3D
/// map is a 2D map whose elevation is a heightfield instead of `0.0`. A graph in
/// 3D is the same statement with centrality or risk on the Z axis.
pub trait ElevationSource: Debug {
    /// Height of feature `id`, given the world position the [`PositionSource`]
    /// produced (a terrain source samples at `p`; a metric source ignores `p`).
    fn elevation(&self, id: u32, p: WorldPos) -> f64;

    /// The `[min, max]` this source can ever emit — the culler needs it to grow
    /// 2D bounds into 3D ones without sampling every feature.
    fn z_range(&self) -> (f64, f64) {
        (0.0, 0.0)
    }

    /// Batch form; default loops.
    fn elevations(&self, ids: &[u32], pos: &[WorldPos], out: &mut Vec<f64>) {
        out.clear();
        out.reserve(ids.len());
        for (n, &id) in ids.iter().enumerate() {
            out.push(self.elevation(id, pos.get(n).copied().unwrap_or_default()));
        }
    }

    fn kind(&self) -> &'static str;
}

/// **Flat** — `Z = 0`. Use cases 1, 3 and 4. Zero cost: the engine special-cases
/// a `z_range()` of `(0, 0)` and skips the elevation pass entirely.
#[derive(Clone, Copy, Debug, Default)]
pub struct Flat;

impl ElevationSource for Flat {
    fn elevation(&self, _id: u32, _p: WorldPos) -> f64 {
        0.0
    }
    fn elevations(&self, ids: &[u32], _pos: &[WorldPos], out: &mut Vec<f64>) {
        out.clear();
        out.resize(ids.len(), 0.0);
    }
    fn kind(&self) -> &'static str {
        "flat"
    }
}

/// **Metric** — per-feature scalar × a scale. Use cases 5 and 6: node height IS
/// betweenness centrality, or a Mímir risk score.
#[derive(Clone, Debug, Default)]
pub struct Metric {
    values: Vec<f32>,
    scale: f64,
    lo: f64,
    hi: f64,
}

impl Metric {
    #[must_use]
    pub fn new(values: Vec<f32>, scale: f64) -> Self {
        let (mut lo, mut hi) = (f64::INFINITY, f64::NEG_INFINITY);
        for &v in &values {
            let z = v as f64 * scale;
            if z.is_finite() {
                lo = lo.min(z);
                hi = hi.max(z);
            }
        }
        if !lo.is_finite() {
            lo = 0.0;
            hi = 0.0;
        }
        Self { values, scale, lo, hi }
    }
}

impl ElevationSource for Metric {
    fn elevation(&self, id: u32, _p: WorldPos) -> f64 {
        self.values.get(id as usize).map_or(0.0, |&v| v as f64 * self.scale)
    }
    fn z_range(&self) -> (f64, f64) {
        (self.lo, self.hi)
    }
    fn kind(&self) -> &'static str {
        "metric"
    }
}

/// **Sampled** — height from a pure `(x, y) -> z` function plus a declared
/// range. `facett-geomap` wraps its terrain heightfield in this; `facett-core`
/// never learns what a DEM is.
pub struct Sampled {
    sample: Box<dyn Fn(f64, f64) -> f64 + Send + Sync>,
    range: (f64, f64),
    kind: &'static str,
}

impl Debug for Sampled {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        f.debug_struct("Sampled").field("kind", &self.kind).field("range", &self.range).finish()
    }
}

impl Sampled {
    #[must_use]
    pub fn new(
        kind: &'static str,
        range: (f64, f64),
        sample: impl Fn(f64, f64) -> f64 + Send + Sync + 'static,
    ) -> Self {
        Self { sample: Box::new(sample), range, kind }
    }
}

impl ElevationSource for Sampled {
    fn elevation(&self, _id: u32, p: WorldPos) -> f64 {
        (self.sample)(p.x, p.y)
    }
    fn z_range(&self) -> (f64, f64) {
        self.range
    }
    fn kind(&self) -> &'static str {
        self.kind
    }
}

// ─────────────────────────────────────────────────────────────────────────────
// 3. Hierarchy — what "one step deeper" means
// ─────────────────────────────────────────────────────────────────────────────

/// **What does one step deeper mean?**
///
/// ★ The key idea of the whole engine: *a map zoom and a graph cluster-expand are
/// the same operation* — descend one level in a hierarchy of bounding volumes and
/// swap coarse instances for fine ones. Both are this trait. There is one culler
/// and one indirect draw serving both.
///
/// Level `0` is the **coarsest** (Sweden; the repo node). `depth() - 1` is the
/// finest (a street; a call edge).
pub trait Hierarchy: Debug {
    /// Number of levels, `>= 1`.
    fn depth(&self) -> u32;

    /// Which level this camera scale wants. `scale` is world-units-per-pixel's
    /// reciprocal — the same number `Facet::scale_range()` clamps, so a map band
    /// and a graph band are literally the same control.
    fn level_for(&self, scale: f32) -> u32;

    /// Every feature present at `level`, ascending. For a map this is "the tiles
    /// / features of this zoom band"; for a graph, "the visible nodes with the
    /// currently-expanded clusters substituted in".
    fn members(&self, level: u32) -> &[u32];

    /// The children that replace `parent` when you descend from `level` to
    /// `level + 1`. Empty = `parent` is a leaf and survives the descent.
    fn expand(&self, level: u32, parent: u32) -> &[u32];

    /// The inverse of [`expand`](Self::expand): the coarse feature that stands in
    /// for `child` at `level - 1`. Drives "zoom out and my selection follows".
    fn parent_of(&self, level: u32, child: u32) -> Option<u32>;

    fn kind(&self) -> &'static str;
}

/// **Flatten** — one level, everything in it. The honest hierarchy of a small
/// graph or a single-zoom overlay; also the migration floor, so a renderer can
/// move onto the engine before it has a real LOD story.
#[derive(Clone, Debug, Default)]
pub struct Flatten {
    all: Vec<u32>,
}

impl Flatten {
    #[must_use]
    pub fn new(n: usize) -> Self {
        Self { all: (0..n as u32).collect() }
    }
}

impl Hierarchy for Flatten {
    fn depth(&self) -> u32 {
        1
    }
    fn level_for(&self, _scale: f32) -> u32 {
        0
    }
    fn members(&self, _level: u32) -> &[u32] {
        &self.all
    }
    fn expand(&self, _level: u32, _parent: u32) -> &[u32] {
        &[]
    }
    fn parent_of(&self, _level: u32, _child: u32) -> Option<u32> {
        None
    }
    fn kind(&self) -> &'static str {
        "flatten"
    }
}

/// One rung of a [`Bands`] hierarchy.
#[derive(Clone, Debug, Default)]
pub struct Band {
    /// The features drawn at this level.
    pub members: Vec<u32>,
    /// `scale >= min_scale` selects this level (levels are searched coarse→fine,
    /// so the finest band whose threshold is met wins).
    pub min_scale: f32,
    /// `parent -> children` for the descent into the next level.
    pub children: std::collections::BTreeMap<u32, Vec<u32>>,
}

/// **Bands** — THE shared hierarchy. A map zoom pyramid and a graph
/// cluster-expansion tree are both a list of [`Band`]s; nothing in the engine
/// distinguishes them.
#[derive(Clone, Debug, Default)]
pub struct Bands {
    levels: Vec<Band>,
    /// `level -> (child -> parent)`, derived once from `children`.
    parents: Vec<std::collections::BTreeMap<u32, u32>>,
    kind: &'static str,
}

impl Bands {
    #[must_use]
    pub fn new(levels: Vec<Band>, kind: &'static str) -> Self {
        let parents = levels
            .iter()
            .map(|b| {
                let mut m = std::collections::BTreeMap::new();
                for (&p, cs) in &b.children {
                    for &c in cs {
                        m.insert(c, p);
                    }
                }
                m
            })
            .collect();
        Self { levels, parents, kind }
    }
}

impl Hierarchy for Bands {
    fn depth(&self) -> u32 {
        self.levels.len().max(1) as u32
    }
    fn level_for(&self, scale: f32) -> u32 {
        let mut chosen = 0u32;
        for (i, b) in self.levels.iter().enumerate() {
            if scale >= b.min_scale {
                chosen = i as u32;
            }
        }
        chosen
    }
    fn members(&self, level: u32) -> &[u32] {
        self.levels.get(level as usize).map_or(&[], |b| &b.members)
    }
    fn expand(&self, level: u32, parent: u32) -> &[u32] {
        self.levels
            .get(level as usize)
            .and_then(|b| b.children.get(&parent))
            .map_or(&[], |v| v.as_slice())
    }
    fn parent_of(&self, level: u32, child: u32) -> Option<u32> {
        let l = level.checked_sub(1)?;
        self.parents.get(l as usize).and_then(|m| m.get(&child)).copied()
    }
    fn kind(&self) -> &'static str {
        self.kind
    }
}