1use std::{cmp::Ordering, f32::consts::PI, ops::Range};
2
3use bitflags::bitflags;
4
5use crate::{
6 geometry::{Bounds, Position, Transform2D, Vector},
7 renderer::Vertex,
8 utils::VecRetainMut,
9 FillRule, LineCap, LineJoin, Solidity,
10};
11
12use super::Verb;
13
14bitflags! {
15 #[derive(Default, Clone, Copy, Debug, PartialEq, Eq, Hash)]
16 pub struct PointFlags: u8 {
17 const CORNER = 0x01;
18 const LEFT = 0x02;
19 const BEVEL = 0x04;
20 const INNERBEVEL = 0x08;
21 }
22}
23
24#[derive(Copy, Clone, Debug, Default)]
25pub struct Point {
26 pos: Position,
27 dpos: Vector,
28 len: f32,
29 dmpos: Vector,
30 flags: PointFlags,
31}
32
33impl Point {
34 pub fn new(x: f32, y: f32, flags: PointFlags) -> Self {
35 Self {
36 pos: Position { x, y },
37 flags,
38 ..Default::default()
39 }
40 }
41
42 pub fn is_left(p0: &Self, p1: &Self, x: f32, y: f32) -> f32 {
43 let pos: Position = Position { x, y };
44 (p1.pos - p0.pos).dot((pos - p0.pos).orthogonal())
45 }
46
47 pub fn approx_eq(&self, other: &Self, tolerance: f32) -> bool {
48 (other.pos - self.pos).mag2() < tolerance * tolerance
49 }
50}
51
52#[derive(Copy, Clone, Debug, Eq, PartialEq)]
53pub enum Convexity {
54 Concave,
55 Convex,
56 Unknown,
57}
58
59impl Default for Convexity {
60 fn default() -> Self {
61 Self::Unknown
62 }
63}
64
65#[derive(Clone, Debug)]
66pub struct Contour {
67 point_range: Range<usize>,
68 closed: bool,
69 bevel: usize,
70 solidity: Solidity,
71 pub(crate) fill: Vec<Vertex>,
72 pub(crate) stroke: Vec<Vertex>,
73 pub(crate) convexity: Convexity,
74}
75
76impl Default for Contour {
77 fn default() -> Self {
78 Self {
79 point_range: 0..0,
80 closed: Default::default(),
81 bevel: Default::default(),
82 solidity: Default::default(),
83 fill: Default::default(),
84 stroke: Default::default(),
85 convexity: Default::default(),
86 }
87 }
88}
89
90impl Contour {
91 fn point_pairs<'a>(&self, points: &'a [Point]) -> impl Iterator<Item = (&'a Point, &'a Point)> {
92 PointPairsIter {
93 curr: 0,
94 points: &points[self.point_range.clone()],
95 }
96 }
97
98 fn polygon_area(points: &[Point]) -> f32 {
99 let mut area: f32 = 0.0;
100
101 for (p0: &Point, p1: &Point) in (PointPairsIter { curr: 0, points }) {
102 area += (p1.pos.x - p0.pos.x) * (p1.pos.y + p0.pos.y);
103 }
104
105 area * 0.5
106 }
107
108 fn point_count(&self) -> usize {
109 self.point_range.end - self.point_range.start
110 }
111}
112
113struct PointPairsIter<'a> {
114 curr: usize,
115 points: &'a [Point],
116}
117
118impl<'a> Iterator for PointPairsIter<'a> {
119 type Item = (&'a Point, &'a Point);
120
121 fn next(&mut self) -> Option<Self::Item> {
122 let curr: Option<&Point> = self.points.get(self.curr);
123
124 let prev: Option<&Point> = if self.curr == 0 {
125 self.points.last()
126 } else {
127 self.points.get(self.curr - 1)
128 };
129
130 self.curr += 1;
131
132 curr.and_then(|some_curr: &Point| prev.map(|some_prev: &Point| (some_prev, some_curr)))
133 }
134}
135
136#[derive(Clone, Debug, Default)]
137pub struct PathCache {
138 pub(crate) contours: Vec<Contour>,
139 pub(crate) bounds: Bounds,
140 points: Vec<Point>,
141}
142
143impl PathCache {
144 pub fn new(verbs: impl Iterator<Item = Verb>, transform: &Transform2D, tess_tol: f32, dist_tol: f32) -> Self {
145 let mut cache = Self::default();
146
147 // Convert path verbs to a set of contours
148 for verb in verbs {
149 match verb {
150 Verb::MoveTo(x, y) => {
151 cache.add_contour();
152 let (x, y) = transform.transform_point(x, y);
153 cache.add_point(x, y, PointFlags::CORNER, dist_tol);
154 }
155 Verb::LineTo(x, y) => {
156 let (x, y) = transform.transform_point(x, y);
157 cache.add_point(x, y, PointFlags::CORNER, dist_tol);
158 }
159 Verb::BezierTo(c1x, c1y, c2x, c2y, x, y) => {
160 if let Some(last) = cache.points.last().copied() {
161 let (c1x, c1y) = transform.transform_point(c1x, c1y);
162 let (c2x, c2y) = transform.transform_point(c2x, c2y);
163 let (x, y) = transform.transform_point(x, y);
164
165 cache.tesselate_bezier(
166 last.pos.x,
167 last.pos.y,
168 c1x,
169 c1y,
170 c2x,
171 c2y,
172 x,
173 y,
174 0,
175 PointFlags::CORNER,
176 tess_tol,
177 dist_tol,
178 );
179
180 // cache.tesselate_bezier_afd(
181 // last.pos.x,
182 // last.pos.y,
183 // c1x,
184 // c1y,
185 // c2x,
186 // c2y,
187 // x,
188 // y,
189 // PointFlags::CORNER,
190 // tess_tol,
191 // dist_tol,
192 // );
193 }
194 }
195 Verb::Close => {
196 if let Some(contour) = cache.contours.last_mut() {
197 contour.closed = true;
198 }
199 }
200 Verb::Solid => {
201 if let Some(contour) = cache.contours.last_mut() {
202 contour.solidity = Solidity::Solid;
203 }
204 }
205 Verb::Hole => {
206 if let Some(contour) = cache.contours.last_mut() {
207 contour.solidity = Solidity::Hole;
208 }
209 }
210 }
211 }
212
213 let all_points = &mut cache.points;
214 let bounds = &mut cache.bounds;
215
216 VecRetainMut::retain_mut(&mut cache.contours, |contour| {
217 let mut points = &mut all_points[contour.point_range.clone()];
218
219 // If the first and last points are the same, remove the last, mark as closed contour.
220 if let (Some(p0), Some(p1)) = (points.last(), points.first()) {
221 if p0.approx_eq(p1, dist_tol) {
222 contour.point_range.end -= 1;
223 contour.closed = true;
224 points = &mut all_points[contour.point_range.clone()];
225 }
226 }
227
228 if points.len() < 2 {
229 return false;
230 }
231
232 // Enforce solidity by reversing the winding.
233 let area = Contour::polygon_area(points);
234
235 if contour.solidity == Solidity::Solid && area < 0.0 {
236 points.reverse();
237 }
238
239 if contour.solidity == Solidity::Hole && area > 0.0 {
240 points.reverse();
241 }
242
243 for i in 0..contour.point_count() {
244 let p1 = points.get(i).copied().unwrap();
245
246 let p0 = if i == 0 {
247 points.last_mut().unwrap()
248 } else {
249 points.get_mut(i - 1).unwrap()
250 };
251
252 p0.dpos = p1.pos - p0.pos;
253 p0.len = p0.dpos.normalize();
254
255 bounds.minx = bounds.minx.min(p0.pos.x);
256 bounds.miny = bounds.miny.min(p0.pos.y);
257 bounds.maxx = bounds.maxx.max(p0.pos.x);
258 bounds.maxy = bounds.maxy.max(p0.pos.y);
259 }
260
261 true
262 });
263
264 cache
265 }
266
267 fn add_contour(&mut self) {
268 let mut contour = Contour::default();
269
270 contour.point_range.start = self.points.len();
271 contour.point_range.end = self.points.len();
272
273 self.contours.push(contour);
274 }
275
276 fn add_point(&mut self, x: f32, y: f32, flags: PointFlags, dist_tol: f32) {
277 if let Some(contour) = self.contours.last_mut() {
278 let new_point = Point::new(x, y, flags);
279
280 // If last point equals this new point just OR the flags and ignore the new point
281 if let Some(last_point) = self.points.get_mut(contour.point_range.end) {
282 if last_point.approx_eq(&new_point, dist_tol) {
283 last_point.flags |= new_point.flags;
284 return;
285 }
286 }
287
288 self.points.push(new_point);
289 contour.point_range.end += 1;
290 }
291 }
292
293 #[allow(clippy::too_many_arguments)]
294 fn tesselate_bezier(
295 &mut self,
296 x1: f32,
297 y1: f32,
298 x2: f32,
299 y2: f32,
300 x3: f32,
301 y3: f32,
302 x4: f32,
303 y4: f32,
304 level: usize,
305 flags: PointFlags,
306 tess_tol: f32,
307 dist_tol: f32,
308 ) {
309 if level > 10 {
310 return;
311 }
312
313 let x12 = (x1 + x2) * 0.5;
314 let y12 = (y1 + y2) * 0.5;
315 let x23 = (x2 + x3) * 0.5;
316 let y23 = (y2 + y3) * 0.5;
317 let x34 = (x3 + x4) * 0.5;
318 let y34 = (y3 + y4) * 0.5;
319 let x123 = (x12 + x23) * 0.5;
320 let y123 = (y12 + y23) * 0.5;
321
322 let dx = x4 - x1;
323 let dy = y4 - y1;
324 let d2 = ((x2 - x4) * dy - (y2 - y4) * dx).abs();
325 let d3 = ((x3 - x4) * dy - (y3 - y4) * dx).abs();
326
327 if (d2 + d3) * (d2 + d3) < tess_tol * (dx * dx + dy * dy) {
328 self.add_point(x4, y4, flags, dist_tol);
329 return;
330 }
331
332 let x234 = (x23 + x34) * 0.5;
333 let y234 = (y23 + y34) * 0.5;
334 let x1234 = (x123 + x234) * 0.5;
335 let y1234 = (y123 + y234) * 0.5;
336
337 self.tesselate_bezier(
338 x1,
339 y1,
340 x12,
341 y12,
342 x123,
343 y123,
344 x1234,
345 y1234,
346 level + 1,
347 PointFlags::empty(),
348 tess_tol,
349 dist_tol,
350 );
351 self.tesselate_bezier(
352 x1234,
353 y1234,
354 x234,
355 y234,
356 x34,
357 y34,
358 x4,
359 y4,
360 level + 1,
361 flags,
362 tess_tol,
363 dist_tol,
364 );
365 }
366
367 // fn tesselate_bezier_afd(
368 // &mut self,
369 // x1: f32,
370 // y1: f32,
371 // x2: f32,
372 // y2: f32,
373 // x3: f32,
374 // y3: f32,
375 // x4: f32,
376 // y4: f32,
377 // flags: PointFlags,
378 // tess_tol: f32,
379 // dist_tol: f32,
380 // ) {
381 // let ax = -x1 + 3.*x2 - 3.*x3 + x4;
382 // let ay = -y1 + 3.*y2 - 3.*y3 + y4;
383 // let bx = 3.*x1 - 6.*x2 + 3.*x3;
384 // let by = 3.*y1 - 6.*y2 + 3.*y3;
385 // let cx = -3.*x1 + 3.*x2;
386 // let cy = -3.*y1 + 3.*y2;
387
388 // // Transform to forward difference basis (stepsize 1)
389 // let mut px = x1;
390 // let mut py = y1;
391 // let mut dx = ax + bx + cx;
392 // let mut dy = ay + by + cy;
393 // let mut ddx = 6.*ax + 2.*bx;
394 // let mut ddy = 6.*ay + 2.*by;
395 // let mut dddx = 6.*ax;
396 // let mut dddy = 6.*ay;
397
398 // //printf("dx: %f, dy: %f\n", dx, dy);
399 // //printf("ddx: %f, ddy: %f\n", ddx, ddy);
400 // //printf("dddx: %f, dddy: %f\n", dddx, dddy);
401
402 // const AFD_ONE: i32 = 1<<10;
403
404 // let mut t = 0;
405 // let mut dt = AFD_ONE;
406
407 // let tol = tess_tol * 4.0;
408
409 // while t < AFD_ONE {
410
411 // // Flatness measure.
412 // let mut d = ddx*ddx + ddy*ddy + dddx*dddx + dddy*dddy;
413
414 // // Go to higher resolution if we're moving a lot
415 // // or overshooting the end.
416 // while (d > tol && dt > 1) || (t+dt > AFD_ONE) {
417
418 // // Apply L to the curve. Increase curve resolution.
419 // dx = 0.5 * dx - (1.0/8.0)*ddx + (1.0/16.0)*dddx;
420 // dy = 0.5 * dy - (1.0/8.0)*ddy + (1.0/16.0)*dddy;
421 // ddx = (1.0/4.0) * ddx - (1.0/8.0) * dddx;
422 // ddy = (1.0/4.0) * ddy - (1.0/8.0) * dddy;
423 // dddx = (1.0/8.0) * dddx;
424 // dddy = (1.0/8.0) * dddy;
425
426 // // Half the stepsize.
427 // dt >>= 1;
428
429 // // Recompute d
430 // d = ddx*ddx + ddy*ddy + dddx*dddx + dddy*dddy;
431
432 // }
433
434 // // Go to lower resolution if we're really flat
435 // // and we aren't going to overshoot the end.
436 // // XXX: tol/32 is just a guess for when we are too flat.
437 // while (d > 0.0 && d < tol/32.0 && dt < AFD_ONE) && (t+2*dt <= AFD_ONE) {
438
439 // // printf("down\n");
440
441 // // Apply L^(-1) to the curve. Decrease curve resolution.
442 // dx = 2. * dx + ddx;
443 // dy = 2. * dy + ddy;
444 // ddx = 4. * ddx + 4. * dddx;
445 // ddy = 4. * ddy + 4. * dddy;
446 // dddx = 8. * dddx;
447 // dddy = 8. * dddy;
448
449 // // Double the stepsize.
450 // dt <<= 1;
451
452 // // Recompute d
453 // d = ddx*ddx + ddy*ddy + dddx*dddx + dddy*dddy;
454
455 // }
456
457 // // Forward differencing.
458 // px += dx;
459 // py += dy;
460 // dx += ddx;
461 // dy += ddy;
462 // ddx += dddx;
463 // ddy += dddy;
464
465 // // Output a point.
466 // self.add_point(px, py, flags, dist_tol);
467
468 // // Advance along the curve.
469 // t += dt;
470
471 // // Ensure we don't overshoot.
472 // debug_assert!(t <= AFD_ONE);
473
474 // }
475 // }
476
477 pub fn contains_point(&self, x: f32, y: f32, fill_rule: FillRule) -> bool {
478 // Early out if point is outside the bounding rectangle
479 if !self.bounds.contains(x, y) {
480 return false;
481 }
482
483 if fill_rule == FillRule::EvenOdd {
484 for contour in &self.contours {
485 let mut crossing = false;
486
487 for (p0, p1) in contour.point_pairs(&self.points) {
488 if (p1.pos.y > y) != (p0.pos.y > y)
489 && (x < (p0.pos.x - p1.pos.x) * (y - p1.pos.y) / (p0.pos.y - p1.pos.y) + p1.pos.x)
490 {
491 crossing = !crossing;
492 }
493 }
494
495 if crossing {
496 return true;
497 }
498 }
499
500 false
501 } else {
502 // NonZero
503 for contour in &self.contours {
504 let mut winding_number: i32 = 0;
505
506 for (p0, p1) in contour.point_pairs(&self.points) {
507 if p0.pos.y <= y {
508 if p1.pos.y > y && Point::is_left(p0, p1, x, y) > 0.0 {
509 winding_number = winding_number.wrapping_add(1);
510 }
511 } else if p1.pos.y <= y && Point::is_left(p0, p1, x, y) < 0.0 {
512 winding_number = winding_number.wrapping_sub(1);
513 }
514 }
515
516 if winding_number != 0 {
517 return true;
518 }
519 }
520
521 false
522 }
523 }
524
525 pub(crate) fn expand_fill(&mut self, fringe_width: f32, line_join: LineJoin, miter_limit: f32) {
526 let has_fringe = fringe_width > 0.0;
527
528 self.calculate_joins(fringe_width, line_join, miter_limit);
529
530 // Calculate max vertex usage.
531 for contour in &mut self.contours {
532 let point_count = contour.point_count();
533 let mut vertex_count = point_count + contour.bevel + 1;
534
535 if has_fringe {
536 vertex_count += (point_count + contour.bevel * 5 + 1) * 2;
537 contour.stroke.reserve(vertex_count);
538 }
539
540 contour.fill.reserve(vertex_count);
541 }
542
543 let convex = self.contours.len() == 1 && self.contours[0].convexity == Convexity::Convex;
544
545 for contour in &mut self.contours {
546 contour.stroke.clear();
547 contour.fill.clear();
548
549 // TODO: woff = 0.0 produces no artifaacts for small sizes
550 let woff = 0.5 * fringe_width;
551 //let woff = 0.0; // Makes everything thicker
552
553 if has_fringe {
554 for (p0, p1) in contour.point_pairs(&self.points) {
555 if p1.flags.contains(PointFlags::BEVEL) {
556 if p1.flags.contains(PointFlags::LEFT) {
557 let lpos = p1.pos + p1.dmpos * woff;
558 contour.fill.push(Vertex::pos(lpos, 0.5, 1.0));
559 } else {
560 let lpos0 = p1.pos + p0.dpos.orthogonal() * woff;
561 let lpos1 = p1.pos + p1.dpos.orthogonal() * woff;
562 contour.fill.push(Vertex::pos(lpos0, 0.5, 1.0));
563 contour.fill.push(Vertex::pos(lpos1, 0.5, 1.0));
564 }
565 } else {
566 contour.fill.push(Vertex::pos(p1.pos + p1.dmpos * woff, 0.5, 1.0));
567 }
568 }
569 } else {
570 let points = &self.points[contour.point_range.clone()];
571
572 for point in points {
573 contour.fill.push(Vertex::pos(point.pos, 0.5, 1.0));
574 }
575 }
576
577 if has_fringe {
578 let rw = fringe_width - woff;
579 let ru = 1.0;
580
581 let (lw, lu) = if convex {
582 // Create only half a fringe for convex shapes so that
583 // the shape can be rendered without stenciling.
584 (woff, 0.5)
585 } else {
586 (fringe_width + woff, 0.0)
587 };
588
589 for (p0, p1) in contour.point_pairs(&self.points) {
590 if p1.flags.contains(PointFlags::BEVEL | PointFlags::INNERBEVEL) {
591 bevel_join(&mut contour.stroke, p0, p1, lw, rw, lu, ru);
592 } else {
593 contour.stroke.push(Vertex::pos(p1.pos + p1.dmpos * lw, lu, 1.0));
594 contour.stroke.push(Vertex::pos(p1.pos - p1.dmpos * rw, ru, 1.0));
595 }
596 }
597
598 // Loop it
599 let p0 = contour.stroke[0];
600 let p1 = contour.stroke[1];
601 contour.stroke.push(Vertex::new(p0.x, p0.y, lu, 1.0));
602 contour.stroke.push(Vertex::new(p1.x, p1.y, ru, 1.0));
603 }
604 }
605 }
606
607 #[allow(clippy::too_many_arguments)]
608 pub(crate) fn expand_stroke(
609 &mut self,
610 stroke_width: f32,
611 fringe_width: f32,
612 line_cap_start: LineCap,
613 line_cap_end: LineCap,
614 line_join: LineJoin,
615 miter_limit: f32,
616 tess_tol: f32,
617 ) {
618 let ncap = curve_divisions(stroke_width, PI, tess_tol);
619
620 let stroke_width = stroke_width + (fringe_width * 0.5);
621
622 // Disable the gradient used for antialiasing when antialiasing is not enabled.
623 let (u0, u1) = if fringe_width == 0.0 { (0.5, 0.5) } else { (0.0, 1.0) };
624
625 self.calculate_joins(stroke_width, line_join, miter_limit);
626
627 for contour in &mut self.contours {
628 contour.stroke.clear();
629
630 for (i, (p0, p1)) in contour.point_pairs(&self.points).enumerate() {
631 // Add start cap
632 if !contour.closed && i == 1 {
633 match line_cap_start {
634 LineCap::Butt => butt_cap_start(
635 &mut contour.stroke,
636 p0,
637 p0,
638 stroke_width,
639 -fringe_width * 0.5,
640 fringe_width,
641 u0,
642 u1,
643 ),
644 LineCap::Square => butt_cap_start(
645 &mut contour.stroke,
646 p0,
647 p0,
648 stroke_width,
649 stroke_width - fringe_width,
650 fringe_width,
651 u0,
652 u1,
653 ),
654 LineCap::Round => {
655 round_cap_start(&mut contour.stroke, p0, p0, stroke_width, ncap as usize, u0, u1)
656 }
657 }
658 }
659
660 if (i > 0 && i < contour.point_count() - 1) || contour.closed {
661 if p1.flags.contains(PointFlags::BEVEL) || p1.flags.contains(PointFlags::INNERBEVEL) {
662 if line_join == LineJoin::Round {
663 round_join(
664 &mut contour.stroke,
665 p0,
666 p1,
667 stroke_width,
668 stroke_width,
669 u0,
670 u1,
671 ncap as usize,
672 );
673 } else {
674 bevel_join(&mut contour.stroke, p0, p1, stroke_width, stroke_width, u0, u1);
675 }
676 } else {
677 contour
678 .stroke
679 .push(Vertex::pos(p1.pos + p1.dmpos * stroke_width, u0, 1.0));
680 contour
681 .stroke
682 .push(Vertex::pos(p1.pos - p1.dmpos * stroke_width, u1, 1.0));
683 }
684 }
685
686 // Add end cap
687 if !contour.closed && i == contour.point_count() - 1 {
688 match line_cap_end {
689 LineCap::Butt => butt_cap_end(
690 &mut contour.stroke,
691 p1,
692 p0,
693 stroke_width,
694 -fringe_width * 0.5,
695 fringe_width,
696 u0,
697 u1,
698 ),
699 LineCap::Square => butt_cap_end(
700 &mut contour.stroke,
701 p1,
702 p0,
703 stroke_width,
704 stroke_width - fringe_width,
705 fringe_width,
706 u0,
707 u1,
708 ),
709 LineCap::Round => {
710 round_cap_end(&mut contour.stroke, p1, p0, stroke_width, ncap as usize, u0, u1)
711 }
712 }
713 }
714 }
715
716 if contour.closed {
717 contour
718 .stroke
719 .push(Vertex::new(contour.stroke[0].x, contour.stroke[0].y, u0, 1.0));
720 contour
721 .stroke
722 .push(Vertex::new(contour.stroke[1].x, contour.stroke[1].y, u1, 1.0));
723 }
724 }
725 }
726
727 fn calculate_joins(&mut self, stroke_width: f32, line_join: LineJoin, miter_limit: f32) {
728 let inv_stroke_width = if stroke_width > 0.0 { 1.0 / stroke_width } else { 0.0 };
729
730 for contour in &mut self.contours {
731 let points = &mut self.points[contour.point_range.clone()];
732 let mut nleft = 0;
733
734 contour.bevel = 0;
735
736 let mut x_sign = 0;
737 let mut y_sign = 0;
738 let mut x_first_sign = 0; // Sign of first nonzero edge vector x
739 let mut y_first_sign = 0; // Sign of first nonzero edge vector y
740 let mut x_flips = 0; // Number of sign changes in x
741 let mut y_flips = 0; // Number of sign changes in y
742
743 for i in 0..points.len() {
744 let p0 = if i == 0 {
745 points.last().copied().unwrap()
746 } else {
747 points.get(i - 1).copied().unwrap()
748 };
749
750 let p1 = points.get_mut(i).unwrap();
751
752 let dlpos0 = p0.dpos.orthogonal();
753 let dlpos1 = p1.dpos.orthogonal();
754
755 // Calculate extrusions
756 p1.dmpos = (dlpos0 + dlpos1) * 0.5;
757 let dmr2 = p1.dmpos.mag2();
758
759 if dmr2 > 0.000_001 {
760 let scale = (1.0 / dmr2).min(600.0);
761
762 p1.dmpos *= scale;
763 }
764
765 // Clear flags, but keep the corner.
766 p1.flags = if p1.flags.contains(PointFlags::CORNER) {
767 PointFlags::CORNER
768 } else {
769 PointFlags::empty()
770 };
771
772 // Keep track of left turns.
773 let cross = p0.dpos.cross(p1.dpos);
774
775 if cross > 0.0 {
776 nleft += 1;
777 p1.flags |= PointFlags::LEFT;
778 }
779
780 // Determine sign for convexity
781 match p1.dpos.x.partial_cmp(&0.0) {
782 Some(Ordering::Greater) => {
783 match x_sign.cmp(&0) {
784 Ordering::Equal => x_first_sign = 1,
785 Ordering::Less => x_flips += 1,
786 _ => (),
787 }
788
789 x_sign = 1;
790 }
791 Some(Ordering::Less) => {
792 match x_sign.cmp(&0) {
793 Ordering::Equal => x_first_sign = -1,
794 Ordering::Greater => x_flips += 1,
795 _ => (),
796 }
797
798 x_sign = -1;
799 }
800 _ => (),
801 }
802
803 match p1.dpos.y.partial_cmp(&0.0) {
804 Some(Ordering::Greater) => {
805 match y_sign.cmp(&0) {
806 Ordering::Equal => y_first_sign = 1,
807 Ordering::Less => y_flips += 1,
808 _ => (),
809 }
810
811 y_sign = 1;
812 }
813 Some(Ordering::Less) => {
814 match y_sign.cmp(&0) {
815 Ordering::Equal => y_first_sign = -1,
816 Ordering::Greater => y_flips += 1,
817 _ => (),
818 }
819
820 y_sign = -1;
821 }
822 _ => (),
823 }
824
825 // Calculate if we should use bevel or miter for inner join.
826 let limit = (p0.len.min(p1.len) * inv_stroke_width).max(1.01);
827
828 if (dmr2 * limit * limit) < 1.0 {
829 p1.flags |= PointFlags::INNERBEVEL;
830 }
831
832 #[allow(clippy::collapsible_if)]
833 // Check to see if the corner needs to be beveled.
834 if p1.flags.contains(PointFlags::CORNER) {
835 if (dmr2 * miter_limit * miter_limit) < 1.0
836 || line_join == LineJoin::Bevel
837 || line_join == LineJoin::Round
838 {
839 p1.flags |= PointFlags::BEVEL;
840 }
841 }
842
843 if p1.flags.contains(PointFlags::BEVEL | PointFlags::INNERBEVEL) {
844 contour.bevel += 1;
845 }
846 }
847
848 if x_sign != 0 && x_first_sign != 0 && x_sign != x_first_sign {
849 x_flips += 1;
850 }
851
852 if y_sign != 0 && y_first_sign != 0 && y_sign != y_first_sign {
853 y_flips += 1;
854 }
855
856 let convex = x_flips == 2 && y_flips == 2;
857
858 contour.convexity = if nleft == points.len() && convex {
859 Convexity::Convex
860 } else {
861 Convexity::Concave
862 };
863 }
864 }
865
866 /// If this path is merely a rectangle, return it
867 pub(crate) fn path_fill_is_rect(&self) -> Option<crate::Rect> {
868 if self.contours.len() != 1 {
869 return None;
870 }
871
872 let vertices = &self.contours[0].fill;
873 if vertices.len() != 4 {
874 return None;
875 }
876
877 let maybe_top_left = vertices[0];
878 let maybe_bottom_left = vertices[1];
879 let maybe_bottom_right = vertices[2];
880 let maybe_top_right = vertices[3];
881
882 if maybe_top_left.x == maybe_bottom_left.x
883 && maybe_top_left.y == maybe_top_right.y
884 && maybe_bottom_right.x == maybe_top_right.x
885 && maybe_bottom_right.y == maybe_bottom_left.y
886 {
887 Some(crate::Rect::new(
888 maybe_top_left.x,
889 maybe_top_left.y,
890 maybe_top_right.x - maybe_top_left.x,
891 maybe_bottom_left.y - maybe_top_left.y,
892 ))
893 } else {
894 None
895 }
896 }
897}
898
899fn curve_divisions(radius: f32, arc: f32, tol: f32) -> u32 {
900 let da: f32 = (radius / (radius + tol)).acos() * 2.0;
901
902 ((arc / da).ceil() as u32).max(2)
903}
904
905#[allow(clippy::too_many_arguments)]
906fn butt_cap_start(verts: &mut Vec<Vertex>, p0: &Point, p1: &Point, w: f32, d: f32, aa: f32, u0: f32, u1: f32) {
907 let ppos: Position = p0.pos - p1.dpos * d;
908 let dlpos: Vector = p1.dpos.orthogonal();
909
910 verts.push(Vertex::pos(position:ppos + dlpos * w - p1.dpos * aa, u:u0, v:0.0));
911 verts.push(Vertex::pos(position:ppos - dlpos * w - p1.dpos * aa, u:u1, v:0.0));
912 verts.push(Vertex::pos(position:ppos + dlpos * w, u:u0, v:1.0));
913 verts.push(Vertex::pos(position:ppos - dlpos * w, u:u1, v:1.0));
914}
915
916#[allow(clippy::too_many_arguments)]
917fn butt_cap_end(verts: &mut Vec<Vertex>, p0: &Point, p1: &Point, w: f32, d: f32, aa: f32, u0: f32, u1: f32) {
918 let ppos: Position = p0.pos + p1.dpos * d;
919 let dlpos: Vector = p1.dpos.orthogonal();
920
921 verts.push(Vertex::pos(position:ppos + dlpos * w, u:u0, v:1.0));
922 verts.push(Vertex::pos(position:ppos - dlpos * w, u:u1, v:1.0));
923 verts.push(Vertex::pos(position:ppos + dlpos * w + p1.dpos * aa, u:u0, v:0.0));
924 verts.push(Vertex::pos(position:ppos - dlpos * w + p1.dpos * aa, u:u1, v:0.0));
925}
926
927fn round_cap_start(verts: &mut Vec<Vertex>, p0: &Point, p1: &Point, w: f32, ncap: usize, u0: f32, u1: f32) {
928 let ppos: Position = p0.pos;
929 let dlpos: Vector = p1.dpos.orthogonal();
930
931 for i: usize in 0..ncap {
932 let a: f32 = i as f32 / (ncap as f32 - 1.0) * PI;
933 let offset: Vector = Vector::from_angle(a).with_basis(-dlpos, -p1.dpos) * w;
934
935 verts.push(Vertex::pos(position:ppos + offset, u:u0, v:1.0));
936 verts.push(Vertex::pos(position:ppos, u:0.5, v:1.0));
937 }
938
939 verts.push(Vertex::pos(position:ppos + dlpos * w, u:u0, v:1.0));
940 verts.push(Vertex::pos(position:ppos - dlpos * w, u:u1, v:1.0));
941}
942
943fn round_cap_end(verts: &mut Vec<Vertex>, p0: &Point, p1: &Point, w: f32, ncap: usize, u0: f32, u1: f32) {
944 let ppos: Position = p0.pos;
945 let dlpos: Vector = p1.dpos.orthogonal();
946
947 verts.push(Vertex::pos(position:ppos + dlpos * w, u:u0, v:1.0));
948 verts.push(Vertex::pos(position:ppos - dlpos * w, u:u1, v:1.0));
949
950 for i: usize in 0..ncap {
951 let a: f32 = i as f32 / (ncap as f32 - 1.0) * PI;
952 let offset: Vector = Vector::from_angle(a).with_basis(-dlpos, basis_y:p1.dpos) * w;
953
954 verts.push(Vertex::pos(position:ppos, u:0.5, v:1.0));
955 verts.push(Vertex::pos(position:ppos + offset, u:u0, v:1.0));
956 }
957}
958
959fn choose_bevel(bevel: bool, p0: &Point, p1: &Point, w: f32) -> (Position, Position) {
960 if bevel {
961 (p1.pos + p0.dpos.orthogonal() * w, p1.pos + p1.dpos.orthogonal() * w)
962 } else {
963 let pos: Position = p1.pos + p1.dmpos * w;
964 (pos, pos)
965 }
966}
967
968#[allow(clippy::too_many_arguments)]
969fn round_join(verts: &mut Vec<Vertex>, p0: &Point, p1: &Point, lw: f32, rw: f32, lu: f32, ru: f32, ncap: usize) {
970 let dlpos0 = p0.dpos.orthogonal();
971 let dlpos1 = p1.dpos.orthogonal();
972
973 let a0;
974 let mut a1;
975
976 if p1.flags.contains(PointFlags::LEFT) {
977 let (lpos0, lpos1) = choose_bevel(p1.flags.contains(PointFlags::INNERBEVEL), p0, p1, lw);
978 a0 = (-dlpos0).angle();
979 a1 = (-dlpos1).angle();
980
981 if a1 > a0 {
982 a1 -= PI * 2.0;
983 }
984
985 verts.push(Vertex::pos(lpos0, lu, 1.0));
986 verts.push(Vertex::pos(p1.pos - dlpos0 * rw, ru, 1.0));
987
988 let n = ((((a0 - a1) / PI) * ncap as f32).ceil() as usize).max(2).min(ncap);
989
990 for i in 0..n {
991 let u = i as f32 / (n - 1) as f32;
992 let a = a0 + u * (a1 - a0);
993 let rpos = p1.pos + Vector::from_angle(a) * rw;
994
995 verts.push(Vertex::pos(p1.pos, 0.5, 1.0));
996 verts.push(Vertex::pos(rpos, ru, 1.0));
997 }
998
999 verts.push(Vertex::pos(lpos1, lu, 1.0));
1000 verts.push(Vertex::pos(p1.pos - dlpos1 * rw, ru, 1.0));
1001 } else {
1002 let (rpos0, rpos1) = choose_bevel(p1.flags.contains(PointFlags::INNERBEVEL), p0, p1, -rw);
1003 a0 = dlpos0.angle();
1004 a1 = dlpos1.angle();
1005
1006 if a1 < a0 {
1007 a1 += PI * 2.0;
1008 }
1009
1010 verts.push(Vertex::pos(p1.pos + dlpos0 * rw, lu, 1.0));
1011 verts.push(Vertex::pos(rpos0, ru, 1.0));
1012
1013 let n = ((((a1 - a0) / PI) * ncap as f32).ceil() as usize).max(2).min(ncap);
1014
1015 for i in 0..n {
1016 let u = i as f32 / (n - 1) as f32;
1017 let a = a0 + u * (a1 - a0);
1018 let lpos = p1.pos + Vector::from_angle(a) * lw;
1019
1020 verts.push(Vertex::pos(lpos, lu, 1.0));
1021 verts.push(Vertex::pos(p1.pos, 0.5, 1.0));
1022 }
1023
1024 verts.push(Vertex::pos(p1.pos + dlpos1 * rw, lu, 1.0));
1025 verts.push(Vertex::pos(rpos1, ru, 1.0));
1026 }
1027}
1028
1029#[allow(clippy::branches_sharing_code)]
1030fn bevel_join(verts: &mut Vec<Vertex>, p0: &Point, p1: &Point, lw: f32, rw: f32, lu: f32, ru: f32) {
1031 let dlpos0 = p0.dpos.orthogonal();
1032 let dlpos1 = p1.dpos.orthogonal();
1033
1034 if p1.flags.contains(PointFlags::LEFT) {
1035 let (lpos0, lpos1) = choose_bevel(p1.flags.contains(PointFlags::INNERBEVEL), p0, p1, lw);
1036
1037 verts.push(Vertex::pos(lpos0, lu, 1.0));
1038 verts.push(Vertex::pos(p1.pos - dlpos0 * rw, ru, 1.0));
1039
1040 if p1.flags.contains(PointFlags::BEVEL) {
1041 verts.push(Vertex::pos(lpos0, lu, 1.0));
1042 verts.push(Vertex::pos(p1.pos - dlpos0 * rw, ru, 1.0));
1043
1044 verts.push(Vertex::pos(lpos1, lu, 1.0));
1045 verts.push(Vertex::pos(p1.pos - dlpos1 * rw, ru, 1.0));
1046 } else {
1047 let rpos0 = p1.pos - p1.dmpos * rw;
1048
1049 verts.push(Vertex::pos(p1.pos, 0.5, 1.0));
1050 verts.push(Vertex::pos(p1.pos - dlpos0 * rw, ru, 1.0));
1051
1052 verts.push(Vertex::pos(rpos0, ru, 1.0));
1053 verts.push(Vertex::pos(rpos0, ru, 1.0));
1054
1055 verts.push(Vertex::pos(p1.pos, 0.5, 1.0));
1056 verts.push(Vertex::pos(p1.pos - dlpos1 * rw, ru, 1.0));
1057 }
1058
1059 verts.push(Vertex::pos(lpos1, lu, 1.0));
1060 verts.push(Vertex::pos(p1.pos - dlpos1 * rw, ru, 1.0));
1061 } else {
1062 let (rpos0, rpos1) = choose_bevel(p1.flags.contains(PointFlags::INNERBEVEL), p0, p1, -rw);
1063
1064 verts.push(Vertex::pos(p1.pos + dlpos0 * lw, lu, 1.0));
1065 verts.push(Vertex::pos(rpos0, ru, 1.0));
1066
1067 if p1.flags.contains(PointFlags::BEVEL) {
1068 verts.push(Vertex::pos(p1.pos + dlpos0 * lw, lu, 1.0));
1069 verts.push(Vertex::pos(rpos0, ru, 1.0));
1070
1071 verts.push(Vertex::pos(p1.pos + dlpos1 * lw, lu, 1.0));
1072 verts.push(Vertex::pos(rpos1, ru, 1.0));
1073 } else {
1074 let lpos0 = p1.pos + p1.dmpos * lw;
1075
1076 verts.push(Vertex::pos(p1.pos + dlpos0 * lw, lu, 1.0));
1077 verts.push(Vertex::pos(p1.pos, 0.5, 1.0));
1078
1079 verts.push(Vertex::pos(lpos0, lu, 1.0));
1080 verts.push(Vertex::pos(lpos0, lu, 1.0));
1081
1082 verts.push(Vertex::pos(p1.pos + dlpos1 * lw, lu, 1.0));
1083 verts.push(Vertex::pos(p1.pos, 0.5, 1.0));
1084 }
1085
1086 verts.push(Vertex::pos(p1.pos + dlpos1 * lw, lu, 1.0));
1087 verts.push(Vertex::pos(rpos1, ru, 1.0));
1088 }
1089}
1090
1091#[cfg(test)]
1092mod tests {
1093
1094 use super::*;
1095 use crate::Path;
1096
1097 #[test]
1098 fn self_intersecting_polygon_is_concave() {
1099 // star
1100 let mut path = Path::new();
1101 path.move_to(50.0, 0.0);
1102 path.line_to(21.0, 90.0);
1103 path.line_to(98.0, 35.0);
1104 path.line_to(2.0, 35.0);
1105 path.line_to(79.0, 90.0);
1106 path.close();
1107
1108 let transform = Transform2D::identity();
1109
1110 let mut path_cache = PathCache::new(path.verbs(), &transform, 0.25, 0.01);
1111 path_cache.expand_fill(1.0, LineJoin::Miter, 10.0);
1112
1113 assert_eq!(path_cache.contours[0].convexity, Convexity::Concave);
1114 }
1115}
1116
1117/*
1118pub struct MutStridedChunks<'a, T: 'a> {
1119 buffer: &'a mut [T],
1120 rotated: bool,
1121 pos: usize,
1122}
1123
1124impl<'a, T: 'a> MutStridedChunks<'a, T> {
1125 pub fn new(buffer: &'a mut [T]) -> Self {
1126 buffer.rotate_right(1);
1127 Self {
1128 buffer: buffer,
1129 rotated: false,
1130 pos: 0
1131 }
1132 }
1133
1134 fn next(&mut self) -> Option<&mut [T]> {
1135 if self.pos == self.buffer.len() - 1 && !self.rotated {
1136 self.buffer.rotate_left(1);
1137 self.rotated = true;
1138 self.pos -= 1;
1139 }
1140
1141 let len = self.buffer.len() - self.pos;
1142
1143 if 2 <= len {
1144 let (start, end) = (self.pos, self.pos + 2);
1145 let subslice = &mut self.buffer[start..end];
1146
1147 self.pos += 1;
1148 Some(subslice)
1149 } else {
1150 None
1151 }
1152 }
1153}
1154
1155fn main() {
1156 let mut my_array = [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19];
1157
1158 let mut iter = MutStridedChunks::new(&mut my_array);
1159
1160 while let Some(subslice) = iter.next() {
1161 log::info!("{:?}", subslice);
1162 }
1163}
1164*/
1165