mirage-engine 0.2.0

//! The flagged lights' depth maps: where they are held, what is drawn into
//! them, and the matrices the forward pass samples them by.

use core::f32::consts::FRAC_PI_2;

use bytemuck::{Pod, Zeroable};

use crate::Camera;
use crate::assets::Textures;
use crate::gpu::DEPTH_FORMAT;
use crate::light::{GpuLight, Kind, Light, NO_SHADOW};
use crate::math::camera::rh::proj::directx::{orthographic, perspective};
use crate::math::camera::rh::view::look_at_mat4;
use crate::math::{Mat4, UVec2, Vec3, Vec4};
use crate::overrun::Overrun;
use crate::renderer::draw_list::Batch;
use crate::renderer::passes::{SKIN, Scene};
use crate::renderer::pipelines::Skinning;

pub(crate) use crate::light::MAX_SHADOWS;

/// The side a depth map has where none is configured, in texels.
pub(crate) const DEFAULT_RESOLUTION: u32 = 2048;

/// The smallest side a depth map may be configured to, in texels.
pub(crate) const SMALLEST_RESOLUTION: u32 = 256;

/// The largest side a depth map may be configured to, in texels.
pub(crate) const LARGEST_RESOLUTION: u32 = 4096;

/// The six directions a lamp draws its cube along, each with an up it is not
/// parallel to; `forward.wgsl` chooses between them in this order.
const FACES: [(Vec3, Vec3); 6] = [
    (Vec3::X, Vec3::Y),
    (Vec3::NEG_X, Vec3::Y),
    (Vec3::Y, Vec3::Z),
    (Vec3::NEG_Y, Vec3::Z),
    (Vec3::Z, Vec3::Y),
    (Vec3::NEG_Z, Vec3::Y),
];

/// Map cap one frame can draw: six faces each for four lamps.
pub(crate) const MAX_MAPS: usize = MAX_SHADOWS * FACES.len();

/// Map count a sun is drawn into, one per slice of the camera's view;
/// `forward.wgsl` walks them in the order they are fitted.
const CASCADES: usize = 3;

/// The ratio between the extents a cascade may be fitted at, `2^(1/4)`:
/// dense enough that a map keeps close to the slice it covers, wide enough
/// that a turning camera takes few steps of it.
const EXTENT_STEP: f32 = 1.189_207_1;

/// Nearest distance to a lamp or a cone a caster is still drawn at.
const NEAR: f32 = 0.05;

/// The largest angle a cone's map opens to; a larger one has no usable
/// projection.
const WIDEST_CONE: f32 = 2.9;

/// The texels a cascade keeps around what it must hold, so that holding its
/// center to whole texels never pushes a corner out.
const SLACK: f32 = 4.0;

/// The corners of the space a camera projects into, which its inverse takes
/// back to the world.
const CORNERS: [Vec3; 8] = [
    Vec3::new(-1.0, -1.0, 0.0),
    Vec3::new(1.0, -1.0, 0.0),
    Vec3::new(-1.0, 1.0, 0.0),
    Vec3::new(1.0, 1.0, 0.0),
    Vec3::new(-1.0, -1.0, 1.0),
    Vec3::new(1.0, -1.0, 1.0),
    Vec3::new(-1.0, 1.0, 1.0),
    Vec3::new(1.0, 1.0, 1.0),
];

/// Everything one frame's lights cast: the lights as the shader reads
/// them, the maps to draw, and the index the forward pass samples them by.
#[derive(Default)]
pub(crate) struct Plan {
    lights: Vec<GpuLight>,
    wide: Vec<Cast>,
    faces: Vec<Cast>,
    sampled: Vec<GpuMap>,
    /// Each flagged sun's cascades as fitted last frame, kept by the sun
    /// they belong to, so that submission order does not move them from one
    /// sun to another; a sun that stops casting is dropped.
    ladders: Vec<Held>,
    overrun: Overrun,
}

impl Plan {
    /// Plans what `lights` cast, in submission order, over maps `side` texels
    /// across.
    fn run(&mut self, lights: &[Light], camera: Camera, aspect: f32, side: u32) {
        self.lights.clear();
        self.wide.clear();
        self.faces.clear();
        self.sampled.clear();
        self.ladders
            .retain(|held| lights.iter().any(|light| held.belongs_to(light)));

        let mut casting = 0;
        for light in lights {
            let shadow = if !light.casts {
                NO_SHADOW
            } else if casting == MAX_SHADOWS {
                self.overrun.report(format_args!(
                    "a frame flagged more than {MAX_SHADOWS} lights to cast; ignoring one"
                ));
                NO_SHADOW
            } else {
                match self.fit(light, camera, aspect, side) {
                    Ok(first) => {
                        casting += 1;
                        first
                    }
                    Err(Missing::Reach) => {
                        log::debug!(
                            "a light that reaches nowhere was flagged to cast; ignoring it"
                        );
                        NO_SHADOW
                    }
                    Err(Missing::Slice) => {
                        log::debug!(
                            "a sun was flagged to cast, but the camera leaves it no slice to \
                             cover; ignoring it"
                        );
                        NO_SHADOW
                    }
                }
            };
            self.lights.push(GpuLight::new(light, shadow));
        }
    }

    /// Adds the maps `light` needs, a sun fitted over the ladders it holds
    /// from the frames before; the light reads the first map, and the rest
    /// follow it in the order `forward.wgsl` walks them.
    fn fit(
        &mut self,
        light: &Light,
        camera: Camera,
        aspect: f32,
        side: u32,
    ) -> Result<i32, Missing> {
        let first = self.sampled.len() as i32;
        // The light a relief's texels are offset towards. A lamp passes its
        // six faces this one position, so each face takes the same depth of
        // a texel and the seams agree.
        let towards = match light.kind {
            Kind::Directional => (-light.direction).extend(0.0),
            Kind::Point | Kind::Spot => light.position.extend(1.0),
        };
        match light.kind {
            Kind::Directional => {
                let held = self.holding(light.direction);
                let cascades = sun(
                    light.direction,
                    camera,
                    aspect,
                    side,
                    &mut self.ladders[held].ladders,
                )?;
                for fit in cascades {
                    self.push_wide(fit, side, towards);
                }
            }
            Kind::Spot => self.push_wide(light.cone_map().ok_or(Missing::Reach)?, side, towards),
            Kind::Point => {
                let half = half_of(side);
                for face in light.cube_maps().ok_or(Missing::Reach)? {
                    self.push_face(face, half, towards);
                }
            }
        }
        Ok(first)
    }

    /// The index the steps a sun pointing along `direction` holds are kept
    /// at, starting it at none where no frame has fitted it yet.
    fn holding(&mut self, direction: Vec3) -> usize {
        let sun = Sunlight::new(direction);
        if let Some(held) = self.ladders.iter().position(|held| held.sun == sun) {
            return held;
        }
        self.ladders.push(Held {
            sun,
            ladders: [Ladder::default(); CASCADES],
        });

        self.ladders.len() - 1
    }

    /// Takes a map at the configured side, which a sun or a cone draws one of.
    fn push_wide(&mut self, fit: Mat4, side: u32, towards: Vec4) {
        self.sampled.push(GpuMap::new(fit, side, self.wide.len()));
        self.wide.push(Cast::new(fit, towards, UVec2::splat(side)));
    }

    /// Takes a map at half that side, which a lamp draws six of.
    fn push_face(&mut self, fit: Mat4, side: u32, towards: Vec4) {
        self.sampled.push(GpuMap::new(fit, side, self.faces.len()));
        self.faces.push(Cast::new(fit, towards, UVec2::splat(side)));
    }

    /// The frame's lights, each reading whatever map the plan left it.
    pub(crate) fn lights(&self) -> &[GpuLight] {
        &self.lights
    }

    /// The maps the forward pass samples, from the index each light
    /// holds.
    pub(crate) fn sampled(&self) -> &[GpuMap] {
        &self.sampled
    }

    /// Each map as it is drawn, in the order the maps are drawn.
    pub(crate) fn casters(&self) -> impl Iterator<Item = Cast> {
        self.wide.iter().chain(&self.faces).copied()
    }
}

impl Light {
    /// The map a cone draws what it lights into: as wide as the cone, out to
    /// its range. Absent where it points nowhere or reaches no further than
    /// [`NEAR`].
    fn cone_map(&self) -> Option<Mat4> {
        if self.direction == Vec3::ZERO || self.range <= NEAR {
            return None;
        }
        let spread = (2.0 * self.cone.clamp(-1.0, 1.0).acos()).min(WIDEST_CONE);
        let view = look_at_mat4(
            self.position,
            self.position + self.direction,
            up_from(self.direction),
        );

        Some(perspective(spread, 1.0, NEAR, self.range) * view)
    }

    /// The cube a lamp draws into: six square maps out to its range, in the
    /// order [`FACES`] lists them. Absent where it reaches no further than
    /// [`NEAR`].
    fn cube_maps(&self) -> Option<[Mat4; 6]> {
        if self.range <= NEAR {
            return None;
        }
        let projection = perspective(FRAC_PI_2, 1.0, NEAR, self.range);

        Some(FACES.map(|(direction, up)| {
            projection * look_at_mat4(self.position, self.position + direction, up)
        }))
    }
}

/// The reason a flagged light was left without a map.
#[derive(Clone, Copy, Debug)]
enum Missing {
    /// It points nowhere, or extends no further than its own `near` plane.
    Reach,
    /// The camera leaves a sun no slice to fit a cascade to.
    Slice,
}

/// A step of the extent ladder: the power of [`EXTENT_STEP`] an extent is
/// held up to.
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
struct Rung(i32);

impl Rung {
    /// The smallest step that covers `extent`; absent where there is nothing
    /// to cover.
    fn over(extent: f32) -> Option<Self> {
        (extent > 0.0).then(|| Self(extent.log(EXTENT_STEP).ceil() as i32))
    }

    /// The step's extent.
    fn extent(self) -> f32 {
        EXTENT_STEP.powi(self.0)
    }

    /// Whether a cascade at this step covers what `needed` requires and is no
    /// more than a step larger than it.
    fn holds(self, needed: Self) -> bool {
        (self.0 - 1..=self.0).contains(&needed.0)
    }
}

/// The steps one cascade was fitted at, across the light and into it.
#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
struct Ladder {
    across: Option<Rung>,
    deep: Option<Rung>,
}

/// One sun's cascades as they were last fitted, and the sun they belong to.
struct Held {
    sun: Sunlight,
    ladders: [Ladder; CASCADES],
}

impl Held {
    /// Whether these are the steps `light` is fitted over.
    fn belongs_to(&self, light: &Light) -> bool {
        light.casts && light.kind == Kind::Directional && self.sun == Sunlight::new(light.direction)
    }
}

/// The sun a [`Held`] is kept for: the direction it points, by bits, which
/// is all its cascades are fitted from. Two lights pointing the same way are
/// fitted the same and share one; a sun that turns takes a new one.
#[derive(Clone, Copy, Eq, PartialEq)]
struct Sunlight([u32; 3]);

impl Sunlight {
    fn new(direction: Vec3) -> Self {
        Self(direction.to_array().map(f32::to_bits))
    }
}

/// One viewpoint a pass draws through: what it projects the world by, what
/// its light is — a lamp's position, or a sun's direction, the last lane
/// holding `1.0` for a position and `0.0` for a direction — and what a draw
/// lying in a plane reads that plane's depth through, and what a place in
/// the space it projects into is read back to the world through.
///
/// The camera's own slot leaves the light empty. The caster stages read it
/// to offset a relief's texels from the plane towards the light.
#[repr(C)]
#[derive(Clone, Copy, Debug, Pod, Zeroable)]
pub(crate) struct Cast {
    view_projection: Mat4,
    towards: Vec4,
    read_plane: Mat4,
}

impl Cast {
    /// The camera's own viewpoint, over a target `size` pixels across, which
    /// holds no light.
    pub(crate) fn camera(view_projection: Mat4, size: UVec2) -> Self {
        Self::new(view_projection, Vec4::ZERO, size)
    }

    /// One drawn from `towards`, over a map `size` pixels across.
    ///
    /// A viewpoint that projects the world flat has no inverse: its draws
    /// take the depth of their own corners.
    fn new(view_projection: Mat4, towards: Vec4, size: UVec2) -> Self {
        Self {
            view_projection,
            towards,
            read_plane: read_plane(view_projection, size),
        }
    }
}

/// What a world plane is taken through to give its own depth over a target
/// `size` across: the plane comes back as four coefficients over that
/// target's own coordinates, which `forward.wgsl` divides to get the depth
/// of one place on that plane. A target one coordinate across leaves them
/// over the `0..1` a map is sampled by.
///
/// A viewpoint that projects the world flat has no inverse, and a plane read
/// through it comes back empty.
fn read_plane(view_projection: Mat4, size: UVec2) -> Mat4 {
    let unproject = match view_projection.determinant() == 0.0 {
        true => Mat4::ZERO,
        false => view_projection.inverse(),
    };
    let window = Mat4::from_cols(
        Vec4::new(2.0 / size.x as f32, 0.0, 0.0, -1.0),
        Vec4::new(0.0, -2.0 / size.y as f32, 0.0, 1.0),
        Vec4::Z,
        Vec4::W,
    );

    window * unproject.transpose()
}

/// One depth map as the shader reads it: what it projects the world by,
/// which layer holds it, one texel of it across the map, and what a world
/// plane's own depth over that map is read through.
#[repr(C)]
#[derive(Clone, Copy, Debug, Pod, Zeroable)]
pub(crate) struct GpuMap {
    view_projection: Mat4,
    texel: f32,
    layer: u32,
    /// Holds `read_plane` to the 16-byte alignment WGSL reads it at;
    /// `bytemuck` needs padding written out.
    _padding: [u32; 2],
    read_plane: Mat4,
}

impl GpuMap {
    /// The map `view_projection` fits, `side` texels across, at `layer` of
    /// its own array.
    ///
    /// A map that projects the world flat leaves every tap of the shader
    /// compared at the one depth.
    fn new(view_projection: Mat4, side: u32, layer: usize) -> Self {
        Self {
            view_projection,
            texel: 1.0 / side as f32,
            layer: layer as u32,
            _padding: [0; 2],
            read_plane: read_plane(view_projection, UVec2::ONE),
        }
    }
}

/// Where a sun's cascades hand over to each other, as `forward.wgsl` reads
/// them: the depth along the view each slice ends at, one lane per cascade,
/// and the share of a slice one hands over across in the lane past them.
#[repr(C)]
#[derive(Clone, Copy, Debug, Pod, Zeroable)]
pub(crate) struct Handover {
    ends: Vec3,
    share: f32,
}

impl Handover {
    /// End of each slice, as a fraction of the reach past the camera's
    /// `near` plane. Geometric by four: the nearest map covers the first
    /// 12.5 meters at full density, and the widest covers every meter of the
    /// reach at a 0.1 meter texel.
    const SPLITS: [f32; CASCADES] = [0.0625, 0.25, 1.0];

    /// The distance from the camera the slices reach, in meters. Casters
    /// still draw this far again behind what the cascades cover, so a wall
    /// the reach's length outside a cascade's own box still records in it.
    const REACH: f32 = 200.0;

    /// The share of its own slice a cascade hands over to the one past it
    /// across, at the end of that slice; for the widest cascade it is the
    /// last 20 meters of a 200 meter reach, fading out to no shadow at all.
    const SHARE: f32 = 0.1;

    /// Where `camera`'s own slices end, and the share each one hands over
    /// across.
    pub(crate) fn of(camera: Camera) -> Self {
        Self {
            ends: Vec3::from(Self::ends(camera)),
            share: Self::SHARE,
        }
    }

    /// End distance of each of `camera`'s slices: [`Self::SPLITS`] of the
    /// reach past its `near` plane.
    fn ends(camera: Camera) -> [f32; CASCADES] {
        let near = camera.projection().near();
        let reach = Self::reach(camera);

        Self::SPLITS.map(|split| near + reach * split)
    }

    /// The reach `camera` leaves the slices: [`Self::REACH`], or what its
    /// lens holds inside that.
    fn reach(camera: Camera) -> f32 {
        let lens = camera.projection();

        (lens.far() - lens.near()).min(Self::REACH)
    }
}

/// The depth maps a frame's flagged lights draw into, and what the forward
/// pass samples them through.
pub(crate) struct Shadows {
    side: u32,
    layout: wgpu::BindGroupLayout,
    sampler: wgpu::Sampler,
    /// The view bound in place of an array of maps the frame has no light
    /// for.
    absent: wgpu::TextureView,
    wide: Option<Array>,
    faces: Option<Array>,
    bindings: wgpu::BindGroup,
    plan: Plan,
}

impl Shadows {
    pub(crate) fn new(device: &wgpu::Device, side: u32) -> Self {
        let layout = device.create_bind_group_layout(&wgpu::BindGroupLayoutDescriptor {
            label: Some("mirage-engine shadows"),
            entries: &[sampled(0), sampled(1), compared(2)],
        });
        let sampler = device.create_sampler(&wgpu::SamplerDescriptor {
            label: Some("mirage-engine shadows"),
            address_mode_u: wgpu::AddressMode::ClampToEdge,
            address_mode_v: wgpu::AddressMode::ClampToEdge,
            address_mode_w: wgpu::AddressMode::ClampToEdge,
            mag_filter: wgpu::FilterMode::Linear,
            min_filter: wgpu::FilterMode::Linear,
            compare: Some(wgpu::CompareFunction::LessEqual),
            ..Default::default()
        });
        let absent = Array::new(device, 1, 1).sampled;
        let bindings = bind(device, &layout, &sampler, &absent, &absent);

        Self {
            side,
            layout,
            sampler,
            absent,
            wide: None,
            faces: None,
            bindings,
            plan: Plan::default(),
        }
    }

    /// Plans what `lights` cast and builds the arrays of maps it requires,
    /// keeping every array already large enough.
    pub(crate) fn prepare(
        &mut self,
        device: &wgpu::Device,
        lights: &[Light],
        camera: Camera,
        aspect: f32,
    ) {
        self.plan.run(lights, camera, aspect, self.side);

        let wide = rebuilt(&mut self.wide, device, self.side, self.plan.wide.len());
        let faces = rebuilt(
            &mut self.faces,
            device,
            half_of(self.side),
            self.plan.faces.len(),
        );
        if wide || faces {
            self.bindings = bind(
                device,
                &self.layout,
                &self.sampler,
                self.wide.as_ref().map_or(&self.absent, Array::sampled),
                self.faces.as_ref().map_or(&self.absent, Array::sampled),
            );
        }
    }

    /// The plan this frame's lights cast, as the last
    /// [`prepare`](Shadows::prepare) planned it.
    pub(crate) fn plan(&self) -> &Plan {
        &self.plan
    }

    pub(crate) fn layout(&self) -> &wgpu::BindGroupLayout {
        &self.layout
    }

    pub(crate) fn bindings(&self) -> &wgpu::BindGroup {
        &self.bindings
    }

    /// The layers this frame draws into, in the order its maps are drawn.
    fn drawn<'a>(&'a self) -> impl Iterator<Item = &'a wgpu::TextureView> {
        let layers = |array: &'a Option<Array>| array.iter().flat_map(|held| &held.layers);
        layers(&self.wide)
            .take(self.plan.wide.len())
            .chain(layers(&self.faces).take(self.plan.faces.len()))
    }
}

/// One array of depth maps: a layer each caster pass draws into, and the view
/// the forward pass samples all of them through.
struct Array {
    sampled: wgpu::TextureView,
    layers: Vec<wgpu::TextureView>,
}

impl Array {
    fn new(device: &wgpu::Device, side: u32, layers: u32) -> Self {
        let texture = device.create_texture(&wgpu::TextureDescriptor {
            label: Some("mirage-engine shadows"),
            size: wgpu::Extent3d {
                width: side,
                height: side,
                depth_or_array_layers: layers,
            },
            mip_level_count: 1,
            sample_count: 1,
            dimension: wgpu::TextureDimension::D2,
            format: DEPTH_FORMAT,
            usage: wgpu::TextureUsages::RENDER_ATTACHMENT | wgpu::TextureUsages::TEXTURE_BINDING,
            view_formats: &[],
        });

        Self {
            sampled: texture.create_view(&wgpu::TextureViewDescriptor {
                dimension: Some(wgpu::TextureViewDimension::D2Array),
                ..Default::default()
            }),
            layers: (0..layers)
                .map(|layer| {
                    texture.create_view(&wgpu::TextureViewDescriptor {
                        dimension: Some(wgpu::TextureViewDimension::D2),
                        base_array_layer: layer,
                        array_layer_count: Some(1),
                        ..Default::default()
                    })
                })
                .collect(),
        }
    }

    fn sampled(&self) -> &wgpu::TextureView {
        &self.sampled
    }
}

/// Fits a sun's cascades around the camera's view, out to where the
/// [`Handover`] ends them and densest first, each holding the step `ladders`
/// left it.
///
/// The steps are taken back only once every cascade is fitted, so a sun the
/// camera leaves no slice keeps the ones it held.
fn sun(
    direction: Vec3,
    camera: Camera,
    aspect: f32,
    side: u32,
    ladders: &mut [Ladder; CASCADES],
) -> Result<[Mat4; CASCADES], Missing> {
    if direction == Vec3::ZERO {
        return Err(Missing::Reach);
    }
    // The view turns the world without moving it, so that only the box that
    // is held to whole texels decides where a map lands.
    let view = look_at_mat4(Vec3::ZERO, direction, up_from(direction));
    let ends = Handover::ends(camera);
    let mut stepping = *ladders;
    let fitted: [Option<Mat4>; CASCADES] =
        core::array::from_fn(|at| cascade(view, camera, aspect, ends[at], side, &mut stepping[at]));
    let [nearest, between, widest] = fitted;
    let cascades = [
        nearest.ok_or(Missing::Slice)?,
        between.ok_or(Missing::Slice)?,
        widest.ok_or(Missing::Slice)?,
    ];
    *ladders = stepping;

    Ok(cascades)
}

/// Fits one cascade to the slice of the camera's view that ends `far`
/// meters out: the box that slice takes in the light's space, its extent held
/// to the step `ladder` is at and its center to whole texels of that step.
fn cascade(
    view: Mat4,
    camera: Camera,
    aspect: f32,
    far: f32,
    side: u32,
    ladder: &mut Ladder,
) -> Option<Mat4> {
    let (low, high) = boxed(view, frustum(camera, aspect, far)?);
    let half = (high - low) / 2.0;
    let across = stepped(&mut ladder.across, half.x.max(half.y))?;
    let deep = stepped(&mut ladder.deep, half.z)?;

    let extent = across * (1.0 + SLACK / side as f32);
    let texel = 2.0 * extent / side as f32;
    let middle = held((low + high) / 2.0, texel);
    let projection = orthographic(
        middle.x - extent,
        middle.x + extent,
        middle.y - extent,
        middle.y + extent,
        -middle.z - deep - Handover::REACH,
        -middle.z + deep,
    );

    Some(projection * view)
}

/// The least and the most `corners` reach along every axis of `view`.
fn boxed(view: Mat4, corners: [Vec3; 8]) -> (Vec3, Vec3) {
    corners.into_iter().fold(
        (Vec3::INFINITY, Vec3::NEG_INFINITY),
        |(low, high), corner| {
            let point = view.transform_point3(corner);
            (low.min(point), high.max(point))
        },
    )
}

/// Holds `extent` up to a step of [`EXTENT_STEP`], which keeps a cascade's
/// texels one size as the camera turns; absent where there is no extent to
/// hold.
///
/// The step `at` stays while the extent needs it or the step under it, so
/// that an extent at the edge of a step does not take a new one every frame.
fn stepped(at: &mut Option<Rung>, extent: f32) -> Option<f32> {
    let needed = Rung::over(extent)?;
    let rung = at.filter(|rung| rung.holds(needed)).unwrap_or(needed);
    *at = Some(rung);

    Some(rung.extent())
}

/// The eight world corners of the camera's view out to `far` meters;
/// absent where the lens leaves them undefined.
fn frustum(camera: Camera, aspect: f32, far: f32) -> Option<[Vec3; 8]> {
    let lens = camera.projection();
    if lens.near() >= far {
        return None;
    }

    let world = Camera::new(camera.view(), lens.clip(lens.near()..far))
        .view_projection(aspect)
        .inverse();
    let corners = CORNERS.map(|corner| world.project_point3(corner));

    corners
        .iter()
        .all(|corner| corner.is_finite())
        .then_some(corners)
}

/// Holds `center` to whole texels, which keeps a still sun's map from
/// shimmering as the camera moves.
fn held(center: Vec3, texel: f32) -> Vec3 {
    (center / texel).floor() * texel
}

/// An up `direction` is not parallel to, so that looking along it is total.
fn up_from(direction: Vec3) -> Vec3 {
    if direction.y.abs() > 0.99 {
        Vec3::Z
    } else {
        Vec3::Y
    }
}

/// The side a lamp's faces are drawn at, which is never nothing.
fn half_of(side: u32) -> u32 {
    (side / 2).max(1)
}

/// Draws the frame's casting batches into every map its flagged lights
/// requested; an additive draw is not one of them.
///
/// Every map draws the one record of each caster, so a lamp's six faces
/// take the same record and agree along their seams.
pub(crate) fn cast(encoder: &mut wgpu::CommandEncoder, scene: &Scene<'_>) {
    for (slot, layer) in scene.shadows.drawn().enumerate() {
        let mut pass = encoder.begin_render_pass(&wgpu::RenderPassDescriptor {
            label: Some("mirage-engine shadow"),
            color_attachments: &[],
            depth_stencil_attachment: Some(wgpu::RenderPassDepthStencilAttachment {
                view: layer,
                depth_ops: Some(wgpu::Operations {
                    load: wgpu::LoadOp::Clear(1.0),
                    store: wgpu::StoreOp::Store,
                }),
                stencil_ops: None,
            }),
            timestamp_writes: None,
            occlusion_query_set: None,
            multiview_mask: None,
        });

        pass.set_bind_group(0, scene.sky.frame(), &[scene.frame.caster_offset(slot)]);
        pass.set_vertex_buffer(1, scene.instances.slice(..));

        cast_into(
            &mut pass,
            scene.pipelines.caster(),
            scene.casters.plain(),
            scene,
            None,
        );
        cast_into(
            &mut pass,
            scene.pipelines.sampled_caster(),
            scene.casters.sampled(),
            scene,
            Some(scene.textures),
        );
    }
}

/// Draws `batches` into the map the pass is set to with `drawn`, binding
/// each batch's own texture where `sampled` holds textures.
///
/// A batch of a skinned mesh is drawn through the pipeline that blends the
/// palette its draws read, so a map records the pose a draw is drawn in.
fn cast_into(
    pass: &mut wgpu::RenderPass<'_>,
    drawn: &Skinning,
    batches: &[Batch],
    scene: &Scene<'_>,
    sampled: Option<&Textures>,
) {
    for run in batches.chunk_by(|batch, next| batch.skinned == next.skinned) {
        let Some(first) = run.first() else {
            continue;
        };
        pass.set_pipeline(drawn.of(first.skinned));
        for batch in run {
            let Some(mesh) = scene.meshes.uploaded(batch.mesh) else {
                continue;
            };
            if let Some(textures) = sampled {
                pass.set_bind_group(
                    1,
                    mesh.part_texture(batch.part)
                        .unwrap_or_else(|| textures.fallback()),
                    &[],
                );
            }
            pass.set_vertex_buffer(0, mesh.vertices().slice(..));
            if let Some(skin) = mesh.skin() {
                pass.set_vertex_buffer(SKIN, skin.slice(..));
            }
            pass.set_index_buffer(mesh.indices().slice(..), wgpu::IndexFormat::Uint32);
            pass.draw_indexed(batch.indices.clone(), 0, batch.instances.clone());
        }
    }
}

/// Builds `array` again where it holds fewer than `layers` maps, and reports
/// whether it did; a frame that flagged no light builds nothing.
fn rebuilt(array: &mut Option<Array>, device: &wgpu::Device, side: u32, layers: usize) -> bool {
    if layers == 0
        || array
            .as_ref()
            .is_some_and(|held| held.layers.len() >= layers)
    {
        return false;
    }
    *array = Some(Array::new(device, side, layers as u32));
    true
}

fn bind(
    device: &wgpu::Device,
    layout: &wgpu::BindGroupLayout,
    sampler: &wgpu::Sampler,
    wide: &wgpu::TextureView,
    faces: &wgpu::TextureView,
) -> wgpu::BindGroup {
    device.create_bind_group(&wgpu::BindGroupDescriptor {
        label: Some("mirage-engine shadows"),
        layout,
        entries: &[
            wgpu::BindGroupEntry {
                binding: 0,
                resource: wgpu::BindingResource::TextureView(wide),
            },
            wgpu::BindGroupEntry {
                binding: 1,
                resource: wgpu::BindingResource::TextureView(faces),
            },
            wgpu::BindGroupEntry {
                binding: 2,
                resource: wgpu::BindingResource::Sampler(sampler),
            },
        ],
    })
}

fn sampled(binding: u32) -> wgpu::BindGroupLayoutEntry {
    wgpu::BindGroupLayoutEntry {
        binding,
        visibility: wgpu::ShaderStages::FRAGMENT,
        ty: wgpu::BindingType::Texture {
            sample_type: wgpu::TextureSampleType::Depth,
            view_dimension: wgpu::TextureViewDimension::D2Array,
            multisampled: false,
        },
        count: None,
    }
}

fn compared(binding: u32) -> wgpu::BindGroupLayoutEntry {
    wgpu::BindGroupLayoutEntry {
        binding,
        visibility: wgpu::ShaderStages::FRAGMENT,
        ty: wgpu::BindingType::Sampler(wgpu::SamplerBindingType::Comparison),
        count: None,
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::{Color, Projection, Spot, View};

    /// The side every map in these tests is drawn at.
    const SIDE: u32 = 512;

    /// The shape of the target they are fitted against.
    const ASPECT: f32 = 16.0 / 9.0;

    /// A camera up and back from a point on the `X` axis, looking at it.
    fn watching(offset: f32) -> Camera {
        Camera::new(
            View::look_at(Vec3::new(offset, 8.0, 12.0), Vec3::new(offset, 0.0, 0.0)),
            Projection::perspective(60.0),
        )
    }

    /// A cone positioned a meter up, pointing `direction`, `range` meters
    /// long.
    fn spot(direction: Vec3, range: f32) -> Spot {
        Spot {
            position: Vec3::Y,
            direction,
            color: Color::WHITE,
            range,
            angle: 0.5,
        }
    }

    /// The sun these tests fit, pointing down and across.
    fn sunlight() -> Vec3 {
        Vec3::new(-0.4, -1.0, -0.6).normalize()
    }

    /// The same camera turned `degrees` about the point it looks at.
    fn turned(degrees: f32) -> Camera {
        let (sin, cos) = degrees.to_radians().sin_cos();
        Camera::new(
            View::look_at(Vec3::new(12.0 * sin, 8.0, 12.0 * cos), Vec3::ZERO),
            Projection::perspective(60.0),
        )
    }

    /// A camera whose lens leaves a slice no depth to be fitted over.
    fn flattened() -> Camera {
        Camera::new(
            View::look_at(Vec3::new(0.0, 8.0, 12.0), Vec3::ZERO),
            Projection::perspective(60.0).clip(50.0..50.0),
        )
    }

    /// The cascades [`sun`] fits for `camera`, holding no step from a frame
    /// before.
    fn cascades(camera: Camera) -> [Mat4; CASCADES] {
        fitting(camera, &mut [Ladder::default(); CASCADES])
    }

    /// The same, over the steps `ladders` holds.
    fn fitting(camera: Camera, ladders: &mut [Ladder; CASCADES]) -> [Mat4; CASCADES] {
        sun(sunlight(), camera, ASPECT, SIDE, ladders).expect("a sun points somewhere")
    }

    /// What one texel of a map `fit` projects the world by measures across
    /// it, in meters: the world width it spans is two of the map's own
    /// coordinates over the length of its first row.
    fn world_texel(fit: Mat4, side: u32) -> f32 {
        2.0 / (fit.row(0).truncate().length() * side as f32)
    }

    fn planned(lights: &[Light]) -> Plan {
        let mut plan = Plan::default();
        plan.run(lights, watching(0.0), ASPECT, SIDE);
        plan
    }

    fn casting(plan: &Plan) -> usize {
        plan.lights()
            .iter()
            .filter(|light| light.shadow != NO_SHADOW)
            .count()
    }

    #[test]
    fn a_map_stays_the_size_the_shader_steps_by() {
        assert_eq!(size_of::<GpuMap>(), 144);
    }

    #[test]
    fn every_cascade_covers_the_corners_of_the_slice_it_holds() {
        let camera = watching(0.0);

        for (fit, split) in cascades(camera).iter().zip(Handover::ends(camera)) {
            let slice = frustum(camera, ASPECT, split).expect("a plain camera has corners");
            for corner in slice {
                let inside = fit.project_point3(corner);
                assert!(
                    inside.x.abs() <= 1.0
                        && inside.y.abs() <= 1.0
                        && inside.z > 0.0
                        && inside.z < 1.0,
                    "{corner} is drawn but sits at {inside} in its map"
                );
            }
        }
    }

    #[test]
    fn a_flagged_sun_costs_three_maps_nested_finest_first() {
        let plan = planned(&[Light::directional(sunlight(), Color::WHITE).shadow()]);
        let maps = plan.sampled();

        assert_eq!(casting(&plan), 1, "which are one light of the four");
        assert_eq!(maps.len(), CASCADES);
        assert_eq!(plan.casters().count(), CASCADES);
        for (finer, wider) in maps.iter().zip(&maps[1..]) {
            assert!(
                world_texel(finer.view_projection, SIDE) < world_texel(wider.view_projection, SIDE),
                "a nearer cascade takes finer texels than the one past it"
            );
        }
    }

    #[test]
    fn the_nearest_cascade_covers_only_the_meters_it_is_split_at() {
        let camera = watching(0.0);
        let fitted = cascades(camera);
        let ahead = |meters: f32| {
            let view = camera.view();
            view.eye() + (view.target() - view.eye()).normalize() * meters
        };
        let holds = |fit: &Mat4, point: Vec3| {
            let inside = fit.project_point3(point);
            inside.x.abs() <= 1.0 && inside.y.abs() <= 1.0
        };

        let ends = Handover::ends(camera);

        assert!(
            holds(&fitted[0], ahead(ends[0] / 4.0)),
            "a point well inside the nearest slice is near"
        );
        assert!(
            !holds(&fitted[0], ahead(ends[1])),
            "and the end of the slice past it is not"
        );
        assert!(
            holds(&fitted[CASCADES - 1], ahead(ends[1])),
            "so the widest has that one"
        );
    }

    #[test]
    fn a_still_suns_cascades_hold_while_the_camera_drifts_under_a_texel() {
        // One ladder across the frames of a walk, as a frame's plan holds it.
        let landing = |at: usize, offset: f32, ladders: &mut [Ladder; CASCADES]| {
            fitting(watching(offset), ladders)[at].project_point3(Vec3::ZERO)
        };
        let distinct = |steps: [Vec3; 16]| {
            steps
                .iter()
                .enumerate()
                .filter(|&(at, landed)| {
                    !steps[..at]
                        .iter()
                        .any(|held| held.abs_diff_eq(*landed, 1e-6))
                })
                .count()
        };

        for (at, &fit) in cascades(watching(0.0)).iter().enumerate() {
            let under_a_texel = world_texel(fit, SIDE) / 32.0;
            let mut drifted = [Ladder::default(); CASCADES];
            let mut moved = [Ladder::default(); CASCADES];
            let drifting =
                core::array::from_fn(|step| landing(at, step as f32 * under_a_texel, &mut drifted));
            let moving = core::array::from_fn(|step| landing(at, step as f32 * 2.0, &mut moved));

            // The center is held to texels on three axes, and a walk shorter
            // than one ticks each of them at most once.
            assert!(
                distinct(drifting) <= 4,
                "a drift under a texel ticks map {at} by a texel at most, once per axis"
            );
            assert!(
                distinct(moving) >= 8,
                "and a move of meters moves it every time"
            );
        }
    }

    #[test]
    fn a_camera_that_clips_past_the_first_split_is_still_fitted_three_maps() {
        let clipped = Camera::new(
            View::look_at(Vec3::new(0.0, 8.0, 12.0), Vec3::ZERO),
            Projection::perspective(60.0).clip(8.0..40.0),
        );
        let fitted = cascades(clipped);

        for (&finer, &wider) in fitted.iter().zip(&fitted[1..]) {
            assert!(
                world_texel(finer, SIDE) < world_texel(wider, SIDE),
                "the slices are split between the near plane and the reach"
            );
        }
    }

    #[test]
    fn a_camera_that_clips_past_the_reach_is_still_fitted_three_maps() {
        let distant = Camera::new(
            View::look_at(Vec3::new(0.0, 8.0, 12.0), Vec3::ZERO),
            Projection::perspective(60.0).clip(60.0..1000.0),
        );
        let fitted = cascades(distant);

        assert_eq!(
            Handover::ends(distant)[CASCADES - 1],
            260.0,
            "the reach is measured from the near plane, not to it"
        );
        assert!(
            Handover::ends(distant).iter().all(|&split| split > 60.0),
            "so every slice ends past that plane"
        );
        for (&finer, &wider) in fitted.iter().zip(&fitted[1..]) {
            assert!(world_texel(finer, SIDE) < world_texel(wider, SIDE));
        }
    }

    #[test]
    fn a_camera_whose_lens_holds_no_depth_leaves_a_sun_without_a_map() {
        let mut plan = Plan::default();
        plan.run(
            &[Light::directional(sunlight(), Color::WHITE).shadow()],
            flattened(),
            ASPECT,
            SIDE,
        );

        assert_eq!(casting(&plan), 0);
        assert!(plan.sampled().is_empty());
        assert!(
            matches!(
                sun(
                    sunlight(),
                    flattened(),
                    ASPECT,
                    SIDE,
                    &mut [Ladder::default(); CASCADES],
                ),
                Err(Missing::Slice)
            ),
            "for want of a slice to cover, not of a light that reaches"
        );
        assert!(
            matches!(
                sun(
                    Vec3::ZERO,
                    watching(0.0),
                    ASPECT,
                    SIDE,
                    &mut [Ladder::default(); CASCADES],
                ),
                Err(Missing::Reach)
            ),
            "where a sun pointing nowhere reaches nothing to cover"
        );
    }

    #[test]
    fn a_sun_the_camera_leaves_no_slice_holds_the_steps_it_was_fitted_at() {
        let mut ladders = [Ladder::default(); CASCADES];
        fitting(watching(0.0), &mut ladders);
        let fitted = ladders;

        assert!(sun(sunlight(), flattened(), ASPECT, SIDE, &mut ladders).is_err());
        assert_eq!(ladders, fitted, "so the next frame fits from where it was");
    }

    #[test]
    fn two_suns_swapping_places_in_a_frame_each_hold_their_own_step() {
        let slanted = Light::directional(sunlight(), Color::WHITE).shadow();
        let overhead =
            Light::directional(Vec3::new(1.0, -4.0, 0.0).normalize(), Color::WHITE).shadow();
        let mut plan = Plan::default();
        // The nearest cascade of each of the two, in the order they were
        // submitted.
        let mut nearest = |lights: [Light; 2]| {
            plan.run(&lights, watching(0.0), ASPECT, SIDE);
            [
                world_texel(plan.sampled()[0].view_projection, SIDE),
                world_texel(plan.sampled()[CASCADES].view_projection, SIDE),
            ]
        };

        let [slanted_texel, overhead_texel] = nearest([slanted, overhead]);
        assert_ne!(
            slanted_texel, overhead_texel,
            "the two are fitted a step apart"
        );
        for _ in 0..3 {
            assert_eq!(
                nearest([overhead, slanted]),
                [overhead_texel, slanted_texel],
                "a sun holds the step it is at however the frame ordered it"
            );
            assert_eq!(
                nearest([slanted, overhead]),
                [slanted_texel, overhead_texel]
            );
        }
    }

    #[test]
    fn a_step_holds_while_the_extent_it_covers_hovers_at_its_boundary() {
        let mut rung = None;
        let step = stepped(&mut rung, 10.0).expect("an extent has a step");
        let stepped_up = stepped(&mut rung, step * 1.001).expect("and so does a wider one");

        assert!(stepped_up > step, "an extent past its step steps up");
        for hovering in [0.999, 1.0001, 0.9, 1.0009] {
            assert_eq!(
                stepped(&mut rung, step * hovering),
                Some(stepped_up),
                "and holds there while what it covers hovers at the boundary"
            );
        }
        assert_eq!(
            stepped(&mut rung, step / 2.0),
            Rung::over(step / 2.0).map(Rung::extent),
            "a drop of more than a step falls to what covers it"
        );
    }

    #[test]
    fn a_cascade_holds_its_step_while_the_camera_hovers_at_a_boundary() {
        let zoomed = |degrees: f32| {
            Camera::new(
                View::look_at(Vec3::new(0.0, 8.0, 12.0), Vec3::ZERO),
                Projection::perspective(degrees),
            )
        };
        let texel = |degrees, ladders: &mut [Ladder; CASCADES]| {
            world_texel(fitting(zoomed(degrees), ladders)[0], SIDE)
        };
        let fresh = |degrees| texel(degrees, &mut [Ladder::default(); CASCADES]);

        // The largest angle takes more than a step of extent over the
        // smallest, so halving between them lands on a boundary.
        let (mut under, mut over) = (30.0f32, 60.0f32);
        for _ in 0..40 {
            let between = (under + over) / 2.0;
            if fresh(between) == fresh(under) {
                under = between;
            } else {
                over = between;
            }
        }
        assert_ne!(fresh(under), fresh(over), "the two sit either side of one");

        let mut ladders = [Ladder::default(); CASCADES];
        let hovering: Vec<f32> = (0..8)
            .map(|frame| texel(if frame % 2 == 0 { under } else { over }, &mut ladders))
            .collect();

        assert!(
            hovering[1..].iter().all(|&reading| reading == hovering[1]),
            "but one cascade fitted across them holds the step it stepped up to"
        );
    }

    #[test]
    fn a_suns_cascades_hold_their_texels_to_steps_while_the_camera_turns() {
        let view = look_at_mat4(Vec3::ZERO, sunlight(), up_from(sunlight()));
        let turning: [f32; 8] = core::array::from_fn(|step| step as f32 * 0.5);
        let distinct = |readings: [f32; 8]| {
            let mut sorted = readings;
            sorted.sort_by(f32::total_cmp);
            sorted
                .iter()
                .zip(&sorted[1..])
                .filter(|(a, b)| a < b)
                .count()
                + 1
        };

        for at in 0..CASCADES {
            let texels = turning.map(|degrees| world_texel(cascades(turned(degrees))[at], SIDE));
            assert!(
                distinct(texels) <= 2,
                "a turn holds a cascade's texels the size they were, or one step from it"
            );
        }

        let boxes = turning.map(|degrees| {
            let camera = turned(degrees);
            let slice = frustum(camera, ASPECT, Handover::ends(camera)[0])
                .expect("a plain camera has corners");
            let (low, high) = boxed(view, slice);
            (high.x - low.x).max(high.y - low.y)
        });
        assert_eq!(
            distinct(boxes),
            turning.len(),
            "though the box each cascade holds is a different size at every angle"
        );
    }

    #[test]
    fn a_frame_that_flags_no_light_draws_no_maps() {
        let plan = planned(&[
            Light::directional(Vec3::NEG_Y, Color::WHITE),
            Light::spot(spot(Vec3::NEG_Y, 8.0)),
            Light::point(Vec3::Y, Color::WHITE, 10.0),
        ]);

        assert_eq!(casting(&plan), 0);
        assert_eq!(plan.casters().count(), 0, "so no pass is encoded for one");
        assert!(plan.sampled().is_empty());
    }

    #[test]
    fn only_four_lights_of_a_frame_cast() {
        let flagged = Light::directional(Vec3::NEG_Y, Color::WHITE).shadow();
        let plan = planned(&[flagged; MAX_SHADOWS + 2]);

        assert_eq!(casting(&plan), MAX_SHADOWS);
        assert_eq!(plan.sampled().len(), MAX_SHADOWS * CASCADES);
    }

    #[test]
    fn a_lamp_costs_six_maps_and_one_of_the_four() {
        let flagged = Light::point(Vec3::Y, Color::WHITE, 10.0).shadow();
        let plan = planned(&[flagged; MAX_SHADOWS + 1]);

        assert_eq!(casting(&plan), MAX_SHADOWS);
        assert_eq!(plan.sampled().len(), MAX_MAPS);
        assert_eq!(plan.casters().count(), MAX_MAPS);
    }

    #[test]
    fn a_light_that_reaches_nowhere_is_left_without_a_map() {
        let plan = planned(&[
            Light::directional(Vec3::ZERO, Color::WHITE).shadow(),
            Light::spot(spot(Vec3::ZERO, 4.0)).shadow(),
            Light::point(Vec3::Y, Color::WHITE, 0.0).shadow(),
        ]);

        assert_eq!(casting(&plan), 0);
        assert!(plan.sampled().is_empty());
    }

    #[test]
    fn a_target_with_no_shape_leaves_a_sun_without_a_map() {
        let mut plan = Plan::default();
        plan.run(
            &[Light::directional(Vec3::NEG_Y, Color::WHITE).shadow()],
            watching(0.0),
            0.0,
            SIDE,
        );

        assert_eq!(casting(&plan), 0);
    }

    #[test]
    fn holding_a_center_to_texels_quantizes_it() {
        assert_eq!(
            held(Vec3::new(0.6, -0.6, 1.0), 0.25),
            Vec3::new(0.5, -0.75, 1.0)
        );
        assert_eq!(held(Vec3::splat(0.5), 0.25), held(Vec3::splat(0.7), 0.25));
    }
}