1use sequoia_core::Point;
2
3use crate::TOLERANCE;
4use crate::path::{Path, PathSeg};
5
6#[derive(Clone, Debug, Default, PartialEq)]
7pub struct Contour {
8 pub points: Vec<Point>,
9
10 pub closed: bool,
11}
12
13impl Contour {
14 pub fn is_degenerate(&self) -> bool {
15 self.points.len() < 2
16 }
17
18 pub fn edge_count(&self) -> usize {
19 if self.closed {
20 self.points.len()
21 } else {
22 self.points.len().saturating_sub(1)
23 }
24 }
25}
26
27const MAX_SUBDIVISION: u32 = 4096;
28
29pub fn flatten(path: &Path, tolerance: f32) -> Vec<Contour> {
30 let tol = if tolerance.is_finite() {
31 tolerance.max(0.01)
32 } else {
33 TOLERANCE
34 };
35 let mut out: Vec<Contour> = Vec::new();
36 let mut current = Contour::default();
37 let mut pen = Point::ZERO;
38 let mut start = Point::ZERO;
39 let mut open = false;
40
41 for seg in path.segs() {
42 match *seg {
43 PathSeg::Move(p) => {
44 finish(&mut current, &mut out, open);
45 current = Contour {
46 points: vec![p],
47 closed: false,
48 };
49 pen = p;
50 start = p;
51 open = true;
52 }
53 PathSeg::Line(p) => {
54 if !open {
55 begin(&mut current, pen);
56 start = pen;
57 open = true;
58 }
59 push_point(&mut current.points, p);
60 pen = p;
61 }
62 PathSeg::Quad(c, p) => {
63 if !open {
64 begin(&mut current, pen);
65 start = pen;
66 open = true;
67 }
68 flatten_quad(&mut current.points, pen, c, p, tol);
69 pen = p;
70 }
71 PathSeg::Cubic(c1, c2, p) => {
72 if !open {
73 begin(&mut current, pen);
74 start = pen;
75 open = true;
76 }
77 flatten_cubic(&mut current.points, pen, c1, c2, p, tol);
78 pen = p;
79 }
80 PathSeg::Close => {
81 if open {
82 push_point(&mut current.points, start);
83 current.closed = true;
84 finish(&mut current, &mut out, true);
85 current = Contour::default();
86 pen = start;
87 open = false;
88 }
89 }
90 }
91 }
92
93 finish(&mut current, &mut out, open);
94 out.retain(|c| !c.is_degenerate());
95 out
96}
97
98fn begin(current: &mut Contour, pen: Point) {
99 current.points.clear();
100 current.points.push(pen);
101}
102
103fn finish(current: &mut Contour, out: &mut Vec<Contour>, open: bool) {
104 if open && current.points.len() >= 2 {
105 let mut contour = std::mem::take(current);
106 contour.points.dedup_by(|a, b| a == b);
107 if contour.points.len() >= 2 {
108 out.push(contour);
109 }
110 } else {
111 current.points.clear();
112 }
113}
114
115fn push_point(points: &mut Vec<Point>, p: Point) {
116 if points.last() != Some(&p) {
117 points.push(p);
118 }
119}
120
121pub(crate) fn flatten_quad(out: &mut Vec<Point>, p0: Point, c: Point, p2: Point, tol: f32) {
122 let mid = Point::new((p0.x + p2.x) * 0.5, (p0.y + p2.y) * 0.5);
123 let dev = ((c.x - mid.x).powi(2) + (c.y - mid.y).powi(2)).sqrt() * 0.5;
124 if dev <= tol {
125 push_point(out, p2);
126 return;
127 }
128
129 let p01 = lerp(p0, c, 0.5);
130 let p12 = lerp(c, p2, 0.5);
131 let m = lerp(p01, p12, 0.5);
132 flatten_quad(out, p0, p01, m, tol);
133 flatten_quad(out, m, p12, p2, tol);
134}
135
136pub(crate) fn flatten_cubic(
137 out: &mut Vec<Point>,
138 p0: Point,
139 c1: Point,
140 c2: Point,
141 p3: Point,
142 tol: f32,
143) {
144 let mut steps = 0;
145 flatten_cubic_rec(out, p0, c1, c2, p3, tol, &mut steps);
146}
147
148fn flatten_cubic_rec(
149 out: &mut Vec<Point>,
150 p0: Point,
151 c1: Point,
152 c2: Point,
153 p3: Point,
154 tol: f32,
155 steps: &mut u32,
156) {
157 if *steps >= MAX_SUBDIVISION {
158 push_point(out, p3);
159 return;
160 }
161 let d1 = dist_to_segment(c1, p0, p3);
162 let d2 = dist_to_segment(c2, p0, p3);
163 if (d1.max(d2)) * 0.75 <= tol {
164 push_point(out, p3);
165 return;
166 }
167 *steps += 1;
168 let p01 = lerp(p0, c1, 0.5);
169 let p12 = lerp(c1, c2, 0.5);
170 let p23 = lerp(c2, p3, 0.5);
171 let p012 = lerp(p01, p12, 0.5);
172 let p123 = lerp(p12, p23, 0.5);
173 let m = lerp(p012, p123, 0.5);
174 flatten_cubic_rec(out, p0, p01, p012, m, tol, steps);
175 flatten_cubic_rec(out, m, p123, p23, p3, tol, steps);
176}
177
178fn lerp(a: Point, b: Point, t: f32) -> Point {
179 Point::new(a.x + (b.x - a.x) * t, a.y + (b.y - a.y) * t)
180}
181
182pub(crate) fn dist_to_segment(p: Point, a: Point, b: Point) -> f32 {
183 let abx = b.x - a.x;
184 let aby = b.y - a.y;
185 let len2 = abx * abx + aby * aby;
186 if len2 <= f32::MIN_POSITIVE {
187 return ((p.x - a.x).powi(2) + (p.y - a.y).powi(2)).sqrt();
188 }
189 let t = (((p.x - a.x) * abx + (p.y - a.y) * aby) / len2).clamp(0.0, 1.0);
190 let dx = p.x - (a.x + abx * t);
191 let dy = p.y - (a.y + aby * t);
192 (dx * dx + dy * dy).sqrt()
193}
194
195pub(crate) fn arc_steps(radius: f32, span_rad: f32, tol: f32) -> usize {
196 if radius <= tol || !span_rad.is_finite() {
197 return 1;
198 }
199 let cos_half = (1.0 - tol / radius).clamp(-1.0, 1.0);
200 let max_step = 2.0 * cos_half.acos();
201 if max_step <= 0.0 {
202 return 1;
203 }
204 ((span_rad.abs() / max_step).ceil() as usize).clamp(1, MAX_SUBDIVISION as usize)
205}