mirage-engine 0.1.0

use core::ops::Range;

use crate::math::{Mat3, Vec3, Vec4};
use crate::mesh::{Animation, Palette, Posing, Rig, Slot, Vertex};
use crate::{Material, ReliefData, ShadingData, TextureData, Transform};

/// How far off its plane a corner may lie and the mesh still count as
/// flat, as a fraction of the radius of the sphere that covers it.
const FLATNESS: f32 = 1e-4;

/// A mesh as the cache holds it: the buffers, the slots with the part each
/// resolves to, and the bounds a draw of it is tested by.
///
/// What a mesh set's build returns; a game never reads one.
#[doc(hidden)]
#[derive(Clone, Debug)]
pub struct Geometry {
    vertices: Vec<Vertex>,
    indices: Vec<u32>,
    slots: Vec<Slot>,
    bounds: Bounds,
    sphere: BoundingSphere,
    /// The plane the mesh is flat in, absent while it is not.
    plane: Option<MeshPlane>,
    /// The joints the mesh is posed by, empty where a model did not load it.
    rig: Rig,
    /// One animation per clip of the mesh's own vocabulary, in clip order.
    clips: Vec<Animation>,
}

impl Geometry {
    /// A mesh with nothing to draw.
    pub(crate) fn empty() -> Self {
        Self::over(Vec::new(), Vec::new(), Vec::new())
    }

    /// The mesh over `slots`, which cover `indices` exactly.
    pub(crate) fn over(vertices: Vec<Vertex>, indices: Vec<u32>, slots: Vec<Slot>) -> Self {
        let bounds = Bounds::over(&slots);
        let sphere = BoundingSphere::over(&vertices);
        let plane = MeshPlane::over(&vertices, sphere);
        Self {
            vertices,
            indices,
            slots,
            bounds,
            sphere,
            plane,
            rig: Rig::default(),
            clips: Vec::new(),
        }
    }

    /// The same mesh posed by `rig`, with one animation per clip its
    /// vocabulary names.
    ///
    /// The sphere a draw of it is tested by grows to cover every pose those
    /// clips reach; the plane it is flat in stays the plane its corners lie
    /// in at rest.
    pub(crate) fn posed(mut self, rig: Rig, clips: Vec<Animation>) -> Self {
        self.sphere = self.sphere.over_poses(&self.vertices, &rig, &clips);
        self.rig = rig;
        self.clips = clips;
        self
    }

    /// The joints the mesh is posed by.
    pub(crate) fn rig(&self) -> &Rig {
        &self.rig
    }

    /// What each clip of the mesh's vocabulary moves, in clip order.
    pub(crate) fn clips(&self) -> &[Animation] {
        &self.clips
    }

    /// The mesh's vertices, in the order the vertex buffer takes them.
    pub(crate) fn vertices(&self) -> &[Vertex] {
        &self.vertices
    }

    /// The triangle indices, three per triangle, counter-clockwise.
    pub(crate) fn indices(&self) -> &[u32] {
        &self.indices
    }

    /// The mesh's slots, in index order.
    pub(crate) fn slots(&self) -> &[Slot] {
        &self.slots
    }

    /// The mesh's slots, to set what every one of them draws with.
    pub(crate) fn slots_mut(&mut self) -> &mut [Slot] {
        &mut self.slots
    }

    /// Memory the mesh holds: its vertices, its indices, the pixels its
    /// slots sample, and the joints and keys it is posed by, without the few
    /// bytes each of the lists costs itself.
    pub(crate) fn bytes(&self) -> usize {
        let pixels: usize = self.slots.iter().map(Slot::bytes).sum();
        let keys: usize = self.clips().iter().map(Animation::bytes).sum();

        size_of_val(self.vertices.as_slice())
            + size_of_val(self.indices.as_slice())
            + pixels
            + self.rig().bytes()
            + keys
    }

    /// The sphere that covers the mesh's corners, in mesh space.
    pub(crate) fn sphere(&self) -> BoundingSphere {
        self.sphere
    }

    /// The plane the mesh's corners all lie in, in mesh space, absent where
    /// they lie in none.
    pub(crate) fn plane(&self) -> Option<MeshPlane> {
        self.plane
    }

    /// Part count the mesh draws as, one per slot.
    pub(crate) fn part_count(&self) -> usize {
        self.slots.len()
    }

    pub(crate) fn part_indices(&self, part: usize) -> Range<u32> {
        self.bounds.range(part)
    }

    /// The index of the part naming slot `part`, absent while it is
    /// anonymous.
    pub(crate) fn part_of(&self, part: usize) -> Option<u32> {
        self.slots.get(part).and_then(Slot::part)
    }

    pub(crate) fn part_material(&self, part: usize) -> Material {
        self.slots
            .get(part)
            .map_or_else(Material::default, Slot::material)
    }

    pub(crate) fn part_texture(&self, part: usize) -> Option<&TextureData> {
        self.slots.get(part).and_then(Slot::texture)
    }

    /// The relief `part` reads, absent where it has none.
    pub(crate) fn part_relief(&self, part: usize) -> Option<&ReliefData> {
        self.slots.get(part).and_then(Slot::relief_map)
    }

    /// The shading map `part` reads, absent where it has none.
    pub(crate) fn part_shading(&self, part: usize) -> Option<&ShadingData> {
        self.slots.get(part).and_then(Slot::shading_map)
    }

    /// The emissive map `part` reads, absent where it has none.
    pub(crate) fn part_emissive(&self, part: usize) -> Option<&TextureData> {
        self.slots.get(part).and_then(Slot::emissive)
    }
}

/// Where each slot's indices start and end: the running sum of the slot
/// lengths, one value more than there are slots.
#[derive(Clone, Debug, PartialEq)]
struct Bounds(Vec<u32>);

impl Bounds {
    /// The bounds of `slots`, each starting where the one before it ends.
    fn over(slots: &[Slot]) -> Self {
        let ends = slots.iter().scan(0u32, |covered, slot| {
            *covered = covered.saturating_add(slot.index_count());
            Some(*covered)
        });

        Self(core::iter::once(0).chain(ends).collect())
    }

    /// The indices of slot `part`.
    fn range(&self, part: usize) -> Range<u32> {
        self.0[part]..self.0[part + 1]
    }
}

/// A sphere that covers every corner of a mesh, in mesh space.
///
/// Turning a mesh leaves it as it is, so which way a draw faces never
/// changes what it covers.
#[derive(Clone, Copy, Debug, PartialEq)]
pub(crate) struct BoundingSphere {
    center: Vec3,
    radius: f32,
}

impl BoundingSphere {
    /// A sphere of `radius` meters about `center`.
    pub(crate) const fn new(center: Vec3, radius: f32) -> Self {
        Self { center, radius }
    }

    /// Sphere center.
    pub(crate) fn center(self) -> Vec3 {
        self.center
    }

    /// Sphere radius, in meters.
    pub(crate) fn radius(self) -> f32 {
        self.radius
    }

    /// The same sphere in world space, placed by `transform`: its largest
    /// column scales the radius, so any size and turn is still covered.
    pub(crate) fn placed(self, transform: Transform) -> Self {
        let model = transform.matrix();
        let widest = [model.x_axis, model.y_axis, model.z_axis]
            .into_iter()
            .map(|column| column.truncate().length())
            .fold(0.0, f32::max);

        Self::new(model.transform_point3(self.center), self.radius * widest)
    }

    /// The same sphere, scaled to cover the furthest point any pose `clips`
    /// reach moves a corner of `vertices` to: each clip is read at every
    /// time a track of it holds a key, and each corner moved by the joints
    /// it takes.
    ///
    /// So a walk that swings a corner past the mesh's own rest is drawn
    /// wherever the camera covers that swing. The center stays where the
    /// rest left it, and a mesh with no joints is left as it is.
    fn over_poses(self, vertices: &[Vertex], rig: &Rig, clips: &[Animation]) -> Self {
        if !rig.skins() {
            return self;
        }
        let mut palette = Palette::default();
        let reached = |palette: &Palette| {
            vertices
                .iter()
                .zip(rig.weights())
                .map(|(vertex, taken)| {
                    self.center
                        .distance_squared(taken.skinned(vertex.position, palette.matrices()))
                })
                .fold(0.0, f32::max)
        };

        let posings = clips.iter().enumerate().flat_map(|(clip, animation)| {
            animation
                .key_times()
                .into_iter()
                .map(move |at| Posing::clip(clip as u32, at))
        });
        let mut furthest = self.radius * self.radius;
        for posing in core::iter::once(None).chain(posings.map(Some)) {
            palette.clear();
            palette.composed(rig, clips, posing);
            furthest = furthest.max(reached(&palette));
        }

        Self::new(self.center, furthest.sqrt())
    }

    /// The sphere that covers `vertices`: in the middle of the box they
    /// fill, out to the furthest of them. Nothing covers nothing.
    fn over(vertices: &[Vertex]) -> Self {
        let Some(first) = vertices.first() else {
            return Self::new(Vec3::ZERO, 0.0);
        };
        let (least, most) = vertices
            .iter()
            .fold((first.position, first.position), |(least, most), vertex| {
                (least.min(vertex.position), most.max(vertex.position))
            });
        let center = (least + most) / 2.0;
        let radius = vertices
            .iter()
            .map(|vertex| center.distance_squared(vertex.position))
            .fold(0.0, f32::max)
            .sqrt();

        Self::new(center, radius)
    }
}

/// The one plane every corner of a flat mesh lies in: the direction the
/// plane faces, and its distance from the origin along that
/// direction.
#[derive(Clone, Copy, Debug, PartialEq)]
pub(crate) struct MeshPlane {
    normal: Vec3,
    distance: f32,
}

impl MeshPlane {
    /// The plane `vertices` lie in, absent where any of them lies off it
    /// by more than `FLATNESS` of the radius of `covering`, and absent where
    /// they lie along one line and so lie in no single plane.
    fn over(vertices: &[Vertex], covering: BoundingSphere) -> Option<Self> {
        let first = vertices.first()?.position;
        let longest =
            |left: &Vec3, right: &Vec3| left.length_squared().total_cmp(&right.length_squared());
        let along = vertices
            .iter()
            .map(|vertex| vertex.position - first)
            .max_by(longest)?;
        let normal = normalized(
            vertices
                .iter()
                .map(|vertex| along.cross(vertex.position - first))
                .max_by(longest)?,
        );
        let off = covering.radius() * FLATNESS;
        let flat = normal != Vec3::ZERO
            && vertices
                .iter()
                .all(|vertex| normal.dot(vertex.position - first).abs() <= off);

        flat.then_some(Self {
            normal,
            distance: normal.dot(first),
        })
    }

    /// The same plane in world space, placed by `transform`.
    pub(crate) fn placed(self, transform: Transform) -> Self {
        let model = transform.matrix();
        let [x, y, z] = [model.x_axis, model.y_axis, model.z_axis].map(Vec4::truncate);
        let cofactor = Mat3::from_cols(y.cross(z), z.cross(x), x.cross(y));
        let normal = normalized(cofactor * self.normal);

        Self {
            normal,
            distance: normal.dot(model.transform_point3(self.normal * self.distance)),
        }
    }

    /// The plane equation's four coefficients, which every point on the
    /// plane satisfies: the normal, then the negated distance.
    pub(crate) fn equation(self) -> Vec4 {
        self.normal.extend(-self.distance)
    }
}

/// `direction` at length one, and zero where it has no length: its length
/// divides each number, so a direction along an axis comes out exact
/// whatever the transform scaled it by.
fn normalized(direction: Vec3) -> Vec3 {
    let length = direction.length();
    if length > 0.0 {
        direction / length
    } else {
        Vec3::ZERO
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::Assets;
    use crate::math::{Mat4, Quat, Vec2};
    use crate::mesh::{
        Cube, Joint, Keys, Local, Mesh, MeshData, Moves, Placed, Plane, Quad, Track, Weighted,
    };

    fn corners(count: usize) -> Vec<Vertex> {
        vec![Vertex::new(Vec3::ZERO, Vec3::Y, Vec2::ZERO); count]
    }

    /// A mesh as the cache holds it.
    fn built(mesh: MeshData) -> Geometry {
        mesh.erased().expect("nothing is wrong with it")
    }

    #[test]
    fn bounds_start_each_slot_where_the_one_before_it_ends() {
        let slots = [3, 2, 1].map(|count| Slot::new(count, Material::default()));
        let bounds = Bounds::over(&slots);

        assert_eq!(bounds, Bounds(vec![0, 3, 5, 6]));
        assert_eq!(bounds.range(0), 0..3);
        assert_eq!(bounds.range(1), 3..5);
        assert_eq!(bounds.range(2), 5..6);
        assert_eq!(Bounds::over(&[]), Bounds(vec![0]), "no slot has no bounds");
    }

    /// A mesh of four corners well apart from each other, to take a sphere
    /// over.
    fn wedge() -> Geometry {
        let at = |position| Vertex::new(position, Vec3::Y, Vec2::ZERO);
        let corners = vec![
            at(Vec3::new(-1.0, 0.0, 0.0)),
            at(Vec3::new(9.0, 0.0, 0.0)),
            at(Vec3::new(9.0, 0.5, 0.0)),
            at(Vec3::new(8.5, 0.0, 2.0)),
        ];

        built(MeshData::new(corners, vec![0, 1, 2, 0, 2, 3]))
    }

    #[test]
    fn a_meshs_sphere_covers_every_corner_of_it() {
        let mesh = wedge();
        let sphere = mesh.sphere();

        assert_eq!(sphere.center(), Vec3::new(4.0, 0.25, 1.0));
        for vertex in mesh.vertices() {
            assert!(
                sphere.center().distance(vertex.position) <= sphere.radius(),
                "{} lies outside a sphere of {}",
                vertex.position,
                sphere.radius()
            );
        }
        assert!(
            mesh.vertices()
                .iter()
                .any(
                    |vertex| (sphere.center().distance(vertex.position) - sphere.radius()).abs()
                        < 1e-5
                ),
            "and one of them is what it reaches"
        );
        assert_eq!(
            Geometry::empty().sphere(),
            BoundingSphere::new(Vec3::ZERO, 0.0)
        );
    }

    #[test]
    fn a_placed_sphere_is_scaled_by_the_widest_column_of_the_transform() {
        let sphere = BoundingSphere::new(Vec3::X, 2.0);
        let squashed = sphere.placed(Transform::from_scale(Vec3::new(0.5, 3.0, 1.0)));

        assert_eq!(squashed.center(), Vec3::X * 0.5);
        assert_eq!(squashed.radius(), 6.0);

        let turned = sphere.placed(Transform::from_rotation(Quat::from_rotation_y(0.7)));
        assert!((turned.radius() - 2.0).abs() < 1e-5, "a turn leaves it be");
        assert!(
            turned
                .center()
                .abs_diff_eq(Vec3::new(0.765, 0.0, -0.644), 1e-3)
        );
    }

    /// A mesh of two corners a meter apart up a rig of two joints, each
    /// corner taking the joint beside it whole, under one clip that turns
    /// the joint below a quarter of a turn.
    fn jointed() -> Geometry {
        let at = |position| Vertex::new(position, Vec3::Y, Vec2::ZERO);
        let mesh = built(MeshData::new(
            vec![at(Vec3::ZERO), at(Vec3::Y * 2.0)],
            vec![0, 1, 0],
        ));
        let joint = |placed, position| Joint {
            placed,
            rest: Local::new(position, Quat::IDENTITY, Vec3::ONE),
            bind: Mat4::from_translation(position).inverse(),
        };
        let rig = Rig::new(
            vec![
                joint(Placed::Within(Mat4::IDENTITY), Vec3::ZERO),
                joint(Placed::Under(0), Vec3::Y * 2.0),
            ],
            vec![Weighted::whole(0), Weighted::whole(1)],
        );
        let turn = Keys::Step(vec![(
            0.0,
            Quat::from_rotation_z(core::f32::consts::FRAC_PI_2),
        )]);
        let clip = Animation::new(vec![Track {
            joint: 0,
            moves: Moves::Turn(turn),
        }]);

        mesh.posed(rig, vec![clip])
    }

    #[test]
    fn a_models_sphere_covers_the_corners_every_pose_of_its_clips_reaches() {
        let posed = jointed();
        let rest = BoundingSphere::over(posed.vertices());

        assert_eq!(rest.center(), Vec3::Y, "the corners lie a meter apart");
        assert_eq!(rest.radius(), 1.0);
        assert_eq!(posed.sphere().center(), rest.center(), "widened, not moved");
        assert!(
            (posed.sphere().radius() - 5.0f32.sqrt()).abs() < 1e-5,
            "{} does not reach the corner the clip swings two meters across",
            posed.sphere().radius()
        );
    }

    #[test]
    fn a_flat_mesh_lies_in_one_plane_and_a_mesh_with_depth_lies_in_none() {
        let assets = Assets::default();
        let plane_of = |mesh: MeshData| built(mesh).plane();

        assert_eq!(
            plane_of(Plane.build(&assets)),
            Some(MeshPlane {
                normal: Vec3::Y,
                distance: 0.0,
            }),
            "a square in the ground plane stands across it at the origin"
        );
        assert_eq!(
            plane_of(Quad.build(&assets)),
            Some(MeshPlane {
                normal: Vec3::Z,
                distance: 0.0,
            }),
            "and one in the camera's own plane stands across that"
        );
        assert_eq!(plane_of(Cube.build(&assets)), None, "a cube lies in none");
        assert_eq!(
            plane_of(MeshData::new(corners(3), vec![0, 1, 2])),
            None,
            "and so do corners that name no plane between them"
        );
    }

    #[test]
    fn flat_draws_of_one_world_plane_name_it_the_same_and_a_lifted_one_names_another() {
        let flat = built(Plane.build(&Assets::default()))
            .plane()
            .expect("it is flat");
        let laid = |across: f32, at: Vec3| {
            flat.placed(Transform::from_scale_rotation_translation(
                Vec3::splat(across),
                Quat::IDENTITY,
                at,
            ))
            .equation()
        };

        assert_eq!(
            laid(40.0, Vec3::ZERO),
            laid(3.0, Vec3::new(4.0, 0.0, -2.0)),
            "a square laid on a ground of another size names the same plane"
        );
        assert_ne!(
            laid(40.0, Vec3::ZERO),
            laid(3.0, Vec3::new(4.0, 0.015, -2.0)),
            "and one lifted off that ground names another"
        );
    }
}