2bc41aeb8602
area.rs
//! The outline a Blob Brush or Eraser drag shows while it is dragged: the boundary of the area its
//! tip covers, built a bounded amount at a time.
//!
//! The drag is cut into pieces of up to [`PIECE_SEGMENTS`] segments (one segment each when the
//! tip varies along the drag). A call outlines again, in the space where the tip is round, only the
//! pieces it added segments to. A piece's outline then loses the parts that lie inside the area
//! of another piece, found through a grid of squares that lists the segments near each square, so
//! the pieces show as one outline. When the tip's angle or roundness varies, each segment has its
//! own space where its tip is round, and the grid is on the page. One call takes at most [`POINTS_PER_CALL`] new points and does at most
//! [`WORK_PER_CALL`] units of work, plus the one step it was in; what is left waits for the next
//! call ([`AreaPreview::pending`]). Until then a piece shows the outline it last finished, and the
//! points not yet taken show as a thin line. The settled pieces show as paths of up to
//! [`BLOCK_PIECES`] pieces each, and a call joins again only the paths whose pieces changed, at
//! most [`JOIN_PIECES_PER_CALL`] pieces' worth. The grid holds at most [`LISTINGS`] listings.
use std::collections::{BTreeSet, HashMap};
use std::sync::Arc;
use vectorcraft_brush::Variation;
use vectorcraft_geom::{Affine, BezPath, Line, ParamCurve, PathData, PathEl, PathSeg, Point, SubPath};
use vectorcraft_pathops as po;
use vectorcraft_pathops::{Cap, Join};
use super::super::{MIN_BRUSH_SIZE, blob_tip, eraser_tip, pressure_size};
/// The most segments of a drag that one piece of its outline holds, when the tip does not vary
/// along the drag (a piece then holds one segment).
pub(super) const PIECE_SEGMENTS: usize = 32;
/// The most points of a drag one call takes.
pub(super) const POINTS_PER_CALL: usize = 256;
/// The most work one call does: one unit for each square of the grid a segment is listed in, and
/// for each segment of the drag a piece of an outline is checked against. A call stops before the
/// next point or the next segment of an outline once it has done this much.
pub(super) const WORK_PER_CALL: usize = 200_000;
/// The most segments one square of the grid lists. A segment past them is not listed there, and
/// the outlines inside its area there still show.
const SQUARE_SEGMENTS: usize = 128;
/// The most points, half a square apart, at which a segment of the drag is listed in the squares
/// around them. A longer segment is kept in a short list of its own ([`WIDE_SEGMENTS`]).
pub(super) const SEGMENT_SAMPLES: usize = 32;
/// The most listings all squares of the grid hold together: past them a segment is listed in no
/// square, and the outlines inside its area still show.
pub(super) const LISTINGS: usize = 4_000_000;
/// The most squares, along a side of an outline, whose segments the side is checked against; a
/// longer side is checked against the squares at its ends.
const SIDE_SQUARES: usize = 128;
/// The most pieces one joined path of the outline holds.
pub(super) const BLOCK_PIECES: usize = 64;
/// The most pieces one call joins into those paths; the others show the path last joined.
pub(super) const JOIN_PIECES_PER_CALL: usize = 2048;
/// The most segments the list of long segments holds; the outlines inside the area of a long
/// segment past them still show.
const WIDE_SEGMENTS: usize = 256;
/// The most points along a long segment at which the pieces near it are looked for.
const WIDE_SAMPLES: usize = 128;
/// The most points the thin line over the points not yet taken has.
const GUIDE_POINTS: usize = 256;
/// The most pieces a curve of an outline is checked in, each at its middle.
const CURVE_PIECES: usize = 32;
/// How far inside another piece's area, as a share of its radius, a piece of an outline must be
/// to be left out: an outline along the edge of another area still shows.
const INSIDE: f64 = 5e-3;
/// What the outline depends on besides the drag's points: a change starts it again.
#[derive(Clone, Copy, PartialEq, Debug)]
pub(super) struct AreaKey {
/// The Blob Brush's tip (else the Eraser's).
pub blob: bool,
pub size: f64,
pub variation: f64,
pub angle: f64,
pub roundness: f64,
/// Each segment takes its own tip from the pen's readings at its ends ([`AreaPreview::step`]):
/// its own size, and with `shaped` its own angle and roundness.
pub varies: bool,
/// Each segment's tip has its own angle and roundness.
pub shaped: bool,
/// The tips at the points take the pen's pressure there: once the pen presses less than fully,
/// a point pressed fully takes the tip of full pressure instead of that of a stroke without
/// pressure.
pub pressed: bool,
/// The bearing the tips take at the points before the pen first leaned, when a tip follows the
/// bearing: the first lean gives it to the points already outlined.
pub first_bearing: Option<f64>,
/// The modes and Variations of the angle, roundness and size that the tips at the points follow.
pub modes: [Variation; 3],
pub variations: [f64; 3],
}
/// A tip's angle in degrees, roundness in percent and size in points.
pub(super) type Tip = [f64; 3];
/// The work of the last call.
#[derive(Clone, Copy, Default, Debug)]
pub(super) struct AreaWork {
/// Points taken.
pub points: usize,
/// Points of the drag outlined.
pub outlined: usize,
/// Units of work ([`WORK_PER_CALL`]).
pub work: usize,
/// Pieces joined into the paths shown ([`JOIN_PIECES_PER_CALL`]).
pub joined: usize,
}
/// The paths of the outline to show ([`AreaPreview::paths`]).
pub(super) struct AreaPaths {
/// The settled pieces' outlines, joined [`BLOCK_PIECES`] at a time: a block that did not change
/// is the same shared path as in the call before.
pub settled: Vec<Arc<BezPath>>,
/// The growing last piece's outline and the thin line over the points not taken yet, drawn
/// over the settled ones.
pub live: Vec<BezPath>,
}
/// The joined outline of up to [`BLOCK_PIECES`] settled pieces.
#[derive(Default)]
struct Block {
/// Shared with the paths [`AreaPreview::paths`] returned: a new one only when the block is
/// joined again.
path: Arc<BezPath>,
/// A piece in it changed since `path` was joined.
stale: bool,
}
/// A piece of the drag: segments `from..to` (segment `j` joins points `j` and `j + 1`).
struct Piece {
from: usize,
to: usize,
/// Its outline where the tip is round, segment by segment: the segment, whether it starts a
/// contour and whether it ends a closed one.
outline: Vec<(PathSeg, bool, bool)>,
/// The part of its outline that shows, on the page.
shown: BezPath,
}
/// A piece whose outline is being checked, up to segment `at` of it.
struct Check {
piece: usize,
at: usize,
out: BezPath,
pen: Option<Point>,
/// Every segment of the current contour shows whole.
whole: bool,
}
pub(super) struct AreaPreview {
key: AreaKey,
first: Point,
/// The map from the page to the grid's space: where the tip is round, or the page itself when
/// each segment's tip has its own angle and roundness.
squash: Affine,
stretch: Affine,
/// The side of the grid's squares, in the grid's space.
side: f64,
/// The points taken, in the grid's space.
sq: Vec<Point>,
/// The last point taken, on the page.
last: Point,
/// The tip at the last point taken, when the tip varies along the drag.
last_tip: Option<Tip>,
/// The tip's radius along each segment, where its tip is round. It is also as far as the
/// segment's area reaches from the segment in the grid's space.
radius: Vec<f64>,
/// The map from the grid's space to the space where each segment's tip is round, when each
/// segment's tip has its own angle and roundness (empty otherwise: the grid's space).
to_round: Vec<Affine>,
pieces: Vec<Piece>,
squares: HashMap<(i64, i64), Vec<u32>>,
/// How many listings the squares hold ([`LISTINGS`]).
listed: usize,
wide: Vec<usize>,
/// The pieces whose outline is to be checked again.
dirty: BTreeSet<usize>,
check: Option<Check>,
/// The outlines that show of every piece but a growing last one, joined [`BLOCK_PIECES`] at a
/// time.
blocks: Vec<Block>,
pub work: AreaWork,
}
impl AreaPreview {
/// The outline of a drag that starts at `first`.
pub(super) fn new(key: AreaKey, first: Point) -> Self {
let stretch = match key {
AreaKey { shaped: true, .. } => Affine::IDENTITY,
AreaKey { blob: true, .. } => blob_tip(key.angle, key.roundness),
_ => eraser_tip(key.angle, key.roundness),
};
let widest = if key.varies { pressure_size(key.size, key.variation, 1.0) } else { key.size };
Self {
key,
first,
squash: stretch.inverse(),
stretch,
side: widest.max(MIN_BRUSH_SIZE),
sq: vec![],
last: first,
last_tip: None,
radius: vec![],
to_round: vec![],
pieces: vec![],
squares: HashMap::new(),
listed: 0,
wide: vec![],
dirty: BTreeSet::new(),
check: None,
blocks: vec![],
work: AreaWork::default(),
}
}
/// Is this the outline of the drag `pts` with `key`: the same start, and the points it took
/// still the drag's?
pub(super) fn fits(&self, key: AreaKey, pts: &[Point]) -> bool {
self.key == key
&& pts.first() == Some(&self.first)
&& self.sq.len() <= pts.len()
&& self.sq.len().checked_sub(1).and_then(|i| pts.get(i)) == Some(&self.last)
}
/// Is part of the drag `pts` not shown yet as it should be?
pub(super) fn pending(&self, pts: &[Point]) -> bool {
self.sq.len() < pts.len() || !self.dirty.is_empty() || self.check.is_some() || self.blocks.iter().any(|b| b.stale)
}
/// How many listings the grid's squares hold.
#[cfg(test)]
pub(super) fn listed(&self) -> usize {
self.listed
}
/// Mark the joined path that holds settled piece `k` to be joined again.
fn mark(&mut self, k: usize) {
let b = k / BLOCK_PIECES;
if self.blocks.len() <= b {
self.blocks.resize_with(b + 1, Block::default);
}
self.blocks[b].stale = true;
}
/// Take the points of the drag `pts` added since the last call and check outlines, within this
/// call's limits. When the tip varies along the drag, `tip(i)` gives the tip at point `i`, and
/// segment `j` takes `middle(j)`, the tip halfway along it. A last point whose tip changed since
/// it was taken (a pen turned or tilted in place) gives its segment the new tip.
pub(super) fn step(&mut self, pts: &[Point], tip: &dyn Fn(usize) -> Tip, middle: &dyn Fn(usize) -> Tip) {
self.work = AreaWork::default();
let mut changed = BTreeSet::new();
if self.key.varies
&& let Some(j) = self.sq.len().checked_sub(2)
&& self.last_tip.is_some_and(|t| t != tip(j + 1))
{
let k = self.piece_of(j);
let old = self.radius[j];
self.set_tip(j, middle(j));
self.last_tip = Some(tip(j + 1));
changed.insert(k);
// The pieces near the old tip or the new one are checked again.
let new = self.radius[j];
self.radius[j] = old.max(new);
self.near(j, k, false);
self.radius[j] = new;
}
while self.sq.len() < pts.len() && self.work.points < POINTS_PER_CALL && self.work.work < WORK_PER_CALL {
let i = self.sq.len();
self.sq.push(self.squash * pts[i]);
self.last = pts[i];
self.work.points += 1;
if self.key.varies {
self.last_tip = Some(tip(i));
}
let Some(j) = i.checked_sub(1) else { continue };
if self.key.varies {
self.radius.push(0.0);
self.set_tip(j, middle(j));
} else {
self.radius.push(self.key.size / 2.0);
}
if self.key.varies || self.pieces.last().is_none_or(|p| p.to - p.from >= PIECE_SEGMENTS) {
self.pieces.push(Piece { from: j, to: j, outline: vec![], shown: BezPath::new() });
}
let k = self.pieces.len() - 1;
self.pieces[k].to = j + 1;
changed.insert(k);
self.near(j, k, true);
}
for k in changed {
self.outline_piece(k);
}
self.check_some();
}
/// Give segment `j` the tip `[angle, roundness, size]`, the tip halfway along it: its radius,
/// and with `shaped` the map to the space where that tip is round.
fn set_tip(&mut self, j: usize, [angle, roundness, size]: Tip) {
self.radius[j] = size.max(MIN_BRUSH_SIZE) / 2.0;
if self.key.shaped {
let round = eraser_tip(angle, roundness).inverse();
match self.to_round.get_mut(j) {
Some(m) => *m = round,
None => self.to_round.push(round),
}
}
}
/// The map from the grid's space to the space where segment `m`'s tip is round.
fn round_of(&self, m: usize) -> Affine {
self.to_round.get(m).copied().unwrap_or(Affine::IDENTITY)
}
/// The paths to show: the settled pieces' outlines, joined [`BLOCK_PIECES`] at a time, the
/// growing last piece's and a thin line over the points of `pts` not taken yet. The joined
/// paths with a changed piece are joined again, newest first, at most
/// [`JOIN_PIECES_PER_CALL`] pieces a call; the others show the path last joined, the same
/// shared path each call.
pub(super) fn paths(&mut self, pts: &[Point]) -> AreaPaths {
let settled = self.settled_count();
for b in (0..self.blocks.len()).rev() {
if self.work.joined >= JOIN_PIECES_PER_CALL {
break;
}
if !self.blocks[b].stale {
continue;
}
let pieces = self.pieces.get(b * BLOCK_PIECES..settled.min((b + 1) * BLOCK_PIECES)).unwrap_or_default();
let mut joined = BezPath::new();
for p in pieces {
joined.extend(p.shown.elements().iter().copied());
}
self.work.joined += pieces.len();
self.blocks[b] = Block { path: Arc::new(joined), stale: false };
}
let settled_paths = self.blocks.iter().filter(|b| !b.path.elements().is_empty()).map(|b| Arc::clone(&b.path)).collect();
let mut out = vec![];
if let Some(p) = self.pieces.get(settled).filter(|p| !p.shown.elements().is_empty()) {
out.push(p.shown.clone());
}
if let Some(rest) = pts.get(self.sq.len()..).filter(|r| !r.is_empty()) {
let stride = rest.len().div_ceil(GUIDE_POINTS).max(1);
let mut guide = BezPath::new();
guide.move_to(self.last);
for p in rest.iter().skip(stride - 1).step_by(stride) {
guide.line_to(*p);
}
if let Some(&end) = rest.last().filter(|_| (rest.len() % stride) != 0) {
guide.line_to(end);
}
out.push(guide);
}
AreaPaths { settled: settled_paths, live: out }
}
/// How many pieces no longer grow: all of them but a last one with room for more segments.
fn settled_count(&self) -> usize {
let growing = !self.key.varies && self.pieces.last().is_some_and(|p| p.to - p.from < PIECE_SEGMENTS);
self.pieces.len() - usize::from(growing)
}
/// The piece that holds segment `j`.
fn piece_of(&self, j: usize) -> usize {
if self.key.varies { j } else { j / PIECE_SEGMENTS }
}
/// The square of the grid that holds `p`; `None` far outside any document.
fn square(&self, p: Point) -> Option<(i64, i64)> {
let (x, y) = ((p.x / self.side).floor(), (p.y / self.side).floor());
(x.abs() < 1e15 && y.abs() < 1e15).then_some((x as i64, y as i64))
}
/// The squares around points half a square apart along the segment from `a` to `b`: every
/// square holding a point within half a square of it. `None` past `samples` points.
fn squares_along(&self, a: Point, b: Point, samples: usize) -> Option<Vec<(i64, i64)>> {
let n = (a.distance(b) / (0.5 * self.side)).ceil().max(1.0);
if !n.is_finite() || n > samples as f64 {
return None;
}
let mut keys = vec![];
for k in 0..=(n as usize) {
let (x, y) = self.square(a.lerp(b, k as f64 / n))?;
for dy in -1..=1 {
for dx in -1..=1 {
keys.push((x + dx, y + dy));
}
}
}
keys.sort_unstable();
keys.dedup();
Some(keys)
}
/// With `add`, list segment `j` of piece `k` in the squares its area reaches; either way, mark
/// the other pieces whose outline its area can reach to be checked again.
fn near(&mut self, j: usize, k: usize, add: bool) {
let (a, b, r) = (self.sq[j], self.sq[j + 1], self.radius[j]);
let mut near = vec![];
match self.squares_along(a, b, SEGMENT_SAMPLES) {
Some(keys) => {
for key in keys {
self.work.work += 1;
if self.listed >= LISTINGS || !add {
near.extend(self.squares.get(&key).into_iter().flatten().map(|m| *m as usize));
continue;
}
let listed = self.squares.entry(key).or_default();
near.extend(listed.iter().map(|m| *m as usize));
if listed.len() < SQUARE_SEGMENTS {
listed.push(j as u32);
self.listed += 1;
}
}
}
None => {
// The pieces near points along it, at most WIDE_SAMPLES of them.
let n = (a.distance(b) / (0.5 * self.side)).ceil().clamp(1.0, WIDE_SAMPLES as f64);
for s in 0..=(n as usize) {
let Some((x, y)) = self.square(a.lerp(b, s as f64 / n)) else { continue };
for dy in -1..=1 {
for dx in -1..=1 {
self.work.work += 1;
near.extend(self.squares.get(&(x + dx, y + dy)).into_iter().flatten().map(|m| *m as usize));
}
}
}
if add && self.wide.len() < WIDE_SEGMENTS {
self.wide.push(j);
}
}
}
near.extend(self.wide.iter().copied().filter(|m| *m != j));
near.sort_unstable();
near.dedup();
for m in near {
self.work.work += 1;
let q = self.piece_of(m);
if q != k && !self.dirty.contains(&q) && segment_distance(a, b, self.sq[m], self.sq[m + 1]) < r + self.radius[m] {
self.dirty.insert(q);
if self.check.as_ref().is_some_and(|c| c.piece == q) {
self.check = None;
}
}
}
}
/// Outline piece `k` again, and mark it to be checked.
fn outline_piece(&mut self, k: usize) {
let settled = self.settled_count();
let Some(p) = self.pieces.get(k) else { return };
let width = 2.0 * self.radius[p.from];
self.work.outlined += p.to + 1 - p.from;
// A piece whose tip has its own angle and roundness (one segment) is outlined where that
// tip is round and taken back to the grid's space.
let area = match self.to_round.get(p.from) {
Some(&round) => {
let pts = [round * self.sq[p.from], round * self.sq[p.to]];
round.inverse()
* po::outline_stroke(&PathData::single(SubPath::polyline(&pts, false)), width, Cap::Round, Join::Round, 4.0).to_bezpath()
}
None => {
let pts = &self.sq[p.from..=p.to];
po::outline_stroke(&PathData::single(SubPath::polyline(pts, false)), width, Cap::Round, Join::Round, 4.0).to_bezpath()
}
};
let outline = segments(&area);
let shown = self.stretch * area;
if let Some(p) = self.pieces.get_mut(k) {
p.outline = outline;
p.shown = shown;
}
if self.check.as_ref().is_some_and(|c| c.piece == k) {
self.check = None;
}
self.dirty.insert(k);
if k < settled {
self.mark(k);
}
}
/// Check the outlines of the pieces marked, newest first, one segment of an outline at a
/// time, until this call's work is done.
fn check_some(&mut self) {
while self.work.work < WORK_PER_CALL {
let mut c = match self.check.take() {
Some(c) => c,
None => match self.dirty.pop_last() {
Some(piece) => Check { piece, at: 0, out: BezPath::new(), pen: None, whole: true },
None => break,
},
};
let Some(p) = self.pieces.get(c.piece) else { continue };
let Some(&(seg, starts, closes)) = p.outline.get(c.at) else {
// The whole outline is checked.
let settled = self.settled_count();
let shown = self.stretch * std::mem::take(&mut c.out);
if let Some(p) = self.pieces.get_mut(c.piece) {
p.shown = shown;
}
if c.piece < settled {
self.mark(c.piece);
}
continue;
};
let own = p.from..p.to;
if starts {
c.pen = None;
c.whole = true;
}
let runs = self.visible(seg, own);
if !matches!(runs[..], [(a, b)] if a == 0.0 && b == 1.0) {
c.whole = false;
}
for (a, b) in runs {
push_seg(&mut c.out, &mut c.pen, if a == 0.0 && b == 1.0 { seg } else { seg.subsegment(a..b) });
}
if closes && c.whole {
c.out.close_path();
c.pen = None;
}
c.at += 1;
self.check = Some(c);
}
}
/// The segments of the drag, but `own`, whose area can hold a point of the squares `keys`.
fn candidates(&mut self, keys: impl IntoIterator<Item = (i64, i64)>, own: &std::ops::Range<usize>) -> Vec<usize> {
let mut out: Vec<usize> = self.wide.clone();
for key in keys {
out.extend(self.squares.get(&key).into_iter().flatten().map(|m| *m as usize));
}
self.work.work += out.len();
out.retain(|m| !own.contains(m));
out.sort_unstable();
out.dedup();
out
}
/// The stretches of `seg` (from and to, 0 at its start, 1 at its end) that lie inside no area
/// of a segment of the drag but `own`.
fn visible(&mut self, seg: PathSeg, own: std::ops::Range<usize>) -> Vec<(f64, f64)> {
// Each segment's area is tested where its tip is round.
let inside = |s: &Self, q: Point, m: usize| {
let round = s.round_of(m);
distance_to_segment(round * q, round * s.sq[m], round * s.sq[m + 1]) < s.radius[m] * (1.0 - INSIDE)
};
match seg {
PathSeg::Line(line) => {
let len = line.p0.distance(line.p1);
let n = (len / self.side).ceil().max(1.0);
let keys: Vec<(i64, i64)> = if !n.is_finite() || n > SIDE_SQUARES as f64 {
// A very long side: the squares at its ends.
[line.p0, line.p1].into_iter().filter_map(|p| self.square(p)).collect()
} else {
let mut keys = vec![];
for i in 0..(n as usize) {
let (p, q) = (line.p0.lerp(line.p1, i as f64 / n), line.p0.lerp(line.p1, (i + 1) as f64 / n));
let (Some(lo), Some(hi)) =
(self.square(Point::new(p.x.min(q.x), p.y.min(q.y))), self.square(Point::new(p.x.max(q.x), p.y.max(q.y))))
else {
continue;
};
for y in lo.1..=hi.1 {
for x in lo.0..=hi.0 {
keys.push((x, y));
}
}
}
keys.sort_unstable();
keys.dedup();
keys
};
let near = self.candidates(keys, &own);
// A map keeps a line's points where they are along it.
let spans = near
.iter()
.filter_map(|&m| {
let round = self.round_of(m);
capsule_span(round * line, round * self.sq[m], round * self.sq[m + 1], self.radius[m] * (1.0 - INSIDE))
})
.collect();
gaps(&merge_spans(spans))
}
_ => {
let reach: f64 = match seg {
PathSeg::Quad(q) => q.p0.distance(q.p1) + q.p1.distance(q.p2),
PathSeg::Cubic(c) => c.p0.distance(c.p1) + c.p1.distance(c.p2) + c.p2.distance(c.p3),
PathSeg::Line(l) => l.p0.distance(l.p1),
};
let n = (reach / (0.025 * self.side)).ceil().clamp(1.0, CURVE_PIECES as f64) as usize;
let mut shows = vec![];
for i in 0..n {
let mid = seg.eval((i as f64 + 0.5) / n as f64);
let near = self.candidates(self.square(mid), &own);
shows.push(!near.iter().any(|&m| inside(self, mid, m)));
}
let mut runs: Vec<(f64, f64)> = vec![];
for (i, show) in shows.into_iter().enumerate() {
if !show {
continue;
}
let (a, b) = (i as f64 / n as f64, (i + 1) as f64 / n as f64);
match runs.last_mut() {
Some(last) if last.1 == a => last.1 = b,
_ => runs.push((a, b)),
}
}
runs
}
}
}
}
/// The segments of `path`: each with whether it starts a contour and whether it ends a closed one.
fn segments(path: &BezPath) -> Vec<(PathSeg, bool, bool)> {
let mut out: Vec<(PathSeg, bool, bool)> = vec![];
let (mut start, mut pen, mut first) = (Point::ZERO, Point::ZERO, true);
for el in path.elements() {
let seg = match *el {
PathEl::MoveTo(p) => {
(start, pen, first) = (p, p, true);
continue;
}
PathEl::LineTo(p) => PathSeg::Line(Line::new(pen, p)),
PathEl::QuadTo(p1, p2) => PathSeg::Quad(vectorcraft_geom::kurbo::QuadBez::new(pen, p1, p2)),
PathEl::CurveTo(p1, p2, p3) => PathSeg::Cubic(vectorcraft_geom::CubicBez::new(pen, p1, p2, p3)),
PathEl::ClosePath => {
if pen != start {
out.push((PathSeg::Line(Line::new(pen, start)), first, false));
first = false;
}
if !first && let Some(last) = out.last_mut() {
last.2 = true;
}
pen = start;
first = true;
continue;
}
};
out.push((seg, first, false));
first = false;
pen = seg.end();
}
out
}
/// Add `seg` to `out`, starting a new subpath unless it starts at `pen`, where the last one ended.
fn push_seg(out: &mut BezPath, pen: &mut Option<Point>, seg: PathSeg) {
let a = seg.start();
if *pen != Some(a) {
out.move_to(a);
}
match seg {
PathSeg::Line(l) => out.line_to(l.p1),
PathSeg::Quad(q) => out.quad_to(q.p1, q.p2),
PathSeg::Cubic(c) => out.curve_to(c.p1, c.p2, c.p3),
}
*pen = Some(seg.end());
}
/// How far `q` is from the segment from `a` to `b`.
fn distance_to_segment(q: Point, a: Point, b: Point) -> f64 {
let d = b - a;
let t = if d.hypot2() > 0.0 { ((q - a).dot(d) / d.hypot2()).clamp(0.0, 1.0) } else { 0.0 };
q.distance(a + d * t)
}
/// How far the segment from `a` to `b` is from the segment from `c` to `d`.
fn segment_distance(a: Point, b: Point, c: Point, d: Point) -> f64 {
let side = |p: Point, q: Point, s: Point| (q - p).cross(s - p);
if side(a, b, c) * side(a, b, d) < 0.0 && side(c, d, a) * side(c, d, b) < 0.0 {
return 0.0;
}
distance_to_segment(a, c, d).min(distance_to_segment(b, c, d)).min(distance_to_segment(c, a, b)).min(distance_to_segment(d, a, b))
}
/// The stretch of `line`, as from and to along it (0 at its start, 1 at its end, and beyond), that
/// lies within `rad` of the segment from `a` to `b`; `None` when no point of the line does.
fn capsule_span(line: Line, a: Point, b: Point, rad: f64) -> Option<(f64, f64)> {
let (p, d) = (line.p0, line.p1 - line.p0);
let dd = d.hypot2();
if dd <= 0.0 || rad.is_nan() || rad <= 0.0 {
return None;
}
let (mut lo, mut hi) = (f64::INFINITY, f64::NEG_INFINITY);
// The round ends.
for c in [a, b] {
let f = p - c;
let (half_b, k) = (d.dot(f), f.hypot2() - rad * rad);
let disc = half_b * half_b - dd * k;
if disc >= 0.0 {
let root = disc.sqrt();
lo = lo.min((-half_b - root) / dd);
hi = hi.max((-half_b + root) / dd);
}
}
// The part between them: along the segment from 0 to its length, and across it within `rad`.
let e = b - a;
let len = e.hypot();
if len > 0.0 {
let u = e / len;
let n = vectorcraft_geom::Vec2::new(-u.y, u.x);
let (mut s0, mut s1) = (f64::NEG_INFINITY, f64::INFINITY);
for (at, rate, min, max) in [((p - a).dot(u), d.dot(u), 0.0, len), ((p - a).dot(n), d.dot(n), -rad, rad)] {
if rate == 0.0 {
if at < min || at > max {
s1 = f64::NEG_INFINITY;
}
} else {
let (x, y) = ((min - at) / rate, (max - at) / rate);
s0 = s0.max(x.min(y));
s1 = s1.min(x.max(y));
}
}
if s0 <= s1 {
lo = lo.min(s0);
hi = hi.max(s1);
}
}
(lo < hi).then_some((lo, hi))
}
/// `spans` sorted and joined where they overlap.
fn merge_spans(mut spans: Vec<(f64, f64)>) -> Vec<(f64, f64)> {
spans.sort_by(|x, y| x.0.total_cmp(&y.0));
let mut out: Vec<(f64, f64)> = Vec::with_capacity(spans.len());
for (a, b) in spans {
match out.last_mut() {
Some(last) if a <= last.1 => last.1 = last.1.max(b),
_ => out.push((a, b)),
}
}
out
}
/// The stretches of 0 to 1 that none of `spans` (from [`merge_spans`]) holds.
fn gaps(spans: &[(f64, f64)]) -> Vec<(f64, f64)> {
let mut out = vec![];
let mut at = 0.0;
for &(a, b) in spans {
if b <= at {
continue;
}
if a >= 1.0 {
break;
}
if a > at {
out.push((at, a));
}
at = b;
}
if at < 1.0 {
out.push((at, 1.0));
}
out
}
No file is open. Choose one in the tree, or press Ctrl+O (⌘O on a Mac) to find one by name.
Syntax highlighting could not load. The unmodified read-only text remains available above.