facett-core/src/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
}
}