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