viewport-lib 0.19.0

//! Scene graph with parent-child hierarchy, layers, and dirty-flag transform propagation.
//!
//! `Scene` is a standalone struct that apps own alongside `ViewportRenderer`.
//! It produces `Vec<SceneRenderItem>` via `collect_render_items()`, which feeds
//! into `SceneFrame::surfaces` (usually via `SceneFrame::from_surface_items(...)`).
//! The renderer itself remains stateless.

use std::collections::{HashMap, HashSet};
use std::sync::atomic::{AtomicU64, Ordering};

use crate::interaction::select::selection::{NodeId, Selection};
use crate::renderer::{PickId, SceneRenderItem};
use crate::resources::mesh::mesh_store::MeshId;
use crate::scene::aabb::Aabb;
use crate::scene::material::Material;
use crate::scene::spatial_index::SpatialIndex;
use crate::scene::traits::ViewportObject;
use crate::{LightKind, LightSource};

/// Node count above which `collect_render_items_culled` uses the octree
/// spatial index instead of the flat walk.
const SPATIAL_THRESHOLD: usize = 500;

// ---------------------------------------------------------------------------
// Layer
// ---------------------------------------------------------------------------

/// Opaque layer identifier.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub struct LayerId(pub u32);

/// A named visibility layer. Nodes belong to exactly one layer.
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub struct Layer {
    /// Unique layer identifier.
    pub id: LayerId,
    /// Human-readable layer name.
    pub name: String,
    /// Whether nodes on this layer are rendered.
    pub visible: bool,
    /// When true, nodes on this layer render but cannot appear selected.
    pub locked: bool,
    /// Display colour for this layer (RGBA, each component 0.0-1.0).
    pub colour: [f32; 4],
    /// Sort order for layer display. Lower values appear first.
    pub order: u32,
}

// ---------------------------------------------------------------------------
// Group
// ---------------------------------------------------------------------------

/// Opaque group identifier.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub struct GroupId(pub u32);

/// A named group of scene nodes. Membership is independent of parent-child hierarchy.
pub struct Group {
    /// Unique group identifier.
    pub id: GroupId,
    /// Human-readable group name.
    pub name: String,
    /// Set of node IDs belonging to this group.
    pub members: HashSet<NodeId>,
}

// ---------------------------------------------------------------------------
// SceneNode
// ---------------------------------------------------------------------------

/// A node in the scene graph.
pub struct SceneNode {
    id: NodeId,
    name: String,
    mesh_id: Option<MeshId>,
    material: Material,
    appearance: crate::scene::material::ItemSettings,
    visible: bool,
    show_normals: bool,
    local_transform: glam::Mat4,
    world_transform: glam::Mat4,
    parent: Option<NodeId>,
    children: Vec<NodeId>,
    layer: LayerId,
    dirty: bool,
    /// Per-node deformer instance ID. See
    /// [`SceneRenderItem::deform_instance`](crate::renderer::SceneRenderItem::deform_instance).
    deform_instance: Option<u32>,
    /// Whether projected decals land on this surface. Default: `true`.
    receives_decals: bool,
    /// LOD group this node draws through, if any. When set, the renderer
    /// picks a level each frame from the node's on-screen size and overwrites
    /// the drawn mesh; `mesh_id` should hold the full-detail (level 0) mesh so
    /// the node is collected and frustum-culled against the shared AABB.
    lod_group: Option<crate::resources::LodGroupId>,
    /// Light source carried by this node. Position and direction are resolved
    /// from `world_transform` at collect time; the values stored here serve
    /// as the local-space template.
    pub light: Option<LightSource>,
}

impl SceneNode {
    /// Unique identifier for this node.
    pub fn id(&self) -> NodeId {
        self.id
    }

    /// Display name of this node.
    pub fn name(&self) -> &str {
        &self.name
    }

    /// GPU mesh associated with this node, or `None` if no mesh has been uploaded.
    pub fn mesh_id(&self) -> Option<MeshId> {
        self.mesh_id
    }

    /// LOD group this node draws through, or `None` for a plain mesh.
    pub fn lod_group(&self) -> Option<crate::resources::LodGroupId> {
        self.lod_group
    }

    /// Material parameters (colour, shading, texture) for this node.
    pub fn material(&self) -> &Material {
        &self.material
    }

    /// Per-node appearance overrides (hidden, unlit, opacity, wireframe).
    pub fn appearance(&self) -> &crate::scene::material::ItemSettings {
        &self.appearance
    }

    /// Whether this node is visible.
    pub fn is_visible(&self) -> bool {
        self.visible
    }

    /// Whether per-vertex normals are rendered for this node.
    pub fn show_normals(&self) -> bool {
        self.show_normals
    }

    /// Local transform relative to this node's parent (or world if no parent).
    pub fn local_transform(&self) -> glam::Mat4 {
        self.local_transform
    }

    /// World-space transform. Updated by `Scene::update_transforms()`.
    pub fn world_transform(&self) -> glam::Mat4 {
        self.world_transform
    }

    /// Parent node ID, or `None` if this is a root node.
    pub fn parent(&self) -> Option<NodeId> {
        self.parent
    }

    /// IDs of this node's direct children.
    pub fn children(&self) -> &[NodeId] {
        &self.children
    }

    /// Layer this node belongs to.
    pub fn layer(&self) -> LayerId {
        self.layer
    }

    /// Whether projected decals land on this surface.
    pub fn receives_decals(&self) -> bool {
        self.receives_decals
    }

    /// Set whether projected decals land on this surface.
    pub fn set_receives_decals(&mut self, v: bool) {
        self.receives_decals = v;
    }
}

impl ViewportObject for SceneNode {
    fn id(&self) -> u64 {
        self.id
    }

    fn mesh_id(&self) -> Option<u64> {
        self.mesh_id.map(|m| m.index() as u64)
    }

    fn model_matrix(&self) -> glam::Mat4 {
        self.world_transform
    }

    fn position(&self) -> glam::Vec3 {
        self.world_transform.col(3).truncate()
    }

    fn rotation(&self) -> glam::Quat {
        let (_scale, rotation, _translation) = self.world_transform.to_scale_rotation_translation();
        rotation
    }

    fn scale(&self) -> glam::Vec3 {
        let (scale, _rotation, _translation) = self.world_transform.to_scale_rotation_translation();
        scale
    }

    fn is_visible(&self) -> bool {
        self.visible
    }

    fn colour(&self) -> glam::Vec3 {
        glam::Vec3::from(self.material.base_colour)
    }

    fn show_normals(&self) -> bool {
        self.show_normals
    }

    fn material(&self) -> Material {
        self.material
    }
}

// ---------------------------------------------------------------------------
// SceneStats
// ---------------------------------------------------------------------------

/// Per-frame diagnostics from `collect_render_items_culled`.
#[derive(Debug, Clone, Copy, Default)]
pub struct SceneStats {
    /// Number of nodes currently held in the spatial index.
    /// Zero when the flat walk is active (scene below the threshold).
    pub spatial_index_nodes: u32,
    /// Time spent in the frustum cull traversal, in milliseconds.
    pub frustum_cull_traversal_ms: f32,
}

// ---------------------------------------------------------------------------
// Scene
// ---------------------------------------------------------------------------

/// Resolve a light source's geometric parameters into world space.
///
/// - Directional: the stored direction is rotated by the node's world rotation.
/// - Point: position comes from the world translation; stored position is ignored.
/// - Spot: position from world translation, direction rotated by world rotation.
fn resolve_light_to_world(src: &LightSource, world: glam::Mat4) -> LightSource {
    let translation = world.col(3).truncate();
    let kind = match &src.kind {
        LightKind::Directional { direction } => {
            let rotated = world
                .transform_vector3(glam::Vec3::from(*direction))
                .normalize();
            LightKind::Directional {
                direction: rotated.into(),
            }
        }
        LightKind::Point { range, .. } => LightKind::Point {
            position: translation.into(),
            range: *range,
        },
        LightKind::Spot {
            direction,
            range,
            inner_angle,
            outer_angle,
            ..
        } => {
            let rotated = world
                .transform_vector3(glam::Vec3::from(*direction))
                .normalize();
            LightKind::Spot {
                position: translation.into(),
                direction: rotated.into(),
                range: *range,
                inner_angle: *inner_angle,
                outer_angle: *outer_angle,
            }
        }
    };
    LightSource {
        kind,
        colour: src.colour,
        intensity: src.intensity,
        importance: src.importance,
        cast_shadows: src.cast_shadows,
    }
}

/// Default layer ID (always exists, cannot be removed).
const DEFAULT_LAYER: LayerId = LayerId(0);

/// A scene graph managing nodes with parent-child hierarchy and layers.
pub struct Scene {
    nodes: HashMap<NodeId, SceneNode>,
    roots: Vec<NodeId>,
    layers: Vec<Layer>,
    next_id: u64,
    next_layer_id: u32,
    groups: Vec<Group>,
    next_group_id: u32,
    /// Monotonically increasing generation counter. Incremented on every mutation.
    /// Callers can compare against a cached value to detect changes without hashing.
    version: u64,
    spatial: SpatialIndex,
    /// True after the first full octree build. Incremental updates apply from here.
    spatial_built: bool,
    last_scene_stats: SceneStats,
    // D4: live decals with lifetime / animation.
    live_decals: Vec<LiveDecal>,
    next_decal_id: u64,
}

/// Global monotonic clock for scene versions.
///
/// Each `Scene::new()` draws an initial offset from this counter so that two
/// distinct scenes can never share the same `version()` value, even when they
/// have been mutated the same number of times.  The renderer's batch cache
/// therefore correctly invalidates when the active scene changes.
static SCENE_VERSION_CLOCK: AtomicU64 = AtomicU64::new(0);

impl Scene {
    /// Create an empty scene with a default layer.
    pub fn new() -> Self {
        // Reserve a block of 2^20 (~1 M) version slots per scene so that
        // wrapping_add(1) mutations stay within this scene's unique range.
        let base = SCENE_VERSION_CLOCK.fetch_add(1 << 20, Ordering::Relaxed);
        Self {
            nodes: HashMap::new(),
            roots: Vec::new(),
            layers: vec![Layer {
                id: DEFAULT_LAYER,
                name: "Default".to_string(),
                visible: true,
                locked: false,
                colour: [1.0, 1.0, 1.0, 1.0],
                order: 0,
            }],
            next_id: 1,
            next_layer_id: 1,
            groups: Vec::new(),
            next_group_id: 0,
            version: base,
            spatial: SpatialIndex::new(),
            spatial_built: false,
            last_scene_stats: SceneStats::default(),
            live_decals: Vec::new(),
            next_decal_id: 0,
        }
    }

    /// Monotonically increasing generation counter.
    ///
    /// Incremented by `wrapping_add(1)` on every mutation. Compare against a
    /// cached value to detect scene changes without hashing instance data.
    pub fn version(&self) -> u64 {
        self.version
    }

    // -- Node lifecycle --

    /// Add a node with a mesh, transform, and material. Returns the new node's ID.
    pub fn add(
        &mut self,
        mesh_id: Option<MeshId>,
        transform: glam::Mat4,
        material: Material,
    ) -> NodeId {
        self.add_named("", mesh_id, transform, material)
    }

    /// Add a named node. Returns the new node's ID.
    pub fn add_named(
        &mut self,
        name: &str,
        mesh_id: Option<MeshId>,
        transform: glam::Mat4,
        material: Material,
    ) -> NodeId {
        let id = self.next_id;
        self.next_id += 1;
        let node = SceneNode {
            id,
            name: name.to_string(),
            mesh_id,
            material,
            appearance: crate::scene::material::ItemSettings::default(),
            visible: true,
            show_normals: false,
            local_transform: transform,
            world_transform: transform,
            parent: None,
            children: Vec::new(),
            layer: DEFAULT_LAYER,
            dirty: true,
            deform_instance: None,
            receives_decals: true,
            lod_group: None,
            light: None,
        };
        self.nodes.insert(id, node);
        self.roots.push(id);
        self.version = self.version.wrapping_add(1);
        if self.spatial_built {
            self.spatial.mark_dirty(id);
        }
        id
    }

    /// Remove a node and all its descendants. Returns all removed IDs
    /// (caller can use these to release mesh references).
    pub fn remove(&mut self, id: NodeId) -> Vec<NodeId> {
        let mut removed = Vec::new();
        self.remove_recursive(id, &mut removed);

        // Remove from parent's children list or from roots.
        if let Some(parent_id) = self.nodes.get(&id).and_then(|n| n.parent) {
            if let Some(parent) = self.nodes.get_mut(&parent_id) {
                parent.children.retain(|c| *c != id);
            }
        } else {
            self.roots.retain(|r| *r != id);
        }

        // Remove from spatial index before nodes are gone.
        if self.spatial_built {
            for &rid in &removed {
                self.spatial.remove_node(rid);
            }
        }

        // Actually remove nodes.
        for &rid in &removed {
            self.nodes.remove(&rid);
        }
        // Also remove from roots any descendant that might have been listed.
        self.roots.retain(|r| !removed.contains(r));

        // Remove removed nodes from all groups.
        for group in &mut self.groups {
            for &rid in &removed {
                group.members.remove(&rid);
            }
        }

        self.version = self.version.wrapping_add(1);
        removed
    }

    fn remove_recursive(&self, id: NodeId, out: &mut Vec<NodeId>) {
        out.push(id);
        if let Some(node) = self.nodes.get(&id) {
            for &child in &node.children {
                self.remove_recursive(child, out);
            }
        }
    }

    /// Remove several nodes and all their descendants in one pass. Returns
    /// every removed ID. IDs that are not in the scene are skipped, and a node
    /// listed more than once (or nested under another removed node) appears
    /// only once in the result.
    ///
    /// This is equivalent to calling [`remove`](Self::remove) for each ID, but
    /// it scans the roots list, group membership, and the version counter once
    /// for the whole batch instead of once per node. Removing N individual root
    /// nodes one at a time is O(N * roots) because each `remove` rescans the
    /// roots list; `remove_many` collapses that to a single scan. Use it when
    /// evicting many nodes at once: a streaming cell, a layer toggle, or
    /// tearing down part of a scene.
    pub fn remove_many(&mut self, ids: &[NodeId]) -> Vec<NodeId> {
        // Collect the full removal set: the given nodes plus all descendants,
        // de-duplicated so overlapping subtrees are visited once.
        let mut removed = Vec::new();
        let mut removed_set = HashSet::new();
        for &id in ids {
            if self.nodes.contains_key(&id) {
                self.collect_subtree(id, &mut removed_set, &mut removed);
            }
        }
        if removed.is_empty() {
            return removed;
        }

        // Detach surviving parents from the removed nodes. Parents that are
        // themselves being removed are skipped: their child lists are about to
        // be dropped. Gather distinct parents first so a parent shared by
        // several removed children is rewritten only once.
        let mut parents_to_fix = HashSet::new();
        for &id in ids {
            if let Some(parent_id) = self.nodes.get(&id).and_then(|n| n.parent) {
                if !removed_set.contains(&parent_id) {
                    parents_to_fix.insert(parent_id);
                }
            }
        }
        for parent_id in parents_to_fix {
            if let Some(parent) = self.nodes.get_mut(&parent_id) {
                parent.children.retain(|c| !removed_set.contains(c));
            }
        }

        // Remove from the spatial index before the nodes are gone. Each removal
        // follows the node's stored path, so this is cheap per node.
        if self.spatial_built {
            for &rid in &removed {
                self.spatial.remove_node(rid);
            }
        }

        for &rid in &removed {
            self.nodes.remove(&rid);
        }

        // One pass each over roots and group membership for the whole batch.
        self.roots.retain(|r| !removed_set.contains(r));
        for group in &mut self.groups {
            group.members.retain(|m| !removed_set.contains(m));
        }

        self.version = self.version.wrapping_add(1);
        removed
    }

    /// Push `id` and all its descendants into `out`, using `seen` to skip nodes
    /// already collected (so overlapping subtrees are not visited twice).
    fn collect_subtree(&self, id: NodeId, seen: &mut HashSet<NodeId>, out: &mut Vec<NodeId>) {
        if !seen.insert(id) {
            return;
        }
        out.push(id);
        if let Some(node) = self.nodes.get(&id) {
            for &child in &node.children {
                self.collect_subtree(child, seen, out);
            }
        }
    }

    // -- Hierarchy --

    /// Reparent a node. `None` makes it a root node.
    pub fn set_parent(&mut self, child_id: NodeId, new_parent: Option<NodeId>) {
        // Remove from current parent or roots.
        let old_parent = self.nodes.get(&child_id).and_then(|n| n.parent);
        if let Some(old_pid) = old_parent {
            if let Some(old_p) = self.nodes.get_mut(&old_pid) {
                old_p.children.retain(|c| *c != child_id);
            }
        } else {
            self.roots.retain(|r| *r != child_id);
        }

        // Add to new parent or roots.
        if let Some(new_pid) = new_parent {
            if let Some(new_p) = self.nodes.get_mut(&new_pid) {
                new_p.children.push(child_id);
            }
        } else {
            self.roots.push(child_id);
        }

        if let Some(node) = self.nodes.get_mut(&child_id) {
            node.parent = new_parent;
            node.dirty = true;
        }
        self.version = self.version.wrapping_add(1);
        if self.spatial_built {
            self.mark_spatial_dirty_subtree(child_id);
        }
    }

    /// Children of a node.
    pub fn children(&self, id: NodeId) -> &[NodeId] {
        self.nodes
            .get(&id)
            .map(|n| n.children.as_slice())
            .unwrap_or(&[])
    }

    /// Parent of a node.
    pub fn parent(&self, id: NodeId) -> Option<NodeId> {
        self.nodes.get(&id).and_then(|n| n.parent)
    }

    /// Root nodes.
    pub fn roots(&self) -> &[NodeId] {
        &self.roots
    }

    // -- Properties --

    /// Set the local transform of a node, marking it and its descendants dirty.
    pub fn set_local_transform(&mut self, id: NodeId, transform: glam::Mat4) {
        if let Some(node) = self.nodes.get_mut(&id) {
            node.local_transform = transform;
            node.dirty = true;
        }
        self.mark_descendants_dirty(id);
        self.version = self.version.wrapping_add(1);
        if self.spatial_built {
            self.mark_spatial_dirty_subtree(id);
        }
    }

    /// Set node visibility.
    pub fn set_visible(&mut self, id: NodeId, visible: bool) {
        if let Some(node) = self.nodes.get_mut(&id) {
            node.visible = visible;
        }
        self.version = self.version.wrapping_add(1);
        if self.spatial_built {
            self.spatial.mark_dirty(id);
        }
    }

    /// Set node material.
    pub fn set_material(&mut self, id: NodeId, material: Material) {
        if let Some(node) = self.nodes.get_mut(&id) {
            node.material = material;
        }
        self.version = self.version.wrapping_add(1);
    }

    /// Set node appearance overrides.
    pub fn set_appearance(&mut self, id: NodeId, appearance: crate::scene::material::ItemSettings) {
        if let Some(node) = self.nodes.get_mut(&id) {
            node.appearance = appearance;
        }
        self.version = self.version.wrapping_add(1);
    }

    /// Set node mesh.
    pub fn set_mesh(&mut self, id: NodeId, mesh_id: Option<MeshId>) {
        if let Some(node) = self.nodes.get_mut(&id) {
            node.mesh_id = mesh_id;
        }
        self.version = self.version.wrapping_add(1);
        if self.spatial_built {
            self.spatial.mark_dirty(id);
        }
    }

    /// Attach (or clear) a LOD group on a node.
    ///
    /// The renderer chooses a level from the node's on-screen size each frame
    /// and overwrites the drawn mesh. Set the node's `mesh_id` to the group's
    /// full-detail (level 0) mesh so the node is collected and frustum-culled
    /// against the shared AABB. `None` reverts the node to its plain mesh.
    pub fn set_lod_group(&mut self, id: NodeId, lod_group: Option<crate::resources::LodGroupId>) {
        if let Some(node) = self.nodes.get_mut(&id) {
            node.lod_group = lod_group;
        }
        self.version = self.version.wrapping_add(1);
    }

    /// Set node name.
    pub fn set_name(&mut self, id: NodeId, name: &str) {
        if let Some(node) = self.nodes.get_mut(&id) {
            node.name = name.to_string();
        }
        self.version = self.version.wrapping_add(1);
    }

    /// Set the per-instance deformer ID for a node.
    ///
    /// Addresses per-(mesh, instance) deformer data such as a GPU skinning
    /// joint palette. `None` treats the node as having no per-instance
    /// deformer data and uses the per-mesh slot only.
    pub fn set_deform_instance(&mut self, id: NodeId, instance: Option<u32>) {
        if let Some(node) = self.nodes.get_mut(&id) {
            node.deform_instance = instance;
        }
        self.version = self.version.wrapping_add(1);
    }

    /// Set whether projected decals land on this node's surface.
    pub fn set_receives_decals(&mut self, id: NodeId, v: bool) {
        if let Some(node) = self.nodes.get_mut(&id) {
            node.receives_decals = v;
        }
        self.version = self.version.wrapping_add(1);
    }

    /// Set whether to show normals.
    pub fn set_show_normals(&mut self, id: NodeId, show: bool) {
        if let Some(node) = self.nodes.get_mut(&id) {
            node.show_normals = show;
        }
        self.version = self.version.wrapping_add(1);
    }

    /// Set the layer of a node.
    pub fn set_layer(&mut self, id: NodeId, layer: LayerId) {
        if let Some(node) = self.nodes.get_mut(&id) {
            node.layer = layer;
        }
        self.version = self.version.wrapping_add(1);
    }

    /// Get a reference to a node.
    pub fn node(&self, id: NodeId) -> Option<&SceneNode> {
        self.nodes.get(&id)
    }

    /// Number of nodes in the scene.
    pub fn node_count(&self) -> usize {
        self.nodes.len()
    }

    /// Iterate over all nodes.
    pub fn nodes(&self) -> impl Iterator<Item = &SceneNode> {
        self.nodes.values()
    }

    // -- Layers --

    /// Add a new layer, returning its ID.
    pub fn add_layer(&mut self, name: &str) -> LayerId {
        let id = LayerId(self.next_layer_id);
        let order = self.next_layer_id;
        self.next_layer_id += 1;
        self.layers.push(Layer {
            id,
            name: name.to_string(),
            visible: true,
            locked: false,
            colour: [1.0, 1.0, 1.0, 1.0],
            order,
        });
        self.version = self.version.wrapping_add(1);
        id
    }

    /// Remove a layer, moving all its nodes to the default layer.
    /// Cannot remove the default layer (LayerId(0)).
    pub fn remove_layer(&mut self, id: LayerId) {
        if id == DEFAULT_LAYER {
            return;
        }
        // Move nodes to default layer.
        for node in self.nodes.values_mut() {
            if node.layer == id {
                node.layer = DEFAULT_LAYER;
            }
        }
        self.layers.retain(|l| l.id != id);
        self.version = self.version.wrapping_add(1);
    }

    /// Set layer visibility.
    pub fn set_layer_visible(&mut self, id: LayerId, visible: bool) {
        if let Some(layer) = self.layers.iter_mut().find(|l| l.id == id) {
            layer.visible = visible;
        }
        self.version = self.version.wrapping_add(1);
    }

    /// Set layer locked state. Locked layers render but nodes cannot appear selected.
    pub fn set_layer_locked(&mut self, id: LayerId, locked: bool) {
        if let Some(layer) = self.layers.iter_mut().find(|l| l.id == id) {
            layer.locked = locked;
        }
        self.version = self.version.wrapping_add(1);
    }

    /// Set layer display colour.
    pub fn set_layer_colour(&mut self, id: LayerId, colour: [f32; 4]) {
        if let Some(layer) = self.layers.iter_mut().find(|l| l.id == id) {
            layer.colour = colour;
        }
        self.version = self.version.wrapping_add(1);
    }

    /// Set layer sort order.
    pub fn set_layer_order(&mut self, id: LayerId, order: u32) {
        if let Some(layer) = self.layers.iter_mut().find(|l| l.id == id) {
            layer.order = order;
        }
        self.version = self.version.wrapping_add(1);
    }

    /// Whether a layer is currently locked.
    pub fn is_layer_locked(&self, id: LayerId) -> bool {
        self.layers
            .iter()
            .find(|l| l.id == id)
            .map(|l| l.locked)
            .unwrap_or(false)
    }

    /// All layers, sorted by their `order` field (ascending).
    pub fn layers(&self) -> Vec<&Layer> {
        let mut sorted: Vec<&Layer> = self.layers.iter().collect();
        sorted.sort_by_key(|l| l.order);
        sorted
    }

    // -- Groups --

    /// Create a new named group, returning its ID.
    pub fn create_group(&mut self, name: &str) -> GroupId {
        let id = GroupId(self.next_group_id);
        self.next_group_id += 1;
        self.groups.push(Group {
            id,
            name: name.to_string(),
            members: HashSet::new(),
        });
        self.version = self.version.wrapping_add(1);
        id
    }

    /// Remove a group by ID. Does not affect its member nodes.
    pub fn remove_group(&mut self, id: GroupId) {
        self.groups.retain(|g| g.id != id);
        self.version = self.version.wrapping_add(1);
    }

    /// Add a node to a group.
    pub fn add_to_group(&mut self, node: NodeId, group: GroupId) {
        if let Some(g) = self.groups.iter_mut().find(|g| g.id == group) {
            g.members.insert(node);
        }
        self.version = self.version.wrapping_add(1);
    }

    /// Remove a node from a group.
    pub fn remove_from_group(&mut self, node: NodeId, group: GroupId) {
        if let Some(g) = self.groups.iter_mut().find(|g| g.id == group) {
            g.members.remove(&node);
        }
        self.version = self.version.wrapping_add(1);
    }

    /// Get a group by ID.
    pub fn get_group(&self, id: GroupId) -> Option<&Group> {
        self.groups.iter().find(|g| g.id == id)
    }

    /// All groups in the scene.
    pub fn groups(&self) -> &[Group] {
        &self.groups
    }

    /// Which groups contain the given node.
    pub fn node_groups(&self, node: NodeId) -> Vec<GroupId> {
        self.groups
            .iter()
            .filter(|g| g.members.contains(&node))
            .map(|g| g.id)
            .collect()
    }

    // -- Transform propagation --

    /// Recompute world transforms for all dirty nodes (BFS from roots).
    pub fn update_transforms(&mut self) {
        // We need to iterate roots and process the tree. Since we can't borrow
        // self mutably while iterating, collect the root list first.
        let roots: Vec<NodeId> = self.roots.clone();
        for &root_id in &roots {
            self.propagate_transform(root_id, glam::Mat4::IDENTITY);
        }
    }

    fn propagate_transform(&mut self, id: NodeId, parent_world: glam::Mat4) {
        let (dirty, local, children) = {
            let Some(node) = self.nodes.get(&id) else {
                return;
            };
            (node.dirty, node.local_transform, node.children.clone())
        };

        if dirty {
            let world = parent_world * local;
            let node = self.nodes.get_mut(&id).unwrap();
            node.world_transform = world;
            node.dirty = false;
            // All children must recompute.
            for &child_id in &children {
                self.mark_dirty(child_id);
                self.propagate_transform(child_id, world);
            }
        } else {
            let world = self.nodes[&id].world_transform;
            for &child_id in &children {
                self.propagate_transform(child_id, world);
            }
        }
    }

    fn mark_dirty(&mut self, id: NodeId) {
        if let Some(node) = self.nodes.get_mut(&id) {
            node.dirty = true;
        }
    }

    fn mark_descendants_dirty(&mut self, id: NodeId) {
        let children = self
            .nodes
            .get(&id)
            .map(|n| n.children.clone())
            .unwrap_or_default();
        for child_id in children {
            self.mark_dirty(child_id);
            self.mark_descendants_dirty(child_id);
        }
    }

    /// Mark `id` and all of its descendants dirty in the spatial index.
    fn mark_spatial_dirty_subtree(&mut self, id: NodeId) {
        self.spatial.mark_dirty(id);
        let children = self
            .nodes
            .get(&id)
            .map(|n| n.children.clone())
            .unwrap_or_default();
        for child_id in children {
            self.mark_spatial_dirty_subtree(child_id);
        }
    }

    /// Build the spatial index from scratch using all currently visible nodes
    /// that have a mesh. World transforms must be up to date before calling.
    fn build_spatial_index_from(&mut self, mesh_aabb_fn: &impl Fn(MeshId) -> Option<Aabb>) {
        let entries: Vec<(NodeId, Aabb)> = self
            .nodes
            .values()
            .filter(|n| n.visible && n.mesh_id.is_some())
            .filter_map(|n| {
                let local_aabb = mesh_aabb_fn(n.mesh_id.unwrap())?;
                let world_aabb = local_aabb.transformed(&n.world_transform);
                Some((n.id, world_aabb))
            })
            .collect();
        self.spatial.rebuild(&entries);
        self.spatial_built = true;
    }

    /// Process all pending dirty entries in the spatial index.
    /// World transforms must be up to date before calling.
    fn flush_spatial_dirty(&mut self, mesh_aabb_fn: &impl Fn(MeshId) -> Option<Aabb>) {
        let dirty = self.spatial.drain_dirty();
        for id in dirty {
            self.spatial.remove_entry(id);
            let new_aabb = self.nodes.get(&id).and_then(|node| {
                if !node.visible {
                    return None;
                }
                let mesh_id = node.mesh_id?;
                let local_aabb = mesh_aabb_fn(mesh_id)?;
                Some(local_aabb.transformed(&node.world_transform))
            });
            if let Some(aabb) = new_aabb {
                self.spatial.insert_entry(id, aabb);
            }
        }
    }

    // -- Spatial index public API --

    /// Rebuild the spatial index from scratch.
    ///
    /// Call this after bulk scene construction (level load, import) to avoid
    /// accumulating many incremental dirty updates. The index is maintained
    /// automatically from this point on.
    pub fn rebuild_spatial_index(&mut self, mesh_aabb_fn: impl Fn(MeshId) -> Option<Aabb>) {
        self.update_transforms();
        self.build_spatial_index_from(&mesh_aabb_fn);
    }

    /// Diagnostic statistics from the most recent `collect_render_items_culled` call.
    pub fn scene_stats(&self) -> SceneStats {
        self.last_scene_stats
    }

    // -- Render collection --

    /// Update transforms and collect render items for all visible nodes.
    ///
    /// Skips nodes that are invisible, on an invisible layer, or have no mesh.
    /// Marks selected nodes based on the provided `Selection`.
    pub fn collect_render_items(&mut self, selection: &Selection) -> Vec<SceneRenderItem> {
        self.update_transforms();

        let layer_visible: HashMap<LayerId, bool> =
            self.layers.iter().map(|l| (l.id, l.visible)).collect();

        let layer_locked: HashMap<LayerId, bool> =
            self.layers.iter().map(|l| (l.id, l.locked)).collect();

        let mut items = Vec::new();
        for node in self.nodes.values() {
            if !node.visible {
                continue;
            }
            if !layer_visible.get(&node.layer).copied().unwrap_or(true) {
                continue;
            }
            let Some(mesh_id) = node.mesh_id else {
                continue;
            };
            let locked = layer_locked.get(&node.layer).copied().unwrap_or(false);
            let mut item_settings = node.appearance;
            item_settings.pick_id = PickId(node.id);
            item_settings.selected = if locked {
                false
            } else {
                selection.contains(node.id)
            };
            items.push(SceneRenderItem {
                mesh_id,
                model: node.world_transform.to_cols_array_2d(),
                settings: item_settings,
                show_normals: node.show_normals,
                material: node.material,
                active_attribute: None,
                scalar_range: None,
                colourmap_id: None,
                nan_colour: None,
                warp_attribute: None,
                warp_scale: 1.0,
                deform_instance: node.deform_instance,
                receives_decals: node.receives_decals,
                lic: None,
                lod_group: node.lod_group,
            });
        }
        items
    }

    /// Update transforms and collect render items, culling objects outside the frustum.
    ///
    /// Like `collect_render_items`, but skips objects whose world-space AABB is
    /// entirely outside the given frustum. `mesh_aabb_fn` should return the
    /// local-space AABB for a given `MeshId` (typically read from `GpuMesh::aabb`).
    ///
    /// When the scene has at least 500 nodes, a loose octree spatial index is
    /// used to prune subtrees that are entirely outside the frustum. Below that
    /// threshold the existing flat walk is used.
    pub fn collect_render_items_culled(
        &mut self,
        selection: &Selection,
        frustum: &crate::camera::frustum::Frustum,
        mesh_aabb_fn: impl Fn(MeshId) -> Option<Aabb>,
    ) -> (Vec<SceneRenderItem>, crate::camera::frustum::CullStats) {
        self.update_transforms();

        let layer_visible: HashMap<LayerId, bool> =
            self.layers.iter().map(|l| (l.id, l.visible)).collect();
        let layer_locked: HashMap<LayerId, bool> =
            self.layers.iter().map(|l| (l.id, l.locked)).collect();

        let mut items = Vec::new();
        let mut stats = crate::camera::frustum::CullStats::default();

        if self.nodes.len() >= SPATIAL_THRESHOLD {
            // -- Octree path --
            if !self.spatial_built {
                self.build_spatial_index_from(&mesh_aabb_fn);
            } else {
                self.flush_spatial_dirty(&mesh_aabb_fn);
            }

            let t0 = std::time::Instant::now();
            let mut candidate_ids = Vec::new();
            self.spatial
                .collect_visible(frustum, &mut candidate_ids, &mut stats);
            let traversal_ms = t0.elapsed().as_secs_f32() * 1000.0;

            for id in candidate_ids {
                let Some(node) = self.nodes.get(&id) else {
                    continue;
                };
                if !node.visible {
                    continue;
                }
                if !layer_visible.get(&node.layer).copied().unwrap_or(true) {
                    continue;
                }
                let Some(mesh_id) = node.mesh_id else {
                    continue;
                };
                let locked = layer_locked.get(&node.layer).copied().unwrap_or(false);
                let mut item_settings = node.appearance;
                item_settings.pick_id = PickId(node.id);
                item_settings.selected = if locked {
                    false
                } else {
                    selection.contains(node.id)
                };
                items.push(SceneRenderItem {
                    mesh_id,
                    model: node.world_transform.to_cols_array_2d(),
                    settings: item_settings,
                    show_normals: node.show_normals,
                    material: node.material,
                    active_attribute: None,
                    scalar_range: None,
                    colourmap_id: None,
                    nan_colour: None,
                    warp_attribute: None,
                    warp_scale: 1.0,
                    deform_instance: node.deform_instance,
                    receives_decals: node.receives_decals,
                    lic: None,
                    lod_group: node.lod_group,
                });
            }

            self.last_scene_stats = SceneStats {
                spatial_index_nodes: self.spatial.node_count(),
                frustum_cull_traversal_ms: traversal_ms,
            };
        } else {
            // -- Flat walk --
            let t0 = std::time::Instant::now();

            for node in self.nodes.values() {
                if !node.visible {
                    continue;
                }
                if !layer_visible.get(&node.layer).copied().unwrap_or(true) {
                    continue;
                }
                let Some(mesh_id) = node.mesh_id else {
                    continue;
                };

                stats.total += 1;

                // Frustum cull using world-space AABB.
                if let Some(local_aabb) = mesh_aabb_fn(mesh_id) {
                    let world_aabb = local_aabb.transformed(&node.world_transform);
                    if frustum.cull_aabb(&world_aabb) {
                        stats.culled += 1;
                        continue;
                    }
                }

                let locked = layer_locked.get(&node.layer).copied().unwrap_or(false);
                stats.visible += 1;
                let mut item_settings = node.appearance;
                item_settings.pick_id = PickId(node.id);
                item_settings.selected = if locked {
                    false
                } else {
                    selection.contains(node.id)
                };
                items.push(SceneRenderItem {
                    mesh_id,
                    model: node.world_transform.to_cols_array_2d(),
                    settings: item_settings,
                    show_normals: node.show_normals,
                    material: node.material,
                    active_attribute: None,
                    scalar_range: None,
                    colourmap_id: None,
                    nan_colour: None,
                    warp_attribute: None,
                    warp_scale: 1.0,
                    deform_instance: node.deform_instance,
                    receives_decals: node.receives_decals,
                    lic: None,
                    lod_group: node.lod_group,
                });
            }

            self.last_scene_stats = SceneStats {
                spatial_index_nodes: 0,
                frustum_cull_traversal_ms: t0.elapsed().as_secs_f32() * 1000.0,
            };
        }

        (items, stats)
    }

    // -- Lights --

    /// Add a light source to the scene graph. Returns the new node's ID.
    ///
    /// The node has no mesh. Set its transform with [`Scene::set_local_transform`]
    /// to position and orient the light. For directional lights, rotation drives
    /// the shading direction; for point and spot lights, translation drives position.
    ///
    /// Pass the result of [`Scene::collect_lights`] into `SceneFrame::lights` each
    /// frame so the renderer unions these lights with `EffectsFrame::lighting.lights`.
    pub fn add_light(&mut self, light: LightSource) -> NodeId {
        let id = self.next_id;
        self.next_id += 1;
        let node = SceneNode {
            id,
            name: String::new(),
            mesh_id: None,
            material: crate::scene::material::Material::default(),
            appearance: crate::scene::material::ItemSettings::default(),
            visible: true,
            show_normals: false,
            local_transform: glam::Mat4::IDENTITY,
            world_transform: glam::Mat4::IDENTITY,
            parent: None,
            children: Vec::new(),
            layer: DEFAULT_LAYER,
            dirty: true,
            deform_instance: None,
            receives_decals: false,
            lod_group: None,
            light: Some(light),
        };
        self.nodes.insert(id, node);
        self.roots.push(id);
        self.version = self.version.wrapping_add(1);
        id
    }

    /// Collect world-space light sources from all visible nodes on visible layers.
    ///
    /// Position and direction values are resolved from each node's world transform:
    /// directional lights rotate their direction, point lights take their position
    /// from the world translation, and spot lights take both.
    ///
    /// Push the returned vec into `SceneFrame::lights` each frame. The renderer
    /// unions it with `EffectsFrame::lighting.lights` before building the GPU
    /// light uniform.
    pub fn collect_lights(&mut self) -> Vec<LightSource> {
        self.update_transforms();

        let layer_visible: HashMap<LayerId, bool> =
            self.layers.iter().map(|l| (l.id, l.visible)).collect();

        let mut out = Vec::new();
        for node in self.nodes.values() {
            if !node.visible {
                continue;
            }
            if !layer_visible.get(&node.layer).copied().unwrap_or(true) {
                continue;
            }
            let Some(src) = &node.light else {
                continue;
            };
            out.push(resolve_light_to_world(src, node.world_transform));
        }
        out
    }

    /// Replace the light source on a node. Pass `None` to remove the light.
    pub fn set_light(&mut self, id: NodeId, light: Option<LightSource>) {
        if let Some(node) = self.nodes.get_mut(&id) {
            node.light = light;
        }
        self.version = self.version.wrapping_add(1);
    }

    // -- Tree walking --

    // -- Mesh ref counting --

    /// Count how many scene nodes reference the given mesh.
    ///
    /// O(n) over all nodes. Useful for deciding when to free a GPU mesh.
    pub fn mesh_ref_count(&self, mesh_id: MeshId) -> usize {
        self.nodes
            .values()
            .filter(|n| n.mesh_id == Some(mesh_id))
            .count()
    }

    // -- Tree walking --

    /// Depth-first traversal of the scene tree. Returns `(NodeId, depth)` pairs.
    pub fn walk_depth_first(&self) -> Vec<(NodeId, usize)> {
        let mut result = Vec::new();
        for &root_id in &self.roots {
            self.walk_recursive(root_id, 0, &mut result);
        }
        result
    }

    fn walk_recursive(&self, id: NodeId, depth: usize, out: &mut Vec<(NodeId, usize)>) {
        out.push((id, depth));
        if let Some(node) = self.nodes.get(&id) {
            for &child_id in &node.children {
                self.walk_recursive(child_id, depth + 1, out);
            }
        }
    }
}

impl Default for Scene {
    fn default() -> Self {
        Self::new()
    }
}

// ---------------------------------------------------------------------------
// D4: Live decals with lifetime and animation.
// ---------------------------------------------------------------------------

/// Opaque handle returned by [`Scene::add_decal`].
///
/// Pass to [`Scene::remove_decal`] to delete the decal before it expires.
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub struct DecalHandle(u64);

/// A persistent decal managed by the scene, with optional lifetime and animation.
///
/// Created via [`Scene::add_decal`] or [`Scene::add_decal_with_lifetime`].
/// Call [`Scene::update_decals`] once per frame with the frame delta-time to
/// advance ages and expire finished decals. Call [`Scene::collect_decal_items`]
/// to get the current [`DecalItem`] list ready to push into `fd.scene.decals`.
pub struct LiveDecal {
    id: u64,
    /// The base decal parameters. `uv_offset` and `uv_scale` are recomputed
    /// from `animation` each frame; all other fields are used as-is.
    pub item: crate::renderer::DecalItem,
    /// Optional UV animation. See [`DecalAnimation`].
    pub animation: Option<crate::renderer::DecalAnimation>,
    /// Total lifetime in seconds. `None` = permanent.
    pub lifetime: Option<f32>,
    /// How many seconds the fade-out lasts at the end of the lifetime.
    /// Must be <= `lifetime`. Default: 20% of lifetime when 0.0.
    pub fade_duration: f32,
    /// Elapsed time in seconds since the decal was added.
    pub age: f32,
}

impl Scene {
    /// Add a permanent decal to the scene. Returns a handle for later removal.
    pub fn add_decal(&mut self, item: crate::renderer::DecalItem) -> DecalHandle {
        self.add_live_decal(item, None, None, 0.0)
    }

    /// Add a decal that fades and is automatically removed after `lifetime` seconds.
    ///
    /// `fade_duration` controls how many seconds the alpha ramps to zero before
    /// expiry. Pass `0.0` to use the default (20% of lifetime).
    pub fn add_decal_with_lifetime(
        &mut self,
        item: crate::renderer::DecalItem,
        lifetime: f32,
        fade_duration: f32,
    ) {
        self.add_live_decal(item, Some(lifetime), None, fade_duration);
    }

    /// Add a decal with an optional animation and optional lifetime.
    pub fn add_decal_animated(
        &mut self,
        item: crate::renderer::DecalItem,
        animation: crate::renderer::DecalAnimation,
        lifetime: Option<f32>,
    ) -> DecalHandle {
        self.add_live_decal(item, lifetime, Some(animation), 0.0)
    }

    /// Remove a decal by handle. No-op if the handle is no longer valid.
    pub fn remove_decal(&mut self, handle: DecalHandle) {
        self.live_decals.retain(|d| d.id != handle.0);
    }

    /// Advance all live decals by `dt` seconds and drop expired ones.
    ///
    /// Call once per frame before [`Scene::collect_decal_items`].
    pub fn update_decals(&mut self, dt: f32) {
        for ld in &mut self.live_decals {
            ld.age += dt;
        }
        self.live_decals
            .retain(|ld| ld.lifetime.map_or(true, |lt| ld.age < lt));
    }

    /// Build the [`DecalItem`] list for this frame's `fd.scene.decals`.
    ///
    /// Applies lifetime fading (alpha ramps to 0 in the last 20% of life) and
    /// computes UV offset/scale for animated decals.
    pub fn collect_decal_items(&self) -> Vec<crate::renderer::DecalItem> {
        self.live_decals
            .iter()
            .map(|ld| {
                let mut item = ld.item.clone();

                // Fade out at the end of lifetime.
                if let Some(lt) = ld.lifetime {
                    let fade = if ld.fade_duration > 0.0 {
                        ld.fade_duration.min(lt)
                    } else {
                        lt * 0.2
                    };
                    let time_left = lt - ld.age;
                    if time_left < fade {
                        item.alpha *= (time_left / fade).clamp(0.0, 1.0);
                    }
                }

                // Apply animation.
                if let Some(anim) = &ld.animation {
                    match anim {
                        crate::renderer::DecalAnimation::UvScroll { vx, vy } => {
                            // Accumulate offset from base, wrapping in [0, 1].
                            item.uv_offset[0] =
                                (ld.item.uv_offset[0] + vx * ld.age).rem_euclid(1.0);
                            item.uv_offset[1] =
                                (ld.item.uv_offset[1] + vy * ld.age).rem_euclid(1.0);
                        }
                        crate::renderer::DecalAnimation::SpriteSheet { cols, rows, fps } => {
                            let total = cols * rows;
                            let frame = ((ld.age * fps) as u32).rem_euclid(total.max(1));
                            let col = frame % cols;
                            let row = frame / cols;
                            item.uv_scale = [1.0 / *cols as f32, 1.0 / *rows as f32];
                            item.uv_offset = [col as f32 / *cols as f32, row as f32 / *rows as f32];
                        }
                    }
                }

                item
            })
            .collect()
    }

    fn add_live_decal(
        &mut self,
        item: crate::renderer::DecalItem,
        lifetime: Option<f32>,
        animation: Option<crate::renderer::DecalAnimation>,
        fade_duration: f32,
    ) -> DecalHandle {
        let id = self.next_decal_id;
        self.next_decal_id += 1;
        self.live_decals.push(LiveDecal {
            id,
            item,
            animation,
            lifetime,
            fade_duration,
            age: 0.0,
        });
        DecalHandle(id)
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn lod_group_round_trips_onto_render_items() {
        let mut scene = Scene::new();
        // A node needs a mesh to be collected; the LOD group rides alongside.
        let id = scene.add(
            Some(MeshId::new(0, 0)),
            glam::Mat4::IDENTITY,
            Material::default(),
        );
        assert_eq!(scene.node(id).unwrap().lod_group(), None);

        let group = crate::resources::LodGroupId::new(7, 0);
        scene.set_lod_group(id, Some(group));
        assert_eq!(scene.node(id).unwrap().lod_group(), Some(group));

        let items = scene.collect_render_items(&Selection::new());
        assert_eq!(items.len(), 1);
        assert_eq!(items[0].lod_group, Some(group));

        // Clearing reverts the node to a plain mesh.
        scene.set_lod_group(id, None);
        let items = scene.collect_render_items(&Selection::new());
        assert_eq!(items[0].lod_group, None);
    }

    #[test]
    fn test_add_and_remove() {
        let mut scene = Scene::new();
        let id = scene.add(None, glam::Mat4::IDENTITY, Material::default());
        assert!(scene.node(id).is_some());
        assert_eq!(scene.node_count(), 1);

        let removed = scene.remove(id);
        assert_eq!(removed, vec![id]);
        assert!(scene.node(id).is_none());
        assert_eq!(scene.node_count(), 0);
    }

    #[test]
    fn test_remove_cascades_to_children() {
        let mut scene = Scene::new();
        let parent = scene.add(None, glam::Mat4::IDENTITY, Material::default());
        let child1 = scene.add(None, glam::Mat4::IDENTITY, Material::default());
        let child2 = scene.add(None, glam::Mat4::IDENTITY, Material::default());
        scene.set_parent(child1, Some(parent));
        scene.set_parent(child2, Some(parent));

        let removed = scene.remove(parent);
        assert_eq!(removed.len(), 3);
        assert!(removed.contains(&parent));
        assert!(removed.contains(&child1));
        assert!(removed.contains(&child2));
        assert_eq!(scene.node_count(), 0);
    }

    #[test]
    fn test_remove_many_clears_roots_and_descendants() {
        let mut scene = Scene::new();
        let a = scene.add(None, glam::Mat4::IDENTITY, Material::default());
        let b = scene.add(None, glam::Mat4::IDENTITY, Material::default());
        let b_child = scene.add(None, glam::Mat4::IDENTITY, Material::default());
        scene.set_parent(b_child, Some(b));
        // A node left out of the batch survives.
        let keep = scene.add(None, glam::Mat4::IDENTITY, Material::default());

        let removed = scene.remove_many(&[a, b]);
        assert_eq!(removed.len(), 3);
        assert!(removed.contains(&a));
        assert!(removed.contains(&b));
        assert!(removed.contains(&b_child));
        assert!(scene.node(a).is_none());
        assert!(scene.node(b_child).is_none());
        assert!(scene.node(keep).is_some());
        assert_eq!(scene.node_count(), 1);
    }

    #[test]
    fn test_remove_many_dedups_overlapping_and_missing() {
        let mut scene = Scene::new();
        let parent = scene.add(None, glam::Mat4::IDENTITY, Material::default());
        let child = scene.add(None, glam::Mat4::IDENTITY, Material::default());
        scene.set_parent(child, Some(parent));

        // child is nested under parent, parent is listed twice, and 9999 is not
        // in the scene. Each live node should appear exactly once.
        let removed = scene.remove_many(&[parent, child, parent, 9999_u64]);
        assert_eq!(removed.len(), 2);
        assert!(removed.contains(&parent));
        assert!(removed.contains(&child));
        assert_eq!(scene.node_count(), 0);
    }

    #[test]
    fn test_remove_many_detaches_surviving_parent() {
        let mut scene = Scene::new();
        let parent = scene.add(None, glam::Mat4::IDENTITY, Material::default());
        let child1 = scene.add(None, glam::Mat4::IDENTITY, Material::default());
        let child2 = scene.add(None, glam::Mat4::IDENTITY, Material::default());
        scene.set_parent(child1, Some(parent));
        scene.set_parent(child2, Some(parent));

        scene.remove_many(&[child1, child2]);
        assert!(scene.node(parent).is_some());
        assert!(scene.node(parent).unwrap().children().is_empty());
    }

    #[test]
    fn test_remove_many_empty_is_noop() {
        let mut scene = Scene::new();
        scene.add(None, glam::Mat4::IDENTITY, Material::default());
        let before = scene.version();
        let removed = scene.remove_many(&[]);
        assert!(removed.is_empty());
        assert_eq!(scene.version(), before);
        assert_eq!(scene.node_count(), 1);
    }

    #[test]
    fn test_set_parent_updates_world_transform() {
        let mut scene = Scene::new();
        let parent = scene.add(
            None,
            glam::Mat4::from_translation(glam::Vec3::new(5.0, 0.0, 0.0)),
            Material::default(),
        );
        let child = scene.add(
            None,
            glam::Mat4::from_translation(glam::Vec3::new(1.0, 0.0, 0.0)),
            Material::default(),
        );
        scene.set_parent(child, Some(parent));
        scene.update_transforms();

        let world = scene.node(child).unwrap().world_transform();
        let pos = world.col(3).truncate();
        assert!((pos.x - 6.0).abs() < 1e-5, "expected x=6.0, got {}", pos.x);
    }

    #[test]
    fn test_dirty_propagation() {
        let mut scene = Scene::new();
        let parent = scene.add(
            None,
            glam::Mat4::from_translation(glam::Vec3::new(1.0, 0.0, 0.0)),
            Material::default(),
        );
        let child = scene.add(
            None,
            glam::Mat4::from_translation(glam::Vec3::new(2.0, 0.0, 0.0)),
            Material::default(),
        );
        scene.set_parent(child, Some(parent));
        scene.update_transforms();

        // Now move the parent.
        scene.set_local_transform(
            parent,
            glam::Mat4::from_translation(glam::Vec3::new(10.0, 0.0, 0.0)),
        );
        scene.update_transforms();

        let child_pos = scene
            .node(child)
            .unwrap()
            .world_transform()
            .col(3)
            .truncate();
        assert!(
            (child_pos.x - 12.0).abs() < 1e-5,
            "expected x=12.0, got {}",
            child_pos.x
        );
    }

    #[test]
    fn test_layer_visibility_hides_nodes() {
        let mut scene = Scene::new();
        let layer = scene.add_layer("Hidden");
        let id = scene.add(
            Some(MeshId::new(0, 0)),
            glam::Mat4::IDENTITY,
            Material::default(),
        );
        scene.set_layer(id, layer);
        scene.set_layer_visible(layer, false);

        let items = scene.collect_render_items(&Selection::new());
        assert!(items.is_empty());
    }

    #[test]
    fn test_collect_skips_invisible_nodes() {
        let mut scene = Scene::new();
        let id = scene.add(
            Some(MeshId::new(0, 0)),
            glam::Mat4::IDENTITY,
            Material::default(),
        );
        scene.set_visible(id, false);

        let items = scene.collect_render_items(&Selection::new());
        assert!(items.is_empty());
    }

    #[test]
    fn test_collect_skips_meshless_nodes() {
        let mut scene = Scene::new();
        scene.add(None, glam::Mat4::IDENTITY, Material::default());

        let items = scene.collect_render_items(&Selection::new());
        assert!(items.is_empty());
    }

    #[test]
    fn test_collect_marks_selected() {
        let mut scene = Scene::new();
        let id = scene.add(
            Some(MeshId::new(0, 0)),
            glam::Mat4::IDENTITY,
            Material::default(),
        );

        let mut sel = Selection::new();
        sel.select_one(id);

        let items = scene.collect_render_items(&sel);
        assert_eq!(items.len(), 1);
        assert!(items[0].settings.selected);
    }

    #[test]
    fn test_unparent_makes_root() {
        let mut scene = Scene::new();
        let parent = scene.add(None, glam::Mat4::IDENTITY, Material::default());
        let child = scene.add(None, glam::Mat4::IDENTITY, Material::default());
        scene.set_parent(child, Some(parent));
        assert!(!scene.roots().contains(&child));

        scene.set_parent(child, None);
        assert!(scene.roots().contains(&child));
        assert!(scene.node(child).unwrap().parent().is_none());
    }

    #[test]
    fn test_collect_culled_filters_offscreen() {
        let mut scene = Scene::new();
        // Object at origin : should be visible.
        let visible_id = scene.add(
            Some(MeshId::new(0, 0)),
            glam::Mat4::IDENTITY,
            Material::default(),
        );
        // Object far behind camera : should be culled.
        let _behind = scene.add(
            Some(MeshId::new(1, 0)),
            glam::Mat4::from_translation(glam::Vec3::new(0.0, 0.0, 100.0)),
            Material::default(),
        );

        let sel = Selection::new();
        // Camera at z=5 looking toward origin.
        let view = glam::Mat4::look_at_rh(
            glam::Vec3::new(0.0, 0.0, 5.0),
            glam::Vec3::ZERO,
            glam::Vec3::Y,
        );
        let proj = glam::Mat4::perspective_rh(std::f32::consts::FRAC_PI_4, 1.0, 0.1, 50.0);
        let frustum = crate::camera::frustum::Frustum::from_view_proj(&(proj * view));

        // Both meshes get a unit-cube AABB.
        let unit_aabb = crate::scene::aabb::Aabb {
            min: glam::Vec3::splat(-0.5),
            max: glam::Vec3::splat(0.5),
        };

        let (items, stats) =
            scene.collect_render_items_culled(&sel, &frustum, |_mesh_id| Some(unit_aabb));

        assert_eq!(stats.total, 2);
        assert_eq!(stats.visible, 1);
        assert_eq!(stats.culled, 1);
        assert_eq!(items.len(), 1);
        // The visible item should be the one at the origin (mesh_index 0).
        assert_eq!(items[0].mesh_id.index(), visible_id as usize - 1); // MeshId::new(0, 0).index() == 0
        let _ = visible_id; // suppress unused warning
    }

    // --- Layer lock/colour/order tests ---

    #[test]
    fn test_layer_locked_field_default_false() {
        let scene = Scene::new();
        let layers = scene.layers();
        let default_layer = layers.iter().find(|l| l.id == LayerId(0)).unwrap();
        assert!(!default_layer.locked);
    }

    #[test]
    fn test_add_layer_has_locked_false_colour_white_and_order() {
        let mut scene = Scene::new();
        let layer_id = scene.add_layer("Test");
        let layers = scene.layers();
        let layer = layers.iter().find(|l| l.id == layer_id).unwrap();
        assert!(!layer.locked);
        assert_eq!(layer.colour, [1.0, 1.0, 1.0, 1.0]);
        assert!(layer.order > 0); // non-default layer has order >= 1
    }

    #[test]
    fn test_set_layer_locked() {
        let mut scene = Scene::new();
        let layer_id = scene.add_layer("Locked");
        scene.set_layer_locked(layer_id, true);
        assert!(scene.is_layer_locked(layer_id));
        scene.set_layer_locked(layer_id, false);
        assert!(!scene.is_layer_locked(layer_id));
    }

    #[test]
    fn test_set_layer_colour() {
        let mut scene = Scene::new();
        let layer_id = scene.add_layer("Coloured");
        scene.set_layer_colour(layer_id, [1.0, 0.0, 0.0, 1.0]);
        let layers = scene.layers();
        let layer = layers.iter().find(|l| l.id == layer_id).unwrap();
        assert_eq!(layer.colour, [1.0, 0.0, 0.0, 1.0]);
    }

    #[test]
    fn test_set_layer_order() {
        let mut scene = Scene::new();
        let layer_id = scene.add_layer("Orderly");
        scene.set_layer_order(layer_id, 99);
        let layers = scene.layers();
        let layer = layers.iter().find(|l| l.id == layer_id).unwrap();
        assert_eq!(layer.order, 99);
    }

    #[test]
    fn test_locked_layer_suppresses_selection_in_render_items() {
        let mut scene = Scene::new();
        let layer_id = scene.add_layer("Locked");
        let node_id = scene.add(
            Some(MeshId::new(0, 0)),
            glam::Mat4::IDENTITY,
            Material::default(),
        );
        scene.set_layer(node_id, layer_id);
        scene.set_layer_locked(layer_id, true);

        let mut sel = Selection::new();
        sel.select_one(node_id);

        let items = scene.collect_render_items(&sel);
        assert_eq!(items.len(), 1, "locked layer nodes still render");
        assert!(
            !items[0].settings.selected,
            "locked layer nodes must not appear selected"
        );
    }

    #[test]
    fn test_layers_sorted_by_order() {
        let mut scene = Scene::new();
        let a = scene.add_layer("A");
        let b = scene.add_layer("B");
        // Set reverse order
        scene.set_layer_order(a, 10);
        scene.set_layer_order(b, 5);
        let layers = scene.layers();
        // Find positions
        let pos_b = layers.iter().position(|l| l.id == b).unwrap();
        let pos_a = layers.iter().position(|l| l.id == a).unwrap();
        assert!(
            pos_b < pos_a,
            "layer B (order=5) should appear before A (order=10)"
        );
    }

    // --- Group tests ---

    #[test]
    fn test_create_group_returns_id() {
        let mut scene = Scene::new();
        let gid = scene.create_group("MyGroup");
        let group = scene.get_group(gid).unwrap();
        assert_eq!(group.name, "MyGroup");
        assert!(group.members.is_empty());
    }

    #[test]
    fn test_add_to_group_and_remove_from_group() {
        let mut scene = Scene::new();
        let gid = scene.create_group("G");
        let node_id = scene.add(None, glam::Mat4::IDENTITY, Material::default());
        scene.add_to_group(node_id, gid);
        assert!(scene.get_group(gid).unwrap().members.contains(&node_id));
        scene.remove_from_group(node_id, gid);
        assert!(!scene.get_group(gid).unwrap().members.contains(&node_id));
    }

    #[test]
    fn test_groups_returns_all_groups() {
        let mut scene = Scene::new();
        scene.create_group("G1");
        scene.create_group("G2");
        assert_eq!(scene.groups().len(), 2);
    }

    #[test]
    fn test_node_groups_returns_containing_groups() {
        let mut scene = Scene::new();
        let g1 = scene.create_group("G1");
        let g2 = scene.create_group("G2");
        let node_id = scene.add(None, glam::Mat4::IDENTITY, Material::default());
        scene.add_to_group(node_id, g1);
        scene.add_to_group(node_id, g2);
        let groups = scene.node_groups(node_id);
        assert_eq!(groups.len(), 2);
        assert!(groups.contains(&g1));
        assert!(groups.contains(&g2));
    }

    #[test]
    fn test_remove_node_cleans_up_group_membership() {
        let mut scene = Scene::new();
        let gid = scene.create_group("G");
        let node_id = scene.add(None, glam::Mat4::IDENTITY, Material::default());
        scene.add_to_group(node_id, gid);
        scene.remove(node_id);
        assert!(!scene.get_group(gid).unwrap().members.contains(&node_id));
    }

    // --- Mesh ref count tests ---

    #[test]
    fn test_mesh_ref_count_zero_for_unused_mesh() {
        let scene = Scene::new();
        assert_eq!(scene.mesh_ref_count(MeshId::new(42, 0)), 0);
    }

    #[test]
    fn test_mesh_ref_count_correct_for_nodes() {
        let mut scene = Scene::new();
        scene.add(
            Some(MeshId::new(0, 0)),
            glam::Mat4::IDENTITY,
            Material::default(),
        );
        scene.add(
            Some(MeshId::new(0, 0)),
            glam::Mat4::IDENTITY,
            Material::default(),
        );
        scene.add(
            Some(MeshId::new(1, 0)),
            glam::Mat4::IDENTITY,
            Material::default(),
        );
        assert_eq!(scene.mesh_ref_count(MeshId::new(0, 0)), 2);
        assert_eq!(scene.mesh_ref_count(MeshId::new(1, 0)), 1);
    }

    #[test]
    fn test_mesh_ref_count_decreases_after_remove() {
        let mut scene = Scene::new();
        let node_a = scene.add(
            Some(MeshId::new(0, 0)),
            glam::Mat4::IDENTITY,
            Material::default(),
        );
        scene.add(
            Some(MeshId::new(0, 0)),
            glam::Mat4::IDENTITY,
            Material::default(),
        );
        assert_eq!(scene.mesh_ref_count(MeshId::new(0, 0)), 2);
        scene.remove(node_a);
        assert_eq!(scene.mesh_ref_count(MeshId::new(0, 0)), 1);
    }

    #[test]
    fn test_remove_group() {
        let mut scene = Scene::new();
        let gid = scene.create_group("G");
        scene.remove_group(gid);
        assert!(scene.get_group(gid).is_none());
        assert!(scene.groups().is_empty());
    }

    #[test]
    fn test_walk_depth_first_order() {
        let mut scene = Scene::new();
        let root = scene.add_named("root", None, glam::Mat4::IDENTITY, Material::default());
        let child_a = scene.add_named("a", None, glam::Mat4::IDENTITY, Material::default());
        let child_b = scene.add_named("b", None, glam::Mat4::IDENTITY, Material::default());
        let grandchild = scene.add_named("a1", None, glam::Mat4::IDENTITY, Material::default());
        scene.set_parent(child_a, Some(root));
        scene.set_parent(child_b, Some(root));
        scene.set_parent(grandchild, Some(child_a));

        let walk = scene.walk_depth_first();
        assert_eq!(walk.len(), 4);
        assert_eq!(walk[0], (root, 0));
        assert_eq!(walk[1], (child_a, 1));
        assert_eq!(walk[2], (grandchild, 2));
        assert_eq!(walk[3], (child_b, 1));
    }

    // --- Octree spatial index tests ---

    fn make_test_frustum() -> crate::camera::frustum::Frustum {
        let view = glam::Mat4::look_at_rh(
            glam::Vec3::new(0.0, 0.0, 300.0),
            glam::Vec3::ZERO,
            glam::Vec3::Y,
        );
        let proj = glam::Mat4::perspective_rh(std::f32::consts::FRAC_PI_4, 1.0, 1.0, 400.0);
        crate::camera::frustum::Frustum::from_view_proj(&(proj * view))
    }

    fn unit_aabb() -> crate::scene::aabb::Aabb {
        crate::scene::aabb::Aabb {
            min: glam::Vec3::splat(-0.5),
            max: glam::Vec3::splat(0.5),
        }
    }

    /// Octree path produces the same visible set as the flat walk.
    ///
    /// 100 nodes at the origin (visible) + 500 nodes far behind the camera
    /// (culled). With 600 total the octree path is active.
    #[test]
    fn test_octree_parity_with_known_counts() {
        let mut scene = Scene::new();
        let frustum = make_test_frustum();

        // 100 visible nodes at origin.
        for _ in 0..100 {
            scene.add(
                Some(MeshId::new(0, 0)),
                glam::Mat4::IDENTITY,
                Material::default(),
            );
        }
        // 500 culled nodes behind camera (z >> 300 far plane).
        for _ in 0..500 {
            let mat = glam::Mat4::from_translation(glam::Vec3::new(0.0, 0.0, 9000.0));
            scene.add(Some(MeshId::new(0, 0)), mat, Material::default());
        }

        assert!(scene.node_count() >= SPATIAL_THRESHOLD);

        let sel = Selection::new();
        let (items, stats) =
            scene.collect_render_items_culled(&sel, &frustum, |_| Some(unit_aabb()));

        assert_eq!(
            items.len(),
            100,
            "expected 100 visible items, got {}",
            items.len()
        );
        assert_eq!(stats.visible, 100);
        let scene_stats = scene.scene_stats();
        assert!(
            scene_stats.spatial_index_nodes > 0,
            "spatial index should be active"
        );
    }

    /// After moving nodes outside the frustum via set_local_transform, the
    /// octree reflects the update without a full rebuild.
    #[test]
    fn test_octree_incremental_transform_update() {
        let mut scene = Scene::new();
        let frustum = make_test_frustum();

        let mut ids = Vec::new();
        // 600 nodes all at origin (all visible).
        for _ in 0..600 {
            let id = scene.add(
                Some(MeshId::new(0, 0)),
                glam::Mat4::IDENTITY,
                Material::default(),
            );
            ids.push(id);
        }

        let sel = Selection::new();
        let (items, _) = scene.collect_render_items_culled(&sel, &frustum, |_| Some(unit_aabb()));
        assert_eq!(items.len(), 600, "all 600 should be visible initially");

        // Move the first 300 nodes behind the camera.
        let behind = glam::Mat4::from_translation(glam::Vec3::new(0.0, 0.0, 9000.0));
        for &id in &ids[..300] {
            scene.set_local_transform(id, behind);
        }

        let (items2, _) = scene.collect_render_items_culled(&sel, &frustum, |_| Some(unit_aabb()));
        assert_eq!(
            items2.len(),
            300,
            "300 nodes should be visible after moving the others out"
        );
    }

    /// Removing nodes from a large scene updates the octree correctly.
    #[test]
    fn test_octree_node_removal() {
        let mut scene = Scene::new();
        let frustum = make_test_frustum();

        let mut ids = Vec::new();
        for _ in 0..600 {
            let id = scene.add(
                Some(MeshId::new(0, 0)),
                glam::Mat4::IDENTITY,
                Material::default(),
            );
            ids.push(id);
        }

        let sel = Selection::new();
        let (items, _) = scene.collect_render_items_culled(&sel, &frustum, |_| Some(unit_aabb()));
        assert_eq!(items.len(), 600);

        // Remove 150 nodes.
        for &id in &ids[..150] {
            scene.remove(id);
        }

        let (items2, _) = scene.collect_render_items_culled(&sel, &frustum, |_| Some(unit_aabb()));
        assert_eq!(items2.len(), 450, "should have 450 after removing 150");
    }
}