facett-map/tests/fill_tess_cache.rs
//! **The fill triangulation must be cached across camera moves, and must be the
//! same fill.** (`mapdraw-1`)
//!
//! MEASURED 2026-08-03 on a real 1600×1000 window against an RTX 4090 (Vulkan,
//! DiscreteGpu — not llvmpipe), 20 000 real Swedish ways / 452 697 vertices, median
//! of 230 frames after a 20-frame warm-up:
//!
//! ```text
//! before after
//! fills only 49.06 ms 9.35 ms 5.25×
//! all layers 43.65 ms 9.71 ms 4.50×
//! lines only 0.26 ms 0.22 ms (untouched)
//! ```
//!
//! `tessellate::triangulate` was 36.22 ms of a 42.45 ms frame — 85.4 % — an O(n²)
//! ear clip over 1 890 filled polygons / 81 906 vertices → 78 126 triangles, redone
//! from scratch every frame. The largest ring in view is 659 vertices, i.e. up to
//! 434 281 in-triangle tests per frame, for geometry that had not moved since it
//! was read off disk.
//!
//! ## Why a rendered frame cannot be the guard
//!
//! Every claim here is about work that did **not** happen. A frame painted from
//! cached indices and a frame painted from a fresh ear clip are the same pixels —
//! that is the point — so no screenshot, no `assert!(drew())`, no feature count and
//! no severity can tell them apart. That is exactly how 85 % of the frame stayed
//! invisible for as long as it did. The observable is [`MapFacet::ear_clips`], and
//! the discriminating assertion is that it STOPS while the camera keeps moving.
use egui::Pos2;
use facett_map::layer::{LatLon, MapFacet, MapTheme, MapView, WaysLayer};
use facett_map::style::MapPalette;
use facett_map::{Way, tessellate};
// ── Fixtures ─────────────────────────────────────────────────────────────────
/// A concave ring with a real notch, spanning Sweden's own latitude range (55 → 69)
/// so the Mercator step is emphatically not a no-op. Closed (first vertex repeated),
/// which is what makes `Way::from_lonlat_with` treat it as an area and fill it.
fn concave_ring() -> Vec<(f64, f64)> {
vec![
(11.0, 55.0),
(24.0, 55.5),
(23.0, 69.0),
(17.5, 60.0), // the notch — a convex fan would fill this in
(12.0, 68.0),
(11.0, 55.0),
]
}
/// A hole inside [`concave_ring`]'s solid part (a lake's island / a courtyard).
fn hole_ring() -> Vec<(f64, f64)> {
vec![(13.0, 57.0), (16.0, 57.0), (16.0, 59.0), (13.0, 59.0)]
}
/// A ring on which ear clipping in `(lon, lat)` and in Mercator genuinely DISAGREE:
/// the lon/lat index set, applied to the Mercator (and hence screen) points,
/// over-fills by **2.71 %** because two of its "ears" stop being ears once latitude
/// is warped. Found by search over random simple 5–7-gons in the Nordic latitude
/// band (`lat 50..72`), keeping only rings that are simple in BOTH spaces and whose
/// lon/lat clip produces a full n−2 triangles — so the disagreement is a genuine
/// space difference and not a degenerate-input artefact.
///
/// It exists because the obvious shortcut ("the rings are already in lon/lat, clip
/// those") is wrong, and nothing in a well-behaved fixture would ever say so.
fn mercator_sensitive_ring() -> Vec<(f64, f64)> {
vec![
(27.903, 67.614),
(24.524, 70.562),
(11.997, 69.997),
(19.462, 68.561),
(22.631, 62.284),
(6.081, 69.861),
(20.899, 54.478),
]
}
fn shift(ring: &[(f64, f64)], dx: f64) -> Vec<(f64, f64)> {
ring.iter().map(|&(lo, la)| (lo + dx, la)).collect()
}
/// A REAL filled way through the real OSM constructor (`natural=water` ⇒ an area
/// with a themed fill), so the fixture is the same kind of object the basemap
/// carries rather than a hand-assembled struct.
fn filled_way(id: i64, outer: &[(f64, f64)], holes: Vec<Vec<(f64, f64)>>) -> Way {
let tags = vec![("natural".to_string(), "water".to_string())];
let pal = MapPalette::cartographic(true);
let mut w = Way::from_lonlat_with(id, outer, &tags, &pal).expect("a 6-vertex ring is a way");
assert!(w.fill.is_some(), "the fixture must actually be a FILLED way");
w.holes = holes;
w
}
// ── Geometry helpers (all in f64 over the projected screen points) ───────────
fn cross(a: Pos2, b: Pos2, c: Pos2) -> f64 {
(f64::from(b.x) - f64::from(a.x)) * (f64::from(c.y) - f64::from(a.y))
- (f64::from(b.y) - f64::from(a.y)) * (f64::from(c.x) - f64::from(a.x))
}
/// Total (unsigned) area of a triangle set indexed into `verts`.
fn tri_area(verts: &[Pos2], tris: &[[u32; 3]]) -> f64 {
tris.iter()
.map(|&[a, b, c]| cross(verts[a as usize], verts[b as usize], verts[c as usize]).abs() / 2.0)
.sum()
}
/// Shoelace area of a ring (a repeated closing vertex contributes zero).
fn ring_area(pts: &[Pos2]) -> f64 {
let mut s = 0.0;
for i in 0..pts.len() {
let p = pts[i];
let q = pts[(i + 1) % pts.len()];
s += f64::from(p.x) * f64::from(q.y) - f64::from(q.x) * f64::from(p.y);
}
s.abs() / 2.0
}
fn in_tri(p: Pos2, a: Pos2, b: Pos2, c: Pos2) -> bool {
let (d1, d2, d3) = (cross(a, b, p), cross(b, c, p), cross(c, a, p));
!((d1 < 0.0 || d2 < 0.0 || d3 < 0.0) && (d1 > 0.0 || d2 > 0.0 || d3 > 0.0))
}
fn covered(p: Pos2, verts: &[Pos2], tris: &[[u32; 3]]) -> bool {
tris.iter()
.any(|&[a, b, c]| in_tri(p, verts[a as usize], verts[b as usize], verts[c as usize]))
}
/// Project a `(lon, lat)` ring through the REAL shared camera projection — the same
/// `MapView::project` every layer and the painter itself go through.
fn project(view: &MapView, ring: &[(f64, f64)]) -> Vec<Pos2> {
ring.iter()
.map(|&(lon, lat)| {
let (x, y) = view.project(lon, lat);
Pos2::new(x, y)
})
.collect()
}
// ── G1 · the cached fill IS the fill ─────────────────────────────────────────
/// **RED-when-broken:** the cached (Mercator-space) index set, applied to the
/// SCREEN-space ring, fills exactly the polygon — outer minus hole — and no more.
///
/// The area equality is the discriminator, and it is an *applied output*: real
/// screen px² of real triangles at a real camera, not a round-trip through the
/// cache. An index set that overlaps its own triangles over-counts; a fan across
/// the notch over-counts; an index set whose vertex order disagrees with
/// [`tessellate::fill_vertices`] addresses the wrong points and lands anywhere.
///
/// **Seen RED** (injection run 2026-08-03, reverted): `fill_vertices` concatenating
/// the hole rings BEFORE the outer ring — the fill came out at 75 669.71 px²
/// against a true 115 835.66 px², i.e. the mesh addressed the wrong points and the
/// water sprayed across the pane.
///
/// What it did NOT catch, stated plainly: making `FillTessCache::tris` tessellate
/// the raw `(lon, lat)` ring instead of its Mercator image leaves this test GREEN.
/// For [`concave_ring`] the two spaces happen to yield equally valid (if different)
/// triangulations, so every area and coverage assert here still holds. Only
/// [`tessellating_in_lon_lat_instead_of_mercator_is_a_different_and_wrong_fill`],
/// which is built on a ring found by search *because* the two spaces disagree on
/// it, goes red for that one. Two guards, two different failure modes — neither is
/// redundant.
#[test]
fn the_cached_ear_clip_fills_exactly_the_polygon_in_screen_space() {
// A ring UNIQUE to this test (base shift 0.41): the tessellation memo is
// process-GLOBAL and content-keyed, so a ring another test already clipped is
// served, not re-clipped — this test's counters must count ITS OWN ring.
let outer = shift(&concave_ring(), 0.41);
let holes = vec![shift(&hole_ring(), 0.41)];
let cache = tessellate::FillTessCache::new(1);
let tris = cache.tris(0, &outer, &holes).expect("a closed 6-vertex ring tessellates");
assert!(!tris.is_empty(), "the ring produced triangles");
let view = MapView::new(LatLon::new(62.0, 17.0), 5.0, (1600.0, 1000.0));
let sp_outer = project(&view, &outer);
let sp_holes: Vec<Vec<Pos2>> = holes.iter().map(|h| project(&view, h)).collect();
let verts = tessellate::fill_vertices(&sp_outer, &sp_holes);
// AREA: outer − hole, in real screen px², to 0.1 %.
let want = ring_area(&sp_outer) - ring_area(&sp_holes[0]);
let got = tri_area(&verts, &tris);
assert!(want > 1.0e4, "the fixture is a big on-screen polygon, not a speck: {want} px²");
assert!(
(got - want).abs() / want < 1.0e-3,
"cached fill area {got} px² must equal outer−hole {want} px² — an overlap or a \
spill over-counts, a dropped triangle under-counts"
);
// COVERAGE, at three points that each mean something different.
let hole_centre = project(&view, &[(14.5, 58.0)])[0];
assert!(
!covered(hole_centre, &verts, &tris),
"the hole must stay punched out once the indices are applied under a camera"
);
let solid = project(&view, &[(12.5, 56.0)])[0];
assert!(covered(solid, &verts, &tris), "the solid part of the ring must be filled");
let notch = project(&view, &[(17.6, 66.0)])[0];
assert!(!covered(notch, &verts, &tris), "the concave notch must NOT be filled (no fan spill)");
}
/// The cached path and the uncached path must produce the **same fill**, not merely
/// two fills of equal area: same triangle count, same total area, and the same
/// verdict at every probe point. This is the A/B that says "switching the cache on
/// changed no pixels".
#[test]
fn cached_and_uncached_tessellation_agree_on_the_same_ring() {
// A ring UNIQUE to this test (base shift 0.53): the tessellation memo is
// process-GLOBAL and content-keyed, so a ring another test already clipped is
// served, not re-clipped — this test's counters must count ITS OWN ring.
let outer = shift(&concave_ring(), 0.53);
let holes = vec![shift(&hole_ring(), 0.53)];
let view = MapView::new(LatLon::new(60.0, 15.0), 5.5, (1600.0, 1000.0));
let sp_outer = project(&view, &outer);
let sp_holes: Vec<Vec<Pos2>> = holes.iter().map(|h| project(&view, h)).collect();
let verts = tessellate::fill_vertices(&sp_outer, &sp_holes);
// The path that shipped: ear clip the SCREEN-space ring, every frame.
let (live_verts, live_tris) = tessellate::triangulate_with_holes(&sp_outer, &sp_holes);
// The path that ships now: ear clip the MERCATOR ring, once, ever.
let cache = tessellate::FillTessCache::new(1);
let cached = cache.tris(0, &outer, &holes).expect("tessellates");
assert_eq!(live_verts, verts, "both paths mesh over the same vertex list, in the same order");
assert_eq!(
live_tris.len(),
cached.len(),
"a simple polygon has n−2 triangles either way ({} live vs {} cached)",
live_tris.len(),
cached.len()
);
let (a, b) = (tri_area(&verts, &live_tris), tri_area(&verts, &cached));
assert!((a - b).abs() / a < 1.0e-3, "same filled area: live {a} px² vs cached {b} px²");
// Same coverage verdict on a grid over the polygon's screen bbox — this is what
// "no pixel changed" actually means, and it catches a same-area-different-shape
// triangulation that the area assert alone would wave through.
let (x0, x1) = (
sp_outer.iter().map(|p| p.x).fold(f32::MAX, f32::min),
sp_outer.iter().map(|p| p.x).fold(f32::MIN, f32::max),
);
let (y0, y1) = (
sp_outer.iter().map(|p| p.y).fold(f32::MAX, f32::min),
sp_outer.iter().map(|p| p.y).fold(f32::MIN, f32::max),
);
let mut probes = 0usize;
let mut disagreements = 0usize;
for i in 0..40 {
for j in 0..40 {
let p = Pos2::new(
x0 + (x1 - x0) * (i as f32 + 0.5) / 40.0,
y0 + (y1 - y0) * (j as f32 + 0.5) / 40.0,
);
probes += 1;
if covered(p, &verts, &live_tris) != covered(p, &verts, &cached) {
disagreements += 1;
}
}
}
assert_eq!(
disagreements, 0,
"cached and live tessellation disagreed at {disagreements}/{probes} probe points \
inside the polygon's screen bbox"
);
}
// ── G2 · the indices survive a camera move (the affine-invariance claim) ─────
/// **RED-when-broken:** ONE cached index set, applied at six genuinely different
/// cameras — pan, zoom, bearing, tilt, and all of them at once — fills exactly the
/// projected polygon at every one. This is the property the whole change rests on:
/// `MapView::project` is `affine(mercator(lon, lat))`, a triangulation is
/// affine-invariant, so the indices are a function of the DATA and not the camera.
///
/// The identity trap this deliberately avoids (LAW #2): a test at one camera — or
/// at several that differ only by a uniform scale — cannot tell a
/// camera-independent triangulation from a camera-dependent one, because a uniform
/// scale is the transform under which even a WRONG index set keeps its area ratio.
/// Bearing 41° and tilt 35° are in the list precisely because they are the
/// transforms that "it's just a scale and an offset" does not cover.
#[test]
fn one_cached_index_set_fills_correctly_at_every_camera() {
// A ring UNIQUE to this test (base shift 0.67): the tessellation memo is
// process-GLOBAL and content-keyed, so a ring another test already clipped is
// served, not re-clipped — this test's counters must count ITS OWN ring.
let outer = shift(&concave_ring(), 0.67);
let holes = vec![shift(&hole_ring(), 0.67)];
let cache = tessellate::FillTessCache::new(1);
let tris = cache.tris(0, &outer, &holes).expect("tessellates");
assert_eq!(cache.ear_clips(), 1, "one ring, one ear clip");
// (lat, lon, zoom, bearing°, tilt°)
let cams: [(f64, f64, f32, f32, f32); 6] = [
(62.0, 17.0, 5.0, 0.0, 0.0),
(62.0, 17.0, 9.5, 0.0, 0.0), // deep zoom — a uniform scale
(58.0, 12.0, 5.0, 0.0, 0.0), // panned off-centre
(62.0, 17.0, 5.0, 41.0, 0.0), // ROTATED — not a scale
(62.0, 17.0, 5.0, 0.0, 35.0), // TILTED — anisotropic
(59.5, 20.0, 7.25, 137.0, 22.0), // all four at once
];
for (lat, lon, zoom, bearing, tilt) in cams {
let mut view = MapView::new(LatLon::new(lat, lon), zoom, (1600.0, 1000.0));
view.bearing_deg = bearing;
view.tilt_deg = tilt;
let sp_outer = project(&view, &outer);
let sp_holes: Vec<Vec<Pos2>> = holes.iter().map(|h| project(&view, h)).collect();
let verts = tessellate::fill_vertices(&sp_outer, &sp_holes);
let want = ring_area(&sp_outer) - ring_area(&sp_holes[0]);
let got = tri_area(&verts, &tris);
assert!(want > 1.0, "camera (bearing {bearing}, tilt {tilt}) still shows the polygon");
assert!(
(got - want).abs() / want < 1.0e-3,
"at (lat {lat}, lon {lon}, zoom {zoom}, bearing {bearing}°, tilt {tilt}°) the ONE \
cached index set must still fill exactly outer−hole: got {got} px², want {want} px²"
);
}
assert_eq!(
cache.ear_clips(),
1,
"six cameras must not have re-triangulated anything — the cache key is the DATA"
);
}
/// **The Mercator step is load-bearing, and here is the proof.** Ear-clipping the
/// raw `(lon, lat)` ring and applying those indices to the projected polygon is
/// NOT equivalent — Mercator warps latitude nonlinearly, so a country-scale ring
/// triangulates differently in the two spaces.
///
/// This is the guard against the plausible-looking shortcut ("the rings are already
/// in lon/lat, just clip those"), and it is written as an inequality on purpose:
/// it fails the moment [`tessellate::FillTessCache`] stops projecting to Mercator
/// first, which no area-equality test on the correct implementation could ever see.
#[test]
fn tessellating_in_lon_lat_instead_of_mercator_is_a_different_and_wrong_fill() {
let outer = mercator_sensitive_ring();
let holes: Vec<Vec<(f64, f64)>> = vec![];
let view = MapView::new(LatLon::new(62.0, 17.0), 5.0, (1600.0, 1000.0));
let sp_outer = project(&view, &outer);
let want = ring_area(&sp_outer);
// What the implementation does: clip the Mercator image.
let cache = tessellate::FillTessCache::new(1);
let merc_tris = cache.tris(0, &outer, &holes).expect("tessellates");
let got_merc = tri_area(&sp_outer, &merc_tris);
assert!(
(got_merc - want).abs() / want < 1.0e-3,
"Mercator-space indices fill the projected ring exactly: {got_merc} vs {want}"
);
// The shortcut: clip the raw lon/lat ring, apply to the projected points.
let ll: Vec<Pos2> = outer.iter().map(|&(lo, la)| Pos2::new(lo as f32, la as f32)).collect();
let ll_tris = tessellate::triangulate(&ll);
let got_ll = tri_area(&sp_outer, &ll_tris);
// They must not be the same triangulation. If this ever passes it means the
// fixture stopped spanning enough latitude for Mercator to matter — fix the
// fixture, do not delete the assert.
assert_ne!(
merc_tris.as_ref(),
ll_tris.as_slice(),
"lon/lat and Mercator must give DIFFERENT ear clips for a 14°-of-latitude ring — \
if they agree, this test can no longer tell the two spaces apart"
);
assert!(
(got_ll - want).abs() / want > 1.0e-3,
"the lon/lat shortcut must MIS-fill the projected ring ({got_ll} px² vs the true \
{want} px², off by {:.2} %); if it happens to be right here the guard is blind",
(got_ll - want).abs() / want * 100.0
);
}
// ── G3 · the live facet stops ear-clipping while the camera keeps moving ────
/// **THE `mapdraw-1` claim, driven through the real widget.**
///
/// Mounts the real [`MapFacet`] in `egui_kittest` and paints 40 frames, moving the
/// camera between every one — pan, zoom AND bearing, so no two frames share a
/// projection. The ear-clip count must reach the number of filled areas once and
/// then stop dead.
///
/// **Seen RED twice** (injections run 2026-08-03, both reverted):
/// * `WaysLayer::features_into` emitting `tri: None` — the code exactly as it
/// shipped. `ear_clips` stays 0 forever while `triangulate` runs once per filled
/// way per frame, and the FIRST assert catches it (`0 != 12`). This is why the
/// guard asserts the ceiling is reached rather than merely `> 0`.
/// * `FillTessCache::tris` recomputing on every call instead of latching the
/// `OnceLock` — a cache that does not cache. `ear_clips` then climbs by 12 every
/// frame and the per-frame assert fires on frame 0.
///
/// Both broken states paint byte-identical pixels, which is precisely why the guard
/// measures the work and not the picture.
#[test]
fn a_moving_camera_does_not_re_triangulate_the_basemap() {
const FILLS: usize = 12;
// A base offset UNIQUE to this test: the tessellation memo is process-GLOBAL
// and keyed on ring coordinates (a ring another test already clipped is served,
// not re-clipped — that is the memo's contract, `tessellate.rs`), and the
// sibling tests in this binary use `concave_ring()` at dx 0 / the same 0.02
// grid. Without the base, this test's i=0 ring collides with theirs and the
// first frame honestly clips 11 — the guard must count THIS test's distinct
// rings, so the rings must be this test's alone.
let ways: Vec<Way> = (0..FILLS)
.map(|i| {
let dx = 0.0137 + i as f64 * 0.02;
filled_way(i as i64 + 1, &shift(&concave_ring(), dx), vec![shift(&hole_ring(), dx)])
})
.collect();
// Zoom 7 = the REGION lod tier. `natural=water` is a Region-tier way, so at the
// country tier (zoom < 6) `lod_visible` culls all twelve and the guard would sit
// on 0 ear clips and pass while proving nothing — the exact hollow-green shape
// this file exists to avoid. Every camera below stays at zoom >= 7.
let view = MapView::new(LatLon::new(62.0, 17.0), 7.0, (900.0, 700.0));
let mut facet =
MapFacet::new("map", view, MapTheme::cartographic(&facett_core::Theme::default(), true));
facet.push_layer(Box::new(WaysLayer::new("areas", ways)));
assert_eq!(facet.ear_clips(), 0, "nothing tessellated before the first paint");
assert_eq!(facet.fill_polygon_count(), FILLS, "the fixture really is {FILLS} filled areas");
let mut harness = egui_kittest::Harness::builder()
.with_size(egui::Vec2::new(900.0, 700.0))
.build_ui_state(|ui, f: &mut MapFacet| f.ui(ui), facet);
harness.run();
let after_first = harness.state().ear_clips();
assert_eq!(
after_first, FILLS,
"the first painted frame must tessellate ALL {FILLS} filled areas — a guard that \
starts at 0 and stays at 0 would pass while the cache does nothing, and one that \
starts below the ceiling cannot tell a later first-clip from a re-clip"
);
let mut seen_cameras = Vec::new();
for frame in 0..40u32 {
{
// A genuinely different camera every frame: pan, zoom AND rotate.
// Pan small enough that all twelve areas stay on screen (so a rising
// count can only mean a RE-clip, never a first clip), zoom always in the
// Region tier, bearing right around the compass.
let v = harness.state_mut().view_mut();
v.center = LatLon::new(62.0 + f64::from(frame) * 0.004, 17.0 + f64::from(frame) * 0.006);
v.zoom = 7.0 + (frame % 7) as f32 * 0.15;
v.bearing_deg = (frame * 9) as f32;
seen_cameras.push((v.center.lat, v.zoom, v.bearing_deg));
}
harness.run();
let now = harness.state().ear_clips();
assert_eq!(
now, after_first,
"frame {frame} (lat {:.2}, zoom {:.2}, bearing {}°) ran {} extra ear clips — a \
camera move must never re-triangulate: the projection is affine and ear clipping \
is affine-invariant",
seen_cameras[frame as usize].0,
seen_cameras[frame as usize].1,
seen_cameras[frame as usize].2,
now - after_first
);
}
let end = harness.state().ear_clips();
assert!(
end <= FILLS,
"at most one ear clip per filled area, ever — {end} > {FILLS} means something \
re-tessellated behind the cache"
);
// The cameras really were 40 distinct ones (guard against a loop that did nothing).
seen_cameras.dedup();
assert_eq!(seen_cameras.len(), 40, "every frame really did carry a different camera");
// And the number a robot/About box reads agrees with the accessor.
let st = harness.state().state_json();
assert_eq!(
st["fill_tess"]["ear_clips"].as_u64().expect("state_json publishes the ear-clip count"),
end as u64,
"state_json's fill_tess.ear_clips must be the same number MapFacet::ear_clips returns"
);
assert_eq!(
st["fill_tess"]["polygons"].as_u64().expect("state_json publishes the polygon ceiling"),
FILLS as u64
);
}