Oregami
Repositories/oxedyne/fe2o3

oxedyne/fe2o3/fe2o3_graphics/src/path.rs

35.6 KiB, 83 runs

created by r1870400018:13942, which is this file's identity for as long as the history lasts, whatever it is later renamed to

download · who wrote it · its history

1//! Paths: the shapes a rasteriser fills.
2//!
3//! A path is a sequence of contours, each a run of lines and Bezier curves. Glyph outlines arrive
4//! in exactly this form, and so do boxes, rules and borders, so one type serves both.
5//!
6//! [Written with AI entirely](https://need2know.ai/entirely-ai/code)\
7//! Anthropic Claude
8
9use crate::transform::Transform;
10
11use oxedyne_fe2o3_core::prelude::*;
12
13// The default flattening tolerance, in pixels: the furthest a straight segment may stray from the
14// curve it stands in for. A tenth of a pixel is below what an eye can resolve at any sane size,
15// and well below what the anti-aliasing can express.
16pub const TOLERANCE: f32 = 0.1;
17
18// The most straight segments a single curve may be flattened into, however cruel its control
19// points. A curve needing more than this has been given nonsense coordinates.
20const MAX_STEPS: usize = 1_000;
21
22// How far along each tangent a control point sits, for a cubic bézier that meets a quarter arc:
23// the magic constant 4/3 * (sqrt(2) - 1), which makes a bézier hug a quarter circle to about one
24// part in a thousand of the radius. Every arc this module draws is built from it.
25const KAPPA: f32 = 0.552_284_75;
26
27#[derive(Clone, Copy, Debug, Default, PartialEq)]
28pub struct Pt {
29 pub x: f32,
30 pub y: f32,
31}
32
33impl Pt {
34
35 pub const fn new(x: f32, y: f32) -> Self {
36 Self { x, y }
37 }
38
39 pub fn midpoint(&self, other: Self) -> Self {
40 Self::new(0.5 * (self.x + other.x), 0.5 * (self.y + other.y))
41 }
42
43 pub fn distance(&self, other: Self) -> f32 {
44 let dx = other.x - self.x;
45 let dy = other.y - self.y;
46 (dx * dx + dy * dy).sqrt()
47 }
48
49 /// Are both coordinates finite? Every point reaching the rasteriser must be.
50 pub fn is_finite(&self) -> bool {
51 self.x.is_finite() && self.y.is_finite()
52 }
53}
54
55/// One step of a path.
56#[derive(Clone, Copy, Debug, PartialEq)]
57pub enum Seg {
58 MoveTo(Pt), // begins a new contour at a point
59 LineTo(Pt), // a straight line to a point
60 QuadTo(Pt, Pt), // quadratic bézier, one control point; TrueType outlines are these
61 CubicTo(Pt, Pt, Pt), // cubic bézier, two; PostScript outlines are these
62 Close, // back to where the contour began
63}
64
65/// An axis-aligned bounding box.
66#[derive(Clone, Copy, Debug, PartialEq)]
67pub struct Bounds {
68 pub x0: f32, // left edge
69 pub y0: f32, // top edge
70 pub x1: f32, // right edge, exclusive
71 pub y1: f32, // bottom edge, exclusive
72}
73
74impl Bounds {
75
76 /// Creates a bounding box, ordering the coordinates so that it is never inverted.
77 pub fn new(x0: f32, y0: f32, x1: f32, y1: f32) -> Self {
78 Self {
79 x0: x0.min(x1),
80 y0: y0.min(y1),
81 x1: x0.max(x1),
82 y1: y0.max(y1),
83 }
84 }
85
86 pub fn is_empty(&self) -> bool {
87 self.x1 <= self.x0 || self.y1 <= self.y0
88 }
89
90 pub fn intersect(&self, other: Self) -> Self {
91 Self {
92 x0: self.x0.max(other.x0),
93 y0: self.y0.max(other.y0),
94 x1: self.x1.min(other.x1),
95 y1: self.y1.min(other.y1),
96 }
97 }
98
99 /// The smallest box holding both this one and another.
100 ///
101 /// The counterpart of [`Bounds::intersect`], and what anything gathering several boxes into the
102 /// one that contains them needs: a compositor totalling the damage of a frame, an accessibility
103 /// tree giving a rectangle to a node that is made of several runs of text.
104 pub fn union(&self, other: Self) -> Self {
105 Self {
106 x0: self.x0.min(other.x0),
107 y0: self.y0.min(other.y0),
108 x1: self.x1.max(other.x1),
109 y1: self.y1.max(other.y1),
110 }
111 }
112
113 /// The box grown by `d` on every side, or shrunk where `d` is negative.
114 ///
115 /// A blur, a stroke and a shadow all reach past the shape they came from, so the box that holds
116 /// the ink is the box that holds the geometry, grown by that reach. The coordinates are not
117 /// reordered afterwards, as [`Bounds::new`] would: a shrink deeper than the box is wide leaves a
118 /// box that encloses nothing, and [`Bounds::is_empty`] should say so rather than have it turned
119 /// inside out into a box that encloses something.
120 pub fn grow(&self, d: f32) -> Self {
121 Self {
122 x0: self.x0 - d,
123 y0: self.y0 - d,
124 x1: self.x1 + d,
125 y1: self.y1 + d,
126 }
127 }
128
129 /// The width of the box, or zero if it is empty.
130 pub fn width(&self) -> f32 {
131 (self.x1 - self.x0).max(0.0)
132 }
133
134 /// The height of the box, or zero if it is empty.
135 pub fn height(&self) -> f32 {
136 (self.y1 - self.y0).max(0.0)
137 }
138}
139
140/// A contour after flattening: a polyline, and whether it ran back to where it began.
141///
142/// A fill can forget whether a contour was closed, since an interior is an interior either way. A
143/// stroke cannot: a closed contour is joined all the way round and an open one is capped at both
144/// ends, so the two give different ink.
145#[derive(Clone, Debug, Default, PartialEq)]
146pub struct Polyline {
147 pub pts: Vec<Pt>, // in order; a closed contour's closing point is not repeated
148 pub closed: bool, // does the contour close back onto its first point?
149}
150
151/// A shape: a sequence of contours built from lines and curves.
152#[derive(Clone, Debug, Default, PartialEq)]
153pub struct Path {
154 segs: Vec<Seg>,
155}
156
157impl Path {
158
159 pub fn segs(&self) -> &[Seg] {
160 &self.segs
161 }
162
163 pub fn is_empty(&self) -> bool {
164 self.segs.is_empty()
165 }
166
167 /// This path in another frame.
168 ///
169 /// Every other transform in this crate is applied at fill time, so a path is written once and
170 /// drawn wherever it is wanted, and nothing is baked. This bakes one in, for the caller that must
171 /// hand its result to something which applies a transform of its own and takes only a path. A
172 /// glyph outline is the case it exists for: it arrives in the font's frame, at a size, and the
173 /// painter then shears and places it.
174 ///
175 /// Mapping the control points is the whole of it, and no curve is approximated: an affine map
176 /// carries a Bezier to the Bezier through its mapped control points, exactly. That is the same
177 /// fact [`Path::flatten`] leans on when it flattens under a transform rather than transforming
178 /// and then flattening.
179 pub fn transform(&self, t: &Transform) -> Outcome<Self> {
180 let mut pb = PathBuilder::new();
181 for seg in &self.segs {
182 match *seg {
183 Seg::MoveTo(p) => pb.move_to(t.apply(p)),
184 Seg::LineTo(p) => pb.line_to(t.apply(p)),
185 Seg::QuadTo(c, p) => pb.quad_to(t.apply(c), t.apply(p)),
186 Seg::CubicTo(c0, c1, p) => pb.cubic_to(t.apply(c0), t.apply(c1), t.apply(p)),
187 Seg::Close => pb.close(),
188 }
189 }
190 pb.finish()
191 }
192
193 /// An axis-aligned rectangle, as a closed path.
194 pub fn rect(b: Bounds) -> Outcome<Self> {
195 let mut pb = PathBuilder::new();
196 pb.move_to(Pt::new(b.x0, b.y0));
197 pb.line_to(Pt::new(b.x1, b.y0));
198 pb.line_to(Pt::new(b.x1, b.y1));
199 pb.line_to(Pt::new(b.x0, b.y1));
200 pb.close();
201 pb.finish()
202 }
203
204 /// A circle centred at `(cx, cy)` with radius `r`, as a closed path.
205 ///
206 /// A circle is drawn as four cubic segments, one per quadrant, which is the standard bézier
207 /// approximation and is accurate to about one part in a thousand of the radius -- indistinguishable
208 /// from a true circle at any size a screen shows. See [`Path::ellipse`], of which this is the case
209 /// with equal radii.
210 pub fn circle(cx: f32, cy: f32, r: f32) -> Outcome<Self> {
211 Self::ellipse(cx, cy, r, r)
212 }
213
214 /// An axis-aligned ellipse centred at `(cx, cy)` with radii `rx` and `ry`, as a closed path.
215 ///
216 /// Each quadrant is one cubic bézier whose control points sit `k` of the way along the tangent,
217 /// where `k` is the magic constant `4/3 * (sqrt(2) - 1)` that makes a bézier hug a quarter circle.
218 /// The contour runs clockwise from the rightmost point, which fills solid under either fill rule.
219 pub fn ellipse(cx: f32, cy: f32, rx: f32, ry: f32) -> Outcome<Self> {
220 let (kx, ky) = (rx * KAPPA, ry * KAPPA);
221 let mut pb = PathBuilder::new();
222 // Rightmost point, then clockwise: down to the bottom, left to the leftmost, up to the top.
223 pb.move_to(Pt::new(cx + rx, cy));
224 pb.cubic_to(Pt::new(cx + rx, cy + ky), Pt::new(cx + kx, cy + ry), Pt::new(cx, cy + ry));
225 pb.cubic_to(Pt::new(cx - kx, cy + ry), Pt::new(cx - rx, cy + ky), Pt::new(cx - rx, cy));
226 pb.cubic_to(Pt::new(cx - rx, cy - ky), Pt::new(cx - kx, cy - ry), Pt::new(cx, cy - ry));
227 pb.cubic_to(Pt::new(cx + kx, cy - ry), Pt::new(cx + rx, cy - ky), Pt::new(cx + rx, cy));
228 pb.close();
229 pb.finish()
230 }
231
232 /// An axis-aligned rectangle with rounded corners, as a closed path.
233 ///
234 /// The radius is clamped to half the shorter side, so a radius larger than the box gives the
235 /// stadium or the circle that box inscribes rather than a shape turned inside out. A radius of
236 /// zero, or less, is a square corner and returns exactly [`Path::rect`], so a caller that rounds
237 /// nothing draws precisely what it drew before rounding existed.
238 ///
239 /// Each corner is one cubic bézier, the same quarter-arc approximation [`Path::ellipse`] uses, and
240 /// the contour runs clockwise from the top-left corner's end, matching [`Path::rect`] so the two
241 /// fill identically under either fill rule.
242 pub fn round_rect(b: Bounds, r: f32) -> Outcome<Self> {
243 if !r.is_finite() {
244 return Err(err!(
245 "A corner radius must be finite, but {} was given.", r; Invalid, Input));
246 }
247 // A square corner is the rectangle, and is the rectangle's own path: identical, not merely
248 // equivalent.
249 if r <= 0.0 {
250 return Self::rect(b);
251 }
252 // A corner cannot eat more than half the side it turns, or the two corners of one side would
253 // cross and the outline would fold through itself.
254 let r = r.min(b.width() * 0.5).min(b.height() * 0.5);
255 if r <= 0.0 {
256 return Self::rect(b);
257 }
258 let k = r * KAPPA;
259 let mut pb = PathBuilder::new();
260 // Clockwise, in a frame whose y falls: along the top, then each corner in turn.
261 pb.move_to(Pt::new(b.x0 + r, b.y0));
262 pb.line_to(Pt::new(b.x1 - r, b.y0));
263 pb.cubic_to(
264 Pt::new(b.x1 - r + k, b.y0),
265 Pt::new(b.x1, b.y0 + r - k),
266 Pt::new(b.x1, b.y0 + r),
267 );
268 pb.line_to(Pt::new(b.x1, b.y1 - r));
269 pb.cubic_to(
270 Pt::new(b.x1, b.y1 - r + k),
271 Pt::new(b.x1 - r + k, b.y1),
272 Pt::new(b.x1 - r, b.y1),
273 );
274 pb.line_to(Pt::new(b.x0 + r, b.y1));
275 pb.cubic_to(
276 Pt::new(b.x0 + r - k, b.y1),
277 Pt::new(b.x0, b.y1 - r + k),
278 Pt::new(b.x0, b.y1 - r),
279 );
280 pb.line_to(Pt::new(b.x0, b.y0 + r));
281 pb.cubic_to(
282 Pt::new(b.x0, b.y0 + r - k),
283 Pt::new(b.x0 + r - k, b.y0),
284 Pt::new(b.x0 + r, b.y0),
285 );
286 pb.close();
287 pb.finish()
288 }
289
290 /// The bounding box of the path's points under a transform.
291 ///
292 /// Control points are included, so the box is conservative: it can be larger than the curve,
293 /// never smaller, which is what a caller sizing a buffer needs.
294 pub fn bounds(&self, t: &Transform) -> Option<Bounds> {
295 let mut out: Option<Bounds> = None;
296 let mut grow = |p: Pt| {
297 let p = t.apply(p);
298 out = Some(match out {
299 None => Bounds { x0: p.x, y0: p.y, x1: p.x, y1: p.y },
300 Some(b) => Bounds {
301 x0: b.x0.min(p.x),
302 y0: b.y0.min(p.y),
303 x1: b.x1.max(p.x),
304 y1: b.y1.max(p.y),
305 },
306 });
307 };
308 for seg in &self.segs {
309 match *seg {
310 Seg::MoveTo(p) => grow(p),
311 Seg::LineTo(p) => grow(p),
312 Seg::QuadTo(c, p) => { grow(c); grow(p); },
313 Seg::CubicTo(c0, c1, p) => { grow(c0); grow(c1); grow(p); },
314 Seg::Close => (),
315 }
316 }
317 out
318 }
319
320 /// Flattens the path into closed polylines, one per contour, under a transform.
321 ///
322 /// Every contour comes back closed, whether or not the path said [`Seg::Close`], because an
323 /// unclosed contour has no interior and the rasteriser fills interiors. The tolerance is in
324 /// pixels, and is divided by the transform's scale so that a shape enlarged tenfold is
325 /// flattened ten times more finely rather than turning into a polygon.
326 pub fn flatten(&self, t: &Transform, tol: f32) -> Vec<Vec<Pt>> {
327 let scale = t.scale_factor().max(f32::EPSILON);
328 let tol = (tol / scale).max(f32::EPSILON);
329 let mut out: Vec<Vec<Pt>> = Vec::new();
330 let mut cur: Vec<Pt> = Vec::new();
331 let mut pos = Pt::default();
332 let mut start = Pt::default();
333
334 for seg in &self.segs {
335 match *seg {
336 Seg::MoveTo(p) => {
337 if cur.len() > 1 {
338 out.push(std::mem::take(&mut cur));
339 } else {
340 cur.clear();
341 }
342 cur.push(t.apply(p));
343 pos = p;
344 start = p;
345 },
346 Seg::LineTo(p) => {
347 cur.push(t.apply(p));
348 pos = p;
349 },
350 Seg::QuadTo(c, p) => {
351 flatten_quad(&mut cur, t, tol, pos, c, p);
352 pos = p;
353 },
354 Seg::CubicTo(c0, c1, p) => {
355 flatten_cubic(&mut cur, t, tol, pos, c0, c1, p);
356 pos = p;
357 },
358 Seg::Close => {
359 if cur.len() > 1 {
360 out.push(std::mem::take(&mut cur));
361 } else {
362 cur.clear();
363 }
364 pos = start;
365 },
366 }
367 }
368 if cur.len() > 1 {
369 out.push(cur);
370 }
371 out
372 }
373
374 /// Flattens the path into polylines, one per contour, keeping which contours were closed.
375 ///
376 /// This is what a stroker wants, where [`Path::flatten`] is what a filler wants. The two differ
377 /// in what they throw away. A filler closes every contour and drops any that is a single point,
378 /// since neither an open contour nor a point has an interior to fill. A stroker must keep both:
379 /// an open contour takes caps, and a lone point takes a round cap and becomes a dot.
380 pub fn flatten_contours(&self, t: &Transform, tol: f32) -> Vec<Polyline> {
381 let scale = t.scale_factor().max(f32::EPSILON);
382 let tol = (tol / scale).max(f32::EPSILON);
383 let mut out: Vec<Polyline> = Vec::new();
384 let mut cur: Vec<Pt> = Vec::new();
385 let mut pos = Pt::default();
386 let mut start = Pt::default();
387
388 // A contour is worth keeping if it has a segment to stroke, or if it was closed on a single
389 // point, which is how a path asks for a dot. A bare move_to with nothing after it is not.
390 fn flush(cur: &mut Vec<Pt>, closed: bool, out: &mut Vec<Polyline>) {
391 if cur.len() > 1 || (closed && !cur.is_empty()) {
392 out.push(Polyline { pts: std::mem::take(cur), closed });
393 } else {
394 cur.clear();
395 }
396 }
397
398 for seg in &self.segs {
399 match *seg {
400 Seg::MoveTo(p) => {
401 flush(&mut cur, false, &mut out);
402 cur.push(t.apply(p));
403 pos = p;
404 start = p;
405 },
406 Seg::LineTo(p) => {
407 cur.push(t.apply(p));
408 pos = p;
409 },
410 Seg::QuadTo(c, p) => {
411 flatten_quad(&mut cur, t, tol, pos, c, p);
412 pos = p;
413 },
414 Seg::CubicTo(c0, c1, p) => {
415 flatten_cubic(&mut cur, t, tol, pos, c0, c1, p);
416 pos = p;
417 },
418 Seg::Close => {
419 flush(&mut cur, true, &mut out);
420 pos = start;
421 },
422 }
423 }
424 flush(&mut cur, false, &mut out);
425 out
426 }
427
428 /// Reorders this path's contours so that filling it non-zero paints what filling it even-odd would.
429 ///
430 /// The engine's fill operators are non-zero throughout, so a path an SVG marks
431 /// `fill-rule="evenodd"` must have its geometry adjusted rather than its rule carried downstream.
432 /// For properly nested contours -- a ring inside a ring inside a ring, none crossing another --
433 /// even-odd paints a point iff it lies inside an odd number of contours, and non-zero does the same
434 /// once each contour's winding alternates with its nesting depth: the outermost wound one way, its
435 /// holes the other, an island inside a hole back the first way. This gives every contour the winding
436 /// its depth wants, reversing the ones that disagree. A self-crossing contour -- which a glyph or an
437 /// icon outline does not carry -- is left as it is, since its own two rules already differ.
438 pub fn even_odd_as_non_zero(&self) -> Outcome<Self> {
439 let contours = self.contours();
440 if contours.len() < 2 {
441 // One contour (or none) fills the same either way, so nothing needs reordering.
442 return Ok(self.clone());
443 }
444
445 // A flattened polygon per contour, for the area and the containment tests. The order matches
446 // `contours`, so a polygon and its segment list share an index.
447 let polys: Vec<Vec<Pt>> = contours
448 .iter()
449 .map(|segs| flatten_segs(segs))
450 .collect();
451
452 let mut pb = PathBuilder::new();
453 for (i, segs) in contours.iter().enumerate() {
454 // The nesting depth is how many of the other contours contain this one. A point taken at a
455 // boundary vertex, nudged a hair towards the contour's own centroid, reflects where the
456 // contour actually lies -- unlike the bare centroid, which for a ring can fall in its hole and
457 // so inside a smaller sibling. For non-crossing contours, one such point decides containment.
458 let mut depth = 0usize;
459 if let Some(pt) = probe_point(&polys[i]) {
460 for (j, other) in polys.iter().enumerate() {
461 if j != i && point_in_polygon(pt, other) {
462 depth += 1;
463 }
464 }
465 }
466 // Even depth wants a positive winding, odd depth a negative one; a contour whose signed area
467 // already has that sign is emitted as read, one that disagrees is emitted reversed.
468 let want_positive = depth % 2 == 0;
469 let is_positive = signed_area(&polys[i]) >= 0.0;
470 if want_positive == is_positive {
471 replay(&mut pb, segs);
472 } else {
473 replay(&mut pb, &reverse_contour(segs));
474 }
475 }
476 pb.finish()
477 }
478
479 /// Splits the path into its contours, each a segment list beginning at a [`Seg::MoveTo`] and carrying
480 /// any trailing [`Seg::Close`]. A stray segment before the first move starts a contour of its own
481 /// rather than being lost.
482 fn contours(&self) -> Vec<Vec<Seg>> {
483 let mut out: Vec<Vec<Seg>> = Vec::new();
484 let mut cur: Vec<Seg> = Vec::new();
485 for seg in &self.segs {
486 match *seg {
487 Seg::MoveTo(_) => {
488 if !cur.is_empty() {
489 out.push(std::mem::take(&mut cur));
490 }
491 cur.push(*seg);
492 },
493 Seg::Close => {
494 cur.push(*seg);
495 out.push(std::mem::take(&mut cur));
496 },
497 _ => cur.push(*seg),
498 }
499 }
500 if !cur.is_empty() {
501 out.push(cur);
502 }
503 out
504 }
505}
506
507/// Replays a contour's segments into a builder, so several contours become one path again.
508fn replay(pb: &mut PathBuilder, segs: &[Seg]) {
509 for seg in segs {
510 match *seg {
511 Seg::MoveTo(p) => pb.move_to(p),
512 Seg::LineTo(p) => pb.line_to(p),
513 Seg::QuadTo(c, p) => pb.quad_to(c, p),
514 Seg::CubicTo(c0, c1, p) => pb.cubic_to(c0, c1, p),
515 Seg::Close => pb.close(),
516 }
517 }
518}
519
520/// Reverses one contour, so a clockwise ring becomes anticlockwise and the reverse.
521///
522/// The vertices are walked backwards from the last endpoint to the first, and each segment's controls
523/// come with it -- a cubic's two controls swap, a quadratic's one stays -- so the traced curve is
524/// identical and only its direction is turned. The contour keeps its closedness: a closed ring reverses
525/// to a closed ring.
526fn reverse_contour(segs: &[Seg]) -> Vec<Seg> {
527 // The endpoint of each segment, the first being the move's own point, plus whether the contour closed.
528 let mut pts: Vec<Pt> = Vec::new();
529 let mut kinds: Vec<Seg> = Vec::new(); // one per edge, its controls only; endpoints read from `pts`
530 let mut closed = false;
531 for seg in segs {
532 match *seg {
533 Seg::MoveTo(p) => pts.push(p),
534 Seg::LineTo(p) => { kinds.push(Seg::LineTo(p)); pts.push(p); },
535 Seg::QuadTo(c, p) => { kinds.push(Seg::QuadTo(c, p)); pts.push(p); },
536 Seg::CubicTo(c0, c1, p) => { kinds.push(Seg::CubicTo(c0, c1, p)); pts.push(p); },
537 Seg::Close => closed = true,
538 }
539 }
540 if pts.is_empty() {
541 return segs.to_vec();
542 }
543 let mut out: Vec<Seg> = Vec::new();
544 out.push(Seg::MoveTo(*pts.last().unwrap_or(&Pt::default())));
545 // Edge k joins pts[k] to pts[k+1]; reversed, it joins pts[k+1] back to pts[k].
546 for k in (0..kinds.len()).rev() {
547 let to = pts[k];
548 match kinds[k] {
549 Seg::LineTo(_) => out.push(Seg::LineTo(to)),
550 Seg::QuadTo(c, _) => out.push(Seg::QuadTo(c, to)),
551 Seg::CubicTo(c0, c1, _) => out.push(Seg::CubicTo(c1, c0, to)),
552 _ => out.push(Seg::LineTo(to)),
553 }
554 }
555 if closed {
556 out.push(Seg::Close);
557 }
558 out
559}
560
561/// Flattens one contour's segments to a polygon, at a tolerance fine enough for the area and containment
562/// tests, in the contour's own frame.
563fn flatten_segs(segs: &[Seg]) -> Vec<Pt> {
564 let mut pb = PathBuilder::new();
565 replay(&mut pb, segs);
566 match pb.finish() {
567 Ok(p) => p.flatten(&Transform::IDENTITY, TOLERANCE)
568 .into_iter()
569 .next()
570 .unwrap_or_default(),
571 Err(_) => Vec::new(),
572 }
573}
574
575/// The signed area of a closed polygon by the shoelace formula; positive one way round, negative the
576/// other. Only the sign is read, to tell a contour's winding.
577fn signed_area(poly: &[Pt]) -> f32 {
578 let n = poly.len();
579 if n < 3 {
580 return 0.0;
581 }
582 let mut a = 0.0;
583 for i in 0..n {
584 let p = poly[i];
585 let q = poly[(i + 1) % n];
586 a += p.x * q.y - q.x * p.y;
587 }
588 a * 0.5
589}
590
591/// A point that lies where the contour lies, for the containment test: the first vertex pulled a small
592/// way towards the centroid, so it is just inside the boundary rather than out at the middle. `None` for
593/// a degenerate polygon.
594fn probe_point(poly: &[Pt]) -> Option<Pt> {
595 let n = poly.len();
596 if n < 3 {
597 return None;
598 }
599 let mut cx = 0.0;
600 let mut cy = 0.0;
601 for p in poly {
602 cx += p.x;
603 cy += p.y;
604 }
605 let c = Pt::new(cx / n as f32, cy / n as f32);
606 // A hair towards the centroid keeps the point close to the boundary vertex, which is what tells this
607 // contour's extent apart from a smaller sibling that shares its middle.
608 let v = poly[0];
609 Some(Pt::new(v.x + (c.x - v.x) * 0.02, v.y + (c.y - v.y) * 0.02))
610}
611
612/// Is a point inside a polygon, by the even-odd ray-crossing count?
613fn point_in_polygon(pt: Pt, poly: &[Pt]) -> bool {
614 let n = poly.len();
615 if n < 3 {
616 return false;
617 }
618 let mut inside = false;
619 let mut j = n - 1;
620 for i in 0..n {
621 let a = poly[i];
622 let b = poly[j];
623 if (a.y > pt.y) != (b.y > pt.y) {
624 let t = (pt.y - a.y) / (b.y - a.y);
625 let x = a.x + t * (b.x - a.x);
626 if pt.x < x {
627 inside = !inside;
628 }
629 }
630 j = i;
631 }
632 inside
633}
634
635/// Flattens a quadratic Bezier, appending the points after the first.
636///
637/// A straight line drawn between the ends of a quadratic strays from it by at most an eighth of the
638/// length of the second difference of its control points, and the error falls with the square of
639/// the number of steps, which is what fixes the step count.
640fn flatten_quad(out: &mut Vec<Pt>, t: &Transform, tol: f32, p0: Pt, c: Pt, p1: Pt) {
641 let dx = p0.x - 2.0 * c.x + p1.x;
642 let dy = p0.y - 2.0 * c.y + p1.y;
643 let dev = (dx * dx + dy * dy).sqrt();
644 let n = steps((dev / (8.0 * tol)).sqrt());
645 for i in 1..=n {
646 let s = (i as f32) / (n as f32);
647 let r = 1.0 - s;
648 let p = Pt::new(
649 r * r * p0.x + 2.0 * r * s * c.x + s * s * p1.x,
650 r * r * p0.y + 2.0 * r * s * c.y + s * s * p1.y,
651 );
652 out.push(t.apply(p));
653 }
654}
655
656/// Flattens a cubic Bezier, appending the points after the first.
657fn flatten_cubic(out: &mut Vec<Pt>, t: &Transform, tol: f32, p0: Pt, c0: Pt, c1: Pt, p1: Pt) {
658 let d0x = p0.x - 2.0 * c0.x + c1.x;
659 let d0y = p0.y - 2.0 * c0.y + c1.y;
660 let d1x = c0.x - 2.0 * c1.x + p1.x;
661 let d1y = c0.y - 2.0 * c1.y + p1.y;
662 let dev = (d0x * d0x + d0y * d0y).sqrt().max((d1x * d1x + d1y * d1y).sqrt());
663 let n = steps((3.0 * dev / (4.0 * tol)).sqrt());
664 for i in 1..=n {
665 let s = (i as f32) / (n as f32);
666 let r = 1.0 - s;
667 let (rr, ss) = (r * r, s * s);
668 let p = Pt::new(
669 rr * r * p0.x + 3.0 * rr * s * c0.x + 3.0 * r * ss * c1.x + ss * s * p1.x,
670 rr * r * p0.y + 3.0 * rr * s * c0.y + 3.0 * r * ss * c1.y + ss * s * p1.y,
671 );
672 out.push(t.apply(p));
673 }
674}
675
676/// Turns an ideal step count into a usable one: at least one, never absurd, never a NaN.
677fn steps(n: f32) -> usize {
678 if !n.is_finite() {
679 return MAX_STEPS;
680 }
681 (n.ceil().max(1.0) as usize).min(MAX_STEPS)
682}
683
684/// Builds a [`Path`] one step at a time.
685///
686/// The builder refuses a path that is not well formed rather than letting the rasteriser meet it:
687/// a line before any move, or a point that is not finite.
688#[derive(Clone, Debug, Default)]
689pub struct PathBuilder {
690 segs: Vec<Seg>,
691 open: bool,
692 bad: Option<String>,
693}
694
695impl PathBuilder {
696
697 pub fn new() -> Self {
698 Self::default()
699 }
700
701 /// Records the first fault met, so that [`PathBuilder::finish`] can report it. Nothing panics
702 /// and nothing is silently dropped.
703 fn fault(&mut self, msg: String) {
704 if self.bad.is_none() {
705 self.bad = Some(msg);
706 }
707 }
708
709 /// Checks a point, recording a fault if it is not finite.
710 fn check(&mut self, p: Pt, what: &str) -> bool {
711 if p.is_finite() {
712 return true;
713 }
714 self.fault(fmt!("The {} point ({}, {}) is not finite.", what, p.x, p.y));
715 false
716 }
717
718 pub fn move_to(&mut self, p: Pt) {
719 if self.check(p, "move_to") {
720 self.segs.push(Seg::MoveTo(p));
721 self.open = true;
722 }
723 }
724
725 pub fn line_to(&mut self, p: Pt) {
726 if !self.open {
727 self.fault(fmt!("A line_to at ({}, {}) precedes any move_to.", p.x, p.y));
728 return;
729 }
730 if self.check(p, "line_to") {
731 self.segs.push(Seg::LineTo(p));
732 }
733 }
734
735 pub fn quad_to(&mut self, c: Pt, p: Pt) {
736 if !self.open {
737 self.fault(fmt!("A quad_to at ({}, {}) precedes any move_to.", p.x, p.y));
738 return;
739 }
740 if self.check(c, "quad_to control") && self.check(p, "quad_to end") {
741 self.segs.push(Seg::QuadTo(c, p));
742 }
743 }
744
745 pub fn cubic_to(&mut self, c0: Pt, c1: Pt, p: Pt) {
746 if !self.open {
747 self.fault(fmt!("A cubic_to at ({}, {}) precedes any move_to.", p.x, p.y));
748 return;
749 }
750 if self.check(c0, "cubic_to first control")
751 && self.check(c1, "cubic_to second control")
752 && self.check(p, "cubic_to end")
753 {
754 self.segs.push(Seg::CubicTo(c0, c1, p));
755 }
756 }
757
758 pub fn close(&mut self) {
759 if self.open {
760 self.segs.push(Seg::Close);
761 self.open = false;
762 }
763 }
764
765 /// Finishes the path, or reports the first fault met while building it.
766 pub fn finish(self) -> Outcome<Path> {
767 match self.bad {
768 Some(msg) => Err(err!("{}", msg; Invalid, Input)),
769 None => Ok(Path { segs: self.segs }),
770 }
771 }
772}
773
774#[cfg(test)]
775mod tests {
776 use super::*;
777
778 #[test]
779 fn test_a_baked_transform_matches_one_applied_at_fill_20() -> Outcome<()> {
780 // The two routes to the same picture must put the geometry in the same place, or a glyph
781 // would land somewhere other than where filling the same path under the same transform would.
782 //
783 // The comparison is the bounds and not the flattened points: flattening is adaptive, so a
784 // path already scaled up is cut into more pieces than the same path cut before scaling, and
785 // the two polylines legitimately differ in length while tracing the same curve. Bounds come
786 // off the control points, which the transform maps exactly.
787 let p = res!(Path::round_rect(Bounds::new(1.0, 2.0, 9.0, 7.0), 1.5));
788 let t = Transform::translate(3.0, -4.0).then(&Transform::scale(2.0, -1.5));
789 let baked = res!(p.transform(&t));
790 let a = match baked.bounds(&Transform::IDENTITY) {
791 Some(b) => b,
792 None => return Err(err!("The baked path has no bounds."; Test)),
793 };
794 let b = match p.bounds(&t) {
795 Some(b) => b,
796 None => return Err(err!("The path has no bounds under the transform."; Test)),
797 };
798 for (got, want, side) in [
799 (a.x0, b.x0, "x0"), (a.y0, b.y0, "y0"), (a.x1, b.x1, "x1"), (a.y1, b.y1, "y1"),
800 ] {
801 assert!((got - want).abs() < 1e-4, "{}: baked {}, applied at fill {}", side, got, want);
802 }
803 Ok(())
804 }
805
806 #[test]
807 fn test_baking_keeps_the_curves_curves_21() -> Outcome<()> {
808 // An affine map carries a Bezier to a Bezier, so nothing is flattened on the way through: the
809 // segments that go in are the segments that come out, kind for kind.
810 let p = res!(Path::circle(0.0, 0.0, 4.0));
811 let baked = res!(p.transform(&Transform::scale(2.0, 3.0)));
812 assert_eq!(p.segs().len(), baked.segs().len());
813 for (a, b) in p.segs().iter().zip(baked.segs().iter()) {
814 assert_eq!(std::mem::discriminant(a), std::mem::discriminant(b));
815 }
816 Ok(())
817 }
818
819 #[test]
820 fn test_rect_has_four_corners_00() -> Outcome<()> {
821 let p = res!(Path::rect(Bounds::new(0.0, 0.0, 10.0, 5.0)));
822 let cs = p.flatten(&Transform::IDENTITY, TOLERANCE);
823 assert_eq!(cs.len(), 1);
824 assert_eq!(cs[0].len(), 4);
825 Ok(())
826 }
827
828 #[test]
829 fn test_a_circle_stays_on_its_radius_08() -> Outcome<()> {
830 // Every flattened point of a circle must sit close to the radius from the centre: the bézier
831 // quadrants approximate the arc to about a part in a thousand, so a tolerance of one percent of
832 // the radius is generous and still catches a control point put in the wrong place.
833 let (cx, cy, r) = (40.0, 30.0, 20.0);
834 let p = res!(Path::circle(cx, cy, r));
835 let cs = p.flatten(&Transform::IDENTITY, TOLERANCE);
836 assert_eq!(cs.len(), 1, "a circle is one contour");
837 for pt in &cs[0] {
838 let d = ((pt.x - cx).powi(2) + (pt.y - cy).powi(2)).sqrt();
839 assert!((d - r).abs() < r * 0.01, "a point at distance {} is off the radius {}", d, r);
840 }
841 // And its bounding box is the square the radius inscribes.
842 let b = match p.bounds(&Transform::IDENTITY) {
843 Some(b) => b,
844 None => return Err(err!("The circle has no bounds."; Test)),
845 };
846 assert!((b.x0 - (cx - r)).abs() < 0.01 && (b.x1 - (cx + r)).abs() < 0.01, "width spans 2r");
847 assert!((b.y0 - (cy - r)).abs() < 0.01 && (b.y1 - (cy + r)).abs() < 0.01, "height spans 2r");
848 Ok(())
849 }
850
851 #[test]
852 fn test_a_round_rect_of_no_radius_is_the_rectangle_09() -> Outcome<()> {
853 // Not "looks the same": IS the same path. A caller that asks for no rounding must be able to
854 // rely on getting back exactly what it would have got from Path::rect.
855 let b = Bounds::new(3.0, 7.0, 40.0, 25.0);
856 assert_eq!(res!(Path::round_rect(b, 0.0)), res!(Path::rect(b)));
857 assert_eq!(res!(Path::round_rect(b, -5.0)), res!(Path::rect(b)));
858 Ok(())
859 }
860
861 #[test]
862 fn test_a_round_rect_keeps_its_box_and_rounds_its_corners_10() -> Outcome<()> {
863 let (b, r) = (Bounds::new(0.0, 0.0, 60.0, 40.0), 8.0);
864 let p = res!(Path::round_rect(b, r));
865 // The shape still occupies exactly the box it was given: rounding takes corners away, it does
866 // not move edges.
867 let bb = match p.bounds(&Transform::IDENTITY) {
868 Some(bb) => bb,
869 None => return Err(err!("The rounded rectangle has no bounds."; Test)),
870 };
871 assert!((bb.x0 - b.x0).abs() < 0.01 && (bb.x1 - b.x1).abs() < 0.01, "the width is the box's");
872 assert!((bb.y0 - b.y0).abs() < 0.01 && (bb.y1 - b.y1).abs() < 0.01, "the height is the box's");
873
874 // And the corner itself is gone: no point of the outline lies in the square the radius cuts off
875 // at the top-left, beyond the arc's own centre distance.
876 let cs = p.flatten(&Transform::IDENTITY, TOLERANCE);
877 assert_eq!(cs.len(), 1, "a rounded rectangle is one contour");
878 let (cx, cy) = (b.x0 + r, b.y0 + r); // The top-left corner's arc centre.
879 for pt in &cs[0] {
880 if pt.x < cx && pt.y < cy {
881 let d = ((pt.x - cx).powi(2) + (pt.y - cy).powi(2)).sqrt();
882 assert!(
883 (d - r).abs() < r * 0.01,
884 "the point ({}, {}) is inside the corner square at distance {} from the arc \
885 centre, which is not on the radius {}", pt.x, pt.y, d, r,
886 );
887 }
888 }
889 Ok(())
890 }
891
892 #[test]
893 fn test_a_radius_larger_than_the_box_is_clamped_11() -> Outcome<()> {
894 // A radius of half the shorter side is the most a box can take. Beyond that the corners would
895 // cross, so the radius is clamped and the shape stays inside its box.
896 let b = Bounds::new(0.0, 0.0, 40.0, 20.0);
897 let p = res!(Path::round_rect(b, 500.0));
898 let bb = match p.bounds(&Transform::IDENTITY) {
899 Some(bb) => bb,
900 None => return Err(err!("The clamped rounded rectangle has no bounds."; Test)),
901 };
902 assert!(bb.x0 >= b.x0 - 0.01 && bb.x1 <= b.x1 + 0.01, "a clamped radius stays in its box");
903 assert!(bb.y0 >= b.y0 - 0.01 && bb.y1 <= b.y1 + 0.01, "in both axes");
904 // Half the shorter side: a stadium, whose ends are semicircles of the box's half-height.
905 assert_eq!(p, res!(Path::round_rect(b, b.height() * 0.5)), "the radius clamps to half the side");
906 Ok(())
907 }
908
909 #[test]
910 fn test_line_before_move_is_rejected_01() {
911 let mut pb = PathBuilder::new();
912 pb.line_to(Pt::new(1.0, 1.0));
913 assert!(pb.finish().is_err());
914 }
915
916 #[test]
917 fn test_infinite_point_is_rejected_02() {
918 let mut pb = PathBuilder::new();
919 pb.move_to(Pt::new(f32::INFINITY, 0.0));
920 assert!(pb.finish().is_err());
921 }
922
923 #[test]
924 fn test_curve_flattens_more_finely_when_scaled_03() -> Outcome<()> {
925 let mut pb = PathBuilder::new();
926 pb.move_to(Pt::new(0.0, 0.0));
927 pb.quad_to(Pt::new(50.0, 100.0), Pt::new(100.0, 0.0));
928 pb.close();
929 let p = res!(pb.finish());
930 let small = p.flatten(&Transform::IDENTITY, TOLERANCE);
931 let big = p.flatten(&Transform::scale(10.0, 10.0), TOLERANCE);
932 assert!(
933 big[0].len() > small[0].len(),
934 "a tenfold enlargement should need more segments, found {} then {}",
935 small[0].len(), big[0].len(),
936 );
937 Ok(())
938 }
939
940 #[test]
941 fn test_unclosed_contour_still_flattens_04() -> Outcome<()> {
942 // An unclosed contour has an interior all the same; the rasteriser closes it.
943 let mut pb = PathBuilder::new();
944 pb.move_to(Pt::new(0.0, 0.0));
945 pb.line_to(Pt::new(10.0, 0.0));
946 pb.line_to(Pt::new(10.0, 10.0));
947 let p = res!(pb.finish());
948 let cs = p.flatten(&Transform::IDENTITY, TOLERANCE);
949 assert_eq!(cs.len(), 1);
950 assert_eq!(cs[0].len(), 3);
951 Ok(())
952 }
953
954 #[test]
955 fn test_flatten_contours_remembers_what_was_closed_06() -> Outcome<()> {
956 let mut pb = PathBuilder::new();
957 pb.move_to(Pt::new(0.0, 0.0));
958 pb.line_to(Pt::new(10.0, 0.0));
959 pb.line_to(Pt::new(10.0, 10.0));
960 pb.close();
961 pb.move_to(Pt::new(20.0, 0.0));
962 pb.line_to(Pt::new(30.0, 0.0));
963 let p = res!(pb.finish());
964 let cs = p.flatten_contours(&Transform::IDENTITY, TOLERANCE);
965 assert_eq!(cs.len(), 2);
966 assert!(cs[0].closed, "the first contour was closed");
967 assert_eq!(cs[0].pts.len(), 3, "and its closing point is not repeated");
968 assert!(!cs[1].closed, "the second was left open");
969 // The filler throws the distinction away, and still sees two contours.
970 assert_eq!(p.flatten(&Transform::IDENTITY, TOLERANCE).len(), 2);
971 Ok(())
972 }
973
974 #[test]
975 fn test_a_move_closed_on_itself_is_a_point_but_a_lone_move_is_nothing_07() -> Outcome<()> {
976 // A stroker needs both of these, and they differ: a path may ask for a dot, and a path may
977 // pick the pen up and put it down again without asking for anything.
978 let mut pb = PathBuilder::new();
979 pb.move_to(Pt::new(5.0, 5.0));
980 pb.close();
981 let dot = res!(pb.finish());
982 let cs = dot.flatten_contours(&Transform::IDENTITY, TOLERANCE);
983 assert_eq!(cs.len(), 1, "a move closed on itself is a contour of one point");
984 assert_eq!(cs[0].pts.len(), 1);
985 assert!(cs[0].closed);
986
987 let mut pb = PathBuilder::new();
988 pb.move_to(Pt::new(5.0, 5.0));
989 let lone = res!(pb.finish());
990 assert!(lone.flatten_contours(&Transform::IDENTITY, TOLERANCE).is_empty());
991 // The filler drops both, since a point has no interior.
992 assert!(dot.flatten(&Transform::IDENTITY, TOLERANCE).is_empty());
993 Ok(())
994 }
995
996 #[test]
997 fn test_bounds_are_conservative_05() -> Outcome<()> {
998 let mut pb = PathBuilder::new();
999 pb.move_to(Pt::new(0.0, 0.0));
1000 pb.quad_to(Pt::new(50.0, 100.0), Pt::new(100.0, 0.0));
1001 let p = res!(pb.finish());
1002 let b = match p.bounds(&Transform::IDENTITY) {
1003 Some(b) => b,
1004 None => return Err(err!("The path has points, so it must have bounds."; Bug)),
1005 };
1006 // The curve only reaches y = 50, but the control point at y = 100 is counted.
1007 assert_eq!(b.y1, 100.0);
1008 Ok(())
1009 }
1010
1011 #[test]
1012 fn test_even_odd_hole_reverses_to_a_non_zero_hole_30() -> Outcome<()> {
1013 // An outer ring and an inner ring wound the same way. Even-odd hollows the inner one; so must the
1014 // converted path fill non-zero, which means the two rings end wound against each other.
1015 let mut pb = PathBuilder::new();
1016 // Outer, anticlockwise in a y-down frame.
1017 pb.move_to(Pt::new(0.0, 0.0));
1018 pb.line_to(Pt::new(10.0, 0.0));
1019 pb.line_to(Pt::new(10.0, 10.0));
1020 pb.line_to(Pt::new(0.0, 10.0));
1021 pb.close();
1022 // Inner, the same sense as the outer.
1023 pb.move_to(Pt::new(3.0, 3.0));
1024 pb.line_to(Pt::new(7.0, 3.0));
1025 pb.line_to(Pt::new(7.0, 7.0));
1026 pb.line_to(Pt::new(3.0, 7.0));
1027 pb.close();
1028 let p = res!(pb.finish());
1029
1030 // Before: both rings wind the same way, so their signed areas share a sign.
1031 let before: Vec<f32> = p.contours().iter().map(|c| signed_area(&flatten_segs(c))).collect();
1032 assert_eq!(before.len(), 2);
1033 assert!(before[0].signum() == before[1].signum(),
1034 "the source rings wind the same way, areas {before:?}");
1035
1036 let conv = res!(p.even_odd_as_non_zero());
1037 let after: Vec<f32> = conv.contours().iter().map(|c| signed_area(&flatten_segs(c))).collect();
1038 assert_eq!(after.len(), 2);
1039 // After: the inner ring has been reversed, so the two now wind against each other and non-zero
1040 // leaves the middle empty exactly as even-odd would.
1041 assert!(after[0].signum() != after[1].signum(),
1042 "the converted rings must wind against each other, areas {after:?}");
1043 Ok(())
1044 }
1045}