GitCorner

Code

ossartcrafttexturecraft🌐
d84914ef1e5a
//! The internal triangle mesh.

use glam::{Vec2, Vec3, Vec4};

use crate::{GeomError, Result};

/// An edge by the bits of its two end positions, the lower one first
type EdgePositions = ([u32; 3], [u32; 3]);

/// Normals closer than about one degree are the same normal: the edge between them is smooth
const SAME_NORMAL_MIN_COSINE: f32 = 0.9998;

/// A contiguous index range drawn with one material.
#[derive(Clone, Debug, PartialEq)]
pub struct SubMesh {
    pub name: String,
    pub material: usize,
    /// First index (into [`Mesh::indices`]) and index count.
    pub start: u32,
    pub count: u32,
}

/// A material's base color (what a color-map bake transfers): `factor` (linear RGBA) times an
/// optional texture sampled at the mesh UVs.
#[derive(Clone, Debug, PartialEq)]
pub struct BaseColor {
    pub factor: Vec4,
    pub width: u32,
    pub height: u32,
    /// `width × height` RGBA8 texels (color sRGB-encoded, alpha linear), rows top → bottom like
    /// the UVs' v; empty without a texture.
    pub texels: Vec<[u8; 4]>,
}

/// Triangle mesh in world space. UVs use the glTF convention (origin top-left, v down).
#[derive(Clone, Debug, Default, PartialEq)]
pub struct Mesh {
    pub positions: Vec<Vec3>,
    pub normals: Vec<Vec3>,
    /// xyz tangent, w bitangent sign.
    pub tangents: Vec<Vec4>,
    pub uvs: Vec<Vec2>,
    /// RGBA vertex colors in 0..1 (glTF: linear; OBJ, PLY: as stored): one per vertex, or empty.
    pub colors: Vec<Vec4>,
    pub indices: Vec<u32>,
    /// Index ranges per material and part (node / object); `name` is the part name.
    pub submeshes: Vec<SubMesh>,
    pub materials: Vec<String>,
    /// Per triangle, bit `i` set when edge `i` (corner `i` to corner `i + 1`) is a diagonal the
    /// importer added to split a polygon, which wireframes leave out. Empty: every edge is real.
    pub diagonals: Vec<u8>,
}

/// [`Mesh::diagonals`] marks of the two fan triangles of a quad: the first has the diagonal as
/// its edge 2 (last corner back to the first), the second as its edge 0.
const QUAD_FIRST_MARK: u8 = 0b100;
const QUAD_SECOND_MARK: u8 = 0b001;

/// Hard cap on mesh size accepted from files (triangles).
pub const MAX_TRIANGLES: usize = 20_000_000;

impl Mesh {
    pub fn triangle_count(&self) -> usize {
        self.indices.len() / 3
    }

    pub fn vertex_count(&self) -> usize {
        self.positions.len()
    }

    /// Axis-aligned bounds (zero box for an empty mesh).
    pub fn bounds(&self) -> (Vec3, Vec3) {
        if self.positions.is_empty() {
            return (Vec3::ZERO, Vec3::ZERO);
        }
        self.positions.iter().fold((Vec3::splat(f32::MAX), Vec3::splat(f32::MIN)), |(lo, hi), p| (lo.min(*p), hi.max(*p)))
    }

    /// Axis-aligned bounds of the triangles drawn with `material` (None when none are).
    pub fn bounds_of_material(&self, material: usize) -> Option<(Vec3, Vec3)> {
        let mut bounds: Option<(Vec3, Vec3)> = None;
        for triangle in self.triangles_of(material) {
            let Some(corners) = self.tri(triangle) else { continue };
            for corner in corners {
                let Some(position) = self.positions.get(corner) else { continue };
                bounds = Some(bounds.map_or((*position, *position), |(lo, hi)| (lo.min(*position), hi.max(*position))));
            }
        }
        bounds
    }

    /// Bounding-sphere radius around the bounds center (at least a small epsilon).
    pub fn radius(&self) -> f32 {
        let (lo, hi) = self.bounds();
        ((hi - lo).length() * 0.5).max(1e-4)
    }

    /// Vertex indices of triangle `t`.
    pub fn tri(&self, t: usize) -> Option<[usize; 3]> {
        let i = self.indices.get(t * 3..t * 3 + 3)?;
        Some([i[0] as usize, i[1] as usize, i[2] as usize])
    }

    /// The edges wireframes draw: each vertex pair once (smaller index first), leaving out
    /// polygon diagonals ([`Mesh::diagonals`]) unless only one triangle has the edge (a UV seam
    /// split it from its twin), per material in `0..materials.len().max(1)`.
    pub fn wire_edges(&self) -> Vec<Vec<(u32, u32)>> {
        (0..self.materials.len().max(1))
            .map(|material| {
                // Keep first-seen edge order while counting its triangle uses
                let mut edges: Vec<((u32, u32), bool, u8)> = Vec::new();
                let mut edge_indices: std::collections::HashMap<(u32, u32), usize> = std::collections::HashMap::new();
                for triangle in self.triangles_of(material) {
                    let Some(vertices) = self.indices.get(triangle * 3..triangle * 3 + 3) else { continue };
                    let hidden = self.diagonals.get(triangle).copied().unwrap_or(0);
                    for (side, (from, to)) in [(vertices[0], vertices[1]), (vertices[1], vertices[2]), (vertices[2], vertices[0])].into_iter().enumerate() {
                        let key = (from.min(to), from.max(to));
                        let is_polygon_edge = hidden >> side & 1 == 0;
                        let edge_index = *edge_indices.entry(key).or_insert_with(|| {
                            edges.push((key, false, 0));
                            edges.len() - 1
                        });
                        if let Some((_, edge_is_polygon_side, triangle_count)) = edges.get_mut(edge_index) {
                            *edge_is_polygon_side |= is_polygon_edge;
                            *triangle_count = triangle_count.saturating_add(1);
                        }
                    }
                }
                edges.into_iter().filter(|(_, is_polygon_edge, triangle_count)| *is_polygon_edge || *triangle_count == 1).map(|(edge, ..)| edge).collect()
            })
            .collect()
    }

    /// Hard edges the UV layout does not split, which bake visible lines into the normal map: two triangles meet there with different normals but the same UVs, per material in `0..materials.len().max(1)`
    pub fn missing_seam_edges(&self) -> Vec<Vec<(u32, u32)>> {
        // Signed zero denotes the same position on either side of an imported seam
        let bits = |position: Vec3| position.to_array().map(|coordinate| if coordinate == 0.0 { 0 } else { coordinate.to_bits() });
        let mut seams = vec![Vec::new(); self.materials.len().max(1)];

        // Match across materials before grouping the lines for texture-set visibility
        let mut sides: std::collections::HashMap<EdgePositions, Vec<(u32, u32, usize)>> = std::collections::HashMap::new();
        for material in 0..seams.len() {
            for triangle in self.triangles_of(material) {
                let Some(corners) = self.indices.get(triangle * 3..triangle * 3 + 3) else { continue };

                for (from, to) in [(corners[0], corners[1]), (corners[1], corners[2]), (corners[2], corners[0])] {
                    let (Some(from_position), Some(to_position)) = (self.positions.get(from as usize), self.positions.get(to as usize)) else { continue };

                    let (from_bits, to_bits) = (bits(*from_position), bits(*to_position));
                    let (edge, pair) = if from_bits <= to_bits { ((from_bits, to_bits), (from, to)) } else { ((to_bits, from_bits), (to, from)) };
                    sides.entry(edge).or_default().push((pair.0, pair.1, material));
                }
            }
        }

        let uv = |index: u32| self.uvs.get(index as usize).copied();

        // Imported normals need not be unit length; two missing normals agree
        let direction = |index: u32| self.normals.get(index as usize).map_or(Vec3::ZERO, |normal| normal.normalize_or_zero());
        let same_normal = |a: u32, b: u32| {
            let (a, b) = (direction(a), direction(b));
            a == b || a.dot(b) >= SAME_NORMAL_MIN_COSINE
        };
        for pairs in sides.into_values() {
            let Some(&(first_from, first_to, _)) = pairs.first() else { continue };

            let uv_split = pairs.iter().any(|&(from, to, _)| (uv(from), uv(to)) != (uv(first_from), uv(first_to)));
            let hard = pairs.iter().any(|&(from, to, _)| !same_normal(from, first_from) || !same_normal(to, first_to));
            if hard && !uv_split {
                for (from, to, material) in pairs {
                    if let Some(edges) = seams.get_mut(material) {
                        edges.push((from.min(to), from.max(to)));
                    }
                }
            }
        }
        for edges in &mut seams {
            edges.sort_unstable();
            edges.dedup();
        }

        seams
    }

    /// Material of triangle `t`.
    pub fn material_of(&self, t: usize) -> Option<usize> {
        let idx = (t * 3) as u32;
        self.submeshes.iter().find(|s| idx >= s.start && idx < s.start.saturating_add(s.count)).map(|s| s.material)
    }

    /// Triangle index range belonging to material `m` (all submeshes of that material).
    pub fn triangles_of(&self, m: usize) -> impl Iterator<Item = usize> + '_ {
        self.submeshes.iter().filter(move |s| s.material == m).flat_map(|s| (s.start / 3) as usize..((s.start + s.count) / 3) as usize)
    }

    /// Check that attribute arrays agree and every index is in range.
    pub fn validate(&self) -> Result<()> {
        let n = self.positions.len();
        if self.normals.len() != n || self.uvs.len() != n || self.tangents.len() != n {
            return Err(GeomError::Invalid(format!(
                "attribute counts differ: {} positions, {} normals, {} uvs, {} tangents",
                n,
                self.normals.len(),
                self.uvs.len(),
                self.tangents.len()
            )));
        }
        if !self.colors.is_empty() && self.colors.len() != n {
            return Err(GeomError::Invalid(format!("{} vertex colors for {n} vertices", self.colors.len())));
        }
        if !self.indices.len().is_multiple_of(3) {
            return Err(GeomError::Invalid("index count is not a multiple of 3".into()));
        }
        if self.triangle_count() > MAX_TRIANGLES {
            return Err(GeomError::Invalid(format!("mesh has more than {MAX_TRIANGLES} triangles")));
        }
        if let Some(bad) = self.indices.iter().find(|i| **i as usize >= n) {
            return Err(GeomError::Invalid(format!("index {bad} out of range ({n} vertices)")));
        }
        if self.positions.iter().any(|p| !p.is_finite()) {
            return Err(GeomError::Invalid("mesh has non-finite positions".into()));
        }
        for s in &self.submeshes {
            if s.start as usize + s.count as usize > self.indices.len() || s.material >= self.materials.len().max(1) {
                return Err(GeomError::Invalid(format!("submesh {} is out of range", s.name)));
            }
        }
        Ok(())
    }

    /// Area-weighted smooth normals over the index buffer.
    pub fn compute_normals(&mut self) {
        let mut normals = vec![Vec3::ZERO; self.positions.len()];
        for &[a, b, c] in self.indices.as_chunks::<3>().0 {
            let (a, b, c) = (a as usize, b as usize, c as usize);
            let (Some(pa), Some(pb), Some(pc)) = (self.positions.get(a), self.positions.get(b), self.positions.get(c)) else { continue };
            let face = (*pb - *pa).cross(*pc - *pa);
            for v in [a, b, c] {
                if let Some(x) = normals.get_mut(v) {
                    *x += face;
                }
            }
        }

        self.normals = normals.into_iter().map(|v| v.try_normalize().unwrap_or(Vec3::Y)).collect();
    }

    /// The faces MikkTSpace sees: each importer quad (a fan pair marked in [`Mesh::diagonals`])
    /// as one four-corner face, like Blender hands it over, and every other triangle as a
    /// triangle. Polygons with more than four corners stay fan triangles. The vertex and index
    /// buffers are untouched; only tangent generation looks at the quads.
    fn tangent_faces(&self) -> Vec<TangentFace> {
        let triangles = self.indices.len() / 3;
        // An empty face table keeps the original constant-space triangle adapter.
        // Do not allocate a per-triangle table unless a valid quad needs one.
        if !self.diagonals.contains(&QUAD_FIRST_MARK) || !(0..triangles).any(|t| self.quad_at(t).is_some()) {
            return Vec::new();
        }
        let mut faces = Vec::with_capacity(triangles);
        let mut t = 0;
        while t < triangles {
            if let Some(corners) = self.quad_at(t) {
                faces.push(TangentFace { corners: [corners[0], corners[1], corners[2], corners[3]], count: 4 });
                t += 2;
                continue;
            }
            let c = |k: usize| self.indices.get(t * 3 + k).copied().unwrap_or(0);
            faces.push(TangentFace { corners: [c(0), c(1), c(2), 0], count: 3 });
            t += 1;
        }
        faces
    }

    /// The four corners of the quad whose fan triangles are `t` and `t + 1`, or `None` when they
    /// are not an intact quad: the marks must be exactly the shared diagonal (a fan of more
    /// corners marks more edges), the triangles must share the fan's first corner and the
    /// diagonal's end, the four vertices must differ, have finite UVs and make two triangles of
    /// positive area (anything else keeps its triangles, which MikkTSpace already survives).
    fn quad_at(&self, t: usize) -> Option<[u32; 4]> {
        if self.diagonals.get(t).copied()? != QUAD_FIRST_MARK || self.diagonals.get(t + 1).copied()? != QUAD_SECOND_MARK {
            return None;
        }
        let a = self.indices.get(t * 3..t * 3 + 3)?;
        let b = self.indices.get(t * 3 + 3..t * 3 + 6)?;
        if a[0] != b[0] || a[2] != b[1] {
            return None;
        }
        let corners = [a[0], a[1], a[2], b[2]];
        if (1..4).any(|i| corners[..i].contains(&corners[i])) {
            return None;
        }
        let point = |c: usize| self.positions.get(corners[c] as usize).copied();
        let (p0, p1, p2, p3) = (point(0)?, point(1)?, point(2)?, point(3)?);
        let points = [p0, p1, p2, p3];
        // Distinct corner indices can still share one position (a seam); MikkTSpace compares
        // positions exactly and underflows when every triangle of a folded quad is dropped.
        if (1..4).any(|i| points[..i].contains(&points[i])) {
            return None;
        }
        let area = |p: Vec3, q: Vec3, r: Vec3| (q - p).cross(r - p).length_squared() > 0.0;
        if area(p0, p1, p2) && area(p0, p2, p3) && corners.iter().all(|&c| self.uvs.get(c as usize).is_some_and(|uv| uv.is_finite())) {
            Some(corners)
        } else {
            None
        }
    }

    /// MikkTSpace tangents (falls back to per-triangle tangents if generation fails). Quads the
    /// importer split ([`Mesh::diagonals`]) are tangent-generated as quads, as Blender does.
    pub fn compute_tangents(&mut self) {
        self.tangents = vec![Vec4::new(1.0, 0.0, 0.0, 1.0); self.positions.len()];
        if self.normals.len() != self.positions.len() {
            self.compute_normals();
        }
        if self.uvs.len() != self.positions.len() {
            self.uvs = vec![Vec2::ZERO; self.positions.len()];
        }
        // mikktspace crashes (out-of-bounds) when every triangle is degenerate; skip it then.
        if crate::unwrap::all_triangles_degenerate(self) {
            self.simple_tangents();
        } else {
            let faces = self.tangent_faces();
            let mut g = Mikk { mesh: self, faces };
            if !mikktspace::generate_tangents(&mut g) {
                self.simple_tangents();
            }
        }
        for (t, n) in self.tangents.iter_mut().zip(&self.normals) {
            // Orthonormalize against the normal; repair degenerate results.
            let v = t.truncate();
            let o = (v - *n * n.dot(v)).try_normalize().unwrap_or_else(|| n.any_orthonormal_vector());
            *t = o.extend(if t.w < 0.0 { -1.0 } else { 1.0 });
        }
    }

    fn simple_tangents(&mut self) {
        let mut tangents = vec![Vec3::ZERO; self.positions.len()];
        for &[a, b, c] in self.indices.as_chunks::<3>().0 {
            let (a, b, c) = (a as usize, b as usize, c as usize);
            let (Some(pa), Some(pb), Some(pc)) = (self.positions.get(a), self.positions.get(b), self.positions.get(c)) else { continue };
            let (Some(ua), Some(ub), Some(uc)) = (self.uvs.get(a), self.uvs.get(b), self.uvs.get(c)) else { continue };
            let (e1, e2) = (*pb - *pa, *pc - *pa);
            let (d1, d2) = (*ub - *ua, *uc - *ua);
            let determinant = d1.x * d2.y - d2.x * d1.y;
            if determinant.abs() < 1e-12 {
                continue;
            }

            let tangent = (e1 * d2.y - e2 * d1.y) / determinant;
            for v in [a, b, c] {
                if let Some(x) = tangents.get_mut(v) {
                    *x += tangent;
                }
            }
        }

        self.tangents = tangents.into_iter().map(|t| t.try_normalize().unwrap_or(Vec3::X).extend(1.0)).collect();
    }

    /// The UV tiles material `m` covers: integer parts of its triangles' UV centroids (v down),
    /// ascending. Non-finite UVs are skipped.
    pub fn uv_tiles(&self, m: usize) -> std::collections::BTreeSet<(i32, i32)> {
        self.triangles_of(m)
            .filter_map(|t| {
                let [a, b, c] = self.tri(t)?;
                let uv = (*self.uvs.get(a)? + *self.uvs.get(b)? + *self.uvs.get(c)?) / 3.0;
                uv.is_finite().then(|| (uv.x.floor() as i32, uv.y.floor() as i32))
            })
            .collect()
    }

    /// Remap the UVs of material `m`'s triangles with `f`. Vertices they share with other
    /// materials are duplicated first, so the other triangles keep their UVs.
    pub fn map_material_uvs(&mut self, m: usize, f: impl Fn(Vec2) -> Vec2) {
        self.map_material_uvs_with(m, |_, uv| f(uv));
    }

    /// [`Mesh::map_material_uvs`] where `f` also gets the UV centroid of the first of the
    /// material's triangles using the vertex: piecewise maps (UV tiles of different sizes) then
    /// place a vertex on a tile border with its own triangle's tile.
    pub fn map_material_uvs_with(&mut self, m: usize, f: impl Fn(Vec2, Vec2) -> Vec2) {
        let material_triangles: Vec<usize> = self.triangles_of(m).collect();
        let mut in_material = vec![false; self.triangle_count()];
        for t in &material_triangles {
            if let Some(x) = in_material.get_mut(*t) {
                *x = true;
            }
        }

        let mut shared = vec![false; self.positions.len()];
        for (_, tri) in self.indices.as_chunks::<3>().0.iter().enumerate().filter(|(t, _)| !in_material.get(*t).copied().unwrap_or(false)) {
            for v in tri {
                if let Some(s) = shared.get_mut(*v as usize) {
                    *s = true;
                }
            }
        }

        let mut duplicates = std::collections::HashMap::new();
        for k in material_triangles.iter().flat_map(|t| t * 3..t * 3 + 3) {
            let Some(&v) = self.indices.get(k) else { continue };
            let v =
                if shared.get(v as usize).copied().unwrap_or(false) { *duplicates.entry(v).or_insert_with(|| self.duplicate_vertex(v as usize)) } else { v };
            if let Some(i) = self.indices.get_mut(k) {
                *i = v;
            }
        }

        // (vertex, centroid of its first triangle), each vertex once
        let mut vertices = Vec::with_capacity(material_triangles.len() * 3);
        for t in &material_triangles {
            let Some(tri) = self.tri(*t) else { continue };
            let centroid = tri.iter().map(|v| self.uvs.get(*v).copied().unwrap_or_default()).sum::<Vec2>() / 3.0;
            vertices.extend(tri.map(|v| (v, centroid)));
        }

        vertices.sort_by_key(|(v, _)| *v);
        vertices.dedup_by_key(|(v, _)| *v);
        for (v, centroid) in vertices {
            if let Some(uv) = self.uvs.get_mut(v) {
                *uv = f(centroid, *uv);
            }
        }
    }

    /// Append a copy of vertex `v`; returns its index.
    fn duplicate_vertex(&mut self, v: usize) -> u32 {
        let i = self.positions.len() as u32;
        self.positions.push(self.positions.get(v).copied().unwrap_or_default());
        self.normals.push(self.normals.get(v).copied().unwrap_or(Vec3::Y));
        self.tangents.push(self.tangents.get(v).copied().unwrap_or(Vec4::new(1.0, 0.0, 0.0, 1.0)));
        self.uvs.push(self.uvs.get(v).copied().unwrap_or_default());
        if !self.colors.is_empty() {
            self.colors.push(self.colors.get(v).copied().unwrap_or(Vec4::ONE));
        }
        i
    }

    /// Append `other`, offsetting indices; its submeshes keep their material indices shifted by
    /// this mesh's material count.
    pub fn append(&mut self, other: &Mesh) {
        let base = self.positions.len() as u32;
        let ibase = self.indices.len() as u32;
        let mbase = self.materials.len();
        self.positions.extend_from_slice(&other.positions);
        self.normals.extend_from_slice(&other.normals);
        self.tangents.extend_from_slice(&other.tangents);
        self.uvs.extend_from_slice(&other.uvs);
        if !(self.colors.is_empty() && other.colors.is_empty()) {
            // Vertices of the side without colors become white.
            self.colors.resize(base as usize, Vec4::ONE);
            self.colors.extend(other.colors.iter().copied().chain(std::iter::repeat(Vec4::ONE)).take(other.positions.len()));
        }
        if !(self.diagonals.is_empty() && other.diagonals.is_empty()) {
            self.diagonals.resize(ibase as usize / 3, 0);
            self.diagonals.extend(other.diagonals.iter().copied().chain(std::iter::repeat(0)).take(other.triangle_count()));
        }
        self.indices.extend(other.indices.iter().map(|i| i + base));
        self.materials.extend(other.materials.iter().cloned());
        self.submeshes.extend(other.submeshes.iter().map(|s| SubMesh {
            name: s.name.clone(),
            material: s.material + mbase,
            start: s.start + ibase,
            count: s.count,
        }));
    }

    /// Uniformly scale and translate so the mesh is centered with the given bounding radius.
    pub fn normalize_to(&mut self, radius: f32) {
        let (lo, hi) = self.bounds();
        let c = (lo + hi) * 0.5;
        let s = radius / self.radius();
        for p in &mut self.positions {
            *p = (*p - c) * s;
        }
    }

    /// A single-material mesh from raw attributes; computes missing normals and tangents.
    pub fn from_parts(positions: Vec<Vec3>, normals: Option<Vec<Vec3>>, uvs: Vec<Vec2>, indices: Vec<u32>, material: &str) -> Result<Mesh> {
        let count = indices.len() as u32;
        let mut m = Mesh {
            normals: normals.unwrap_or_default(),
            uvs,
            positions,
            indices,
            tangents: Vec::new(),
            colors: Vec::new(),
            submeshes: vec![SubMesh { name: material.into(), material: 0, start: 0, count }],
            materials: vec![material.into()],
            diagonals: Vec::new(),
        };
        if m.normals.len() != m.positions.len() {
            m.compute_normals();
        }
        m.compute_tangents();
        m.validate()?;
        Ok(m)
    }
}

/// One MikkTSpace face: a triangle or a quad, as vertex indices.
struct TangentFace {
    corners: [u32; 4],
    /// 3 or 4 corners in use.
    count: usize,
}

struct Mikk<'a> {
    mesh: &'a mut Mesh,
    faces: Vec<TangentFace>,
}

impl Mikk<'_> {
    fn vi(&self, face: usize, vert: usize) -> usize {
        if self.faces.is_empty() {
            self.mesh.indices.get(face * 3 + vert).copied().unwrap_or(0) as usize
        } else {
            self.faces.get(face).and_then(|f| f.corners.get(vert)).copied().unwrap_or(0) as usize
        }
    }
}

impl mikktspace::Geometry for Mikk<'_> {
    fn num_faces(&self) -> usize {
        if self.faces.is_empty() { self.mesh.indices.len() / 3 } else { self.faces.len() }
    }
    fn num_vertices_of_face(&self, face: usize) -> usize {
        self.faces.get(face).map_or(3, |f| f.count)
    }
    fn position(&self, face: usize, vert: usize) -> [f32; 3] {
        self.mesh.positions.get(self.vi(face, vert)).copied().unwrap_or_default().to_array()
    }
    fn normal(&self, face: usize, vert: usize) -> [f32; 3] {
        self.mesh.normals.get(self.vi(face, vert)).copied().unwrap_or(Vec3::Y).to_array()
    }
    fn tex_coord(&self, face: usize, vert: usize) -> [f32; 2] {
        // MikkTSpace expects OpenGL texture coordinates (v up); our UVs are glTF (v down). With
        // v flipped, the bitangent `cross(N, T) * w` points up the image, as glTF requires.
        let uv = self.mesh.uvs.get(self.vi(face, vert)).copied().unwrap_or_default();
        [uv.x, 1.0 - uv.y]
    }
    fn set_tangent_encoded(&mut self, tangent: [f32; 4], face: usize, vert: usize) {
        let i = self.vi(face, vert);
        if let Some(t) = self.mesh.tangents.get_mut(i) {
            *t = Vec4::from_array(tangent);
        }
    }
}

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

    #[test]
    fn unmarked_and_invalid_quad_meshes_need_no_face_table() {
        let mut mesh = quad();
        assert_eq!(mesh.tangent_faces().capacity(), 0);
        mesh.diagonals = vec![QUAD_FIRST_MARK, QUAD_SECOND_MARK];
        assert_eq!(mesh.tangent_faces().len(), 1);
        mesh.positions.fill(Vec3::ZERO);
        mesh.normals.fill(Vec3::X);
        assert_eq!(mesh.tangent_faces().capacity(), 0);
        mesh.compute_tangents();
        assert!(mesh.tangents.iter().all(|t| t.is_finite() && t.truncate().dot(Vec3::X).abs() < 1e-6));
    }

    fn quad() -> Mesh {
        Mesh::from_parts(
            vec![Vec3::new(0.0, 0.0, 0.0), Vec3::new(1.0, 0.0, 0.0), Vec3::new(1.0, 1.0, 0.0), Vec3::new(0.0, 1.0, 0.0)],
            None,
            vec![Vec2::new(0.0, 1.0), Vec2::new(1.0, 1.0), Vec2::new(1.0, 0.0), Vec2::new(0.0, 0.0)],
            vec![0, 1, 2, 0, 2, 3],
            "Default",
        )
        .unwrap()
    }

    #[test]
    fn normals_and_tangents_of_a_quad() {
        let m = quad();
        for n in &m.normals {
            assert!((*n - Vec3::Z).length() < 1e-5);
        }
        for t in &m.tangents {
            assert!((t.truncate() - Vec3::X).length() < 1e-4, "{t:?}");
        }
        assert_eq!(m.material_of(1), Some(0));
        assert_eq!(m.triangles_of(0).collect::<Vec<_>>(), vec![0, 1]);
    }

    #[test]
    fn bounds_of_a_material_cover_only_its_triangles() {
        let m = quad();
        assert_eq!(m.bounds_of_material(0), Some((Vec3::ZERO, Vec3::new(1.0, 1.0, 0.0))));
        assert_eq!(m.bounds_of_material(1), None);
    }

    #[test]
    fn wire_edges_leave_out_polygon_diagonals() {
        let mut m = quad();
        assert_eq!(m.wire_edges(), vec![vec![(0, 1), (1, 2), (0, 2), (2, 3), (0, 3)]], "triangles show every edge");

        // Hide the quad's shared diagonal
        m.diagonals = vec![0b100, 0b001];
        assert_eq!(m.wire_edges(), vec![vec![(0, 1), (1, 2), (2, 3), (0, 3)]]);

        // Keep the diagonal when a seam splits its twin
        let mut seam = m.clone();
        seam.indices[3] = 4;
        assert_eq!(seam.wire_edges()[0].len(), 6);

        // Appending preserves each side's own diagonals
        let mut a = Mesh::from_parts(m.positions.clone(), None, m.uvs.clone(), vec![0, 1, 2], "A").unwrap();
        a.append(&m);
        assert_eq!(a.diagonals, vec![0, 0b100, 0b001]);
        assert_eq!(crate::primitives::plane(1.0, 2).wire_edges()[0].len(), 12, "a 2×2 grid of quads has 12 edges");
    }

    /// `quad` with vertex 4 a copy of vertex 0 at `uv` with `normal`, used by the second triangle: the diagonal (0, 2) / (4, 2) has two sides
    fn split_quad(uv: Vec2, normal: Vec3) -> Mesh {
        let mut mesh = quad();
        mesh.positions.push(mesh.positions[0]);
        mesh.normals.push(normal);
        mesh.tangents.push(mesh.tangents[0]);
        mesh.uvs.push(uv);
        mesh.indices[3] = 4;
        mesh
    }

    #[test]
    fn missing_seams_are_hard_edges_the_uv_layout_does_not_split() {
        let none = vec![Vec::<(u32, u32)>::new()];
        assert_eq!(quad().missing_seam_edges(), none, "a smooth quad has no hard edge");

        let shared_uv = quad().uvs[0];
        let smooth_split = split_quad(shared_uv, Vec3::Z);
        assert_eq!(smooth_split.missing_seam_edges(), none, "the same normal on both sides is a smooth edge");

        let hard = split_quad(shared_uv, Vec3::new(1.0, 0.0, 1.0).normalize());
        assert_eq!(hard.missing_seam_edges(), vec![vec![(0, 2), (2, 4)]], "a hard edge inside one UV island");

        let seamed = split_quad(Vec2::new(0.9, 0.9), hard.normals[4]);
        assert_eq!(seamed.missing_seam_edges(), none, "a hard edge on a UV seam is fine");

        let mut short_normals = quad();
        short_normals.normals.iter_mut().for_each(|normal| *normal *= 0.5);
        assert_eq!(short_normals.missing_seam_edges(), none, "normals shorter than unit length point the same way");
        assert_eq!(split_quad(shared_uv, Vec3::Z * 0.5).missing_seam_edges(), none, "normals of different lengths point the same way");

        let mut no_normals = quad();
        no_normals.normals.fill(Vec3::ZERO);
        assert_eq!(no_normals.missing_seam_edges(), none, "two missing normals agree");
    }

    #[test]
    fn missing_seams_join_positions_with_opposite_signed_zero() {
        let mut mesh = split_quad(quad().uvs[0], Vec3::X);
        mesh.positions[4] = Vec3::new(-0.0, 0.0, 0.0);
        assert_eq!(mesh.positions[0], mesh.positions[4]);
        assert_eq!(mesh.missing_seam_edges(), vec![vec![(0, 2), (2, 4)]]);
    }

    #[test]
    fn missing_seams_between_materials_belong_to_both_materials() {
        let mut mesh = split_quad(quad().uvs[0], Vec3::X);
        mesh.materials.push("second".into());
        mesh.submeshes[0].count = 3;
        mesh.submeshes.push(SubMesh { name: "second".into(), material: 1, start: 3, count: 3 });

        assert_eq!(mesh.missing_seam_edges(), vec![vec![(0, 2)], vec![(2, 4)]]);
        mesh.normals[4] = mesh.normals[0];
        assert_eq!(mesh.missing_seam_edges(), vec![Vec::<(u32, u32)>::new(); 2], "a material boundary alone is not a hard edge");
    }

    /// MikkTSpace run directly on one quad, the way Blender hands it over (the reference the
    /// triangle-corner results are held to).
    struct QuadRef<'a> {
        mesh: &'a Mesh,
        out: [Vec4; 4],
    }

    impl mikktspace::Geometry for QuadRef<'_> {
        fn num_faces(&self) -> usize {
            1
        }
        fn num_vertices_of_face(&self, _face: usize) -> usize {
            4
        }
        fn position(&self, _face: usize, vert: usize) -> [f32; 3] {
            self.mesh.positions[vert].to_array()
        }
        fn normal(&self, _face: usize, vert: usize) -> [f32; 3] {
            self.mesh.normals[vert].to_array()
        }
        fn tex_coord(&self, _face: usize, vert: usize) -> [f32; 2] {
            [self.mesh.uvs[vert].x, 1.0 - self.mesh.uvs[vert].y]
        }
        fn set_tangent_encoded(&mut self, tangent: [f32; 4], _face: usize, vert: usize) {
            self.out[vert] = Vec4::from_array(tangent);
        }
    }

    /// A non-planar quad with a trapezoid UV layout, split as the importer does (two fan
    /// triangles, the diagonal marked), tangents computed.
    fn warped_quad() -> Mesh {
        let mut m = Mesh::from_parts(
            vec![Vec3::new(0.0, 0.0, 0.0), Vec3::new(1.0, 0.0, 0.0), Vec3::new(1.0, 1.0, 0.6), Vec3::new(0.0, 1.0, 0.0)],
            None,
            vec![Vec2::new(0.0, 0.9), Vec2::new(1.0, 1.0), Vec2::new(0.9, 0.0), Vec2::new(0.3, 0.2)],
            vec![0, 1, 2, 0, 2, 3],
            "Default",
        )
        .unwrap();
        m.diagonals = vec![0b100, 0b001];
        m.compute_tangents();
        m
    }

    /// Largest angle in degrees between the tangents of `a` and `b`, and whether any sign differs.
    fn tangent_gap(a: &[Vec4], b: &[Vec4]) -> (f32, bool) {
        let angle = a.iter().zip(b).map(|(x, y)| x.truncate().dot(y.truncate()).clamp(-1.0, 1.0).acos().to_degrees()).fold(0.0, f32::max);
        (angle, a.iter().zip(b).any(|(x, y)| x.w != y.w))
    }

    #[test]
    fn warped_quad_tangents_match_quad_mikktspace() {
        let m = warped_quad();
        let mut reference = QuadRef { mesh: &m, out: [Vec4::ZERO; 4] };
        assert!(mikktspace::generate_tangents(&mut reference));
        let n = m.normals.clone();
        let reference: Vec<Vec4> = reference
            .out
            .iter()
            .zip(&n)
            .map(|(t, n)| {
                let v = t.truncate();
                (v - *n * n.dot(v)).normalize().extend(t.w)
            })
            .collect();
        let (angle, sign) = tangent_gap(&m.tangents, &reference);
        assert!(angle < 0.01 && !sign, "tangents differ from quad MikkTSpace by {angle} degrees (sign differs: {sign})");

        // Without the polygon marks the mesh is two triangles, whose tangents are another frame.
        let mut tris = m.clone();
        tris.diagonals.clear();
        tris.compute_tangents();
        assert!(tangent_gap(&tris.tangents, &reference).0 > 0.5, "the quad and the triangle frames must differ for this test to mean anything");
    }

    #[test]
    fn planar_quad_tangents_do_not_change() {
        let mut m = quad();
        let before = m.tangents.clone();
        m.diagonals = vec![0b100, 0b001];
        m.compute_tangents();
        let (angle, flipped) = tangent_gap(&m.tangents, &before);
        assert!(angle < 1e-3 && !flipped, "angle {angle}, flipped {flipped}");
    }

    #[test]
    fn folded_quad_sharing_a_position_does_not_crash_mikktspace() {
        // Corner 3 reuses corner 1's position with its own UV (a 4-line OBJ makes this). With
        // only this quad in the mesh every MikkTSpace triangle used to be dropped and it crashed.
        let mut m = Mesh::from_parts(
            vec![Vec3::ZERO, Vec3::X, Vec3::new(1.0, 1.0, 0.0), Vec3::X],
            Some(vec![Vec3::Z; 4]),
            vec![Vec2::new(0.0, 1.0), Vec2::new(1.0, 1.0), Vec2::new(1.0, 0.0), Vec2::new(0.5, 0.5)],
            vec![0, 1, 2, 0, 2, 3],
            "Default",
        )
        .unwrap();
        m.diagonals = vec![0b100, 0b001];
        m.compute_tangents();
        assert!(m.tangents.iter().all(|t| t.is_finite()), "{:?}", m.tangents);
    }

    #[test]
    fn hostile_quads_keep_triangle_tangents_and_do_not_panic() {
        // A repeated corner, a non-finite UV and a collapsed quad: no panic, tangents stay finite.
        for edit in 0..3 {
            let mut m = warped_quad();
            match edit {
                0 => m.indices = vec![0, 1, 1, 0, 1, 3],
                1 => m.uvs[2] = Vec2::new(f32::NAN, 0.0),
                _ => m.positions = vec![Vec3::ZERO; 4],
            }
            m.compute_tangents();
            assert!(m.tangents.iter().all(|t| t.is_finite()), "edit {edit}: {:?}", m.tangents);
        }
        // Diagonal marks on triangles that are not a fan pair are ignored.
        let mut m = warped_quad();
        m.diagonals = vec![0b100, 0b100];
        m.compute_tangents();
        let mut plain = warped_quad();
        plain.diagonals.clear();
        plain.compute_tangents();
        assert_eq!(m.tangents, plain.tangents);
    }

    #[test]
    fn polygons_beyond_four_corners_stay_triangles() {
        // A fan of three triangles (a pentagon) marks 0b100, 0b101, 0b001: no quad is found.
        let mut m = Mesh::from_parts(
            vec![Vec3::new(0.0, 0.0, 0.0), Vec3::new(1.0, 0.0, 0.0), Vec3::new(1.3, 1.0, 0.4), Vec3::new(0.5, 1.5, 0.0), Vec3::new(-0.3, 1.0, 0.0)],
            Some(vec![Vec3::Z; 5]),
            vec![Vec2::new(0.0, 1.0), Vec2::new(1.0, 1.0), Vec2::new(0.8, 0.0), Vec2::new(0.5, 0.0), Vec2::new(0.2, 0.0)],
            vec![0, 1, 2, 0, 2, 3, 0, 3, 4],
            "Default",
        )
        .unwrap();
        let before = m.tangents.clone();
        m.diagonals = vec![0b100, 0b101, 0b001];
        m.compute_tangents();
        assert_eq!(m.tangents, before);
    }

    #[test]
    fn validate_catches_bad_indices() {
        let mut m = quad();
        m.indices[0] = 99;
        assert!(m.validate().is_err());
        let mut m = quad();
        m.uvs.pop();
        assert!(m.validate().is_err());
    }

    #[test]
    fn append_offsets_indices_and_materials() {
        let mut a = quad();
        let b = quad();
        a.append(&b);
        assert_eq!(a.indices[6], 4);
        assert_eq!(a.submeshes[1].material, 1);
        assert_eq!(a.submeshes[1].start, 6);
        a.validate().unwrap();
        // Colors on one side only: the other side's vertices become white.
        let mut red = quad();
        red.colors = vec![Vec4::new(1.0, 0.0, 0.0, 1.0); 4];
        a.append(&red);
        assert_eq!(a.colors.len(), 12);
        assert_eq!((a.colors[0], a.colors[8]), (Vec4::ONE, Vec4::new(1.0, 0.0, 0.0, 1.0)));
        a.append(&quad());
        assert_eq!(a.colors[15], Vec4::ONE);
        a.validate().unwrap();
        a.colors.pop();
        assert!(a.validate().is_err());
    }

    #[test]
    fn material_uvs_remap_and_split_shared_vertices() {
        // quad(): two triangles sharing an edge; put the second in its own material.
        let mut m = quad();
        m.materials = vec!["a".into(), "b".into()];
        m.submeshes = vec![SubMesh { name: "a".into(), material: 0, start: 0, count: 3 }, SubMesh { name: "b".into(), material: 1, start: 3, count: 3 }];
        let before = m.clone();
        m.map_material_uvs(1, |uv| uv + Vec2::X);
        m.validate().unwrap();
        assert_eq!(m.vertex_count(), 6, "the two shared vertices are split");
        assert_eq!(&m.indices[..3], &before.indices[..3]);
        for k in 0..3 {
            let (old, new) = (before.indices[k] as usize, m.indices[k] as usize);
            assert_eq!(m.uvs[new], before.uvs[old], "material a keeps its UVs");
            let (old, new) = (before.indices[3 + k] as usize, m.indices[3 + k] as usize);
            assert_eq!((m.uvs[new], m.positions[new]), (before.uvs[old] + Vec2::X, before.positions[old]));
        }
        assert_eq!(m.uv_tiles(1).into_iter().collect::<Vec<_>>(), vec![(1, 0)]);
        assert_eq!(m.uv_tiles(0).into_iter().collect::<Vec<_>>(), vec![(0, 0)]);
    }
}