1use crate::geom::{Matrix, Point};
5
6#[derive(Debug, Clone, PartialEq)]
8pub struct Dash {
9 pub pattern: Vec<f64>,
11 pub phase: f64,
13}
14
15impl Dash {
16 pub fn solid() -> Self {
18 Self {
19 pattern: Vec::new(),
20 phase: 0.0,
21 }
22 }
23
24 pub fn is_solid(&self) -> bool {
26 self.pattern.is_empty() || self.pattern.iter().all(|length| *length <= 0.0)
27 }
28}
29
30#[derive(Debug, Clone, Copy, PartialEq, Eq)]
32pub enum Cap {
33 Butt,
35 Round,
37 Square,
39}
40
41#[derive(Debug, Clone, Copy, PartialEq, Eq)]
43pub enum Join {
44 Miter,
46 Round,
48 Bevel,
50}
51
52#[derive(Debug, Clone, Copy, PartialEq)]
54pub enum Segment {
55 Line(Point),
57 Cubic {
59 c1: Point,
61 c2: Point,
63 to: Point,
65 },
66}
67
68#[derive(Debug, Clone, PartialEq)]
70pub struct Subpath {
71 pub start: Point,
73 pub segments: Vec<Segment>,
75 pub closed: bool,
77}
78
79#[derive(Debug, Clone, Default, PartialEq)]
81pub struct Path {
82 pub subpaths: Vec<Subpath>,
84}
85
86impl Path {
87 pub fn new() -> Self {
89 Self::default()
90 }
91
92 pub fn is_empty(&self) -> bool {
94 self.subpaths
95 .iter()
96 .all(|subpath| subpath.segments.is_empty())
97 }
98
99 pub fn move_to(&mut self, point: Point) {
101 self.subpaths.push(Subpath {
102 start: point,
103 segments: Vec::new(),
104 closed: false,
105 });
106 }
107
108 pub fn line_to(&mut self, point: Point) {
110 if let Some(subpath) = self.subpaths.last_mut() {
111 subpath.segments.push(Segment::Line(point));
112 } else {
113 self.move_to(point);
114 }
115 }
116
117 pub fn curve_to(&mut self, c1: Point, c2: Point, to: Point) {
119 if let Some(subpath) = self.subpaths.last_mut() {
120 subpath.segments.push(Segment::Cubic { c1, c2, to });
121 } else {
122 self.move_to(to);
123 }
124 }
125
126 pub fn close(&mut self) {
128 if let Some(subpath) = self.subpaths.last_mut() {
129 subpath.closed = true;
130 }
131 }
132
133 pub fn add_rect(&mut self, x: f64, y: f64, width: f64, height: f64) {
135 self.move_to(Point::new(x, y));
136 self.line_to(Point::new(x + width, y));
137 self.line_to(Point::new(x + width, y + height));
138 self.line_to(Point::new(x, y + height));
139 self.close();
140 }
141
142 pub fn flatten(&self, ctm: Matrix) -> Vec<Vec<Point>> {
148 const CURVE_STEPS: usize = 24;
149 let mut polylines = Vec::with_capacity(self.subpaths.len());
150 for subpath in &self.subpaths {
151 let mut points = vec![ctm.apply(subpath.start)];
152 let mut current = subpath.start;
153 for segment in &subpath.segments {
154 match *segment {
155 Segment::Line(to) => {
156 points.push(ctm.apply(to));
157 current = to;
158 }
159 Segment::Cubic { c1, c2, to } => {
160 for step in 1..=CURVE_STEPS {
161 let t = step as f64 / CURVE_STEPS as f64;
162 points.push(ctm.apply(cubic_at(current, c1, c2, to, t)));
163 }
164 current = to;
165 }
166 }
167 }
168 if subpath.closed && points.len() > 1 {
169 let first = points[0];
170 let last = *points.last().expect("non-empty");
171 if (first.x - last.x).abs() > f64::EPSILON
172 || (first.y - last.y).abs() > f64::EPSILON
173 {
174 points.push(first);
175 }
176 }
177 if points.len() > 1 {
178 polylines.push(points);
179 }
180 }
181 polylines
182 }
183}
184
185fn cubic_at(p0: Point, c1: Point, c2: Point, p3: Point, t: f64) -> Point {
186 let u = 1.0 - t;
187 let a = u * u * u;
188 let b = 3.0 * u * u * t;
189 let c = 3.0 * u * t * t;
190 let d = t * t * t;
191 Point::new(
192 a * p0.x + b * c1.x + c * c2.x + d * p3.x,
193 a * p0.y + b * c1.y + c * c2.y + d * p3.y,
194 )
195}
196
197pub fn dash_polyline(polyline: &[Point], dash: &Dash, ctm_scale: f64) -> Vec<Vec<Point>> {
203 if dash.is_solid() || polyline.len() < 2 {
204 return vec![polyline.to_vec()];
205 }
206 let pattern: Vec<f64> = dash
207 .pattern
208 .iter()
209 .map(|length| (length * ctm_scale).abs())
210 .filter(|length| *length > 1e-9)
211 .collect();
212 if pattern.is_empty() {
213 return vec![polyline.to_vec()];
214 }
215 let mut runs = Vec::new();
216 let mut current_run: Vec<Point> = Vec::new();
217 let mut index = 0usize;
219 let mut remaining = pattern[0];
220 let mut phase = dash.phase * ctm_scale;
221 while phase > 0.0 {
222 if phase >= remaining {
223 phase -= remaining;
224 index = (index + 1) % pattern.len();
225 remaining = pattern[index];
226 } else {
227 remaining -= phase;
228 phase = 0.0;
229 }
230 }
231 let mut on = index.is_multiple_of(2);
232 if on {
233 current_run.push(polyline[0]);
234 }
235 for window in polyline.array_windows::<2>() {
236 let mut start = window[0];
237 let end = window[1];
238 let dx = end.x - start.x;
239 let dy = end.y - start.y;
240 let length = (dx * dx + dy * dy).sqrt();
241 if length <= 1e-12 {
242 continue;
243 }
244 let unit_x = dx / length;
245 let unit_y = dy / length;
246 let mut travelled = 0.0;
247 while travelled < length {
248 let step = remaining.min(length - travelled);
249 let next = Point::new(start.x + unit_x * step, start.y + unit_y * step);
250 if on {
251 if current_run.is_empty() {
252 current_run.push(start);
253 }
254 current_run.push(next);
255 }
256 travelled += step;
257 remaining -= step;
258 if remaining <= 1e-9 {
259 if on && current_run.len() > 1 {
260 runs.push(std::mem::take(&mut current_run));
261 }
262 index = (index + 1) % pattern.len();
263 remaining = pattern[index];
264 on = index.is_multiple_of(2);
265 }
266 start = next;
267 }
268 }
269 if on && current_run.len() > 1 {
270 runs.push(current_run);
271 }
272 runs
273}
274
275pub fn stroke_outline(
280 polylines: &[Vec<Point>],
281 width: f64,
282 cap: Cap,
283 join: Join,
284 miter_limit: f64,
285) -> Vec<Vec<Point>> {
286 let half = (width / 2.0).max(0.0);
287 if half <= 0.0 {
288 return Vec::new();
289 }
290 let mut polygons = Vec::new();
291 for polyline in polylines {
292 if polyline.len() < 2 {
293 continue;
294 }
295 let last_index = polyline.len() - 2;
296 for (index, window) in polyline.array_windows::<2>().enumerate() {
297 let start = window[0];
298 let end = window[1];
299 let first = index == 0;
300 let last = index == last_index;
301 let (from, to) = if cap == Cap::Square {
304 (
305 if first {
306 extend(start, end, half)
307 } else {
308 start
309 },
310 if last { extend(end, start, half) } else { end },
311 )
312 } else {
313 (start, end)
314 };
315 let quad = segment_quad(from, to, half);
316 if quad.is_empty() {
317 continue;
318 }
319 polygons.push(oriented(quad));
320 if !first {
323 polygons.push(join_polygon(polyline, index, half, join, miter_limit));
324 }
325 if last && cap == Cap::Round {
326 polygons.push(oriented(circle(end, half)));
327 }
328 }
329 if cap == Cap::Round {
330 polygons.push(oriented(circle(polyline[0], half)));
331 }
332 }
333 polygons
334}
335
336fn join_polygon(
339 polyline: &[Point],
340 index: usize,
341 half: f64,
342 join: Join,
343 miter_limit: f64,
344) -> Vec<Point> {
345 let vertex = polyline[index];
346 let before = polyline[index - 1];
347 let after = polyline[index + 1];
348 if join == Join::Round {
349 return oriented(circle(vertex, half));
350 }
351 let (Some(incoming), Some(outgoing)) = (unit(before, vertex), unit(vertex, after)) else {
352 return oriented(circle(vertex, half));
353 };
354 let cross = incoming.0 * outgoing.1 - incoming.1 * outgoing.0;
357 let factor = if cross > 0.0 { -1.0 } else { 1.0 };
358 let back_out = offset(vertex, incoming, half * factor);
359 let forward_out = offset(vertex, outgoing, half * factor);
360 if join == Join::Bevel || cross.abs() < 1e-9 {
361 return oriented(vec![vertex, back_out, forward_out]);
362 }
363 let Some(tip) = intersect(back_out, incoming, forward_out, outgoing) else {
366 return oriented(vec![vertex, back_out, forward_out]);
367 };
368 let length = ((tip.x - vertex.x).powi(2) + (tip.y - vertex.y).powi(2)).sqrt();
369 if length > half * miter_limit.max(1.0) {
370 return oriented(vec![vertex, back_out, forward_out]);
371 }
372 oriented(vec![vertex, back_out, tip, forward_out])
373}
374
375fn offset(from: Point, direction: (f64, f64), distance: f64) -> Point {
377 Point::new(
378 from.x - direction.1 * distance,
379 from.y + direction.0 * distance,
380 )
381}
382
383fn unit(from: Point, to: Point) -> Option<(f64, f64)> {
385 let dx = to.x - from.x;
386 let dy = to.y - from.y;
387 let length = (dx * dx + dy * dy).sqrt();
388 if length <= 1e-12 {
389 return None;
390 }
391 Some((dx / length, dy / length))
392}
393
394fn intersect(p: Point, d: (f64, f64), q: Point, e: (f64, f64)) -> Option<Point> {
396 let denominator = d.0 * e.1 - d.1 * e.0;
397 if denominator.abs() < 1e-9 {
398 return None;
399 }
400 let dx = q.x - p.x;
401 let dy = q.y - p.y;
402 let t = (dx * e.1 - dy * e.0) / denominator;
403 Some(Point::new(p.x + d.0 * t, p.y + d.1 * t))
404}
405
406fn extend(from: Point, towards: Point, distance: f64) -> Point {
408 let dx = towards.x - from.x;
409 let dy = towards.y - from.y;
410 let length = (dx * dx + dy * dy).sqrt();
411 if length <= 1e-12 {
412 return from;
413 }
414 Point::new(
415 from.x - dx / length * distance,
416 from.y - dy / length * distance,
417 )
418}
419
420fn segment_quad(start: Point, end: Point, half: f64) -> Vec<Point> {
421 let dx = end.x - start.x;
422 let dy = end.y - start.y;
423 let length = (dx * dx + dy * dy).sqrt();
424 if length <= 1e-12 {
425 return Vec::new();
426 }
427 let nx = -dy / length * half;
428 let ny = dx / length * half;
429 vec![
430 Point::new(start.x + nx, start.y + ny),
431 Point::new(end.x + nx, end.y + ny),
432 Point::new(end.x - nx, end.y - ny),
433 Point::new(start.x - nx, start.y - ny),
434 ]
435}
436
437pub fn circle(center: Point, radius: f64) -> Vec<Point> {
439 const SEGMENTS: usize = 16;
440 let mut points = Vec::with_capacity(SEGMENTS);
441 for step in 0..SEGMENTS {
442 let angle = step as f64 / SEGMENTS as f64 * std::f64::consts::TAU;
443 points.push(Point::new(
444 center.x + radius * angle.cos(),
445 center.y + radius * angle.sin(),
446 ));
447 }
448 points
449}
450
451fn oriented(mut polygon: Vec<Point>) -> Vec<Point> {
454 let area = signed_area(&polygon);
455 if area < 0.0 {
456 polygon.reverse();
457 }
458 polygon
459}
460
461fn signed_area(polygon: &[Point]) -> f64 {
462 let mut sum = 0.0;
463 for index in 0..polygon.len() {
464 let current = polygon[index];
465 let next = polygon[(index + 1) % polygon.len()];
466 sum += current.x * next.y - next.x * current.y;
467 }
468 sum / 2.0
469}
470
471#[cfg(test)]
472mod tests {
473 use super::{Cap, Dash, Join, Path, dash_polyline, stroke_outline};
474 use crate::geom::{Matrix, Point};
475
476 #[test]
477 fn rectangles_flatten_to_closed_polylines() {
478 let mut path = Path::new();
479 path.add_rect(0.0, 0.0, 10.0, 20.0);
480 let polylines = path.flatten(Matrix::IDENTITY);
481 assert_eq!(polylines.len(), 1);
482 assert_eq!(polylines[0].len(), 5, "four corners plus the closing point");
483 assert_eq!(polylines[0][0], Point::new(0.0, 0.0));
484 assert_eq!(polylines[0][2], Point::new(10.0, 20.0));
485 }
486
487 #[test]
488 fn curves_are_subdivided() {
489 let mut path = Path::new();
490 path.move_to(Point::new(0.0, 0.0));
491 path.curve_to(
492 Point::new(0.0, 10.0),
493 Point::new(10.0, 10.0),
494 Point::new(10.0, 0.0),
495 );
496 let polylines = path.flatten(Matrix::IDENTITY);
497 assert_eq!(polylines[0].len(), 25);
498 assert_eq!(*polylines[0].last().expect("end"), Point::new(10.0, 0.0));
499 }
500
501 #[test]
502 fn a_solid_dash_keeps_the_polyline() {
503 let line = vec![Point::new(0.0, 0.0), Point::new(10.0, 0.0)];
504 let runs = dash_polyline(&line, &Dash::solid(), 1.0);
505 assert_eq!(runs.len(), 1);
506 assert_eq!(runs[0], line);
507 }
508
509 #[test]
510 fn a_dash_pattern_splits_the_line() {
511 let line = vec![Point::new(0.0, 0.0), Point::new(20.0, 0.0)];
512 let dash = Dash {
513 pattern: vec![5.0, 5.0],
514 phase: 0.0,
515 };
516 let runs = dash_polyline(&line, &dash, 1.0);
517 assert_eq!(runs.len(), 2);
518 assert_eq!(runs[0], vec![Point::new(0.0, 0.0), Point::new(5.0, 0.0)]);
519 assert_eq!(runs[1], vec![Point::new(10.0, 0.0), Point::new(15.0, 0.0)]);
520 }
521
522 #[test]
523 fn a_phase_offsets_the_first_run() {
524 let line = vec![Point::new(0.0, 0.0), Point::new(20.0, 0.0)];
525 let dash = Dash {
526 pattern: vec![5.0, 5.0],
527 phase: 2.0,
528 };
529 let runs = dash_polyline(&line, &dash, 1.0);
530 assert_eq!(runs[0][0], Point::new(0.0, 0.0));
531 assert_eq!(runs[0][1], Point::new(3.0, 0.0));
532 }
533
534 #[test]
535 fn strokes_become_polygons_around_the_line() {
536 let line = vec![Point::new(10.0, 10.0), Point::new(30.0, 10.0)];
537 let polygons = stroke_outline(&[line], 4.0, Cap::Butt, Join::Miter, 10.0);
538 assert!(!polygons.is_empty());
539 for polygon in &polygons {
541 assert!(super::signed_area(polygon) >= 0.0);
542 }
543 let quad = &polygons[0];
545 let min_y = quad.iter().fold(f64::MAX, |min, point| min.min(point.y));
546 let max_y = quad.iter().fold(f64::MIN, |max, point| max.max(point.y));
547 assert!((min_y - 8.0).abs() < 1e-9, "{min_y}");
548 assert!((max_y - 12.0).abs() < 1e-9, "{max_y}");
549 }
550
551 fn corner(join: Join, limit: f64) -> Vec<Vec<Point>> {
555 let path = vec![
556 Point::new(0.0, 10.0),
557 Point::new(10.0, 10.0),
558 Point::new(10.0, 20.0),
559 ];
560 stroke_outline(&[path], 4.0, Cap::Butt, join, limit)
561 }
562
563 fn painted(polygons: &[Vec<Point>], x: u32, y: u32) -> bool {
564 let mut canvas = crate::canvas::Canvas::new(24, 30, crate::canvas::Color::WHITE);
565 let mask = crate::canvas::ClipMask::all(24, 30);
566 crate::raster::fill_polygons(
567 &mut canvas,
568 &mask,
569 polygons,
570 crate::canvas::Color::BLACK,
571 false,
572 1.0,
573 crate::canvas::BlendMode::Normal,
574 );
575 canvas.pixel(x, y) == Some([0, 0, 0, 255])
576 }
577
578 #[test]
579 fn a_miter_join_fills_the_corner_and_a_bevel_cuts_it() {
580 assert!(
582 painted(&corner(Join::Miter, 10.0), 11, 8),
583 "the miter fills the corner"
584 );
585 assert!(
586 !painted(&corner(Join::Bevel, 10.0), 11, 8),
587 "the bevel cuts the corner"
588 );
589 }
590
591 #[test]
592 fn the_miter_limit_cuts_the_corner_back_to_a_bevel() {
593 assert!(
596 painted(&corner(Join::Miter, 10.0), 11, 8),
597 "limit 10 miters"
598 );
599 assert!(
600 !painted(&corner(Join::Miter, 1.2), 11, 8),
601 "limit 1.2 bevels"
602 );
603 }
604}