nordisk/facett

OSM rendering techniques — facett 2D + 3D (wgpu + CPU fallback)

How facett draws OSM maps fast, navigably, and from any angle — the algorithms, spatial indices, and cutting-edge tricks actually used. Companion to the build spec osm-viewer-spec.md. Grounded in the real impls: facett-geomap/src/osm2d.rs (2D), facett-map/src/gpu (wgpu accel), facett-map3d/src/{lib.rs,camera.rs} (3D).

Device-adaptive design (the big idea)

Two render paths behind one viewer, picked by device class:

The CPU path is universal (the default viewer renders through the egui painter, so it runs with no GPU at all); the wgpu compute path is the fast-lane for massive datasets when a GPU is present. The spatial index, LOD, projection, and clipping below run identically on both paths — only the final draw differs (GPU draw_indirect vs CPU-tessellated painter shapes).

2D techniques

Projection. Web Mercator units; MercatorCamera (osm2d.rs) maps merc↔px with center+zoom. viewport_merc_bbox(rect) is the cull key every frame (it unprojects all four pane corners, so a tilted view's receding trapezoid is still fully culled). Optional 2.5D tilt: pitch_deg (with_tilt/Msg::SetTilt, clamped [0,60]) leans the flat ground plane back toward the horizon — a perspective foreshortening applied inside the single to_px (about the pane's horizontal centre axis: north recedes, south comes forward) and exactly inverted in to_merc, so zoom-to-cursor + hit-testing stay truthful when leaned. Because every layer projects through that one to_px, ways/points/pins/graph tilt as one and stay registered; pitch_deg == 0 is byte-identical to the top-down map. No textures/lighting — this is the 2D viewer's cheap lean, distinct from the full 3D facett-map3d city. The GPU line lane is flat, so it falls back to the CPU painter while tilted.

Overlays (shared coordinate space — one to_px, no twin): the cartographic palette (with_palette/cartographic(day)) reskins the built way set + paints a preset land background as the Garmin car-navigator basemap (see the subsection below); address pins (with_pins) are labelled markers registered to (lon,lat) with a stable-id click hit-test + per-pin AccessKit node; the graph overlay (with_graph) draws a reused facett-graphview GraphModel with each node placed at a geo (lon,lat) and projected through the SAME map to_px (dodging graphview's [0.25,4] zoom clamp) — a node co-located with a way vertex lands on it (<1px alignment guard). All report through state_json.

Garmin car-navigator basemap (cartographic mode — facett-geomap/src/osm2d.rs). cartographic(day) paints the way set as a real turn-by-turn nav map, not a flat theme reskin (#50):

• Road-class hierarchy — each way is ranked 0..4 by facett_map::style::road_rank (4 = motorway/trunk, 3 = primary, 2 = secondary, 1 = tertiary, 0 = residential/minor) and drawn in class order so a highway reads above a lane.
• Casing then fill (two passes) — Pass 1 draws every road's dark casing first (low→high rank, widening with class), so a higher road's casing is never cut by a lower one; Pass 2 lays the bright road fill on top of all the casings.
• One-way chevrons — draw_direction_arrows drops ›-shaped chevrons along each one-way road (spaced by arc-length), pointing in travel direction (sense flips for a reverse one-way).
• Route ribbon — with_route/set_route paints a bright cased ribbon (dark casing → bright fill → forward chevrons, wider than a road) over the basemap and below the pins.
• Priority labels — one horizontal road-name label per named road at its on-screen midpoint, ranked by class with a greedy collision test; pins reserve their boxes first so a name never lands on a pin; luminance-chosen halo; MAX_LABELS = 48, count cached in last_vis_labels.

Spatial indices (O(visible), not O(all)):

• Points → a dependency-free uniform grid (PointGrid): the frame queries only the cells the viewport overlaps. Bulk-built once; brute-force fallback for tiny N. (An rstar R*-tree is the drop-in for skewed data — see spec.)
• Ways → facett-map's MapIndex: LOD tiers (country/region/city) + per-way Mercator bbox; query_visible(vp, lod) returns only ways crossing the viewport at the current zoom's tier.

Level of detail (LOD):

• Point-stride decimation — when zoomed out, draw every Nth point (point_stride rises with span) so a continent isn't a million-dot blob.
• Douglas–Peucker line simplification per LOD tier — drop sub-pixel vertices on ways far from the camera (see spec; tier split in MapIndex).

Segment clipping (the flicker fix — cutting-edge correctness): a bbox-culled way can still have vertices far off-screen; at high zoom to_px maps them to ~1e8 px, and egui's line/mesh tessellation of a near-infinite point flickers / shoots lines off-screen. So geometry is clipped to a margin-expanded viewport before drawing — Liang–Barsky per-segment for line ways (emitting clipped sub-polylines), Sutherland–Hodgman polygon clip for filled ways (the rect is convex, so it's correct for concave OSM polygons too). Preserves slopes (no point-clamping). Implemented in osm2d.rs.

Zero per-frame allocation. A reused scratch: Vec<Pos2> + vis_pts buffer — the hot polyline/point path never heap-allocates. (wgpu path goes further: geometry is uploaded once to VRAM; a frame only writes the camera uniform.)

Navigation (state of the art map UX): wheel zoom-to-cursor (zoom_to anchors the geo point under the cursor — the slippy-map standard), drag-pan, keyboard pan/zoom via the per-OS keymap, damped zoom (1-exp ease), macOS pinch/two-finger folded through egui's zoom_delta/scroll honoring OS natural-scroll.

3D techniques

Camera (facett-map3d/src/camera.rs OrbitCamera): spherical coords (azimuth + elevation + distance) around a target; real perspective look-at (foreshortening + parallax); pole-clamped elevation (no gimbal flip). Dolly-to-cursor shifts the target along the cursor ray so the point under the cursor stays put. View presets (top/iso/oblique/front) snap azimuth+elevation. Frame-rate- independent damping 1-exp(-k·dt) toward goal pose (deterministic settle() for headless tests).

Geometry + perf:

• Extrusion — OSM ways/buildings → 3D prisms (height from tags / default), emitted as instanceable geometry.
• Frustum cull (drop tris behind the eye / outside the view), back-face cull (screen-space winding), then — on the CPU path — a software z-buffer (raster_zbuffer, a true 1/z per-pixel depth test) resolves occlusion. It replaces the old painter's-algorithm centroid sort, which tore where a small near face sat behind a large one (the depth-tearing fix); each vertex now carries its view-space depth vz.
• ACES tonemap — shaded colour runs through aces_tonemap (Narkowicz ACES, tonemap_shaded/cpu_exposure) so the CPU look matches the wgpu path's curve.
• Project once into a reused buffer — no per-tri re-projection or per-frame alloc.
• GPU path: instanced meshes + depth buffer; far prisms use DP-simplified mesh LOD by camera distance.

Cutting-edge tricks, in one list

1. Compute-shader frustum cull + draw_indirect (GPU does the culling; CPU never walks the full set on the fast path).
2. Upload-once VRAM geometry — pan/zoom = a uniform write, not a re-upload.
3. Spatial index everywhere (grid / LOD-tier+bbox / R-tree) → O(visible).
4. Zoom→LOD ladder: point-stride decimation + Douglas–Peucker line simplification.
5. Liang–Barsky + Sutherland–Hodgman clipping to kill far-coordinate tessellation artifacts (the corner-case flicker).
6. Zero per-frame heap alloc (reused scratch buffers).
7. Dolly/zoom-to-cursor (the point under the cursor stays fixed) in both 2D and 3D.
8. Critically-damped, frame-rate-independent camera (1-exp(-k·dt)) — smooth + deterministic under an injected clock (so it's testable headless).
9. Per-OS input feel (macOS pinch/natural-scroll/momentum vs Windows wheel) read from the active keymap/scroll preset — never re-invert egui's normalized deltas.
10. One viewer, two backends: universal CPU painter path (no GPU needed) + wgpu compute/instancing fast-lane — same index/LOD/projection, different draw.
11. One to_px for every layer → overlays (pins, geo-placed graph) register to the basemap for free; a co-located feature is <1px off (shared coordinate space).
12. Optional 2.5D tilt as a perspective divide inside to_px (exactly inverted in to_merc) — the whole map + overlays lean as one, pitch=0 is byte-identical, no textures/lighting (the 2D viewer's cheap lean, not the 3D city).
13. Garmin car-navigator 2D basemap — road-class hierarchy (ranked), casing-then-fill passes, one-way chevrons, a cased route ribbon, and priority road-name labels with collision-avoidance (pins reserve boxes first).
14. Software z-buffer on the CPU 3D path (true 1/z per-pixel depth, no painter's-sort tearing) + ACES tonemap matching the wgpu look — the whole city renders correctly on llvmpipe / wasm with no GPU.

Where it lives

• 2D: facett-geomap/src/osm2d.rs (OsmView/MercatorCamera/PointGrid), ways via facett-map MapIndex, wgpu accel facett-map/src/gpu.
• 3D: facett-map3d/src/{lib.rs,camera.rs} (Map3D/OrbitCamera), GPU mesh path reuses facett-graph3d logo3d::gpu.
• All implement the canonical Facet trait + state_json (camera pose, visible feature/tri count, fps) so the test matrix mechanically discovers + asserts them.