facett-map/src/tessellate.rs
//! **Polygon fill tessellation** for the vector basemap. OSM area rings (lakes,
//! parks, coastline-bounded land, building footprints) are almost never convex,
//! so `egui::Shape::convex_polygon` mis-fills them (it fans from the first
//! vertex → spurious triangles spill outside a concave ring). This module
//! triangulates an arbitrary simple polygon with **ear clipping** — O(n²),
//! dependency-free, no rayon — and emits an `egui::Mesh` the painter draws as a
//! correct flat fill. For the small per-way rings a basemap carries this is
//! plenty fast, and it is exact for concave shapes (where `convex_polygon` is not).
use egui::{Color32, Mesh, Pos2, Shape};
/// Signed area ×2 of a polygon (CCW positive). Used to orient the ring so the
/// ear-clipping "is this a convex ear?" test has a consistent winding.
fn signed_area2(pts: &[Pos2]) -> f32 {
let mut a = 0.0;
for i in 0..pts.len() {
let p = pts[i];
let q = pts[(i + 1) % pts.len()];
a += p.x * q.y - q.x * p.y;
}
a
}
/// Cross product `(b-a) × (c-a)` — sign tells the turn direction at `b`.
#[inline]
fn cross(a: Pos2, b: Pos2, c: Pos2) -> f32 {
(b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x)
}
/// Point-in-triangle (barycentric sign test), inclusive of edges.
fn in_triangle(p: Pos2, a: Pos2, b: Pos2, c: Pos2) -> bool {
let d1 = cross(a, b, p);
let d2 = cross(b, c, p);
let d3 = cross(c, a, p);
let neg = d1 < 0.0 || d2 < 0.0 || d3 < 0.0;
let pos = d1 > 0.0 || d2 > 0.0 || d3 > 0.0;
!(neg && pos)
}
/// **Where the hand-rolled ear clip stops being affordable and `earcutr` takes over.**
///
/// [`triangulate`]'s clip is a scan for a convex vertex, an O(m) point-in-triangle test
/// inside it and an O(m) `Vec::remove` — **O(n²)** to consume a ring, with the only bound
/// `guard < n*n + 16`, which for a real coastline is astronomically large. It is correct;
/// it is just quadratic.
///
/// That was invisible while the biggest ring on a korp pane was the bundled Natural Earth
/// country outline: **238 vertices**. korp's cut step `h` replaced that with the region's
/// OWN coastline, and the Swedish mainland is **295 186 vertices** at its z11 rung —
/// ~10¹¹ elementary operations, roughly **100 seconds** of frozen UI on the first frame
/// that paints it. MEASURED here on a 20 001-vertex concave spiral, release build:
/// **7.13 s** for the hand-rolled clip.
///
/// `earcutr` — the tiny pure-Rust port of MapBox's earcut, already a dependency and
/// already the with-holes path — is O(n log n) and does the same job. So: below this
/// count nothing changes (the small-ring case was already right, and it is the one every
/// building footprint takes); at or above it, earcut. 256 is chosen well under the size
/// where the quadratic term is measurable (256² is 65 k operations) and well over every
/// footprint.
pub const EARCUT_MIN_VERTICES: usize = 256;
/// Triangulate a **simple polygon** (one ring, no holes) given as a CW/CCW vertex
/// loop, returning index triples into the input. Concave-safe (ear clipping).
/// Degenerate input (<3 vertices) → no triangles. A self-intersecting ring may
/// drop a few triangles but never panics — graceful for messy OSM geometry.
///
/// A ring of [`EARCUT_MIN_VERTICES`] or more goes through `earcutr` instead of the
/// hand-rolled clip below — same contract, same index space, O(n log n) instead of O(n²).
/// See that constant for the coastline this exists for.
pub fn triangulate(pts: &[Pos2]) -> Vec<[u32; 3]> {
let n = pts.len();
if n < 3 {
return Vec::new();
}
if n >= EARCUT_MIN_VERTICES {
let mut data: Vec<f64> = Vec::with_capacity(n * 2);
for p in pts {
data.push(f64::from(p.x));
data.push(f64::from(p.y));
}
// No holes: one ring, so no hole indices. A failure falls through to the clip
// below rather than leaving the polygon unfilled.
if let Ok(idx) = earcutr::earcut(&data, &[], 2) && !idx.is_empty() {
return idx
.as_chunks::<3>().0.iter()
.map(|c| [c[0] as u32, c[1] as u32, c[2] as u32])
.collect();
}
}
// Work on an index list so we can clip ears off in place. Orient CCW so the
// convexity test (cross > 0 = convex vertex) is consistent.
let ccw = signed_area2(pts) >= 0.0;
let mut idx: Vec<usize> = if ccw { (0..n).collect() } else { (0..n).rev().collect() };
let mut tris: Vec<[u32; 3]> = Vec::with_capacity(n.saturating_sub(2));
let mut guard = 0usize;
let max_iters = n * n + 16; // O(n²) ear clipping; bound it so a bad ring can't hang
while idx.len() > 3 && guard < max_iters {
guard += 1;
let m = idx.len();
let mut clipped = false;
for i in 0..m {
let ia = idx[(i + m - 1) % m];
let ib = idx[i];
let ic = idx[(i + 1) % m];
let (a, b, c) = (pts[ia], pts[ib], pts[ic]);
// Convex vertex? (CCW ring → left turn at an ear)
if cross(a, b, c) <= 0.0 {
continue;
}
// No other vertex inside this candidate ear?
let mut ear = true;
for &j in &idx {
if j == ia || j == ib || j == ic {
continue;
}
if in_triangle(pts[j], a, b, c) {
ear = false;
break;
}
}
if ear {
tris.push([ia as u32, ib as u32, ic as u32]);
idx.remove(i);
clipped = true;
break;
}
}
if !clipped {
// No ear found (likely a near-degenerate / self-touching ring): fan
// the remainder so we still produce *some* fill rather than nothing.
break;
}
}
if idx.len() == 3 {
tris.push([idx[0] as u32, idx[1] as u32, idx[2] as u32]);
} else if idx.len() > 3 {
// Fallback fan over whatever is left (keeps the area visibly filled).
for k in 1..idx.len() - 1 {
tris.push([idx[0] as u32, idx[k] as u32, idx[k + 1] as u32]);
}
}
tris
}
/// Build a filled `egui::Mesh` for a polygon ring with `fill` colour. Concave-safe
/// (ear clipping). Returns `None` for a degenerate ring (<3 vertices).
pub fn filled_mesh(pts: &[Pos2], fill: Color32) -> Option<Shape> {
let tris = triangulate(pts);
if tris.is_empty() {
return None;
}
let mut mesh = Mesh::default();
for &p in pts {
mesh.colored_vertex(p, fill);
}
for [a, b, c] in tris {
mesh.add_triangle(a, b, c);
}
Some(Shape::mesh(mesh))
}
// ── Polygon-with-holes tessellation (lakes-with-islands, donut landuse) ────────
//
// OSM areas are frequently **polygon-with-holes** (a lake carrying an island, a
// forest with a clearing, a landuse ring around a courtyard) or **multipolygons**
// (several such polygons under one tag). `triangulate`/`filled_mesh` above fill a
// SINGLE ring only — so a hole would be filled solid (the island painted as water)
// and a multipolygon's rings would be bridged into one bad shape. The functions
// below punch the holes. The single-ring path still uses the hand-rolled ear clip
// above (byte-identical); the WITH-HOLES path routes through `earcutr` — the tiny
// pure-Rust port of MapBox's earcut — which robustly triangulates outer-minus-holes
// on the messy, self-touching rings real OSM geometry throws at it (a hand-rolled
// bridge stalled on the collinear bridge vertices and fanned the hole shut).
/// **THE vertex order a filled ring set tessellates in**: the `outer` ring, then
/// every hole ring with ≥3 vertices, concatenated in order. Degenerate holes
/// (<3 vertices, which cannot bound anything) are dropped — they are dropped by
/// [`triangulate_with_holes`] too, and if the two disagreed by even one ring an
/// index triple from one would address a different vertex in the other.
///
/// One writer, three consumers: [`triangulate_with_holes`] builds earcut's buffer
/// from it, [`mesh_from_tris`] builds the screen-space mesh from it, and
/// [`FillTessCache`] tessellates the Mercator-space copy of it. That is the whole
/// reason the cached indices are safe to reuse across spaces.
#[must_use]
pub fn fill_vertices(outer: &[Pos2], holes: &[Vec<Pos2>]) -> Vec<Pos2> {
let n = outer.len() + holes.iter().filter(|h| h.len() >= 3).map(Vec::len).sum::<usize>();
let mut verts = Vec::with_capacity(n);
verts.extend_from_slice(outer);
for h in holes {
if h.len() >= 3 {
verts.extend_from_slice(h);
}
}
verts
}
/// Build the fill mesh for `outer` (+ `holes`) from an **already-computed** index
/// triple list — the cached-triangulation twin of [`filled_mesh_with_holes`],
/// with the ear clip skipped.
///
/// `tris` must index into [`fill_vertices`]`(outer, holes)`; a triple that runs
/// past the end is dropped rather than panicking (a cache built for a different
/// ring is a bug, but it must not take the process down mid-frame).
#[must_use]
pub fn mesh_from_tris(
outer: &[Pos2],
holes: &[Vec<Pos2>],
tris: &[[u32; 3]],
fill: Color32,
) -> Option<Shape> {
if tris.is_empty() || outer.len() < 3 {
return None;
}
let verts = fill_vertices(outer, holes);
let n = verts.len() as u32;
let mut mesh = Mesh::default();
for &p in &verts {
mesh.colored_vertex(p, fill);
}
for &[a, b, c] in tris {
if a < n && b < n && c < n {
mesh.add_triangle(a, b, c);
}
}
if mesh.indices.is_empty() { None } else { Some(Shape::mesh(mesh)) }
}
// ── The per-layer ear-clip cache: the frame's single biggest cost, deleted ─────
//
// MEASURED 2026-08-03, real 1600×1000 window on an RTX 4090, 20 000 real Swedish
// ways / 452 697 vertices, median of 230 frames: the whole frame was 42.45 ms, of
// which `tessellate::triangulate` was **36.22 ms — 85.4 %**, redone from scratch
// every frame over 1 890 filled polygons / 81 906 vertices → 78 126 triangles. The
// largest ring in view is 659 vertices, i.e. up to 434 281 in-triangle tests per
// frame, for a ring that had not changed since it was read off disk.
//
// **Why the indices survive a camera move.** The painter tessellates in SCREEN
// space, so it looked camera-dependent. It is not. `MapView::project` is
// `affine(mercator(lon, lat))` — Mercator, then a rotate (`bearing`), a `cos(tilt)`
// foreshorten, a uniform scale (`world_px`) and a translate. Every one of those is
// affine, and **a triangulation of a simple polygon is affine-invariant**: an affine
// map sends triangles to triangles and preserves incidence, so a valid ear-clip of
// the Mercator ring is a valid triangulation of its projected image at any camera.
// (Reflection reverses winding, which neither `triangulate`'s orientation step nor
// `egui::Mesh` cares about.) What the indices are NOT invariant under is the
// Mercator step itself — Mercator bends latitude nonlinearly, so a ring that spans
// a country does not triangulate the same in `(lon, lat)`. Hence: tessellate in
// **Mercator**, never in lon/lat, never in screen px.
//
// So the invalidation key is the DATA, not the camera — and here it is the data by
// construction rather than by comparison: a cache is built alongside the ring set it
// belongs to and has exactly as many slots. New ways ⇒ new layer ⇒ new cache ⇒ empty
// cells. Nothing has to remember to invalidate anything.
/// The ear-clip index triples of one filled ring set, shared by every frame that
/// paints it.
pub type FillTris = std::sync::Arc<[[u32; 3]]>;
/// **Per-layer ear-clip cache**, one slot per filled polygon, filled lazily on the
/// first frame that paints each polygon and never recomputed.
///
/// Built with [`FillTessCache::new(n)`](Self::new) beside the `n` rings it caches,
/// so it is invalidated **by construction** when the data changes (see the module
/// note above). `&self` throughout — [`std::sync::OnceLock`] does the interior
/// mutability, so a painter holding `&self` can fill it mid-frame.
#[derive(Debug, Default)]
pub struct FillTessCache {
slots: Vec<std::sync::OnceLock<FillTris>>,
/// How many slots this cache has actually EAR-CLIPPED. The applied-output fact
/// the "computed once, not once per frame" guard reads: a cache that silently
/// went back to per-frame tessellation moves this number every frame, and a
/// counter that only ever reports the same number as `len()` cannot tell the two
/// apart. Never a state round-trip.
computed: std::sync::atomic::AtomicUsize,
}
impl FillTessCache {
/// A cache with `n` empty slots — one per polygon of the layer it belongs to.
#[must_use]
pub fn new(n: usize) -> Self {
Self { slots: (0..n).map(|_| std::sync::OnceLock::new()).collect(), computed: 0.into() }
}
/// Slot count (the ring count this cache was built for).
#[must_use]
pub fn len(&self) -> usize {
self.slots.len()
}
/// Is this cache empty (no rings)?
#[must_use]
pub fn is_empty(&self) -> bool {
self.slots.is_empty()
}
/// **How many ear clips this cache has run** since it was built. With a live
/// camera and unchanged data this stops at the number of polygons ever painted
/// and never moves again; that is exactly the claim `mapdraw-1` makes.
#[must_use]
pub fn ear_clips(&self) -> usize {
self.computed.load(std::sync::atomic::Ordering::Relaxed)
}
/// The index triples for ring `i` — `(lon, lat)` rings, tessellated **in
/// Mercator space** on the first call and returned from the slot on every later
/// one. `None` for an out-of-range index or a degenerate ring.
pub fn tris(&self, i: usize, outer: &[(f64, f64)], holes: &[Vec<(f64, f64)>]) -> Option<FillTris> {
let slot = self.slots.get(i)?;
if let Some(t) = slot.get() {
return Some(t.clone());
}
let merc = |r: &[(f64, f64)]| -> Vec<Pos2> {
r.iter()
.map(|&(lon, lat)| {
let (x, y) = crate::mercator(lon, lat);
Pos2::new(x as f32, y as f32)
})
.collect()
};
// **The cross-layer memo, before the O(n²) clip.** Per-layer slots die with
// their layer, and korp rebuilds the whole facet on every viewport apply — so
// a pan re-earned every triangulation it had already paid for ("36.22 ms of a
// 42.45 ms frame" is what that cost the first time, see the layer note). The
// ring's COORDINATES are its identity, so a ring that survived the pan (most
// of them — a pan step overlaps ~2/3 of the viewport) hands its triples over
// for the price of a hash. The slot still short-circuits every later frame of
// THIS layer; `computed` still counts real ear clips only, so the mapdraw-1
// guard keeps meaning what it says.
let key = ring_identity(outer, holes);
if let Some(hit) = global_tess_get(key) {
return Some(slot.get_or_init(|| hit).clone());
}
let m_outer = merc(outer);
let m_holes: Vec<Vec<Pos2>> = holes.iter().map(|h| merc(h)).collect();
let (_, tris) = triangulate_with_holes(&m_outer, &m_holes);
self.computed.fetch_add(1, std::sync::atomic::Ordering::Relaxed);
let arc: FillTris = tris.into();
global_tess_put(key, arc.clone());
Some(slot.get_or_init(|| arc).clone())
}
}
/// **A ring set's identity: a 128-bit FNV over its raw coordinates.** Two rings with
/// the same coordinates ARE the same polygon — the tessellation is a pure function of
/// them — so the hash is the whole invalidation story, exactly as the per-layer
/// slot's "new data ⇒ new cache" is. 128 bits so an accidental collision (a wrong
/// fill on a real map) is out of the probability budget entirely.
fn ring_identity(outer: &[(f64, f64)], holes: &[Vec<(f64, f64)>]) -> u128 {
const OFFSET: u128 = 0x6c62_272e_07bb_0142_62b8_2175_6295_c58d;
const PRIME: u128 = 0x0000_0000_0100_0000_0000_0000_0000_013b;
fn eat(h: &mut u128, v: f64) {
for b in v.to_bits().to_le_bytes() {
*h ^= u128::from(b);
*h = h.wrapping_mul(PRIME);
}
}
let mut h = OFFSET;
for &(lon, lat) in outer {
eat(&mut h, lon);
eat(&mut h, lat);
}
for hole in holes {
// A ring SEPARATOR distinct from any coordinate byte stream, so
// ([a,b],[c]) and ([a],[b,c]) cannot collide by concatenation.
h ^= 0xff;
h = h.wrapping_mul(PRIME);
for &(lon, lat) in hole {
eat(&mut h, lon);
eat(&mut h, lat);
}
}
h
}
/// **How many ring sets ONE generation of the cross-layer memo holds.** The memo keeps
/// the current generation and the one before it (see [`GlobalTess`]), so the live
/// ceiling is twice this.
///
/// # The number is a MEASUREMENT, not a round one
///
/// It was `8192`, and 8192 is smaller than the thing the memo exists to hold. MEASURED
/// 2026-09-05 on the real 890M Sweden cut (`/home/korp/.korp/work/sweden`), a 900×700
/// pane on central Stockholm, counting `FillTessCache::ear_clips` on a FRESH facet per
/// level — which is what korp builds on every `REBUILD 2D`:
///
/// ```text
/// level ways filled rings ear clips on a cold facet
/// z9 50 101 34 519 7 428
/// z10 30 873 16 587 5 470
/// z11 15 598 6 759 4 844
/// z12 34 349 26 691 5 555
/// z13 13 466 9 110 3 661
/// ```
///
/// A LEVEL CROSSING alternates two of those, so the set that has to stay resident is
/// their sum: **9 305 rings for z11↔z12, 12 898 for z9↔z10** — both above 8 192. So the
/// alternation evicted exactly what it was about to ask for again, and the counter said
/// so: driving z11↔z12 four times ran `4859, 4844, 4844, 4844` ear clips at z11 and
/// `5555` at z12 on every single round — **10 399 ear clips per crossing, for ever**,
/// against a memo that was supposed to make the second crossing free. Priced on the same
/// cut: one level's fills cost **16.5 ms** (z11) and **11.1 ms** (z12) to ear-clip, which
/// is korp's whole reported `REBUILD 2D` budget of 15–19 ms.
///
/// The weight of holding them is nothing: the same measurement says z9's 34 519 filled
/// rings triangulate to 286 653 triangles — **3.44 MB** of `[u32; 3]`, 8.3 triangles per
/// ring. At 32 768 per generation the ceiling is 65 536 resident rings, ~6.6 MB of index
/// triples plus map overhead, to delete a 15 ms class of per-crossing work.
const GLOBAL_TESS_CAP: usize = 32_768;
/// **The cross-layer ear-clip memo: two generations, no ordering list.**
///
/// It was a `HashMap` + a `VecDeque` walked as an LRU, and the walk is why the cap
/// could not simply be raised: `global_tess_get` did
/// `order.iter().position(|k| *k == key)` on every **hit**, an O(cap) scan followed by an
/// O(cap) `VecDeque::remove`. A rebuild consults this memo once per filled ring — every
/// per-layer slot is fresh — so a z11↔z12 crossing that started HITTING at cap 8 192
/// would have paid up to 10 399 × 8 192 ≈ **85 million key comparisons**, and at 32 768
/// four times that. Making the memo big enough and keeping the LRU were mutually
/// exclusive.
///
/// So the recency structure is the generation itself. Everything goes into `hot`; when
/// `hot` fills, it becomes `cold` and a new `hot` starts; a lookup that misses `hot` but
/// finds `cold` promotes the entry back into `hot`. Every operation is one or two hash
/// lookups — no scan, no list, nothing proportional to the cap — and the guarantee is
/// the one this cache is for: **anything touched since the last rotation survives**, and
/// a rotation costs `GLOBAL_TESS_CAP` fresh rings, which is three times the widest
/// single level measured. A crossing whose two levels both fit in one generation is
/// free after its first pass, which is the whole point.
struct GlobalTess {
hot: std::collections::HashMap<u128, FillTris>,
cold: std::collections::HashMap<u128, FillTris>,
}
fn global_tess() -> &'static std::sync::Mutex<GlobalTess> {
static CELL: std::sync::OnceLock<std::sync::Mutex<GlobalTess>> = std::sync::OnceLock::new();
CELL.get_or_init(|| {
std::sync::Mutex::new(GlobalTess {
hot: std::collections::HashMap::new(),
cold: std::collections::HashMap::new(),
})
})
}
fn global_tess_get(key: u128) -> Option<FillTris> {
let g = global_tess().lock().ok()?;
if let Some(hit) = g.hot.get(&key) {
return Some(hit.clone());
}
// In the older generation: hand it back AND promote it, so a ring that is used every
// frame cannot be dropped by the next rotation just because it was first seen long
// ago. Promotion can itself fill `hot`, which is why it goes through `put`.
let hit = g.cold.get(&key).cloned()?;
drop(g);
global_tess_put(key, hit.clone());
Some(hit)
}
fn global_tess_put(key: u128, tris: FillTris) {
let Ok(mut g) = global_tess().lock() else { return };
g.hot.insert(key, tris);
if g.hot.len() > GLOBAL_TESS_CAP {
// ROTATE: the generation that just filled becomes the survivor pool, and the one
// before it is dropped whole. One `mem::take` — never a per-entry eviction pass.
g.cold = std::mem::take(&mut g.hot);
}
}
/// Triangulate a polygon with holes: an `outer` ring MINUS the `holes` rings.
/// Returns the vertex list (outer then each hole, concatenated) plus index triples
/// into it, so the caller can build a mesh or hit-test the fill. The outer ring is
/// filled and each hole is punched (its interior carries no triangles). Concave-
/// safe; graceful (on a tessellation failure it falls back to filling the outer
/// ring alone rather than producing nothing).
///
/// With **no holes** this is exactly `triangulate(outer)` over `outer`'s vertices,
/// so the common single-ring case is unchanged (and never touches earcutr).
pub fn triangulate_with_holes(outer: &[Pos2], holes: &[Vec<Pos2>]) -> (Vec<Pos2>, Vec<[u32; 3]>) {
if outer.len() < 3 {
return (Vec::new(), Vec::new());
}
if holes.iter().all(|h| h.len() < 3) {
// No real holes → the byte-identical hand-rolled single-ring ear clip.
return (outer.to_vec(), triangulate(outer));
}
// Flatten outer + holes into earcut's `[x0, y0, x1, y1, …]` buffer; a hole's
// start index is its first vertex's index in that buffer. The vertex ORDER is
// [`fill_vertices`]' — the one writer both this and the cached-index painter
// concatenate through, so an index triple computed here always addresses the
// same vertex on the other side (LAW #5).
let verts = fill_vertices(outer, holes);
let mut data: Vec<f64> = Vec::with_capacity(verts.len() * 2);
for &p in &verts {
data.push(p.x as f64);
data.push(p.y as f64);
}
let mut hole_indices: Vec<usize> = Vec::new();
let mut at = outer.len();
for h in holes {
if h.len() < 3 {
continue;
}
hole_indices.push(at);
at += h.len();
}
match earcutr::earcut(&data, &hole_indices, 2) {
Ok(idx) => {
let tris: Vec<[u32; 3]> =
idx.as_chunks::<3>().0.iter().map(|c| [c[0] as u32, c[1] as u32, c[2] as u32]).collect();
(verts, tris)
}
// Never corrupt the fill: on failure fill the outer ring alone.
Err(_) => (outer.to_vec(), triangulate(outer)),
}
}
/// Build a filled `egui::Mesh` for a polygon **with holes** (`outer` MINUS
/// `holes`) in `fill` colour. Concave-safe; punches every hole. Returns `None` for
/// a degenerate outer ring. With no holes this equals [`filled_mesh`].
pub fn filled_mesh_with_holes(outer: &[Pos2], holes: &[Vec<Pos2>], fill: Color32) -> Option<Shape> {
let (verts, tris) = triangulate_with_holes(outer, holes);
if tris.is_empty() {
return None;
}
let mut mesh = Mesh::default();
for &p in &verts {
mesh.colored_vertex(p, fill);
}
for [a, b, c] in tris {
mesh.add_triangle(a, b, c);
}
Some(Shape::mesh(mesh))
}
/// Paint one **filled area way** from ALREADY-PROJECTED screen-space geometry: the
/// outer `ring` and its (possibly empty) `holes`. When `fill` is `Some`, punches the
/// holes out of the fill ([`filled_mesh_with_holes`]) if present, else the plain
/// single-ring [`filled_mesh`] (the byte-identical common path), and adds the mesh.
/// Then always closes and strokes the outer outline; when `outline_holes` is set each
/// hole ring (≥3 pts) is closed and stroked too (an island shoreline / courtyard edge).
///
/// The ONE home for the fill-way paint recipe `facett-map` (`MapView` + `MapFacet`) and
/// `facett-geomap` (`GeoMap` + `osm2d`) each open-coded (duplication-audit cluster I).
/// Projection — f32 `to_px`, f64 `cam.to_px` + Sutherland–Hodgman clip, tilt-fade — stays
/// at each call site (the genuinely different part); this owns the shared mesh + outline
/// tail. `MapFacet` strokes outlines even for unfilled polygons, hence `fill: Option`.
///
/// `tris` is the **cached ear clip** ([`FillTessCache`]): `Some` skips the O(n²)
/// triangulation entirely and meshes straight off the indices — the frame's single
/// biggest cost, and it is the same fill because the indices were computed on the
/// Mercator preimage of this very `ring` (see the [`FillTessCache`] note). `None`
/// keeps the byte-identical per-frame path, so every caller that has no cache yet
/// is unchanged.
pub fn paint_filled_way(
painter: &egui::Painter,
ring: Vec<Pos2>,
holes: &[Vec<Pos2>],
fill: Option<Color32>,
stroke: egui::Stroke,
outline_holes: bool,
tris: Option<&[[u32; 3]]>,
) {
if let Some(fill) = fill {
let mesh = match tris {
Some(t) => mesh_from_tris(&ring, holes, t, fill),
None if holes.is_empty() => filled_mesh(&ring, fill),
None => filled_mesh_with_holes(&ring, holes, fill),
};
if let Some(mesh) = mesh {
painter.add(mesh);
}
}
let mut outline = ring;
if let Some(&first) = outline.first() {
outline.push(first);
}
painter.add(Shape::line(outline, stroke));
if outline_holes {
for mut hr in holes.iter().cloned() {
if hr.len() >= 3 {
if let Some(&first) = hr.first() {
hr.push(first);
}
painter.add(Shape::line(hr, stroke));
}
}
}
}
#[cfg(test)]
mod tests {
use super::*;
/// **★ A ring outlives the layer that first clipped it.** korp rebuilds the whole
/// facet per viewport apply, so per-layer slots alone re-earn every triangulation
/// on every pan (the 36 ms class). The probe is the ear-clip counter itself: a
/// SECOND cache — a fresh layer — serving the same ring must produce identical
/// triples with ZERO ear clips of its own. Deleting the `global_tess_get` probe in
/// `tris` turns the zero red, and that is the direction that matters. Distinct
/// coordinates must still clip fresh — the identity is the ring, nothing looser.
#[test]
fn a_rings_triangulation_survives_its_layers_death() {
// Unique coordinates so a parallel test's global entries cannot alias these.
let outer: Vec<(f64, f64)> =
vec![(31.07, 59.01), (31.29, 59.02), (31.28, 59.24), (31.06, 59.23), (31.02, 59.12)];
let first = FillTessCache::new(1);
let a = first.tris(0, &outer, &[]).expect("a real ring tessellates");
assert_eq!(first.ear_clips(), 1, "the FIRST cache genuinely clipped");
let second = FillTessCache::new(1); // the rebuilt layer, same data
let b = second.tris(0, &outer, &[]).expect("the reborn layer serves the same ring");
assert_eq!(
second.ear_clips(),
0,
"the reborn layer re-ran the ear clip — the cross-layer memo is not serving",
);
assert_eq!(a.as_ref(), b.as_ref(), "and the served triples are the SAME triangulation");
// A DIFFERENT ring in a third cache must clip fresh — the memo keys on the
// coordinates, not on 'anything was cached before'.
let other: Vec<(f64, f64)> =
vec![(32.51, 58.41), (32.72, 58.42), (32.71, 58.63), (32.50, 58.62)];
let third = FillTessCache::new(1);
let _ = third.tris(0, &other, &[]).expect("a distinct ring tessellates");
assert_eq!(third.ear_clips(), 1, "a distinct ring is NOT a memo hit");
}
/// **★ A ring that is used across a ROTATION is not dropped by it.**
///
/// The memo holds two generations and drops the older one whole. That is the trade
/// that bought an O(1) hit path (see [`GlobalTess`]), and it is only safe because a
/// hit in the older generation PROMOTES. Without the promotion, a ring painted on
/// every crossing still dies exactly one rotation after it was first seen — which is
/// the failure the old LRU existed to prevent and the one this test stands in for.
///
/// Driven RED by deleting the `global_tess_put` call from `global_tess_get`'s cold
/// arm: the survivor's second lookup then re-clips (`ear_clips() == 1`).
///
/// The sweep is **two** generations wide, and that is not padding: one rotation only
/// moves the survivor from `hot` into `cold`, where a lookup still finds it. It takes
/// the SECOND rotation to drop a generation that was never promoted out of — which is
/// exactly the arm that must go red. (Measured: at one generation the test passes with
/// the promotion deleted, i.e. it is hollow.) The fillers are 4-vertex quads, so the
/// whole sweep is ~66 k two-triangle clips.
#[test]
fn a_ring_used_in_both_generations_survives_a_rotation() {
// Unique coordinates so a parallel test's entries cannot alias these.
let survivor: Vec<(f64, f64)> =
vec![(41.11, 12.01), (41.33, 12.02), (41.32, 12.24), (41.10, 12.23)];
let warm = FillTessCache::new(1);
let a = warm.tris(0, &survivor, &[]).expect("a real ring tessellates");
assert_eq!(warm.ear_clips(), 1, "the survivor was genuinely clipped once");
// Fill a whole generation with rings nobody will ask for again, touching the
// survivor as we go — which is what a real crossing does to its shared coastline.
let sweep = 2 * GLOBAL_TESS_CAP + 2;
let filler = FillTessCache::new(sweep);
for i in 0..sweep {
let x = 60.0 + i as f64 * 1e-4;
let ring = vec![(x, 20.0), (x + 5e-5, 20.0), (x + 5e-5, 20.00005), (x, 20.00005)];
let _ = filler.tris(i, &ring, &[]);
if i % 1024 == 0 {
// The survivor is still in use, so every rotation must carry it forward.
let touch = FillTessCache::new(1);
let _ = touch.tris(0, &survivor, &[]);
assert_eq!(touch.ear_clips(), 0, "the survivor was re-clipped mid-sweep at i={i}");
}
}
let after = FillTessCache::new(1);
let b = after.tris(0, &survivor, &[]).expect("the survivor still tessellates");
assert_eq!(
after.ear_clips(),
0,
"a rotation dropped a ring that was still being used every generation",
);
assert_eq!(a.as_ref(), b.as_ref(), "and it is the SAME triangulation, not a re-derived one");
}
#[test]
fn triangulates_a_convex_quad_into_two_triangles() {
let quad = [Pos2::new(0.0, 0.0), Pos2::new(2.0, 0.0), Pos2::new(2.0, 2.0), Pos2::new(0.0, 2.0)];
let tris = triangulate(&quad);
assert_eq!(tris.len(), 2, "a quad → 2 triangles");
// total triangle area == polygon area (4.0)
let area: f32 = tris
.iter()
.map(|&[a, b, c]| (cross(quad[a as usize], quad[b as usize], quad[c as usize])).abs() / 2.0)
.sum();
assert!((area - 4.0).abs() < 1e-4, "triangulated area == 4.0, got {area}");
}
#[test]
fn triangulates_a_concave_polygon_without_spilling_outside() {
// An arrow / "L"-ish concave pentagon (the notch makes convex_polygon fail).
let poly = [
Pos2::new(0.0, 0.0),
Pos2::new(4.0, 0.0),
Pos2::new(4.0, 4.0),
Pos2::new(2.0, 1.0), // the concave notch vertex
Pos2::new(0.0, 4.0),
];
let tris = triangulate(&poly);
assert_eq!(tris.len(), poly.len() - 2, "n-2 triangles for a simple polygon");
// The triangle area must equal the polygon's true (shoelace) area — a
// convex fan would OVER-count (filling the notch), so this is the proof
// the concave shape tessellated correctly.
let true_area = signed_area2(&poly).abs() / 2.0;
let tri_area: f32 = tris
.iter()
.map(|&[a, b, c]| cross(poly[a as usize], poly[b as usize], poly[c as usize]).abs() / 2.0)
.sum();
assert!(
(tri_area - true_area).abs() < 1e-3,
"concave fill area {tri_area} must equal true area {true_area} (no spill into the notch)"
);
}
#[test]
fn degenerate_rings_are_graceful() {
assert!(triangulate(&[]).is_empty());
assert!(triangulate(&[Pos2::ZERO]).is_empty());
assert!(triangulate(&[Pos2::ZERO, Pos2::new(1.0, 0.0)]).is_empty());
assert!(filled_mesh(&[Pos2::ZERO, Pos2::new(1.0, 0.0)], Color32::RED).is_none());
}
/// Total area of a triangle set indexed into `verts`.
fn tri_set_area(verts: &[Pos2], tris: &[[u32; 3]]) -> f32 {
tris.iter()
.map(|&[a, b, c]| cross(verts[a as usize], verts[b as usize], verts[c as usize]).abs() / 2.0)
.sum()
}
/// Is `p` covered by any triangle of the set?
fn covered(p: Pos2, verts: &[Pos2], tris: &[[u32; 3]]) -> bool {
tris.iter()
.any(|&[a, b, c]| in_triangle(p, verts[a as usize], verts[b as usize], verts[c as usize]))
}
/// RED-when-broken: a polygon **with a hole** (a lake with an island / a
/// donut landuse) must tessellate to `outer` MINUS `hole` — the hole region is
/// NOT covered by the fill. The old single-ring tessellator filled the island
/// in (it saw one bridged ring), so the hole-centre point sat inside a
/// triangle; here it must sit OUTSIDE the filled set.
#[test]
fn a_hole_is_punched_out_of_the_fill() {
// 10×10 outer square, 4×4 hole centred at (5,5) (island at 3..7).
let outer = [Pos2::new(0.0, 0.0), Pos2::new(10.0, 0.0), Pos2::new(10.0, 10.0), Pos2::new(0.0, 10.0)];
let hole = vec![Pos2::new(3.0, 3.0), Pos2::new(7.0, 3.0), Pos2::new(7.0, 7.0), Pos2::new(3.0, 7.0)];
let (verts, tris) = triangulate_with_holes(&outer, &[hole]);
assert!(!tris.is_empty(), "the ring-with-hole tessellates to triangles");
// The hole centre must be OUTSIDE the fill (the island is not painted).
assert!(
!covered(Pos2::new(5.0, 5.0), &verts, &tris),
"the hole (island) centre must NOT be covered by the fill"
);
// A point in the solid ring (between outer edge and hole) MUST be filled.
assert!(
covered(Pos2::new(1.0, 5.0), &verts, &tris),
"the water ring around the island must still be filled"
);
// Area = outer (100) − hole (16) = 84, proving the hole is subtracted.
let area = tri_set_area(&verts, &tris);
assert!((area - 84.0).abs() < 1e-2, "fill area == outer − hole (100−16=84), got {area}");
}
#[test]
fn no_holes_matches_the_single_ring_tessellation() {
// With an empty hole list the merged fill must equal the plain single-ring
// tessellation (the common OSM case stays unchanged / byte-identical).
let quad = [Pos2::new(0.0, 0.0), Pos2::new(2.0, 0.0), Pos2::new(2.0, 2.0), Pos2::new(0.0, 2.0)];
let (verts, tris) = triangulate_with_holes(&quad, &[]);
assert_eq!(verts, quad.to_vec(), "no bridging → the original vertices");
assert_eq!(tris, triangulate(&quad), "no holes → identical triangles to triangulate()");
}
}
/// **Tessellate a path into a GLOW RIBBON** — one `epaint::Mesh` whose cross-section is
/// [`facett_core::render::decor::glow_cross_section`], bright at the centreline and
/// transparent at both edges.
///
/// # Why a mesh and not strokes (owner, 2026-09-03)
///
/// *"its not a soft spline its a flat band with some smoth edges … the eqII paths where
/// like a soul / spirit trace shiny and transparent glowing"*.
///
/// A glow used to be five concentric `Shape::line` strokes drawn over each other. They
/// composite source-over, so the centreline's alpha is `1 − Π(1 − αᵢ)` and the ladder's
/// core pass is `alpha 1.0`: the middle is FULLY OPAQUE and only the outermost halo is
/// soft. That is a band, and nothing shows through it.
///
/// One mesh with per-vertex alpha has no such arithmetic. Every pixel is written once,
/// the alpha is INTERPOLATED between the profile's rings, and the ground stays visible
/// through all of it — which is what makes it read as light rather than as a line.
///
/// # The two things that make it look right rather than merely correct
///
/// * **The offset is taken along the MITRE, not the segment normal.** Using each
/// segment's own normal leaves a wedge on the outside of every bend and a fold on the
/// inside — on a bowed spline, which is exactly what this draws, that reads as a chain
/// of overlapping lozenges. The mitre is the normalised sum of the adjacent normals,
/// rescaled by `1/cos(θ/2)` so the ribbon keeps its PERPENDICULAR width through a turn.
/// * **The mitre is CLAMPED.** A near-reversal sends `1/cos` to infinity and would fire
/// a vertex off the screen; past the limit the joint falls back, which is a visible
/// notch on a hairpin and invisible on anything a map draws.
pub fn glow_ribbon_mesh(
pts: &[egui::Pos2],
core_w: f32,
ink: egui::Color32,
night: bool,
) -> egui::epaint::Mesh {
use facett_core::render::decor::{glow_cross_section, GlowGround};
let mut mesh = egui::epaint::Mesh::default();
if pts.len() < 2 || core_w <= 0.0 {
return mesh;
}
/// Past this the mitre is a spike; fall back to the segment normal.
const MITRE_LIMIT: f32 = 4.0;
let rgb = [
f32::from(ink.r()) / 255.0,
f32::from(ink.g()) / 255.0,
f32::from(ink.b()) / 255.0,
];
let ground = if night { GlowGround::Dark } else { GlowGround::Light };
// Outer → centre. Mirrored below into a full profile: −outer … 0 … +outer.
let half = glow_cross_section(core_w, rgb, ground);
if half.len() < 2 {
return mesh;
}
let profile: Vec<(f32, egui::Color32)> = half
.iter()
.map(|(o, c)| (-*o, glow_rgba32(*c)))
.chain(half.iter().rev().skip(1).map(|(o, c)| (*o, glow_rgba32(*c))))
.collect();
let seg_n = |a: egui::Pos2, b: egui::Pos2| -> egui::Vec2 {
let d = b - a;
let len = d.length().max(1e-6);
egui::vec2(-d.y / len, d.x / len)
};
let mut normals: Vec<egui::Vec2> = Vec::with_capacity(pts.len());
for i in 0..pts.len() {
let n = if i == 0 {
seg_n(pts[0], pts[1])
} else if i == pts.len() - 1 {
seg_n(pts[i - 1], pts[i])
} else {
let (a, b) = (seg_n(pts[i - 1], pts[i]), seg_n(pts[i], pts[i + 1]));
let m = a + b;
let l = m.length();
if l < 1e-6 {
a
} else {
let m = m / l;
// `a·m̂` is cos(θ/2); the mitre scales by its reciprocal.
let cos_half = (a.x * m.x + a.y * m.y).abs().max(1e-6);
m * (1.0 / cos_half).min(MITRE_LIMIT)
}
};
normals.push(n);
}
let cols = profile.len() as u32;
for (i, p) in pts.iter().enumerate() {
for (off, col) in &profile {
mesh.colored_vertex(*p + normals[i] * *off, *col);
}
}
for i in 0..pts.len().saturating_sub(1) {
let (r0, r1) = (i as u32 * cols, (i as u32 + 1) * cols);
for c in 0..cols - 1 {
mesh.add_triangle(r0 + c, r0 + c + 1, r1 + c);
mesh.add_triangle(r1 + c, r0 + c + 1, r1 + c + 1);
}
}
mesh
}
/// Straight (non-premultiplied) linear rgba → egui.
fn glow_rgba32(c: [f32; 4]) -> egui::Color32 {
let f = |x: f32| (x.clamp(0.0, 1.0) * 255.0).round() as u8;
egui::Color32::from_rgba_unmultiplied(f(c[0]), f(c[1]), f(c[2]), f(c[3]))
}
#[cfg(test)]
mod glow_ribbon_tests {
use super::*;
fn straight() -> Vec<egui::Pos2> {
(0..8).map(|i| egui::pos2(10.0 + i as f32 * 20.0, 50.0)).collect()
}
/// **RED-WHEN-BROKEN: the ribbon is transparent at both edges and brightest inside**
/// — the property the stroke stack could not have (owner, 2026-09-03).
///
/// Five source-over strokes composite to `1 − Π(1 − αᵢ)` at the middle, and the
/// ladder's core is `alpha 1.0`, so the trail is OPAQUE there and the ground never
/// shows through. This asserts the opposite on the emitted vertices.
#[test]
fn the_ribbon_fades_at_both_edges_and_peaks_in_the_middle() {
let m = glow_ribbon_mesh(&straight(), 1.6, egui::Color32::from_rgb(50, 200, 255), true);
assert!(!m.is_empty(), "a ribbon over 8 points is not empty");
let cols = m.vertices.len() / 8;
assert!(cols >= 5, "the profile has rings, got {cols} per path vertex");
let row: Vec<u8> = m.vertices[..cols].iter().map(|v| v.color.a()).collect();
assert_eq!(row[0], 0, "the ribbon's first edge is TRANSPARENT: {row:?}");
assert_eq!(*row.last().expect("a row"), 0, "…and so is the far edge: {row:?}");
let peak = row.iter().copied().max().expect("a peak");
assert!(peak > 0, "something is drawn: {row:?}");
let at = row.iter().position(|a| *a == peak).expect("the peak index");
assert!(at > 0 && at < cols - 1, "the peak is INSIDE, not on an edge: {row:?}");
// NON-VACUITY: an all-zero row would satisfy both edge assertions.
assert!(row.iter().filter(|a| **a > 0).count() >= 3, "a real profile: {row:?}");
}
/// **RED-WHEN-BROKEN: a bend is MITRED by `1/cos(θ/2)`.**
///
/// Offsetting along each segment's own normal leaves a wedge on the outside of every
/// bend and a fold on the inside, which on a bowed spline — exactly what the case
/// trail is — reads as a chain of overlapping lozenges.
///
/// **The first version of this test was wrong and the code was right**, which is
/// worth recording. It measured the straight-line distance between the two outermost
/// vertices at a corner and demanded it equal the width on the straight. It does not
/// and must not: a mitre joint's vertex sits `1/cos(θ/2)` FURTHER OUT, and that extra
/// length is precisely what holds the perpendicular width constant. Measured at the
/// 90° corner below: **39.598 against 28.0**, a ratio of 1.41421 — `√2`, i.e.
/// `1/cos(45°)`, to five decimals. So the law itself is what is asserted.
#[test]
fn a_bend_is_mitred_by_one_over_cos_half_theta() {
let corner =
vec![egui::pos2(0.0, 0.0), egui::pos2(100.0, 0.0), egui::pos2(100.0, 100.0)];
let m = glow_ribbon_mesh(&corner, 2.0, egui::Color32::WHITE, true);
let cols = m.vertices.len() / 3;
let span = |i: usize| -> f32 {
let row = &m.vertices[i * cols..(i + 1) * cols];
(row[0].pos - row[cols - 1].pos).length()
};
let (straight_w, joint) = (span(0), span(1));
let ratio = joint / straight_w;
assert!(
(ratio - std::f32::consts::SQRT_2).abs() < 1e-3,
"a 90° corner mitres by 1/cos(45°) = √2; got {ratio} ({joint} / {straight_w}). \
A ratio of 1.0 means the segment normal was used and every bend has a wedge",
);
assert!(
(span(2) - straight_w).abs() / straight_w < 1e-3,
"the far end is straight again",
);
// The CLAMP: a near-reversal sends 1/cos(θ/2) to infinity.
let hairpin =
vec![egui::pos2(0.0, 0.0), egui::pos2(100.0, 0.0), egui::pos2(0.5, 0.0)];
let hm = glow_ribbon_mesh(&hairpin, 2.0, egui::Color32::WHITE, true);
let hcols = hm.vertices.len() / 3;
let hjoint = {
let row = &hm.vertices[hcols..2 * hcols];
(row[0].pos - row[hcols - 1].pos).length()
};
assert!(
hjoint <= straight_w * 4.0 + 1e-3,
"the mitre must be CLAMPED — a hairpin gave {hjoint} against a {straight_w} \
straight, which is a spike off the screen",
);
}
}