Skip to content

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

32.1 KB
Raw Blame
//! Original median-split BVH. World geometry is rebased around the camera target for f32.
#[path = "planar_patches.rs"]
mod planar_patches;
use solidcraft_geom::prelude::*;
use std::collections::HashMap;

use solidcore_record::Vec3;
use solidcraft_render::{
    ProductScene,
    job::{CancelToken, ErrorCode, JobError, Result},
    surface::{OpaqueSurface, srgb8_to_linear},
    transmission::Transmission,
};

pub(super) struct Triangle {
    pub p: [Vec3; 3],
    pub indices: [u32; 3],
    pub surface: OpaqueSurface,
    pub transmission: Option<Transmission>,
    pub medium: u32,
    pub scalar_face: bool,
}
type MediumEdge = (usize, usize, i32);
// The material header word reserves the high two bits for model lanes and wavelength sampling.
pub(super) const MATERIAL_OFFSET_MASK: u32 = 0x3fff_ffff;

pub(super) fn model_bytes_per_triangle(scene: &ProductScene) -> u64 {
    let modeled = |t: Option<Transmission>| t.is_some_and(|t| t.model().is_some());
    if scene.meshes.iter().any(|m| modeled(m.transmission) || m.faces.iter().any(|f| modeled(f.transmission))) { 16 } else { 0 }
}
pub(super) fn medium_preparation_bytes(scene: &ProductScene) -> u64 {
    // Validation consumes one body's scratch at a time. Opaque/thin-sheet bodies
    // allocate none of the weld table: do not charge their triangles for it.
    let closed = |t: Option<Transmission>| t.is_some_and(|v| v.thin_wall_thickness_mm().is_none());
    let mut total = 0u64;
    let mut largest_medium = 0u64;
    for body in &scene.meshes {
        let triangles = body.mesh.triangles.len() as u64;
        total = total.saturating_add(triangles);
        if closed(body.transmission) || body.faces.iter().any(|face| closed(face.transmission)) {
            largest_medium = largest_medium.max(triangles);
        }
    }
    // Three representatives per triangle at most. The 320 includes positions,
    // full eight-slot hash entries, control bytes and worst-case table rounding.
    let scratch = 3 * (std::mem::size_of::<MediumEdge>() + 320) + std::mem::size_of::<usize>();
    total.saturating_mul(std::mem::size_of::<Triangle>() as u64).saturating_add(largest_medium.saturating_mul(scratch as u64))
}

pub(super) fn planar_preparation_bytes_per_triangle() -> usize {
    let common = std::mem::size_of::<Triangle>() + 2 * std::mem::size_of::<Node>();
    (common + planar_patches::temporary_bytes_per_triangle()).max(common + 100 + 80 + 4)
}

impl Triangle {
    fn centre(&self, axis: usize) -> f64 {
        self.p.iter().map(|p| [p.x, p.y, p.z].get(axis).copied().unwrap_or(0.0)).sum::<f64>() / 3.0
    }
}

#[derive(Default)]
struct Node {
    lo: [f32; 3],
    hi: [f32; 3],
    first: u32,
    count: u32,
}

pub(super) struct Upload {
    pub geometry: Vec<u8>,
    pub nodes: Vec<u8>,
    pub epsilon: f32,
    pub active_glass_model: bool,
}

fn invalid(message: &str) -> JobError {
    JobError::new(ErrorCode::InvalidScene, message)
}
pub(super) fn reserved<T>(count: usize) -> Result<Vec<T>> {
    let mut v = Vec::new();
    v.try_reserve_exact(count).map_err(|_| JobError::new(ErrorCode::AllocationFailed, "path tracer allocation failed"))?;
    Ok(v)
}

#[cfg(test)]
pub(super) fn flatten(scene: &ProductScene, origin: Vec3, cancel: &CancelToken) -> Result<Upload> {
    flatten_with_media(scene, origin, cancel, false)
}
pub(super) fn flatten_with_media(scene: &ProductScene, origin: Vec3, cancel: &CancelToken, nested: bool) -> Result<Upload> {
    let model_bytes = model_bytes_per_triangle(scene) as usize;
    let material_bytes = 80 + model_bytes;
    let mut material_flags = if model_bytes > 0 { 0x80000000 } else { 0 };
    let mut active_glass_model = false;
    let transmissions =
        scene.meshes.iter().flat_map(|body| std::iter::once(body.transmission).chain(body.faces.iter().map(|face| face.transmission)));
    for model in transmissions.filter_map(|transmission| transmission.and_then(Transmission::model)) {
        active_glass_model |= !model.is_identity();
        if model.spectral() {
            material_flags |= 0x40000000;
            break;
        }
    }
    let count = scene.meshes.iter().map(|m| m.mesh.triangles.len()).sum::<usize>();
    let mut triangles = reserved(count)?;
    let vertex_count = scene.meshes.iter().map(|m| m.mesh.positions.len()).sum::<usize>();
    let mut vertices = reserved(vertex_count * 32)?;
    let mut vertex_offset = 0u32;
    let mut media_bounds = reserved::<super::media_hierarchy::Region>(solidcraft_render::job::MAX_GPU_DIELECTRICS)?;
    for (body_index, body) in scene.meshes.iter().enumerate() {
        cancel.check()?;
        let body_start = triangles.len();
        let mut authored_optical = false;
        let mut faces = reserved(body.faces.len())?;
        faces.extend(body.faces.iter());
        faces.sort_unstable_by_key(|f| f.face);
        if faces.windows(2).any(|f| f[0].face == f[1].face) {
            return Err(invalid("duplicate face appearance"));
        }
        let mesh = &body.mesh;
        if mesh.normals.len() != mesh.positions.len() || mesh.tri_face.len() != mesh.triangles.len() {
            return Err(invalid("path tracer requires normals and a face ID for every triangle"));
        }
        for (index, (position, normal)) in mesh.positions.iter().zip(&mesh.normals).enumerate() {
            if index % 1024 == 0 {
                cancel.check()?;
            }
            let position = *position - origin;
            if !position.is_finite() || [position.x, position.y, position.z].iter().any(|x| x.abs() > 1e7) {
                return Err(invalid("path geometry must be finite and within 1e7 mm of the camera target"));
            }
            let normal = solidcraft_render::surface::unit_direction(*normal).map_err(|_| invalid("invalid mesh normal"))?;
            vector(&mut vertices, position, 0.0);
            vector(&mut vertices, normal, 0.0);
        }
        for (index, indices) in mesh.triangles.iter().enumerate() {
            if index % 1024 == 0 {
                cancel.check()?;
            }
            let face = mesh.tri_face.get(index).copied().ok_or_else(|| invalid("missing triangle face"))?;
            let look = faces.binary_search_by_key(&face, |f| f.face).ok().and_then(|i| faces.get(i));
            let opacity = look.map_or(body.opacity, |f| f.opacity);
            let transmission = look.map_or(body.transmission, |f| f.transmission);
            authored_optical |= transmission.is_some();
            if opacity != 1.0 && transmission.is_none() {
                return Err(invalid("gpu-path requires explicit transmission for nonopaque preview appearances"));
            }
            let color = look.map_or(body.color, |f| f.color);
            let surface = look
                .map_or(body.surface, |f| f.surface)
                .map(Ok)
                .unwrap_or_else(|| {
                    OpaqueSurface::new(Vec3::new(srgb8_to_linear(color[0]), srgb8_to_linear(color[1]), srgb8_to_linear(color[2])), 0.0, 0.5, 1.5)
                })
                .map_err(|e| invalid(&e.to_string()))?;
            let mut p = [Vec3::ZERO; 3];
            let mut global_indices = [0u32; 3];
            for (corner, &vertex) in indices.iter().enumerate() {
                let position = *mesh.positions.get(vertex as usize).ok_or_else(|| invalid("triangle index out of bounds"))? - origin;
                if !position.is_finite() || [position.x, position.y, position.z].iter().any(|x| x.abs() > 1e7) {
                    return Err(invalid("path geometry must be finite and within 1e7 mm of the camera target"));
                }
                if let Some(v) = p.get_mut(corner) {
                    *v = position;
                }
                if let Some(v) = global_indices.get_mut(corner) {
                    *v = vertex.checked_add(vertex_offset).ok_or_else(|| invalid("vertex offset overflow"))?;
                }
            }
            if (p[1] - p[0]).cross(p[2] - p[0]).len() <= 1e-12 {
                // Preserve the historical source-degenerate pole-face skip for
                // both sheets and solids. The optical target must retain faces,
                // every retained face must survive upload, and closed targets
                // still require the complete source and uploaded shell proofs.
                continue;
            }
            if let Some(t) = transmission
                && let Some(scatter) = t.subsurface()
            {
                t.with_subsurface(scatter).map_err(|e| invalid(&e.to_string()))?;
            }
            if let Some(model) = transmission.and_then(|t| t.model()) {
                model.validate(surface.dielectric_ior()).map_err(|e| invalid(&e.to_string()))?;
                let roughness = model.roughness as f32;
                let alpha = roughness * roughness;
                if model.roughness > 0.0 && (alpha * alpha < f32::MIN_POSITIVE || !(1.0_f32 / (std::f32::consts::PI * alpha * alpha)).is_finite()) {
                    return Err(invalid("authored glass roughness is below GPU microfacet arithmetic precision"));
                }
            }
            if transmission
                .is_some_and(|t| t.model().is_some_and(|m| m.roughness > 0.0) && t.thin_wall_thickness_mm().is_some() && t.shadow_transmission())
            {
                return Err(invalid("rough thin-sheet glass requires disabled straight shadow transmission"));
            }
            if transmission.is_some() && surface.clear_coat().is_some() {
                return Err(invalid("clear coat and transmission cannot share a surface"));
            }
            if transmission.is_some() && surface.metallic() != 0.0 {
                return Err(invalid("transmission requires a nonmetallic surface"));
            }
            triangles.push(Triangle {
                p,
                indices: global_indices,
                surface,
                transmission,
                medium: body_index as u32 + 1,
                scalar_face: look.is_some(),
            });
        }
        if authored_optical && !triangles[body_start..].iter().any(|t| t.transmission.is_some()) {
            return Err(invalid("glass boundary has no nondegenerate optical triangles"));
        }
        validate_medium(&triangles[body_start..], cancel)?;
        // Prove the boundary actually sent to the shader as well as the source
        // seam topology. Rounding must not close an authored gap, collapse a
        // valid face, reverse its orientation or break its uploaded shell.
        for (index, triangle) in triangles[body_start..].iter_mut().enumerate() {
            if index % 1024 == 0 {
                cancel.check()?;
            }
            if triangle.transmission.is_some() {
                triangle.p = uploaded_optical_positions(triangle.p)?;
            }
        }
        validate_medium(&triangles[body_start..], cancel)?;
        let body_triangles = &triangles[body_start..];
        if body_triangles.iter().any(|t| t.transmission.is_some()) {
            if media_bounds.len() >= solidcraft_render::job::MAX_GPU_DIELECTRICS {
                return Err(invalid("at most 32 disjoint dielectric bodies are supported"));
            }
            let closed = body_triangles.iter().any(|t| t.transmission.is_some_and(|v| v.thin_wall_thickness_mm().is_none()));
            let mut lo = Vec3::new(f64::INFINITY, f64::INFINITY, f64::INFINITY);
            let mut hi = -lo;
            for t in body_triangles {
                for p in t.p {
                    lo = lo.min(p);
                    hi = hi.max(p);
                }
            }
            media_bounds.push(super::media_hierarchy::Region {
                lo,
                hi,
                closed,
                triangles: body_start..triangles.len(),
                medium: body_index as u32 + 1,
            });
        }
        vertex_offset = vertex_offset.checked_add(mesh.positions.len() as u32).ok_or_else(|| invalid("vertex offset overflow"))?;
    }
    let parents = super::media_hierarchy::parents(&media_bounds, &triangles, nested, cancel)?;
    let mut nodes = reserved(triangles.len().saturating_mul(2).max(1))?;
    nodes.push(Node::default());
    build(&mut triangles, 0, &mut nodes, 0, 0, cancel)?;
    let mut representatives = std::collections::BTreeMap::new();
    for (index, t) in triangles.iter().enumerate() {
        if t.transmission.is_some_and(|m| m.thin_wall_thickness_mm().is_none()) {
            representatives.entry(t.medium).or_insert(index as u32 + 1);
        }
    }
    let patches = planar_patches::ids(&triangles, cancel)?;
    let extent = nodes.first().map_or(1.0, |n| n.lo.iter().zip(n.hi).map(|(a, b)| b - a).fold(0.0f32, f32::max));
    let mut geometry = reserved(16 + triangles.len().max(1) * (100 + model_bytes) + vertices.len())?;
    let mut materials = reserved(triangles.len().max(1) * material_bytes)?;
    let vertex_word = 4 + triangles.len().max(1) * 4;
    let material_word = vertex_word + vertices.len() / 4;
    let patch_word = material_word + triangles.len().max(1) * (material_bytes / 4);
    let material_word = u32::try_from(material_word)
        .ok()
        .filter(|word| word & !MATERIAL_OFFSET_MASK == 0)
        .ok_or_else(|| invalid("material table offset exceeds its packed geometry layout"))?;
    for word in [triangles.len() as u32, vertex_word as u32, material_word | material_flags, patch_word as u32] {
        geometry.extend_from_slice(&word.to_le_bytes());
    }
    for (material, t) in triangles.into_iter().enumerate() {
        if material % 1024 == 0 {
            cancel.check()?;
        }
        for index in t.indices {
            geometry.extend_from_slice(&index.to_le_bytes());
        }
        geometry.extend_from_slice(&(material as u32).to_le_bytes());
        vector(&mut materials, t.surface.base_color(), if t.transmission.is_some() { 1.0 } else { 0.0 });
        vector(
            &mut materials,
            Vec3::new(t.surface.metallic(), t.surface.roughness(), t.surface.dielectric_ior()),
            t.transmission.and_then(|t| t.thin_wall_thickness_mm()).unwrap_or(-1.0) as f32,
        );
        vector(&mut materials, t.transmission.map_or(Vec3::ZERO, |t| t.extinction()), t.medium as f32);
        let coat = t.surface.clear_coat().map_or(Vec3::new(0.0, 0.5, 1.5), |c| Vec3::new(c.weight(), c.roughness(), c.ior()));
        vector(&mut materials, coat, if t.transmission.is_some_and(|t| t.shadow_transmission()) { 1.0 } else { 0.0 });
        let scatter = t.transmission.and_then(|m| m.subsurface());
        let parent = parents.iter().find(|(id, _)| *id == t.medium).map_or(0, |(_, id)| *id);
        let parent_triangle =
            if parent == 0 { 0 } else { *representatives.get(&parent).ok_or_else(|| invalid("missing certified parent material"))? };
        if scatter.is_some_and(|m| m.active()) {
            let scale = t.p.iter().map(|p| p.x.abs().max(p.y.abs()).max(p.z.abs())).fold(1.0, f64::max);
            if scatter.is_some_and(|m| m.scattering_per_mm.recip() < scale / 1_048_576.0) {
                return Err(invalid("subsurface mean free path falls below camera-relative GPU position precision"));
            }
        }
        vector(
            &mut materials,
            Vec3::new(
                scatter.map_or(0.0, |s| s.scattering_per_mm),
                scatter.map_or(0.0, |s| s.anisotropy),
                (u32::from(scene.meshes.get(t.medium.saturating_sub(1) as usize).is_some_and(|body| body.name.starts_with("__render_stage__/")))
                    | (u32::from(t.scalar_face) << 1)) as f64,
            ),
            parent_triangle as f32,
        );
        if model_bytes > 0 {
            let model = t.transmission.and_then(|t| t.model());
            vector(
                &mut materials,
                Vec3::new(
                    model.map_or(0.0, |m| m.roughness),
                    model.and_then(|m| m.dispersion).map_or(0.0, |d| d.abbe_number),
                    model.and_then(|m| m.thin_film).map_or(0.0, |f| f.thickness_nm),
                ),
                model.and_then(|m| m.thin_film).map_or(0.0, |f| f.ior) as f32,
            );
        }
    }
    if geometry.len() == 16 {
        geometry.resize(32, 0);
        materials.resize(material_bytes, 0);
    }
    geometry.extend_from_slice(&vertices);
    drop(vertices);
    geometry.extend_from_slice(&materials);
    drop(materials);
    if patches.is_empty() {
        geometry.extend_from_slice(&0u32.to_le_bytes());
    } else {
        for (index, patch) in patches.into_iter().enumerate() {
            if index % 1024 == 0 {
                cancel.check()?;
            }
            geometry.extend_from_slice(&patch.to_le_bytes());
        }
    }
    let mut node_bytes = reserved(nodes.len() * 32)?;
    for node in nodes {
        for x in node.lo {
            node_bytes.extend_from_slice(&x.to_le_bytes());
        }
        node_bytes.extend_from_slice(&node.first.to_le_bytes());
        for x in node.hi {
            node_bytes.extend_from_slice(&x.to_le_bytes());
        }
        node_bytes.extend_from_slice(&node.count.to_le_bytes());
    }
    Ok(Upload { geometry, nodes: node_bytes, epsilon: (extent * 1e-7).max(1e-5), active_glass_model })
}

fn uploaded_optical_positions(source: [Vec3; 3]) -> Result<[Vec3; 3]> {
    let stored = source.map(|p| Vec3::new(f64::from(p.x as f32), f64::from(p.y as f32), f64::from(p.z as f32)));
    let original_normal = (source[1] - source[0]).cross(source[2] - source[0]);
    let stored_normal = (stored[1] - stored[0]).cross(stored[2] - stored[0]);
    let [a, b, c] = stored.map(|p| [p.x as f32, p.y as f32, p.z as f32]);
    let u: [f32; 3] = std::array::from_fn(|i| b[i] - a[i]);
    let v: [f32; 3] = std::array::from_fn(|i| c[i] - a[i]);
    let shader_normal = Vec3::new(f64::from(u[1] * v[2] - u[2] * v[1]), f64::from(u[2] * v[0] - u[0] * v[2]), f64::from(u[0] * v[1] - u[1] * v[0]));
    if !stored.iter().all(|p| p.is_finite())
        || stored_normal.len() == 0.0
        || original_normal.dot(stored_normal) <= 0.0
        || !shader_normal.is_finite()
        || stored_normal.dot(shader_normal) <= 0.0
    {
        return Err(invalid("glass triangle collapses or reverses orientation at camera-relative GPU position precision"));
    }
    Ok(stored)
}

const MEDIUM_WELD_MM: f64 = 1e-6;

#[derive(Default)]
struct MediumBucket {
    representatives: [usize; 8],
    len: usize,
}

/// Only topology uses these representatives; every uploaded vertex stays unchanged.
/// Checking neighboring cells avoids rounding-boundary cracks in curved CAD seams.
struct MediumWeld {
    cells: HashMap<[i64; 3], MediumBucket>,
    positions: Vec<Vec3>,
    limit: usize,
}

impl MediumWeld {
    fn new(limit: usize) -> Result<Self> {
        let mut cells = HashMap::new();
        cells.try_reserve(limit).map_err(|_| JobError::new(ErrorCode::AllocationFailed, "glass topology allocation failed"))?;
        Ok(Self { cells, positions: reserved(limit)?, limit })
    }

    fn key(&mut self, point: Vec3) -> Result<usize> {
        let xyz = [point.x, point.y, point.z];
        // Leave room for neighboring cells and refuse saturated integer casts.
        if !xyz.into_iter().all(|v| v.is_finite() && v.abs() <= 1e9) {
            return Err(invalid("glass topology position exceeds finite coordinate bounds"));
        }
        let cell = xyz.map(|v| (v / MEDIUM_WELD_MM).floor() as i64);
        let mut found: Option<usize> = None;
        for dx in -1..=1 {
            for dy in -1..=1 {
                for dz in -1..=1 {
                    let neighbor = [cell[0] + dx, cell[1] + dy, cell[2] + dz];
                    let Some(bucket) = self.cells.get(&neighbor) else { continue };
                    for &index in bucket.representatives.iter().take(bucket.len) {
                        let other = self.positions.get(index).ok_or_else(|| invalid("missing glass topology representative"))?;
                        let delta = point - *other;
                        if delta.dot(delta) <= MEDIUM_WELD_MM * MEDIUM_WELD_MM && found.is_none_or(|old| index < old) {
                            found = Some(index);
                        }
                    }
                }
            }
        }
        if let Some(index) = found {
            return Ok(index);
        }
        if self.positions.len() >= self.limit {
            return Err(invalid("glass topology representative budget exceeded"));
        }
        let index = self.positions.len();
        let bucket = self.cells.entry(cell).or_default();
        // Split a unit cell into eight half-size cubes: points sharing one are
        // at most sqrt(3)/2 tolerances apart, so a cell has at most eight reps.
        let slot = bucket.representatives.get_mut(bucket.len).ok_or_else(|| invalid("glass topology cell budget exceeded"))?;
        *slot = index;
        bucket.len += 1;
        self.positions.push(point);
        Ok(index)
    }
}

// Volume transmission needs a consistently oriented closed two-manifold. CAD
// tessellation duplicates face-seam vertices; compare their actual Euclidean
// separation at the existing one-nanometre-in-mm tolerance, without modifying
// uploaded geometry or merging chains beyond a representative's tolerance.
fn validate_medium(triangles: &[Triangle], cancel: &CancelToken) -> Result<()> {
    let Some(first) = triangles.iter().find(|t| t.transmission.is_some_and(|v| v.thin_wall_thickness_mm().is_none())) else {
        return Ok(());
    };
    if triangles.iter().any(|t| t.transmission != first.transmission || t.surface.dielectric_ior() != first.surface.dielectric_ior()) {
        return Err(invalid("a closed glass body must use one homogeneous transmission medium; use separate bodies or thin walls"));
    }
    let vertex_count = triangles.len().checked_mul(3).ok_or_else(|| invalid("glass topology vertex count overflow"))?;
    let mut edges = reserved::<MediumEdge>(vertex_count)?;
    let mut weld = MediumWeld::new(vertex_count)?;
    let mut parents = reserved::<usize>(triangles.len())?;
    parents.extend(0..triangles.len());
    let origin = first.p[0];
    let mut six_volume = 0.0;
    for (index, triangle) in triangles.iter().enumerate() {
        if index % 1024 == 0 {
            cancel.check()?;
        }
        let keys = [weld.key(triangle.p[0])?, weld.key(triangle.p[1])?, weld.key(triangle.p[2])?];
        for (a, b) in [(0, 1), (1, 2), (2, 0)] {
            if keys[a] == keys[b] {
                return Err(invalid("glass triangle collapses at the 1e-6 mm topology tolerance"));
            }
            let ordinal = i32::try_from(index + 1).map_err(|_| invalid("too many glass triangles"))?;
            edges.push(if keys[a] < keys[b] { (keys[a], keys[b], ordinal) } else { (keys[b], keys[a], -ordinal) });
        }
        six_volume += (triangle.p[0] - origin).dot((triangle.p[1] - origin).cross(triangle.p[2] - origin));
    }
    edges.sort_unstable();
    for edge in edges.chunks(2) {
        let [a, b] = edge else {
            return Err(invalid("volume glass requires a closed mesh; use thin_wall_thickness_mm for sheets"));
        };
        if a.0 != b.0 || a.1 != b.1 || a.2.signum() + b.2.signum() != 0 {
            return Err(invalid("volume glass requires a closed, consistently outward-oriented mesh"));
        }
        let first = medium_root(&mut parents, a.2.unsigned_abs() as usize - 1)?;
        let second = medium_root(&mut parents, b.2.unsigned_abs() as usize - 1)?;
        *parents.get_mut(first).ok_or_else(|| invalid("invalid glass component"))? = second;
    }
    // Groups with four or more coincident directed edges cannot be a two-manifold.
    if edges.windows(3).any(|e| e[0].0 == e[2].0 && e[0].1 == e[2].1) {
        return Err(invalid("nonmanifold glass edge"));
    }
    let component = medium_root(&mut parents, 0)?;
    for index in 0..parents.len() {
        if index % 1024 == 0 {
            cancel.check()?;
        }
        if medium_root(&mut parents, index)? != component {
            return Err(invalid("closed dielectric body must contain exactly one connected shell"));
        }
    }
    validate_vertex_links(&mut edges, &mut parents, cancel)?;
    if six_volume <= 0.0 || !six_volume.is_finite() {
        return Err(invalid("glass mesh must enclose positive outward-oriented volume"));
    }
    cancel.check()
}

// Reuse the already prepaid edge and face-component scratch. Each matched edge
// supplies one outgoing corner at either endpoint and the adjacent face there.
// In a two-manifold each vertex's incident faces form one circular link; a
// pinched vertex has multiple links even when every edge and the shell pass.
fn validate_vertex_links(edges: &mut [MediumEdge], parents: &mut [usize], cancel: &CancelToken) -> Result<()> {
    for (index, edge) in edges.as_chunks_mut::<2>().0.iter_mut().enumerate() {
        if index % 1024 == 0 {
            cancel.check()?;
        }
        let [a, b] = edge;
        let first = *a;
        let second = *b;
        *a = (if first.2 > 0 { first.0 } else { first.1 }, second.2.unsigned_abs() as usize - 1, first.2.unsigned_abs() as i32);
        *b = (if second.2 > 0 { second.0 } else { second.1 }, first.2.unsigned_abs() as usize - 1, second.2.unsigned_abs() as i32);
    }
    edges.sort_unstable();
    let mut start = 0;
    while start < edges.len() {
        cancel.check()?;
        let vertex = edges.get(start).ok_or_else(|| invalid("missing glass vertex link"))?.0;
        let mut end = start + 1;
        while edges.get(end).is_some_and(|e| e.0 == vertex) {
            if end % 1024 == 0 {
                cancel.check()?;
            }
            end += 1;
        }
        let link = edges.get(start..end).ok_or_else(|| invalid("invalid glass vertex-link range"))?;
        for (index, edge) in link.iter().enumerate() {
            if index % 1024 == 0 {
                cancel.check()?;
            }
            let face = edge.2 as usize - 1;
            *parents.get_mut(face).ok_or_else(|| invalid("invalid glass vertex-link face"))? = face;
        }
        for (index, edge) in link.iter().enumerate() {
            if index % 1024 == 0 {
                cancel.check()?;
            }
            let first = medium_root(parents, edge.2 as usize - 1)?;
            let second = medium_root(parents, edge.1)?;
            *parents.get_mut(first).ok_or_else(|| invalid("invalid glass vertex-link component"))? = second;
        }
        let root = medium_root(parents, link.first().ok_or_else(|| invalid("empty glass vertex link"))?.2 as usize - 1)?;
        for (index, edge) in link.iter().enumerate() {
            if index % 1024 == 0 {
                cancel.check()?;
            }
            if medium_root(parents, edge.2 as usize - 1)? != root {
                return Err(invalid("closed glass vertex link must be one connected circular fan; pinched boundaries are unsupported"));
            }
        }
        start = end;
    }
    cancel.check()
}

fn medium_root(parents: &mut [usize], mut index: usize) -> Result<usize> {
    loop {
        let parent = *parents.get(index).ok_or_else(|| invalid("invalid glass component index"))?;
        if parent == index {
            return Ok(index);
        }
        let grandparent = *parents.get(parent).ok_or_else(|| invalid("invalid glass component parent"))?;
        *parents.get_mut(index).ok_or_else(|| invalid("invalid glass component index"))? = grandparent;
        index = grandparent;
    }
}

// The shader's traversal stack holds 32 nodes and needs at most depth + 1.
const MAX_BVH_DEPTH: usize = 30;
const SAH_BINS: usize = 16;
type Bounds = ([f32; 3], [f32; 3]);
const EMPTY_BOUNDS: Bounds = ([f32::INFINITY; 3], [f32::NEG_INFINITY; 3]);

fn grow(bounds: &mut Bounds, t: &Triangle) {
    for p in t.p {
        for (axis, value) in [p.x as f32, p.y as f32, p.z as f32].into_iter().enumerate() {
            bounds.0[axis] = bounds.0[axis].min(value);
            bounds.1[axis] = bounds.1[axis].max(value);
        }
    }
}

fn merge(bounds: &mut Bounds, other: &Bounds) {
    for axis in 0..3 {
        bounds.0[axis] = bounds.0[axis].min(other.0[axis]);
        bounds.1[axis] = bounds.1[axis].max(other.1[axis]);
    }
}

fn half_area(bounds: &Bounds) -> f64 {
    let [x, y, z] = [0, 1, 2].map(|axis| f64::from((bounds.1[axis] - bounds.0[axis]).max(0.0)));
    x * y + y * z + z * x
}

// Depth a median split adds below a node of `count` triangles.
fn median_levels(mut count: usize) -> usize {
    let mut levels = 0;
    while count > 4 {
        count = count.div_ceil(2);
        levels += 1;
    }
    levels
}

// Binned surface-area heuristic over triangle centres. A split is accepted only
// if a median split of its larger side still fits MAX_BVH_DEPTH, so the median
// fallback always remains available. Returns the left count after partitioning.
fn sah_split(triangles: &mut [Triangle], depth: usize) -> Option<usize> {
    let mut centre_lo = [f64::INFINITY; 3];
    let mut centre_hi = [f64::NEG_INFINITY; 3];
    for t in triangles.iter() {
        for axis in 0..3 {
            centre_lo[axis] = centre_lo[axis].min(t.centre(axis));
            centre_hi[axis] = centre_hi[axis].max(t.centre(axis));
        }
    }
    let bin = |t: &Triangle, axis: usize| {
        let scaled = (t.centre(axis) - centre_lo[axis]) / (centre_hi[axis] - centre_lo[axis]) * SAH_BINS as f64;
        (scaled as usize).min(SAH_BINS - 1)
    };
    let mut best: Option<(f64, usize, usize)> = None;
    for axis in 0..3 {
        if centre_hi[axis] - centre_lo[axis] <= 0.0 {
            continue;
        }
        let mut counts = [0usize; SAH_BINS];
        let mut boxes = [EMPTY_BOUNDS; SAH_BINS];
        for t in triangles.iter() {
            let b = bin(t, axis);
            counts[b] += 1;
            grow(&mut boxes[b], t);
        }
        let mut right_area = [0.0; SAH_BINS];
        let mut right_count = [0usize; SAH_BINS];
        let mut accumulated = EMPTY_BOUNDS;
        let mut count = 0;
        for b in (1..SAH_BINS).rev() {
            merge(&mut accumulated, &boxes[b]);
            count += counts[b];
            right_area[b] = half_area(&accumulated);
            right_count[b] = count;
        }
        accumulated = EMPTY_BOUNDS;
        count = 0;
        for b in 1..SAH_BINS {
            merge(&mut accumulated, &boxes[b - 1]);
            count += counts[b - 1];
            let right = right_count[b];
            if count == 0 || right == 0 || depth + 1 + median_levels(count.max(right)) > MAX_BVH_DEPTH {
                continue;
            }
            let cost = half_area(&accumulated) * count as f64 + right_area[b] * right as f64;
            if best.is_none_or(|(lowest, _, _)| cost < lowest) {
                best = Some((cost, axis, b));
            }
        }
    }
    let (_, axis, split) = best?;
    let mut middle = 0;
    for i in 0..triangles.len() {
        if bin(&triangles[i], axis) < split {
            triangles.swap(i, middle);
            middle += 1;
        }
    }
    Some(middle)
}

fn build(triangles: &mut [Triangle], offset: usize, nodes: &mut Vec<Node>, index: usize, depth: usize, cancel: &CancelToken) -> Result<()> {
    cancel.check()?;
    let mut bounds = EMPTY_BOUNDS;
    for t in triangles.iter() {
        grow(&mut bounds, t);
    }
    let (lo, hi) = bounds;
    let mut node = Node { lo, hi, first: offset as u32, count: triangles.len() as u32 };
    if triangles.is_empty() {
        node = Node { first: u32::MAX, ..Default::default() };
    }
    if triangles.len() > 4 {
        let middle = match sah_split(triangles, depth) {
            Some(middle) => middle,
            None => {
                let axis = (0..3).max_by(|&a, &b| (hi[a] - lo[a]).total_cmp(&(hi[b] - lo[b]))).unwrap_or(0);
                let middle = triangles.len() / 2;
                triangles.select_nth_unstable_by(middle, |a, b| a.centre(axis).total_cmp(&b.centre(axis)));
                middle
            }
        };
        let first = nodes.len();
        nodes.push(Node::default());
        nodes.push(Node::default());
        node.first = first as u32;
        node.count = 0;
        let (left, right) = triangles.split_at_mut(middle);
        build(left, offset, nodes, first, depth + 1, cancel)?;
        build(right, offset + middle, nodes, first + 1, depth + 1, cancel)?;
    }
    *nodes.get_mut(index).ok_or_else(|| invalid("missing BVH node"))? = node;
    Ok(())
}

pub(super) fn vector(bytes: &mut Vec<u8>, v: Vec3, w: f32) {
    for value in [v.x as f32, v.y as f32, v.z as f32, w] {
        bytes.extend_from_slice(&value.to_le_bytes());
    }
}

#[cfg(test)]
#[path = "scene_weld_tests.rs"]
mod weld_tests;

#[cfg(test)]
#[path = "scene_bvh_tests.rs"]
mod bvh_tests;