fix(render): select terrain LOD from native camera cells

3 files changed, 384 insertions, 0 deletions

diff --git a/crates/fparkan-terrain-format/src/lib.rs b/crates/fparkan-terrain-format/src/lib.rs
index 595f4d8..63d21a1 100644
--- a/crates/fparkan-terrain-format/src/lib.rs
+++ b/crates/fparkan-terrain-format/src/lib.rs
@@ -226,6 +226,8 @@ pub enum TerrainLodError {
     DuplicateFaceAssignment { face: usize },
     /// A source face is absent from every supported terrain slot.
     MissingFaceAssignment { face: usize },
+    /// Slot bounds do not form the regular XY cell grid used by terrain rendering.
+    InvalidCellGrid,
     /// A checked index calculation overflowed.
     IntegerOverflow,
 }
@@ -276,6 +278,7 @@ impl std::fmt::Display for TerrainLodError {
             Self::MissingFaceAssignment { face } => {
                 write!(f, "terrain face {face} is not assigned to a supported slot")
             }
+            Self::InvalidCellGrid => write!(f, "terrain slots do not form a regular XY cell grid"),
             Self::IntegerOverflow => write!(f, "terrain slot index overflow"),
         }
     }
diff --git a/crates/fparkan-terrain/src/lib.rs b/crates/fparkan-terrain/src/lib.rs
index 5e17a23..64e6814 100644
--- a/crates/fparkan-terrain/src/lib.rs
+++ b/crates/fparkan-terrain/src/lib.rs
@@ -6,6 +6,9 @@ use std::collections::VecDeque;
 
 mod contour;
 mod foundation;
+mod lod;
+
+pub use lod::TerrainLodPlan;
 
 use foundation::basement_surface_mask;
 pub use foundation::{
@@ -1633,6 +1636,83 @@ mod tests {
     }
 
     #[test]
+    fn lod_grid_uses_authored_face_ownership_and_pins_changed_foundation_cells() {
+        use fparkan_terrain_format::{TerrainStream, TerrainStreamAttributes};
+        let mut mesh = synthetic_land_mesh();
+        mesh.faces.extend(mesh.faces.clone());
+        assign_terrain_lod_slots(&mut mesh, &[[0, 1]], &[[0, 2], [2, 2]]);
+        mesh.slots.header_raw = vec![0; 0x8c];
+        mesh.streams.push(TerrainStream {
+            type_id: 1,
+            attributes: TerrainStreamAttributes {
+                attr1: 1,
+                attr2: 1,
+                attr3: 0,
+            },
+            size: 38,
+        });
+        for slot in &mut mesh.slots.slots_raw {
+            slot[20..24].copy_from_slice(&1.0_f32.to_le_bytes());
+            slot[24..28].copy_from_slice(&1.0_f32.to_le_bytes());
+        }
+        let mut foundation = BasementFoundation {
+            placements: Vec::new(),
+            fragments: (0..2)
+                .map(|face| BasementFoundationFragment {
+                    source_face: Some(face),
+                    surface_mask: mesh.faces[face].flags,
+                    positions: mesh.faces[face]
+                        .vertices
+                        .map(|v| mesh.positions[usize::from(v)]),
+                })
+                .collect(),
+        };
+        foundation.fragments[0].positions.rotate_left(1);
+        let plan = TerrainLodPlan::new(&mesh, Some(&foundation)).unwrap();
+        assert_eq!(plan.source_face_node(3), Some(0));
+        assert_eq!(plan.source_face_node(4), None);
+        assert_eq!(
+            plan.selected_lod(0, [4.0, 4.0], 1.3),
+            Some(TerrainLod::Lod1)
+        );
+        foundation.fragments.pop();
+        let patched = TerrainLodPlan::new(&mesh, Some(&foundation)).unwrap();
+        assert_eq!(
+            patched.selected_lod(0, [4.0, 4.0], 1.3),
+            Some(TerrainLod::Lod0)
+        );
+        mesh.slots.slots_raw[0][24..28].copy_from_slice(&f32::NAN.to_le_bytes());
+        assert!(matches!(
+            TerrainLodPlan::new(&mesh, None),
+            Err(TerrainLodError::InvalidCellGrid)
+        ));
+    }
+
+    #[test]
+    #[ignore = "requires licensed corpus"]
+    fn licensed_corpus_land_meshes_build_native_lod_grids() {
+        let mut files = 0;
+        for path in files_under(&corpus_root("IS")) {
+            if !path
+                .file_name()
+                .and_then(|s| s.to_str())
+                .is_some_and(|s| s.eq_ignore_ascii_case("Land.msh"))
+            {
+                continue;
+            }
+            let bytes = std::fs::read(&path).unwrap();
+            let nres =
+                fparkan_nres::decode(Arc::from(bytes.into_boxed_slice()), ReadProfile::Compatible)
+                    .unwrap();
+            let mesh = fparkan_terrain_format::decode_land_msh(&nres).unwrap();
+            let plan = TerrainLodPlan::new(&mesh, None).unwrap_or_else(|e| panic!("{path:?}: {e}"));
+            assert!(plan.has_far_geometry(), "{path:?}: no far slots");
+            files += 1;
+        }
+        assert_eq!(files, 33, "original game LOD grid count");
+    }
+
+    #[test]
     #[ignore = "requires licensed corpus"]
     fn licensed_corpus_land_meshes_build_surface_worlds() {
         for (corpus, expected_files, expected_faces) in [
diff --git a/crates/fparkan-terrain/src/lod.rs b/crates/fparkan-terrain/src/lod.rs
new file mode 100644
index 0000000..cf5991f
--- /dev/null
+++ b/crates/fparkan-terrain/src/lod.rs
@@ -0,0 +1,301 @@
+use crate::{BasementFoundation, TerrainLod, TerrainLodError};
+use fparkan_terrain_format::LandMeshDocument;
+
+/// Camera-dependent terrain detail selection, retaining LOD0 in basement cells.
+#[derive(Clone, Debug)]
+pub struct TerrainLodPlan {
+    origin: [f32; 2],
+    inverse_cell_size: [f32; 2],
+    counts: [usize; 2],
+    forced_lod0: Vec<bool>,
+    has_lod1: Vec<bool>,
+    face_nodes: Vec<usize>,
+}
+
+impl TerrainLodPlan {
+    /// Validates the authored grid and registers foundation patches in its cells.
+    ///
+    /// # Errors
+    /// Returns an error for an invalid slot mapping, grid or foundation source face.
+    pub fn new(
+        mesh: &LandMeshDocument,
+        foundation: Option<&BasementFoundation>,
+    ) -> Result<Self, TerrainLodError> {
+        let assignments = mesh.face_lod_assignments()?;
+        let bounds = mesh
+            .nodes_raw
+            .chunks_exact(38)
+            .map(|node| {
+                let slot = u16::from_le_bytes([node[8], node[9]]);
+                let raw = mesh.slots.slots_raw.get(usize::from(slot))?;
+                let coordinate =
+                    |offset: usize| f32::from_le_bytes(raw[offset..offset + 4].try_into().unwrap());
+                Some((
+                    [coordinate(8), coordinate(12)],
+                    [coordinate(20), coordinate(24)],
+                ))
+            })
+            .collect::<Option<Vec<_>>>()
+            .ok_or(TerrainLodError::InvalidCellGrid)?;
+        let &(first_min, first_max) = bounds.first().ok_or(TerrainLodError::InvalidCellGrid)?;
+        let header = &mesh.slots.header_raw;
+        let coordinate = |offset: usize| {
+            header
+                .get(offset..offset + 4)
+                .map(|bytes| f32::from_le_bytes(bytes.try_into().unwrap()))
+        };
+        let origin = [
+            coordinate(0).ok_or(TerrainLodError::InvalidCellGrid)?,
+            coordinate(4).ok_or(TerrainLodError::InvalidCellGrid)?,
+        ];
+        let size = [first_max[0] - first_min[0], first_max[1] - first_min[1]];
+        if !origin.iter().all(|value| value.is_finite())
+            || !size.iter().all(|value| value.is_finite() && *value > 0.0)
+        {
+            return Err(TerrainLodError::InvalidCellGrid);
+        }
+        let count_x = mesh
+            .streams
+            .iter()
+            .find(|s| s.type_id == 1)
+            .map(|s| s.attributes.attr2 as usize)
+            .ok_or(TerrainLodError::InvalidCellGrid)?;
+        if count_x == 0 || !bounds.len().is_multiple_of(count_x) {
+            return Err(TerrainLodError::InvalidCellGrid);
+        }
+        let count_y = bounds.len() / count_x;
+        let counts = [count_x, count_y];
+        for (node, &(min, max)) in bounds.iter().enumerate() {
+            let cell = [node / count_y, node % count_y];
+            for axis in 0..2 {
+                let expected = origin[axis] + cell[axis] as f32 * size[axis];
+                let tolerance = size[axis] * 1.0e-5;
+                if !min[axis].is_finite()
+                    || !max[axis].is_finite()
+                    || (min[axis] - expected).abs() > tolerance
+                    || (max[axis] - (expected + size[axis])).abs() > tolerance
+                {
+                    return Err(TerrainLodError::InvalidCellGrid);
+                }
+            }
+        }
+        let has_lod1 = mesh
+            .nodes_raw
+            .chunks_exact(38)
+            .map(|node| {
+                let slot = u16::from_le_bytes([node[10], node[11]]);
+                slot != 0xff
+                    && slot != u16::MAX
+                    && mesh
+                        .slots
+                        .slots_raw
+                        .get(usize::from(slot))
+                        .is_some_and(|raw| u16::from_le_bytes([raw[2], raw[3]]) != 0)
+            })
+            .collect();
+        let mut result = Self {
+            origin,
+            inverse_cell_size: size.map(f32::recip),
+            counts,
+            forced_lod0: vec![false; bounds.len()],
+            has_lod1,
+            face_nodes: assignments.iter().map(|a| a.node_index).collect(),
+        };
+        if let Some(foundation) = foundation {
+            let mut fragments = vec![0usize; mesh.faces.len()];
+            let mut unchanged = vec![false; mesh.faces.len()];
+            for fragment in &foundation.fragments {
+                if let Some(face_index) = fragment.source_face {
+                    let face = mesh
+                        .faces
+                        .get(face_index)
+                        .ok_or(TerrainLodError::MissingFaceAssignment { face: face_index })?;
+                    fragments[face_index] += 1;
+                    let original = face.vertices.map(|v| mesh.positions[usize::from(v)]);
+                    unchanged[face_index] = fragment.positions.iter().all(|p| original.contains(p));
+                }
+            }
+            for assignment in assignments.iter().filter(|a| a.lod == TerrainLod::Lod0) {
+                if fragments[assignment.face_index] != 1 || !unchanged[assignment.face_index] {
+                    result.forced_lod0[assignment.node_index] = true;
+                }
+            }
+            // Native registers patch triangles against every cell, including shared edges.
+            for fragment in foundation.fragments.iter().filter(|fragment| {
+                fragment
+                    .source_face
+                    .is_none_or(|face| fragments[face] != 1 || !unchanged[face])
+            }) {
+                for node in 0..bounds.len() {
+                    let cell = [node / count_y, node % count_y];
+                    let center = std::array::from_fn(|axis| {
+                        (cell[axis] as f32 + 0.5) * size[axis] + origin[axis]
+                    });
+                    if triangle_intersects_cell(
+                        fragment.positions,
+                        center,
+                        result.inverse_cell_size,
+                    ) {
+                        result.forced_lod0[node] = true;
+                    }
+                }
+            }
+        }
+        Ok(result)
+    }
+
+    /// Returns the cell named by the authored slot that owns a source face.
+    #[must_use]
+    pub fn source_face_node(&self, face: usize) -> Option<usize> {
+        self.face_nodes.get(face).copied()
+    }
+
+    fn camera_cell(&self, point: [f32; 2]) -> Option<[i32; 2]> {
+        let cell: [f32; 2] = std::array::from_fn(|axis| {
+            ((point[axis] - self.origin[axis]) * self.inverse_cell_size[axis]).floor()
+        });
+        cell.iter()
+            .all(|v| v.is_finite() && *v >= i32::MIN as f32 && *v < i32::MAX as f32)
+            .then(|| cell.map(|v| v as i32))
+    }
+
+    /// Selects LOD1 at a squared cell distance of at least nine, unless forced near.
+    /// Returns `None` for an invalid node, camera position or FOV.
+    #[must_use]
+    pub fn selected_lod(
+        &self,
+        node: usize,
+        eye: [f32; 2],
+        horizontal_fov: f32,
+    ) -> Option<TerrainLod> {
+        let forced = *self.forced_lod0.get(node)?;
+        let has_far = *self.has_lod1.get(node)?;
+        let camera = self.camera_cell(eye)?;
+        if !horizontal_fov.is_finite() || horizontal_fov <= 0.0 {
+            return None;
+        }
+        let dx = (node / self.counts[1]) as f64 - f64::from(camera[0]);
+        let dy = (node % self.counts[1]) as f64 - f64::from(camera[1]);
+        Some(
+            if !forced && has_far && horizontal_fov >= 0.5 && dx * dx + dy * dy >= 9.0 {
+                TerrainLod::Lod1
+            } else {
+                TerrainLod::Lod0
+            },
+        )
+    }
+
+    /// Whether the map contains any usable far slots.
+    #[must_use]
+    pub fn has_far_geometry(&self) -> bool {
+        self.has_lod1.iter().any(|&value| value)
+    }
+}
+
+fn triangle_intersects_cell(
+    triangle: [[f32; 3]; 3],
+    center: [f32; 2],
+    inverse_size: [f32; 2],
+) -> bool {
+    // Normalize in f32 before testing the native [-0.5, 0.5] box.
+    let points = triangle.map(|p| {
+        std::array::from_fn::<_, 2, _>(|axis| {
+            f64::from((p[axis] - center[axis]) * inverse_size[axis])
+        })
+    });
+    let edges = std::array::from_fn::<_, 3, _>(|i| {
+        let next = points[(i + 1) % 3];
+        [next[1] - points[i][1], points[i][0] - next[0]]
+    });
+    [[1.0, 0.0], [0.0, 1.0]]
+        .into_iter()
+        .chain(edges)
+        .all(|axis| {
+            let projections = points.map(|p| p[0] * axis[0] + p[1] * axis[1]);
+            let radius = 0.5 * (axis[0].abs() + axis[1].abs());
+            projections.iter().copied().fold(f64::INFINITY, f64::min) <= radius
+                && projections
+                    .iter()
+                    .copied()
+                    .fold(f64::NEG_INFINITY, f64::max)
+                    >= -radius
+        })
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn patch_registration_keeps_native_normalization_and_triangle_edges() {
+        let size = f32::from_bits(0x42d4_15f5);
+        let center = [2.5 * size, 6.5 * size];
+        let edge = [
+            [3.0 * size, 6.0 * size, 0.0],
+            [3.0 * size, 7.0 * size, 0.0],
+            [4.0 * size, 6.0 * size, 0.0],
+        ];
+        // The authored boundary rounds outside this cell after native normalization.
+        assert!(!triangle_intersects_cell(edge, center, [size.recip(); 2]));
+        assert!(triangle_intersects_cell(
+            edge,
+            [3.5 * size, 6.5 * size],
+            [size.recip(); 2]
+        ));
+        assert!(!triangle_intersects_cell(
+            [[0.0, 0.0, 0.0], [2.0, 0.0, 0.0], [0.0, 2.0, 0.0]],
+            [1.75, 1.75],
+            [2.0; 2]
+        ));
+        assert!(triangle_intersects_cell(
+            [[0.0, 0.0, 0.0], [2.0, 0.0, 0.0], [0.0, 2.0, 0.0]],
+            [1.5, 1.0],
+            [2.0; 2]
+        ));
+    }
+
+    #[test]
+    fn native_cell_distance_boundary_zoom_and_basement_override() {
+        let mut plan = TerrainLodPlan {
+            origin: [0.0; 2],
+            inverse_cell_size: [1.0; 2],
+            counts: [8, 8],
+            forced_lod0: vec![false; 64],
+            has_lod1: vec![true; 64],
+            face_nodes: Vec::new(),
+        };
+        assert_eq!(
+            plan.selected_lod(2 * 8 + 2, [0.9, 0.9], 1.3),
+            Some(TerrainLod::Lod0)
+        );
+        assert_eq!(
+            plan.selected_lod(3 * 8, [0.9, 0.9], 1.3),
+            Some(TerrainLod::Lod1)
+        );
+        assert_eq!(
+            plan.selected_lod(3 * 8, [1.0, 0.9], 1.3),
+            Some(TerrainLod::Lod0)
+        );
+        assert_eq!(
+            plan.selected_lod(3 * 8, [0.9, 0.9], 0.49),
+            Some(TerrainLod::Lod0)
+        );
+        assert_eq!(
+            plan.selected_lod(3 * 8, [0.9, 0.9], 0.5),
+            Some(TerrainLod::Lod1)
+        );
+        plan.forced_lod0[3 * 8] = true;
+        assert_eq!(
+            plan.selected_lod(3 * 8, [0.9, 0.9], 1.3),
+            Some(TerrainLod::Lod0)
+        );
+        plan.has_lod1[7 * 8] = false;
+        assert_eq!(
+            plan.selected_lod(7 * 8, [0.9, 0.9], 1.3),
+            Some(TerrainLod::Lod0)
+        );
+        assert_eq!(plan.selected_lod(64, [0.0; 2], 1.3), None);
+        assert_eq!(plan.selected_lod(0, [f32::NAN, 0.0], 1.3), None);
+        assert_eq!(plan.selected_lod(0, [0.0; 2], f32::INFINITY), None);
+    }
+}