Skip to content

SolidCraft: an open-source parametric 3D CAD application built in pure Rust. Desktop, web, and automation through MCP.

21.2 KB
Raw Blame
//! Flat, deterministic binary hierarchy with resumable constant-size build work.
use super::{Bounds, Hit, MAX_BUILD_STEP, Ray, Result, TraceError, Triangle, WorkBudget, check_cancel, component};
use crate::job::CancelToken;
use std::mem::size_of;

pub const MAX_TRIANGLES: usize = crate::job::MAX_CPU_TRIANGLES;
pub const MAX_DEPTH: u8 = 48;
pub const MAX_MEMORY_BYTES: u64 = 12 * 1024 * 1024 * 1024;
const STACK_SLOTS: usize = MAX_DEPTH as usize + 1;

/// Logical owned-buffer admission. Does not reserve the host pool or promise OS RSS.
#[derive(Clone, Copy, Debug)]
pub struct BuildLimits {
    pub max_triangles: usize,
    pub max_memory_bytes: u64,
    pub max_work: u64,
    pub max_depth: u8,
    pub leaf_size: usize,
}
impl Default for BuildLimits {
    fn default() -> Self {
        Self { max_triangles: 100_000, max_memory_bytes: 128 * 1024 * 1024, max_work: 10_000_000, max_depth: 32, leaf_size: 8 }
    }
}
impl BuildLimits {
    fn validate(self) -> Result<()> {
        if self.max_triangles == 0
            || self.max_triangles > MAX_TRIANGLES
            || self.max_memory_bytes == 0
            || self.max_memory_bytes > MAX_MEMORY_BYTES
            || self.max_work == 0
            || self.max_work > crate::job::MAX_CPU_WORK
            || self.max_depth == 0
            || self.max_depth > MAX_DEPTH
            || self.leaf_size == 0
            || self.leaf_size > 64
        {
            return Err(TraceError::InvalidInput("BVH build limits exceed supported bounds"));
        }
        Ok(())
    }
}

#[derive(Clone, Copy, Debug)]
enum Kind {
    Leaf { start: usize, end: usize },
    Branch { left: usize, right: usize },
}
#[derive(Clone, Copy, Debug)]
struct Node {
    bounds: Bounds,
    kind: Kind,
}
impl Node {
    fn pending() -> Self {
        Self { bounds: Bounds::empty(), kind: Kind::Leaf { start: 0, end: 0 } }
    }
}
#[derive(Clone, Copy, Debug)]
struct Task {
    node: usize,
    start: usize,
    end: usize,
    depth: u8,
}
#[derive(Clone, Copy, Debug)]
enum State {
    Loading(usize),
    Next,
    Bounds { task: Task, cursor: usize, bounds: Bounds, centers: Bounds },
    Partition { task: Task, cursor: usize, split: usize, axis: usize, plane: f64, bounds: Bounds },
    Done,
}

/// No partial acceleration structure escapes this builder. Each `step` operation
/// handles at most one input ordinal, bound or partition item, or one node transition.
pub struct BvhBuilder {
    triangles: Vec<Triangle>,
    order: Vec<usize>,
    nodes: Vec<Node>,
    pending: Vec<Task>,
    state: State,
    limits: BuildLimits,
    work: WorkBudget,
    admitted_bytes: u64,
}

/// Progress is work consumed, not a speculative completion percentage.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct BuildProgress {
    pub complete: bool,
    pub work_used: u64,
}

fn bytes_for(count: usize, item: usize) -> Result<u64> {
    let bytes = count.checked_mul(item).ok_or(TraceError::MemoryLimit)?;
    u64::try_from(bytes).map_err(|_| TraceError::MemoryLimit)
}

fn memory(triangles: usize, order: usize, nodes: usize, pending: usize) -> Result<u64> {
    let mut total = (size_of::<BvhBuilder>() + size_of::<Bvh>() + size_of::<[usize; STACK_SLOTS]>()) as u64;
    for amount in [
        bytes_for(triangles, size_of::<Triangle>())?,
        bytes_for(order, size_of::<usize>())?,
        bytes_for(nodes, size_of::<Node>())?,
        bytes_for(pending, size_of::<Task>())?,
    ] {
        total = total.checked_add(amount).ok_or(TraceError::MemoryLimit)?;
    }
    Ok(total)
}

impl BvhBuilder {
    /// Includes the supplied input Vec's capacity, maximum nodes, ordinal array,
    /// pending tasks and one traversal stack. No hidden full-scene sorting copy.
    pub fn required_bytes(triangle_count: usize, input_capacity: usize, limits: BuildLimits) -> Result<u64> {
        limits.validate()?;
        if triangle_count > limits.max_triangles || input_capacity < triangle_count {
            return Err(TraceError::InvalidInput("triangle count or input capacity"));
        }
        let nodes =
            if triangle_count == 0 { 0 } else { triangle_count.checked_mul(2).and_then(|n| n.checked_sub(1)).ok_or(TraceError::MemoryLimit)? };
        let amount = memory(input_capacity, triangle_count, nodes, usize::from(limits.max_depth) + 1)?;
        if amount > limits.max_memory_bytes {
            return Err(TraceError::MemoryLimit);
        }
        Ok(amount)
    }

    /// Takes ownership of already admitted primitives. Checks/reserves before
    /// building; copying/initializing one million ordinals is deferred to `step`.
    pub fn new(triangles: Vec<Triangle>, limits: BuildLimits, cancel: &CancelToken) -> Result<Self> {
        check_cancel(cancel)?;
        let n = triangles.len();
        Self::required_bytes(n, triangles.capacity(), limits)?;
        let node_capacity = if n == 0 { 0 } else { n.checked_mul(2).and_then(|v| v.checked_sub(1)).ok_or(TraceError::MemoryLimit)? };
        let mut order = Vec::new();
        order.try_reserve_exact(n).map_err(|_| TraceError::AllocationFailed)?;
        check_cancel(cancel)?;
        let mut nodes = Vec::new();
        nodes.try_reserve_exact(node_capacity).map_err(|_| TraceError::AllocationFailed)?;
        check_cancel(cancel)?;
        let mut pending = Vec::new();
        pending.try_reserve_exact(usize::from(limits.max_depth) + 1).map_err(|_| TraceError::AllocationFailed)?;
        let admitted_bytes = memory(triangles.capacity(), order.capacity(), nodes.capacity(), pending.capacity())?;
        if admitted_bytes > limits.max_memory_bytes {
            return Err(TraceError::MemoryLimit);
        }
        let state = if n == 0 {
            State::Done
        } else {
            nodes.push(Node::pending());
            pending.push(Task { node: 0, start: 0, end: n, depth: 0 });
            State::Loading(0)
        };
        check_cancel(cancel)?;
        Ok(Self { triangles, order, nodes, pending, state, limits, work: WorkBudget::new(limits.max_work)?, admitted_bytes })
    }

    pub fn admitted_bytes(&self) -> u64 {
        self.admitted_bytes
    }

    fn triangle_at(&self, ordinal: usize) -> Result<Triangle> {
        let index = *self.order.get(ordinal).ok_or(TraceError::Internal("build ordinal"))?;
        self.triangles.get(index).copied().ok_or(TraceError::Internal("build primitive"))
    }

    pub fn step(&mut self, operations: usize, cancel: &CancelToken) -> Result<BuildProgress> {
        if operations == 0 || operations > MAX_BUILD_STEP {
            return Err(TraceError::InvalidInput("build step outside 1..=MAX_BUILD_STEP"));
        }
        check_cancel(cancel)?;
        for _ in 0..operations {
            if matches!(self.state, State::Done) {
                break;
            }
            self.work.tick(cancel)?;
            self.state = match self.state {
                State::Loading(cursor) => {
                    if cursor < self.triangles.len() {
                        self.order.push(cursor);
                        State::Loading(cursor + 1)
                    } else {
                        State::Next
                    }
                }
                State::Next => match self.pending.pop() {
                    Some(task) => State::Bounds { task, cursor: task.start, bounds: Bounds::empty(), centers: Bounds::empty() },
                    None => State::Done,
                },
                State::Bounds { task, cursor, mut bounds, mut centers } => {
                    if cursor < task.end {
                        let triangle = self.triangle_at(cursor)?;
                        bounds = bounds.include(triangle.bounds());
                        centers = centers.include(Bounds::point(triangle.centroid()));
                        State::Bounds { task, cursor: cursor + 1, bounds, centers }
                    } else if task.end - task.start <= self.limits.leaf_size || task.depth >= self.limits.max_depth {
                        let node = self.nodes.get_mut(task.node).ok_or(TraceError::Internal("build leaf"))?;
                        *node = Node { bounds, kind: Kind::Leaf { start: task.start, end: task.end } };
                        State::Next
                    } else {
                        let extent = centers.max - centers.min;
                        let axis = if extent.x >= extent.y && extent.x >= extent.z {
                            0
                        } else if extent.y >= extent.z {
                            1
                        } else {
                            2
                        };
                        let plane = component(centers.min, axis) * 0.5 + component(centers.max, axis) * 0.5;
                        State::Partition { task, cursor: task.start, split: task.start, axis, plane, bounds }
                    }
                }
                State::Partition { task, cursor, mut split, axis, plane, bounds } => {
                    if cursor < task.end {
                        if component(self.triangle_at(cursor)?.centroid(), axis) < plane {
                            // `swap` indices are bounded by this private task range,
                            // but still check rather than panic if an invariant breaks.
                            let value = *self.order.get(cursor).ok_or(TraceError::Internal("partition cursor"))?;
                            let other = *self.order.get(split).ok_or(TraceError::Internal("partition split"))?;
                            *self.order.get_mut(cursor).ok_or(TraceError::Internal("partition cursor"))? = other;
                            *self.order.get_mut(split).ok_or(TraceError::Internal("partition split"))? = value;
                            split += 1;
                        }
                        State::Partition { task, cursor: cursor + 1, split, axis, plane, bounds }
                    } else {
                        // Coincident centroids still make progress, in existing input
                        // order. Never recurse or retry an empty partition forever.
                        if split == task.start || split == task.end {
                            split = task.start + (task.end - task.start) / 2;
                        }
                        let left = self.nodes.len();
                        let right = left.checked_add(1).ok_or(TraceError::Internal("node count"))?;
                        if self.nodes.capacity() - self.nodes.len() < 2 || self.pending.capacity() - self.pending.len() < 2 {
                            return Err(TraceError::Internal("reserved BVH capacity"));
                        }
                        self.nodes.push(Node::pending());
                        self.nodes.push(Node::pending());
                        let parent = self.nodes.get_mut(task.node).ok_or(TraceError::Internal("build branch"))?;
                        *parent = Node { bounds, kind: Kind::Branch { left, right } };
                        self.pending.push(Task { node: right, start: split, end: task.end, depth: task.depth + 1 });
                        self.pending.push(Task { node: left, start: task.start, end: split, depth: task.depth + 1 });
                        State::Next
                    }
                }
                State::Done => State::Done,
            };
        }
        check_cancel(cancel)?;
        Ok(BuildProgress { complete: matches!(self.state, State::Done), work_used: self.work.used() })
    }

    pub fn finish(self) -> Result<Bvh> {
        if !matches!(self.state, State::Done) {
            return Err(TraceError::BuildIncomplete);
        }
        Ok(Bvh { triangles: self.triangles, order: self.order, nodes: self.nodes })
    }
}

/// Completed owned geometry; no shared cache, host worker or device state.
pub struct Bvh {
    triangles: Vec<Triangle>,
    order: Vec<usize>,
    nodes: Vec<Node>,
}
impl Bvh {
    pub fn primitive_count(&self) -> usize {
        self.triangles.len()
    }
    pub fn node_count(&self) -> usize {
        self.nodes.len()
    }
    pub fn retained_bytes(&self) -> Result<u64> {
        // Conservatively retains the builder's fixed overhead allowance as well.
        memory(self.triangles.capacity(), self.order.capacity(), self.nodes.capacity(), 0)
    }
    pub const fn traversal_scratch_bytes() -> usize {
        size_of::<[usize; STACK_SLOTS]>()
    }

    pub fn closest_hit(&self, ray: &Ray, work: &mut WorkBudget, cancel: &CancelToken) -> Result<Option<Hit>> {
        self.trace(ray, false, work, cancel)
    }
    pub fn any_hit(&self, ray: &Ray, work: &mut WorkBudget, cancel: &CancelToken) -> Result<bool> {
        self.trace(ray, true, work, cancel).map(|hit| hit.is_some())
    }

    fn trace(&self, ray: &Ray, any: bool, work: &mut WorkBudget, cancel: &CancelToken) -> Result<Option<Hit>> {
        check_cancel(cancel)?;
        if self.nodes.is_empty() {
            return Ok(None);
        }
        let mut stack = [0_usize; STACK_SLOTS];
        let mut length = 1;
        let mut best: Option<Hit> = None;
        while length != 0 {
            work.tick(cancel)?;
            length -= 1;
            let node_index = *stack.get(length).ok_or(TraceError::Internal("traversal pop"))?;
            let node = self.nodes.get(node_index).ok_or(TraceError::Internal("traversal node"))?;
            let maximum = best.map_or(ray.max, |hit| hit.geometry.distance);
            if node.bounds.clip(ray, maximum).is_none() {
                continue;
            }
            match node.kind {
                Kind::Branch { left, right } => {
                    for child in [right, left] {
                        *stack.get_mut(length).ok_or(TraceError::Internal("bounded traversal stack"))? = child;
                        length += 1;
                    }
                }
                Kind::Leaf { start, end } => {
                    for ordinal in start..end {
                        work.tick(cancel)?;
                        let index = *self.order.get(ordinal).ok_or(TraceError::Internal("traversal ordinal"))?;
                        let triangle = self.triangles.get(index).ok_or(TraceError::Internal("traversal primitive"))?;
                        if let Some(geometry) = triangle.intersect(ray) {
                            let hit = Hit { primitive_index: index, geometry };
                            if any {
                                check_cancel(cancel)?;
                                return Ok(Some(hit));
                            }
                            if best.is_none_or(|old| {
                                geometry.distance < old.geometry.distance
                                    || (geometry.distance == old.geometry.distance && index < old.primitive_index)
                            }) {
                                best = Some(hit);
                            }
                        }
                    }
                }
            }
        }
        check_cancel(cancel)?;
        Ok(best)
    }
}
/// Resumable traversal used by image jobs. Each step visits one node or primitive.
/// The fixed stack is included in image admission; no per-ray heap allocation.
pub(crate) struct TraceCursor {
    ray: Ray,
    source_plane: Option<(std::ops::Range<usize>, [solidcore_record::Vec3; 3])>,
    any: bool,
    stack: [usize; STACK_SLOTS],
    length: usize,
    leaf: Option<(usize, usize)>,
    best: Option<Hit>,
    done: bool,
}
impl TraceCursor {
    pub(crate) fn new(ray: Ray, any: bool) -> Self {
        Self { ray, source_plane: None, any, stack: [0; STACK_SLOTS], length: 1, leaf: None, best: None, done: false }
    }
    /// Only the opt-in general-glass route uses an exact on-surface origin.
    /// Exclude its producing plane, not an epsilon slab or a parallel face.
    pub(crate) fn from_plane(ray: Ray, range: std::ops::Range<usize>, plane: [solidcore_record::Vec3; 3]) -> Self {
        let mut cursor = Self::new(ray, false);
        cursor.source_plane = Some((range, plane));
        cursor
    }
    pub(crate) fn step(&mut self, bvh: &Bvh, work: &mut WorkBudget, cancel: &CancelToken) -> Result<Option<Option<Hit>>> {
        self.step_ordered(bvh, work, cancel, |new, old| new.primitive_index < old.primitive_index)
    }
    /// Opt-in transport can choose a material ordering at an exact distance tie;
    /// ordinary visibility retains its original input-ordinal ordering.
    pub(crate) fn step_ordered(
        &mut self,
        bvh: &Bvh,
        work: &mut WorkBudget,
        cancel: &CancelToken,
        prefer: impl Fn(Hit, Hit) -> bool,
    ) -> Result<Option<Option<Hit>>> {
        work.tick(cancel)?;
        if self.done {
            return Err(TraceError::Internal("completed traversal cursor"));
        }
        if bvh.nodes.is_empty() {
            self.done = true;
            return Ok(Some(None));
        }
        if let Some((ordinal, end)) = self.leaf {
            if ordinal < end {
                self.leaf = Some((ordinal + 1, end));
                let index = *bvh.order.get(ordinal).ok_or(TraceError::Internal("cursor ordinal"))?;
                let triangle = bvh.triangles.get(index).ok_or(TraceError::Internal("cursor primitive"))?;
                if self
                    .source_plane
                    .as_ref()
                    .is_some_and(|(range, plane)| range.contains(&index) && super::glass_mesh::same_plane(*plane, triangle.vertices()))
                {
                    return Ok(None);
                }
                if let Some(geometry) = triangle.intersect(&self.ray) {
                    let hit = Hit { primitive_index: index, geometry };
                    if self.any {
                        self.done = true;
                        return Ok(Some(Some(hit)));
                    }
                    if self.best.is_none_or(|old| {
                        geometry.distance < old.geometry.distance || (geometry.distance == old.geometry.distance && prefer(hit, old))
                    }) {
                        self.best = Some(hit);
                    }
                }
                return Ok(None);
            }
            self.leaf = None;
        }
        if self.length == 0 {
            self.done = true;
            return Ok(Some(self.best));
        }
        self.length -= 1;
        let node_index = *self.stack.get(self.length).ok_or(TraceError::Internal("cursor pop"))?;
        let node = bvh.nodes.get(node_index).ok_or(TraceError::Internal("cursor node"))?;
        if node.bounds.clip(&self.ray, self.best.map_or(self.ray.max, |hit| hit.geometry.distance)).is_some() {
            match node.kind {
                Kind::Leaf { start, end } => self.leaf = Some((start, end)),
                Kind::Branch { left, right } => {
                    for child in [right, left] {
                        *self.stack.get_mut(self.length).ok_or(TraceError::Internal("cursor stack"))? = child;
                        self.length += 1;
                    }
                }
            }
        }
        Ok(None)
    }
}

/// Cooperative candidate enumeration for exact origin predicates. Query boxes
/// are conservative (an axis ray or finite segment's box); no floating ray-depth
/// ordering, nearest-hit truncation or probability is used for the certificate.
pub(super) struct PrimitiveScan {
    min: solidcore_record::Vec3,
    max: solidcore_record::Vec3,
    stack: [usize; STACK_SLOTS],
    length: usize,
    leaf: Option<(usize, usize)>,
    done: bool,
}
pub(super) enum ScanPoll {
    Pending,
    Primitive(usize),
    Done,
}
impl PrimitiveScan {
    pub(super) fn new(min: solidcore_record::Vec3, max: solidcore_record::Vec3) -> Result<Self> {
        if !min.is_finite() || !max.is_finite() || min.x > max.x || min.y > max.y || min.z > max.z {
            return Err(TraceError::InvalidInput("CPU origin scan bounds"));
        }
        Ok(Self { min, max, stack: [0; STACK_SLOTS], length: 1, leaf: None, done: false })
    }
    pub(super) fn step(&mut self, bvh: &Bvh, work: &mut WorkBudget, cancel: &CancelToken) -> Result<ScanPoll> {
        work.tick(cancel)?;
        if self.done {
            return Err(TraceError::Internal("completed CPU origin scan"));
        }
        if bvh.nodes.is_empty() {
            self.done = true;
            return Ok(ScanPoll::Done);
        }
        if let Some((at, end)) = self.leaf {
            if at < end {
                self.leaf = Some((at + 1, end));
                let index = *bvh.order.get(at).ok_or(TraceError::Internal("CPU origin scan ordinal"))?;
                return Ok(ScanPoll::Primitive(index));
            }
            self.leaf = None;
        }
        if self.length == 0 {
            self.done = true;
            return Ok(ScanPoll::Done);
        }
        self.length -= 1;
        let index = *self.stack.get(self.length).ok_or(TraceError::Internal("CPU origin scan stack"))?;
        let node = bvh.nodes.get(index).ok_or(TraceError::Internal("CPU origin scan node"))?;
        let lo = node.bounds.min();
        let hi = node.bounds.max();
        if !(hi.x < self.min.x || lo.x > self.max.x || hi.y < self.min.y || lo.y > self.max.y || hi.z < self.min.z || lo.z > self.max.z) {
            match node.kind {
                Kind::Leaf { start, end } => self.leaf = Some((start, end)),
                Kind::Branch { left, right } => {
                    for child in [right, left] {
                        *self.stack.get_mut(self.length).ok_or(TraceError::Internal("CPU origin scan bounded stack"))? = child;
                        self.length += 1;
                    }
                }
            }
        }
        Ok(ScanPoll::Pending)
    }
}