facett-core 0.1.16

//! **facett-core::engine** — THE unified view core.
//!
//! `facett-map` (OSM 2D), `facett-map3d` (OSM 3D), the L1 vello overlay and the
//! graph views (`facett-graphview` / `facett-graphnav` / `facett-graph3d` /
//! `facett-graphpan`) are today separate code drawing the **same primitives**. A
//! road is a polyline; a graph edge is a polyline. A POI label is a screen-space
//! box with a priority; a node label is the same box with the same priority.
//! A translucent admin boundary and a translucent community hull composite
//! identically. Same tessellator, same miter clamp, same label collision, same
//! order-independent transparency, same pick buffer.
//!
//! Only **three** things actually differ, and they are the three traits in
//! [`source`]:
//!
//! * [`PositionSource`] — Mercator(lat, lon) | Layout(node) | Identity(x, y)
//! * [`ElevationSource`] — terrain heightfield | `0.0` | a graph metric
//! * [`Hierarchy`] — what "one step deeper" means
//!
//! ## ★ Drill-down and LOD are the same operation
//! A map zoom and a graph cluster-expand are both *descend one level in a
//! hierarchy of bounding volumes, swap coarse instances for fine*. [`Hierarchy`]
//! is that operation, [`cull::CullIndex`] is the volume index, and one culler
//! serves both.
//!
//! ## ★ The index is Ragnar's, not a Hilbert R-tree
//! See [`cull`]: the S(+)-tree from `znippy_zoomies::stree32` — branchless SIMD
//! node compare, software-pipelined prefetch, already a `facett-core` dependency.
//!
//! ## What this module is, at this stage
//! The **CPU spine**: sources → cull → project (RTE) → legibility plan → pick
//! index. Every stage is pure and headless-testable. The GPU stages Gemini
//! specified (compute culling into `DrawIndexedIndirect`, WGSL atomic label
//! collision, OIT fragment linked lists, stencil road casings, XeGTAO,
//! velocity-buffer TAA) hang off exactly these seams and change no caller.
//!
//! ## Layers, and why use case 7 works
//! [`plan`] takes a **slice** of [`LayerRef`]s. Each carries its own position
//! source, elevation source and hierarchy. A graph drawn on geography is
//! therefore two layers in one frame sharing one culler, one label placer, one
//! pick buffer — not a special case, just `len() == 2`.

pub mod cull;
pub mod pick;
pub mod rte;
pub mod source;

pub use cull::{CullIndex, CullReport};
pub use pick::{LayerId, PickHit, PickId, PickIndex, PickShape};
pub use rte::{RtePos, Split};
pub use source::{
    Band, Bands, ElevationSource, Flat, Flatten, Hierarchy, Identity, Layout, Metric, PositionSource,
    Projected, Sampled, WorldAabb, WorldPos,
};

use crate::legibility::{FrameInput, FrameOpts, FramePlan, plan_frame};
use egui::{Pos2, Rect, Vec2};

/// **The view** — world→screen, in `f64`, with the RTE split available for the
/// GPU lane.
///
/// This is deliberately *not* [`crate::render::camera::Camera`]. That type is an
/// `f32` orbit camera whose `V3`/`Projected`/`view_proj` are a verbatim copy of
/// `facett-map3d::OrbitCamera`'s (the census measured 54 + 143 duplicated lines
/// between them) and it cannot express Mercator zoom 22 without jitter. `View`
/// is the `f64` spine; the orbit/pitch/yaw layer folds onto it next.
#[derive(Clone, Copy, Debug, PartialEq)]
pub struct View {
    /// The world point at the centre of the viewport — the **eye**, and the
    /// origin every RTE evaluation is relative to.
    pub centre: WorldPos,
    /// Screen pixels per world unit. This is the number a [`Hierarchy`] reads to
    /// choose a level, and the number `Facet::scale_range()` clamps — which is
    /// why a map band and a graph band are the same control.
    pub scale: f64,
    /// Viewport rect in screen px.
    pub viewport: Rect,
    /// A monotonically bumped stamp so caches can key on "the view moved".
    pub epoch: u64,
}

impl Default for View {
    fn default() -> Self {
        Self {
            centre: WorldPos::default(),
            scale: 1.0,
            viewport: Rect::from_min_size(Pos2::ZERO, Vec2::new(1.0, 1.0)),
            epoch: 0,
        }
    }
}

impl View {
    /// World → screen. Evaluated **relative to the eye in `f64`**, which is the
    /// CPU mirror of the RTE vertex shader — see [`rte`].
    #[must_use]
    pub fn to_screen(&self, p: WorldPos) -> Pos2 {
        let c = self.viewport.center();
        Pos2::new(
            c.x + ((p.x - self.centre.x) * self.scale) as f32,
            c.y + ((p.y - self.centre.y) * self.scale) as f32,
        )
    }

    /// Screen → world (z = 0 plane).
    #[must_use]
    pub fn to_world(&self, p: Pos2) -> WorldPos {
        let c = self.viewport.center();
        let s = if self.scale.abs() < f64::MIN_POSITIVE { 1.0 } else { self.scale };
        WorldPos::flat(self.centre.x + (p.x - c.x) as f64 / s, self.centre.y + (p.y - c.y) as f64 / s)
    }

    /// The viewport as a world-space AABB — what [`CullIndex::query`] wants.
    #[must_use]
    pub fn world_aabb(&self) -> WorldAabb {
        let a = self.to_world(self.viewport.min);
        let b = self.to_world(self.viewport.max);
        WorldAabb {
            min: WorldPos::flat(a.x.min(b.x), a.y.min(b.y)),
            max: WorldPos::flat(a.x.max(b.x), a.y.max(b.y)),
        }
    }

    /// The eye in RTE form — upload once per frame, subtract in the shader.
    #[must_use]
    pub fn eye_rte(&self) -> RtePos {
        RtePos::of(self.centre)
    }
}

/// One layer of a frame: its three traits plus its identity and pick radius.
/// A frame is a slice of these; **use case 7 is `len() == 2`**.
pub struct LayerRef<'a> {
    /// `1..=255`; `0` is reserved for "nothing" in [`PickId`].
    pub id: LayerId,
    pub position: &'a dyn PositionSource,
    pub elevation: &'a dyn ElevationSource,
    pub hierarchy: &'a dyn Hierarchy,
    /// What a feature of this layer occupies for a click.
    pub pick_shape: pick::PickShape,
    /// Measured label box per feature id (`Vec2::ZERO` = no label). Short slices
    /// mean "no label from here on", matching [`FrameInput`].
    pub label_size: &'a [Vec2],
    /// Label ranking; short slice = all equal.
    pub label_priority: &'a [f32],
    /// Labels that must never be dropped (selection / hover / search hit).
    pub label_pinned: &'a [bool],
    /// Edges as `(from, to)` **feature ids**. A map's roads have none; a graph's
    /// are its edges. Same field, same thinner.
    pub edges: &'a [(u32, u32)],
}

impl<'a> LayerRef<'a> {
    /// A layer with no labels and no edges — the floor a migration starts from.
    #[must_use]
    pub fn new(
        id: LayerId,
        position: &'a dyn PositionSource,
        elevation: &'a dyn ElevationSource,
        hierarchy: &'a dyn Hierarchy,
    ) -> Self {
        Self {
            id,
            position,
            elevation,
            hierarchy,
            pick_shape: pick::PickShape::default(),
            label_size: &[],
            label_priority: &[],
            label_pinned: &[],
            edges: &[],
        }
    }

    /// The cache key contribution of this layer: its sources' generations.
    #[must_use]
    pub fn generation(&self) -> u64 {
        self.position.generation()
    }
}

/// What one layer contributed to the frame.
#[derive(Clone, Debug, Default)]
pub struct LayerPlan {
    pub id: LayerId,
    /// Feature ids that survived hierarchy + cull, ascending by Morton order.
    pub visible: Vec<u32>,
    /// Screen positions of `visible`, index-aligned.
    pub screen: Vec<Pos2>,
    /// Elevations of `visible`, index-aligned. All-zero for a [`Flat`] source
    /// (and the pass is skipped entirely in that case).
    pub elevation: Vec<f64>,
    /// The hierarchy level this layer drew at.
    pub level: u32,
    pub cull: CullReport,
}

/// The frame: every layer's visible set, the shared legibility plan, and the
/// pick index that click will hit.
#[derive(Debug, Default)]
pub struct EnginePlan {
    pub layers: Vec<LayerPlan>,
    /// Label placement + edge thinning, planned **once across all layers** — a
    /// map pin and a graph node compete for the same pixels, so they must be
    /// planned together or both will claim them.
    pub frame: FramePlan,
    pub pick: PickIndex,
}

impl EnginePlan {
    /// `state_json` fragment — the observable a robot/matrix row asserts on.
    #[must_use]
    pub fn state_json(&self) -> serde_json::Value {
        serde_json::json!({
            "layers": self.layers.iter().map(|l| serde_json::json!({
                "id": l.id,
                "visible": l.visible.len(),
                "level": l.level,
                "cull": l.cull.state_json(),
            })).collect::<Vec<_>>(),
            "frame": self.frame.report.state_json(),
            "pick_layers": self.pick.layer_count(),
        })
    }

    /// Total visible features across every layer.
    #[must_use]
    pub fn visible(&self) -> usize {
        self.layers.iter().map(|l| l.visible.len()).sum()
    }
}

/// A prebuilt cull index per layer, so a static dataset is not re-Mortoned every
/// frame. Rebuild when a layer's [`generation`](PositionSource::generation)
/// changes.
#[derive(Debug, Default)]
pub struct EngineCache {
    indices: Vec<(LayerId, u64, CullIndex)>,
}

impl EngineCache {
    /// The index for `layer`, building it if absent or stale.
    fn index_for(&mut self, layer: &LayerRef<'_>, level: u32) -> &CullIndex {
        // The generation key folds in the level: a different level is a
        // different member set, hence a different index.
        let key = layer.generation() ^ ((level as u64) << 48);
        let slot = self.indices.iter().position(|(id, k, _)| *id == layer.id && *k == key);
        let pos = match slot {
            Some(i) => i,
            None => {
                let members = layer.hierarchy.members(level);
                let items: Vec<(u32, WorldAabb)> =
                    members.iter().map(|&f| (f, layer.position.bounds(f))).collect();
                let idx = CullIndex::build(&items);
                if let Some(existing) = self.indices.iter().position(|(id, _, _)| *id == layer.id) {
                    self.indices[existing] = (layer.id, key, idx);
                    existing
                } else {
                    self.indices.push((layer.id, key, idx));
                    self.indices.len() - 1
                }
            }
        };
        &self.indices[pos].2
    }

    /// How many layer indices are resident.
    #[must_use]
    pub fn len(&self) -> usize {
        self.indices.len()
    }
    #[must_use]
    pub fn is_empty(&self) -> bool {
        self.indices.is_empty()
    }
}

/// **Plan one frame.** The single entry point every map and graph pane calls.
///
/// 1. Each layer's [`Hierarchy`] picks its level from `view.scale` — *the zoom
///    band and the cluster-expansion depth are the same choice*.
/// 2. [`CullIndex`] slices that level's bounding volumes against the viewport.
/// 3. Survivors are projected through [`PositionSource`] + [`ElevationSource`]
///    + [`View`] — eye-relative, in `f64`.
/// 4. All layers' projected anchors go into **one** [`plan_frame`] call, so
///    labels and edges compete across layers rather than per-layer.
/// 5. One [`PickIndex`] is built over the same anchors, so the click and the
///    paint can never disagree about what is where.
///
/// Pure: no `Ui`, no painter, no GPU.
#[must_use]
pub fn plan(
    layers: &[LayerRef<'_>],
    view: &View,
    opts: FrameOpts,
    cache: &mut EngineCache,
) -> EnginePlan {
    let mut out = EnginePlan::default();
    let view_box = view.world_aabb();

    // ── stages 1–3: per layer, hierarchy → cull → project ────────────────────
    let mut world = Vec::new();
    for layer in layers {
        let level = layer.hierarchy.level_for(view.scale as f32);
        let idx = cache.index_for(layer, level);

        let mut visible = Vec::new();
        let mut cull_rep = idx.query(view_box, &mut visible);
        // Features too wide for the lattice are drawn unconditionally — correct,
        // and counted so the cost is visible rather than mysterious.
        for &f in idx.oversize() {
            if !visible.contains(&f) {
                visible.push(f);
                cull_rep.oversize_forced += 1;
            }
        }
        cull_rep.visible = visible.len();

        layer.position.positions(&visible, &mut world);
        let mut elevation = Vec::new();
        if layer.elevation.z_range() != (0.0, 0.0) {
            layer.elevation.elevations(&visible, &world, &mut elevation);
            for (w, &z) in world.iter_mut().zip(elevation.iter()) {
                w.z = z;
            }
        } else {
            elevation.clear();
            elevation.resize(visible.len(), 0.0);
        }
        let screen: Vec<Pos2> = world.iter().map(|&w| view.to_screen(w)).collect();

        out.layers.push(LayerPlan { id: layer.id, visible, screen, elevation, level, cull: cull_rep });
    }

    // ── stage 4: ONE legibility plan across every layer ──────────────────────
    // Concatenate the layers into a single index space; a layer's feature id `f`
    // at layer offset `o` becomes plan index `o + rank_of(f)`.
    let total: usize = out.layers.iter().map(|l| l.screen.len()).sum();
    let mut centres = Vec::with_capacity(total);
    let mut label_size = Vec::with_capacity(total);
    let mut label_priority = Vec::with_capacity(total);
    let mut label_pinned = Vec::with_capacity(total);
    let mut edges: Vec<(u32, u32)> = Vec::new();
    let mut offset = 0u32;
    for (layer, lp) in layers.iter().zip(out.layers.iter()) {
        // feature id -> plan index, for this layer's edges.
        let mut rank = std::collections::HashMap::with_capacity(lp.visible.len());
        for (i, &f) in lp.visible.iter().enumerate() {
            rank.insert(f, offset + i as u32);
        }
        for (i, &f) in lp.visible.iter().enumerate() {
            centres.push(lp.screen[i]);
            let fi = f as usize;
            label_size.push(layer.label_size.get(fi).copied().unwrap_or(Vec2::ZERO));
            label_priority.push(layer.label_priority.get(fi).copied().unwrap_or(0.0));
            label_pinned.push(layer.label_pinned.get(fi).copied().unwrap_or(false));
        }
        for &(a, b) in layer.edges {
            if let (Some(&pa), Some(&pb)) = (rank.get(&a), rank.get(&b)) {
                edges.push((pa, pb));
            }
        }
        offset += lp.visible.len() as u32;
    }
    out.frame = plan_frame(
        &FrameInput {
            centres: &centres,
            label_size: &label_size,
            label_priority: &label_priority,
            label_pinned: &label_pinned,
            edges: &edges,
            edge_always: &[],
            edge_weight: &[],
            viewport: view.viewport,
        },
        opts,
    );

    // ── stage 5: ONE pick index over the same anchors ────────────────────────
    let mut key = view.epoch;
    for l in layers {
        key = key.rotate_left(7) ^ l.generation();
    }
    out.pick.begin(key);
    for (layer, lp) in layers.iter().zip(out.layers.iter()) {
        out.pick.push_layer(layer.id, &lp.screen, lp.visible.clone(), layer.pick_shape);
    }

    out
}

#[cfg(test)]
mod tests;