rustial_engine/terrain/

terrain_manager.rs

//! Terrain manager: fetches, caches, and generates terrain meshes.

use crate::camera_projection::CameraProjection;
use crate::terrain::backfill::{
    expand_with_clamped_border, patch_changed_tiles, BackfillState,
};
use crate::terrain::config::TerrainConfig;
use crate::terrain::elevation_source::ElevationSourceDiagnostics;
use crate::terrain::hillshade::{prepare_hillshade_raster, PreparedHillshadeRaster};
use crate::terrain::mesh::{build_terrain_descriptor_with_source, skirt_height, TerrainMeshData};
use crate::tile_manager::TileTextureRegion;
use rustial_math::{visible_tiles, visible_tiles_lod, ElevationGrid, GeoCoord, TileId, WorldBounds};
use std::collections::HashMap;

/// Snapshot diagnostics for the terrain pipeline.
#[derive(Debug, Clone, Default, PartialEq)]
pub struct TerrainDiagnostics {
    /// Whether terrain rendering is enabled.
    pub enabled: bool,
    /// Number of cached elevation tiles currently retained.
    pub cache_entries: usize,
    /// Number of elevation fetches currently pending.
    pub pending_tiles: usize,
    /// Number of terrain mesh descriptors visible in the most recent frame.
    pub visible_mesh_tiles: usize,
    /// Number of visible tiles whose elevation source data is cached.
    pub visible_loaded_tiles: usize,
    /// Number of visible tiles whose elevation source data is still pending.
    pub visible_pending_tiles: usize,
    /// Number of visible tiles currently using flat placeholder elevation.
    pub visible_placeholder_tiles: usize,
    /// Number of prepared hillshade rasters for the most recent visible terrain set.
    pub visible_hillshade_tiles: usize,
    /// Elevation source max zoom currently configured.
    pub source_max_zoom: u8,
    /// Most recent desired terrain zoom requested by the terrain manager.
    pub last_desired_zoom: u8,
    /// Terrain mesh resolution configured on the manager.
    pub mesh_resolution: u16,
    /// Terrain vertical exaggeration currently in effect.
    pub vertical_exaggeration: f64,
    /// Terrain skirt depth in meters.
    pub skirt_depth_m: f64,
    /// Minimum visible terrain elevation in rendered meters, if any visible mesh has elevation data.
    pub visible_min_elevation_m: Option<f64>,
    /// Maximum visible terrain elevation in rendered meters, if any visible mesh has elevation data.
    pub visible_max_elevation_m: Option<f64>,
    /// Number of visible terrain descriptors carrying an elevation texture payload.
    pub elevation_texture_tiles: usize,
    /// Total materialized terrain vertices currently present in the visible mesh set.
    pub materialized_vertex_count: usize,
    /// Total materialized terrain indices currently present in the visible mesh set.
    pub materialized_index_count: usize,
    /// Optional transport/failure diagnostics from the active elevation source.
    pub source_diagnostics: Option<ElevationSourceDiagnostics>,
}

/// Clamp a tile ID to a maximum zoom level by walking up to the
/// nearest ancestor at or below `max_zoom`.
///
/// If the tile is already at or below `max_zoom`, it is returned
/// unchanged.
fn clamp_tile_to_zoom(tile: TileId, max_zoom: u8) -> TileId {
    if tile.zoom <= max_zoom {
        return tile;
    }
    let dz = tile.zoom - max_zoom;
    let scale = 1u32 << dz;
    TileId::new(max_zoom, tile.x / scale, tile.y / scale)
}

fn terrain_base_tile_budget(required_tiles: usize) -> usize {
    required_tiles.max(80).min(256)
}

fn terrain_horizon_tile_budget(base_budget: usize, pitch: f64) -> usize {
    if pitch <= 0.5 {
        0
    } else {
        (base_budget / 3).max(24).min(96)
    }
}

/// Manages terrain elevation data and mesh generation.
pub struct TerrainManager {
    config: TerrainConfig,
    /// Cached elevation grids keyed by tile ID.
    ///
    /// Grids are stored in **expanded** form: `(W+2) x (H+2)` with a
    /// 1-sample border that is initially clamped to the nearest interior
    /// sample and incrementally patched from neighbour data as it becomes
    /// available (see [`BackfillState`]).
    cache: HashMap<TileId, ElevationGrid>,
    /// Tiles with pending fetch requests.
    pending: std::collections::HashSet<TileId>,
    /// Maximum cache entries.
    max_cache: usize,
    /// Monotonic access stamp used for cache eviction ordering.
    access_clock: u64,
    /// Last access stamp for each cached source tile.
    last_touched: HashMap<TileId, u64>,
    /// Last requested zoom level for elevation_at queries.
    last_desired_zoom: u8,
    /// Monotonic counter used to generate unique per-tile generations.
    next_generation: u64,
    /// Per-tile generation: tracks the generation of the elevation data
    /// that was used to build each tile's mesh.  Updated only when a
    /// specific tile's elevation data actually changes.
    tile_generations: HashMap<TileId, u64>,
    /// Per-tile backfill state tracking which neighbour borders have
    /// been patched.  Prevents redundant copies when nothing changes.
    backfill_states: HashMap<TileId, BackfillState>,
    /// Cached prepared hillshade rasters keyed by tile id and generation.
    hillshade_cache: HashMap<TileId, PreparedHillshadeRaster>,
    /// Prepared hillshade rasters for the most recent visible terrain set.
    last_hillshade_rasters: Vec<PreparedHillshadeRaster>,
    /// Cached mesh set for the most recent visible terrain frame.
    last_meshes: Vec<TerrainMeshData>,
    /// Cache key for the most recent visible terrain frame.
    last_frame_key: Option<TerrainFrameKey>,
}

#[derive(Debug, Clone, PartialEq)]
struct TerrainFrameKey {
    desired_tiles: Vec<TileId>,
    tile_generations: Vec<u64>,
    projection: CameraProjection,
    resolution: u16,
    vertical_exaggeration: f64,
    effective_skirt: f64,
}

impl TerrainFrameKey {
    fn new(
        desired_tiles: &[TileId],
        tile_generations: Vec<u64>,
        projection: CameraProjection,
        resolution: u16,
        vertical_exaggeration: f64,
        effective_skirt: f64,
    ) -> Self {
        Self {
            desired_tiles: desired_tiles.to_vec(),
            tile_generations,
            projection,
            resolution,
            vertical_exaggeration,
            effective_skirt,
        }
    }
}

impl TerrainManager {
    #[inline]
    fn touch_tile(&mut self, tile: TileId) {
        let stamp = self.access_clock;
        self.access_clock = self.access_clock.saturating_add(1);
        self.last_touched.insert(tile, stamp);
    }

    /// Create a new terrain manager.
    pub fn new(config: TerrainConfig, max_cache: usize) -> Self {
        Self {
            config,
            cache: HashMap::new(),
            pending: std::collections::HashSet::new(),
            max_cache,
            access_clock: 1,
            last_touched: HashMap::new(),
            last_desired_zoom: 0,
            next_generation: 1,
            tile_generations: HashMap::new(),
            backfill_states: HashMap::new(),
            hillshade_cache: HashMap::new(),
            last_hillshade_rasters: Vec::new(),
            last_meshes: Vec::new(),
            last_frame_key: None,
        }
    }

    /// Whether terrain is enabled.
    pub fn enabled(&self) -> bool {
        self.config.enabled
    }

    /// Set terrain enabled/disabled.
    pub fn set_enabled(&mut self, enabled: bool) {
        self.config.enabled = enabled;
        if !enabled {
            self.last_meshes.clear();
            self.last_hillshade_rasters.clear();
            self.last_frame_key = None;
        }
    }

    /// Get the vertical exaggeration.
    pub fn vertical_exaggeration(&self) -> f64 {
        self.config.vertical_exaggeration
    }

    /// Set vertical exaggeration.
    pub fn set_vertical_exaggeration(&mut self, exaggeration: f64) {
        self.config.vertical_exaggeration = exaggeration;
        self.last_frame_key = None;
    }

    /// Mesh resolution (vertices per tile edge) from the current configuration.
    #[inline]
    pub fn mesh_resolution(&self) -> u16 {
        self.config.mesh_resolution
    }

    /// Number of tile elevation requests currently pending (sent but
    /// not yet received).
    ///
    /// Used by the [`TileRequestCoordinator`](crate::TileRequestCoordinator)
    /// to estimate terrain demand for global budget allocation.
    #[inline]
    pub fn pending_count(&self) -> usize {
        self.pending.len()
    }

    /// Number of cached elevation tiles currently retained.
    #[inline]
    pub fn cache_entries(&self) -> usize {
        self.cache.len()
    }

    /// Most recent desired terrain zoom requested by the manager.
    #[inline]
    pub fn last_desired_zoom(&self) -> u8 {
        self.last_desired_zoom
    }

    /// Snapshot diagnostics for the current terrain state.
    pub fn diagnostics(&self) -> TerrainDiagnostics {
        let mut diagnostics = TerrainDiagnostics {
            enabled: self.config.enabled,
            cache_entries: self.cache.len(),
            pending_tiles: self.pending.len(),
            visible_mesh_tiles: self.last_meshes.len(),
            visible_hillshade_tiles: self.last_hillshade_rasters.len(),
            source_max_zoom: self.config.source_max_zoom,
            last_desired_zoom: self.last_desired_zoom,
            mesh_resolution: self.config.mesh_resolution,
            vertical_exaggeration: self.config.vertical_exaggeration,
            skirt_depth_m: skirt_height(self.last_desired_zoom, self.config.vertical_exaggeration),
            source_diagnostics: self.config.source.diagnostics(),
            ..TerrainDiagnostics::default()
        };

        let mut min_elev = f64::INFINITY;
        let mut max_elev = f64::NEG_INFINITY;

        for mesh in &self.last_meshes {
            let source_tile = clamp_tile_to_zoom(mesh.tile, self.config.source_max_zoom);
            if self.cache.contains_key(&source_tile) {
                diagnostics.visible_loaded_tiles += 1;
            } else if self.pending.contains(&source_tile) {
                diagnostics.visible_pending_tiles += 1;
            } else {
                diagnostics.visible_placeholder_tiles += 1;
            }

            if let Some(elevation) = mesh.elevation_texture.as_ref() {
                diagnostics.elevation_texture_tiles += 1;
                let lo = elevation.min_elev as f64 * self.config.vertical_exaggeration;
                let hi = elevation.max_elev as f64 * self.config.vertical_exaggeration;
                min_elev = min_elev.min(lo);
                max_elev = max_elev.max(hi);
            }

            if mesh.positions.is_empty() {
                // GPU-displacement path: report theoretical grid size.
                let res = mesh.grid_resolution as usize;
                let grid_verts = res * res;
                let skirt_verts = 4 * 2 * (res - 1);
                diagnostics.materialized_vertex_count += grid_verts + skirt_verts;
                let grid_idx = (res - 1) * (res - 1) * 6;
                let skirt_idx = 4 * (res - 1) * 6;
                diagnostics.materialized_index_count += grid_idx + skirt_idx;
            } else {
                diagnostics.materialized_vertex_count += mesh.positions.len();
                diagnostics.materialized_index_count += mesh.indices.len();
            }
        }

        if min_elev.is_finite() && max_elev.is_finite() {
            diagnostics.visible_min_elevation_m = Some(min_elev);
            diagnostics.visible_max_elevation_m = Some(max_elev);
        }

        diagnostics
    }

    /// Update terrain data for the current frame.
    ///
    /// Returns terrain meshes for all visible tiles that have elevation data.
    pub fn update(
        &mut self,
        viewport_bounds: &WorldBounds,
        zoom: u8,
        camera_world: (f64, f64),
        projection: CameraProjection,
        camera_distance: f64,
        camera_pitch: f64,
    ) -> Vec<TerrainMeshData> {
        let desired = if camera_pitch > 0.3 {
            let near_threshold = camera_distance * 1.5;
            let mid_threshold = camera_distance * 4.0;
            let max_tiles = 80;

            let mut tiles = visible_tiles_lod(
                viewport_bounds,
                zoom,
                camera_world,
                near_threshold,
                mid_threshold,
                max_tiles,
            );

            // Remove coarser tiles that overlap with finer tiles to
            // prevent z-fighting from duplicate terrain geometry at
            // different zoom levels.
            {
                let snapshot: Vec<TileId> = tiles.clone();
                tiles.retain(|t| {
                    !snapshot.iter().any(|other| {
                        if other.zoom <= t.zoom { return false; }
                        let dz = other.zoom - t.zoom;
                        (other.x >> dz) == t.x && (other.y >> dz) == t.y
                    })
                });
            }

            // Horizon fill: add coarser tiles to cover distant ground
            // beyond the base-zoom LOD set.  Only tiles that do NOT
            // overlap (are not an ancestor of) any existing tile are
            // added, preventing duplicate terrain geometry at different
            // zoom levels.
            if camera_pitch > 0.5 && zoom > 2 {
                use std::collections::HashSet;
                let seen: HashSet<TileId> = tiles.iter().copied().collect();
                let base_tiles: Vec<TileId> = tiles.clone();
                let is_ancestor_of_existing = |candidate: &TileId| -> bool {
                    base_tiles.iter().any(|t| {
                        if t.zoom <= candidate.zoom { return false; }
                        let dz = t.zoom - candidate.zoom;
                        (t.x >> dz) == candidate.x && (t.y >> dz) == candidate.y
                    })
                };
                let mut budget = terrain_horizon_tile_budget(max_tiles, camera_pitch);
                let mut hz = zoom.saturating_sub(2);
                while hz > 0 && budget > 0 {
                    let coarse = visible_tiles(viewport_bounds, hz);
                    let mut extras: Vec<_> = coarse
                        .into_iter()
                        .filter(|t| !seen.contains(t) && !is_ancestor_of_existing(t))
                        .map(|t| {
                            let b = rustial_math::tile_bounds_world(&t);
                            let cx = (b.min.position.x + b.max.position.x) * 0.5;
                            let cy = (b.min.position.y + b.max.position.y) * 0.5;
                            let dx = cx - camera_world.0;
                            let dy = cy - camera_world.1;
                            (t, dx * dx + dy * dy)
                        })
                        .collect();
                    extras.sort_by(|a, b| {
                        b.1.partial_cmp(&a.1).unwrap_or(std::cmp::Ordering::Equal)
                    });
                    let take = extras.len().min(budget);
                    tiles.extend(extras.into_iter().take(take).map(|(t, _)| t));
                    budget = budget.saturating_sub(take);
                    hz = hz.saturating_sub(2);
                }
            }

            tiles
        } else {
            visible_tiles(viewport_bounds, zoom)
        };

        self.update_with_tiles(&desired, zoom, projection)
    }

    /// Update terrain using an externally-provided tile set.
    ///
    /// This is used when the tile layer has already computed the desired
    /// visible tile set (e.g. via covering-tiles traversal) and the
    /// terrain manager should use the same tiles to ensure texture
    /// availability for every terrain mesh entity.
    pub fn update_with_tiles(
        &mut self,
        desired: &[TileId],
        zoom: u8,
        projection: CameraProjection,
    ) -> Vec<TerrainMeshData> {
        if !self.config.enabled {
            self.last_meshes.clear();
            self.last_hillshade_rasters.clear();
            self.last_frame_key = None;
            return Vec::new();
        }

        let source_max_zoom = self.config.source_max_zoom;

        // Poll completed elevation fetches.  New grids are immediately
        // expanded with a clamped 1-sample border before insertion into
        // the cache (see `expand_with_clamped_border`).
        let completed = self.config.source.poll();
        let mut changed_tiles = std::collections::HashSet::new();
        for (id, result) in completed {
            self.pending.remove(&id);
            if let Ok(grid) = result {
                // Expand to (W+2)x(H+2) with clamped border -- one
                // allocation per tile, at load time only.
                let expanded = expand_with_clamped_border(&grid);
                self.cache.insert(id, expanded);
                self.touch_tile(id);
                changed_tiles.insert(id);
            }
        }

        // Incrementally patch borders of changed tiles and their
        // neighbours.  Only the affected edge strips are overwritten
        // in-place -- no full-grid copies.
        if !changed_tiles.is_empty() {
            let backfill_modified = patch_changed_tiles(
                &mut self.cache,
                &mut self.backfill_states,
                &changed_tiles,
            );

            // Bump generation for tiles whose elevation data changed
            // (either from new source data or from border patching).
            let gen = self.next_generation;
            self.next_generation += 1;
            for tile_id in changed_tiles.iter().chain(backfill_modified.iter()) {
                self.tile_generations.insert(*tile_id, gen);
            }
        }

        self.last_desired_zoom = zoom;

        // Build the set of *source* tiles we actually need to fetch
        // (clamped to source_max_zoom) plus keep track of the desired
        // tiles for eviction decisions.
        let desired_set: std::collections::HashSet<TileId> =
            desired.iter().copied().collect();
        let source_tiles: std::collections::HashSet<TileId> = desired
            .iter()
            .map(|t| clamp_tile_to_zoom(*t, source_max_zoom))
            .collect();
        let hot_cached_tiles: Vec<_> = source_tiles
            .iter()
            .filter(|tile| self.cache.contains_key(tile))
            .copied()
            .collect();
        for tile in hot_cached_tiles {
            self.touch_tile(tile);
        }

        // Prune stale queued DEM requests that are no longer relevant to the
        // current desired source-tile set. In-flight requests remain tracked
        // until completion, but unsent queued requests should not accumulate
        // across aggressive fly-to transitions.
        let stale_pending: Vec<_> = self
            .pending
            .iter()
            .copied()
            .filter(|tile| !source_tiles.contains(tile))
            .collect();
        for tile in stale_pending {
            if self.config.source.cancel(tile) {
                self.pending.remove(&tile);
            }
        }

        // Retain both desired display tiles and their source ancestors.
        let mut retain_set = desired_set.clone();
        retain_set.extend(source_tiles.iter().copied());
        self.evict_outside(&retain_set);

        // Request elevation at the source zoom (clamped), not the
        // display zoom.  This ensures tiles beyond the source's max
        // zoom reuse parent elevation data instead of generating
        // failed/flat requests.
        for source_tile in &source_tiles {
            if !self.cache.contains_key(source_tile) && !self.pending.contains(source_tile) {
                self.config.source.request(*source_tile);
                self.pending.insert(*source_tile);
            }
        }

        let resolution = self.config.mesh_resolution;

        let effective_skirt = skirt_height(zoom, self.config.vertical_exaggeration);

        let tile_generations: Vec<u64> = desired
            .iter()
            .map(|tile| {
                let source_tile = clamp_tile_to_zoom(*tile, source_max_zoom);
                self.tile_generations.get(&source_tile).copied().unwrap_or(0)
            })
            .collect();
        let frame_key = TerrainFrameKey::new(
            desired,
            tile_generations,
            projection,
            resolution,
            self.config.vertical_exaggeration,
            effective_skirt,
        );

        if self.last_frame_key.as_ref() == Some(&frame_key) {
            return self.last_meshes.clone();
        }

        // The cache already holds border-expanded grids.  No per-frame
        // allocation is needed -- just read directly from the cache.
        let mut meshes = Vec::with_capacity(desired.len());
        let mut hillshade_rasters = Vec::with_capacity(desired.len());
        for tile in desired {
            let source_tile = clamp_tile_to_zoom(*tile, source_max_zoom);

            // Use the cached (border-expanded) grid by reference, or fall
            // back to a flat placeholder if not yet loaded.  Avoiding
            // `.cloned()` here eliminates a ~260 KB deep copy per tile.
            let fallback;
            let elevation = match self.cache.get(&source_tile) {
                Some(cached) => cached,
                None => {
                    fallback =
                        ElevationGrid::flat(*tile, resolution as u32, resolution as u32);
                    &fallback
                }
            };

            let tile_gen = self.tile_generations.get(&source_tile).copied().unwrap_or(0);
            let elevation_region = TileTextureRegion::from_tiles(tile, &source_tile);

            let mesh = build_terrain_descriptor_with_source(
                tile,
                source_tile,
                elevation_region,
                &elevation,
                resolution,
                self.config.vertical_exaggeration,
                tile_gen,
            );
            meshes.push(mesh);

            let raster = match self.hillshade_cache.get(tile) {
                Some(cached) if cached.generation == tile_gen => cached.clone(),
                _ => {
                    let prepared = prepare_hillshade_raster(
                        &elevation,
                        self.config.vertical_exaggeration,
                        tile_gen,
                    );
                    self.hillshade_cache.insert(*tile, prepared.clone());
                    prepared
                }
            };
            hillshade_rasters.push(raster);
        }

        self.last_hillshade_rasters = hillshade_rasters;
        self.last_meshes = meshes.clone();
        self.last_frame_key = Some(frame_key);

        meshes
    }

    /// Lightweight source-only update: poll elevation fetches, determine
    /// visible tiles, request missing elevation data, and return the desired
    /// tile set with their cached elevation grids.
    ///
    /// This does **not** build terrain meshes or hillshade rasters.  It is
    /// the first half of the split pipeline used by the async data path,
    /// where mesh building is dispatched to background tasks.
    pub fn update_sources(
        &mut self,
        viewport_bounds: &WorldBounds,
        zoom: u8,
        camera_world: (f64, f64),
        camera_distance: f64,
        camera_pitch: f64,
    ) -> Vec<(TileId, ElevationGrid, u64)> {
        if !self.config.enabled {
            return Vec::new();
        }

        // Poll completed elevation fetches -- expand on insertion.
        let completed = self.config.source.poll();
        let mut changed_tiles = std::collections::HashSet::new();
        for (id, result) in completed {
            self.pending.remove(&id);
            if let Ok(grid) = result {
                let expanded = expand_with_clamped_border(&grid);
                self.cache.insert(id, expanded);
                self.touch_tile(id);
                changed_tiles.insert(id);
            }
        }
        if !changed_tiles.is_empty() {
            let backfill_modified = patch_changed_tiles(
                &mut self.cache,
                &mut self.backfill_states,
                &changed_tiles,
            );
            let gen = self.next_generation;
            self.next_generation += 1;
            for tile_id in changed_tiles.iter().chain(backfill_modified.iter()) {
                self.tile_generations.insert(*tile_id, gen);
            }
        }

        let desired = if camera_pitch > 0.3 {
            let near_threshold = camera_distance * 1.5;
            let mid_threshold = camera_distance * 4.0;
            let strict_tiles = visible_tiles(viewport_bounds, zoom);
            let max_tiles = terrain_base_tile_budget(strict_tiles.len());
            visible_tiles_lod(
                viewport_bounds,
                zoom,
                camera_world,
                near_threshold,
                mid_threshold,
                max_tiles,
            )
        } else {
            visible_tiles(viewport_bounds, zoom)
        };

        let source_max_zoom = self.config.source_max_zoom;
        self.last_desired_zoom = zoom;

        let desired_set: std::collections::HashSet<TileId> =
            desired.iter().copied().collect();
        let source_tiles: std::collections::HashSet<TileId> = desired
            .iter()
            .map(|t| clamp_tile_to_zoom(*t, source_max_zoom))
            .collect();
        let hot_cached_tiles: Vec<_> = source_tiles
            .iter()
            .filter(|tile| self.cache.contains_key(tile))
            .copied()
            .collect();
        for tile in hot_cached_tiles {
            self.touch_tile(tile);
        }

        let stale_pending: Vec<_> = self
            .pending
            .iter()
            .copied()
            .filter(|tile| !source_tiles.contains(tile))
            .collect();
        for tile in stale_pending {
            if self.config.source.cancel(tile) {
                self.pending.remove(&tile);
            }
        }

        let mut retain_set = desired_set.clone();
        retain_set.extend(source_tiles.iter().copied());
        self.evict_outside(&retain_set);

        for source_tile in &source_tiles {
            if !self.cache.contains_key(source_tile) && !self.pending.contains(source_tile) {
                self.config.source.request(*source_tile);
                self.pending.insert(*source_tile);
            }
        }

        let resolution = self.config.mesh_resolution;

        // Cache already holds border-expanded grids -- read directly.
        let mut result = Vec::with_capacity(desired.len());
        for tile in &desired {
            let source_tile = clamp_tile_to_zoom(*tile, source_max_zoom);
            let elevation = self
                .cache
                .get(&source_tile)
                .cloned()
                .unwrap_or_else(|| ElevationGrid::flat(*tile, resolution as u32, resolution as u32));
            let tile_gen = self.tile_generations.get(&source_tile).copied().unwrap_or(0);
            result.push((*tile, elevation, tile_gen));
        }
        result
    }

    /// Lightweight source-only update using an externally-provided tile set.
    ///
    /// This mirrors [`update_with_tiles`](Self::update_with_tiles) for the
    /// async terrain path: poll elevation fetches, request missing source tiles,
    /// and return the desired tile set paired with cached (or flat fallback)
    /// elevation grids and per-tile generations.
    pub fn update_sources_with_tiles(
        &mut self,
        desired: &[TileId],
        zoom: u8,
    ) -> Vec<(TileId, ElevationGrid, u64)> {
        if !self.config.enabled {
            return Vec::new();
        }

        let completed = self.config.source.poll();
        let mut changed_tiles = std::collections::HashSet::new();
        for (id, result) in completed {
            self.pending.remove(&id);
            if let Ok(grid) = result {
                let expanded = expand_with_clamped_border(&grid);
                self.cache.insert(id, expanded);
                self.touch_tile(id);
                changed_tiles.insert(id);
            }
        }
        if !changed_tiles.is_empty() {
            let backfill_modified = patch_changed_tiles(
                &mut self.cache,
                &mut self.backfill_states,
                &changed_tiles,
            );
            let generation = self.next_generation;
            self.next_generation += 1;
            for tile_id in changed_tiles.iter().chain(backfill_modified.iter()) {
                self.tile_generations.insert(*tile_id, generation);
            }
        }

        self.last_desired_zoom = zoom;

        let source_max_zoom = self.config.source_max_zoom;
        let desired_set: std::collections::HashSet<TileId> = desired.iter().copied().collect();
        let source_tiles: std::collections::HashSet<TileId> = desired
            .iter()
            .map(|tile| clamp_tile_to_zoom(*tile, source_max_zoom))
            .collect();
        let hot_cached_tiles: Vec<_> = source_tiles
            .iter()
            .filter(|tile| self.cache.contains_key(tile))
            .copied()
            .collect();
        for tile in hot_cached_tiles {
            self.touch_tile(tile);
        }

        let stale_pending: Vec<_> = self
            .pending
            .iter()
            .copied()
            .filter(|tile| !source_tiles.contains(tile))
            .collect();
        for tile in stale_pending {
            if self.config.source.cancel(tile) {
                self.pending.remove(&tile);
            }
        }

        let mut retain_set = desired_set.clone();
        retain_set.extend(source_tiles.iter().copied());
        self.evict_outside(&retain_set);

        for source_tile in &source_tiles {
            if !self.cache.contains_key(source_tile) && !self.pending.contains(source_tile) {
                self.config.source.request(*source_tile);
                self.pending.insert(*source_tile);
            }
        }

        let resolution = self.config.mesh_resolution;

        // Cache already holds border-expanded grids -- read directly.
        let mut result = Vec::with_capacity(desired.len());
        for tile in desired {
            let source_tile = clamp_tile_to_zoom(*tile, source_max_zoom);
            let elevation = self
                .cache
                .get(&source_tile)
                .cloned()
                .unwrap_or_else(|| ElevationGrid::flat(*tile, resolution as u32, resolution as u32));
            let tile_gen = self.tile_generations.get(&source_tile).copied().unwrap_or(0);
            result.push((*tile, elevation, tile_gen));
        }

        result
    }

    /// Query elevation at a geographic coordinate.
    ///
    /// Uses a targeted tile lookup: computes which tile contains the
    /// coordinate at the most recent zoom level, then falls back to
    /// parent zoom levels if the exact tile is not cached.  This is
    /// O(zoom) instead of O(cache_size).
    ///
    /// Returns `None` if terrain is disabled or no cached tile covers
    /// the coordinate.
    pub fn elevation_at(&self, coord: &GeoCoord) -> Option<f64> {
        if !self.config.enabled {
            return None;
        }

        let max_z = self.last_desired_zoom.min(self.config.source_max_zoom);
        let mut z = max_z;
        loop {
            let tile = rustial_math::geo_to_tile(coord, z).tile_id();
            if let Some(grid) = self.cache.get(&tile) {
                if let Some(elev) = grid.sample_geo(coord) {
                    return Some(elev as f64 * self.config.vertical_exaggeration);
                }
            }
            if z == 0 {
                break;
            }
            z -= 1;
        }

        None
    }

    /// Access the configuration.
    pub fn config(&self) -> &TerrainConfig {
        &self.config
    }

    /// Access the configuration mutably.
    pub fn config_mut(&mut self) -> &mut TerrainConfig {
        self.last_frame_key = None;
        &mut self.config
    }

    /// Prepared hillshade rasters for the most recently visible terrain set.
    pub fn visible_hillshade_rasters(&self) -> &[PreparedHillshadeRaster] {
        &self.last_hillshade_rasters
    }

    /// The source max zoom for elevation data.
    #[inline]
    pub fn source_max_zoom(&self) -> u8 {
        self.config.source_max_zoom
    }

    /// Return the DEM source tile used to back a visible terrain tile.
    #[inline]
    pub fn elevation_source_tile_for(&self, tile: TileId) -> TileId {
        clamp_tile_to_zoom(tile, self.config.source_max_zoom)
    }

    /// Return the DEM sub-region sampled by a visible terrain tile.
    #[inline]
    pub fn elevation_region_for(&self, tile: TileId) -> TileTextureRegion {
        let source_tile = self.elevation_source_tile_for(tile);
        TileTextureRegion::from_tiles(&tile, &source_tile)
    }

    fn evict_outside(&mut self, desired: &std::collections::HashSet<TileId>) {
        while self.cache.len() > self.max_cache {
            let stale = self
                .cache
                .keys()
                .filter(|id| !desired.contains(id) && id.zoom != self.last_desired_zoom)
                .min_by_key(|id| self.last_touched.get(id).copied().unwrap_or(0))
                .copied();
            if let Some(key) = stale {
                self.cache.remove(&key);
                self.last_touched.remove(&key);
                self.tile_generations.remove(&key);
                self.hillshade_cache.remove(&key);
                self.backfill_states.remove(&key);
                self.last_frame_key = None;
                continue;
            }
            let expendable = self
                .cache
                .keys()
                .filter(|id| !desired.contains(id))
                .min_by_key(|id| self.last_touched.get(id).copied().unwrap_or(0))
                .copied();
            if let Some(key) = expendable {
                self.cache.remove(&key);
                self.last_touched.remove(&key);
                self.tile_generations.remove(&key);
                self.hillshade_cache.remove(&key);
                self.backfill_states.remove(&key);
                self.last_frame_key = None;
                continue;
            }
            break;
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::camera_projection::CameraProjection;
    use crate::terrain::elevation_source::FlatElevationSource;
    use rustial_math::{WebMercator, WorldCoord};

    fn full_world_bounds() -> WorldBounds {
        let extent = WebMercator::max_extent();
        WorldBounds::new(
            WorldCoord::new(-extent, -extent, 0.0),
            WorldCoord::new(extent, extent, 0.0),
        )
    }

    #[test]
    fn disabled_returns_empty() {
        let config = TerrainConfig::default();
        let mut mgr = TerrainManager::new(config, 100);
        let meshes = mgr.update(&full_world_bounds(), 0, (0.0, 0.0), CameraProjection::WebMercator, 10_000_000.0, 0.0);
        assert!(meshes.is_empty());
    }

    #[test]
    fn enabled_with_flat_source() {
        let config = TerrainConfig {
            enabled: true,
            mesh_resolution: 4,
            source: Box::new(FlatElevationSource::new(4, 4)),
            ..TerrainConfig::default()
        };
        let mut mgr = TerrainManager::new(config, 100);

        let meshes = mgr.update(&full_world_bounds(), 0, (0.0, 0.0), CameraProjection::WebMercator, 10_000_000.0, 0.0);
        assert_eq!(meshes.len(), 1);
        assert_eq!(meshes[0].tile, TileId::new(0, 0, 0));

        let meshes = mgr.update(&full_world_bounds(), 0, (0.0, 0.0), CameraProjection::WebMercator, 10_000_000.0, 0.0);
        assert_eq!(meshes.len(), 1);
        assert_eq!(meshes[0].tile, TileId::new(0, 0, 0));
    }

    #[test]
    fn steady_state_reuses_cached_meshes() {
        let config = TerrainConfig {
            enabled: true,
            mesh_resolution: 8,
            source: Box::new(FlatElevationSource::new(8, 8)),
            ..TerrainConfig::default()
        };
        let mut mgr = TerrainManager::new(config, 100);

        mgr.update(&full_world_bounds(), 0, (0.0, 0.0), CameraProjection::WebMercator, 10_000_000.0, 0.0);
        let first = mgr.update(&full_world_bounds(), 0, (0.0, 0.0), CameraProjection::WebMercator, 10_000_000.0, 0.0);
        let second = mgr.update(&full_world_bounds(), 0, (0.0, 0.0), CameraProjection::WebMercator, 10_000_000.0, 0.0);

        assert_eq!(first.len(), second.len());
        assert_eq!(first[0].tile, second[0].tile);
        assert_eq!(first[0].grid_resolution, second[0].grid_resolution);
        assert_eq!(
            first[0].elevation_texture.as_ref().map(|t| (t.width, t.height)),
            second[0].elevation_texture.as_ref().map(|t| (t.width, t.height)),
        );
        assert!(first[0].positions.is_empty());
        assert!(second[0].positions.is_empty());
    }

    #[test]
    fn changing_projection_invalidates_cached_meshes() {
        let config = TerrainConfig {
            enabled: true,
            mesh_resolution: 8,
            source: Box::new(FlatElevationSource::new(8, 8)),
            ..TerrainConfig::default()
        };
        let mut mgr = TerrainManager::new(config, 100);

        mgr.update(&full_world_bounds(), 0, (0.0, 0.0), CameraProjection::WebMercator, 10_000_000.0, 0.0);
        let merc = mgr.update(&full_world_bounds(), 0, (0.0, 0.0), CameraProjection::WebMercator, 10_000_000.0, 0.0);
        let eq = mgr.update(&full_world_bounds(), 0, (0.0, 0.0), CameraProjection::Equirectangular, 10_000_000.0, 0.0);

        assert_eq!(merc.len(), eq.len());
        assert_eq!(merc[0].tile, eq[0].tile);
        assert_eq!(merc[0].grid_resolution, eq[0].grid_resolution);
        assert!(merc[0].positions.is_empty());
        assert!(eq[0].positions.is_empty());
    }

    #[test]
    fn elevation_at_flat() {
        let config = TerrainConfig {
            enabled: true,
            mesh_resolution: 4,
            source: Box::new(FlatElevationSource::new(4, 4)),
            ..TerrainConfig::default()
        };
        let mut mgr = TerrainManager::new(config, 100);
        mgr.update(&full_world_bounds(), 0, (0.0, 0.0), CameraProjection::WebMercator, 10_000_000.0, 0.0);
        mgr.update(&full_world_bounds(), 0, (0.0, 0.0), CameraProjection::WebMercator, 10_000_000.0, 0.0);

        let elev = mgr.elevation_at(&GeoCoord::from_lat_lon(0.0, 0.0));
        assert_eq!(elev, Some(0.0));
    }

    #[test]
    fn prepared_hillshade_is_emitted_for_visible_tiles() {
        let config = TerrainConfig {
            enabled: true,
            mesh_resolution: 4,
            source: Box::new(FlatElevationSource::new(4, 4)),
            ..TerrainConfig::default()
        };
        let mut mgr = TerrainManager::new(config, 100);
        mgr.update(&full_world_bounds(), 0, (0.0, 0.0), CameraProjection::WebMercator, 10_000_000.0, 0.0);
        mgr.update(&full_world_bounds(), 0, (0.0, 0.0), CameraProjection::WebMercator, 10_000_000.0, 0.0);

        let rasters = mgr.visible_hillshade_rasters();
        assert_eq!(rasters.len(), 1);
        assert_eq!(rasters[0].tile, TileId::new(0, 0, 0));
        // After DEM backfilling the elevation grid is expanded by a
        // 1-sample border on each edge, so the hillshade raster
        // dimensions are (original + 2) x (original + 2).
        assert_eq!(rasters[0].image.width, 6);
        assert_eq!(rasters[0].image.height, 6);
    }

    #[test]
    fn diagnostics_report_visible_and_cache_state() {
        let config = TerrainConfig {
            enabled: true,
            mesh_resolution: 4,
            vertical_exaggeration: 1.5,
            skirt_depth: 120.0,
            source: Box::new(FlatElevationSource::new(4, 4)),
            ..TerrainConfig::default()
        };
        let mut mgr = TerrainManager::new(config, 100);

        // First frame requests data and emits placeholder terrain.
        mgr.update(
            &full_world_bounds(),
            0,
            (0.0, 0.0),
            CameraProjection::WebMercator,
            10_000_000.0,
            0.0,
        );
        let first = mgr.diagnostics();
        assert!(first.enabled);
        assert_eq!(first.visible_mesh_tiles, 1);
        assert_eq!(first.visible_pending_tiles, 1);
        assert_eq!(first.visible_loaded_tiles, 0);
        assert_eq!(first.cache_entries, 0);
        assert_eq!(first.pending_tiles, 1);
        assert_eq!(first.visible_hillshade_tiles, 1);
        assert_eq!(first.elevation_texture_tiles, 1);
        assert_eq!(first.mesh_resolution, 4);
        assert_eq!(first.vertical_exaggeration, 1.5);
        assert_eq!(first.skirt_depth_m, skirt_height(0, 1.5));

        // Second frame receives the flat DEM and reports it as loaded.
        mgr.update(
            &full_world_bounds(),
            0,
            (0.0, 0.0),
            CameraProjection::WebMercator,
            10_000_000.0,
            0.0,
        );
        let second = mgr.diagnostics();
        assert_eq!(second.visible_mesh_tiles, 1);
        assert_eq!(second.visible_loaded_tiles, 1);
        assert_eq!(second.visible_pending_tiles, 0);
        assert_eq!(second.visible_placeholder_tiles, 0);
        assert_eq!(second.cache_entries, 1);
        assert_eq!(second.pending_tiles, 0);
        assert_eq!(second.visible_hillshade_tiles, 1);
        assert_eq!(second.visible_min_elevation_m, Some(0.0));
        assert_eq!(second.visible_max_elevation_m, Some(0.0));
        assert_eq!(second.last_desired_zoom, 0);
        assert_eq!(second.source_max_zoom, 15);
    }

    #[test]
    fn overzoomed_child_mesh_uses_parent_dem_subregion() {
        let config = TerrainConfig {
            enabled: true,
            mesh_resolution: 4,
            source_max_zoom: 15,
            source: Box::new(FlatElevationSource::new(4, 4)),
            ..TerrainConfig::default()
        };
        let mut mgr = TerrainManager::new(config, 100);
        let child = TileId::new(16, 1000, 2000);

        // First frame requests the clamped parent DEM tile.
        let _ = mgr.update_with_tiles(&[child], 16, CameraProjection::WebMercator);
        // Second frame receives it and builds the visible mesh.
        let meshes = mgr.update_with_tiles(&[child], 16, CameraProjection::WebMercator);

        assert_eq!(meshes.len(), 1);
        let mesh = &meshes[0];
        assert_eq!(mesh.tile, child);
        assert_eq!(mesh.elevation_source_tile, TileId::new(15, 500, 1000));
        assert_eq!(mesh.elevation_region.u_min, 0.0);
        assert_eq!(mesh.elevation_region.v_min, 0.0);
        assert_eq!(mesh.elevation_region.u_max, 0.5);
        assert_eq!(mesh.elevation_region.v_max, 0.5);
    }

    #[test]
    fn evict_outside_prefers_least_recently_used_non_retained_tile() {
        let config = TerrainConfig {
            enabled: true,
            source: Box::new(FlatElevationSource::new(4, 4)),
            ..TerrainConfig::default()
        };
        let mut mgr = TerrainManager::new(config, 2);
        let a = TileId::new(3, 0, 0);
        let b = TileId::new(3, 1, 0);
        let c = TileId::new(3, 2, 0);

        mgr.cache.insert(a, ElevationGrid::flat(a, 4, 4));
        mgr.touch_tile(a);
        mgr.cache.insert(b, ElevationGrid::flat(b, 4, 4));
        mgr.touch_tile(b);
        mgr.cache.insert(c, ElevationGrid::flat(c, 4, 4));
        mgr.touch_tile(c);

        let retain = std::collections::HashSet::from([c]);
        mgr.evict_outside(&retain);

        assert!(!mgr.cache.contains_key(&a));
        assert!(mgr.cache.contains_key(&b));
        assert!(mgr.cache.contains_key(&c));
        assert!(!mgr.last_touched.contains_key(&a));
    }
}