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.

9.8 KB
Raw Blame
//! Boolean operations on filled outlines: PowerPoint's Merge Shapes (Union,
//! Combine, Fragment, Intersect, Subtract).
//!
//! Each input shape is a set of filled paths in slide space. Curves are
//! flattened (within [`FLATTEN_TOLERANCE`] points) and every vertex is snapped
//! to a fixed grid, so the arrangement of all edges can be built with exact
//! integer predicates: edges are split wherever they cross, touch, or overlap
//! (snap rounding keeps that consistent), then each edge learns which shapes
//! cover its two sides from exact winding numbers (the non-zero rule, which
//! is how the renderer fills). An operation keeps the edges whose two sides
//! differ in the result and chains them into closed contours with the
//! inside on their right: outer contours run clockwise on screen and holes
//! counter-clockwise, so the result fills the same with the even-odd and the
//! non-zero rule. Contour pieces that follow one input curve become that
//! curve again (the sub-curve between the cuts), so circles stay circles.

mod arrangement;
mod contour;

use arrangement::Arrangement;

/// How finely curves are flattened to find intersections (points).
pub const FLATTEN_TOLERANCE: f64 = 0.05;

/// A point in slide points.
#[derive(Clone, Copy, Debug, Default, PartialEq)]
pub struct Pt {
    /// Horizontal coordinate.
    pub x: f64,
    /// Vertical coordinate (down is positive).
    pub y: f64,
}

impl Pt {
    /// Creates a point.
    pub const fn new(x: f64, y: f64) -> Self {
        Self { x, y }
    }

    fn lerp(self, o: Pt, t: f64) -> Pt {
        Pt::new(self.x + (o.x - self.x) * t, self.y + (o.y - self.y) * t)
    }

    fn add(self, o: Pt) -> Pt {
        Pt::new(self.x + o.x, self.y + o.y)
    }

    fn sub(self, o: Pt) -> Pt {
        Pt::new(self.x - o.x, self.y - o.y)
    }
}

/// One piece of an outline.
#[derive(Clone, Copy, Debug, PartialEq)]
pub enum Seg {
    /// A straight line from the first point to the second.
    Line(Pt, Pt),
    /// A cubic Bézier: start, two control points, end.
    Cubic(Pt, Pt, Pt, Pt),
}

impl Seg {
    /// Where the segment starts.
    pub fn start(&self) -> Pt {
        match *self {
            Seg::Line(a, _) | Seg::Cubic(a, ..) => a,
        }
    }

    /// Where the segment ends.
    pub fn end(&self) -> Pt {
        match *self {
            Seg::Line(_, b) | Seg::Cubic(.., b) => b,
        }
    }

    /// The point at parameter `t` (0 at the start, 1 at the end).
    pub fn at(&self, t: f64) -> Pt {
        match *self {
            Seg::Line(a, b) => a.lerp(b, t),
            Seg::Cubic(p0, p1, p2, p3) => {
                let mt = 1.0 - t;
                let (a, b, c, d) = (mt * mt * mt, 3.0 * mt * mt * t, 3.0 * mt * t * t, t * t * t);
                Pt::new(
                    a * p0.x + b * p1.x + c * p2.x + d * p3.x,
                    a * p0.y + b * p1.y + c * p2.y + d * p3.y,
                )
            }
        }
    }

    /// The part of the segment between parameters `t0` and `t1` (reversed
    /// when `t1 < t0`).
    pub fn part(&self, t0: f64, t1: f64) -> Seg {
        match *self {
            Seg::Line(..) => Seg::Line(self.at(t0), self.at(t1)),
            Seg::Cubic(..) => {
                if t1 < t0 {
                    return self.part(t1, t0).reversed();
                }
                // Split at t1, keep the head, then split that at t0 / t1.
                let head = if t1 < 1.0 {
                    split_cubic(self, t1).0
                } else {
                    *self
                };
                if t0 <= 0.0 || t1 <= 0.0 {
                    return head;
                }
                split_cubic(&head, t0 / t1).1
            }
        }
    }

    /// The same segment traversed backwards.
    pub fn reversed(&self) -> Seg {
        match *self {
            Seg::Line(a, b) => Seg::Line(b, a),
            Seg::Cubic(a, b, c, d) => Seg::Cubic(d, c, b, a),
        }
    }
}

/// Splits a cubic at `t` (de Casteljau).
fn split_cubic(seg: &Seg, t: f64) -> (Seg, Seg) {
    let Seg::Cubic(p0, p1, p2, p3) = *seg else {
        let m = seg.at(t);
        return (Seg::Line(seg.start(), m), Seg::Line(m, seg.end()));
    };
    let a = p0.lerp(p1, t);
    let b = p1.lerp(p2, t);
    let c = p2.lerp(p3, t);
    let d = a.lerp(b, t);
    let e = b.lerp(c, t);
    let m = d.lerp(e, t);
    (Seg::Cubic(p0, a, d, m), Seg::Cubic(m, e, c, p3))
}

/// A filled path: closed loops filled by the non-zero winding rule. A loop
/// that does not end where it starts is closed with a straight line.
#[derive(Clone, Debug, Default, PartialEq)]
pub struct FillPath {
    /// The loops (sub-paths), each a chain of segments.
    pub loops: Vec<Vec<Seg>>,
}

/// One input shape: the union of its filled paths.
#[derive(Clone, Debug, Default, PartialEq)]
pub struct Operand {
    /// The filled paths.
    pub paths: Vec<FillPath>,
}

/// A merge operation, as PowerPoint names them.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum MergeMode {
    /// Everything any shape covers.
    Union,
    /// What an odd number of shapes covers (overlaps are cut out).
    Combine,
    /// Every region the outlines cut out, as separate pieces.
    Fragment,
    /// What every shape covers.
    Intersect,
    /// The first shape without what the others cover.
    Subtract,
}

/// One connected result region: an outer contour (clockwise on screen) and
/// its holes (counter-clockwise), or for single-result modes every contour
/// of the result.
#[derive(Clone, Debug, Default, PartialEq)]
pub struct Piece {
    /// Closed contours; each ends where it starts.
    pub loops: Vec<Vec<Seg>>,
}

/// The most operands an operation takes (each side of an edge records the
/// operands covering it in a 64-bit mask).
pub const MAX_OPERANDS: usize = 64;

/// Merges `operands` (at most [`MAX_OPERANDS`]). Fragment returns one piece
/// per connected region (with its holes); the other modes return one piece
/// holding the whole result, or nothing when the result is empty.
pub fn merge(operands: &[Operand], mode: MergeMode) -> Vec<Piece> {
    let n = operands.len().min(MAX_OPERANDS);
    let arr = Arrangement::build(&operands[..n]);
    let all: u64 = if n == 64 { u64::MAX } else { (1u64 << n) - 1 };
    let keep: fn(u64, u64) -> bool = match mode {
        MergeMode::Union => |m, _| m != 0,
        MergeMode::Intersect => |m, all| m != 0 && m == all,
        MergeMode::Subtract => |m, _| m == 1,
        MergeMode::Combine => |m, _| m.count_ones() % 2 == 1,
        MergeMode::Fragment => return fragment(&arr),
    };
    let loops = contour::chain(&arr.region_edges(|m| keep(m, all)));
    let loops: Vec<Vec<Seg>> = loops
        .iter()
        .filter(|l| !contour::is_sliver(l))
        .map(|l| contour::to_segs(l, &arr.curves))
        .filter(|l| !l.is_empty())
        .collect();
    if loops.is_empty() {
        Vec::new()
    } else {
        vec![Piece { loops }]
    }
}

/// Fragment: each distinct cover (set of operands) cut into its connected regions.
fn fragment(arr: &Arrangement) -> Vec<Piece> {
    let mut out = Vec::new();
    for label in arr.labels() {
        let loops: Vec<_> = contour::chain(&arr.region_edges(|m| m == label))
            .into_iter()
            .filter(|l| !contour::is_sliver(l))
            .collect();
        for piece in contour::assemble(loops) {
            let loops: Vec<Vec<Seg>> = piece
                .iter()
                .map(|l| contour::to_segs(l, &arr.curves))
                .filter(|l| !l.is_empty())
                .collect();
            if !loops.is_empty() {
                out.push(Piece { loops });
            }
        }
    }
    out
}

/// `[left, top, right, bottom]` of segments with curves counted exactly
/// (their extremes, not their control points); `None` when there are none.
pub fn bounds(segs: &[Seg]) -> Option<[f64; 4]> {
    let mut b: Option<[f64; 4]> = None;
    let mut add = |p: Pt| {
        b = Some(match b {
            None => [p.x, p.y, p.x, p.y],
            Some([l, t, r, bt]) => [l.min(p.x), t.min(p.y), r.max(p.x), bt.max(p.y)],
        });
    };
    for s in segs {
        add(s.start());
        add(s.end());
        if let Seg::Cubic(p0, p1, p2, p3) = *s {
            for t in extremes(p0.x, p1.x, p2.x, p3.x)
                .into_iter()
                .chain(extremes(p0.y, p1.y, p2.y, p3.y))
                .flatten()
            {
                add(s.at(t));
            }
        }
    }
    b
}

/// Parameters in (0, 1) where one coordinate of a cubic turns.
fn extremes(a: f64, b: f64, c: f64, d: f64) -> [Option<f64>; 2] {
    // The derivative over 3: p(1-t)² + 2q(1-t)t + r t².
    let (p, q, r) = (b - a, c - b, d - c);
    let (qa, qb, qc) = (p - 2.0 * q + r, 2.0 * (q - p), p);
    let inside = |t: f64| (t > 0.0 && t < 1.0).then_some(t);
    if qa.abs() < 1e-12 {
        if qb.abs() < 1e-12 {
            return [None, None];
        }
        return [inside(-qc / qb), None];
    }
    let disc = qb * qb - 4.0 * qa * qc;
    if disc < 0.0 {
        return [None, None];
    }
    let s = disc.sqrt();
    [
        inside((-qb + s) / (2.0 * qa)),
        inside((-qb - s) / (2.0 * qa)),
    ]
}

/// The signed area of a closed chain of segments (positive when clockwise on
/// screen), counting curves exactly.
pub fn area(loop_: &[Seg]) -> f64 {
    loop_
        .iter()
        .map(|s| match *s {
            Seg::Line(a, b) => (a.x * b.y - b.x * a.y) / 2.0,
            // Green's theorem over a cubic Bézier: ½∫(x y' − y x') dt is a
            // weighted sum of the control points' cross products.
            Seg::Cubic(p0, p1, p2, p3) => {
                let c = |a: Pt, b: Pt| a.x * b.y - b.x * a.y;
                (0.6 * c(p0, p1)
                    + 0.3 * c(p0, p2)
                    + 0.1 * c(p0, p3)
                    + 0.3 * c(p1, p2)
                    + 0.3 * c(p1, p3)
                    + 0.6 * c(p2, p3))
                    / 2.0
            }
        })
        .sum()
}

#[cfg(test)]
mod test;