alice-sdf 3.0.0

//! Bytecode-driven BVH AABB refit.
//!
//! Case B P1 (bytecode-driven full refit): recomputes every AABB in a
//! [`crate::compiled::CompiledSdfBvh`] from the current
//! `Instruction.params[]` values, without needing the original `SdfNode`.
//!
//! Case B P2 (partial refit): given a `dirty` set of instruction indices,
//! walks the ancestor chain via `parent_indices` and only recomputes AABBs
//! for instructions that (a) are dirty themselves or (b) are ancestors of a
//! dirty instruction. Non-affected subtrees keep their cached AABBs.
//!
//! ## Opcode coverage
//!
//! Every `OpCode` (dispatch is on [`OpCode::kind`], which is exhaustive).
//! Primitives without a tight analytic bound use a conservative box derived
//! from their parameters; genuinely unbounded shapes (`Plane`, infinite
//! cylinder / cone, TPMS surfaces) and unbounded modifiers (`RepeatInfinite`,
//! `IFS`, `ProjectiveTransform`, `LatticeDeform`, `SdfSkinning`) are
//! `AabbPacked::infinite()`. `tests/test_evaluator_opcode_parity.rs`
//! samples every primitive against its AABB to enforce conservativeness.
//!
//! Since 1.9.2 this module is also the AABB pass of
//! [`crate::compiled::CompiledSdfBvh::try_compile`] (there is no separate BVH
//! compiler any more).

use super::aabb::{primitives as aabb_prims, AabbPacked};
use super::eval_bvh::CompiledSdfBvh;
use super::instruction::Instruction;
use super::opcode::{OpCode, OpKind};
use glam::{Quat, Vec2, Vec3};
use std::collections::HashSet;

/// Errors returned by the bytecode refit walker.
#[derive(Debug, thiserror::Error)]
pub enum RefitError {
    /// An opcode encountered in the bytecode is not covered by the refit
    /// walker (P1 / P2 slice, ~24 opcodes). Fall back to
    /// `ParamDependencyIndex::refit_bvh(&mut bvh, &sdf_node)`.
    #[error("opcode {opcode:?} at instruction {instruction_index} is not supported by refit; fall back to SdfNode-based refit_bvh")]
    UnsupportedOpcode {
        /// Offending opcode.
        opcode: OpCode,
        /// Instruction index where it was encountered.
        instruction_index: usize,
    },

    /// The value stack underflowed while consuming children for a binary /
    /// unary operator. Indicates malformed bytecode.
    #[error(
        "value stack underflow at instruction {instruction_index} ({opcode:?}); malformed bytecode"
    )]
    ValueStackUnderflow {
        /// Instruction index where the pop failed.
        instruction_index: usize,
        /// Offending opcode.
        opcode: OpCode,
    },

    /// `PopTransform` was reached with no matching transform / modifier on
    /// the transform stack. Indicates malformed bytecode.
    #[error("transform stack underflow at PopTransform (instruction {instruction_index})")]
    TransformStackUnderflow {
        /// Instruction index of the PopTransform that failed.
        instruction_index: usize,
    },

    /// A `dirty` index passed to `refit_partial` exceeds `bvh.instructions.len()`.
    #[error("dirty index {index} out of bounds ({len} instructions)")]
    DirtyIndexOutOfBounds {
        /// Requested index.
        index: usize,
        /// Number of instructions in the BVH.
        len: usize,
    },

    /// `bvh.aabbs.len()` and `bvh.instructions.len()` disagree.
    #[error("bvh internal invariant: aabbs.len()={aabbs} != instructions.len()={instructions}")]
    LengthMismatch {
        /// AABB vector length.
        aabbs: usize,
        /// Instruction vector length.
        instructions: usize,
    },
}

/// Compile-time helper: build `parent_indices` for a prebuilt BVH.
///
/// Simulates the same tape walk as the evaluator. `parent_indices[i]` is
/// `Some(parent_index)` when instruction `i` is a child in a CSG binary op
/// (parent is the op instruction that consumes it) or an inner instruction
/// of a transform / modifier (parent is the transform instruction). Root
/// instruction gets `None`.
///
/// This is intentionally decoupled from `BvhCompiler` so that the same walk
/// can populate the field on already-compiled BVHs (e.g. loaded from disk)
/// without re-running the SdfNode compile path.
///
/// # Errors
///
/// Returns `RefitError::UnsupportedOpcode` if an opcode outside the P1 /
/// P2 coverage slice is encountered.
pub fn build_parent_indices(bvh: &CompiledSdfBvh) -> Result<Vec<Option<u32>>, RefitError> {
    let n = bvh.instructions.len();
    let mut parent = vec![None; n];
    let mut value_stack: Vec<usize> = Vec::new();
    // (transform instruction index)
    let mut transform_stack: Vec<usize> = Vec::new();

    for (i, inst) in bvh.instructions.iter().enumerate() {
        let opcode = inst.opcode;
        match opcode.kind() {
            // Leaves — primitives push themselves onto the value stack.
            OpKind::Primitive => {
                // If inside a transform, the top of transform_stack becomes
                // parent for this primitive.
                if let Some(&t) = transform_stack.last() {
                    parent[i] = Some(t as u32);
                }
                value_stack.push(i);
            }
            // CSG binary — pop 2 children, record parent as this instruction.
            OpKind::Binary => {
                let b = value_stack.pop().ok_or(RefitError::ValueStackUnderflow {
                    instruction_index: i,
                    opcode,
                })?;
                let a = value_stack.pop().ok_or(RefitError::ValueStackUnderflow {
                    instruction_index: i,
                    opcode,
                })?;
                parent[a] = Some(i as u32);
                parent[b] = Some(i as u32);
                if let Some(&t) = transform_stack.last() {
                    parent[i] = Some(t as u32);
                }
                value_stack.push(i);
            }
            // Transforms / modifiers — push onto transform_stack; the child
            // will follow in the bytecode.
            OpKind::Transform | OpKind::Modifier => {
                if let Some(&t) = transform_stack.last() {
                    parent[i] = Some(t as u32);
                }
                transform_stack.push(i);
            }
            OpKind::PopTransform => {
                let t = transform_stack
                    .pop()
                    .ok_or(RefitError::TransformStackUnderflow {
                        instruction_index: i,
                    })?;
                // Consume the child AABB the transform wraps.
                let child = value_stack.pop().ok_or(RefitError::ValueStackUnderflow {
                    instruction_index: i,
                    opcode,
                })?;
                parent[child] = Some(t as u32);
                // PopTransform itself does not participate in the value
                // stack — the transform instruction takes its place.
                value_stack.push(t);
            }
            OpKind::End => break,
        }
    }
    Ok(parent)
}

/// Compile-time companion to [`build_parent_indices`] that records the
/// inclusive end index of each instruction's subtree. See
/// [`crate::compiled::CompiledSdfBvh::subtree_end`] for the semantics.
///
/// # Errors
///
/// Returns `RefitError::UnsupportedOpcode` if an opcode outside the P1 /
/// P3 coverage slice is encountered, or `TransformStackUnderflow` when a
/// `PopTransform` appears with no matching transform.
pub fn build_subtree_ends(bvh: &CompiledSdfBvh) -> Result<Vec<u32>, RefitError> {
    let n = bvh.instructions.len();
    let mut ends: Vec<u32> = (0..n as u32).collect(); // default: end == self
    let mut transform_stack: Vec<usize> = Vec::new();

    for (i, inst) in bvh.instructions.iter().enumerate() {
        let opcode = inst.opcode;
        match opcode.kind() {
            OpKind::Transform | OpKind::Modifier => {
                transform_stack.push(i);
            }
            OpKind::PopTransform => {
                let t = transform_stack
                    .pop()
                    .ok_or(RefitError::TransformStackUnderflow {
                        instruction_index: i,
                    })?;
                // The transform's subtree ends at this PopTransform.
                ends[t] = i as u32;
            }
            OpKind::End => break,
            OpKind::Primitive | OpKind::Binary => {
                // Nothing to do — end == self was the initial value.
            }
        }
    }
    Ok(ends)
}

/// Recompute every AABB in `bvh` from `Instruction.params[]`.
///
/// Walks the bytecode linearly using a value stack + transform stack that
/// mirrors the original `BvhCompiler::compile_node` semantics but reads
/// primitive dimensions from the compiled instructions.
///
/// # Errors
///
/// - `RefitError::LengthMismatch` if the caller passed a BVH whose
///   `aabbs` / `instructions` lengths disagree.
/// - `RefitError::UnsupportedOpcode` for opcodes outside the P1 slice.
/// - `RefitError::ValueStackUnderflow` / `TransformStackUnderflow` if the
///   bytecode is malformed.
pub fn refit_all(bvh: &mut CompiledSdfBvh) -> Result<usize, RefitError> {
    if bvh.aabbs.len() != bvh.instructions.len() {
        return Err(RefitError::LengthMismatch {
            aabbs: bvh.aabbs.len(),
            instructions: bvh.instructions.len(),
        });
    }
    let dirty = None;
    walk_and_recompute(bvh, dirty.as_ref())
}

/// Recompute AABBs only for `dirty` instructions and their ancestor chain.
///
/// The tape walk itself is O(N) — every instruction is visited to keep the
/// value stack coherent — but only the instructions in the effective
/// "recompute set" (dirty ∪ their ancestors) have their AABBs recomputed.
/// Non-affected subtrees keep their cached AABBs, which are still pushed
/// onto the value stack so parent operators see consistent inputs.
///
/// True O(dirty × depth) refit (skipping non-affected subtree walks)
/// requires storing subtree extents and is future work (P3).
///
/// # Errors
///
/// Same as [`refit_all`], plus:
///
/// - `RefitError::DirtyIndexOutOfBounds` if any `dirty` index is beyond
///   `bvh.instructions.len()`.
pub fn refit_partial(bvh: &mut CompiledSdfBvh, dirty: &[usize]) -> Result<usize, RefitError> {
    if bvh.aabbs.len() != bvh.instructions.len() {
        return Err(RefitError::LengthMismatch {
            aabbs: bvh.aabbs.len(),
            instructions: bvh.instructions.len(),
        });
    }
    let n = bvh.instructions.len();
    for &d in dirty {
        if d >= n {
            return Err(RefitError::DirtyIndexOutOfBounds { index: d, len: n });
        }
    }

    // Fold ancestors via parent_indices — this is the "affected set".
    let mut affected: HashSet<usize> = HashSet::with_capacity(dirty.len() * 2);
    for &d in dirty {
        let mut cursor = Some(d);
        while let Some(idx) = cursor {
            if !affected.insert(idx) {
                break;
            }
            cursor = bvh
                .parent_indices
                .get(idx)
                .and_then(|p| p.map(|q| q as usize));
        }
    }

    walk_and_recompute(bvh, Some(&affected))
}

/// Core walker used by both `refit_all` (`affected = None`) and
/// `refit_partial` (`affected = Some(set)`). Returns the number of AABBs
/// actually recomputed.
fn walk_and_recompute(
    bvh: &mut CompiledSdfBvh,
    affected: Option<&HashSet<usize>>,
) -> Result<usize, RefitError> {
    let n = bvh.instructions.len();
    let mut value_stack: Vec<AabbPacked> = Vec::with_capacity(64);
    // (transform instruction index, opcode) — the AABB is written on
    // PopTransform.
    let mut transform_stack: Vec<usize> = Vec::with_capacity(32);
    let mut recomputed = 0usize;
    let mut scene_aabb: Option<AabbPacked> = None;

    let should_recompute = |i: usize| affected.is_none_or(|set| set.contains(&i));
    // Fast subtree skip: if we're about to enter a transform whose subtree
    // contains no dirty instruction (i.e. the transform itself is not in
    // the affected set — since affected includes all ancestors of dirty,
    // this implies no descendant is dirty either), jump past the whole
    // subtree and push the cached AABB. Requires `bvh.subtree_end` to be
    // populated; falls back to per-instruction walk otherwise.
    let has_subtree_ends =
        bvh.subtree_end.len() == n && affected.is_some() && !bvh.subtree_end.is_empty();

    let mut i = 0usize;
    while i < n {
        let inst = bvh.instructions[i];
        let opcode = inst.opcode;
        // Try to skip a transform / modifier subtree wholesale.
        if has_subtree_ends
            && matches!(opcode.kind(), OpKind::Transform | OpKind::Modifier)
            && !should_recompute(i)
        {
            let end = bvh.subtree_end[i] as usize;
            if end > i {
                let aabb = bvh.aabbs[i];
                value_stack.push(aabb);
                scene_aabb = Some(scene_aabb.map_or(aabb, |prev| prev.union(&aabb)));
                i = end + 1;
                continue;
            }
        }
        match opcode.kind() {
            OpKind::Primitive => {
                let aabb = if should_recompute(i) {
                    let new_aabb = primitive_aabb(opcode, &inst, &bvh.aux_data);
                    bvh.aabbs[i] = new_aabb;
                    recomputed += 1;
                    new_aabb
                } else {
                    bvh.aabbs[i]
                };
                value_stack.push(aabb);
                scene_aabb = Some(scene_aabb.map_or(aabb, |prev| prev.union(&aabb)));
            }
            OpKind::Binary => {
                let b = value_stack.pop().ok_or(RefitError::ValueStackUnderflow {
                    instruction_index: i,
                    opcode,
                })?;
                let a = value_stack.pop().ok_or(RefitError::ValueStackUnderflow {
                    instruction_index: i,
                    opcode,
                })?;
                let aabb = if should_recompute(i) {
                    let new_aabb = csg_binary_aabb(opcode, &inst.params, a, b);
                    bvh.aabbs[i] = new_aabb;
                    recomputed += 1;
                    new_aabb
                } else {
                    bvh.aabbs[i]
                };
                value_stack.push(aabb);
                scene_aabb = Some(scene_aabb.map_or(aabb, |prev| prev.union(&aabb)));
            }
            OpKind::Transform | OpKind::Modifier => {
                transform_stack.push(i);
            }
            OpKind::PopTransform => {
                let t = transform_stack
                    .pop()
                    .ok_or(RefitError::TransformStackUnderflow {
                        instruction_index: i,
                    })?;
                let child = value_stack.pop().ok_or(RefitError::ValueStackUnderflow {
                    instruction_index: i,
                    opcode,
                })?;
                let t_inst = bvh.instructions[t];
                let aabb = if should_recompute(t) {
                    let new_aabb = transform_or_modifier_aabb(t_inst.opcode, &t_inst.params, child);
                    bvh.aabbs[t] = new_aabb;
                    recomputed += 1;
                    new_aabb
                } else {
                    bvh.aabbs[t]
                };
                value_stack.push(aabb);
                scene_aabb = Some(scene_aabb.map_or(aabb, |prev| prev.union(&aabb)));
            }
            OpKind::End => break,
        }
        i += 1;
    }

    // The scene bound is the root's AABB (top of the value stack at `End`), not the
    // union of every intermediate push — an inner child's untransformed bound must
    // not leak into the scene bound (e.g. `sphere.translate(5,3,0)`).
    if let Some(root) = value_stack.last() {
        bvh.scene_aabb = *root;
    } else if let Some(aabb) = scene_aabb {
        bvh.scene_aabb = aabb;
    }
    Ok(recomputed)
}

/// Conservative axis-aligned bound of a primitive instruction.
///
/// Exhaustive over every primitive opcode. Shapes whose orientation or exact
/// extent is not worth encoding use a centred cube of a generous radius;
/// `tests/test_evaluator_opcode_parity.rs::primitive_aabbs_are_conservative`
/// samples the SDF against the bound.
fn primitive_aabb(opcode: OpCode, inst: &Instruction, aux_data: &[f32]) -> AabbPacked {
    let params = &inst.params;
    let cube = |r: f32| AabbPacked::new(Vec3::splat(-r.abs()), Vec3::splat(r.abs()));
    match opcode {
        OpCode::Sphere => aabb_prims::sphere_aabb(params[0]),
        OpCode::Box3d => aabb_prims::box_aabb(Vec3::new(params[0], params[1], params[2])),
        OpCode::Cylinder => aabb_prims::cylinder_aabb(params[0], params[1]),
        OpCode::Torus => aabb_prims::torus_aabb(params[0], params[1]),
        OpCode::Plane => aabb_prims::plane_aabb(),
        OpCode::Capsule => {
            let a = Vec3::new(params[0], params[1], params[2]);
            let b = Vec3::new(params[3], params[4], params[5]);
            aabb_prims::capsule_aabb(a, b, params[6])
        }
        OpCode::Cone => {
            let r = params[0];
            let hh = params[1];
            AabbPacked::new(Vec3::new(-r, -hh, -r), Vec3::new(r, hh, r))
        }
        OpCode::Ellipsoid => {
            let radii = Vec3::new(params[0], params[1], params[2]);
            AabbPacked::new(-radii, radii)
        }
        OpCode::RoundedCone => {
            // Capsule-like: spheres of r1 / r2 centred at y = -hh / +hh
            let (r1, r2, hh) = (params[0], params[1], params[2]);
            let max_r = r1.max(r2);
            AabbPacked::new(
                Vec3::new(-max_r, -hh - r1, -max_r),
                Vec3::new(max_r, hh + r2, max_r),
            )
        }
        OpCode::Pyramid => {
            let hh = params[0];
            AabbPacked::new(Vec3::new(-0.5, -hh, -0.5), Vec3::new(0.5, hh, 0.5))
        }
        OpCode::Octahedron => cube(params[0]),
        OpCode::HexPrism => {
            let hex_r = params[0];
            let hh = params[1];
            AabbPacked::new(Vec3::new(-hex_r, -hex_r, -hh), Vec3::new(hex_r, hex_r, hh))
        }
        OpCode::Link => {
            let half_length = params[0];
            let r1 = params[1];
            let r2 = params[2];
            let extent = r1 + r2;
            AabbPacked::new(
                Vec3::new(-extent, -(half_length + extent), -r2),
                Vec3::new(extent, half_length + extent, r2),
            )
        }
        // === Extended primitives: box where the axes are explicit, generous cube otherwise ===
        OpCode::RoundedBox | OpCode::ChamferedCube | OpCode::Superellipsoid => {
            let he = Vec3::new(params[0], params[1], params[2]);
            let r = if opcode == OpCode::RoundedBox {
                params[3]
            } else {
                0.0
            };
            AabbPacked::new(-(he + r), he + r)
        }
        OpCode::BoxFrame => {
            let he = Vec3::new(params[0], params[1], params[2]) + params[3];
            AabbPacked::new(-he, he)
        }
        OpCode::CappedCone => cube(params[0].max(params[1]).max(params[2])),
        OpCode::CappedTorus => cube(params[0] + params[1]),
        // sdf_rounded_cylinder follows IQ's formula where the radial term is `2*radius`
        OpCode::RoundedCylinder => cube(params[0].max(params[2] + params[1])),
        OpCode::TriangularPrism => cube(params[0] + params[1]),
        OpCode::CutSphere | OpCode::CutHollowSphere => cube(params[0]),
        OpCode::DeathStar => cube(params[0] + params[1] + params[2]),
        OpCode::SolidAngle => cube(params[1]),
        OpCode::Rhombus => cube(params[0] + params[1] + params[2] + params[3]),
        OpCode::Horseshoe => cube(params[1] + params[2] + params[3] + params[4]),
        OpCode::Vesica => cube(params[0] + params[1]),
        OpCode::Heart => cube(params[0] * 2.0),
        OpCode::Tube => cube(params[0].max(params[2])),
        OpCode::Barrel => cube((params[0] + params[2]).max(params[1])),
        OpCode::Diamond => cube(params[0].max(params[1])),
        OpCode::RoundedX => cube(params[0] + params[1] + params[2]),
        OpCode::Pie => cube(params[1].max(params[2])),
        OpCode::Trapezoid => cube(params[0].max(params[1]) + params[2] + params[3]),
        OpCode::Parallelogram => cube(params[0] + params[1] + params[2].abs() + params[3]),
        OpCode::Tunnel => cube(params[0] + params[1] + params[2]),
        OpCode::UnevenCapsule => cube(params[0].max(params[1]) + params[2] + params[3]),
        OpCode::Egg => cube((params[0] + params[1]) * 2.0),
        OpCode::ArcShape => cube(params[1] + params[2] + params[3]),
        OpCode::Moon => cube(params[0].abs() + params[1] + params[2] + params[3]),
        OpCode::CrossShape => cube(params[0] + params[1] + params[2] + params[3]),
        OpCode::BlobbyCross => cube(params[0].mul_add(2.0, params[1])),
        OpCode::ParabolaSegment => cube(params[0] + params[1] + params[2]),
        OpCode::RegularPolygon => cube(params[0] + params[2]),
        OpCode::StarPolygon => cube(params[0].max(params[2]) + params[3]),
        OpCode::Stairs => cube((params[0] + params[1]).mul_add(params[2].max(1.0), params[3])),
        OpCode::Helix => cube(params[0] + params[1] + params[2].abs() + params[3]),
        OpCode::Tetrahedron => cube(params[0] * 2.0),
        OpCode::Dodecahedron
        | OpCode::Icosahedron
        | OpCode::TruncatedOctahedron
        | OpCode::TruncatedIcosahedron => cube(params[0] * 2.0),
        // === Unbounded shapes ===
        OpCode::InfiniteCylinder
        | OpCode::InfiniteCone
        | OpCode::Gyroid
        | OpCode::SchwarzP
        | OpCode::DiamondSurface
        | OpCode::Neovius
        | OpCode::Lidinoid
        | OpCode::IWP
        | OpCode::FRD
        | OpCode::FischerKochS
        | OpCode::PMY => AabbPacked::infinite(),
        // === 2D primitives extruded along Z ===
        OpCode::Circle2D => {
            let r = params[0];
            AabbPacked::new(Vec3::new(-r, -r, -params[1]), Vec3::new(r, r, params[1]))
        }
        OpCode::Rect2D => {
            let he = Vec3::new(params[0], params[1], params[2]);
            AabbPacked::new(-he, he)
        }
        OpCode::RoundedRect2D => {
            let he = Vec3::new(params[0], params[1], params[3]);
            AabbPacked::new(-he, he)
        }
        OpCode::Segment2D => {
            let r = params[0]
                .abs()
                .max(params[1].abs())
                .max(params[2].abs())
                .max(params[3].abs())
                + params[4];
            AabbPacked::new(Vec3::new(-r, -r, -params[5]), Vec3::new(r, r, params[5]))
        }
        OpCode::Annular2D => {
            let r = params[0] + params[1];
            AabbPacked::new(Vec3::new(-r, -r, -params[2]), Vec3::new(r, r, params[2]))
        }
        OpCode::Polygon2D => {
            // Vertices live in aux_data as flat [x0, y0, x1, y1, ...]
            let off = inst.aux_offset as usize;
            let flat = aux_data
                .get(off..off + inst.aux_len as usize)
                .unwrap_or(&[]);
            let mut mn = Vec2::splat(f32::INFINITY);
            let mut mx = Vec2::splat(f32::NEG_INFINITY);
            for v in flat.chunks_exact(2) {
                mn = mn.min(Vec2::new(v[0], v[1]));
                mx = mx.max(Vec2::new(v[0], v[1]));
            }
            if flat.len() < 6 {
                return AabbPacked::empty();
            }
            AabbPacked::new(
                Vec3::new(mn.x, mn.y, -params[0]),
                Vec3::new(mx.x, mx.y, params[0]),
            )
        }
        // Not primitives — unreachable by `OpKind::Primitive` dispatch, listed so the
        // match stays exhaustive when the enum grows.
        OpCode::Union
        | OpCode::Intersection
        | OpCode::Subtraction
        | OpCode::SmoothUnion
        | OpCode::SmoothIntersection
        | OpCode::SmoothSubtraction
        | OpCode::ChamferUnion
        | OpCode::ChamferIntersection
        | OpCode::ChamferSubtraction
        | OpCode::StairsUnion
        | OpCode::StairsIntersection
        | OpCode::StairsSubtraction
        | OpCode::XOR
        | OpCode::Morph
        | OpCode::ColumnsUnion
        | OpCode::ColumnsIntersection
        | OpCode::ColumnsSubtraction
        | OpCode::Pipe
        | OpCode::Engrave
        | OpCode::Groove
        | OpCode::Tongue
        | OpCode::ExpSmoothUnion
        | OpCode::ExpSmoothIntersection
        | OpCode::ExpSmoothSubtraction
        | OpCode::Translate
        | OpCode::Rotate
        | OpCode::Scale
        | OpCode::ScaleNonUniform
        | OpCode::ProjectiveTransform
        | OpCode::LatticeDeform
        | OpCode::SdfSkinning
        | OpCode::Twist
        | OpCode::Bend
        | OpCode::RepeatInfinite
        | OpCode::RepeatFinite
        | OpCode::Round
        | OpCode::Onion
        | OpCode::Elongate
        | OpCode::Noise
        | OpCode::Mirror
        | OpCode::Revolution
        | OpCode::Extrude
        | OpCode::Taper
        | OpCode::Displacement
        | OpCode::PolarRepeat
        | OpCode::SweepBezier
        | OpCode::OctantMirror
        | OpCode::Shear
        | OpCode::Animated
        | OpCode::IcosahedralSymmetry
        | OpCode::IFS
        | OpCode::HeightmapDisplacement
        | OpCode::SurfaceRoughness
        | OpCode::PopTransform
        | OpCode::End => unreachable!("primitive_aabb called with non-primitive {opcode:?}"),
    }
}

fn csg_binary_aabb(opcode: OpCode, params: &[f32; 7], a: AabbPacked, b: AabbPacked) -> AabbPacked {
    match opcode {
        // Union-shape ops that don't expand the union bound.
        OpCode::Union | OpCode::XOR | OpCode::Morph | OpCode::Pipe => a.union(&b),
        // Smooth blends expand the union AABB by their radius / k.
        OpCode::SmoothUnion => a.union(&b).expand(params[0]),
        OpCode::ChamferUnion => a.union(&b).expand(params[0]),
        OpCode::StairsUnion => a.union(&b).expand(params[0]),
        OpCode::ColumnsUnion => a.union(&b).expand(params[0]),
        OpCode::ExpSmoothUnion => a.union(&b).expand(params[0]),
        // Intersection-shape ops shrink to the geometric intersection.
        OpCode::Intersection
        | OpCode::SmoothIntersection
        | OpCode::ChamferIntersection
        | OpCode::StairsIntersection
        | OpCode::ColumnsIntersection
        | OpCode::ExpSmoothIntersection => a.intersection(&b),
        // Subtraction / carving ops keep the LHS bound (RHS only removes).
        OpCode::Subtraction
        | OpCode::SmoothSubtraction
        | OpCode::ChamferSubtraction
        | OpCode::StairsSubtraction
        | OpCode::ColumnsSubtraction
        | OpCode::ExpSmoothSubtraction
        | OpCode::Engrave
        | OpCode::Groove
        | OpCode::Tongue => a,
        _ => unreachable!("csg_binary_aabb called with non-binary {opcode:?}"),
    }
}

fn transform_or_modifier_aabb(opcode: OpCode, params: &[f32; 7], child: AabbPacked) -> AabbPacked {
    match opcode {
        // === Transforms ===
        OpCode::Translate => {
            let offset = Vec3::new(params[0], params[1], params[2]);
            child.translate(offset)
        }
        OpCode::Rotate => {
            let quat = Quat::from_xyzw(params[0], params[1], params[2], params[3]);
            child.rotate(quat)
        }
        OpCode::Scale => {
            // params[0] = 1/factor, params[1] = factor
            child.scale(params[1])
        }
        OpCode::ScaleNonUniform => {
            // params[0..3] = 1/sx, 1/sy, 1/sz — invert to recover factors.
            let sx = 1.0 / params[0];
            let sy = 1.0 / params[1];
            let sz = 1.0 / params[2];
            child.scale_nonuniform(Vec3::new(sx, sy, sz))
        }
        // === Surface-offset modifiers (radial expand) ===
        OpCode::Round => child.expand(params[0]),
        OpCode::Onion => child.expand(params[0]),
        OpCode::Displacement => child.expand(params[0].abs()),
        OpCode::Noise => child.expand(params[0]),
        // === Point-modifying modifiers with conservative expand ===
        OpCode::Twist => {
            let max_extent = child.half_size().max_element();
            child.expand(max_extent * params[0].abs() * 0.5)
        }
        OpCode::Bend => {
            let max_extent = child.half_size().max_element();
            child.expand(max_extent * params[0].abs())
        }
        // Taper is a perspective map: |p_xz| = |q_xz| · |1 − f·y| ≤ r_xz (1 + |f| r_y)
        // over the child's y range, y unchanged. (Until 2.0 this expanded by
        // `max_extent · |f|`, which undershoots for shapes larger than 1.)
        OpCode::Taper => {
            let f = params[0].abs();
            let (lo, hi) = (child.min(), child.max());
            let reach = |a: f32, b: f32| a.abs().max(b.abs());
            let r_xz = reach(lo.x, hi.x).max(reach(lo.z, hi.z));
            let r_y = reach(lo.y, hi.y);
            let e = r_xz * f.mul_add(r_y, 1.0);
            AabbPacked::new(Vec3::new(-e, lo.y, -e), Vec3::new(e, hi.y, e))
        }
        OpCode::Shear => {
            let max_shear = params[0].abs().max(params[1].abs()).max(params[2].abs());
            let half = child.half_size();
            let expand = half.length() * max_shear;
            child.expand(expand)
        }
        OpCode::Elongate => {
            let amount = Vec3::new(params[0], params[1], params[2]);
            AabbPacked::new(child.min() - amount, child.max() + amount)
        }
        // === Repeat / mirror / symmetry ===
        OpCode::RepeatInfinite => AabbPacked::infinite(),
        OpCode::RepeatFinite => {
            // params[0..3] = counts (as f32), params[3..6] = spacing
            let cx = params[0];
            let cy = params[1];
            let cz = params[2];
            let sx = params[3];
            let sy = params[4];
            let sz = params[5];
            let expand = Vec3::new(cx * sx, cy * sy, cz * sz);
            AabbPacked::new(child.min() - expand, child.max() + expand)
        }
        OpCode::Mirror => {
            // params[0..3] = axis mask (non-zero → mirrored). Match the BVH
            // compiler's Mirror { child, axes } branch.
            let ax = params[0];
            let ay = params[1];
            let az = params[2];
            let cmin = child.min();
            let cmax = child.max();
            let ex = cmax.x.abs().max(cmin.x.abs());
            let ey = cmax.y.abs().max(cmin.y.abs());
            let ez = cmax.z.abs().max(cmin.z.abs());
            AabbPacked::new(
                Vec3::new(
                    if ax != 0.0 { -ex } else { cmin.x },
                    if ay != 0.0 { -ey } else { cmin.y },
                    if az != 0.0 { -ez } else { cmin.z },
                ),
                Vec3::new(
                    if ax != 0.0 { ex } else { cmax.x },
                    if ay != 0.0 { ey } else { cmax.y },
                    if az != 0.0 { ez } else { cmax.z },
                ),
            )
        }
        OpCode::PolarRepeat => {
            let half = child.half_size();
            let center = child.center();
            let max_r = half.x.max(half.z) + center.x.abs().max(center.z.abs());
            AabbPacked::new(
                Vec3::new(-max_r, child.min().y, -max_r),
                Vec3::new(max_r, child.max().y, max_r),
            )
        }
        // === 2D → 3D lifts ===
        OpCode::Revolution => {
            let offset = params[0];
            let max_r = child.max().x.abs().max(child.min().x.abs()) + offset.abs();
            AabbPacked::new(
                Vec3::new(-max_r, child.min().y, -max_r),
                Vec3::new(max_r, child.max().y, max_r),
            )
        }
        OpCode::Extrude => {
            let hh = params[0];
            AabbPacked::new(
                Vec3::new(child.min().x, child.min().y, -hh),
                Vec3::new(child.max().x, child.max().y, hh),
            )
        }
        OpCode::SweepBezier => {
            // params[0..6] = p0.x, p0.z, p1.x, p1.z, p2.x, p2.z
            let bmin_x = params[0].min(params[2]).min(params[4]);
            let bmax_x = params[0].max(params[2]).max(params[4]);
            let bmin_z = params[1].min(params[3]).min(params[5]);
            let bmax_z = params[1].max(params[3]).max(params[5]);
            let max_perp = child.max().x.abs().max(child.min().x.abs());
            AabbPacked::new(
                Vec3::new(bmin_x - max_perp, child.min().y, bmin_z - max_perp),
                Vec3::new(bmax_x + max_perp, child.max().y, bmax_z + max_perp),
            )
        }
        // === Symmetry folds: result is symmetric in every axis / permutation ===
        OpCode::OctantMirror | OpCode::IcosahedralSymmetry => {
            let cmin = child.min();
            let cmax = child.max();
            let m = cmax
                .x
                .abs()
                .max(cmin.x.abs())
                .max(cmax.y.abs())
                .max(cmin.y.abs())
                .max(cmax.z.abs())
                .max(cmin.z.abs());
            // Icosahedral fold is a composition of reflections (norm-preserving):
            // bound by the sphere of the farthest corner.
            let r = if opcode == OpCode::IcosahedralSymmetry {
                m * 3f32.sqrt()
            } else {
                m
            };
            AabbPacked::new(Vec3::splat(-r), Vec3::splat(r))
        }
        // === Surface displacement: radial expand by amplitude ===
        OpCode::HeightmapDisplacement => child.expand(params[0].abs()),
        OpCode::SurfaceRoughness => child.expand(params[1].abs()),
        // === Transparent ===
        OpCode::Animated => child,
        // === Unbounded deformations (control points / matrices live in aux_data) ===
        OpCode::ProjectiveTransform | OpCode::LatticeDeform | OpCode::SdfSkinning | OpCode::IFS => {
            AabbPacked::infinite()
        }
        _ => unreachable!("transform_or_modifier_aabb called with non-prefix {opcode:?}"),
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::compiled::CompiledSdfBvh;
    use crate::types::SdfNode;

    fn build_two_sphere_union() -> (SdfNode, CompiledSdfBvh) {
        let a = SdfNode::sphere(1.0);
        let b = SdfNode::sphere(0.5).translate(3.0, 0.0, 0.0);
        let scene = a.union(b);
        let bvh = CompiledSdfBvh::compile(&scene);
        (scene, bvh)
    }

    #[test]
    fn refit_all_produces_same_aabbs_as_fresh_compile() {
        let (scene, mut bvh) = build_two_sphere_union();
        let baseline = CompiledSdfBvh::compile(&scene);
        let count = refit_all(&mut bvh).expect("refit_all must succeed");
        assert!(count > 0);
        for (a, b) in bvh.aabbs.iter().zip(baseline.aabbs.iter()) {
            assert!((a.min() - b.min()).length() < 1e-4);
            assert!((a.max() - b.max()).length() < 1e-4);
        }
        assert!((bvh.scene_aabb.min() - baseline.scene_aabb.min()).length() < 1e-4);
    }

    #[test]
    fn refit_all_reflects_param_mutation() {
        let (_, mut bvh) = build_two_sphere_union();
        // Find first Sphere and enlarge its radius directly in the bytecode.
        let sphere_idx = bvh
            .instructions
            .iter()
            .position(|i| i.opcode == OpCode::Sphere)
            .unwrap();
        bvh.instructions[sphere_idx].params[0] = 4.0;
        refit_all(&mut bvh).unwrap();
        let aabb = bvh.aabbs[sphere_idx];
        assert!((aabb.max() - Vec3::splat(4.0)).length() < 1e-4);
        assert!((aabb.min() - Vec3::splat(-4.0)).length() < 1e-4);
    }

    #[test]
    fn refit_all_rejects_malformed_bytecode() {
        // Every opcode has an AABB law since 1.9.2, so "unsupported opcode" no
        // longer exists; malformed stack shape must still fail loudly. Turning a
        // leaf into a prefix transform without its PopTransform starves the
        // following binary op.
        let (_, mut bvh) = build_two_sphere_union();
        bvh.instructions[0].opcode = OpCode::ProjectiveTransform;
        let err = refit_all(&mut bvh).expect_err("dangling prefix transform must fail refit");
        assert!(
            matches!(
                err,
                RefitError::ValueStackUnderflow { .. } | RefitError::TransformStackUnderflow { .. }
            ),
            "expected a stack-shape error, got {err:?}"
        );
    }

    #[test]
    fn refit_partial_recomputes_only_ancestor_chain() {
        let (_, mut bvh) = build_two_sphere_union();
        let baseline_count = refit_all(&mut bvh).unwrap();
        assert!(baseline_count > 0);

        let sphere_idx = bvh
            .instructions
            .iter()
            .position(|i| i.opcode == OpCode::Sphere)
            .unwrap();
        // Refit just this primitive's chain.
        let partial_count = refit_partial(&mut bvh, &[sphere_idx]).unwrap();
        assert!(partial_count > 0);
        assert!(
            partial_count < baseline_count,
            "partial refit should recompute fewer instructions than full ({partial_count} vs {baseline_count})"
        );
    }

    #[test]
    fn refit_partial_matches_refit_all_when_dirty_is_everything() {
        let (scene, mut bvh_partial) = build_two_sphere_union();
        let mut bvh_full = CompiledSdfBvh::compile(&scene);
        let all_indices: Vec<usize> = (0..bvh_partial.instructions.len()).collect();
        refit_partial(&mut bvh_partial, &all_indices).unwrap();
        refit_all(&mut bvh_full).unwrap();
        for (a, b) in bvh_partial.aabbs.iter().zip(bvh_full.aabbs.iter()) {
            assert!((a.min() - b.min()).length() < 1e-4);
            assert!((a.max() - b.max()).length() < 1e-4);
        }
    }

    #[test]
    fn refit_partial_rejects_out_of_bounds_dirty() {
        let (_, mut bvh) = build_two_sphere_union();
        let err = refit_partial(&mut bvh, &[9999]).expect_err("out of bounds must fail");
        assert!(matches!(err, RefitError::DirtyIndexOutOfBounds { .. }));
    }

    #[test]
    fn build_parent_indices_root_has_no_parent() {
        let (_, bvh) = build_two_sphere_union();
        let parents = build_parent_indices(&bvh).unwrap();
        // The Union instruction is the outermost — its parent is None.
        let union_idx = bvh
            .instructions
            .iter()
            .position(|i| i.opcode == OpCode::Union)
            .unwrap();
        assert_eq!(parents[union_idx], None);
    }

    #[test]
    fn build_parent_indices_child_points_to_parent_op() {
        let scene = SdfNode::sphere(1.0).union(SdfNode::sphere(0.5));
        let bvh = CompiledSdfBvh::compile(&scene);
        let parents = build_parent_indices(&bvh).unwrap();
        let union_idx = bvh
            .instructions
            .iter()
            .position(|i| i.opcode == OpCode::Union)
            .unwrap();
        let first_sphere = bvh
            .instructions
            .iter()
            .position(|i| i.opcode == OpCode::Sphere)
            .unwrap();
        assert_eq!(parents[first_sphere], Some(union_idx as u32));
    }

    // ── P3 opcode coverage smoke tests ──

    fn compile_and_refit(scene: SdfNode) -> Result<CompiledSdfBvh, RefitError> {
        let mut bvh = CompiledSdfBvh::compile(&scene);
        refit_all(&mut bvh)?;
        Ok(bvh)
    }

    #[test]
    fn refit_supports_twist_modifier() {
        let scene = SdfNode::sphere(1.0).twist(0.5);
        let bvh = compile_and_refit(scene).expect("Twist refit must succeed");
        assert!(bvh.scene_aabb.is_valid());
    }

    #[test]
    fn refit_supports_bend_modifier() {
        let scene = SdfNode::box3d(1.0, 1.0, 1.0).bend(0.3);
        let bvh = compile_and_refit(scene).expect("Bend refit must succeed");
        assert!(bvh.scene_aabb.is_valid());
    }

    #[test]
    fn refit_supports_repeat_finite_modifier() {
        let scene = SdfNode::sphere(0.5).repeat_finite([2, 2, 2], Vec3::splat(1.5));
        let bvh = compile_and_refit(scene).expect("RepeatFinite refit must succeed");
        assert!(bvh.scene_aabb.is_valid());
        assert!(bvh.scene_aabb.half_size().max_element() > 0.5);
    }

    #[test]
    fn refit_supports_repeat_infinite_modifier() {
        let scene = SdfNode::sphere(0.5).repeat_infinite(2.0, 2.0, 2.0);
        let bvh = compile_and_refit(scene).expect("RepeatInfinite refit must succeed");
        assert_eq!(
            bvh.scene_aabb.min().x,
            f32::MIN,
            "RepeatInfinite must yield an infinite scene AABB"
        );
    }

    #[test]
    fn refit_supports_onion_and_displacement_modifiers() {
        let scene = SdfNode::sphere(1.0).onion(0.1);
        let bvh = compile_and_refit(scene).expect("Onion refit must succeed");
        assert!(bvh.scene_aabb.half_size().max_element() >= 1.1);

        let scene = SdfNode::sphere(1.0).displacement(0.2);
        let bvh = compile_and_refit(scene).expect("Displacement refit must succeed");
        assert!(bvh.scene_aabb.half_size().max_element() >= 1.0);
    }

    #[test]
    fn refit_supports_elongate_modifier() {
        let scene = SdfNode::sphere(0.5).elongate(1.0, 0.0, 0.0);
        let bvh = compile_and_refit(scene).expect("Elongate refit must succeed");
        assert!(bvh.scene_aabb.max().x >= 1.5);
    }

    #[test]
    fn refit_supports_mirror_modifier() {
        let scene = SdfNode::sphere(0.5)
            .translate(2.0, 0.0, 0.0)
            .mirror(true, false, false);
        let bvh = compile_and_refit(scene).expect("Mirror refit must succeed");
        assert!(bvh.scene_aabb.is_valid());
    }

    #[test]
    fn refit_supports_extrude_and_revolution() {
        // Extrude / Revolution are validated smoke tests — walker must
        // terminate and produce a valid AABB. Exact bounds depend on how the
        // BVH compiler applies these opcodes to a 3D child (implementation
        // treats the child bounds as-is and rewraps in Z / X respectively).
        let scene = SdfNode::sphere(0.5).extrude(1.0);
        let bvh = compile_and_refit(scene).expect("Extrude refit must succeed");
        assert!(bvh.scene_aabb.is_valid());

        let scene = SdfNode::sphere(0.5).revolution(2.0);
        let bvh = compile_and_refit(scene).expect("Revolution refit must succeed");
        assert!(bvh.scene_aabb.max().x >= 2.0);
    }

    #[test]
    fn refit_supports_polar_repeat_modifier() {
        let scene = SdfNode::sphere(0.5)
            .translate(1.5, 0.0, 0.0)
            .polar_repeat(6);
        let bvh = compile_and_refit(scene).expect("PolarRepeat refit must succeed");
        assert!(bvh.scene_aabb.is_valid());
    }

    #[test]
    fn refit_supports_chamfer_union() {
        let a = SdfNode::sphere(1.0);
        let b = SdfNode::sphere(0.5).translate(1.5, 0.0, 0.0);
        let scene = a.chamfer_union(b, 0.2);
        let bvh = compile_and_refit(scene).expect("ChamferUnion refit must succeed");
        assert!(bvh.scene_aabb.is_valid());
    }

    #[test]
    fn refit_supports_stairs_union() {
        let a = SdfNode::sphere(1.0);
        let b = SdfNode::sphere(0.5).translate(1.5, 0.0, 0.0);
        let scene = a.stairs_union(b, 0.15, 3.0);
        let bvh = compile_and_refit(scene).expect("StairsUnion refit must succeed");
        assert!(bvh.scene_aabb.is_valid());
    }

    #[test]
    fn refit_supports_columns_pipe_engrave_variants() {
        // Sanity: three lesser-used binary variants should each refit.
        let a = SdfNode::sphere(1.0);
        let b = SdfNode::sphere(0.5).translate(1.5, 0.0, 0.0);
        let scene = a.clone().columns_union(b.clone(), 0.2, 3.0);
        compile_and_refit(scene).expect("ColumnsUnion refit must succeed");

        let scene = a.clone().pipe(b.clone(), 0.1);
        compile_and_refit(scene).expect("Pipe refit must succeed");

        let scene = a.engrave(b, 0.15);
        compile_and_refit(scene).expect("Engrave refit must succeed");
    }

    #[test]
    fn refit_supports_exp_smooth_union_intersection_subtraction() {
        let a = SdfNode::sphere(1.0);
        let b = SdfNode::sphere(0.5).translate(1.5, 0.0, 0.0);
        compile_and_refit(a.clone().exp_smooth_union(b.clone(), 0.2))
            .expect("ExpSmoothUnion refit must succeed");
        compile_and_refit(a.clone().exp_smooth_intersection(b.clone(), 0.2))
            .expect("ExpSmoothIntersection refit must succeed");
        compile_and_refit(a.exp_smooth_subtract(b, 0.2))
            .expect("ExpSmoothSubtraction refit must succeed");
    }

    #[test]
    fn refit_partial_walks_ancestor_chain_with_modifiers() {
        // Ensure partial refit still terminates correctly when the tree
        // contains a modifier chain (previously P1-only path panicked here).
        let scene = SdfNode::sphere(1.0).twist(0.5).bend(0.3);
        let mut bvh = CompiledSdfBvh::compile(&scene);
        let sphere_idx = bvh
            .instructions
            .iter()
            .position(|i| i.opcode == OpCode::Sphere)
            .unwrap();
        let count = refit_partial(&mut bvh, &[sphere_idx]).unwrap();
        // Expect: Sphere + Twist ancestor + Bend ancestor = 3 recomputes.
        assert_eq!(count, 3);
    }

    // ── P4 subtree skip tests ──

    #[test]
    fn subtree_end_populates_on_compile() {
        // Union(Sphere, Translate(...).Box) should populate a non-empty
        // subtree_end vector matching the instruction count.
        let (_, bvh) = build_two_sphere_union();
        assert_eq!(
            bvh.subtree_end.len(),
            bvh.instructions.len(),
            "subtree_end must cover every instruction"
        );
        // Translate's subtree_end should point at the matching PopTransform.
        let translate_idx = bvh
            .instructions
            .iter()
            .position(|i| i.opcode == OpCode::Translate);
        if let Some(idx) = translate_idx {
            let end = bvh.subtree_end[idx] as usize;
            assert!(end > idx, "transform subtree_end must be > its own index");
            assert_eq!(bvh.instructions[end].opcode, OpCode::PopTransform);
        }
    }

    #[test]
    fn refit_partial_skips_untouched_transform_subtree() {
        // Union(dirty_sphere, Translate.Box). Marking only the sphere dirty
        // should let the walker skip the Translate/Box/PopTransform triplet
        // wholesale — the recompute count stays low but the Translate branch
        // still needs its ancestor Union recomputed.
        let a = SdfNode::sphere(1.0);
        let b = SdfNode::box3d(0.5, 0.5, 0.5).translate(3.0, 0.0, 0.0);
        let scene = a.union(b);
        let mut bvh = CompiledSdfBvh::compile(&scene);
        let sphere_idx = bvh
            .instructions
            .iter()
            .position(|i| i.opcode == OpCode::Sphere)
            .unwrap();
        // Enlarge just the sphere, then partial-refit.
        bvh.instructions[sphere_idx].params[0] = 2.0;
        let count = refit_partial(&mut bvh, &[sphere_idx]).unwrap();
        // Expect: Sphere + Union ancestor = 2 recomputes (Translate/Box/Pop
        // are skipped). No recomputes for the box subtree.
        assert_eq!(
            count, 2,
            "only dirty leaf + Union ancestor should recompute"
        );
        let sphere_aabb = bvh.aabbs[sphere_idx];
        assert!((sphere_aabb.max().x - 2.0).abs() < 1e-4);
    }

    #[test]
    fn refit_all_matches_baseline_for_extended_opcodes() {
        // Exhaustive parity check: for a scene that exercises every P3-
        // added CSG variant, modifier and transform, refit_all(scene)
        // must produce byte-for-byte equivalent AABBs vs a fresh
        // CompiledSdfBvh::compile(scene). This is stricter than the
        // per-opcode smoke tests, which only check "valid AABB".
        let leaf = SdfNode::sphere(1.0);
        let cube = SdfNode::box3d(0.5, 0.5, 0.5).translate(2.0, 0.0, 0.0);

        let cases: Vec<(&str, SdfNode)> = vec![
            (
                "chamfer_union",
                leaf.clone().chamfer_union(cube.clone(), 0.2),
            ),
            (
                "chamfer_intersection",
                leaf.clone().chamfer_intersection(cube.clone(), 0.2),
            ),
            (
                "chamfer_subtraction",
                leaf.clone().chamfer_subtract(cube.clone(), 0.2),
            ),
            (
                "stairs_union",
                leaf.clone().stairs_union(cube.clone(), 0.15, 3.0),
            ),
            (
                "columns_union",
                leaf.clone().columns_union(cube.clone(), 0.2, 3.0),
            ),
            ("pipe", leaf.clone().pipe(cube.clone(), 0.1)),
            ("engrave", leaf.clone().engrave(cube.clone(), 0.15)),
            ("groove", leaf.clone().groove(cube.clone(), 0.1, 0.05)),
            ("tongue", leaf.clone().tongue(cube.clone(), 0.1, 0.05)),
            ("exp_smooth_union", leaf.clone().exp_smooth_union(cube, 0.2)),
            ("twist", leaf.clone().twist(0.5)),
            ("bend", leaf.clone().bend(0.3)),
            ("onion", leaf.clone().onion(0.1)),
            ("displacement", leaf.clone().displacement(0.2)),
            ("noise", leaf.clone().noise(0.1, 2.0, 42)),
            ("elongate", leaf.clone().elongate(1.0, 0.0, 0.0)),
            (
                "mirror",
                leaf.clone()
                    .translate(2.0, 0.0, 0.0)
                    .mirror(true, false, false),
            ),
            (
                "repeat_finite",
                leaf.clone().repeat_finite([2, 2, 2], Vec3::splat(1.5)),
            ),
            ("shear", leaf.clone().shear(0.1, 0.0, 0.0)),
            ("taper", leaf.clone().taper(0.3)),
            ("extrude", leaf.clone().extrude(1.0)),
            ("revolution", leaf.clone().revolution(2.0)),
            (
                "polar_repeat",
                leaf.translate(1.5, 0.0, 0.0).polar_repeat(6),
            ),
        ];

        for (name, scene) in cases {
            let baseline = CompiledSdfBvh::compile(&scene);
            let mut refit = baseline.clone();
            refit_all(&mut refit).unwrap_or_else(|e| {
                panic!("refit_all failed for {name}: {e:?}");
            });
            for (i, (a, b)) in refit.aabbs.iter().zip(baseline.aabbs.iter()).enumerate() {
                let dmin = (a.min() - b.min()).length();
                let dmax = (a.max() - b.max()).length();
                assert!(
                    dmin < 1e-3 && dmax < 1e-3,
                    "case {name}: instruction {i} AABB drift min={dmin} max={dmax} \
                     (refit min={:?} baseline min={:?})",
                    a.min(),
                    b.min(),
                );
            }
        }
    }

    #[test]
    fn refit_partial_deeply_nested_skips_intermediate_subtrees() {
        // Deep tree: Union(Union(Union(A, B), C), TransformSubtree(D))
        // where only A is dirty. Every sibling subtree (B, C, D) should be
        // skipped and the ancestor chain (Union × 3) recomputed.
        let a = SdfNode::sphere(1.0);
        let b = SdfNode::sphere(0.5).translate(3.0, 0.0, 0.0);
        let c = SdfNode::sphere(0.4).translate(0.0, 4.0, 0.0);
        let d = SdfNode::box3d(0.3, 0.3, 0.3).translate(0.0, 0.0, 5.0);
        let scene = a.union(b).union(c).union(d);

        let mut bvh_partial = CompiledSdfBvh::compile(&scene);
        let mut bvh_full = CompiledSdfBvh::compile(&scene);
        let sphere_idx = bvh_partial
            .instructions
            .iter()
            .position(|i| i.opcode == OpCode::Sphere)
            .unwrap();
        bvh_partial.instructions[sphere_idx].params[0] = 2.5;
        bvh_full.instructions[sphere_idx].params[0] = 2.5;

        let partial_count = refit_partial(&mut bvh_partial, &[sphere_idx]).unwrap();
        let full_count = refit_all(&mut bvh_full).unwrap();

        // Sphere + 3 Union ancestors == 4. Full walks every instruction
        // (Sphere ×4 + Union ×3 + Translate ×3 = 10+).
        assert_eq!(
            partial_count, 4,
            "deep partial should recompute only ancestor chain (Sphere + 3 Union), got {}",
            partial_count
        );
        assert!(
            full_count > partial_count,
            "full refit ({full_count}) must recompute more than partial ({partial_count})"
        );
        assert!(
            (bvh_partial.scene_aabb.max() - bvh_full.scene_aabb.max()).length() < 1e-4,
            "scene AABB agreement across deeply nested partial vs full"
        );
    }

    #[test]
    fn refit_partial_still_produces_correct_scene_aabb() {
        // Compare partial-with-skip vs full refit: identical results.
        let a = SdfNode::sphere(1.0);
        let b = SdfNode::box3d(0.5, 0.5, 0.5).translate(3.0, 0.0, 0.0);
        let c = SdfNode::sphere(0.7).translate(0.0, 4.0, 0.0);
        let scene = a.union(b).union(c);

        let mut bvh_partial = CompiledSdfBvh::compile(&scene);
        let mut bvh_full = CompiledSdfBvh::compile(&scene);
        // Mutate a single sphere in both to keep them in sync, then refit.
        let sphere_idx = bvh_partial
            .instructions
            .iter()
            .position(|i| i.opcode == OpCode::Sphere)
            .unwrap();
        bvh_partial.instructions[sphere_idx].params[0] = 1.5;
        bvh_full.instructions[sphere_idx].params[0] = 1.5;
        refit_partial(&mut bvh_partial, &[sphere_idx]).unwrap();
        refit_all(&mut bvh_full).unwrap();
        // Sphere AABB updated in partial version.
        assert!((bvh_partial.aabbs[sphere_idx].max().x - 1.5).abs() < 1e-4);
        // Scene AABB matches between partial (with skip) and full walk.
        assert!(
            (bvh_partial.scene_aabb.max() - bvh_full.scene_aabb.max()).length() < 1e-4,
            "scene AABB must agree"
        );
    }
}