1use std::cell::Cell;
6use std::iter;
7use std::num::NonZeroU64;
8
9use smallvec::SmallVec;
10
11use crate::math::{self, Bezier, Mat};
12use crate::renderer::StrokeStyle;
13use crate::shapes::paint::{StrokeCap, StrokeJoin};
14
15#[derive(Clone, Debug, Default)]
16pub struct CommandPathBuilder {
17 commands: Vec<Command>,
18}
19
20impl CommandPathBuilder {
21 pub fn new() -> Self {
22 Self { commands: Vec::new() }
23 }
24
25 pub fn move_to(&mut self, p: math::Vec) -> &mut Self {
26 self.commands.push(Command::MoveTo(p));
27 self
28 }
29
30 pub fn line_to(&mut self, p: math::Vec) -> &mut Self {
31 self.commands.push(Command::LineTo(p));
32 self
33 }
34
35 pub fn cubic_to(&mut self, c0: math::Vec, c1: math::Vec, p: math::Vec) -> &mut Self {
36 self.commands.push(Command::CubicTo(c0, c1, p));
37 self
38 }
39
40 pub fn rect(&mut self, p: math::Vec, size: math::Vec) -> &mut Self {
41 self.move_to(p)
42 .line_to(p + math::Vec::new(size.x, 0.0))
43 .line_to(p + math::Vec::new(size.x, size.y))
44 .line_to(p + math::Vec::new(0.0, size.y))
45 .close()
46 }
47
48 pub fn path(&mut self, path: &CommandPath, t: Option<Mat>) -> &mut Self {
49 if let Some(t) = t {
50 self.commands.extend(path.commands.iter().map(|&command| match command {
51 Command::MoveTo(p) => Command::MoveTo(t * p),
52 Command::LineTo(p) => Command::LineTo(t * p),
53 Command::CubicTo(c0, c1, p) => Command::CubicTo(t * c0, t * c1, t * p),
54 Command::Close => Command::Close,
55 }));
56 } else {
57 self.commands.extend(path.commands.iter().copied());
58 }
59 self
60 }
61
62 pub fn close(&mut self) -> &mut Self {
63 self.commands.push(Command::Close);
64 self
65 }
66
67 pub fn build(self) -> CommandPath {
68 CommandPath { commands: self.commands, user_tag: Cell::new(None) }
69 }
70}
71
72#[derive(Clone, Copy, Debug)]
73pub enum Command {
74 MoveTo(math::Vec),
75 LineTo(math::Vec),
76 CubicTo(math::Vec, math::Vec, math::Vec),
77 Close,
78}
79
80#[derive(Clone, Debug)]
81pub struct CommandPath {
82 pub commands: Vec<Command>,
83 pub user_tag: Cell<Option<NonZeroU64>>,
84}
85
86impl CommandPath {
87 pub fn outline_strokes(&self, style: &StrokeStyle) -> Self {
88 let mut commands = Vec::new();
89
90 let mut curves = Vec::new();
91 let mut end_point = None;
92
93 let push = |curves: &mut Vec<Bezier>, curve: Bezier| {
94 if let Some(curve) = curve.normalize() {
95 curves.push(curve);
96 }
97 };
98
99 for command in &self.commands {
100 match *command {
101 Command::MoveTo(p) => {
102 if !curves.is_empty() {
103 if let Some(outline) = Outline::new(&curves, false, style) {
104 commands.extend(outline.as_commands());
105 }
106
107 curves.clear();
108 }
109
110 end_point = Some(p);
111 }
112 Command::LineTo(p) => {
113 push(&mut curves, Bezier::Line([end_point.unwrap(), p]));
114 end_point = Some(p);
115 }
116 Command::CubicTo(c0, c1, p) => {
117 push(&mut curves, Bezier::Cubic([end_point.unwrap(), c0, c1, p]));
118 end_point = Some(p);
119 }
120 Command::Close => {
121 if let (Some(first), Some(last)) = (
122 curves.first().and_then(|c| c.points().first().copied()),
123 curves.last().and_then(|c| c.points().last().copied()),
124 ) {
125 if first.distance(last) > 0.01 {
126 push(&mut curves, Bezier::Line([last, first]));
127 }
128 }
129
130 if let Some(outline) = Outline::new(&curves, true, style) {
131 commands.extend(outline.as_commands());
132 }
133
134 curves.clear();
135 end_point = None;
136 }
137 }
138 }
139
140 if !curves.is_empty() {
141 if let Some(outline) = Outline::new(&curves, false, style) {
142 commands.extend(outline.as_commands());
143 }
144 }
145
146 Self { commands, user_tag: Cell::new(None) }
147 }
148}
149
150#[derive(Debug)]
151struct Ray {
152 point: math::Vec,
153 angle: f32,
154}
155
156impl Ray {
157 pub fn new(p0: math::Vec, p1: math::Vec) -> Self {
158 let diff = p1 - p0;
159 Self { point: p1, angle: diff.y.atan2(diff.x) }
160 }
161
162 fn dir(&self) -> math::Vec {
163 let (sin, cos) = self.angle.sin_cos();
164 math::Vec::new(cos, sin)
165 }
166
167 pub fn intersect(&self, other: &Self) -> Option<math::Vec> {
168 let diff = other.point - self.point;
169
170 let dir0 = self.dir();
171 let dir1 = other.dir();
172 let det = dir1.x * dir0.y - dir1.y * dir0.x;
173
174 if det.abs() == 0.0 {
175 return None;
176 }
177
178 let t = (diff.y * dir1.x - diff.x * dir1.y) / det;
179 let u = (diff.y * dir0.x - diff.x * dir0.y) / det;
180
181 if t.is_sign_negative() || u.is_sign_negative() {
182 return None;
183 }
184
185 Some(self.point + math::Vec::new(dir0.x, dir0.y) * t)
186 }
187
188 pub fn angle_diff(&self, other: &Self) -> f32 {
189 let diff = self.angle - other.angle;
190 let (sin, cos) = diff.sin_cos();
191
192 sin.atan2(cos).abs()
193 }
194
195 pub fn project(&self, dist: f32) -> math::Vec {
196 self.point + self.dir() * dist
197 }
198
199 pub fn mid(&self, other: &Self) -> Self {
200 let mid_angle = (self.dir() + other.dir()) * 0.5;
201 Self { point: (self.point + other.point) * 0.5, angle: mid_angle.y.atan2(mid_angle.x) }
202 }
203}
204
205const MITER_LIMIT: f32 = 10.0;
206
207#[derive(Debug)]
208struct Outline {
209 curves: Vec<Bezier>,
210 second_outline_index: Option<usize>,
211}
212
213impl Outline {
214 fn last_first_ray(&self, next_curves: &[Bezier]) -> (Ray, Ray) {
215 let last = self.curves.last().unwrap();
216 let first = next_curves.first().unwrap();
217
218 let [p0, p1] = last.right_different();
219 let last_ray = Ray::new(p0, p1);
220 let [p0, p1] = first.left_different();
221 let first_ray = Ray::new(p1, p0);
222
223 (last_ray, first_ray)
224 }
225
226 fn join(&mut self, next_curves: &[Bezier], dist: f32, join: StrokeJoin) {
227 let last = self.curves.last().unwrap();
228 let first = next_curves.first().unwrap();
229 let (last_ray, first_ray) = self.last_first_ray(next_curves);
230
231 if last.intersect(first) {
232 self.curves.push(Bezier::Line([last_ray.point, first_ray.point]));
233 } else {
234 let mid_ray = last_ray.mid(&first_ray);
235
236 match join {
237 StrokeJoin::Bevel => {
238 self.curves.push(Bezier::Line([last_ray.point, first_ray.point]));
239 }
240 StrokeJoin::Miter => {
241 let intersection = last_ray.intersect(&first_ray);
242 let above_limit =
243 last_ray.angle_diff(&first_ray) >= MITER_LIMIT.recip().asin() * 2.0;
244
245 match intersection {
246 Some(intersection) if above_limit => {
247 self.curves.push(Bezier::Line([last_ray.point, intersection]));
248 self.curves.push(Bezier::Line([intersection, first_ray.point]));
249 }
250 _ => {
251 self.curves.push(Bezier::Line([last_ray.point, first_ray.point]));
252 }
253 }
254 }
255 StrokeJoin::Round => {
256 let angle = std::f32::consts::PI - last_ray.angle_diff(&first_ray);
257 if angle < std::f32::consts::FRAC_PI_2 {
258 self.curves.push(Bezier::Cubic([
259 last_ray.point,
260 last_ray.project(math::arc_constant(angle) * dist),
261 first_ray.project(math::arc_constant(angle) * dist),
262 first_ray.point,
263 ]));
264 } else {
265 let angle = angle / 2.0;
266 let mid_dist = (1.0 - angle.cos()) * dist;
267 let mid = mid_ray.project(mid_dist);
268
269 let mid_left =
270 Ray { point: mid, angle: mid_ray.angle + std::f32::consts::FRAC_PI_2 };
271 let mid_right =
272 Ray { point: mid, angle: mid_ray.angle - std::f32::consts::FRAC_PI_2 };
273
274 self.curves.push(Bezier::Cubic([
275 last_ray.point,
276 last_ray.project(math::arc_constant(angle) * dist),
277 mid_left.project(math::arc_constant(angle) * dist),
278 mid,
279 ]));
280 self.curves.push(Bezier::Cubic([
281 mid,
282 mid_right.project(math::arc_constant(angle) * dist),
283 first_ray.project(math::arc_constant(angle) * dist),
284 first_ray.point,
285 ]));
286 }
287 }
288 }
289 }
290 }
291
292 fn join_curves(
293 &mut self,
294 mut offset_curves: impl Iterator<Item = SmallVec<[Bezier; 16]>>,
295 dist: f32,
296 join: StrokeJoin,
297 is_closed: bool,
298 ) {
299 let start_index = self.curves.len();
300 self.curves.extend(offset_curves.next().unwrap());
301
302 for next_curves in offset_curves {
303 self.join(&next_curves, dist, join);
304 self.curves.extend(next_curves);
305 }
306
307 if is_closed {
308 let next_curves = [self.curves[start_index].clone()];
309 self.join(&next_curves, dist, join);
310 }
311 }
312
313 fn cap_end(&mut self, last_ray: &Ray, first_ray: &Ray, dist: f32, cap: StrokeCap) {
314 match cap {
315 StrokeCap::Butt => {
316 self.curves.push(Bezier::Line([last_ray.point, first_ray.point]));
317 }
318 StrokeCap::Square => {
319 let projected_last = last_ray.project(dist);
320 let projected_first = first_ray.project(dist);
321
322 self.curves.push(Bezier::Line([last_ray.point, projected_last]));
323 self.curves.push(Bezier::Line([projected_last, projected_first]));
324 self.curves.push(Bezier::Line([projected_first, first_ray.point]));
325 }
326 StrokeCap::Round => {
327 let mid_ray = last_ray.mid(first_ray);
328 let mid = mid_ray.project(dist);
329
330 let mid_left =
331 Ray { point: mid, angle: mid_ray.angle + std::f32::consts::FRAC_PI_2 };
332 let mid_right =
333 Ray { point: mid, angle: mid_ray.angle - std::f32::consts::FRAC_PI_2 };
334
335 self.curves.push(Bezier::Cubic([
336 last_ray.point,
337 last_ray.project(math::arc_constant(std::f32::consts::FRAC_PI_2) * dist),
338 mid_left.project(math::arc_constant(std::f32::consts::FRAC_PI_2) * dist),
339 mid,
340 ]));
341 self.curves.push(Bezier::Cubic([
342 mid,
343 mid_right.project(math::arc_constant(std::f32::consts::FRAC_PI_2) * dist),
344 first_ray.project(math::arc_constant(std::f32::consts::FRAC_PI_2) * dist),
345 first_ray.point,
346 ]));
347 }
348 }
349 }
350
351 pub fn new(curves: &[Bezier], is_closed: bool, style: &StrokeStyle) -> Option<Self> {
352 if curves.is_empty() {
353 return None;
354 }
355
356 let mut outline = Self { curves: Vec::new(), second_outline_index: None };
357
358 let dist = style.thickness / 2.0;
359
360 if !is_closed {
361 outline.join_curves(
362 curves.iter().map(|curve| curve.offset(dist)),
363 dist,
364 style.join,
365 is_closed,
366 );
367
368 let mut flipside_curves =
369 curves.iter().rev().map(|curve| curve.offset(-dist)).peekable();
370
371 let (last_ray, first_ray) = outline.last_first_ray(flipside_curves.peek().unwrap());
372 outline.cap_end(&last_ray, &first_ray, dist, style.cap);
373
374 outline.join_curves(flipside_curves, dist, style.join, is_closed);
375
376 let (last_ray, first_ray) = outline.last_first_ray(&outline.curves);
377 outline.cap_end(&last_ray, &first_ray, dist, style.cap);
378 } else {
379 outline.join_curves(
380 curves.iter().map(|curve| curve.offset(dist)),
381 dist,
382 style.join,
383 is_closed,
384 );
385 outline.second_outline_index = Some(outline.curves.len());
386 outline.join_curves(
387 curves.iter().rev().map(|curve| curve.offset(-dist)),
388 dist,
389 style.join,
390 is_closed,
391 );
392 }
393
394 Some(outline)
395 }
396
397 pub fn as_commands(&self) -> impl Iterator<Item = Command> + '_ {
398 let mid_move =
399 self.second_outline_index.map(|i| Command::MoveTo(self.curves[i].points()[0]));
400 let as_commands = |curve: &Bezier| match *curve {
401 Bezier::Line([_, p1]) => Command::LineTo(p1),
402 Bezier::Cubic([_, p1, p2, p3]) => Command::CubicTo(p1, p2, p3),
403 };
404
405 iter::once(Command::MoveTo(self.curves[0].points()[0]))
406 .chain(
407 self.curves[..self.second_outline_index.unwrap_or_default()]
408 .iter()
409 .map(as_commands),
410 )
411 .chain(self.second_outline_index.map(|_| Command::Close))
412 .chain(mid_move)
413 .chain(
414 self.curves[self.second_outline_index.unwrap_or_default()..]
415 .iter()
416 .map(as_commands),
417 )
418 .chain(iter::once(Command::Close))
419 }
420}