use std::collections::HashMap;
use std::hash::{Hash, Hasher};

use serde::{Deserialize, Serialize};

use bone_types::{
    AngleTolerance, BrepFaceId, ChordHeightTolerance, FaceLabel, FaceRole, MeshGeneration, Point3,
    Tolerance, UnitVec3,
};
use slotmap::Key;
use truck_meshalgo::prelude::{BoundedSurface, ParameterDivision2D, PolygonMesh};
use truck_meshalgo::tessellation::RobustMeshableShape;
use truck_modeling::{
    Invertible, NurbsSurface, Point3 as TruckPoint3, Surface, TOLERANCE, Vector3 as TruckVector3,
    Vector4,
};

use super::convert::{point_from_truck, try_unit_from_truck};
use super::{BrepFace, BrepSolid};

const UNIT_NORMAL_TOLERANCE: Tolerance = Tolerance::new(1.0e-9);

#[derive(Clone, Debug, PartialEq, Serialize, Deserialize)]
#[serde(deny_unknown_fields)]
pub struct FaceMesh {
    face: BrepFaceId,
    label: FaceLabel,
    positions: Vec<Point3>,
    normals: Vec<UnitVec3>,
    triangles: Vec<[u32; 3]>,
}

impl FaceMesh {
    #[must_use]
    pub fn face(&self) -> BrepFaceId {
        self.face
    }

    #[must_use]
    pub fn label(&self) -> FaceLabel {
        self.label
    }

    #[must_use]
    pub fn positions(&self) -> &[Point3] {
        &self.positions
    }

    #[must_use]
    pub fn normals(&self) -> &[UnitVec3] {
        &self.normals
    }

    #[must_use]
    pub fn triangles(&self) -> &[[u32; 3]] {
        &self.triangles
    }
}

#[derive(Clone, Debug, PartialEq, Serialize, Deserialize)]
#[serde(deny_unknown_fields)]
pub struct SolidMesh {
    faces: Vec<FaceMesh>,
    generation: MeshGeneration,
}

impl SolidMesh {
    #[must_use]
    pub fn faces(&self) -> &[FaceMesh] {
        &self.faces
    }

    #[must_use]
    pub fn generation(&self) -> MeshGeneration {
        self.generation
    }

    pub fn validate(&self, tolerance: Tolerance) -> Result<(), MeshError> {
        self.faces
            .iter()
            .try_for_each(|slab| validate_slab(slab, tolerance))
    }
}

#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
pub enum MeshError {
    #[error("face {0:?} produced no triangles")]
    EmptyFace(BrepFaceId),
    #[error("face {face:?} triangle {triangle} has an edge below tolerance")]
    DegenerateTriangle { face: BrepFaceId, triangle: usize },
    #[error("face {face:?} triangle {triangle} winds against its surface normal")]
    NonCcwTriangle { face: BrepFaceId, triangle: usize },
    #[error("face {face:?} has an edge incident to more than two triangles")]
    NonManifoldEdge { face: BrepFaceId },
    #[error("face {face:?} surface tessellation produced no polygon")]
    SurfaceTessellationFailed { face: BrepFaceId },
    #[error("face {face:?} surface emitted a normal that is not unit length")]
    InvalidSurfaceNormal { face: BrepFaceId },
    #[error("face {face:?} slab exceeds u32 vertex addressing")]
    SlabTooLarge { face: BrepFaceId },
}

pub(super) fn tessellate_solid(
    brep: &BrepSolid,
    chord: ChordHeightTolerance,
    angle: AngleTolerance,
) -> Result<SolidMesh, MeshError> {
    let tol = effective_tolerance(brep, chord, angle);
    if let Some(mesh) = tessellate_skin(brep, tol, chord, angle) {
        return Ok(mesh);
    }
    let original = brep.arena.solid();
    let meshed = original.robust_triangulation(tol);

    let face_index = brep.arena.face_index();
    let mut slabs: HashMap<BrepFaceId, FaceMesh> = brep
        .iter_faces()
        .map(|face| {
            (
                face.id(),
                FaceMesh {
                    face: face.id(),
                    label: face.label(),
                    positions: Vec::new(),
                    normals: Vec::new(),
                    triangles: Vec::new(),
                },
            )
        })
        .collect();

    original
        .boundaries()
        .iter()
        .zip(meshed.boundaries().iter())
        .flat_map(|(orig_shell, mesh_shell)| orig_shell.face_iter().zip(mesh_shell.face_iter()))
        .try_for_each(|(orig_face, mesh_face)| {
            let brep_face = *face_index
                .get(&orig_face.id())
                .unwrap_or_else(|| unreachable!("face_index covers every truck face in the arena"));
            let Some(mut polygon) = mesh_face.surface() else {
                return Err(MeshError::SurfaceTessellationFailed { face: brep_face });
            };
            if !mesh_face.orientation() {
                polygon.invert();
            }
            let slab = slabs.get_mut(&brep_face).unwrap_or_else(|| {
                unreachable!("slabs pre-filled from iter_faces over the same slotmap")
            });
            append_polygon(slab, &polygon)
        })?;

    let faces: Vec<FaceMesh> = brep
        .iter_faces()
        .map(|face| {
            slabs
                .remove(&face.id())
                .unwrap_or_else(|| unreachable!("slabs pre-filled from iter_faces"))
        })
        .collect();
    faces.iter().try_for_each(|slab| {
        if slab.triangles.is_empty() {
            Err(MeshError::EmptyFace(slab.face))
        } else {
            Ok(())
        }
    })?;
    let generation = derive_generation(&faces, chord, angle);
    Ok(SolidMesh { faces, generation })
}

fn effective_tolerance(
    brep: &BrepSolid,
    chord: ChordHeightTolerance,
    angle: AngleTolerance,
) -> f64 {
    chord
        .millimeters()
        .min(angular_chord(brep, angle))
        .max(TOLERANCE)
}

fn angular_chord(brep: &BrepSolid, angle: AngleTolerance) -> f64 {
    let radians = angle.radians();
    if !(radians.is_finite() && radians > 0.0) {
        return f64::INFINITY;
    }
    brep.edge_bounding_box().map_or(f64::INFINITY, |bbox| {
        let radius = bbox.extent().norm_mm() / 2.0;
        radius * (1.0 - (radians / 2.0).cos())
    })
}

fn append_polygon(slab: &mut FaceMesh, polygon: &PolygonMesh) -> Result<(), MeshError> {
    let mut lookup: HashMap<(usize, Option<usize>), u32> = HashMap::new();
    let positions = polygon.positions();
    let normals = polygon.normals();
    polygon.tri_faces().iter().try_for_each(|tri| {
        let [v0, v1, v2] = *tri;
        let a = append_vertex(slab, positions, normals, v0, &mut lookup)?;
        let b = append_vertex(slab, positions, normals, v1, &mut lookup)?;
        let c = append_vertex(slab, positions, normals, v2, &mut lookup)?;
        slab.triangles.push([a, b, c]);
        Ok(())
    })
}

fn append_vertex(
    slab: &mut FaceMesh,
    positions: &[truck_modeling::Point3],
    normals: &[truck_modeling::Vector3],
    v: truck_meshalgo::prelude::StandardVertex,
    lookup: &mut HashMap<(usize, Option<usize>), u32>,
) -> Result<u32, MeshError> {
    if let Some(existing) = lookup.get(&(v.pos, v.nor)) {
        return Ok(*existing);
    }
    let Some(nor_index) = v.nor else {
        return Err(MeshError::InvalidSurfaceNormal { face: slab.face });
    };
    let Some(normal) = try_unit_from_truck(normals[nor_index], UNIT_NORMAL_TOLERANCE) else {
        return Err(MeshError::InvalidSurfaceNormal { face: slab.face });
    };
    let index = u32::try_from(slab.positions.len())
        .map_err(|_| MeshError::SlabTooLarge { face: slab.face })?;
    slab.positions.push(point_from_truck(positions[v.pos]));
    slab.normals.push(normal);
    lookup.insert((v.pos, v.nor), index);
    Ok(index)
}

struct StableHasher(blake3::Hasher);

impl Hasher for StableHasher {
    fn write(&mut self, bytes: &[u8]) {
        self.0.update(bytes);
    }

    fn write_u8(&mut self, i: u8) {
        self.0.update(&i.to_le_bytes());
    }

    fn write_u16(&mut self, i: u16) {
        self.0.update(&i.to_le_bytes());
    }

    fn write_u32(&mut self, i: u32) {
        self.0.update(&i.to_le_bytes());
    }

    fn write_u64(&mut self, i: u64) {
        self.0.update(&i.to_le_bytes());
    }

    fn write_u128(&mut self, i: u128) {
        self.0.update(&i.to_le_bytes());
    }

    fn write_usize(&mut self, i: usize) {
        let Ok(widened) = u64::try_from(i) else {
            unreachable!("usize exceeds u64 only above 64-bit platforms");
        };
        self.0.update(&widened.to_le_bytes());
    }

    fn write_i8(&mut self, i: i8) {
        self.0.update(&i.to_le_bytes());
    }

    fn write_i16(&mut self, i: i16) {
        self.0.update(&i.to_le_bytes());
    }

    fn write_i32(&mut self, i: i32) {
        self.0.update(&i.to_le_bytes());
    }

    fn write_i64(&mut self, i: i64) {
        self.0.update(&i.to_le_bytes());
    }

    fn write_i128(&mut self, i: i128) {
        self.0.update(&i.to_le_bytes());
    }

    fn write_isize(&mut self, i: isize) {
        let Ok(widened) = i64::try_from(i) else {
            unreachable!("isize exceeds i64 only above 64-bit platforms");
        };
        self.0.update(&widened.to_le_bytes());
    }

    fn finish(&self) -> u64 {
        let digest = self.0.finalize();
        let Ok(head) = <[u8; 8]>::try_from(&digest.as_bytes()[..8]) else {
            unreachable!("blake3 digest is 32 bytes");
        };
        u64::from_le_bytes(head)
    }
}

fn derive_generation(
    faces: &[FaceMesh],
    chord: ChordHeightTolerance,
    angle: AngleTolerance,
) -> MeshGeneration {
    let mut hasher = StableHasher(blake3::Hasher::new());
    chord.millimeters().to_bits().hash(&mut hasher);
    angle.radians().to_bits().hash(&mut hasher);
    faces.iter().for_each(|slab| {
        slab.face.data().as_ffi().hash(&mut hasher);
        slab.label.hash(&mut hasher);
        slab.positions.iter().for_each(|p| {
            let (x, y, z) = p.coords_mm();
            x.to_bits().hash(&mut hasher);
            y.to_bits().hash(&mut hasher);
            z.to_bits().hash(&mut hasher);
        });
        slab.normals.iter().for_each(|n| {
            let (x, y, z) = n.components();
            x.to_bits().hash(&mut hasher);
            y.to_bits().hash(&mut hasher);
            z.to_bits().hash(&mut hasher);
        });
        slab.triangles.iter().for_each(|tri| tri.hash(&mut hasher));
    });
    MeshGeneration::new(hasher.finish())
}

fn validate_slab(slab: &FaceMesh, tolerance: Tolerance) -> Result<(), MeshError> {
    slab.triangles
        .iter()
        .enumerate()
        .try_for_each(|(triangle_index, indices)| {
            let p = corners(slab, *indices);
            check_non_degenerate(slab.face, triangle_index, p, tolerance)?;
            check_ccw_winding(slab, triangle_index, *indices, p)
        })?;
    check_manifold(slab)
}

type Corners = [Point3; 3];

fn corners(slab: &FaceMesh, indices: [u32; 3]) -> Corners {
    indices.map(|i| slab.positions[i as usize])
}

fn check_non_degenerate(
    face: BrepFaceId,
    triangle: usize,
    corners: Corners,
    tolerance: Tolerance,
) -> Result<(), MeshError> {
    let min_sq = tolerance.value() * tolerance.value();
    let edge_sq = |a: usize, b: usize| {
        let d = corners[b] - corners[a];
        d.norm_squared_mm2()
    };
    if edge_sq(0, 1) <= min_sq || edge_sq(1, 2) <= min_sq || edge_sq(2, 0) <= min_sq {
        Err(MeshError::DegenerateTriangle { face, triangle })
    } else {
        Ok(())
    }
}

fn check_ccw_winding(
    slab: &FaceMesh,
    triangle: usize,
    indices: [u32; 3],
    corners: Corners,
) -> Result<(), MeshError> {
    let edge_a = corners[1] - corners[0];
    let edge_b = corners[2] - corners[0];
    let cross = edge_a.cross(edge_b);
    let normal_sum = indices.iter().fold([0.0_f64; 3], |acc, idx| {
        let (nx, ny, nz) = slab.normals[*idx as usize].components();
        [acc[0] + nx, acc[1] + ny, acc[2] + nz]
    });
    let (cx, cy, cz) = cross.coords_mm();
    let dot = cx * normal_sum[0] + cy * normal_sum[1] + cz * normal_sum[2];
    if dot > 0.0 {
        Ok(())
    } else {
        Err(MeshError::NonCcwTriangle {
            face: slab.face,
            triangle,
        })
    }
}

fn check_manifold(slab: &FaceMesh) -> Result<(), MeshError> {
    let counts = slab
        .triangles
        .iter()
        .flat_map(|tri| {
            [
                edge_key(tri[0], tri[1]),
                edge_key(tri[1], tri[2]),
                edge_key(tri[2], tri[0]),
            ]
        })
        .fold(HashMap::<(u32, u32), u32>::new(), |mut counts, key| {
            *counts.entry(key).or_insert(0) += 1;
            counts
        });
    if counts.values().any(|count| *count > 2) {
        Err(MeshError::NonManifoldEdge { face: slab.face })
    } else {
        Ok(())
    }
}

fn edge_key(a: u32, b: u32) -> (u32, u32) {
    if a < b { (a, b) } else { (b, a) }
}

const SKIN_MERGE_TOLERANCE_MM: f64 = 1.0e-6;
const SKIN_MESH_TOLERANCE: Tolerance = Tolerance::new(1.0e-9);

struct SkinSide {
    face: BrepFaceId,
    label: FaceLabel,
    surface: NurbsSurface<Vector4>,
    orientation: bool,
}

struct SkinCap {
    face: BrepFaceId,
    label: FaceLabel,
    normal: TruckVector3,
    orientation: bool,
}

fn tessellate_skin(
    brep: &BrepSolid,
    tol: f64,
    chord: ChordHeightTolerance,
    angle: AngleTolerance,
) -> Option<SolidMesh> {
    let (sides, start_cap, end_cap) = classify_skin(brep)?;
    let divided: Vec<(SkinSide, Vec<f64>, Vec<f64>)> = sides
        .into_iter()
        .map(|side| {
            let (section_div, along_div) = side
                .surface
                .parameter_division(side.surface.range_tuple(), tol);
            (side, section_div, along_div)
        })
        .collect();
    let path_division =
        merge_divisions(divided.iter().map(|(_, _, along_div)| along_div.as_slice()))?;
    let (&v_start, &v_end) = (path_division.first()?, path_division.last()?);

    let section_row = |v: f64| -> Vec<Vec<TruckPoint3>> {
        divided
            .iter()
            .map(|(side, section_div, _)| {
                section_div
                    .iter()
                    .map(|&u| side.surface.subs(u, v))
                    .collect()
            })
            .collect()
    };
    let start_rows = section_row(v_start);
    let end_rows = section_row(v_end);

    let mut slabs: Vec<FaceMesh> = divided
        .iter()
        .map(|(side, section_div, _)| build_side_slab(side, section_div, &path_division))
        .collect::<Option<_>>()?;
    slabs.push(build_cap_slab(&start_cap, &start_rows)?);
    slabs.push(build_cap_slab(&end_cap, &end_rows)?);

    let ordered = order_slabs(brep, slabs)?;
    if !is_watertight(&ordered) {
        return None;
    }
    let generation = derive_generation(&ordered, chord, angle);
    Some(SolidMesh {
        faces: ordered,
        generation,
    })
}

fn classify_skin(brep: &BrepSolid) -> Option<(Vec<SkinSide>, SkinCap, SkinCap)> {
    let (sides, start_cap, end_cap) = brep.iter_faces().try_fold(
        (Vec::new(), None, None),
        |(mut sides, start_cap, end_cap), face| {
            let truck = brep.arena.truck_face(face.id())?;
            match face.label().role {
                FaceRole::Side { .. } => {
                    let Surface::NurbsSurface(surface) = truck.surface() else {
                        return None;
                    };
                    sides.push(SkinSide {
                        face: face.id(),
                        label: face.label(),
                        surface,
                        orientation: truck.orientation(),
                    });
                    Some((sides, start_cap, end_cap))
                }
                FaceRole::StartCap if start_cap.is_none() => {
                    Some((sides, Some(planar_cap(face, truck)?), end_cap))
                }
                FaceRole::EndCap if end_cap.is_none() => {
                    Some((sides, start_cap, Some(planar_cap(face, truck)?)))
                }
                FaceRole::StartCap | FaceRole::EndCap | FaceRole::Imported { .. } => None,
            }
        },
    )?;
    (sides.len() >= 3).then_some((sides, start_cap?, end_cap?))
}

fn planar_cap(face: &BrepFace, truck: &truck_modeling::Face) -> Option<SkinCap> {
    let Surface::Plane(plane) = truck.surface() else {
        return None;
    };
    Some(SkinCap {
        face: face.id(),
        label: face.label(),
        normal: plane.normal(),
        orientation: truck.orientation(),
    })
}

fn merge_divisions<'a>(rows: impl Iterator<Item = &'a [f64]>) -> Option<Vec<f64>> {
    let mut all: Vec<f64> = rows.flat_map(|row| row.iter().copied()).collect();
    if all.len() < 2 {
        return None;
    }
    all.sort_by(f64::total_cmp);
    let span = all.last()? - all.first()?;
    let eps = (span * 1.0e-7).max(1.0e-12);
    let merged: Vec<f64> = all.into_iter().fold(Vec::new(), |mut acc, value| {
        match acc.last() {
            Some(&prev) if (value - prev).abs() <= eps => {}
            _ => acc.push(value),
        }
        acc
    });
    (merged.len() >= 2).then_some(merged)
}

fn build_side_slab(side: &SkinSide, section_div: &[f64], along_div: &[f64]) -> Option<FaceMesh> {
    let nu = section_div.len();
    let nv = along_div.len();
    if nu < 2 || nv < 2 {
        return None;
    }
    let positions: Vec<Point3> = section_div
        .iter()
        .flat_map(|&u| {
            along_div
                .iter()
                .map(move |&v| point_from_truck(side.surface.subs(u, v)))
        })
        .collect();
    let index = |i: usize, j: usize| i * nv + j;
    let cells = (1..nu).flat_map(|i| (1..nv).map(move |j| (i, j)));
    let triangles: Vec<[usize; 3]> = cells
        .flat_map(|(i, j)| {
            let a = index(i - 1, j - 1);
            let b = index(i, j - 1);
            let c = index(i, j);
            let d = index(i - 1, j);
            if side.orientation {
                [[a, b, c], [a, c, d]]
            } else {
                [[a, c, b], [a, d, c]]
            }
        })
        .collect();
    let normals = facet_averaged_normals(&positions, &triangles)?;
    let triangles: Vec<[u32; 3]> = triangles
        .into_iter()
        .map(|tri| {
            Some([
                u32::try_from(tri[0]).ok()?,
                u32::try_from(tri[1]).ok()?,
                u32::try_from(tri[2]).ok()?,
            ])
        })
        .collect::<Option<_>>()?;
    Some(FaceMesh {
        face: side.face,
        label: side.label,
        positions,
        normals,
        triangles,
    })
}

fn facet_averaged_normals(positions: &[Point3], triangles: &[[usize; 3]]) -> Option<Vec<UnitVec3>> {
    let accum = triangles.iter().fold(
        vec![[0.0_f64; 3]; positions.len()],
        |mut acc, &[a, b, c]| {
            let [nx, ny, nz] = facet_normal(positions[a], positions[b], positions[c]);
            [a, b, c].into_iter().for_each(|vertex| {
                acc[vertex][0] += nx;
                acc[vertex][1] += ny;
                acc[vertex][2] += nz;
            });
            acc
        },
    );
    accum
        .into_iter()
        .map(|[x, y, z]| try_unit_from_truck(TruckVector3::new(x, y, z), UNIT_NORMAL_TOLERANCE))
        .collect()
}

fn facet_normal(a: Point3, b: Point3, c: Point3) -> [f64; 3] {
    let (ax, ay, az) = a.coords_mm();
    let (bx, by, bz) = b.coords_mm();
    let (cx, cy, cz) = c.coords_mm();
    let (ux, uy, uz) = (bx - ax, by - ay, bz - az);
    let (vx, vy, vz) = (cx - ax, cy - ay, cz - az);
    let normal = [uy * vz - uz * vy, uz * vx - ux * vz, ux * vy - uy * vx];
    let len = (normal[0] * normal[0] + normal[1] * normal[1] + normal[2] * normal[2]).sqrt();
    if len > 0.0 {
        [normal[0] / len, normal[1] / len, normal[2] / len]
    } else {
        [0.0, 0.0, 0.0]
    }
}

fn build_cap_slab(cap: &SkinCap, rows: &[Vec<TruckPoint3>]) -> Option<FaceMesh> {
    let ring = assemble_ring(rows)?;
    let outward = if cap.orientation {
        cap.normal
    } else {
        -cap.normal
    };
    let normal = try_unit_from_truck(outward, UNIT_NORMAL_TOLERANCE)?;
    let (e1, e2) = plane_basis(outward)?;
    let projected: Vec<(f64, f64)> = ring
        .iter()
        .map(|p| {
            (
                p.x * e1.x + p.y * e1.y + p.z * e1.z,
                p.x * e2.x + p.y * e2.y + p.z * e2.z,
            )
        })
        .collect();
    let triangles: Vec<[u32; 3]> = ear_clip(&projected)?
        .into_iter()
        .map(|[a, b, c]| {
            Some([
                u32::try_from(a).ok()?,
                u32::try_from(b).ok()?,
                u32::try_from(c).ok()?,
            ])
        })
        .collect::<Option<_>>()?;
    let positions: Vec<Point3> = ring.iter().map(|p| point_from_truck(*p)).collect();
    let normals = vec![normal; positions.len()];
    Some(FaceMesh {
        face: cap.face,
        label: cap.label,
        positions,
        normals,
        triangles,
    })
}

fn assemble_ring(rows: &[Vec<TruckPoint3>]) -> Option<Vec<TruckPoint3>> {
    if rows.iter().any(|row| row.len() < 2) {
        return None;
    }
    let mut used = vec![false; rows.len()];
    used[0] = true;
    let mut ring: Vec<TruckPoint3> = rows[0].clone();
    while !used.iter().all(|flag| *flag) {
        let tail = *ring.last()?;
        let (matched, extension) = rows.iter().enumerate().find_map(|(k, row)| {
            if used[k] {
                return None;
            }
            let head = row.first()?;
            let foot = row.last()?;
            if near_point(*head, tail) {
                Some((k, row.iter().skip(1).copied().collect::<Vec<_>>()))
            } else if near_point(*foot, tail) {
                Some((k, row.iter().rev().skip(1).copied().collect::<Vec<_>>()))
            } else {
                None
            }
        })?;
        used[matched] = true;
        ring.extend(extension);
    }
    if ring.len() >= 2 && near_point(*ring.first()?, *ring.last()?) {
        ring.pop();
    }
    (ring.len() >= 3).then_some(ring)
}

fn ear_clip(poly: &[(f64, f64)]) -> Option<Vec<[usize; 3]>> {
    let n = poly.len();
    if n < 3 {
        return None;
    }
    let mut remaining: Vec<usize> = if polygon_area(poly) >= 0.0 {
        (0..n).collect()
    } else {
        (0..n).rev().collect()
    };
    let mut triangles = Vec::with_capacity(n - 2);
    while remaining.len() > 3 {
        let m = remaining.len();
        let ear = (0..m).find(|&k| {
            is_ear(
                poly,
                &remaining,
                remaining[(k + m - 1) % m],
                remaining[k],
                remaining[(k + 1) % m],
            )
        })?;
        triangles.push([
            remaining[(ear + m - 1) % m],
            remaining[ear],
            remaining[(ear + 1) % m],
        ]);
        remaining.remove(ear);
    }
    triangles.push([remaining[0], remaining[1], remaining[2]]);
    Some(triangles)
}

fn polygon_area(poly: &[(f64, f64)]) -> f64 {
    poly.iter().enumerate().fold(0.0, |acc, (i, &(x0, y0))| {
        let (x1, y1) = poly[(i + 1) % poly.len()];
        acc + (x0 * y1 - x1 * y0)
    }) / 2.0
}

fn is_ear(poly: &[(f64, f64)], remaining: &[usize], i0: usize, i1: usize, i2: usize) -> bool {
    let a = poly[i0];
    let b = poly[i1];
    let c = poly[i2];
    let convex = (b.0 - a.0) * (c.1 - a.1) - (b.1 - a.1) * (c.0 - a.0);
    if convex <= 0.0 {
        return false;
    }
    !remaining
        .iter()
        .any(|&idx| idx != i0 && idx != i1 && idx != i2 && point_in_triangle(poly[idx], a, b, c))
}

fn point_in_triangle(p: (f64, f64), a: (f64, f64), b: (f64, f64), c: (f64, f64)) -> bool {
    let cross = |u: (f64, f64), v: (f64, f64)| u.0 * v.1 - u.1 * v.0;
    let s1 = cross((b.0 - a.0, b.1 - a.1), (p.0 - a.0, p.1 - a.1));
    let s2 = cross((c.0 - b.0, c.1 - b.1), (p.0 - b.0, p.1 - b.1));
    let s3 = cross((a.0 - c.0, a.1 - c.1), (p.0 - c.0, p.1 - c.1));
    (s1 >= 0.0 && s2 >= 0.0 && s3 >= 0.0) || (s1 <= 0.0 && s2 <= 0.0 && s3 <= 0.0)
}

fn plane_basis(normal: TruckVector3) -> Option<(TruckVector3, TruckVector3)> {
    let len = (normal.x * normal.x + normal.y * normal.y + normal.z * normal.z).sqrt();
    if len < 1.0e-12 {
        return None;
    }
    let n = normal * (1.0 / len);
    let helper = if n.x.abs() < 0.9 {
        TruckVector3::new(1.0, 0.0, 0.0)
    } else {
        TruckVector3::new(0.0, 1.0, 0.0)
    };
    let raw = cross3(n, helper);
    let raw_len = (raw.x * raw.x + raw.y * raw.y + raw.z * raw.z).sqrt();
    if raw_len < 1.0e-12 {
        return None;
    }
    let e1 = raw * (1.0 / raw_len);
    Some((e1, cross3(n, e1)))
}

fn cross3(a: TruckVector3, b: TruckVector3) -> TruckVector3 {
    TruckVector3::new(
        a.y * b.z - a.z * b.y,
        a.z * b.x - a.x * b.z,
        a.x * b.y - a.y * b.x,
    )
}

fn near_point(a: TruckPoint3, b: TruckPoint3) -> bool {
    let (dx, dy, dz) = (a.x - b.x, a.y - b.y, a.z - b.z);
    (dx * dx + dy * dy + dz * dz).sqrt() <= SKIN_MERGE_TOLERANCE_MM
}

fn order_slabs(brep: &BrepSolid, slabs: Vec<FaceMesh>) -> Option<Vec<FaceMesh>> {
    let mut by_id: HashMap<BrepFaceId, FaceMesh> =
        slabs.into_iter().map(|slab| (slab.face, slab)).collect();
    brep.iter_faces()
        .map(|face| by_id.remove(&face.id()))
        .collect()
}

fn is_watertight(faces: &[FaceMesh]) -> bool {
    if faces
        .iter()
        .any(|slab| validate_slab(slab, SKIN_MESH_TOLERANCE).is_err())
    {
        return false;
    }
    let key = |point: &Point3| {
        let (x, y, z) = point.coords_mm();
        (x.to_bits(), y.to_bits(), z.to_bits())
    };
    let mut counts: HashMap<[(u64, u64, u64); 2], u32> = HashMap::new();
    faces.iter().for_each(|slab| {
        let positions = slab.positions();
        slab.triangles().iter().for_each(|tri| {
            [(tri[0], tri[1]), (tri[1], tri[2]), (tri[2], tri[0])]
                .into_iter()
                .for_each(|(a, b)| {
                    let ka = key(&positions[a as usize]);
                    let kb = key(&positions[b as usize]);
                    let ordered = if ka <= kb { [ka, kb] } else { [kb, ka] };
                    *counts.entry(ordered).or_insert(0) += 1;
                });
        });
    });
    counts.values().all(|count| *count == 2)
}

#[cfg(test)]
mod tests {
    use super::StableHasher;
    use std::hash::Hasher;

    fn digest_via(emit: impl FnOnce(&mut StableHasher)) -> u64 {
        let mut hasher = StableHasher(blake3::Hasher::new());
        emit(&mut hasher);
        hasher.finish()
    }

    #[test]
    fn integer_writes_are_little_endian_not_native() {
        let value = 0x0102_0304_0506_0708_u64;
        let method = digest_via(|h| h.write_u64(value));
        assert_eq!(
            method,
            digest_via(|h| h.write(&value.to_le_bytes())),
            "write_u64 must emit little-endian bytes on every host"
        );
        assert_ne!(
            method,
            digest_via(|h| h.write(&value.to_be_bytes())),
            "a big-endian framing must not collide with the canonical one"
        );
    }

    #[test]
    fn pointer_sized_writes_are_normalized_to_64_bit() {
        assert_eq!(
            digest_via(|h| h.write_usize(0x0102_0304)),
            digest_via(|h| h.write_u64(0x0102_0304_u64)),
            "usize must hash as a 64-bit value so 32-bit and 64-bit hosts agree"
        );
        assert_eq!(
            digest_via(|h| h.write_isize(-0x0102_0304)),
            digest_via(|h| h.write_i64(-0x0102_0304_i64)),
            "isize must hash as a 64-bit value so 32-bit and 64-bit hosts agree"
        );
    }
}
