Skip to content

armgit / macro

Public Imported from GitHub
0

Macro is a unified workspace for teams: email, chat, docs, tasks, agents, calls, and CRM — @-linked together with shared AI memory.

12.0 KB
Raw Blame
//! Drawing meshes: patches are cut into a grid of triangles (one grid size
//! per mesh, so neighbors share edge points and leave no cracks), and
//! triangles are filled with colors interpolated across them (Gouraud
//! shading) into a scratch buffer, where later triangles cover earlier
//! ones, before blending once into the target.

use super::Shading;
use super::mesh::Mesh;
use super::paint::{Affine, Lut, Rect, Target, in_box};
use crate::color::{ColorSpace, to_u8};
use crate::function::MAX_ARITY;

/// Grid cells along a patch side, at most.
const MAX_STEPS: usize = 64;
/// Device pixels per grid cell side, roughly.
const CELL: f64 = 3.0;
/// Grid cells in a whole mesh, at most.
const MAX_CELLS: usize = 1 << 22;

/// Turns interpolated values into colors.
enum Colorizer<'a> {
    /// One value by table: `t` through the function, or the component of
    /// a one-component space, over `t0..=t1`.
    Table { lut: Lut, t0: f32, t1: f32 },
    /// Color space components, remembering the last conversion.
    Space {
        cs: &'a ColorSpace,
        last: Vec<f32>,
        rgb: [u8; 3],
    },
}

impl Colorizer<'_> {
    fn rgb(&mut self, values: &[f32]) -> [u8; 3] {
        match self {
            Colorizer::Table { lut, t0, t1 } => {
                let s = if t1 == t0 {
                    0.0
                } else {
                    (values[0] - *t0) / (*t1 - *t0)
                };
                lut.at(f64::from(s.clamp(0.0, 1.0)), [true, true])
                    .unwrap_or([0; 3])
            }
            Colorizer::Space { cs, last, rgb } => {
                if last.as_slice() != values {
                    last.clear();
                    last.extend_from_slice(values);
                    *rgb = cs.to_rgb(values).map(to_u8);
                }
                *rgb
            }
        }
    }
}

/// Painted colors over a rectangle of the target; alpha 0 where nothing
/// is painted.
struct Scratch {
    rect: Rect,
    rgba: Vec<u8>,
}

impl Scratch {
    fn put(&mut self, x: usize, y: usize, rgb: [u8; 3]) {
        let w = self.rect.x1 - self.rect.x0;
        let at = ((y - self.rect.y0) * w + (x - self.rect.x0)) * 4;
        self.rgba[at..at + 4].copy_from_slice(&[rgb[0], rgb[1], rgb[2], 255]);
    }
}

/// Device-space triangles with their colors.
struct Triangles {
    points: Vec<[f64; 2]>,
    colors: Vec<f32>,
    triangles: Vec<[u32; 3]>,
}

pub(super) fn mesh(sh: &Shading, mesh: &Mesh, target: &mut Target<'_>, to_device: Affine) {
    let n = mesh.ncomp;
    if n == 0 || n > MAX_ARITY {
        return;
    }
    let tris = if mesh.patches.is_empty() {
        Triangles {
            points: mesh
                .points
                .iter()
                .map(|p| {
                    let (x, y) = to_device.map(f64::from(p[0]), f64::from(p[1]));
                    [x, y]
                })
                .collect(),
            colors: mesh.colors.clone(),
            triangles: mesh.triangles.clone(),
        }
    } else {
        cut_patches(mesh, to_device)
    };
    if tris.triangles.is_empty() {
        return;
    }
    let (min, max) = tris.points.iter().fold(
        ((f64::MAX, f64::MAX), (f64::MIN, f64::MIN)),
        |(lo, hi), p| {
            (
                (lo.0.min(p[0]), lo.1.min(p[1])),
                (hi.0.max(p[0]), hi.1.max(p[1])),
            )
        },
    );
    let Some(mut rect) = target
        .bounds()
        .and_then(|r| r.intersect(Rect::covering(min, max)?))
    else {
        return;
    };
    if let Some(b) = sh.bbox {
        match Rect::of_box(b, to_device).and_then(|r| rect.intersect(r)) {
            Some(r) => rect = r,
            None => return,
        }
    }
    // As many table entries as the mesh is long on the device, at least.
    let samples = Lut::samples_for((max.0 - min.0).hypot(max.1 - min.1));
    let mut colorizer = match &mesh.function {
        Some(function) => {
            let [t0, t1] = mesh.t_range;
            Colorizer::Table {
                lut: Lut::new(&sh.color_space, function, [t0, t1], samples),
                t0,
                t1,
            }
        }
        // One component (a spot color, say): a table over its range
        // rather than its tint transform per pixel.
        None if n == 1 => {
            let [t0, t1] = sh
                .color_space
                .ranges()
                .first()
                .copied()
                .unwrap_or([0.0, 1.0]);
            Colorizer::Table {
                lut: Lut::of_space(&sh.color_space, [t0, t1], samples),
                t0,
                t1,
            }
        }
        None => Colorizer::Space {
            cs: &sh.color_space,
            last: Vec::new(),
            rgb: [0; 3],
        },
    };
    let (w, h) = (rect.x1 - rect.x0, rect.y1 - rect.y0);
    let mut scratch = Scratch {
        rect,
        rgba: Vec::new(),
    };
    if scratch.rgba.try_reserve_exact(w * h * 4).is_err() {
        return;
    }
    scratch.rgba.resize(w * h * 4, 0);
    for t in &tris.triangles {
        let corner = |k: usize| {
            let v = t[k] as usize;
            (
                tris.points.get(v).copied(),
                tris.colors.get(v * n..v * n + n),
            )
        };
        let (Some(p0), Some(c0)) = corner(0) else {
            continue;
        };
        let (Some(p1), Some(c1)) = corner(1) else {
            continue;
        };
        let (Some(p2), Some(c2)) = corner(2) else {
            continue;
        };
        triangle(&mut scratch, [p0, p1, p2], [c0, c1, c2], &mut colorizer);
    }
    // Blend once, so overlaps inside the mesh do not darken.
    let to_shading = to_device.invert();
    for y in rect.y0..rect.y1 {
        for x in rect.x0..rect.x1 {
            let at = ((y - rect.y0) * w + (x - rect.x0)) * 4;
            if scratch.rgba[at + 3] == 0 {
                continue;
            }
            if let (Some(b), Some(inv)) = (sh.bbox, to_shading) {
                let (sx, sy) = inv.map(x as f64 + 0.5, y as f64 + 0.5);
                if !in_box(Some(b), sx, sy) {
                    continue;
                }
            }
            let cover = target.coverage(x, y);
            if cover > 0 {
                let px = &scratch.rgba[at..at + 3];
                target.blend(x, y, [px[0], px[1], px[2]], cover);
            }
        }
    }
}

/// Cuts every patch into a grid of triangles, in device space.
fn cut_patches(mesh: &Mesh, to_device: Affine) -> Triangles {
    let n = mesh.ncomp;
    // One grid size for the mesh, from its largest patch.
    let largest = mesh
        .patches
        .iter()
        .map(|patch| {
            let pts = patch.points.iter().flatten();
            let (min, max) = pts.fold(
                ((f64::MAX, f64::MAX), (f64::MIN, f64::MIN)),
                |(lo, hi), p| {
                    let (x, y) = to_device.map(f64::from(p[0]), f64::from(p[1]));
                    ((lo.0.min(x), lo.1.min(y)), (hi.0.max(x), hi.1.max(y)))
                },
            );
            (max.0 - min.0).max(max.1 - min.1)
        })
        .fold(0.0f64, f64::max);
    let mut steps = if largest.is_finite() {
        ((largest / CELL).ceil() as usize).clamp(1, MAX_STEPS)
    } else {
        1
    };
    let patches = mesh.patches.len().max(1);
    while steps > 1 && steps * steps * patches > MAX_CELLS {
        steps -= 1;
    }
    let side = steps + 1;
    let mut out = Triangles {
        points: Vec::with_capacity(patches * side * side),
        colors: Vec::with_capacity(patches * side * side * n),
        triangles: Vec::with_capacity(patches * steps * steps * 2),
    };
    let bernstein = |t: f64| {
        let s = 1.0 - t;
        [s * s * s, 3.0 * t * s * s, 3.0 * t * t * s, t * t * t]
    };
    let basis: Vec<[f64; 4]> = (0..side)
        .map(|k| bernstein(k as f64 / steps as f64))
        .collect();
    for patch in &mesh.patches {
        let control = patch
            .points
            .map(|row| row.map(|p| to_device.map(f64::from(p[0]), f64::from(p[1]))));
        let corner = |k: usize| {
            let c = patch.corners[k] as usize * n;
            mesh.colors.get(c..c + n)
        };
        let (Some(c00), Some(c03), Some(c33), Some(c30)) =
            (corner(0), corner(1), corner(2), corner(3))
        else {
            continue;
        };
        let base = out.points.len() as u32;
        // Points row by row along v, each row along u.
        for (b, bv) in basis.iter().enumerate() {
            let v = b as f32 / steps as f32;
            for (a, bu) in basis.iter().enumerate() {
                let u = a as f32 / steps as f32;
                let (mut x, mut y) = (0.0, 0.0);
                for (i, wu) in bu.iter().enumerate() {
                    for (j, wv) in bv.iter().enumerate() {
                        let w = wu * wv;
                        x += w * control[i][j].0;
                        y += w * control[i][j].1;
                    }
                }
                out.points.push([x, y]);
                for k in 0..n {
                    let c = (1.0 - u) * (1.0 - v) * c00[k]
                        + (1.0 - u) * v * c03[k]
                        + u * v * c33[k]
                        + u * (1.0 - v) * c30[k];
                    out.colors.push(c);
                }
            }
        }
        // Cells in order of v, then u: later ones paint over earlier.
        let at = |a: usize, b: usize| base + (b * side + a) as u32;
        for b in 0..steps {
            for a in 0..steps {
                out.triangles
                    .push([at(a, b), at(a + 1, b), at(a + 1, b + 1)]);
                out.triangles
                    .push([at(a, b), at(a + 1, b + 1), at(a, b + 1)]);
            }
        }
    }
    out
}

/// Fills a triangle, interpolating its corners' values, into the scratch
/// buffer (pixel centers on an edge are inside).
fn triangle(
    scratch: &mut Scratch,
    p: [[f64; 2]; 3],
    c: [&[f32]; 3],
    colorizer: &mut Colorizer<'_>,
) {
    let edge = |a: [f64; 2], b: [f64; 2], x: f64, y: f64| {
        (b[0] - a[0]) * (y - a[1]) - (b[1] - a[1]) * (x - a[0])
    };
    let area = edge(p[0], p[1], p[2][0], p[2][1]);
    if area == 0.0 || !area.is_finite() {
        return;
    }
    // Make the area positive.
    let (p, c, area) = if area < 0.0 {
        ([p[0], p[2], p[1]], [c[0], c[2], c[1]], -area)
    } else {
        (p, c, area)
    };
    let rect = scratch.rect;
    let min_y = p.iter().map(|q| q[1]).fold(f64::MAX, f64::min);
    let max_y = p.iter().map(|q| q[1]).fold(f64::MIN, f64::max);
    let y0 = ((min_y - 0.5).ceil().max(rect.y0 as f64)) as usize;
    let y1 = ((max_y - 0.5).floor() + 1.0).min(rect.y1 as f64).max(0.0) as usize;
    // Edge k is opposite corner k: its function is corner k's weight.
    let edges = [(p[1], p[2]), (p[2], p[0]), (p[0], p[1])];
    let n = c[0].len().min(MAX_ARITY);
    let mut values = [0.0f32; MAX_ARITY];
    for y in y0..y1 {
        let cy = y as f64 + 0.5;
        // Each edge function is linear in x: e(x) = e0 + dx * x.
        let mut lo = rect.x0 as f64 + 0.5;
        let mut hi = rect.x1 as f64 - 0.5;
        let mut fns = [(0.0f64, 0.0f64); 3];
        for (k, &(a, b)) in edges.iter().enumerate() {
            let e0 = edge(a, b, 0.0, cy);
            let dx = -(b[1] - a[1]);
            fns[k] = (e0, dx);
            if dx > 0.0 {
                lo = lo.max(-e0 / dx);
            } else if dx < 0.0 {
                hi = hi.min(-e0 / dx);
            } else if e0 < 0.0 {
                hi = f64::MIN;
            }
        }
        if lo > hi {
            continue;
        }
        let x0 = ((lo - 0.5).ceil().max(rect.x0 as f64)) as usize;
        let x1 = ((hi - 0.5).floor() + 1.0).min(rect.x1 as f64).max(0.0) as usize;
        for x in x0..x1 {
            let cx = x as f64 + 0.5;
            let w = fns.map(|(e0, dx)| ((e0 + dx * cx) / area).clamp(0.0, 1.0) as f32);
            for (k, v) in values[..n].iter_mut().enumerate() {
                *v = w[0] * c[0][k] + w[1] * c[1][k] + w[2] * c[2][k];
            }
            let rgb = colorizer.rgb(&values[..n]);
            scratch.put(x, y, rgb);
        }
    }
}