Skip to content

The animation engine for agents: blazingly fast math and 3D videos with Manim's Python API, on a Rust GPU core.

Python
97.7 KB
Raw Blame
//! A view's paths, drawn with analytic segment coverage (see `vector.wgsl`): flattened per
//! frame on the GPU to the size they are drawn at through the view's camera (projectively in 3D),
//! their segment areas accumulated into a float atlas and composited per 16×16 tile in depth order
//! (the draw order among equal depths: a 2D view's whole order), each pixel kept as two regions. A
//! 2D view's point clouds and meshes are drawn by the raster pipeline (`blend.wgsl`), each alone in
//! its rectangle of a raster atlas, which the composite lays in its place in the order; a 3D view's
//! are its raster base, z-buffered, which the composite lays at its depth per pixel.
//!
//! A view's objects are composited in groups that fit the atlases, in draw order, each group over
//! what the ones before it made; a pixel two groups share is settled at the seam between them (its
//! two regions merged). Only a view whose objects overflow the atlases has more than one group.

use bytemuck::{Pod, Zeroable};

use super::{Camera, Kind, Mat34, NONE, Paint, ROUND, Record, SQUARE, Shape, Store, compose};

const TILE: u32 = 16;
const ATLAS_WIDTH: u32 = 4096;

/// One object as the shader reads it (432 bytes; see `vector.wgsl`).
#[repr(C)]
#[derive(Clone, Copy, Pod, Zeroable)]
struct Object {
    t1x: [f32; 4],
    t1y: [f32; 4],
    t2x: [f32; 4],
    t2y: [f32; 4],
    t1w: [f32; 4], // rows w of the projective map: pixel = (x, y) / w (a 2D view's: (0, 0, 0, 1) and 0)
    t2w: [f32; 4],
    rect: [f32; 4], // its box: corner (view pixels, y down), size
    atlas: [u32; 4],
    ids: [u32; 4],
    params: [f32; 4],
    dash: [f32; 4],
    scale: [f32; 4],
    /// where it lies in depth, z = a (x - x0) + b (y - y0) + c over view pixels from its reference point (`flags`, zw:
    /// its flat's first path's box's corner, else its own), so c, the depth there, keeps its digits (from the view's
    /// corner a steep plane's terms outweigh its depth by orders, and their f32 sum lost them) (a 2D view's: 0, its
    /// order alone decides), and CE's light added to its gradients
    place: [f32; 4],
    // its strokes' depth per pixel (x: a 3D view's path that is not planar); clipped by the near plane (y); its depth
    // plane's reference point (zw: whole view pixels)
    flags: [u32; 4],
    /// its first fill slot, first stroke slot (of its group's); segments a curve is cut into at most, dash windows a
    /// segment meets at most (1: not dashed)
    slots: [u32; 4],
    pieces: [u32; 4], // records a joint takes, a cap; dash windows a subpath meets at most (1: not dashed)
    paint: Paint,
    material: [f32; 4], // metallic, roughness, reflectance; 1 where its fill is lit by the view's lights
    normal: [f32; 4],   // which way its plane faces in the world (a lit fill's)
    t1z: [f32; 4],      // rows of its depth from the far plane (z - w, clip's): a non-planar path's strokes' is z / w
    t2z: [f32; 4],
    near: [f32; 4],     // a clipped object's shadows on the near plane (`flags`, y): see `plan`
}

#[repr(C)]
#[derive(Clone, Copy, Pod, Zeroable)]
struct FrameUniform {
    size: [f32; 4],
    tiles: [u32; 4],
    counts: [u32; 4],
    background: [f32; 4],
    depth: [f32; 4],
    lists: [u32; 4],
    inverse: [[f32; 4]; 4], // clip -> world (columns): a 3D view's
    light: [f32; LIGHT],    // toward the viewer, the eye, lighting, the lights (see `Plan::light`)
}

/// A 3D view's light as its composite reads it (`vector.wgsl`'s `Frame`, from `toward`): the unit vector toward the
/// viewer, where it sees from, how many lights with the exposure and the tone mapping, 8 lights of 32 floats
/// (`light.wgsl`'s `Light`), and its environment's diffuse light (9 vectors).
pub(crate) const LIGHT: usize = 12 + 32 * 8 + 36 + 4;

/// A 3D view's see-through points lie among its pixels' this many nearest layers, a slab between each two (as
/// `vector.wgsl`'s `SLABS`; `blend_lists.wgsl` writes them as targets, all in one pass).
pub(crate) const SLABS: usize = 4;

/// A 3D view's see-through fragments for its composite: its lists (heads, nodes: see `blend.wgsl`), the rows whose
/// heads are this frame's, its samples per pixel, and its raster base's samples (color, depth; with lit meshes, their
/// light: `Out::Color`'s `light`) to lay among them.
pub(crate) struct Listed<'a> {
    pub(crate) heads: &'a wgpu::Buffer,
    pub(crate) nodes: &'a wgpu::Buffer,
    pub(crate) rows: [u32; 2],
    pub(crate) samples: u32,
    pub(crate) colors: &'a wgpu::TextureView,
    pub(crate) depths: &'a wgpu::TextureView,
    pub(crate) lights: Option<&'a wgpu::TextureView>,
}

/// Rectangles packed row by row (a row as tall as its tallest), `width` wide.
#[derive(Clone, Copy)]
struct Shelves {
    width: u32,
    x: u32,
    y: u32,
    row: u32,
}

impl Shelves {
    fn new(width: u32) -> Self {
        Self { width, x: 0, y: 0, row: 0 }
    }

    fn rows(&self) -> u32 {
        self.y + self.row
    }

    /// Where a `w`×`h` rectangle goes (x | y << 16), if the rows stay within `limit`.
    fn place(&mut self, w: u32, h: u32, limit: u32) -> Option<u32> {
        let (mut x, mut y, mut row) = (self.x, self.y, self.row);
        if x + w > self.width {
            (x, y, row) = (0, y + row, 0);
        }
        if y + h > limit || w > self.width {
            return None;
        }
        (self.x, self.y, self.row) = (x + w, y, row.max(h));
        Some(x | (y << 16))
    }
}

/// A point cloud or mesh of a 2D view: record `record`, drawn by the raster pipeline into `rect`
/// of the raster atlas (x, y, width, height), which shows the view from `corner` (pixels, y down).
pub(crate) struct Raster {
    pub(crate) record: usize,
    pub(crate) rect: [u32; 4],
    corner: [f32; 2],
}

/// Consecutive objects of a view whose layers fit the atlases: the tiles each reaches, and the
/// slots of the records their flattening can write (fill, stroke).
pub(crate) struct Group {
    objects: Vec<Object>,
    spans: Vec<[u32; 4]>, // first tile x, y, last tile x, y
    masks: Vec<Option<Vec<u8>>>, // which of those tiles each layer can cover (`tile_masks`; none: all, every layer)
    coverage: Shelves,
    raster: Shelves,
    pub(crate) rasters: Vec<Raster>,
    fills: u32,
    strokes: u32,
}

/// A 2D view, planned: its groups, in draw order.
pub(crate) struct Plan {
    pub(crate) groups: Vec<Group>,
    pub(crate) raster_size: [u32; 2], // the part of the raster atlas its groups draw into
    size: [u32; 2],
    background: [f32; 4],
    bias: f32,              // depth units within which paths lie on one another and on the raster base (a 2D view's: 0)
    inverse: [[f32; 4]; 4], // clip -> world (columns)
    pub(crate) lit: bool,   // whether a path of it is lit (its composite's pipeline: with the light)
    crossings: bool,        // whether its depths can cross (a 3D view's: its composite's second pass)
    pub(crate) light: [f32; LIGHT], // what lights its paths with a material (all 0: none; see `FrameUniform`)
}

impl Plan {
    /// Where a raster is drawn: the view's clip space mapped into its rectangle of the raster
    /// atlas (x ↦ scale·x + bias·w, y alike), and the view's pixels (y up) moved by `shift`.
    pub(crate) fn place(&self, raster: &Raster) -> Place {
        let ([w, h], [aw, ah]) = (self.size.map(|v| v as f32), self.raster_size.map(|v| v as f32));
        let offset = [raster.rect[0] as f32 - raster.corner[0], raster.rect[1] as f32 - raster.corner[1]];
        Place { scale: [w / aw, h / ah], bias: [(w + 2.0 * offset[0]) / aw - 1.0, 1.0 - (h + 2.0 * offset[1]) / ah], shift: [offset[0], ah - h - offset[1]] }
    }
}

/// A raster's map from its view into the raster atlas (see `Plan::place`).
#[derive(Clone, Copy)]
pub(crate) struct Place {
    pub(crate) scale: [f32; 2],
    pub(crate) bias: [f32; 2],
    pub(crate) shift: [f32; 2],
}

/// Pixels per unit of one term (rows x, y, w) of a projective map, in its worst direction, where the whole map
/// (every term's rows added) gives pixel (px, py) and w: the largest singular value of its Jacobian there (the quotient
/// rule; an affine map's: `stretch`).
fn stretch_at(x: &[f32; 4], y: &[f32; 4], w: &[f32; 4], [px, py]: [f32; 2], ww: f32) -> f32 {
    let jx = [0, 1, 2].map(|i| (x[i] - px * w[i]) / ww);
    let jy = [0, 1, 2].map(|i| (y[i] - py * w[i]) / ww);
    stretch(&[jx[0], jx[1], jx[2], 0.0], &[jy[0], jy[1], jy[2], 0.0])
}

/// The inverse of a projection (rows), as the shader takes a matrix (columns); a view that has none (singular), 0.
fn inverse(rows: &super::Mat4) -> [[f32; 4]; 4] {
    let mut a: [[f64; 8]; 4] = std::array::from_fn(|i| std::array::from_fn(|j| if j < 4 { rows[i][j] as f64 } else if j - 4 == i { 1.0 } else { 0.0 }));
    for c in 0..4 {
        let p = (c..4).max_by(|&x, &y| a[x][c].abs().total_cmp(&a[y][c].abs())).expect("a row");
        if a[p][c].abs() < 1e-12 {
            return [[0.0; 4]; 4];
        }
        a.swap(c, p);
        let d = a[c][c];
        a[c] = a[c].map(|x| x / d);
        for r in 0..4 {
            if r != c {
                let f = a[r][c];
                a[r] = std::array::from_fn(|j| a[r][j] - f * a[c][j]);
            }
        }
    }
    std::array::from_fn(|col| std::array::from_fn(|row| a[row][4 + col] as f32))
}

/// The plane z = a x + b y + c nearest to points (x, y, z) (least squares). Points on a line on screen (a straight
/// path, a plane seen edge on) fix only the depth along it: the plane that varies along the line alone (the least-norm
/// one); a single point, a flat plane at its depth.
fn fit_plane(points: &[[f64; 3]]) -> [f64; 3] {
    if points.is_empty() {
        return [0.0; 3];
    }
    let n = points.len() as f64;
    let mean = [0, 1, 2].map(|i| points.iter().map(|p| p[i]).sum::<f64>() / n);
    let (mut sxx, mut sxy, mut syy, mut sxz, mut syz) = (0.0, 0.0, 0.0, 0.0, 0.0);
    for p in points {
        let (x, y, z) = (p[0] - mean[0], p[1] - mean[1], p[2] - mean[2]);
        (sxx, sxy, syy, sxz, syz) = (sxx + x * x, sxy + x * y, syy + y * y, sxz + x * z, syz + y * z);
    }
    let det = sxx * syy - sxy * sxy;
    let (a, b) = if det.abs() > 1e-9 * (sxx * syy).max(1e-30) {
        ((sxz * syy - syz * sxy) / det, (syz * sxx - sxz * sxy) / det)
    } else if sxx + syy > 1e-12 {
        // along the line's direction u (the spread's principal axis, eigenvalue l): z = mean + s (u . (p - mean))
        let l = 0.5 * (sxx + syy) + (0.25 * (sxx - syy) * (sxx - syy) + sxy * sxy).sqrt();
        let (ux, uy) = if sxy.abs() > 1e-12 { (sxy, l - sxx) } else if sxx >= syy { (1.0, 0.0) } else { (0.0, 1.0) };
        let m = (ux * ux + uy * uy).sqrt();
        let (ux, uy) = (ux / m, uy / m);
        let s = (ux * sxz + uy * syz) / (ux * ux * sxx + 2.0 * ux * uy * sxy + uy * uy * syy);
        (s * ux, s * uy)
    } else {
        (0.0, 0.0)
    };
    [a, b, mean[2] - a * mean[0] - b * mean[1]]
}

/// A 3D view's paths' flats: the planes (and lines) they lie in, decided in the world, once a frame, as exactly as
/// their points are known: each path's own plane (its shape's three plane points through its placement, a morph's
/// two terms' summed) joins the first flat that holds all three points within 32 ulps of their magnitude, or starts
/// one. A straight path (its points on a line) joins a plane that holds it; else its stroke lies in the plane of the
/// nearest flat it runs along (parallel to it: a grid line over a floor, its whole width over the floor); else it
/// faces the camera, as a line of its own. The paths of a flat share its depth over the view, the same numbers (so
/// where they meet their draw order decides, as in a 2D view), whatever the camera; other paths compare depths alone.
#[derive(Default)]
struct Flats {
    of: std::collections::HashMap<usize, usize>, // record -> its flat
    points: Vec<[[f64; 3]; 3]>,                  // each flat's: three points of its plane in the world (a line's: on it)
}

/// Place plane witnesses without rounding their basis into a different plane. In-plane
/// principal axes may rotate freely when their spreads coincide; only the plane matters.
fn world_plane(a: &Shape, b: Option<&Shape>, record: &Record) -> [[f64; 3]; 3] {
    let at = |m: &Mat34, p: [f64; 3], translate: bool| [0, 1, 2].map(|k| m[k][0] as f64 * p[0] + m[k][1] as f64 * p[1] + m[k][2] as f64 * p[2] + if translate { m[k][3] as f64 } else { 0.0 });
    std::array::from_fn(|i| {
        let first = at(&record.m1, a.plane[i], true);
        let second = b.map_or([0.0; 3], |b| at(&record.m2, b.plane[i], false));
        [0, 1, 2].map(|k| first[k] + second[k])
    })
}

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

    #[test]
    fn a_planes_projection_does_not_depend_on_its_principal_axes() {
        // Equal in-plane spreads have no preferred eigenbasis. Tiny changes can rotate
        // the witnesses by a large angle, but must not rotate or translate their plane.
        for perturbation in [-f64::EPSILON, 0.0, f64::EPSILON] {
            let mut points = [[-1.0, -1.0, 0.0], [1.0, -1.0, 0.0], [1.0, 1.0, 0.0], [-1.0, 1.0, 0.0]];
            points[0][0] += perturbation;
            let mut store = Store::default();
            store.add_path(1, &points, &[[0, 1, 1, 0]], [0.0; 3], [0.0, 0.0, 1.0]);
            let shape = store.shapes.get(&1).unwrap();
            for offset in [0.0f32, 100.0, 100_000.0] {
                let m = [[0.81, 0.24, 0.55, offset], [0.44, 0.93, -0.14, -offset], [0.37, -0.62, 0.89, offset]];
                let record = Record::filled(1, 1, m, [1.0; 4]);
                let placed = world_plane(shape, None, &record);
                let actual = fit_plane(&placed);
                let m = m.map(|row| row.map(f64::from));
                let determinant = m[0][0] * m[1][1] - m[0][1] * m[1][0];
                let a = (m[2][0] * m[1][1] - m[2][1] * m[1][0]) / determinant;
                let b = (m[0][0] * m[2][1] - m[0][1] * m[2][0]) / determinant;
                // Evaluate the fitted plane where the shape actually lies. Intercepts
                // alone are ill-conditioned for a plane translated far from the origin.
                for x in [-1.0, 0.0, 1.0] {
                    for y in [-1.0, 0.0, 1.0] {
                        let wanted = m[2][3] + a * x + b * y;
                        let found = actual[0] * (m[0][3] + x) + actual[1] * (m[1][3] + y) + actual[2];
                        assert!((wanted - found).abs() <= 8.0 * f64::EPSILON * (1.0 + offset as f64), "{perturbation} {offset}: {wanted} != {found}");
                    }
                }
            }
        }
    }
}

fn flats(store: &Store, records: &[Record], order: &[usize]) -> Flats {
    type P = [f64; 3];
    let sub = |a: P, b: P| -> P { [a[0] - b[0], a[1] - b[1], a[2] - b[2]] };
    let add = |a: P, b: P| -> P { [a[0] + b[0], a[1] + b[1], a[2] + b[2]] };
    let dot = |a: P, b: P| a[0] * b[0] + a[1] * b[1] + a[2] * b[2];
    let cross = |a: P, b: P| -> P { [a[1] * b[2] - a[2] * b[1], a[2] * b[0] - a[0] * b[2], a[0] * b[1] - a[1] * b[0]] };
    let unit = |a: P| -> P {
        let l = dot(a, a).sqrt();
        if l > 0.0 { a.map(|x| x / l) } else { [1.0, 0.0, 0.0] }
    };
    // a flat: a point of it, a unit vector (a plane's normal, a line's direction), whether it is a line
    let mut known: Vec<(P, P, bool)> = Vec::new();
    let mut lines: Vec<(usize, [P; 3], f64)> = Vec::new();
    let mut out = Flats::default();
    let near = |points: &[P; 3], scale: f64, (o, u, line): (P, P, bool)| {
        let tol = 32.0 * f32::EPSILON as f64 * scale;
        points.iter().all(|&p| {
            let d = sub(p, o);
            if line {
                let c = cross(d, u);
                dot(c, c) <= tol * tol
            } else {
                dot(d, u).abs() <= tol
            }
        })
    };
    for &k in order {
        let r = &records[k];
        let Some(a) = store.shapes.get(&r.key1).filter(|s| s.kind == Kind::Path) else { continue };
        if r.flags & super::OVERLAY != 0 {
            continue; // in the frame, not the scene
        }
        let b = if r.key2 == 0 { None } else { store.shapes.get(&r.key2) };
        let points = world_plane(a, b, r);
        let scale = points.iter().flat_map(|p| p.iter()).fold(1.0f64, |m, x| m.max(x.abs()));
        let (u, v) = (sub(points[1], points[0]), sub(points[2], points[0]));
        let n = cross(u, v);
        let span = dot(u, u).max(dot(v, v));
        if dot(n, n) <= (64.0 * f32::EPSILON as f64).powi(2) * span * span {
            lines.push((k, points, scale)); // a line: placed once every plane is known
            continue;
        }
        let f = known.iter().position(|&flat| !flat.2 && near(&points, scale, flat)).unwrap_or_else(|| {
            known.push((points[0], unit(n), false));
            out.points.push(points);
            known.len() - 1
        });
        out.of.insert(k, f);
    }
    let planes = known.len();
    for (k, points, scale) in lines {
        let along = {
            let (u, v) = (sub(points[1], points[0]), sub(points[2], points[0]));
            unit(if dot(u, u) >= dot(v, v) { u } else { v })
        };
        let f = known.iter().position(|&flat| near(&points, scale, flat)).unwrap_or_else(|| {
            // the nearest plane it runs along gives its stroke's plane: through it, parallel to that plane
            let parallel = known[..planes].iter().filter(|(_, n, _)| dot(along, *n).abs() <= 1e-5).min_by(|(o, n, _), (p, m, _)| dot(sub(points[0], *o), *n).abs().total_cmp(&dot(sub(points[0], *p), *m).abs()));
            match parallel {
                Some(&(_, n, _)) => {
                    known.push((points[0], unit(n), false));
                    out.points.push([points[0], add(points[0], along), add(points[0], cross(n, along))]);
                }
                None => {
                    known.push((points[0], along, true));
                    out.points.push([points[0], add(points[0], along), add(points[0], along.map(|x| 2.0 * x))]);
                }
            }
            known.len() - 1
        });
        out.of.insert(k, f);
    }
    out
}

/// The largest singular value of a 2×3 map's linear part: pixels per unit in its worst direction.
fn stretch(x: &[f32; 4], y: &[f32; 4]) -> f32 {
    let (a, b, c) = (x[0] * x[0] + x[1] * x[1] + x[2] * x[2], x[0] * y[0] + x[1] * y[1] + x[2] * y[2], y[0] * y[0] + y[1] * y[1] + y[2] * y[2]);
    let m = 0.5 * (a + c);
    (m + (0.25 * (a - c) * (a - c) + b * b).sqrt()).sqrt()
}

/// The triangles of a round piece's fan over half a turn at radius `half` (pixels): its chords
/// within 1/32 px of the arc, as the shader's `fan` (one more for its rounding).
fn fan(half: f32) -> u32 {
    let step = 2.0 * (1.0 - 0.03125 / half).max(-1.0).acos();
    (std::f32::consts::PI / step).ceil().clamp(1.0, 128.0) as u32 + 1
}

/// The tiles (first x, y, last x, y) a box of view pixels reaches.
fn span([x0, y0, x1, y1]: [f32; 4], [tx, ty]: [u32; 2]) -> [u32; 4] {
    let last = |v: f32, tiles: u32| (((v as u32).max(1) - 1) / TILE).min(tiles - 1);
    [x0 as u32 / TILE, y0 as u32 / TILE, last(x1, tx), last(y1, ty)]
}

/// Each tile's list of a group's objects (a counting sort), farthest first by their depth at the tile's center, in
/// draw order among equals (a 2D view's: its draw order), the order the composite expects (and checks): each tile's
/// first entry (and one past the end), then the entries: an object's index, and in its top byte which of its layers
/// can cover the tile (`tile_masks`; a tile none can is not listed).
fn tile_lists(spans: &[[u32; 4]], masks: &[Option<Vec<u8>>], objects: &[Object], tiles_x: u32, tiles: usize) -> Vec<u32> {
    // an object's mask at tile (tx, ty) of its span: its own, or (unclassified) every layer it shows
    let mask = |index: usize, tx: u32, ty: u32| -> u8 {
        let [x0, y0, x1, _] = spans[index];
        match &masks[index] {
            Some(m) => m[((ty - y0) * (x1 - x0 + 1) + (tx - x0)) as usize],
            None => {
                let atlas = objects[index].atlas;
                if atlas[3] != NONE { 1 } else { [1u8, 4, 8].iter().zip(atlas).filter(|(_, at)| *at != NONE).fold(0, |m, (bit, _)| m | bit) }
            }
        }
    };
    let mut starts = vec![0u32; tiles + 1];
    for (index, &[x0, y0, x1, y1]) in spans.iter().enumerate() {
        for ty in y0..=y1 {
            for tx in x0..=x1 {
                if mask(index, tx, ty) != 0 {
                    starts[(ty * tiles_x + tx) as usize + 1] += 1;
                }
            }
        }
    }
    for i in 0..tiles {
        starts[i + 1] += starts[i];
    }
    let mut at = starts.clone();
    let mut entries = vec![0u32; starts[tiles] as usize];
    for (index, &[x0, y0, x1, y1]) in spans.iter().enumerate() {
        for ty in y0..=y1 {
            for tx in x0..=x1 {
                let m = mask(index, tx, ty);
                if m != 0 {
                    let slot = &mut at[(ty * tiles_x + tx) as usize];
                    entries[*slot as usize] = index as u32 | (m as u32) << 24;
                    *slot += 1;
                }
            }
        }
    }
    for t in 0..tiles {
        let list = &mut entries[starts[t] as usize..starts[t + 1] as usize];
        if list.len() > 1 {
            let [cx, cy] = [(t as u32 % tiles_x) as f32 + 0.5, (t as u32 / tiles_x) as f32 + 0.5].map(|c| c * TILE as f32);
            let depth = |e: &u32| {
                let o = &objects[(*e & 0xff_ffff) as usize];
                o.place[0] * (cx - o.flags[2] as f32) + o.place[1] * (cy - o.flags[3] as f32) + o.place[2]
            };
            list.sort_by(|i, j| depth(j).total_cmp(&depth(i)));
        }
    }
    starts.extend(entries);
    starts
}

/// The boxes classified tile by tile: more tiles than this (else every tile, as a small box mostly is).
const BOXED: u32 = 16;

/// Which tiles of an object's box (`span`) each of its shown layers can cover, a byte a tile, row by row: its fill
/// where the fill's edges run (1) and inside them (2), its stroke where it runs (4), its background stroke (8). Its
/// curves run within their control points' hulls (seen through its projective map, whose weights are positive in
/// front of the camera), so a tile meets a layer only within the box of a curve's projected control points grown by
/// how far the layer reaches past the path (`reach`, in pixels); elsewhere a fill winds as its control polygon does
/// (the curves and the polygon differ only inside the hulls): a tile's centre wound around is inside. None: every
/// tile (a box of at most `BOXED` tiles).
fn tile_masks(store: &Store, a: &super::Shape, b: Option<&super::Shape>, rows: &[[f32; 4]; 6], span: [u32; 4], layers: [bool; 3], reach: [f32; 3]) -> Option<Vec<u8>> {
    let [tx0, ty0, tx1, ty1] = span;
    let (columns, lines) = (tx1 - tx0 + 1, ty1 - ty0 + 1);
    if columns * lines <= BOXED {
        return None;
    }
    let [t1x, t1y, t1w, t2x, t2y, t2w] = rows;
    let row = |t: &[f32; 4], p: [f32; 4]| t[0] * p[0] + t[1] * p[1] + t[2] * p[2] + t[3];
    // control point k of curve i, on the view: homogeneous (x, y, w), and divided
    let lift = |i: u32, k: u32| -> [f32; 3] {
        let p = store.ctrl[(4 * (a.curves.first + i) + k) as usize];
        let q = b.map_or([0.0; 4], |b| store.ctrl[(4 * (b.curves.first + i) + k) as usize]);
        [row(t1x, p) + row(t2x, q), row(t1y, p) + row(t2y, q), row(t1w, p) + row(t2w, q)]
    };
    let seen = |i: u32, k: u32| -> [f32; 2] {
        let h = lift(i, k);
        [h[0] / h[2], h[1] / h[2]]
    };
    let mut masks = vec![0u8; (columns * lines) as usize];
    let tile = TILE as f32;
    // each subpath's curves, in pieces (`split`), mark the tiles their pieces' boxes meet, grown by each layer's reach;
    // the pieces' ends make the subpath's outline, which keeps to its curves within the marked tiles (a piece lies in
    // its box, with its chord), closed by the subpath's return to its first point: the fill's edge too, marked for the
    // fill (whether or not the subpath closes itself: a fill closes it, a stroke does not)
    let mut edges: Vec<([f32; 2], [f32; 2])> = Vec::new();
    let mut pieces: Vec<[[f32; 3]; 4]> = Vec::new();
    let subpaths = (0..a.curves.subpaths).map(|s| store.ranges[(a.curves.first_subpath + s) as usize]).map(|r| (r[0], r[1]));
    let all = if a.curves.subpaths == 0 { vec![(0, a.curves.count)] } else { subpaths.collect() };
    for (first, end) in all {
        if end <= first {
            continue;
        }
        let start = seen(first, 0);
        let mut at = start;
        let mut walk = |h: [[f32; 3]; 4], shown: [bool; 3], masks: &mut [u8], at: &mut [f32; 2]| {
            pieces.clear();
            split(h, 0, tile, &mut pieces);
            for piece in &pieces {
                let points = piece.map(|p| [p[0] / p[2], p[1] / p[2]]);
                let (lo, hi) = points.iter().fold(([f32::MAX; 2], [f32::MIN; 2]), |(lo, hi), p| ([lo[0].min(p[0]), lo[1].min(p[1])], [hi[0].max(p[0]), hi[1].max(p[1])]));
                mark(masks, span, columns, (lo, hi), [0, 1, 2].map(|l| layers[l] && shown[l]), reach);
                edges.push((*at, points[3]));
                *at = points[3];
            }
        };
        for i in first..end {
            walk([0, 1, 2, 3].map(|k| lift(i, k)), [true; 3], &mut masks, &mut at);
        }
        if layers[0] && at != start {
            let (q, r) = (lift(end - 1, 3), lift(first, 0));
            let third = |t: f32| [0, 1, 2].map(|n| q[n] + (r[n] - q[n]) * t);
            walk([q, third(1.0 / 3.0), third(2.0 / 3.0), r], [true, false, false], &mut masks, &mut at);
        }
    }
    if layers[0] {
        // inside the fill: where its outlines wind around a tile's centre (a tile no piece's box meets lies off every
        // piece, where the curves wind as their outlines do)
        for ty in ty0..=ty1 {
            let cy = (ty as f32 + 0.5) * tile;
            let mut crossings: Vec<(f32, i32)> = edges
                .iter()
                .filter(|(p, q)| (p[1] <= cy) != (q[1] <= cy))
                .map(|(p, q)| (p[0] + (cy - p[1]) / (q[1] - p[1]) * (q[0] - p[0]), if q[1] > p[1] { 1 } else { -1 }))
                .collect();
            crossings.sort_by(|a, b| a.0.total_cmp(&b.0));
            for tx in tx0..=tx1 {
                let m = &mut masks[((ty - ty0) * columns + (tx - tx0)) as usize];
                if *m & 1 != 0 {
                    continue;
                }
                let cx = (tx as f32 + 0.5) * tile;
                let winding: i32 = crossings.iter().filter(|(x, _)| *x > cx).map(|(_, s)| s).sum();
                if winding != 0 {
                    *m |= 2;
                }
            }
        }
    }
    Some(masks)
}

/// A piece of a curve (its homogeneous control points), halved while its box is wide both ways (de Casteljau, exact
/// for the projected curve: its homogeneous control points are a polynomial's), so that a long straight or gently curved
/// run marks a band of tiles, not its whole box: its pieces, in order, into `out`.
fn split(h: [[f32; 3]; 4], depth: u32, tile: f32, out: &mut Vec<[[f32; 3]; 4]>) {
    let points = h.map(|p| [p[0] / p[2], p[1] / p[2]]);
    let (lo, hi) = points.iter().fold(([f32::MAX; 2], [f32::MIN; 2]), |(lo, hi), p| ([lo[0].min(p[0]), lo[1].min(p[1])], [hi[0].max(p[0]), hi[1].max(p[1])]));
    if depth < 10 && hi[0] - lo[0] > 2.0 * tile && hi[1] - lo[1] > 2.0 * tile {
        let mid = |a: [f32; 3], b: [f32; 3]| [0, 1, 2].map(|n| 0.5 * (a[n] + b[n]));
        let (p01, p12, p23) = (mid(h[0], h[1]), mid(h[1], h[2]), mid(h[2], h[3]));
        let (p012, p123) = (mid(p01, p12), mid(p12, p23));
        let centre = mid(p012, p123);
        split([h[0], p01, p012, centre], depth + 1, tile, out);
        split([centre, p123, p23, h[3]], depth + 1, tile, out);
        return;
    }
    out.push(h);
}

/// The tiles of a box of tiles (`span`, `columns` across) that a box in view pixels (`lo`, `hi`) meets, grown by each
/// shown layer's reach, marked as that layer's edges (its bit).
fn mark(masks: &mut [u8], span: [u32; 4], columns: u32, (lo, hi): ([f32; 2], [f32; 2]), shown: [bool; 3], reach: [f32; 3]) {
    let [tx0, ty0, tx1, ty1] = span;
    let tile = TILE as f32;
    for (layer, (&shown, &grow)) in shown.iter().zip(&reach).enumerate() {
        if !shown {
            continue;
        }
        let bit = [1u8, 4, 8][layer];
        let x0 = (((lo[0] - grow) / tile).floor().max(tx0 as f32) as u32).min(tx1 + 1);
        let x1 = (((hi[0] + grow) / tile).floor().min(tx1 as f32).max(-1.0)) as i64;
        let y0 = (((lo[1] - grow) / tile).floor().max(ty0 as f32) as u32).min(ty1 + 1);
        let y1 = (((hi[1] + grow) / tile).floor().min(ty1 as f32).max(-1.0)) as i64;
        for ty in y0 as i64..=y1 {
            for tx in x0 as i64..=x1 {
                masks[((ty as u32 - ty0) * columns + (tx as u32 - tx0)) as usize] |= bit;
            }
        }
    }
}

/// Place something in the last group or, where it does not fit, in a new one.
fn fit<T>(groups: &mut Vec<Group>, fresh: impl Fn() -> Group, mut place: impl FnMut(&mut Group) -> Option<T>) -> Result<T, String> {
    if let Some(at) = place(groups.last_mut().expect("a group")) {
        return Ok(at);
    }
    groups.push(fresh());
    place(groups.last_mut().expect("a group")).ok_or_else(|| "an object does not fit an empty atlas".into())
}

/// A new texture's view (which keeps it).
fn image(device: &wgpu::Device, label: &str, [width, height]: [u32; 2], format: wgpu::TextureFormat, usage: wgpu::TextureUsages) -> wgpu::TextureView {
    let texture = device.create_texture(&wgpu::TextureDescriptor {
        label: Some(label),
        size: wgpu::Extent3d { width, height, depth_or_array_layers: 1 },
        mip_level_count: 1,
        sample_count: 1,
        dimension: wgpu::TextureDimension::D2,
        format,
        usage,
        view_formats: &[],
    });
    texture.create_view(&Default::default())
}

fn buffer(device: &wgpu::Device, label: &str, size: u64, usage: wgpu::BufferUsages) -> wgpu::Buffer {
    device.create_buffer(&wgpu::BufferDescriptor { label: Some(label), size, usage, mapped_at_creation: false })
}

/// An array the passes read: a storage buffer, and the bytes it has room for.
struct Data(wgpu::Buffer, u64);

impl Data {
    fn new(device: &wgpu::Device, label: &str) -> Self {
        Self(buffer(device, label, 4096, wgpu::BufferUsages::STORAGE | wgpu::BufferUsages::COPY_DST), 4096)
    }

    /// `bytes`, written from its start (made anew, with room for them, where it has less).
    fn hold(&mut self, device: &wgpu::Device, queue: &wgpu::Queue, label: &str, bytes: &[u8]) {
        if self.1 < bytes.len() as u64 {
            self.1 = (bytes.len() as u64).next_power_of_two();
            self.0 = buffer(device, label, self.1, wgpu::BufferUsages::STORAGE | wgpu::BufferUsages::COPY_DST);
        }
        queue.write_buffer(&self.0, 0, bytes);
    }
}

/// A group's buffers: every group drawn in a frame has its own (all are written before any is
/// drawn).
struct GroupBuffers {
    uniform: wgpu::Buffer,
    objects: Data,
    tiles: Data,
}

/// The GPU's path coverage and view composition: its pipelines, and what they draw with.
pub(crate) struct Vector {
    limit: u32, // the largest texture side
    shader: wgpu::ShaderModule,
    single_shader: Option<wgpu::ShaderModule>, // the same composite with single-sample textures
    write_layout: wgpu::BindGroupLayout,
    flatten: [Option<wgpu::ComputePipeline>; 2], // independent fill and stroke records, made when needed
    composite: [Option<[wgpu::ComputePipeline; 2]>; 32], // by what a view lays (`LIT`, ...): the composite, `keep`; made when first needed
    crossing: [Option<[wgpu::ComputePipeline; 2]>; 32], // where depths cross: the count, the pixels (alike)
    crossings: (wgpu::Buffer, wgpu::Buffer, u64),      // their list, the second pass's workgroups; pixels it holds
    groups_layout: wgpu::BindGroupLayout,              // the workgroups, as the count writes them
    records: Option<(wgpu::Buffer, wgpu::Buffer, [u32; 2])>, // fill, stroke records' slots; how many they hold
    depth_layouts: [wgpu::BindGroupLayout; 2], // a 3D view's base depth from its raster depth: multisampled, single
    depth_resolve: [wgpu::ComputePipeline; 2],
    nothing: wgpu::Buffer,                      // a view's lists when it has none (and strokes' depths)
    stroke_depths: Option<(wgpu::Buffer, u64)>, // a non-planar path's strokes' depths, per pixel of the atlas
    no_samples: [[wgpu::TextureView; 2]; 2],         // its base's samples when it has none (color, depth)
    nearest: Option<(wgpu::BindGroupLayout, [wgpu::RenderPipeline; 2])>, // a light's map, a view's opaque depth, from its paths (made when first needed)
    bounds: Option<([wgpu::BindGroupLayout; 2], wgpu::ComputePipeline)>, // a 3D view's slab bounds: what they read, where they go (made when first needed)
    no_slabs: wgpu::TextureView, // a view's slabs when it has none: 1x1, one layer
    scene_layout: wgpu::BindGroupLayout,
    image_layout: [wgpu::BindGroupLayout; 2],
    read_layout: wgpu::BindGroupLayout,
    fill: wgpu::RenderPipeline,
    stroke: wgpu::RenderPipeline,
    groups: Vec<GroupBuffers>,
    used: usize, // groups drawn this frame
    atlas: Option<(wgpu::TextureView, [u32; 2])>,
    rows: u32, // the atlas rows this frame's plans have needed most
    scratch: Option<(wgpu::TextureView, [u32; 2])>, // where an overflowing view's groups alternate with its canvas
    carried: Option<([wgpu::TextureView; 2], [u32; 2])>, // and, a view with lit content, their light (in turn)
    no_light_out: wgpu::TextureView,                     // where a group that shows its pixels leaves no light: 1x1
    empty: wgpu::TextureView,
    base_depth: Option<(wgpu::TextureView, [u32; 2])>, // one float a pixel: its samples' nearest
    base: Option<(wgpu::TextureView, [u32; 2])>,       // its colour, which the raster passes resolve into
    base_light: Option<(wgpu::TextureView, [u32; 2])>, // with lit meshes: their light, beside it
    far: wgpu::TextureView,                            // a 2D view's base depth: 1x1, far
}

impl Vector {
    fn shader(device: &wgpu::Device, multisampled: bool) -> wgpu::ShaderModule {
        super::sampled_shader(device, "vector", &[include_str!("vector.wgsl"), include_str!("light.wgsl"), include_str!("vector_buffers.wgsl"), include_str!("vector_compute.wgsl")].concat(), multisampled)
    }

    pub(crate) fn new(device: &wgpu::Device, queue: &wgpu::Queue) -> Self {
        let limits = device.limits();
        let shader = Self::shader(device, true);
        let (vertex, fragment, compute) = (wgpu::ShaderStages::VERTEX, wgpu::ShaderStages::FRAGMENT, wgpu::ShaderStages::COMPUTE);
        // where the composite runs, and the accumulate pass
        let (composing, all) = (compute, wgpu::ShaderStages::VERTEX_FRAGMENT | compute);
        let entry = |binding, visibility, ty| wgpu::BindGroupLayoutEntry { binding, visibility, ty: wgpu::BindingType::Buffer { ty, has_dynamic_offset: false, min_binding_size: None }, count: None };
        let (read, rw) = (wgpu::BufferBindingType::Storage { read_only: true }, wgpu::BufferBindingType::Storage { read_only: false });
        let layout = |label, entries: &[wgpu::BindGroupLayoutEntry]| device.create_bind_group_layout(&wgpu::BindGroupLayoutDescriptor { label: Some(label), entries });
        let scene_layout = layout("vector scene", &[entry(0, all, wgpu::BufferBindingType::Uniform), entry(1, all, read), entry(2, all, read), entry(3, all, read), entry(4, all, read), entry(5, all, read)]);
        let texture = |binding| wgpu::BindGroupLayoutEntry { binding, visibility: composing, ty: wgpu::BindingType::Texture { sample_type: wgpu::TextureSampleType::Float { filterable: false }, view_dimension: wgpu::TextureViewDimension::D2, multisampled: false }, count: None };
        let sampled = |binding, sample_type, multisampled| wgpu::BindGroupLayoutEntry { binding, visibility: compute, ty: wgpu::BindingType::Texture { sample_type, view_dimension: wgpu::TextureViewDimension::D2, multisampled }, count: None };
        let target = |format| wgpu::BindingType::StorageTexture { access: wgpu::StorageTextureAccess::WriteOnly, format, view_dimension: wgpu::TextureViewDimension::D2 };
        // what its paths with a material are lit with: a 3D view's lights' shadow maps and their comparison, the DFG
        // table and its bilinear reads, its environment's cube, its ambient occlusion
        let maps = wgpu::BindGroupLayoutEntry { binding: 10, visibility: composing, ty: wgpu::BindingType::Texture { sample_type: wgpu::TextureSampleType::Depth, view_dimension: wgpu::TextureViewDimension::D2Array, multisampled: false }, count: None };
        let compare = wgpu::BindGroupLayoutEntry { binding: 11, visibility: composing, ty: wgpu::BindingType::Sampler(wgpu::SamplerBindingType::Comparison), count: None };
        let dfg = wgpu::BindGroupLayoutEntry { binding: 12, visibility: composing, ty: wgpu::BindingType::Texture { sample_type: wgpu::TextureSampleType::Float { filterable: true }, view_dimension: wgpu::TextureViewDimension::D2, multisampled: false }, count: None };
        let linear = wgpu::BindGroupLayoutEntry { binding: 13, visibility: composing, ty: wgpu::BindingType::Sampler(wgpu::SamplerBindingType::Filtering), count: None };
        let cube = wgpu::BindGroupLayoutEntry { binding: 15, visibility: composing, ty: wgpu::BindingType::Texture { sample_type: wgpu::TextureSampleType::Float { filterable: true }, view_dimension: wgpu::TextureViewDimension::Cube, multisampled: false }, count: None };
        // and a 3D view's see-through points' slabs, as many layers as `SLABS`
        let slabs = wgpu::BindGroupLayoutEntry { binding: 21, visibility: composing, ty: wgpu::BindingType::Texture { sample_type: wgpu::TextureSampleType::Float { filterable: false }, view_dimension: wgpu::TextureViewDimension::D2Array, multisampled: false }, count: None };
        let image_layout = [false, true].map(|multisampled| layout(
            "vector images",
            &[texture(0), texture(1), texture(2), wgpu::BindGroupLayoutEntry { binding: 3, visibility: compute, ty: target(super::COLOR), count: None }, texture(4), entry(5, compute, read), entry(6, compute, read), sampled(7, wgpu::TextureSampleType::Float { filterable: false }, multisampled), sampled(8, wgpu::TextureSampleType::Depth, multisampled), entry(9, compute, read), maps, compare, dfg, linear, entry(14, compute, rw), cube, texture(16), texture(17), sampled(18, wgpu::TextureSampleType::Float { filterable: false }, multisampled), wgpu::BindGroupLayoutEntry { binding: 19, visibility: compute, ty: target(super::RADIANCE), count: None }, texture(20), slabs],
        ));
        let read_layout = layout("records in", &[entry(0, vertex, read), entry(1, vertex, read), entry(2, fragment, rw)]);
        let pipeline_layout = |groups: &[Option<&wgpu::BindGroupLayout>]| device.create_pipeline_layout(&wgpu::PipelineLayoutDescriptor { label: None, bind_group_layouts: groups, immediate_size: 0 });
        let accumulate = pipeline_layout(&[Some(&scene_layout), None, None, Some(&read_layout)]);
        let add = wgpu::BlendState { color: wgpu::BlendComponent { src_factor: wgpu::BlendFactor::One, dst_factor: wgpu::BlendFactor::One, operation: wgpu::BlendOperation::Add }, alpha: wgpu::BlendComponent::REPLACE };
        let render = |label: &str, layout: &wgpu::PipelineLayout, vs: &str, fs: &str, targets: &[Option<wgpu::ColorTargetState>]| {
            device.create_render_pipeline(&wgpu::RenderPipelineDescriptor {
                label: Some(label),
                layout: Some(layout),
                vertex: wgpu::VertexState { module: &shader, entry_point: Some(vs), compilation_options: Default::default(), buffers: &[] },
                fragment: Some(wgpu::FragmentState { module: &shader, entry_point: Some(fs), compilation_options: Default::default(), targets }),
                primitive: wgpu::PrimitiveState::default(),
                depth_stencil: None,
                multisample: wgpu::MultisampleState::default(),
                multiview_mask: None,
                cache: None,
            })
        };
        let coverage = [Some(wgpu::ColorTargetState { format: wgpu::TextureFormat::R32Float, blend: Some(add), write_mask: wgpu::ColorWrites::ALL })];
        let (fill, stroke) = (render("vs_fill", &accumulate, "vs_fill", "fs_fill", &coverage), render("vs_stroke", &accumulate, "vs_stroke", "fs_stroke", &coverage));
        let write_layout = layout("records out", &[entry(0, compute, rw), entry(1, compute, rw)]);
        // a 3D view's base depth: its samples' nearest
        let depth_shader = device.create_shader_module(wgpu::ShaderModuleDescriptor { label: Some("base depth"), source: wgpu::ShaderSource::Wgsl(include_str!("depth.wgsl").into()) });
        let depth_entry = |binding, multisampled| wgpu::BindGroupLayoutEntry { binding, visibility: compute, ty: wgpu::BindingType::Texture { sample_type: wgpu::TextureSampleType::Depth, view_dimension: wgpu::TextureViewDimension::D2, multisampled }, count: None };
        let depth_out = wgpu::BindGroupLayoutEntry { binding: 2, visibility: compute, ty: wgpu::BindingType::StorageTexture { access: wgpu::StorageTextureAccess::WriteOnly, format: wgpu::TextureFormat::R32Float, view_dimension: wgpu::TextureViewDimension::D2 }, count: None };
        let depth_layouts = [layout("base depth (multisampled)", &[depth_entry(0, true), depth_out]), layout("base depth", &[depth_entry(1, false), depth_out])];
        let depth_resolve = [("nearest_of_samples", &depth_layouts[0]), ("single_sample", &depth_layouts[1])].map(|(entry, l)| {
            device.create_compute_pipeline(&wgpu::ComputePipelineDescriptor { label: Some(entry), layout: Some(&pipeline_layout(&[Some(l)])), module: &depth_shader, entry_point: Some(entry), compilation_options: Default::default(), cache: None })
        });
        let no_samples = [1, 4].map(|samples| [(super::COLOR, None), (super::DEPTH, Some(wgpu::TextureAspect::DepthOnly))].map(|(format, aspect)| {
            let texture = device.create_texture(&wgpu::TextureDescriptor {
                label: Some("no samples"),
                size: wgpu::Extent3d { width: 1, height: 1, depth_or_array_layers: 1 },
                mip_level_count: 1,
                sample_count: samples,
                dimension: wgpu::TextureDimension::D2,
                format,
                usage: wgpu::TextureUsages::RENDER_ATTACHMENT | wgpu::TextureUsages::TEXTURE_BINDING,
                view_formats: &[],
            });
            texture.create_view(&wgpu::TextureViewDescriptor { aspect: aspect.unwrap_or_default(), ..Default::default() })
        }));
        let far = {
            let t = device.create_texture(&wgpu::TextureDescriptor {
                label: Some("far"),
                size: wgpu::Extent3d { width: 1, height: 1, depth_or_array_layers: 1 },
                mip_level_count: 1,
                sample_count: 1,
                dimension: wgpu::TextureDimension::D2,
                format: wgpu::TextureFormat::R32Float,
                usage: wgpu::TextureUsages::TEXTURE_BINDING | wgpu::TextureUsages::COPY_DST,
                view_formats: &[],
            });
            queue.write_texture(t.as_image_copy(), &0.0f32.to_le_bytes(), wgpu::TexelCopyBufferLayout { offset: 0, bytes_per_row: Some(4), rows_per_image: Some(1) }, wgpu::Extent3d { width: 1, height: 1, depth_or_array_layers: 1 });
            t.create_view(&Default::default())
        };
        Self {
            limit: limits.max_texture_dimension_2d,
            shader,
            single_shader: None,
            write_layout,
            flatten: [None, None],
            composite: Default::default(),
            crossing: Default::default(),
            crossings: (buffer(device, "crossings", 16, wgpu::BufferUsages::STORAGE | wgpu::BufferUsages::COPY_DST), buffer(device, "crossing groups", 16, wgpu::BufferUsages::STORAGE | wgpu::BufferUsages::INDIRECT), 3),
            groups_layout: layout("crossing groups", &[entry(0, compute, rw)]),
            records: None,
            depth_layouts,
            depth_resolve,
            nothing: buffer(device, "nothing", 16, wgpu::BufferUsages::STORAGE),
            stroke_depths: None,
            no_samples,
            nearest: None,
            bounds: None,
            no_slabs: device
                .create_texture(&wgpu::TextureDescriptor { label: Some("no slabs"), size: wgpu::Extent3d { width: 1, height: 1, depth_or_array_layers: 1 }, mip_level_count: 1, sample_count: 1, dimension: wgpu::TextureDimension::D2, format: super::COLOR, usage: wgpu::TextureUsages::TEXTURE_BINDING, view_formats: &[] })
                .create_view(&wgpu::TextureViewDescriptor { dimension: Some(wgpu::TextureViewDimension::D2Array), ..Default::default() }),
            scene_layout,
            image_layout,
            read_layout,
            fill,
            stroke,
            groups: Vec::new(),
            used: 0,
            atlas: None,
            rows: 0,
            scratch: None,
            carried: None,
            no_light_out: image(device, "no light out", [1, 1], super::RADIANCE, wgpu::TextureUsages::STORAGE_BINDING),
            empty: image(device, "empty", [1, 1], super::COLOR, wgpu::TextureUsages::TEXTURE_BINDING),
            base_depth: None,
            base: None,
            base_light: None,
            far,
        }
    }

    /// Plan a 2D view: its records in `order`, a path each an object of the group whose coverage
    /// atlas its layers fit, a point cloud or mesh each a raster.
    pub(crate) fn plan(&self, store: &Store, camera: &Camera, records: &[Record], order: &[usize], background: [f32; 4]) -> Result<Plan, String> {
        let (w, h) = (camera.size[0], camera.size[1]);
        let size = [w as u32, h as u32];
        let tiles = [size[0].div_ceil(TILE), size[1].div_ceil(TILE)];
        let limit = self.limit;
        let fresh = || Group { objects: Vec::new(), spans: Vec::new(), masks: Vec::new(), coverage: Shelves::new(ATLAS_WIDTH.max(size[0])), raster: Shelves::new(size[0]), rasters: Vec::new(), fills: 0, strokes: 0 };
        let mut groups = vec![fresh()];
        // a 3D view's planes: the paths that lie in one share it, its depth over the view the same numbers for each
        let flats = if camera.three_d { flats(store, records, order) } else { Flats::default() };
        // each flat's depth over the view: its plane's three points through the camera, z / w from the far plane
        let depths: Vec<[f64; 3]> = flats.points.iter().map(|points| fit_plane(&points.map(|p| camera.seen(p)))).collect();
        // where each flat's depth is kept to its digits (`plane_depth`): its first path's box's corner, the same point
        // for all its paths, so they meet in it to the bit and their order decides
        let mut references: Vec<Option<[f32; 2]>> = vec![None; depths.len()];
        for &k in order {
            let r = &records[k];
            let a = store.shapes.get(&r.key1).ok_or_else(|| format!("unknown shape {}", r.key1))?;
            if a.kind != Kind::Path {
                let [x0, y0, x1, y1] = store.footprint(camera, r).unwrap_or([0.0, 0.0, w, h]); // (unbounded: the whole view)
                let [x0, y0, x1, y1] = [x0.floor().max(0.0), y0.floor().max(0.0), x1.ceil().min(w), y1.ceil().min(h)];
                if x1 <= x0 || y1 <= y0 {
                    continue;
                }
                let (rw, rh) = ((x1 - x0) as u32, (y1 - y0) as u32);
                let at = fit(&mut groups, fresh, |g| g.raster.place(rw, rh, limit))?;
                let group = groups.last_mut().expect("a group");
                group.rasters.push(Raster { record: k, rect: [at & 0xffff, at >> 16, rw, rh], corner: [x0, y0] });
                group.objects.push(Object { rect: [x0, y0, x1 - x0, y1 - y0], atlas: [NONE, NONE, NONE, at], ids: [NONE; 4], slots: [group.fills, group.strokes, 0, 0], ..Object::zeroed() });
                group.spans.push(span([x0, y0, x1, y1], tiles));
                group.masks.push(None);
                continue;
            }
            let b = if r.key2 == 0 { None } else { Some(store.shapes.get(&r.key2).ok_or_else(|| format!("unknown shape {}", r.key2))?) };
            if let Some(b) = b.filter(|b| b.curves.count != a.curves.count) {
                return Err(format!("morph between unaligned shapes ({} vs {} curves)", a.curves.count, b.curves.count));
            }
            let c = a.curves;
            let (sw, bw) = (r.params[2] * camera.unit, r.params[3] * camera.unit);
            let eye = camera.eye(r);
            let mut paint = store.paint(camera, &eye, r)?;
            let [fill, stroke, background] = [paint.fill, paint.stroke, paint.background].map(|c| c[3]);
            let layers = [fill > 0.0 || paint.brush[1] > 1, sw > 0.0 && (stroke > 0.0 || paint.brush[3] > 1), bw > 0.0 && background > 0.0];
            if c.count == 0 || layers == [false; 3] {
                continue;
            }
            // canonical point -> view pixel (y down), projectively: (x, y) / w through the camera's
            // clip w (a 2D view's is 1: its rows are the affine map's, term by term, arithmetic and all);
            // only term 1 carries the translation
            let pixels = |m: &Mat34, first: bool| {
                let t = compose(&eye, m, first);
                let x = [0, 1, 2, 3].map(|j| 0.5 * w * t[0][j] + 0.5 * w * t[3][j]);
                let y = [0, 1, 2, 3].map(|j| -0.5 * h * t[1][j] + 0.5 * h * t[3][j]);
                (x, y, t[3])
            };
            let (t1x, t1y, t1w) = pixels(&r.m1, true);
            let (t2x, t2y, t2w) = if b.is_some() { pixels(&r.m2, false) } else { ([0.0; 4], [0.0; 4], [0.0; 4]) };
            // rows of its depth from the far plane (z - w, clip's: exact where z / w is near 1): its depth plane's
            // points, a non-planar path's strokes' depth; and the near plane, z = 0, in front of which it shows
            let deep = camera.deep_eye(r);
            let (z1, z2) = if camera.three_d { (compose(&deep, &r.m1, true)[2], if b.is_some() { compose(&deep, &r.m2, false)[2] } else { [0.0; 4] }) } else { ([0.0; 4], [0.0; 4]) };
            // its box and how far its map stretches, over what can be seen of its boxes: the corners in front of the
            // near plane of the pairs of a point of term 1 and one of term 2 (a morph's; their rows add), and where
            // the pairs' box's edges cross the near plane (a box reaching behind it is `clipped`), a projective map of
            // the pair whose extremes over that part of the box are at those points (a 2D view's w is 1: the terms'
            // bounds add)
            let corners = |lo: [f32; 3], hi: [f32; 3]| -> [[f32; 3]; 8] { std::array::from_fn(|corner| [0, 1, 2].map(|i| if corner >> i & 1 == 0 { lo[i] } else { hi[i] })) };
            let (ones, twos) = (corners(a.lo, a.hi), b.map_or([[0.0; 3]; 8], |b| corners(b.lo, b.hi)));
            let projective = [t1w, t2w].iter().any(|w| w[0] != 0.0 || w[1] != 0.0 || w[2] != 0.0);
            let row = |t: &[f32; 4], p: [f32; 3]| t[0] * p[0] + t[1] * p[1] + t[2] * p[2] + t[3];
            let (js, edges) = if b.is_some() { (8, 6) } else { (1, 3) };
            let pair = |i: usize, j: usize| -> [f32; 4] { [(&t1x, &t2x), (&t1y, &t2y), (&z1, &z2), (&t1w, &t2w)].map(|(t1, t2)| row(t1, ones[i]) + row(t2, twos[j])) };
            let (mut seen, mut clipped) = (Vec::with_capacity(8 * js), false);
            for i in 0..8 {
                for j in 0..js {
                    // (its clip z: z - w, plus w)
                    let h = pair(i, j);
                    if h[2] + h[3] >= 0.0 {
                        seen.push(h);
                        continue;
                    }
                    clipped = true;
                    for k in 0..edges {
                        let g = if k < 3 { pair(i ^ 1 << k, j) } else { pair(i, j ^ 1 << (k - 3)) };
                        if g[2] + g[3] >= 0.0 {
                            let f = (h[2] + h[3]) / ((h[2] + h[3]) - (g[2] + g[3]));
                            seen.push(std::array::from_fn(|n| h[n] + f * (g[n] - h[n])));
                        }
                    }
                }
            }
            if seen.is_empty() {
                continue; // all of it behind the near plane
            }
            let (mut lo, mut hi, mut s1, mut s2) = ([f32::MAX; 2], [f32::MIN; 2], 0.0f32, 0.0f32);
            for [x, y, _, ww] in seen {
                let at = [x / ww, y / ww];
                (lo, hi) = ([lo[0].min(at[0]), lo[1].min(at[1])], [hi[0].max(at[0]), hi[1].max(at[1])]);
                if projective {
                    s1 = s1.max(stretch_at(&t1x, &t1y, &t1w, at, ww));
                    s2 = s2.max(stretch_at(&t2x, &t2y, &t2w, at, ww));
                }
            }
            if !projective {
                (s1, s2) = (stretch(&t1x, &t1y), if b.is_some() { stretch(&t2x, &t2y) } else { 0.0 });
            }
            let mut worst = c.flatness * s1;
            let mut reach = c.miter;
            if let Some(b) = b {
                worst += b.curves.flatness * s2;
                reach = reach.max(b.curves.miter);
            }
            // a stroke reaches past the path by its sharpest miter (doubled: affine maps change
            // angles), at most the miter limit
            let margin = if layers[1] || layers[2] { 0.5 * sw.max(bw) * (2.0 * reach).min(10.0) + 2.0 } else { 2.0 };
            let [x0, y0] = [(lo[0] - margin).floor().max(0.0), (lo[1] - margin).floor().max(0.0)];
            let [x1, y1] = [(hi[0] + margin).ceil().min(w), (hi[1] + margin).ceil().min(h)];
            if x1 <= x0 || y1 <= y0 {
                continue;
            }
            let (ow, oh) = ((x1 - x0) as u32, (y1 - y0) as u32);
            let atlas = fit(&mut groups, fresh, |g| {
                let saved = g.coverage;
                let mut atlas = [NONE; 4];
                for (layer, _) in layers.iter().enumerate().filter(|(_, shown)| **shown) {
                    let Some(at) = g.coverage.place(ow, oh, limit) else {
                        g.coverage = saved;
                        return None;
                    };
                    atlas[layer] = at;
                }
                Some(atlas)
            })?;
            // into the object's local pixels: x - x0 w (a 2D view's w is the translation's 1 alone)
            let local = |t: [f32; 4], by: f32, tw: &[f32; 4]| [0, 1, 2, 3].map(|j| t[j] - by * tw[j]);
            // its depth over view pixels: its plane's (a morph's: both terms' plane points, summed), through the
            // camera, exactly that of the paths before it that it lies in (their order decides where they meet, as
            // in a 2D view, whose paths all lie in depth 0)
            // its fill lit by the view's lights: a 3D view's planar path with a material, in the scene (not fixed in
            // the frame); its plane's normal in the world (a morph's: both terms' plane points, summed, as its depth
            // plane takes them)
            let [q0, q1, q2] = world_plane(a, b, r);
            let (u, v) = ([0, 1, 2].map(|k| q1[k] - q0[k]), [0, 1, 2].map(|k| q2[k] - q0[k]));
            let n = [u[1] * v[2] - u[2] * v[1], u[2] * v[0] - u[0] * v[2], u[0] * v[1] - u[1] * v[0]];
            let length = (n[0] * n[0] + n[1] * n[1] + n[2] * n[2]).sqrt();
            let lit = camera.three_d && r.material[3] > 0.0 && r.flags & super::OVERLAY == 0 && a.planar && b.is_none_or(|b| b.planar) && length > 1e-12;
            let normal = if lit { n.map(|x| (x / length) as f32) } else { [0.0; 3] };
            // else lit as a whole, like CE (where it is shaded in 3D): solid colors here, gradients by the composite
            // (`place`)
            let light = if lit { 0.0 } else { store.light(camera, r)? };
            for c in [&mut paint.fill, &mut paint.stroke, &mut paint.background] {
                if c[3] >= 0.0 {
                    *c = super::lighten(*c, light);
                }
            }
            let [pa, pb, pc] = if camera.three_d {
                let row = |t: &[f32; 4], p: [f64; 3]| [0, 1, 2].map(|j| t[j] as f64 * p[j]).iter().sum::<f64>() + t[3] as f64;
                let points: Vec<[f64; 3]> = (0..3)
                    .filter_map(|i| {
                        let (p1, p2) = (a.plane[i], b.map_or([0.0; 3], |b| b.plane[i]));
                        let at = |t1: &[f32; 4], t2: &[f32; 4]| row(t1, p1) + row(t2, p2);
                        let ww = at(&t1w, &t2w);
                        (ww.abs() > 1e-6).then(|| [at(&t1x, &t2x) / ww, at(&t1y, &t2y) / ww, at(&z1, &z2) / ww])
                    })
                    .collect();
                match flats.of.get(&k) {
                    Some(&f) => depths[f],
                    None => fit_plane(&points),
                }
            } else {
                [0.0; 3]
            };
            let reference = match flats.of.get(&k) {
                Some(&f) => *references[f].get_or_insert([x0, y0]),
                None => [x0, y0],
            };
            // the records its flattening can write, a slot each (see `vector.wgsl`): a fill edge per segment of each
            // curve (as many as its curves need most: the shader's own bound, with room for its rounding) and a closing
            // edge per subpath; for each stroke layer, a body piece per segment and dash window it meets, a joint's
            // records at each curve and a cap's at each end of what each subpath shows in each dash window it meets
            let n = (((24.0 * worst).sqrt() * 1.0001).ceil().max(1.0) as u32).min(256);
            let (cap, joint) = (paint.brush2[3] & 3, paint.brush2[3] >> 2 & 3);
            let (windows_per_segment, windows) = if r.dash[0] > 0.0 && r.dash[1] < 1.0 {
                // a segment (a curve's 1 / n) and a subpath (its longest) meet at most this many, and one for rounding
                let longest = store.ranges[c.first_subpath as usize..(c.first_subpath + c.subpaths) as usize].iter().map(|s| s[1] - s[0]).max().unwrap_or(0);
                let meet = |u: f32| ((u / r.dash[0]).ceil() as u32).saturating_add(2).min(1 << 16);
                (meet(1.0 / n as f32), meet(longest as f32))
            } else {
                (1, 1)
            };
            // a round piece's records (two triangles each) over half a turn, at its widest stroke layer
            let round = [(layers[1], sw), (layers[2], bw)].iter().filter(|(shown, _)| *shown).map(|(_, w)| fan(0.5 * w).div_ceil(2)).max().unwrap_or(1);
            let joints = if joint == ROUND { round } else { 1 };
            let caps = match cap {
                ROUND => round,
                SQUARE => 1,
                _ => 0,
            };
            let fills = if layers[0] { c.count.saturating_mul(n).saturating_add(c.subpaths).saturating_mul(1 + clipped as u32) } else { 0 };
            // a clipped object's hidden points' shadows on the near plane, in its shape's own space: clip z's gradient
            // along its plane g (term 1's), and 1 / (z1 . g): a point p moves to p - z(p) g / (z1 . g) (`shadow`)
            let near = if clipped {
                let [p0, p1, p2] = a.plane;
                let (u, v) = ([0, 1, 2].map(|k| p1[k] - p0[k]), [0, 1, 2].map(|k| p2[k] - p0[k]));
                let n = [u[1] * v[2] - u[2] * v[1], u[2] * v[0] - u[0] * v[2], u[0] * v[1] - u[1] * v[0]];
                let dot = |a: [f64; 3], b: [f64; 3]| a[0] * b[0] + a[1] * b[1] + a[2] * b[2];
                let z = [0, 1, 2].map(|i| z1[i] as f64 + t1w[i] as f64); // clip z's
                let g = if dot(n, n) > 1e-20 { [0, 1, 2].map(|k| z[k] - n[k] * dot(z, n) / dot(n, n)) } else { z };
                let d = dot(z, g);
                (if d.abs() > 1e-20 { [g[0], g[1], g[2], 1.0 / d] } else { [z[0], z[1], z[2], 1.0 / dot(z, z).max(1e-20)] }).map(|v| v as f32)
            } else {
                [0.0; 4]
            };
            let per_layer = c.count.saturating_mul(n).saturating_mul(windows_per_segment).saturating_add(c.count.saturating_mul(joints)).saturating_add((2 * c.subpaths).saturating_mul(windows).saturating_mul(caps));
            let strokes = (layers[1] as u32 + layers[2] as u32).saturating_mul(per_layer);
            let group = groups.last_mut().expect("a group");
            group.objects.push(Object {
                t1x: local(t1x, x0, &t1w),
                t1y: local(t1y, y0, &t1w),
                t2x: local(t2x, x0, &t2w),
                t2y: local(t2y, y0, &t2w),
                t1w,
                t2w,
                rect: [x0, y0, x1 - x0, y1 - y0],
                atlas,
                ids: [c.first, b.map_or(NONE, |b| b.curves.first), c.first_subpath, c.subpaths],
                params: [r.params[0], r.params[1], 0.5 * sw, 0.5 * bw],
                dash: [r.dash[0], r.dash[1], r.dash[2], 0.5 * (lo[1] + hi[1]) - y0],
                scale: [s1, s2, margin, c.count as f32],
                // (its depth at its reference point, to its digits: `plane_depth`)
                place: [pa as f32, pb as f32, (pc + pa * reference[0] as f64 + pb * reference[1] as f64) as f32, light],
                flags: [(camera.three_d && !(a.planar && b.is_none_or(|b| b.planar))) as u32, clipped as u32, reference[0] as u32, reference[1] as u32],
                slots: [group.fills, group.strokes, n, windows_per_segment],
                pieces: [joints, caps, windows, 0],
                paint,
                material: if lit { r.material } else { [0.0; 4] },
                normal: [normal[0], normal[1], normal[2], 0.0],
                t1z: z1,
                t2z: z2,
                near,
            });
            let spanned = span([x0, y0, x1, y1], tiles);
            let reach = [2.0, 0.5 * sw * (2.0 * reach).min(10.0) + 2.0, 0.5 * bw * (2.0 * reach).min(10.0) + 2.0];
            let whole = r.params[0] <= 0.0 && r.params[1] >= c.count as f32;
            let rows = [t1x, t1y, t1w, t2x, t2y, t2w];
            group.masks.push(if clipped || !whole { None } else { tile_masks(store, a, b, &rows, spanned, layers, reach) });
            group.spans.push(spanned);
            group.fills = group.fills.saturating_add(fills);
            group.strokes = group.strokes.saturating_add(strokes);
        }
        let raster_size = [size[0], groups.iter().map(|g| g.raster.rows()).max().unwrap_or(0)];
        let lit = groups.iter().any(|g| g.objects.iter().any(|o| o.material[3] > 0.0));
        Ok(Plan { groups, raster_size, size, background, bias: camera.bias, inverse: inverse(&camera.projection), lit, crossings: camera.three_d, light: [0.0; LIGHT] })
    }

    /// A 3D view's base depth for its composite: `depth` (the raster pass's, `samples` per pixel) as its samples'
    /// nearest, one float a pixel.
    pub(crate) fn resolve_depth(&mut self, device: &wgpu::Device, encoder: &mut wgpu::CommandEncoder, depth: &wgpu::TextureView, samples: u32, size: [u32; 2]) {
        let (depth_layouts, depth_resolve) = (&self.depth_layouts, &self.depth_resolve);
        if self.base_depth.as_ref().is_none_or(|(_, have)| *have != size) {
            self.base_depth = Some((image(device, "base depth", size, wgpu::TextureFormat::R32Float, wgpu::TextureUsages::STORAGE_BINDING | wgpu::TextureUsages::TEXTURE_BINDING), size));
        }
        let (out, _) = self.base_depth.as_ref().expect("base depth");
        let k = if samples > 1 { 0 } else { 1 };
        let group = device.create_bind_group(&wgpu::BindGroupDescriptor {
            label: Some("base depth"),
            layout: &depth_layouts[k],
            entries: &[wgpu::BindGroupEntry { binding: k as u32, resource: wgpu::BindingResource::TextureView(depth) }, wgpu::BindGroupEntry { binding: 2, resource: wgpu::BindingResource::TextureView(out) }],
        });
        let mut pass = encoder.begin_compute_pass(&wgpu::ComputePassDescriptor { label: Some("base depth"), timestamp_writes: None });
        pass.set_pipeline(&depth_resolve[k]);
        pass.set_bind_group(0, &group, &[]);
        pass.dispatch_workgroups(size[0].div_ceil(16), size[1].div_ceil(16), 1);
    }

    /// Where a 3D view's raster passes put its base (their colour), for its composite to read as it writes the canvas.
    pub(crate) fn base(&mut self, device: &wgpu::Device, size: [u32; 2]) -> wgpu::TextureView {
        if self.base.as_ref().is_none_or(|(_, have)| *have != size) {
            self.base = Some((image(device, "base", size, super::COLOR, wgpu::TextureUsages::RENDER_ATTACHMENT | wgpu::TextureUsages::TEXTURE_BINDING), size));
        }
        self.base.as_ref().expect("base").0.clone()
    }

    /// Where a 3D view with lit meshes puts its base's light (`blend.wgsl`'s `Base`), beside its paint (`base`).
    pub(crate) fn base_light(&mut self, device: &wgpu::Device, size: [u32; 2]) -> wgpu::TextureView {
        if self.base_light.as_ref().is_none_or(|(_, have)| *have != size) {
            self.base_light = Some((image(device, "base light", size, super::RADIANCE, wgpu::TextureUsages::RENDER_ATTACHMENT | wgpu::TextureUsages::TEXTURE_BINDING), size));
        }
        self.base_light.as_ref().expect("base light").0.clone()
    }

    /// A new frame: the groups' buffers are taken afresh, and the coverage atlas sized again for what the last frame
    /// needed (it only grows within a frame: views and lights' maps take it in turn).
    pub(crate) fn begin(&mut self) {
        self.used = 0;
        if self.atlas.as_ref().is_some_and(|(_, [_, ah])| *ah > 2 * self.rows + 256) {
            self.atlas = None;
        }
        self.rows = 0;
    }

    /// The composite's pipelines for views that lay what `key` says (`LIT`, `RASTERS`, `LISTS`: the overrides in
    /// `vector.wgsl`), made when first needed. Only a 3D view needs the passes where depths cross.
    fn composite(&mut self, device: &wgpu::Device, key: usize, crossings: bool) {
        if self.composite[key].is_some() && (!crossings || self.crossing[key].is_some()) {
            return;
        }
        let kind = (key & SINGLE == 0) as usize;
        let shader = if kind == 0 { self.single_shader.get_or_insert_with(|| Self::shader(device, false)) } else { &self.shader };
        let constants = [("lighting", (key & LIT) as f64), ("rasters", (key & RASTERS != 0) as u8 as f64), ("lists", (key & LISTS != 0) as u8 as f64), ("points", (key & POINTS != 0) as u8 as f64)];
        let layout = |groups: &[Option<&wgpu::BindGroupLayout>]| device.create_pipeline_layout(&wgpu::PipelineLayoutDescriptor { label: None, bind_group_layouts: groups, immediate_size: 0 });
        let composing = layout(&[Some(&self.scene_layout), Some(&self.image_layout[kind])]);
        // workgroup memory is written before it is read: zeroing it would only cost time
        let make = |entry: &str, layout: &wgpu::PipelineLayout| {
            let options = wgpu::PipelineCompilationOptions { constants: &constants, zero_initialize_workgroup_memory: false };
            device.create_compute_pipeline(&wgpu::ComputePipelineDescriptor { label: Some(entry), layout: Some(layout), module: shader, entry_point: Some(entry), compilation_options: options, cache: None })
        };
        if self.composite[key].is_none() {
            self.composite[key] = Some([make("composite", &composing), make("keep", &composing)]);
        }
        if crossings && self.crossing[key].is_none() {
            let counting = layout(&[Some(&self.scene_layout), Some(&self.image_layout[kind]), Some(&self.groups_layout)]);
            self.crossing[key] = Some([make("count_crossings", &counting), make("settle_crossings", &composing)]);
        }
    }

    /// Fill and stroke records have independent producers. A view pays only for the families it draws.
    fn prepare_flatten(&mut self, device: &wgpu::Device, counts: [u32; 2]) {
        for (i, count) in counts.into_iter().enumerate() {
            if count == 0 || self.flatten[i].is_some() { continue; }
            let entry = ["flatten_fill", "flatten_stroke"][i];
            let layout = device.create_pipeline_layout(&wgpu::PipelineLayoutDescriptor { label: None, bind_group_layouts: &[Some(&self.scene_layout), None, Some(&self.write_layout)], immediate_size: 0 });
            let options = wgpu::PipelineCompilationOptions { zero_initialize_workgroup_memory: false, ..Default::default() };
            self.flatten[i] = Some(device.create_compute_pipeline(&wgpu::ComputePipelineDescriptor { label: Some(entry), layout: Some(&layout), module: &self.shader, entry_point: Some(entry), compilation_options: options, cache: None }));
        }
    }

    /// The pipelines of a light's map and of a view's opaque depth from its paths (`fs_nearest`), made when one is
    /// first needed: the coverage atlas and a non-planar path's strokes' depths are what they read besides the scene.
    fn nearest(&mut self, device: &wgpu::Device) {
        if self.nearest.is_some() {
            return;
        }
        let fragment = wgpu::ShaderStages::FRAGMENT;
        let atlas = wgpu::BindGroupLayoutEntry { binding: 0, visibility: fragment, ty: wgpu::BindingType::Texture { sample_type: wgpu::TextureSampleType::Float { filterable: false }, view_dimension: wgpu::TextureViewDimension::D2, multisampled: false }, count: None };
        let depths = wgpu::BindGroupLayoutEntry { binding: 9, visibility: fragment, ty: wgpu::BindingType::Buffer { ty: wgpu::BufferBindingType::Storage { read_only: true }, has_dynamic_offset: false, min_binding_size: None }, count: None };
        let layout = device.create_bind_group_layout(&wgpu::BindGroupLayoutDescriptor { label: Some("nearest"), entries: &[atlas, depths] });
        let pipeline_layout = device.create_pipeline_layout(&wgpu::PipelineLayoutDescriptor { label: None, bind_group_layouts: &[Some(&self.scene_layout), Some(&layout)], immediate_size: 0 });
        // a light's map (standard Z), a view's depth (reversed Z: nearer is greater)
        let pipelines = [(false, wgpu::CompareFunction::Less), (true, wgpu::CompareFunction::Greater)].map(|(view, compare)| {
            let constants = [("view_depth", view as u8 as f64)];
            device.create_render_pipeline(&wgpu::RenderPipelineDescriptor {
                label: Some("nearest"),
                layout: Some(&pipeline_layout),
                vertex: wgpu::VertexState { module: &self.shader, entry_point: Some("vs_cover"), compilation_options: Default::default(), buffers: &[] },
                fragment: Some(wgpu::FragmentState { module: &self.shader, entry_point: Some("fs_nearest"), compilation_options: wgpu::PipelineCompilationOptions { constants: &constants, ..Default::default() }, targets: &[] }),
                primitive: wgpu::PrimitiveState::default(),
                depth_stencil: Some(wgpu::DepthStencilState { format: wgpu::TextureFormat::Depth32Float, depth_write_enabled: Some(true), depth_compare: Some(compare), stencil: Default::default(), bias: Default::default() }),
                multisample: wgpu::MultisampleState::default(),
                multiview_mask: None,
                cache: None,
            })
        });
        self.nearest = Some((layout, pipelines));
    }

    /// The pipeline of a 3D view's slab bounds (`bound_slabs`), made when first needed: what it reads besides the scene
    /// (the coverage atlas, the lists, a non-planar path's strokes' depths), and where it writes them.
    fn bounds(&mut self, device: &wgpu::Device) {
        if self.bounds.is_some() {
            return;
        }
        let compute = wgpu::ShaderStages::COMPUTE;
        let read = |binding| wgpu::BindGroupLayoutEntry { binding, visibility: compute, ty: wgpu::BindingType::Buffer { ty: wgpu::BufferBindingType::Storage { read_only: true }, has_dynamic_offset: false, min_binding_size: None }, count: None };
        let atlas = wgpu::BindGroupLayoutEntry { binding: 0, visibility: compute, ty: wgpu::BindingType::Texture { sample_type: wgpu::TextureSampleType::Float { filterable: false }, view_dimension: wgpu::TextureViewDimension::D2, multisampled: false }, count: None };
        let out = wgpu::BindGroupLayoutEntry { binding: 0, visibility: compute, ty: wgpu::BindingType::StorageTexture { access: wgpu::StorageTextureAccess::WriteOnly, format: wgpu::TextureFormat::Rgba32Float, view_dimension: wgpu::TextureViewDimension::D2 }, count: None };
        let layouts = [("slab bounds in", &[atlas, read(5), read(6), read(9)][..]), ("slab bounds", &[out][..])].map(|(label, entries)| device.create_bind_group_layout(&wgpu::BindGroupLayoutDescriptor { label: Some(label), entries }));
        let layout = device.create_pipeline_layout(&wgpu::PipelineLayoutDescriptor { label: None, bind_group_layouts: &[Some(&self.scene_layout), Some(&layouts[0]), Some(&layouts[1])], immediate_size: 0 });
        let pipeline = device.create_compute_pipeline(&wgpu::ComputePipelineDescriptor { label: Some("bound_slabs"), layout: Some(&layout), module: &self.shader, entry_point: Some("bound_slabs"), compilation_options: Default::default(), cache: None });
        self.bounds = Some((layouts, pipeline));
    }

    /// Encode group `g` of a planned view into `out`: `statics` are the store's control points, subpaths and rows.
    #[allow(clippy::too_many_arguments)]
    pub(crate) fn encode(&mut self, device: &wgpu::Device, queue: &wgpu::Queue, encoder: &mut wgpu::CommandEncoder, plan: &Plan, g: usize, statics: &[wgpu::BindingResource<'_>; 3], out: Out<'_>) {
        let group = &plan.groups[g];
        self.prepare_flatten(device, [group.fills, group.strokes]);
        let [w, h] = plan.size;
        let [tiles_x, tiles_y] = [w.div_ceil(TILE), h.div_ceil(TILE)];
        let (base, light, listed, glowing, slabs) = match &out {
            Out::Color { base, light, listed, light_out, slabs, .. } => (*base, *light, *listed, *light_out, slabs.filter(|_| g == 0)),
            Out::Bounds { listed, .. } => (None, None, *listed, None, None),
            Out::Depth(_) | Out::Opaque(_) => (None, None, None, None, None),
        };
        // records and the coverage atlas, shared by every group (drawn one after another)
        let need = plan.groups.iter().fold([1024, 1024], |[f, s], g| [f.max(g.fills), s.max(g.strokes)]);
        if self.records.as_ref().is_none_or(|(_, _, have)| have[0] < need[0] || have[1] < need[1]) {
            let [f, s] = need.map(u32::next_power_of_two);
            self.records = Some((buffer(device, "fill records", f as u64 * 48, wgpu::BufferUsages::STORAGE), buffer(device, "stroke records", s as u64 * 48, wgpu::BufferUsages::STORAGE), [f, s]));
        }
        let rows = plan.groups.iter().map(|g| g.coverage.rows()).max().unwrap_or(0).max(1);
        self.rows = self.rows.max(rows);
        let width = group.coverage.width;
        if self.atlas.as_ref().is_none_or(|(_, [aw, ah])| *aw != width || *ah < rows) {
            let size = [width, rows.div_ceil(64) * 64];
            self.atlas = Some((image(device, "coverage atlas", size, wgpu::TextureFormat::R32Float, wgpu::TextureUsages::RENDER_ATTACHMENT | wgpu::TextureUsages::TEXTURE_BINDING), size));
        }
        if matches!(out, Out::Color { .. }) && plan.groups.len() > 1 && self.scratch.as_ref().is_none_or(|(_, size)| *size != plan.size) {
            self.scratch = Some((image(device, "overflow", plan.size, super::COLOR, wgpu::TextureUsages::STORAGE_BINDING | wgpu::TextureUsages::TEXTURE_BINDING), plan.size));
        }
        // a view with lit content (paths, or meshes in its base) composites with the light; its groups but the last
        // leave their pixels' light to the next (`vector_compute.wgsl`'s `store`), in turn in two images, and the last
        // leaves it for the view's glow where it has one
        let lit = plan.lit || light.is_some();
        let carries = lit && g + 1 < plan.groups.len();
        let glows = lit && g + 1 == plan.groups.len() && glowing.is_some();
        if carries && self.carried.as_ref().is_none_or(|(_, size)| *size != plan.size) {
            let carried = || image(device, "carried light", plan.size, super::RADIANCE, wgpu::TextureUsages::STORAGE_BINDING | wgpu::TextureUsages::TEXTURE_BINDING);
            self.carried = Some(([carried(), carried()], plan.size));
        }
        // its composite's pipeline: with the code of what the group lays alone (`vector.wgsl`'s overrides)
        let rastered = !group.rasters.is_empty() || (g == 0 && base.is_some());
        let kind = (!listed.is_some_and(|l| l.samples == 1)) as usize;
        let key = (kind == 0) as usize * SINGLE | lit as usize * LIT | rastered as usize * RASTERS | (g == 0 && listed.is_some()) as usize * LISTS | slabs.is_some() as usize * POINTS;
        match out {
            Out::Color { .. } => self.composite(device, key, plan.crossings),
            Out::Bounds { .. } => self.bounds(device),
            Out::Depth(_) | Out::Opaque(_) => self.nearest(device),
        }
        if self.used == self.groups.len() {
            self.groups.push(GroupBuffers {
                uniform: buffer(device, "vector frame", size_of::<FrameUniform>() as u64, wgpu::BufferUsages::UNIFORM | wgpu::BufferUsages::COPY_DST),
                objects: Data::new(device, "objects"),
                tiles: Data::new(device, "tiles"),
            });
        }
        let b = &mut self.groups[self.used];
        self.used += 1;
        let tiles = tile_lists(&group.spans, &group.masks, &group.objects, tiles_x, (tiles_x * tiles_y) as usize);
        b.objects.hold(device, queue, "objects", bytemuck::cast_slice::<Object, u8>(&group.objects));
        b.tiles.hold(device, queue, "tiles", bytemuck::cast_slice(&tiles));
        let (atlas, [aw, ah]) = self.atlas.as_ref().expect("atlas");
        let [red, green, blue, alpha] = plan.background;
        let uniform = FrameUniform {
            size: [w as f32, h as f32, *aw as f32, *ah as f32],
            tiles: [tiles_x, tiles_y, group.fills, group.strokes],
            counts: [group.objects.len() as u32, (g > 0) as u32, base.map_or(0, |_| if g == 0 { 1 } else { 2 }), (if g == 0 { light.is_some() } else { lit }) as u32 | ((carries || glows) as u32) << 1],
            background: [red * alpha, green * alpha, blue * alpha, alpha],
            depth: [plan.bias, 0.0, 0.0, 0.0],
            lists: listed.filter(|_| g == 0).map_or([0, 0, 0, 1], |l| [1, l.rows[0], l.rows[1], l.samples]),
            inverse: plan.inverse,
            light: plan.light,
        };
        queue.write_buffer(&b.uniform, 0, bytemuck::bytes_of(&uniform));
        let bind = |layout: &wgpu::BindGroupLayout, entries: &[(u32, wgpu::BindingResource)]| {
            let entries: Vec<wgpu::BindGroupEntry> = entries.iter().map(|(binding, resource)| wgpu::BindGroupEntry { binding: *binding, resource: resource.clone() }).collect();
            device.create_bind_group(&wgpu::BindGroupDescriptor { label: None, layout, entries: &entries })
        };
        let [ctrl, subs, rows] = statics.clone();
        let scene = bind(&self.scene_layout, &[(0, b.uniform.as_entire_binding()), (1, ctrl), (2, subs), (3, b.objects.0.as_entire_binding()), (4, rows), (5, b.tiles.0.as_entire_binding())]);
        let view = wgpu::BindingResource::TextureView;
        let depth = if base.is_some() { &self.base_depth.as_ref().expect("base depth").0 } else { &self.far };
        let n = group.objects.len() as u32;
        let accumulate = |encoder: &mut wgpu::CommandEncoder, read: &wgpu::BindGroup| {
            let mut pass = encoder.begin_render_pass(&wgpu::RenderPassDescriptor {
                label: Some("accumulate"),
                color_attachments: &[Some(wgpu::RenderPassColorAttachment { view: atlas, depth_slice: None, resolve_target: None, ops: wgpu::Operations { load: wgpu::LoadOp::Clear(wgpu::Color::TRANSPARENT), store: wgpu::StoreOp::Store } })],
                depth_stencil_attachment: None,
                occlusion_query_set: None,
                timestamp_writes: None,
                multiview_mask: None,
            });
            pass.set_bind_group(0, &scene, &[]);
            pass.set_bind_group(3, read, &[]);
            for (pipeline, count) in [(&self.fill, group.fills), (&self.stroke, group.strokes)] {
                if count > 0 {
                    pass.set_pipeline(pipeline);
                    pass.draw(0..6, 0..count);
                }
            }
        };
        // a light's map, or a view's opaque depth (`view`): its paths' nearest depth over its meshes' (`images`: what
        // `fs_nearest` reads), where the group's objects are
        let nearest = |encoder: &mut wgpu::CommandEncoder, map: &wgpu::TextureView, view: bool, images: &[(u32, wgpu::BindingResource)]| {
            let [x0, y0, x1, y1] = group.objects.iter().fold([w, h, 0, 0], |[x0, y0, x1, y1], o| {
                let r = o.rect.map(|v| v as u32);
                [x0.min(r[0]), y0.min(r[1]), x1.max(r[0] + r[2]).min(w), y1.max(r[1] + r[3]).min(h)]
            });
            if x1 <= x0 || y1 <= y0 {
                return;
            }
            let (layout, pipelines) = self.nearest.as_ref().expect("the nearest pipelines");
            let images = bind(layout, images);
            let mut pass = encoder.begin_render_pass(&wgpu::RenderPassDescriptor {
                label: Some("nearest"),
                color_attachments: &[],
                depth_stencil_attachment: Some(wgpu::RenderPassDepthStencilAttachment { view: map, depth_ops: Some(wgpu::Operations { load: wgpu::LoadOp::Load, store: wgpu::StoreOp::Store }), stencil_ops: None }),
                occlusion_query_set: None,
                timestamp_writes: None,
                multiview_mask: None,
            });
            pass.set_scissor_rect(x0, y0, x1 - x0, y1 - y0);
            pass.set_pipeline(&pipelines[view as usize]);
            pass.set_bind_group(0, &scene, &[]);
            pass.set_bind_group(1, &images, &[]);
            pass.draw(0..3, 0..1);
        };
        let (fill_records, stroke_records, _) = self.records.as_ref().expect("records");
        // a non-planar path's strokes keep their depth per pixel of the atlas: cleared for each group that has one
        let deep = group.objects.iter().any(|o| o.flags[0] != 0);
        let depths = if deep {
            let need = *aw as u64 * *ah as u64 * 4;
            if self.stroke_depths.as_ref().is_none_or(|(_, have)| *have < need) {
                self.stroke_depths = Some((buffer(device, "stroke depths", need, wgpu::BufferUsages::STORAGE | wgpu::BufferUsages::COPY_DST), need));
            }
            let (depths, _) = self.stroke_depths.as_ref().expect("stroke depths");
            encoder.clear_buffer(depths, 0, Some(*aw as u64 * group.coverage.rows().max(1) as u64 * 4));
            depths
        } else {
            &self.nothing
        };
        let write = bind(&self.write_layout, &[(0, fill_records.as_entire_binding()), (1, stroke_records.as_entire_binding())]);
        let read = bind(&self.read_layout, &[(0, fill_records.as_entire_binding()), (1, stroke_records.as_entire_binding()), (2, depths.as_entire_binding())]);
        for (pipeline, count) in self.flatten.iter().zip([group.fills, group.strokes]) {
            let slots = count.div_ceil(64); // workgroups: a thread per slot
            if slots == 0 { continue; }
            let mut pass = encoder.begin_compute_pass(&wgpu::ComputePassDescriptor { label: Some("flatten"), timestamp_writes: None });
            pass.set_pipeline(pipeline.as_ref().expect("the required record producer"));
            pass.set_bind_group(0, &scene, &[]);
            pass.set_bind_group(2, &write, &[]);
            pass.dispatch_workgroups(slots.min(65535), slots.div_ceil(65535), 1);
        }
        if n > 0 {
            accumulate(encoder, &read);
        }
        match out {
            Out::Color { rasters, target, lighting, .. } => {
                let (under, written) = layered(g, plan.groups.len(), base.unwrap_or(&self.empty), target, self.scratch.as_ref().map(|(s, _)| s));
                // a 3D view's list of the pixels where depths cross: room for every pixel, emptied
                let pixels = w as u64 * h as u64;
                if plan.crossings && self.crossings.2 < pixels {
                    self.crossings = (buffer(device, "crossings", 4 + 4 * pixels, wgpu::BufferUsages::STORAGE | wgpu::BufferUsages::COPY_DST), buffer(device, "crossing groups", 16, wgpu::BufferUsages::STORAGE | wgpu::BufferUsages::INDIRECT), pixels);
                }
                encoder.clear_buffer(&self.crossings.0, 0, Some(4));
                let (heads, nodes) = listed.map_or((&self.nothing, &self.nothing), |l| (l.heads, l.nodes));
                let [colors, sample_depths] = listed.map_or([&self.no_samples[kind][0], &self.no_samples[kind][1]], |l| [l.colors, l.depths]);
                let lights = listed.and_then(|l| l.lights).unwrap_or(&self.no_samples[kind][0]);
                // the light under the group (the raster base's, or what the group before left), and where it leaves its own
                let carried = self.carried.as_ref().map(|(c, _)| c);
                let light_in = if g == 0 { light.unwrap_or(&self.empty) } else { carried.map_or(&self.empty, |c| &c[(g - 1) % 2]) };
                let light_out = match glowing.filter(|_| glows) {
                    Some(kept) => kept,
                    None if carries => &carried.expect("the carried light")[g % 2],
                    None => &self.no_light_out,
                };
                let images = bind(
                    &self.image_layout[kind],
                    &[(0, view(atlas)), (1, view(rasters.unwrap_or(&self.empty))), (2, view(under)), (3, view(written)), (4, view(depth)), (5, heads.as_entire_binding()), (6, nodes.as_entire_binding()), (7, view(colors)), (8, view(sample_depths)), (9, depths.as_entire_binding()), (10, view(lighting.maps)), (11, wgpu::BindingResource::Sampler(lighting.compare)), (12, view(lighting.dfg)), (13, wgpu::BindingResource::Sampler(lighting.linear)), (14, self.crossings.0.as_entire_binding()), (15, view(lighting.environment)), (16, view(lighting.occlusion)), (17, view(light_in)), (18, view(lights)), (19, view(light_out)), (20, view(slabs.map_or(&self.empty, |s| s[0]))), (21, view(slabs.map_or(&self.no_slabs, |s| s[1])))],
                );
                let mut pass = encoder.begin_compute_pass(&wgpu::ComputePassDescriptor { label: Some("composite"), timestamp_writes: None });
                // the pixels where the group lays something of its own, then (by a lean pass) the others
                let [composite, keep] = self.composite[key].as_ref().expect("the composite");
                pass.set_pipeline(composite);
                pass.set_bind_group(0, &scene, &[]);
                pass.set_bind_group(1, &images, &[]);
                pass.dispatch_workgroups(tiles_x, tiles_y, 1);
                pass.set_pipeline(keep);
                pass.dispatch_workgroups(tiles_x, tiles_y, 1);
                // then (a 3D view's) the pixels where depths cross, as many workgroups as the count says
                if plan.crossings {
                    let [count, settle] = self.crossing[key].as_ref().expect("the crossing passes");
                    pass.set_pipeline(count);
                    pass.set_bind_group(2, &bind(&self.groups_layout, &[(0, self.crossings.1.as_entire_binding())]), &[]);
                    pass.dispatch_workgroups(1, 1, 1);
                    pass.set_pipeline(settle);
                    pass.dispatch_workgroups_indirect(&self.crossings.1, 0);
                }
            }
            Out::Bounds { out: bounds, .. } => {
                let (layouts, pipeline) = self.bounds.as_ref().expect("the slab bounds' pipeline");
                let (heads, nodes) = listed.map_or((&self.nothing, &self.nothing), |l| (l.heads, l.nodes));
                let read = bind(&layouts[0], &[(0, view(atlas)), (5, heads.as_entire_binding()), (6, nodes.as_entire_binding()), (9, depths.as_entire_binding())]);
                let written = bind(&layouts[1], &[(0, view(bounds))]);
                let mut pass = encoder.begin_compute_pass(&wgpu::ComputePassDescriptor { label: Some("slab bounds"), timestamp_writes: None });
                pass.set_pipeline(pipeline);
                pass.set_bind_group(0, &scene, &[]);
                pass.set_bind_group(1, &read, &[]);
                pass.set_bind_group(2, &written, &[]);
                pass.dispatch_workgroups(tiles_x, tiles_y, 1);
            }
            Out::Depth(map) => nearest(encoder, map, false, &[(0, view(atlas)), (9, depths.as_entire_binding())]),
            Out::Opaque(map) => nearest(encoder, map, true, &[(0, view(atlas)), (9, depths.as_entire_binding())]),
        }
    }
}

/// A composite pipeline's key: what the view lays, beyond paths (`vector.wgsl`'s overrides `lighting`, `rasters`,
/// `lists`, `points`): lit content, rasters (a 2D view's points and meshes, a 3D view's raster base), see-through lists,
/// see-through points' slabs.
const LIT: usize = 1;
const RASTERS: usize = 2;
const LISTS: usize = 4;
const POINTS: usize = 8;
const SINGLE: usize = 16; // single-sample texture bindings, with the same compositing code

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

    #[test]
    fn record_families_compile_only_when_first_needed() {
        super::super::with_gpu(|gpu| {
            for first in 0..2 {
                let mut vector = Vector::new(&gpu.device, &gpu.queue);
                vector.prepare_flatten(&gpu.device, [0, 0]);
                assert!(vector.flatten.iter().all(Option::is_none));
                let mut counts = [0, 0];
                counts[first] = 1;
                vector.prepare_flatten(&gpu.device, counts);
                assert!(vector.flatten[1 - first].is_none());
                let pipeline = vector.flatten[first].clone().unwrap();
                for counts in [[0, 0], counts, [1, 1]] {
                    vector.prepare_flatten(&gpu.device, counts);
                    assert_eq!(vector.flatten[first].as_ref(), Some(&pipeline));
                }
                assert!(vector.flatten.iter().all(Option::is_some));
            }
        }).unwrap();
    }

    #[test]
    fn two_d_views_leave_crossing_passes_for_the_first_three_d_view() {
        super::super::with_gpu(|gpu| {
            let mut vector = Vector::new(&gpu.device, &gpu.queue);
            for key in [0, SINGLE] {
                for _ in 0..2 {
                    vector.composite(&gpu.device, key, false);
                    assert!(vector.composite[key].is_some());
                    assert!(vector.crossing[key].is_none());
                }
                for crossings in [true, false, true] {
                    vector.composite(&gpu.device, key, crossings);
                    assert!(vector.composite[key].is_some());
                    assert!(vector.crossing[key].is_some());
                }
            }
        }).unwrap();
    }
}

/// What group `g` of `groups` lies over and writes: each lies over what the ones before it made (the first over
/// `first`); the last writes the target, the others alternate with the scratch image behind it.
fn layered<'a>(g: usize, groups: usize, first: &'a wgpu::TextureView, target: &'a wgpu::TextureView, scratch: Option<&'a wgpu::TextureView>) -> (&'a wgpu::TextureView, &'a wgpu::TextureView) {
    match (g, (groups - 1 - g).is_multiple_of(2)) {
        (0, true) => (first, target),
        (0, false) => (first, scratch.expect("scratch")),
        (_, true) => (scratch.expect("scratch"), target),
        (_, false) => (target, scratch.expect("scratch")),
    }
}

/// What a view's paths with a material are lit with: its lights' shadow maps (`maps`) and their comparison, the DFG
/// table (`dfg`), its environment's cube, and their trilinear reads; its ambient occlusion (`occlusion.rs`).
pub(crate) struct Lighting<'a> {
    pub(crate) maps: &'a wgpu::TextureView,
    pub(crate) compare: &'a wgpu::Sampler,
    pub(crate) dfg: &'a wgpu::TextureView,
    pub(crate) linear: &'a wgpu::Sampler,
    pub(crate) environment: &'a wgpu::TextureView,
    pub(crate) occlusion: &'a wgpu::TextureView,
}

/// What a group's composite makes.
pub(crate) enum Out<'a> {
    /// A canvas's color, `target` (the last group covers it entirely): `rasters` the raster atlas, with the group's
    /// rasters drawn in it; `base` a 3D view's raster base (`base`; its depth `resolve_depth`'s), laid among the first
    /// group's layers at its depth, as are its see-through fragments (`listed`) and its see-through points' slabs
    /// (`slabs`: the bounds `Bounds` left, the slabs); `light` the base's light where the view has lit meshes (`base` its
    /// display paint then: `vector.wgsl`'s `base_at`); `lighting` what its paths with a material are lit with.
    /// `light_out`: where a view with lit content leaves its pixels' light, `target` their paint, for its glow to be
    /// spread from and shown with (`bloom.rs`), as its groups but the last leave theirs to the next (none: the last group
    /// shows its pixels).
    Color { rasters: Option<&'a wgpu::TextureView>, target: &'a wgpu::TextureView, base: Option<&'a wgpu::TextureView>, light: Option<&'a wgpu::TextureView>, listed: Option<&'a Listed<'a>>, slabs: Option<[&'a wgpu::TextureView; 2]>, lighting: Lighting<'a>, light_out: Option<&'a wgpu::TextureView> },
    /// A 3D view's slab bounds (`vector.wgsl`'s `bound`), into `out`: at each pixel the depths of its first group's
    /// nearest layers, its paths' and its see-through fragments' (`listed`), for its see-through points to find their
    /// slab by before they are drawn.
    Bounds { out: &'a wgpu::TextureView, listed: Option<&'a Listed<'a>> },
    /// A light's shadow map (its layer, its meshes' depth drawn in it): at each texel, where nearer, the depth of the
    /// nearest layer of the plan (seen from the light) that covers it, half opaque or more (`fs_nearest`).
    Depth(&'a wgpu::TextureView),
    /// A view's opaque depth, for its ambient occlusion (`occlusion.rs`; its opaque meshes' drawn in it, reversed Z):
    /// at each pixel, where nearer, the depth of the nearest opaque layer of the plan that covers it.
    Opaque(&'a wgpu::TextureView),
}
#[cfg(test)]
mod area_contract {
    use super::*;

    fn expected(first: [f32; 4], second: [f32; 4]) -> f64 {
        let mut points = vec![[-0.5, -0.5], [0.5, -0.5], [0.5, 0.5], [-0.5, 0.5]];
        for [x, y, d, _] in [first, second] {
            let signed = |p: [f64; 2]| p[0] * x as f64 + p[1] * y as f64 - d as f64;
            let mut clipped = Vec::new();
            for i in 0..points.len() {
                let (p, q) = (points[i], points[(i + 1) % points.len()]);
                let (a, b) = (signed(p), signed(q));
                if a >= 0.0 { clipped.push(p); }
                if (a >= 0.0) != (b >= 0.0) {
                    clipped.push([0, 1].map(|j| p[j] + (q[j] - p[j]) * a / (a - b)));
                }
            }
            points = clipped;
        }
        (0..points.len()).map(|i| {
            let (p, q) = (points[i], points[(i + 1) % points.len()]);
            p[0] * q[1] - p[1] * q[0]
        }).sum::<f64>().abs() * 0.5
    }

    #[test]
    fn half_plane_intersection_matches_independent_polygon_clipping() {
        let mut normals = vec![[1.0, 0.0], [0.0, 1.0], [-1.0, 0.0], [0.0, -1.0], [0.6, 0.8], [-0.6, 0.8], [0.6, -0.8], [-0.6, -0.8]];
        for angle in [1e-7f32, 0.01, 0.099, std::f32::consts::PI - 0.099] { normals.push([angle.cos(), angle.sin()]); }
        let offsets = [-1.0, -0.5, -0.49999997, -0.25, 0.0, 0.25, 0.49999997, 0.5, 1.0];
        // x >= 0 intersected with ±16x + y >= 0 removes or retains a triangle
        // of area (1/2) * (1/2) * (1/32) = 1/128. These closed-form witnesses
        // independently catch treating nearly parallel lines as parallel.
        let x = 16.0f32 / 257.0f32.sqrt();
        let axis = [1.0, 0.0, 0.0, 0.0];
        let mut inputs = vec![axis, [x, x / 16.0, 0.0, 0.0], axis, [-x, x / 16.0, 0.0, 0.0]];
        let mut areas = vec![63.0 / 128.0, 1.0 / 128.0];
        for &n in &normals { for &m in &normals { for a in offsets { for b in offsets {
            let first = [n[0], n[1], a, 0.0];
            let second = [m[0], m[1], b, 0.0];
            inputs.extend([first, second]);
            areas.push(expected(first, second));
        }}}}
        super::super::with_gpu(|gpu| {
            let text = include_str!("vector.wgsl");
            let begin = text.find("fn side_area(").unwrap();
            let end = text.find("// What covers a pixel").unwrap();
            let source = format!("{}\n{}", &text[begin..end], r#"
                @group(0) @binding(0) var<storage, read> cases: array<vec4<f32>>;
                @group(0) @binding(1) var<storage, read_write> areas: array<f32>;
                @compute @workgroup_size(64)
                fn area_test(@builtin(global_invocation_id) gid: vec3<u32>) {
                    if (gid.x >= arrayLength(&areas)) { return; }
                    let a = cases[2u * gid.x];
                    let b = cases[2u * gid.x + 1u];
                    areas[gid.x] = both_area(a.xy, a.z, b.xy, b.z);
                }
            "#);
            let device = &gpu.device;
            let module = device.create_shader_module(wgpu::ShaderModuleDescriptor { label: Some("area law"), source: wgpu::ShaderSource::Wgsl(source.into()) });
            let pipeline = device.create_compute_pipeline(&wgpu::ComputePipelineDescriptor { label: Some("area law"), layout: None, module: &module, entry_point: Some("area_test"), compilation_options: Default::default(), cache: None });
            let input = buffer(device, "area inputs", (inputs.len() * 16) as u64, wgpu::BufferUsages::STORAGE | wgpu::BufferUsages::COPY_DST);
            gpu.queue.write_buffer(&input, 0, bytemuck::cast_slice(&inputs));
            let size = (areas.len() * 4) as u64;
            let output = buffer(device, "areas", size, wgpu::BufferUsages::STORAGE | wgpu::BufferUsages::COPY_SRC);
            let read = buffer(device, "area read", size, wgpu::BufferUsages::COPY_DST | wgpu::BufferUsages::MAP_READ);
            let bindings = device.create_bind_group(&wgpu::BindGroupDescriptor { label: None, layout: &pipeline.get_bind_group_layout(0), entries: &[
                wgpu::BindGroupEntry { binding: 0, resource: input.as_entire_binding() },
                wgpu::BindGroupEntry { binding: 1, resource: output.as_entire_binding() },
            ] });
            let mut encoder = device.create_command_encoder(&Default::default());
            {
                let mut pass = encoder.begin_compute_pass(&Default::default());
                pass.set_pipeline(&pipeline);
                pass.set_bind_group(0, &bindings, &[]);
                pass.dispatch_workgroups((areas.len() as u32).div_ceil(64), 1, 1);
            }
            encoder.copy_buffer_to_buffer(&output, 0, &read, 0, size);
            gpu.queue.submit([encoder.finish()]);
            read.slice(..).map_async(wgpu::MapMode::Read, |result| result.unwrap());
            device.poll(wgpu::PollType::wait_indefinitely()).unwrap();
            let data = read.slice(..).get_mapped_range().unwrap();
            for (i, (actual, expected)) in bytemuck::cast_slice::<_, f32>(&data).iter().zip(areas).enumerate() {
                assert!(actual.is_finite() && (*actual as f64 - expected).abs() < 2e-6, "case {:?}: {actual} != {expected}", &inputs[2*i..2*i+2]);
            }
        }).unwrap();
    }
}