1 | use std::{cmp::Ordering, f32::consts::PI, ops::Range}; |
2 | |
3 | use bitflags::bitflags; |
4 | |
5 | use crate::{ |
6 | geometry::{Bounds, Position, Transform2D, Vector}, |
7 | renderer::Vertex, |
8 | utils::VecRetainMut, |
9 | FillRule, LineCap, LineJoin, Solidity, |
10 | }; |
11 | |
12 | use super::Verb; |
13 | |
14 | bitflags! { |
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)] |
25 | pub struct Point { |
26 | pos: Position, |
27 | dpos: Vector, |
28 | len: f32, |
29 | dmpos: Vector, |
30 | flags: PointFlags, |
31 | } |
32 | |
33 | impl 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)] |
53 | pub enum Convexity { |
54 | Concave, |
55 | Convex, |
56 | Unknown, |
57 | } |
58 | |
59 | impl Default for Convexity { |
60 | fn default() -> Self { |
61 | Self::Unknown |
62 | } |
63 | } |
64 | |
65 | #[derive (Clone, Debug)] |
66 | pub 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 | |
76 | impl 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 | |
90 | impl 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 | |
113 | struct PointPairsIter<'a> { |
114 | curr: usize, |
115 | points: &'a [Point], |
116 | } |
117 | |
118 | impl<'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)] |
137 | pub struct PathCache { |
138 | pub(crate) contours: Vec<Contour>, |
139 | pub(crate) bounds: Bounds, |
140 | points: Vec<Point>, |
141 | } |
142 | |
143 | impl 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 | |
899 | fn 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)] |
906 | fn 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)] |
917 | fn 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 | |
927 | fn 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 | |
943 | fn 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 | |
959 | fn 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)] |
969 | fn 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)] |
1030 | fn 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)] |
1092 | mod 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 | /* |
1118 | pub struct MutStridedChunks<'a, T: 'a> { |
1119 | buffer: &'a mut [T], |
1120 | rotated: bool, |
1121 | pos: usize, |
1122 | } |
1123 | |
1124 | impl<'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 | |
1155 | fn 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 | |