cranpose_ui_graphics/
vector_path.rs

1//! SVG path-data (`d` attribute) parsing and CPU fill rasterization.
2//!
3//! [`VectorPath`] parses the SVG path mini-language
4//! (`M/m L/l H/h V/v C/c S/s Q/q T/t A/a Z/z`) into subpaths flattened to
5//! polylines: curves are subdivided adaptively, arcs are converted via the
6//! W3C endpoint-to-center parameterization and sampled. Fills are rendered
7//! with an anti-aliased scanline rasterizer into a coverage mask, which the
8//! draw pipeline turns into an [`crate::ImageBitmap`] primitive — so every
9//! render backend gets vector shapes without new renderer primitives.
10//!
11//! Parse once (`VectorPath::parse`), draw per frame
12//! (`DrawScope::draw_vector_path`); the one-shot
13//! `DrawScope::draw_svg_path(d, brush)` convenience re-parses each call.
14
15use thiserror::Error;
16
17use crate::geometry::{Point, Rect};
18
19/// Maximum recursion depth for adaptive curve flattening.
20const MAX_FLATTEN_DEPTH: u32 = 12;
21/// Curve flattening tolerance in path units.
22const FLATTEN_TOLERANCE: f32 = 0.05;
23/// Arc sampling: maximum angle step per segment.
24const ARC_MAX_ANGLE_STEP: f32 = std::f32::consts::PI / 16.0;
25/// Anti-aliasing sub-scanlines per pixel row.
26const SUBSAMPLES: usize = 4;
27
28/// Errors produced while parsing SVG path data.
29#[derive(Debug, Clone, PartialEq, Eq, Error)]
30pub enum SvgPathError {
31    #[error("unexpected byte {byte:?} at offset {offset}")]
32    UnexpectedByte { byte: char, offset: usize },
33    #[error("expected a number at offset {offset}")]
34    ExpectedNumber { offset: usize },
35    #[error("expected an arc flag (0 or 1) at offset {offset}")]
36    ExpectedFlag { offset: usize },
37    #[error("path data must start with a moveto (M/m) command")]
38    MissingMoveTo,
39}
40
41/// Fill rule for [`VectorPath`] rasterization.
42#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
43pub enum PathFillRule {
44    /// Fill where the winding number is non-zero (SVG default).
45    #[default]
46    NonZero,
47    /// Fill where a ray crosses an odd number of edges.
48    EvenOdd,
49}
50
51/// A parsed SVG path: subpaths flattened to polylines, ready to fill.
52#[derive(Debug, Clone)]
53pub struct VectorPath {
54    subpaths: Vec<Vec<Point>>,
55    fill_rule: PathFillRule,
56    bounds: Rect,
57}
58
59impl VectorPath {
60    /// Parses SVG path data (the `d` attribute syntax).
61    pub fn parse(d: &str) -> Result<Self, SvgPathError> {
62        let subpaths = parse_path_data(d)?;
63        Ok(Self::from_subpaths(subpaths, PathFillRule::NonZero))
64    }
65
66    /// Parses SVG path data with an explicit fill rule.
67    pub fn parse_with_fill_rule(d: &str, fill_rule: PathFillRule) -> Result<Self, SvgPathError> {
68        let subpaths = parse_path_data(d)?;
69        Ok(Self::from_subpaths(subpaths, fill_rule))
70    }
71
72    fn from_subpaths(subpaths: Vec<Vec<Point>>, fill_rule: PathFillRule) -> Self {
73        let mut min = Point::new(f32::INFINITY, f32::INFINITY);
74        let mut max = Point::new(f32::NEG_INFINITY, f32::NEG_INFINITY);
75        for point in subpaths.iter().flatten() {
76            min.x = min.x.min(point.x);
77            min.y = min.y.min(point.y);
78            max.x = max.x.max(point.x);
79            max.y = max.y.max(point.y);
80        }
81        let bounds = if min.x.is_finite() {
82            Rect {
83                x: min.x,
84                y: min.y,
85                width: (max.x - min.x).max(0.0),
86                height: (max.y - min.y).max(0.0),
87            }
88        } else {
89            Rect {
90                x: 0.0,
91                y: 0.0,
92                width: 0.0,
93                height: 0.0,
94            }
95        };
96        Self {
97            subpaths,
98            fill_rule,
99            bounds,
100        }
101    }
102
103    /// Returns a uniformly scaled copy (icon path data drawn at a target
104    /// size: `parse(d)?.scaled(size / view_box)`).
105    pub fn scaled(&self, factor: f32) -> Self {
106        let subpaths = self
107            .subpaths
108            .iter()
109            .map(|subpath| {
110                subpath
111                    .iter()
112                    .map(|point| Point::new(point.x * factor, point.y * factor))
113                    .collect()
114            })
115            .collect();
116        Self::from_subpaths(subpaths, self.fill_rule)
117    }
118
119    /// A copy of this path translated by `(dx, dy)`.
120    pub fn translated(&self, dx: f32, dy: f32) -> Self {
121        let subpaths = self
122            .subpaths
123            .iter()
124            .map(|subpath| {
125                subpath
126                    .iter()
127                    .map(|point| Point::new(point.x + dx, point.y + dy))
128                    .collect()
129            })
130            .collect();
131        Self::from_subpaths(subpaths, self.fill_rule)
132    }
133
134    /// The fill rule used by [`coverage_mask`](Self::coverage_mask).
135    pub fn fill_rule(&self) -> PathFillRule {
136        self.fill_rule
137    }
138
139    /// Tight bounding box of the flattened path, in path units.
140    pub fn bounds(&self) -> Rect {
141        self.bounds
142    }
143
144    /// Whether the path contains no fillable geometry.
145    pub fn is_empty(&self) -> bool {
146        !self.subpaths.iter().any(|subpath| subpath.len() >= 3)
147    }
148
149    /// Flattened subpaths (each is filled as a closed polygon).
150    pub fn subpaths(&self) -> &[Vec<Point>] {
151        &self.subpaths
152    }
153
154    /// Rasterizes the fill into an anti-aliased 8-bit coverage mask of
155    /// `width x height` pixels. A path point `p` maps to the pixel-space
156    /// position `(p - origin) * scale`.
157    pub fn coverage_mask(&self, width: usize, height: usize, origin: Point, scale: f32) -> Vec<u8> {
158        let mut mask = vec![0u8; width * height];
159        if width == 0 || height == 0 || scale <= 0.0 {
160            return mask;
161        }
162
163        struct Edge {
164            top: Point,
165            bottom: Point,
166            winding: i32,
167        }
168        let mut edges = Vec::new();
169        for subpath in &self.subpaths {
170            if subpath.len() < 3 {
171                continue;
172            }
173            let map = |p: &Point| Point::new((p.x - origin.x) * scale, (p.y - origin.y) * scale);
174            for i in 0..subpath.len() {
175                let a = map(&subpath[i]);
176                let b = map(&subpath[(i + 1) % subpath.len()]);
177                if a.y == b.y {
178                    continue;
179                }
180                if a.y < b.y {
181                    edges.push(Edge {
182                        top: a,
183                        bottom: b,
184                        winding: 1,
185                    });
186                } else {
187                    edges.push(Edge {
188                        top: b,
189                        bottom: a,
190                        winding: -1,
191                    });
192                }
193            }
194        }
195        if edges.is_empty() {
196            return mask;
197        }
198
199        let mut crossings: Vec<(f32, i32)> = Vec::new();
200        let mut row_coverage = vec![0.0f32; width];
201        let subsample_weight = 1.0 / SUBSAMPLES as f32;
202
203        for row in 0..height {
204            row_coverage.fill(0.0);
205            let mut row_touched = false;
206
207            for sub in 0..SUBSAMPLES {
208                let sample_y = row as f32 + (sub as f32 + 0.5) * subsample_weight;
209
210                crossings.clear();
211                for edge in &edges {
212                    if edge.top.y <= sample_y && sample_y < edge.bottom.y {
213                        let t = (sample_y - edge.top.y) / (edge.bottom.y - edge.top.y);
214                        let x = edge.top.x + t * (edge.bottom.x - edge.top.x);
215                        crossings.push((x, edge.winding));
216                    }
217                }
218                if crossings.len() < 2 {
219                    continue;
220                }
221                crossings.sort_by(|a, b| a.0.total_cmp(&b.0));
222
223                let mut winding = 0i32;
224                let mut span_start = 0.0f32;
225                for &(x, direction) in crossings.iter() {
226                    let was_inside = match self.fill_rule {
227                        PathFillRule::NonZero => winding != 0,
228                        PathFillRule::EvenOdd => winding % 2 != 0,
229                    };
230                    winding += match self.fill_rule {
231                        PathFillRule::NonZero => direction,
232                        PathFillRule::EvenOdd => 1,
233                    };
234                    let is_inside = match self.fill_rule {
235                        PathFillRule::NonZero => winding != 0,
236                        PathFillRule::EvenOdd => winding % 2 != 0,
237                    };
238                    if !was_inside && is_inside {
239                        span_start = x;
240                    } else if was_inside && !is_inside {
241                        row_touched |= accumulate_span(
242                            &mut row_coverage,
243                            span_start,
244                            x,
245                            subsample_weight,
246                            width,
247                        );
248                    }
249                }
250            }
251
252            if row_touched {
253                let mask_row = &mut mask[row * width..(row + 1) * width];
254                for (dst, coverage) in mask_row.iter_mut().zip(row_coverage.iter()) {
255                    let existing = *dst as f32 / 255.0;
256                    let combined = (existing + coverage).min(1.0);
257                    *dst = (combined * 255.0 + 0.5) as u8;
258                }
259            }
260        }
261
262        mask
263    }
264}
265
266/// Adds one horizontal span `[x0, x1)` of one sub-scanline into the row
267/// coverage accumulator, handling fractional span ends. Returns whether any
268/// pixel was touched.
269fn accumulate_span(row_coverage: &mut [f32], x0: f32, x1: f32, weight: f32, width: usize) -> bool {
270    let x0 = x0.max(0.0);
271    let x1 = x1.min(width as f32);
272    if x1 <= x0 {
273        return false;
274    }
275
276    let first = x0.floor() as usize;
277    let last = (x1.ceil() as usize).min(width);
278    for (pixel, coverage) in row_coverage.iter_mut().enumerate().take(last).skip(first) {
279        let pixel_start = pixel as f32;
280        let pixel_end = pixel_start + 1.0;
281        let covered = (x1.min(pixel_end) - x0.max(pixel_start)).max(0.0);
282        *coverage += covered * weight;
283    }
284    true
285}
286
287struct PathLexer<'a> {
288    bytes: &'a [u8],
289    pos: usize,
290}
291
292impl<'a> PathLexer<'a> {
293    fn new(d: &'a str) -> Self {
294        Self {
295            bytes: d.as_bytes(),
296            pos: 0,
297        }
298    }
299
300    fn skip_separators(&mut self) {
301        while self.pos < self.bytes.len() {
302            match self.bytes[self.pos] {
303                b' ' | b'\t' | b'\r' | b'\n' | b',' => self.pos += 1,
304                _ => break,
305            }
306        }
307    }
308
309    fn peek(&mut self) -> Option<u8> {
310        self.skip_separators();
311        self.bytes.get(self.pos).copied()
312    }
313
314    fn at_number(&mut self) -> bool {
315        matches!(self.peek(), Some(b'0'..=b'9' | b'.' | b'-' | b'+'))
316    }
317
318    fn next_command(&mut self) -> Option<u8> {
319        let byte = self.peek()?;
320        if byte.is_ascii_alphabetic() {
321            self.pos += 1;
322            Some(byte)
323        } else {
324            None
325        }
326    }
327
328    fn next_number(&mut self) -> Result<f32, SvgPathError> {
329        self.skip_separators();
330        let start = self.pos;
331        let bytes = self.bytes;
332        let mut pos = self.pos;
333
334        if pos < bytes.len() && (bytes[pos] == b'+' || bytes[pos] == b'-') {
335            pos += 1;
336        }
337        let int_digits = Self::eat_digits(bytes, &mut pos);
338        let mut frac_digits = 0;
339        if pos < bytes.len() && bytes[pos] == b'.' {
340            pos += 1;
341            frac_digits = Self::eat_digits(bytes, &mut pos);
342        }
343        if int_digits == 0 && frac_digits == 0 {
344            return Err(SvgPathError::ExpectedNumber { offset: start });
345        }
346        if pos < bytes.len() && (bytes[pos] == b'e' || bytes[pos] == b'E') {
347            let mut exp_pos = pos + 1;
348            if exp_pos < bytes.len() && (bytes[exp_pos] == b'+' || bytes[exp_pos] == b'-') {
349                exp_pos += 1;
350            }
351            if Self::eat_digits(bytes, &mut exp_pos) > 0 {
352                pos = exp_pos;
353            }
354        }
355
356        let text = std::str::from_utf8(&bytes[start..pos])
357            .map_err(|_| SvgPathError::ExpectedNumber { offset: start })?;
358        let value = text
359            .parse::<f32>()
360            .map_err(|_| SvgPathError::ExpectedNumber { offset: start })?;
361        self.pos = pos;
362        Ok(value)
363    }
364
365    fn eat_digits(bytes: &[u8], pos: &mut usize) -> usize {
366        let start = *pos;
367        while *pos < bytes.len() && bytes[*pos].is_ascii_digit() {
368            *pos += 1;
369        }
370        *pos - start
371    }
372
373    fn next_flag(&mut self) -> Result<bool, SvgPathError> {
374        self.skip_separators();
375        match self.bytes.get(self.pos) {
376            Some(b'0') => {
377                self.pos += 1;
378                Ok(false)
379            }
380            Some(b'1') => {
381                self.pos += 1;
382                Ok(true)
383            }
384            _ => Err(SvgPathError::ExpectedFlag { offset: self.pos }),
385        }
386    }
387
388    fn at_end(&mut self) -> bool {
389        self.peek().is_none()
390    }
391}
392
393struct PathBuilder {
394    subpaths: Vec<Vec<Point>>,
395    current: Vec<Point>,
396    position: Point,
397    subpath_start: Point,
398    last_cubic_control: Option<Point>,
399    last_quad_control: Option<Point>,
400}
401
402impl PathBuilder {
403    fn new() -> Self {
404        Self {
405            subpaths: Vec::new(),
406            current: Vec::new(),
407            position: Point::ZERO,
408            subpath_start: Point::ZERO,
409            last_cubic_control: None,
410            last_quad_control: None,
411        }
412    }
413
414    fn flush_subpath(&mut self) {
415        if self.current.len() >= 2 {
416            self.subpaths.push(std::mem::take(&mut self.current));
417        } else {
418            self.current.clear();
419        }
420    }
421
422    fn move_to(&mut self, point: Point) {
423        self.flush_subpath();
424        self.position = point;
425        self.subpath_start = point;
426        self.current.push(point);
427    }
428
429    fn line_to(&mut self, point: Point) {
430        if self.current.is_empty() {
431            self.current.push(self.position);
432        }
433        self.current.push(point);
434        self.position = point;
435    }
436
437    fn close(&mut self) {
438        self.position = self.subpath_start;
439        self.flush_subpath();
440        self.current.push(self.subpath_start);
441    }
442
443    fn finish(mut self) -> Vec<Vec<Point>> {
444        self.flush_subpath();
445        self.subpaths
446    }
447}
448
449fn parse_path_data(d: &str) -> Result<Vec<Vec<Point>>, SvgPathError> {
450    let mut lexer = PathLexer::new(d);
451    let mut builder = PathBuilder::new();
452    let mut command: Option<u8> = None;
453    let mut seen_moveto = false;
454
455    loop {
456        if lexer.at_end() {
457            break;
458        }
459
460        if let Some(next) = lexer.next_command() {
461            command = Some(next);
462        } else if command.is_none() || !lexer.at_number() {
463            let offset = lexer.pos;
464            let byte = lexer.bytes.get(offset).copied().unwrap_or(b'?') as char;
465            return Err(SvgPathError::UnexpectedByte { byte, offset });
466        }
467
468        let Some(cmd) = command else {
469            return Err(SvgPathError::MissingMoveTo);
470        };
471        if !seen_moveto && !matches!(cmd, b'M' | b'm') {
472            return Err(SvgPathError::MissingMoveTo);
473        }
474        let relative = cmd.is_ascii_lowercase();
475        let pos = builder.position;
476        let rel = |value: Point| {
477            if relative {
478                Point::new(pos.x + value.x, pos.y + value.y)
479            } else {
480                value
481            }
482        };
483
484        match cmd.to_ascii_uppercase() {
485            b'M' => {
486                let point = rel(read_point(&mut lexer)?);
487                builder.move_to(point);
488                seen_moveto = true;
489                builder.last_cubic_control = None;
490                builder.last_quad_control = None;
491                command = Some(if relative { b'l' } else { b'L' });
492            }
493            b'L' => {
494                let point = rel(read_point(&mut lexer)?);
495                builder.line_to(point);
496                builder.last_cubic_control = None;
497                builder.last_quad_control = None;
498            }
499            b'H' => {
500                let x = lexer.next_number()?;
501                let x = if relative { pos.x + x } else { x };
502                builder.line_to(Point::new(x, pos.y));
503                builder.last_cubic_control = None;
504                builder.last_quad_control = None;
505            }
506            b'V' => {
507                let y = lexer.next_number()?;
508                let y = if relative { pos.y + y } else { y };
509                builder.line_to(Point::new(pos.x, y));
510                builder.last_cubic_control = None;
511                builder.last_quad_control = None;
512            }
513            b'C' => {
514                let c1 = rel(read_point(&mut lexer)?);
515                let c2 = rel(read_point(&mut lexer)?);
516                let end = rel(read_point(&mut lexer)?);
517                emit_cubic(&mut builder, c1, c2, end);
518            }
519            b'S' => {
520                let c1 = match builder.last_cubic_control {
521                    Some(control) => reflect(pos, control),
522                    None => pos,
523                };
524                let c2 = rel(read_point(&mut lexer)?);
525                let end = rel(read_point(&mut lexer)?);
526                emit_cubic(&mut builder, c1, c2, end);
527            }
528            b'Q' => {
529                let control = rel(read_point(&mut lexer)?);
530                let end = rel(read_point(&mut lexer)?);
531                emit_quad(&mut builder, control, end);
532            }
533            b'T' => {
534                let control = match builder.last_quad_control {
535                    Some(control) => reflect(pos, control),
536                    None => pos,
537                };
538                let end = rel(read_point(&mut lexer)?);
539                emit_quad(&mut builder, control, end);
540            }
541            b'A' => {
542                let rx = lexer.next_number()?;
543                let ry = lexer.next_number()?;
544                let x_rotation_deg = lexer.next_number()?;
545                let large_arc = lexer.next_flag()?;
546                let sweep = lexer.next_flag()?;
547                let end = rel(read_point(&mut lexer)?);
548                emit_arc(&mut builder, rx, ry, x_rotation_deg, large_arc, sweep, end);
549                builder.last_cubic_control = None;
550                builder.last_quad_control = None;
551            }
552            b'Z' => {
553                builder.close();
554                builder.last_cubic_control = None;
555                builder.last_quad_control = None;
556                command = None;
557            }
558            other => {
559                return Err(SvgPathError::UnexpectedByte {
560                    byte: other as char,
561                    offset: lexer.pos.saturating_sub(1),
562                });
563            }
564        }
565    }
566
567    if !seen_moveto {
568        return Err(SvgPathError::MissingMoveTo);
569    }
570    Ok(builder.finish())
571}
572
573fn read_point(lexer: &mut PathLexer<'_>) -> Result<Point, SvgPathError> {
574    let x = lexer.next_number()?;
575    let y = lexer.next_number()?;
576    Ok(Point::new(x, y))
577}
578
579fn reflect(origin: Point, point: Point) -> Point {
580    Point::new(2.0 * origin.x - point.x, 2.0 * origin.y - point.y)
581}
582
583fn emit_cubic(builder: &mut PathBuilder, c1: Point, c2: Point, end: Point) {
584    let start = builder.position;
585    flatten_cubic(builder, start, c1, c2, end, 0);
586    builder.position = end;
587    builder.last_cubic_control = Some(c2);
588    builder.last_quad_control = None;
589}
590
591fn emit_quad(builder: &mut PathBuilder, control: Point, end: Point) {
592    let start = builder.position;
593    let c1 = Point::new(
594        start.x + 2.0 / 3.0 * (control.x - start.x),
595        start.y + 2.0 / 3.0 * (control.y - start.y),
596    );
597    let c2 = Point::new(
598        end.x + 2.0 / 3.0 * (control.x - end.x),
599        end.y + 2.0 / 3.0 * (control.y - end.y),
600    );
601    flatten_cubic(builder, start, c1, c2, end, 0);
602    builder.position = end;
603    builder.last_quad_control = Some(control);
604    builder.last_cubic_control = None;
605}
606
607fn flatten_cubic(
608    builder: &mut PathBuilder,
609    p0: Point,
610    p1: Point,
611    p2: Point,
612    p3: Point,
613    depth: u32,
614) {
615    if depth >= MAX_FLATTEN_DEPTH || cubic_is_flat(p0, p1, p2, p3) {
616        builder.line_to(p3);
617        return;
618    }
619
620    let mid = |a: Point, b: Point| Point::new((a.x + b.x) * 0.5, (a.y + b.y) * 0.5);
621    let p01 = mid(p0, p1);
622    let p12 = mid(p1, p2);
623    let p23 = mid(p2, p3);
624    let p012 = mid(p01, p12);
625    let p123 = mid(p12, p23);
626    let p0123 = mid(p012, p123);
627
628    flatten_cubic(builder, p0, p01, p012, p0123, depth + 1);
629    flatten_cubic(builder, p0123, p123, p23, p3, depth + 1);
630}
631
632/// Flatness test: both control points close enough to the chord.
633fn cubic_is_flat(p0: Point, p1: Point, p2: Point, p3: Point) -> bool {
634    let d1 = point_to_chord_distance_squared(p1, p0, p3);
635    let d2 = point_to_chord_distance_squared(p2, p0, p3);
636    let tolerance = FLATTEN_TOLERANCE * FLATTEN_TOLERANCE;
637    d1 <= tolerance && d2 <= tolerance
638}
639
640fn point_to_chord_distance_squared(point: Point, a: Point, b: Point) -> f32 {
641    let ab = Point::new(b.x - a.x, b.y - a.y);
642    let ap = Point::new(point.x - a.x, point.y - a.y);
643    let ab_len_sq = ab.x * ab.x + ab.y * ab.y;
644    if ab_len_sq <= f32::EPSILON {
645        return ap.x * ap.x + ap.y * ap.y;
646    }
647    let cross = ab.x * ap.y - ab.y * ap.x;
648    cross * cross / ab_len_sq
649}
650
651/// Converts an SVG endpoint-parameterized arc to line segments
652/// (W3C SVG 2 appendix B.2.4).
653fn emit_arc(
654    builder: &mut PathBuilder,
655    rx: f32,
656    ry: f32,
657    x_rotation_deg: f32,
658    large_arc: bool,
659    sweep: bool,
660    end: Point,
661) {
662    let start = builder.position;
663    if (start.x - end.x).abs() <= f32::EPSILON && (start.y - end.y).abs() <= f32::EPSILON {
664        return;
665    }
666    let mut rx = rx.abs();
667    let mut ry = ry.abs();
668    if rx <= f32::EPSILON || ry <= f32::EPSILON {
669        builder.line_to(end);
670        return;
671    }
672
673    let phi = x_rotation_deg.to_radians();
674    let (sin_phi, cos_phi) = phi.sin_cos();
675
676    let dx2 = (start.x - end.x) * 0.5;
677    let dy2 = (start.y - end.y) * 0.5;
678    let x1p = cos_phi * dx2 + sin_phi * dy2;
679    let y1p = -sin_phi * dx2 + cos_phi * dy2;
680
681    let lambda = (x1p * x1p) / (rx * rx) + (y1p * y1p) / (ry * ry);
682    if lambda > 1.0 {
683        let scale = lambda.sqrt();
684        rx *= scale;
685        ry *= scale;
686    }
687
688    let rx_sq = rx * rx;
689    let ry_sq = ry * ry;
690    let numerator = (rx_sq * ry_sq - rx_sq * y1p * y1p - ry_sq * x1p * x1p).max(0.0);
691    let denominator = rx_sq * y1p * y1p + ry_sq * x1p * x1p;
692    let mut coefficient = if denominator <= f32::EPSILON {
693        0.0
694    } else {
695        (numerator / denominator).sqrt()
696    };
697    if large_arc == sweep {
698        coefficient = -coefficient;
699    }
700    let cxp = coefficient * rx * y1p / ry;
701    let cyp = -coefficient * ry * x1p / rx;
702
703    let cx = cos_phi * cxp - sin_phi * cyp + (start.x + end.x) * 0.5;
704    let cy = sin_phi * cxp + cos_phi * cyp + (start.y + end.y) * 0.5;
705
706    let angle_of = |x: f32, y: f32| y.atan2(x);
707    let theta1 = angle_of((x1p - cxp) / rx, (y1p - cyp) / ry);
708    let theta2 = angle_of((-x1p - cxp) / rx, (-y1p - cyp) / ry);
709    let two_pi = std::f32::consts::TAU;
710    let mut delta = theta2 - theta1;
711    if sweep {
712        if delta < 0.0 {
713            delta += two_pi;
714        }
715    } else if delta > 0.0 {
716        delta -= two_pi;
717    }
718
719    let segments = ((delta.abs() / ARC_MAX_ANGLE_STEP).ceil() as usize).max(2);
720    for i in 1..=segments {
721        let theta = theta1 + delta * (i as f32 / segments as f32);
722        let (sin_theta, cos_theta) = theta.sin_cos();
723        let x = cos_phi * rx * cos_theta - sin_phi * ry * sin_theta + cx;
724        let y = sin_phi * rx * cos_theta + cos_phi * ry * sin_theta + cy;
725        builder.line_to(Point::new(x, y));
726    }
727    builder.line_to(end);
728    builder.position = end;
729}
730
731#[cfg(test)]
732mod tests {
733    use super::*;
734
735    fn mask_at(mask: &[u8], width: usize, x: usize, y: usize) -> u8 {
736        mask[y * width + x]
737    }
738
739    #[test]
740    fn parses_absolute_triangle() {
741        let path = VectorPath::parse("M 0 0 L 10 0 L 10 10 Z").expect("valid path");
742        assert_eq!(path.subpaths().len(), 1);
743        assert_eq!(
744            path.subpaths()[0],
745            vec![
746                Point::new(0.0, 0.0),
747                Point::new(10.0, 0.0),
748                Point::new(10.0, 10.0)
749            ]
750        );
751        let bounds = path.bounds();
752        assert_eq!((bounds.x, bounds.y), (0.0, 0.0));
753        assert_eq!((bounds.width, bounds.height), (10.0, 10.0));
754    }
755
756    #[test]
757    fn parses_relative_commands_and_h_v() {
758        let path = VectorPath::parse("m 5 5 l 10 0 v 10 h -10 z").expect("valid path");
759        assert_eq!(
760            path.subpaths()[0],
761            vec![
762                Point::new(5.0, 5.0),
763                Point::new(15.0, 5.0),
764                Point::new(15.0, 15.0),
765                Point::new(5.0, 15.0)
766            ]
767        );
768    }
769
770    #[test]
771    fn parses_packed_numbers_and_negative_shorthand() {
772        let path = VectorPath::parse("M10-5L.5.5Z").expect("valid path");
773        assert_eq!(
774            path.subpaths()[0],
775            vec![Point::new(10.0, -5.0), Point::new(0.5, 0.5)]
776        );
777    }
778
779    #[test]
780    fn implicit_lineto_after_moveto() {
781        let path = VectorPath::parse("M 0 0 10 0 10 10").expect("valid path");
782        assert_eq!(path.subpaths()[0].len(), 3);
783        assert_eq!(path.subpaths()[0][2], Point::new(10.0, 10.0));
784    }
785
786    #[test]
787    fn cubic_flattening_hits_endpoints() {
788        let path = VectorPath::parse("M 0 0 C 0 10 10 10 10 0").expect("valid path");
789        let points = &path.subpaths()[0];
790        assert_eq!(points[0], Point::new(0.0, 0.0));
791        assert_eq!(*points.last().unwrap(), Point::new(10.0, 0.0));
792        assert!(points.len() > 4, "curve must be subdivided");
793        let mid = points
794            .iter()
795            .min_by(|a, b| (a.x - 5.0).abs().total_cmp(&(b.x - 5.0).abs()))
796            .unwrap();
797        assert!(
798            (mid.y - 7.5).abs() < 0.2,
799            "flattened curve must pass near the true midpoint, got {mid:?}"
800        );
801    }
802
803    #[test]
804    fn smooth_cubic_reflects_control_point() {
805        let path = VectorPath::parse("M 0 0 C 0 5 2 5 5 5 S 10 5 10 10").expect("valid path");
806        let points = &path.subpaths()[0];
807        assert_eq!(*points.last().unwrap(), Point::new(10.0, 10.0));
808        assert!(
809            points
810                .iter()
811                .any(|p| (p.x - 5.0).abs() < 0.1 && (p.y - 5.0).abs() < 0.1)
812        );
813    }
814
815    #[test]
816    fn quadratic_and_smooth_quadratic() {
817        let path = VectorPath::parse("M 0 0 Q 5 10 10 0 T 20 0").expect("valid path");
818        let points = &path.subpaths()[0];
819        assert_eq!(*points.last().unwrap(), Point::new(20.0, 0.0));
820        assert!(
821            points
822                .iter()
823                .any(|p| (p.x - 5.0).abs() < 0.3 && (p.y - 5.0).abs() < 0.3)
824        );
825        assert!(
826            points
827                .iter()
828                .any(|p| (p.x - 15.0).abs() < 0.3 && (p.y + 5.0).abs() < 0.3)
829        );
830    }
831
832    #[test]
833    fn arc_travels_through_expected_quadrant() {
834        let path = VectorPath::parse("M 0 0 A 5 5 0 0 1 10 0").expect("valid path");
835        let points = &path.subpaths()[0];
836        assert_eq!(*points.last().unwrap(), Point::new(10.0, 0.0));
837        let lowest = points.iter().fold(0.0f32, |acc, p| acc.min(p.y));
838        assert!(
839            (lowest + 5.0).abs() < 0.1,
840            "sweep=1 arc must pass through (5,-5), lowest y = {lowest}"
841        );
842
843        let path = VectorPath::parse("M 0 0 A 5 5 0 0 0 10 0").expect("valid path");
844        let highest = path.subpaths()[0]
845            .iter()
846            .fold(0.0f32, |acc, p| acc.max(p.y));
847        assert!(
848            (highest - 5.0).abs() < 0.1,
849            "sweep=0 arc must pass through (5,5), highest y = {highest}"
850        );
851    }
852
853    #[test]
854    fn arc_flags_may_be_packed() {
855        let spaced = VectorPath::parse("M 0 0 A 5 5 0 0 1 10 0").expect("valid path");
856        let packed = VectorPath::parse("M0 0A5 5 0 0110 0").expect("valid path");
857        assert_eq!(
858            spaced.subpaths()[0].len(),
859            packed.subpaths()[0].len(),
860            "packed arc flags must parse identically"
861        );
862    }
863
864    #[test]
865    fn multiple_subpaths() {
866        let path =
867            VectorPath::parse("M 0 0 h 4 v 4 h -4 Z M 10 10 h 4 v 4 h -4 Z").expect("valid path");
868        assert_eq!(path.subpaths().len(), 2);
869    }
870
871    #[test]
872    fn rejects_garbage() {
873        assert!(VectorPath::parse("this is not a path").is_err());
874        assert!(
875            VectorPath::parse("L 10 10").is_err(),
876            "must start with moveto"
877        );
878        assert!(VectorPath::parse("M 10").is_err(), "missing y coordinate");
879        assert!(
880            VectorPath::parse("M 0 0 A 5 5 0 2 1 10 0").is_err(),
881            "bad flag"
882        );
883        assert_eq!(
884            VectorPath::parse("").unwrap_err(),
885            SvgPathError::MissingMoveTo
886        );
887    }
888
889    #[test]
890    fn fills_axis_aligned_rectangle() {
891        let path = VectorPath::parse("M 2 2 H 8 V 8 H 2 Z").expect("valid path");
892        let mask = path.coverage_mask(10, 10, Point::ZERO, 1.0);
893
894        assert_eq!(mask_at(&mask, 10, 5, 5), 255, "interior must be opaque");
895        assert_eq!(mask_at(&mask, 10, 4, 2), 255, "top edge row is inside");
896        assert_eq!(mask_at(&mask, 10, 0, 0), 0, "outside must stay empty");
897        assert_eq!(mask_at(&mask, 10, 9, 9), 0, "outside must stay empty");
898    }
899
900    #[test]
901    fn triangle_edge_is_antialiased() {
902        let path = VectorPath::parse("M 0 0 L 8 0 L 0 8 Z").expect("valid path");
903        let mask = path.coverage_mask(8, 8, Point::ZERO, 1.0);
904
905        assert_eq!(mask_at(&mask, 8, 1, 1), 255, "deep interior is opaque");
906        assert_eq!(mask_at(&mask, 8, 7, 7), 0, "far corner is empty");
907        let diagonal = mask_at(&mask, 8, 4, 3);
908        assert!(
909            diagonal > 30 && diagonal < 225,
910            "diagonal pixel should be partially covered, got {diagonal}"
911        );
912    }
913
914    #[test]
915    fn even_odd_ring_has_a_hole() {
916        let d = "M 0 0 H 12 V 12 H 0 Z M 4 4 H 8 V 8 H 4 Z";
917        let even_odd =
918            VectorPath::parse_with_fill_rule(d, PathFillRule::EvenOdd).expect("valid path");
919        let non_zero = VectorPath::parse(d).expect("valid path");
920
921        let even_odd_mask = even_odd.coverage_mask(12, 12, Point::ZERO, 1.0);
922        let non_zero_mask = non_zero.coverage_mask(12, 12, Point::ZERO, 1.0);
923
924        assert_eq!(mask_at(&even_odd_mask, 12, 6, 6), 0, "even-odd hole");
925        assert_eq!(mask_at(&even_odd_mask, 12, 2, 6), 255, "even-odd ring");
926        assert_eq!(mask_at(&non_zero_mask, 12, 6, 6), 255, "non-zero solid");
927    }
928
929    #[test]
930    fn non_zero_ring_with_reversed_inner_winding_has_a_hole() {
931        let d = "M 0 0 H 12 V 12 H 0 Z M 4 4 V 8 H 8 V 4 Z";
932        let path = VectorPath::parse(d).expect("valid path");
933        let mask = path.coverage_mask(12, 12, Point::ZERO, 1.0);
934        assert_eq!(mask_at(&mask, 12, 6, 6), 0, "reversed winding hole");
935        assert_eq!(mask_at(&mask, 12, 2, 6), 255, "ring stays filled");
936    }
937
938    #[test]
939    fn circle_from_arcs_fills_center_and_respects_radius() {
940        let path =
941            VectorPath::parse("M 0 8 A 8 8 0 1 1 16 8 A 8 8 0 1 1 0 8 Z").expect("valid path");
942        let mask = path.coverage_mask(16, 16, Point::ZERO, 1.0);
943
944        assert_eq!(mask_at(&mask, 16, 8, 8), 255, "circle center is opaque");
945        assert_eq!(mask_at(&mask, 16, 0, 0), 0, "circle corner is empty");
946        assert_eq!(mask_at(&mask, 16, 15, 0), 0, "circle corner is empty");
947        let area: f32 = mask.iter().map(|&value| value as f32 / 255.0).sum();
948        let expected = std::f32::consts::PI * 8.0 * 8.0;
949        assert!(
950            (area - expected).abs() / expected < 0.05,
951            "filled area {area} should be close to {expected}"
952        );
953    }
954
955    #[test]
956    fn scale_and_origin_map_path_units_to_pixels() {
957        let path = VectorPath::parse("M 10 10 H 14 V 14 H 10 Z").expect("valid path");
958        let mask = path.coverage_mask(8, 8, Point::new(10.0, 10.0), 2.0);
959        assert_eq!(mask_at(&mask, 8, 4, 4), 255, "scaled interior");
960        let full: usize = mask.iter().filter(|&&value| value == 255).count();
961        assert_eq!(full, 64, "the 8x8 pixel mask must be fully covered");
962    }
963
964    #[test]
965    fn empty_and_degenerate_paths_produce_empty_masks() {
966        let path = VectorPath::parse("M 5 5 L 6 6").expect("valid path");
967        assert!(path.is_empty());
968        let mask = path.coverage_mask(8, 8, Point::ZERO, 1.0);
969        assert!(mask.iter().all(|&value| value == 0));
970    }
971}
cranpose_ui_graphics/vector_path.rs

cranpose_ui_graphics/
vector_path.rs
