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.

20.0 KB
Raw Blame
//! Boolean operations on filled paths: Figma's union, subtract, intersect,
//! and exclude, for boolean layers and flattening.
//!
//! An operand is a list of paths, each filled with its own winding rule.
//! Curves are flattened to short lines and every point is snapped to a fine
//! grid, so the arithmetic below is exact. Every edge is split where it
//! meets another and coincident pieces are merged. For each piece, the
//! operands' winding numbers on its two sides (counted with a ray from its
//! midpoint) say whether the result covers either side; the pieces with the
//! result on exactly one side are the result's outline. They are turned to
//! have the result on their left, chained into closed contours (filled
//! nonzero), and runs of pieces that came from one curve are drawn as that
//! curve again, so circles stay circles.

use std::collections::HashMap;
use tiny_skia::{FillRule, Path, PathBuilder, PathSegment};

/// How the operands combine. The first operand is the bottom layer.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum BoolOp {
    Union,
    /// The first operand minus all the others.
    Subtract,
    Intersect,
    /// Covered by an odd number of operands.
    Exclude,
}

impl BoolOp {
    /// Figma's `booleanOperation` names (`XOR` is Exclude).
    pub fn parse(s: &str) -> Option<BoolOp> {
        match s {
            "UNION" => Some(BoolOp::Union),
            "SUBTRACT" => Some(BoolOp::Subtract),
            "INTERSECT" => Some(BoolOp::Intersect),
            "XOR" | "EXCLUDE" => Some(BoolOp::Exclude),
            _ => None,
        }
    }

    pub fn figma_name(self) -> &'static str {
        match self {
            BoolOp::Union => "UNION",
            BoolOp::Subtract => "SUBTRACT",
            BoolOp::Intersect => "INTERSECT",
            BoolOp::Exclude => "XOR",
        }
    }

    /// The layer name Figma gives a new boolean.
    pub fn label(self) -> &'static str {
        match self {
            BoolOp::Union => "Union",
            BoolOp::Subtract => "Subtract",
            BoolOp::Intersect => "Intersect",
            BoolOp::Exclude => "Exclude",
        }
    }

    fn covers(self, inside: &[bool]) -> bool {
        match self {
            BoolOp::Union => inside.iter().any(|&b| b),
            BoolOp::Subtract => {
                inside.first().copied().unwrap_or(false) && !inside[1..].iter().any(|&b| b)
            }
            BoolOp::Intersect => !inside.is_empty() && inside.iter().all(|&b| b),
            BoolOp::Exclude => inside.iter().filter(|&&b| b).count() % 2 == 1,
        }
    }
}

/// One operand: paths in a space shared by all operands, each with the
/// rule it is filled by.
pub type Operand = Vec<(Path, FillRule)>;

/// Grid points per unit.
const GRID: f64 = 4096.0;
/// Largest distance (units) between a curve and the lines standing in for it.
const TOLERANCE: f64 = 0.005;
const MAX_STEPS: usize = 256;

type Pt = (i64, i64);

/// A curve of the input, as a cubic; flattened edges point back to it.
type Cubic = [(f64, f64); 4];

/// Where an edge came from: a curve and the parameters at its two ends.
type Tag = Option<(u32, f64, f64)>;

#[derive(Clone, Copy)]
struct Edge {
    a: Pt,
    b: Pt,
    slot: u32,
    tag: Tag,
}

/// Coincident edge pieces, merged: the segment from `p` to `q` (`p` < `q`)
/// and, per piece, its path slot and direction (+1 from `p` to `q`).
struct Group {
    p: Pt,
    q: Pt,
    members: Vec<(u32, i32)>,
    tag: Tag,
}

/// The region `op` makes of `operands`, filled nonzero; `None` when empty.
pub fn combine(op: BoolOp, operands: &[Operand]) -> Option<Path> {
    let mut curves: Vec<Cubic> = Vec::new();
    let mut edges: Vec<Edge> = Vec::new();
    // Each path is a slot with its own winding; an operand covers a point
    // when any of its slots does.
    let mut slot_operand: Vec<usize> = Vec::new();
    let mut slot_rule: Vec<FillRule> = Vec::new();
    for (k, operand) in operands.iter().enumerate() {
        for (path, rule) in operand {
            let slot = slot_operand.len() as u32;
            slot_operand.push(k);
            slot_rule.push(*rule);
            flatten(path, slot, &mut curves, &mut edges);
        }
    }
    if edges.is_empty() {
        return None;
    }
    let pieces = split(&edges);
    let groups = merge(pieces);
    let kept = classify(op, &groups, &slot_operand, &slot_rule, operands.len());
    build(&chain(kept), &curves)
}

fn snap(x: f64, y: f64) -> Pt {
    ((x * GRID).round() as i64, (y * GRID).round() as i64)
}

fn unsnap(p: Pt) -> (f32, f32) {
    ((p.0 as f64 / GRID) as f32, (p.1 as f64 / GRID) as f32)
}

fn cubic_at(c: &Cubic, t: f64) -> (f64, f64) {
    let u = 1.0 - t;
    let (a, b, cc, d) = (u * u * u, 3.0 * u * u * t, 3.0 * u * t * t, t * t * t);
    (
        a * c[0].0 + b * c[1].0 + cc * c[2].0 + d * c[3].0,
        a * c[0].1 + b * c[1].1 + cc * c[2].1 + d * c[3].1,
    )
}

/// Flattens `path` (its contours closed, as filling closes them) into
/// `edges` for `slot`.
fn flatten(path: &Path, slot: u32, curves: &mut Vec<Cubic>, edges: &mut Vec<Edge>) {
    let mut start = (0.0, 0.0);
    let mut last = (0.0, 0.0);
    let mut open = false;
    let line = |edges: &mut Vec<Edge>, a: (f64, f64), b: (f64, f64)| {
        let (pa, pb) = (snap(a.0, a.1), snap(b.0, b.1));
        if pa != pb {
            edges.push(Edge {
                a: pa,
                b: pb,
                slot,
                tag: None,
            });
        }
    };
    let pt = |p: tiny_skia::Point| (f64::from(p.x), f64::from(p.y));
    for seg in path.segments() {
        match seg {
            PathSegment::MoveTo(p) => {
                if open {
                    line(edges, last, start);
                }
                start = pt(p);
                last = start;
                open = true;
            }
            PathSegment::LineTo(p) => {
                let p = pt(p);
                line(edges, last, p);
                last = p;
            }
            PathSegment::QuadTo(c, p) => {
                let (c, p) = (pt(c), pt(p));
                let c1 = (
                    last.0 + (c.0 - last.0) * 2.0 / 3.0,
                    last.1 + (c.1 - last.1) * 2.0 / 3.0,
                );
                let c2 = (p.0 + (c.0 - p.0) * 2.0 / 3.0, p.1 + (c.1 - p.1) * 2.0 / 3.0);
                push_cubic([last, c1, c2, p], slot, curves, edges);
                last = p;
            }
            PathSegment::CubicTo(c1, c2, p) => {
                let p = pt(p);
                push_cubic([last, pt(c1), pt(c2), p], slot, curves, edges);
                last = p;
            }
            PathSegment::Close => {
                line(edges, last, start);
                last = start;
                open = false;
            }
        }
    }
    if open {
        line(edges, last, start);
    }
}

fn push_cubic(c: Cubic, slot: u32, curves: &mut Vec<Cubic>, edges: &mut Vec<Edge>) {
    // Uniform steps keep the chord error under the tolerance: it is at most
    // max|B''| / (8 n²), and |B''| ≤ 6 × the largest second difference.
    let dd = |i: usize| {
        let x = c[i].0 - 2.0 * c[i + 1].0 + c[i + 2].0;
        let y = c[i].1 - 2.0 * c[i + 1].1 + c[i + 2].1;
        (x * x + y * y).sqrt()
    };
    let l = dd(0).max(dd(1));
    let steps = ((0.75 * l / TOLERANCE).sqrt().ceil() as usize).clamp(1, MAX_STEPS);
    let id = curves.len() as u32;
    curves.push(c);
    let mut prev = snap(c[0].0, c[0].1);
    let mut prev_t = 0.0;
    for i in 1..=steps {
        let t = i as f64 / steps as f64;
        let (x, y) = if i == steps { c[3] } else { cubic_at(&c, t) };
        let p = snap(x, y);
        if p != prev {
            edges.push(Edge {
                a: prev,
                b: p,
                slot,
                tag: Some((id, prev_t, t)),
            });
            prev = p;
            prev_t = t;
        }
    }
}

fn sub(a: Pt, b: Pt) -> (i128, i128) {
    (i128::from(a.0 - b.0), i128::from(a.1 - b.1))
}

fn cross(a: (i128, i128), b: (i128, i128)) -> i128 {
    a.0 * b.1 - a.1 * b.0
}

fn dot(a: (i128, i128), b: (i128, i128)) -> i128 {
    a.0 * b.0 + a.1 * b.1
}

/// Splits every edge where it meets another (crossings, touching ends, and
/// overlaps), returning the pieces.
fn split(edges: &[Edge]) -> Vec<Edge> {
    let n = edges.len();
    let mut cuts: Vec<Vec<(f64, Pt)>> = vec![Vec::new(); n];
    let min_x = |e: &Edge| e.a.0.min(e.b.0);
    let mut order: Vec<usize> = (0..n).collect();
    order.sort_by_key(|&i| min_x(&edges[i]));
    for (k, &i) in order.iter().enumerate() {
        let ei = &edges[i];
        let max_x = ei.a.0.max(ei.b.0);
        let (y0, y1) = (ei.a.1.min(ei.b.1), ei.a.1.max(ei.b.1));
        for &j in &order[k + 1..] {
            let ej = &edges[j];
            if min_x(ej) > max_x {
                break;
            }
            if ej.a.1.max(ej.b.1) < y0 || ej.a.1.min(ej.b.1) > y1 {
                continue;
            }
            intersect(ei, ej, i, j, &mut cuts);
        }
    }
    let mut out = Vec::with_capacity(n + n / 4);
    for (e, mut at) in edges.iter().zip(cuts) {
        if at.is_empty() {
            out.push(*e);
            continue;
        }
        at.sort_by(|x, y| x.0.total_cmp(&y.0));
        let mut from = e.a;
        let mut from_t = 0.0;
        for (t, p) in at.into_iter().chain(std::iter::once((1.0, e.b))) {
            if p == from {
                continue;
            }
            let tag = e
                .tag
                .map(|(id, t0, t1)| (id, t0 + (t1 - t0) * from_t, t0 + (t1 - t0) * t));
            out.push(Edge {
                a: from,
                b: p,
                slot: e.slot,
                tag,
            });
            from = p;
            from_t = t;
        }
    }
    out
}

/// Records where edges `i` and `j` meet, as cuts along each.
fn intersect(ei: &Edge, ej: &Edge, i: usize, j: usize, cuts: &mut [Vec<(f64, Pt)>]) {
    let r = sub(ei.b, ei.a);
    let s = sub(ej.b, ej.a);
    let qp = sub(ej.a, ei.a);
    let denom = cross(r, s);
    if denom == 0 {
        if cross(qp, r) != 0 {
            return;
        }
        // Collinear: each one's ends that lie inside the other cut it.
        let inside = |e: &Edge, d: (i128, i128), p: Pt| -> Option<f64> {
            let len2 = dot(d, d);
            let along = dot(sub(p, e.a), d);
            (along > 0 && along < len2).then(|| along as f64 / len2 as f64)
        };
        for p in [ej.a, ej.b] {
            if let Some(t) = inside(ei, r, p) {
                cuts[i].push((t, p));
            }
        }
        for p in [ei.a, ei.b] {
            if let Some(t) = inside(ej, s, p) {
                cuts[j].push((t, p));
            }
        }
        return;
    }
    let (mut t_num, mut u_num, mut d) = (cross(qp, s), cross(qp, r), denom);
    if d < 0 {
        (t_num, u_num, d) = (-t_num, -u_num, -d);
    }
    if t_num < 0 || t_num > d || u_num < 0 || u_num > d {
        return;
    }
    let point = if u_num == 0 {
        ej.a
    } else if u_num == d {
        ej.b
    } else if t_num == 0 {
        ei.a
    } else if t_num == d {
        ei.b
    } else {
        let t = t_num as f64 / d as f64;
        (
            (ei.a.0 as f64 + r.0 as f64 * t).round() as i64,
            (ei.a.1 as f64 + r.1 as f64 * t).round() as i64,
        )
    };
    if t_num > 0 && t_num < d && point != ei.a && point != ei.b {
        cuts[i].push((t_num as f64 / d as f64, point));
    }
    if u_num > 0 && u_num < d && point != ej.a && point != ej.b {
        cuts[j].push((u_num as f64 / d as f64, point));
    }
}

/// Merges coincident pieces.
fn merge(pieces: Vec<Edge>) -> Vec<Group> {
    let mut index: HashMap<(Pt, Pt), usize> = HashMap::with_capacity(pieces.len());
    let mut groups: Vec<Group> = Vec::with_capacity(pieces.len());
    for e in pieces {
        let forward = e.a < e.b;
        let (p, q) = if forward { (e.a, e.b) } else { (e.b, e.a) };
        let dir = if forward { 1 } else { -1 };
        match index.get(&(p, q)) {
            Some(&g) => groups[g].members.push((e.slot, dir)),
            None => {
                index.insert((p, q), groups.len());
                groups.push(Group {
                    p,
                    q,
                    members: vec![(e.slot, dir)],
                    tag: if forward {
                        e.tag
                    } else {
                        e.tag.map(|(id, t0, t1)| (id, t1, t0))
                    },
                });
            }
        }
    }
    groups
}

/// The groups on the result's outline, as directed edges with the result on
/// their left.
fn classify(
    op: BoolOp,
    groups: &[Group],
    slot_operand: &[usize],
    slot_rule: &[FillRule],
    operand_count: usize,
) -> Vec<(Pt, Pt, Tag)> {
    // Horizontal bands of the groups each crosses, for the ray counts.
    let (y_min, y_max) = groups.iter().fold((i64::MAX, i64::MIN), |(lo, hi), g| {
        (lo.min(g.p.1.min(g.q.1)), hi.max(g.p.1.max(g.q.1)))
    });
    let bands = ((groups.len() as f64).sqrt() as usize).clamp(1, 2048);
    let span = (y_max - y_min + 1) as f64 / bands as f64;
    let band_of = |y: f64| (((y - y_min as f64) / span) as usize).min(bands - 1);
    let mut band: Vec<Vec<u32>> = vec![Vec::new(); bands];
    for (k, g) in groups.iter().enumerate() {
        let (lo, hi) = (g.p.1.min(g.q.1), g.p.1.max(g.q.1));
        if lo == hi {
            continue; // Horizontal pieces never count for a horizontal ray.
        }
        for b in band
            .iter_mut()
            .take(band_of(hi as f64) + 1)
            .skip(band_of(lo as f64))
        {
            b.push(k as u32);
        }
    }
    let slots = slot_operand.len();
    let mut h = vec![0i32; slots];
    let mut d = vec![0i32; slots];
    let mut inside = vec![false; operand_count];
    let mut kept = Vec::new();
    let covered = |w: &[i32], inside: &mut [bool]| {
        inside.iter_mut().for_each(|b| *b = false);
        for (s, &wn) in w.iter().enumerate() {
            let hit = match slot_rule[s] {
                FillRule::Winding => wn != 0,
                FillRule::EvenOdd => wn % 2 != 0,
            };
            if hit {
                inside[slot_operand[s]] = true;
            }
        }
        op.covers(inside)
    };
    let mut left = vec![0i32; slots];
    let mut right = vec![0i32; slots];
    for (k, g) in groups.iter().enumerate() {
        h.iter_mut().for_each(|v| *v = 0);
        d.iter_mut().for_each(|v| *v = 0);
        // Doubled coordinates keep the midpoint on the grid.
        let m = (g.p.0 + g.q.0, g.p.1 + g.q.1);
        for &o in &band[band_of(m.1 as f64 / 2.0)] {
            if o as usize == k {
                continue;
            }
            let other = &groups[o as usize];
            let a = (other.p.0 * 2, other.p.1 * 2);
            let b = (other.q.0 * 2, other.q.1 * 2);
            let side = cross(sub(b, a), sub(m, a));
            let c = if a.1 <= m.1 && m.1 < b.1 && side > 0 {
                1
            } else if b.1 <= m.1 && m.1 < a.1 && side < 0 {
                -1
            } else {
                0
            };
            if c != 0 {
                for &(slot, dir) in &other.members {
                    h[slot as usize] += c * dir;
                }
            }
        }
        for &(slot, dir) in &g.members {
            d[slot as usize] += dir;
        }
        // The count is the winding on the ray's side of the piece: its +x
        // side, or +y for a horizontal piece. Crossing the piece from its
        // right to its left adds `d`.
        for s in 0..slots {
            if g.q.1 > g.p.1 {
                right[s] = h[s];
                left[s] = h[s] + d[s];
            } else {
                left[s] = h[s];
                right[s] = h[s] - d[s];
            }
        }
        let l = covered(&left, &mut inside);
        let r = covered(&right, &mut inside);
        if l != r {
            kept.push(if l {
                (g.p, g.q, g.tag)
            } else {
                (g.q, g.p, g.tag.map(|(id, t0, t1)| (id, t1, t0)))
            });
        }
    }
    kept
}

/// Chains directed edges into closed contours.
fn chain(edges: Vec<(Pt, Pt, Tag)>) -> Vec<Vec<(Pt, Pt, Tag)>> {
    let mut from: HashMap<Pt, Vec<usize>> = HashMap::with_capacity(edges.len());
    for (k, e) in edges.iter().enumerate() {
        from.entry(e.0).or_default().push(k);
    }
    let mut used = vec![false; edges.len()];
    let mut contours = Vec::new();
    for start in 0..edges.len() {
        if used[start] {
            continue;
        }
        let mut contour = Vec::new();
        let mut at = start;
        loop {
            used[at] = true;
            contour.push(edges[at]);
            let next = from
                .get(&edges[at].1)
                .and_then(|list| list.iter().copied().find(|&n| !used[n]));
            match next {
                Some(n) => at = n,
                None => break,
            }
        }
        if contour.len() >= 2 {
            contours.push(contour);
        }
    }
    contours
}

/// The cubic `c` between parameters `t0` and `t1` (either order).
fn sub_cubic(c: &Cubic, t0: f64, t1: f64) -> Cubic {
    if t0 > t1 {
        let [a, b, cc, d] = sub_cubic(c, t1, t0);
        return [d, cc, b, a];
    }
    let lerp =
        |a: (f64, f64), b: (f64, f64), t: f64| (a.0 + (b.0 - a.0) * t, a.1 + (b.1 - a.1) * t);
    // Left part, [0, t1].
    let split_left = |c: &Cubic, t: f64| -> Cubic {
        let ab = lerp(c[0], c[1], t);
        let bc = lerp(c[1], c[2], t);
        let cd = lerp(c[2], c[3], t);
        let abc = lerp(ab, bc, t);
        let bcd = lerp(bc, cd, t);
        [c[0], ab, abc, lerp(abc, bcd, t)]
    };
    let split_right = |c: &Cubic, t: f64| -> Cubic {
        let ab = lerp(c[0], c[1], t);
        let bc = lerp(c[1], c[2], t);
        let cd = lerp(c[2], c[3], t);
        let abc = lerp(ab, bc, t);
        let bcd = lerp(bc, cd, t);
        [lerp(abc, bcd, t), bcd, cd, c[3]]
    };
    let left = if t1 < 1.0 { split_left(c, t1) } else { *c };
    if t0 <= 0.0 || t1 <= 0.0 {
        return left;
    }
    split_right(&left, t0 / t1)
}

/// Draws the contours, with runs from one curve as that curve.
fn build(contours: &[Vec<(Pt, Pt, Tag)>], curves: &[Cubic]) -> Option<Path> {
    let mut pb = PathBuilder::new();
    for contour in contours {
        let (x, y) = unsnap(contour[0].0);
        pb.move_to(x, y);
        let mut k = 0;
        while k < contour.len() {
            let (a, mut b, tag) = contour[k];
            k += 1;
            match tag {
                Some((id, t0, mut t1)) => {
                    // Extend through pieces continuing the same curve.
                    while k < contour.len() {
                        match contour[k].2 {
                            Some((id2, s0, s1))
                                if id2 == id
                                    && (s0 - t1).abs() < 1e-9
                                    && (s1 - s0).signum() == (t1 - t0).signum() =>
                            {
                                t1 = s1;
                                b = contour[k].1;
                                k += 1;
                            }
                            _ => break,
                        }
                    }
                    let c = sub_cubic(&curves[id as usize], t0, t1);
                    let (bx, by) = unsnap(b);
                    pb.cubic_to(
                        c[1].0 as f32,
                        c[1].1 as f32,
                        c[2].0 as f32,
                        c[2].1 as f32,
                        bx,
                        by,
                    );
                }
                None => {
                    // Merge straight runs along one line.
                    while k < contour.len() && contour[k].2.is_none() {
                        let next = contour[k].1;
                        if cross(sub(b, a), sub(next, b)) != 0 || dot(sub(b, a), sub(next, b)) <= 0
                        {
                            break;
                        }
                        b = next;
                        k += 1;
                    }
                    let (bx, by) = unsnap(b);
                    pb.line_to(bx, by);
                }
            }
        }
        pb.close();
    }
    pb.finish()
}

#[cfg(test)]
mod test;