nordisk/facett

The OSM 2D NAVIGATOR — pins, clustering, and a measured frame budget

nornir:class=design

The NAVIGATOR half of the two-viewer partition (osm-3d-gaps.md): Garmin-nav quality, no street-level walk (that is FLIGHT's). This round gave it pin clustering and, for the first time, real numbers. Only the chosen design is named here.

1. What the field does, and what we took from it

Read before designing, per the brief.

MapLibre / Mapbox — symbol placement is the hard part. MapLibre Native treats symbol placement + collision detection as one of the most complex parts of its whole rendering pipeline. Two ideas are worth stealing outright:

• Cross-tile symbol identity. MapLibre keeps a CrossTileSymbolIndex that assigns each symbol an id persisting across zoom levels, specifically so symbols do not pop in and out or jump when you zoom. We already had the primitive — Pin::id is a stable id invariant across pan/zoom — and clustering had to preserve it rather than mint per-frame ids. Hence a cluster's id is derived from its first member (cluster:<n>@<id>), not from its screen position: a stable pile keeps a stable id.
• Variable placement + sort keys. Mapbox's label engine tries several anchors per label and uses a sort key to decide who wins a collision. We have not adopted variable anchors yet (see §5); the honest status is that our labels are fixed-anchor.

Marker clustering — grid vs hierarchical. Google's GridAlgorithm divides the map into equal squares (default 60×60 px) and groups markers per square; its documented weakness is that it does not cache, so markers may flash as the viewport changes. Supercluster's hierarchical-greedy approach clusters at the deepest zoom and folds clusters upward, which is what makes millions of points tractable in a browser.

Our choice: screen-space grid, and here is why it is the right one for us. The hierarchical win is amortising across zoom levels for a dataset too large to re-cluster per frame. Our pin overlay is an annotation layer — hundreds to a few thousand markers, not millions; the millions live in the point layer, which has its own spatial index (§3). Measured, clustering 100000 pins costs 3.16 ms and 5000 pins costs a fraction of a frame, so a per-frame O(n) pass is simply not the bottleneck, and it buys three things a precomputed hierarchy does not:

• it is exact for the current camera — no zoom-level quantisation, so there is no "cluster snaps at a zoom boundary";
• the flashing Google's grid algorithm warns about comes from re-binning against a moving geographic lattice; binning in screen space with a fixed pixel pitch means a pan translates the lattice with the content, and identity is carried by the member ids rather than the bin;
• it is trivially exact to test — no cache to invalidate.

If the pin layer ever grows to Supercluster scale, the hierarchical fold is the upgrade path and cluster_projected is the leaf it would call.

2. Pin clustering — the design

facett-geomap/src/osm2d/cluster.rs.

Screen-space bins of CLUSTER_BIN_PX = 44.0 — about three marker widths. Binning after projection means the threshold is "these markers would visually collide", which is a screen distance; one lattice therefore works at every zoom and every latitude. A geographic lattice clusters far too aggressively near the poles, where Mercator stretches.

state_json publishes both numbers: visible_pins (pins represented) and visible_markers (badges + singles painted). The compression is therefore a matrix oracle, not a claim. member_lonlat_bbox gives a host the geographic bounds of a group so "click a cluster to zoom into it" is a one-liner.

Proofs: cluster.rs's own unit tests (bin-edge sweep, centroid, determinism over 64 repeats, conservation over 5 densities, lossless off switch) and the robot scenario tests/osm_pin_clusters.rs (zoom sweep: compresses ≥4× zoomed out, one-marker-per-pin zoomed in, counts never lie at any step; group click selects the group id, lone click still selects the pin id).

3. FAST RENDERING — the bench, and the bug it found

facett-geomap/benches/heavy_navigator.rs. Benching the parts a frame is made of, swept 10k → 1M, Throughput::Elements throughout.

The bug

PointGrid documents: "touches only the overlapping cells, so the cost scales with what's on screen, not the dataset size." It did not. The lattice was laid over the whole [0,1] Mercator unit square, so a regional dataset collapsed into a corner of it. Sweden is ~3.6% of the world in x and ~4% in y, so a 256×256 world lattice gave it about 90 live cells — roughly 11000 points per cell at 1M — and a city-block viewport still had to scan whole 11000-point cells. The bench made it obvious: cull_city_block/1000000 timed 5.77 ms, byte-for-byte the same as cull_whole_country/1000000.

Two fixes:

1. The lattice spans the DATA's bbox, not the world, restoring the designed ~8 points/cell at any extent.
2. A whole-data fast path: when the viewport contains the entire dataset (the zoomed-all-the-way-out frame) the lattice buys nothing — every cell is visited anyway, and hopping between 65536 separate Vecs costs more than one sequential sweep. That case now extend_from_slices the contiguous position array.

The oracle is structural, not a timing (timings are the bench's job): tests/point_grid_locality.rs asserts that a city block's 3×3 neighbourhood stays a slice of the dataset (it used to be the whole cloud), that occupancy stays low across town/country/world extents, that degenerate extents stay finite and lossless, and that the cull returns exactly what it did before.

The numbers

Host: Threadripper PRO 3975WX, 32 physical cores, SMT off, 499 GB RAM, Radeon 890M iGPU. Single-threaded arms; plain numbers.

Unchanged arms (they were never the problem):

The rollup — one navigator frame's cull + clustering over 1000000 points and 5000 pins: 368210 ns. 0.37 ms of a 16.7 ms 60 fps budget, i.e. ~2 % of the frame, leaving the rest to the painter. That is the first measured number this part of facett has ever had; "60 fps over 1M+ rows" was previously a documented target, never a measurement.

A bench trap worth recording: the "close" camera in the bench initially used zoom_by, which moves target_zoom while viewport_merc_bbox reads the eased live zoom — so the close camera was byte-identical to the wide one and the arm silently benched the same viewport twice. It now settles the easing (while close.tick() {}) and asserts the close camera is really zoomed in, so the comparison cannot degenerate again.

4. What the navigator already had (not re-derived)

Pins registered to (lon, lat) on the f64 to_px lane with a <1 px alignment guard at max zoom; stable ids; click hit-test → selected_pin in state_json; one AccessKit node per on-screen marker; inertial pan with momentum decay; zoom-to-cursor anchoring; LOD stride growth; road-class styling and palette modes; the compass rose and scale bar; a Garmin overlay set. Those were already proven and are untouched.

4b. THE BUILDING-VERTEX LOD — "the corners look like a sea"

facett-geomap/src/osm2d.rs.

The point layer is the OSM node cloud, and in a real extract most nodes are building corners. It painted every surviving node as a circle at any zoom, in the theme's point hue — an unrelated blue on the cartographic-day paper. At the demo's Sigtuna fit the painter emitted ~21500 dots of radius 3 px over an 800×600 pane: 600000 px² of ink on a 480000 px² pane, i.e. more than a full screen of dots. No colour fixes that. It is an LOD rule.

The rule is screen INK, not metres-per-pixel, and that is the whole design decision. point_ink_frac = the dots' combined area over the pane; over POINT_INK_FRAC_MAX = 0.06 the layer emits ZERO primitives. Ink is data-aware, so it is right at both ends where a m/px threshold is right at only one:

• a dense node cloud is culled the moment its dots merge into a texture — for the Sigtuna extract the knee lands at ~1–2 m/px, i.e. exactly building zoom (below it a 10 m wall spans ≥ 5 px and its corners are distinct ink on a visible footprint);
• a sparse annotation layer (tens of points) is never culled at any zoom, because tens of dots are nowhere near a screenful. A m/px rule would have blanked the demo's 43-point "collector data layers" pane — the same class of bug as the zoom-only stride it sits next to.

Colour: a visible corner is MapPalette::building_stroke, hoisted out of recolor_way so the corner and the wall it sits on are the same value by construction (L5).

Debug mode, default OFF, reachable from the UI: a debug pts checkbox in the pane's own header (so every host that mounts the Facet gets it), the V key, and Msg::SetDebugPoints. It bypasses the cull and paints a 3 Hz magenta↔lime flash — two colours no cartographic palette contains, asserted.

state_json publishes points_culled, point_ink_frac and max_point_ink_frac, so the verdict is reproducible from state alone.

Oracle: tests/osm_point_lod.rs. The RED-when-broken one is a count because that is what the bug was — drawn_points == 0 at a whole-dataset camera over a 40000-node cloud, where the pre-fix painter drew five figures; the frame's ink is asserted > 1.0 so the test records the magnitude of the defect, not just its sign.

Bench (host oden, 32 cores, RTX 4090; plain ns): points/lod_decision 2, points/cull_then_lod_wide/10000 1468, /100000 18486, /1000000 749280. The verdict costs 2 ns per frame and removes tens of thousands of circle_filled tessellations from the zoomed-out frame.

5. Open, in priority order

1. Label collision. Pins collide-cluster; their labels do not. This is the MapLibre lesson we have taken only half of. Next: a screen-space collision box per label with a sort key, and variable anchors (Mapbox's text-variable-anchor idea) so a label that would collide tries another side before being dropped.
2. Cluster spiderfy / zoom-on-click. member_lonlat_bbox is there; the pane does not yet act on a group click. One Msg away.
3. Edge thinning at density for the graph overlay — the same problem as label overplotting, one layer down.
4. Vector-tile ingest. We read whole GeoParquet extents; a real tiling pipeline (fetch/decode/evict per tile) is what would take this from "fast over a loaded region" to "fast over a planet". facett-map3d-flight already has the tile planner; the 2D side should consume the same one rather than grow its own.