1// Copyright 2006 The Android Open Source Project
2// Copyright 2020 Yevhenii Reizner
3//
4// Use of this source code is governed by a BSD-style license that can be
5// found in the LICENSE file.
6
7use core::convert::TryInto;
8
9use tiny_skia_path::{f32x2, PathVerb, SaturateCast, Scalar};
10
11use crate::{IntRect, LineCap, Path, PathSegment, Point, Rect};
12
13use crate::blitter::Blitter;
14use crate::fixed_point::{fdot16, fdot6};
15use crate::geom::ScreenIntRect;
16use crate::line_clipper;
17use crate::math::LENGTH_U32_ONE;
18use crate::path_geometry;
19
20#[cfg(all(not(feature = "std"), feature = "no-std-float"))]
21use tiny_skia_path::NoStdFloat;
22
23const FLOAT_PI: f32 = 3.14159265;
24
25pub type LineProc = fn(&[Point], Option<&ScreenIntRect>, &mut dyn Blitter);
26
27const MAX_CUBIC_SUBDIVIDE_LEVEL: u8 = 9;
28const MAX_QUAD_SUBDIVIDE_LEVEL: u8 = 5;
29
30pub fn stroke_path(
31 path: &Path,
32 line_cap: LineCap,
33 clip: &ScreenIntRect,
34 blitter: &mut dyn Blitter,
35) {
36 super::hairline::stroke_path_impl(path, line_cap, clip, line_proc:hair_line_rgn, blitter)
37}
38
39fn hair_line_rgn(points: &[Point], clip: Option<&ScreenIntRect>, blitter: &mut dyn Blitter) {
40 let max = 32767.0;
41 let fixed_bounds = Rect::from_ltrb(-max, -max, max, max).unwrap();
42
43 let clip_bounds = clip.map(|c| c.to_rect());
44
45 for i in 0..points.len() - 1 {
46 let mut pts = [Point::zero(); 2];
47
48 // We have to pre-clip the line to fit in a Fixed, so we just chop the line.
49 if !line_clipper::intersect(&[points[i], points[i + 1]], &fixed_bounds, &mut pts) {
50 continue;
51 }
52
53 if let Some(clip_bounds) = clip_bounds {
54 let tmp = pts.clone();
55 // Perform a clip in scalar space, so we catch huge values which might
56 // be missed after we convert to FDot6 (overflow).
57 if !line_clipper::intersect(&tmp, &clip_bounds, &mut pts) {
58 continue;
59 }
60 }
61
62 let mut x0 = fdot6::from_f32(pts[0].x);
63 let mut y0 = fdot6::from_f32(pts[0].y);
64 let mut x1 = fdot6::from_f32(pts[1].x);
65 let mut y1 = fdot6::from_f32(pts[1].y);
66
67 debug_assert!(fdot6::can_convert_to_fdot16(x0));
68 debug_assert!(fdot6::can_convert_to_fdot16(y0));
69 debug_assert!(fdot6::can_convert_to_fdot16(x1));
70 debug_assert!(fdot6::can_convert_to_fdot16(y1));
71
72 let dx = x1 - x0;
73 let dy = y1 - y0;
74
75 if dx.abs() > dy.abs() {
76 // mostly horizontal
77
78 if x0 > x1 {
79 // we want to go left-to-right
80 core::mem::swap(&mut x0, &mut x1);
81 core::mem::swap(&mut y0, &mut y1);
82 }
83
84 let mut ix0 = fdot6::round(x0);
85 let ix1 = fdot6::round(x1);
86 if ix0 == ix1 {
87 // too short to draw
88 continue;
89 }
90
91 let slope = fdot16::div(dy, dx);
92 #[allow(clippy::precedence)]
93 let mut start_y = fdot6::to_fdot16(y0) + (slope * ((32 - x0) & 63) >> 6);
94
95 // In some cases, probably due to precision/rounding issues,
96 // `start_y` can become equal to the image height,
97 // which will lead to panic, because we would be accessing pixels outside
98 // the current memory buffer.
99 // This is tiny-skia specific issue. Skia handles this part differently.
100 let max_y = if let Some(clip_bounds) = clip_bounds {
101 fdot16::from_f32(clip_bounds.bottom())
102 } else {
103 i32::MAX
104 };
105
106 debug_assert!(ix0 < ix1);
107 loop {
108 if ix0 >= 0 && start_y >= 0 && start_y < max_y {
109 blitter.blit_h(ix0 as u32, (start_y >> 16) as u32, LENGTH_U32_ONE);
110 }
111
112 start_y += slope;
113 ix0 += 1;
114 if ix0 >= ix1 {
115 break;
116 }
117 }
118 } else {
119 // mostly vertical
120
121 if y0 > y1 {
122 // we want to go top-to-bottom
123 core::mem::swap(&mut x0, &mut x1);
124 core::mem::swap(&mut y0, &mut y1);
125 }
126
127 let mut iy0 = fdot6::round(y0);
128 let iy1 = fdot6::round(y1);
129 if iy0 == iy1 {
130 // too short to draw
131 continue;
132 }
133
134 let slope = fdot16::div(dx, dy);
135 #[allow(clippy::precedence)]
136 let mut start_x = fdot6::to_fdot16(x0) + (slope * ((32 - y0) & 63) >> 6);
137
138 debug_assert!(iy0 < iy1);
139 loop {
140 if start_x >= 0 && iy0 >= 0 {
141 blitter.blit_h((start_x >> 16) as u32, iy0 as u32, LENGTH_U32_ONE);
142 }
143
144 start_x += slope;
145 iy0 += 1;
146 if iy0 >= iy1 {
147 break;
148 }
149 }
150 }
151 }
152}
153
154pub fn stroke_path_impl(
155 path: &Path,
156 line_cap: LineCap,
157 clip: &ScreenIntRect,
158 line_proc: LineProc,
159 blitter: &mut dyn Blitter,
160) {
161 let mut inset_clip = None;
162 let mut outset_clip = None;
163
164 {
165 let cap_out = if line_cap == LineCap::Butt { 1.0 } else { 2.0 };
166 let ibounds = match path
167 .bounds()
168 .outset(cap_out, cap_out)
169 .and_then(|r| r.round_out())
170 {
171 Some(v) => v,
172 None => return,
173 };
174 if clip.to_int_rect().intersect(&ibounds).is_none() {
175 return;
176 }
177
178 if !clip.to_int_rect().contains(&ibounds) {
179 // We now cache two scalar rects, to use for culling per-segment (e.g. cubic).
180 // Since we're hairlining, the "bounds" of the control points isn't necessairly the
181 // limit of where a segment can draw (it might draw up to 1 pixel beyond in aa-hairs).
182 //
183 // Compute the pt-bounds per segment is easy, so we do that, and then inversely adjust
184 // the culling bounds so we can just do a straight compare per segment.
185 //
186 // insetClip is use for quick-accept (i.e. the segment is not clipped), so we inset
187 // it from the clip-bounds (since segment bounds can be off by 1).
188 //
189 // outsetClip is used for quick-reject (i.e. the segment is entirely outside), so we
190 // outset it from the clip-bounds.
191 match clip.to_int_rect().make_outset(1, 1) {
192 Some(v) => outset_clip = Some(v),
193 None => return,
194 }
195 match clip.to_int_rect().inset(1, 1) {
196 Some(v) => inset_clip = Some(v),
197 None => return,
198 }
199 }
200 }
201
202 let clip = Some(clip);
203 let mut prev_verb = PathVerb::Move;
204 let mut first_pt = Point::zero();
205 let mut last_pt = Point::zero();
206
207 let mut iter = path.segments();
208 while let Some(segment) = iter.next() {
209 let verb = iter.curr_verb();
210 let next_verb = iter.next_verb();
211 let last_pt2;
212 match segment {
213 PathSegment::MoveTo(p) => {
214 first_pt = p;
215 last_pt = p;
216 last_pt2 = p;
217 }
218 PathSegment::LineTo(p) => {
219 let mut points = [last_pt, p];
220 if line_cap != LineCap::Butt {
221 extend_pts(line_cap, prev_verb, next_verb, &mut points);
222 }
223
224 line_proc(&points, clip, blitter);
225 last_pt = p;
226 last_pt2 = points[0];
227 }
228 PathSegment::QuadTo(p0, p1) => {
229 let mut points = [last_pt, p0, p1];
230 if line_cap != LineCap::Butt {
231 extend_pts(line_cap, prev_verb, next_verb, &mut points);
232 }
233
234 hair_quad(
235 &points,
236 clip,
237 inset_clip.as_ref(),
238 outset_clip.as_ref(),
239 compute_quad_level(&points),
240 line_proc,
241 blitter,
242 );
243
244 last_pt = p1;
245 last_pt2 = points[0];
246 }
247 PathSegment::CubicTo(p0, p1, p2) => {
248 let mut points = [last_pt, p0, p1, p2];
249 if line_cap != LineCap::Butt {
250 extend_pts(line_cap, prev_verb, next_verb, &mut points);
251 }
252
253 hair_cubic(
254 &points,
255 clip,
256 inset_clip.as_ref(),
257 outset_clip.as_ref(),
258 line_proc,
259 blitter,
260 );
261
262 last_pt = p2;
263 last_pt2 = points[0];
264 }
265 PathSegment::Close => {
266 let mut points = [last_pt, first_pt];
267 if line_cap != LineCap::Butt && prev_verb == PathVerb::Move {
268 // cap moveTo/close to match svg expectations for degenerate segments
269 extend_pts(line_cap, prev_verb, next_verb, &mut points);
270 }
271 line_proc(&points, clip, blitter);
272 last_pt2 = points[0];
273 }
274 }
275
276 if line_cap != LineCap::Butt {
277 if prev_verb == PathVerb::Move
278 && matches!(verb, PathVerb::Line | PathVerb::Quad | PathVerb::Cubic)
279 {
280 first_pt = last_pt2; // the curve moved the initial point, so close to it instead
281 }
282
283 prev_verb = verb;
284 }
285 }
286}
287
288/// Extend the points in the direction of the starting or ending tangent by 1/2 unit to
289/// account for a round or square cap.
290///
291/// If there's no distance between the end point and
292/// the control point, use the next control point to create a tangent. If the curve
293/// is degenerate, move the cap out 1/2 unit horizontally.
294fn extend_pts(
295 line_cap: LineCap,
296 prev_verb: PathVerb,
297 next_verb: Option<PathVerb>,
298 points: &mut [Point],
299) {
300 debug_assert!(!points.is_empty()); // TODO: use non-zero slice
301 debug_assert!(line_cap != LineCap::Butt);
302
303 // The area of a circle is PI*R*R. For a unit circle, R=1/2, and the cap covers half of that.
304 let cap_outset = if line_cap == LineCap::Square {
305 0.5
306 } else {
307 FLOAT_PI / 8.0
308 };
309 if prev_verb == PathVerb::Move {
310 let first = points[0];
311 let mut offset = 0;
312 let mut controls = points.len() - 1;
313 let mut tangent;
314 loop {
315 offset += 1;
316 tangent = first - points[offset];
317
318 if !tangent.is_zero() {
319 break;
320 }
321
322 controls -= 1;
323 if controls == 0 {
324 break;
325 }
326 }
327
328 if tangent.is_zero() {
329 tangent = Point::from_xy(1.0, 0.0);
330 controls = points.len() - 1; // If all points are equal, move all but one.
331 } else {
332 tangent.normalize();
333 }
334
335 offset = 0;
336 loop {
337 // If the end point and control points are equal, loop to move them in tandem.
338 points[offset].x += tangent.x * cap_outset;
339 points[offset].y += tangent.y * cap_outset;
340
341 offset += 1;
342 controls += 1;
343 if controls >= points.len() {
344 break;
345 }
346 }
347 }
348
349 if matches!(
350 next_verb,
351 Some(PathVerb::Move) | Some(PathVerb::Close) | None
352 ) {
353 let last = points.last().unwrap().clone();
354 let mut offset = points.len() - 1;
355 let mut controls = points.len() - 1;
356 let mut tangent;
357 loop {
358 offset -= 1;
359 tangent = last - points[offset];
360
361 if !tangent.is_zero() {
362 break;
363 }
364
365 controls -= 1;
366 if controls == 0 {
367 break;
368 }
369 }
370
371 if tangent.is_zero() {
372 tangent = Point::from_xy(-1.0, 0.0);
373 controls = points.len() - 1;
374 } else {
375 tangent.normalize();
376 }
377
378 offset = points.len() - 1;
379 loop {
380 points[offset].x += tangent.x * cap_outset;
381 points[offset].y += tangent.y * cap_outset;
382
383 offset -= 1;
384 controls += 1;
385 if controls >= points.len() {
386 break;
387 }
388 }
389 }
390}
391
392fn hair_quad(
393 points: &[Point; 3],
394 mut clip: Option<&ScreenIntRect>,
395 inset_clip: Option<&IntRect>,
396 outset_clip: Option<&IntRect>,
397 level: u8,
398 line_proc: LineProc,
399 blitter: &mut dyn Blitter,
400) {
401 if let Some(inset_clip: &IntRect) = inset_clip {
402 debug_assert!(outset_clip.is_some());
403 let inset_clip: Rect = inset_clip.to_rect();
404 let outset_clip: Rect = match outset_clip {
405 Some(v: &IntRect) => v.to_rect(),
406 None => return,
407 };
408
409 let bounds: Rect = match compute_nocheck_quad_bounds(points) {
410 Some(v: Rect) => v,
411 None => return,
412 };
413 if !geometric_overlap(&outset_clip, &bounds) {
414 return; // nothing to do
415 } else if geometric_contains(&inset_clip, &bounds) {
416 clip = None;
417 }
418 }
419
420 hair_quad2(points, clip, level, line_proc, blitter);
421}
422
423fn compute_nocheck_quad_bounds(points: &[Point; 3]) -> Option<Rect> {
424 debug_assert!(points[0].is_finite());
425 debug_assert!(points[1].is_finite());
426 debug_assert!(points[2].is_finite());
427
428 let mut min: f32x2 = points[0].to_f32x2();
429 let mut max: f32x2 = min;
430 for i: usize in 1..3 {
431 let pair: f32x2 = points[i].to_f32x2();
432 min = min.min(pair);
433 max = max.max(pair);
434 }
435
436 Rect::from_ltrb(left:min.x(), top:min.y(), right:max.x(), bottom:max.y())
437}
438
439fn geometric_overlap(a: &Rect, b: &Rect) -> bool {
440 a.left() < b.right() && b.left() < a.right() && a.top() < b.bottom() && b.top() < a.bottom()
441}
442
443fn geometric_contains(outer: &Rect, inner: &Rect) -> bool {
444 inner.right() <= outer.right()
445 && inner.left() >= outer.left()
446 && inner.bottom() <= outer.bottom()
447 && inner.top() >= outer.top()
448}
449
450fn hair_quad2(
451 points: &[Point; 3],
452 clip: Option<&ScreenIntRect>,
453 level: u8,
454 line_proc: LineProc,
455 blitter: &mut dyn Blitter,
456) {
457 debug_assert!(level <= MAX_QUAD_SUBDIVIDE_LEVEL); // TODO: to type
458
459 let coeff: QuadCoeff = path_geometry::QuadCoeff::from_points(points);
460
461 const MAX_POINTS: usize = (1 << MAX_QUAD_SUBDIVIDE_LEVEL) + 1;
462 let lines: usize = 1 << level;
463 debug_assert!(lines < MAX_POINTS);
464
465 let mut tmp: [Point; 33] = [Point::zero(); MAX_POINTS];
466 tmp[0] = points[0];
467
468 let mut t: f32x2 = f32x2::default();
469 let dt: f32x2 = f32x2::splat(1.0 / lines as f32);
470 for i: usize in 1..lines {
471 t = t + dt;
472 let v: f32x2 = (coeff.a * t + coeff.b) * t + coeff.c;
473 tmp[i] = Point::from_xy(v.x(), v.y());
474 }
475
476 tmp[lines] = points[2];
477 line_proc(&tmp[0..lines + 1], clip, blitter);
478}
479
480fn compute_quad_level(points: &[Point; 3]) -> u8 {
481 let d: u32 = compute_int_quad_dist(points);
482 // Quadratics approach the line connecting their start and end points
483 // 4x closer with each subdivision, so we compute the number of
484 // subdivisions to be the minimum need to get that distance to be less
485 // than a pixel.
486 let mut level: u32 = (33 - d.leading_zeros()) >> 1;
487 // sanity check on level (from the previous version)
488 if level > MAX_QUAD_SUBDIVIDE_LEVEL as u32 {
489 level = MAX_QUAD_SUBDIVIDE_LEVEL as u32;
490 }
491
492 level as u8
493}
494
495fn compute_int_quad_dist(points: &[Point; 3]) -> u32 {
496 // compute the vector between the control point ([1]) and the middle of the
497 // line connecting the start and end ([0] and [2])
498 let dx: f32 = ((points[0].x + points[2].x).half() - points[1].x).abs();
499 let dy: f32 = ((points[0].y + points[2].y).half() - points[1].y).abs();
500
501 // convert to whole pixel values (use ceiling to be conservative).
502 // assign to unsigned so we can safely add 1/2 of the smaller and still fit in
503 // u32, since T::saturate_from() returns 31 bits at most.
504 let idx: u32 = i32::saturate_from(dx.ceil()) as u32;
505 let idy: u32 = i32::saturate_from(dy.ceil()) as u32;
506
507 // use the cheap approx for distance
508 if idx > idy {
509 idx + (idy >> 1)
510 } else {
511 idy + (idx >> 1)
512 }
513}
514
515fn hair_cubic(
516 points: &[Point; 4],
517 mut clip: Option<&ScreenIntRect>,
518 inset_clip: Option<&IntRect>,
519 outset_clip: Option<&IntRect>,
520 line_proc: LineProc,
521 blitter: &mut dyn Blitter,
522) {
523 if let Some(inset_clip) = inset_clip {
524 debug_assert!(outset_clip.is_some());
525 let inset_clip = inset_clip.to_rect();
526 let outset_clip = match outset_clip {
527 Some(v) => v.to_rect(),
528 None => return,
529 };
530
531 let bounds = match compute_nocheck_cubic_bounds(points) {
532 Some(v) => v,
533 None => return,
534 };
535 if !geometric_overlap(&outset_clip, &bounds) {
536 return; // noting to do
537 } else if geometric_contains(&inset_clip, &bounds) {
538 clip = None;
539 }
540 }
541
542 if quick_cubic_niceness_check(points) {
543 hair_cubic2(points, clip, line_proc, blitter);
544 } else {
545 let mut tmp = [Point::zero(); 13];
546 let mut t_values = path_geometry::new_t_values();
547
548 let count = path_geometry::chop_cubic_at_max_curvature(points, &mut t_values, &mut tmp);
549 for i in 0..count {
550 let offset = i * 3;
551 let new_points: [Point; 4] = tmp[offset..offset + 4].try_into().unwrap();
552 hair_cubic2(&new_points, clip, line_proc, blitter);
553 }
554 }
555}
556
557fn compute_nocheck_cubic_bounds(points: &[Point; 4]) -> Option<Rect> {
558 debug_assert!(points[0].is_finite());
559 debug_assert!(points[1].is_finite());
560 debug_assert!(points[2].is_finite());
561 debug_assert!(points[3].is_finite());
562
563 let mut min: f32x2 = points[0].to_f32x2();
564 let mut max: f32x2 = min;
565 for i: usize in 1..4 {
566 let pair: f32x2 = points[i].to_f32x2();
567 min = min.min(pair);
568 max = max.max(pair);
569 }
570
571 Rect::from_ltrb(left:min.x(), top:min.y(), right:max.x(), bottom:max.y())
572}
573
574// The off-curve points are "inside" the limits of the on-curve points.
575fn quick_cubic_niceness_check(points: &[Point; 4]) -> bool {
576 lt_90(p0:points[1], pivot:points[0], p2:points[3])
577 && lt_90(p0:points[2], pivot:points[0], p2:points[3])
578 && lt_90(p0:points[1], pivot:points[3], p2:points[0])
579 && lt_90(p0:points[2], pivot:points[3], p2:points[0])
580}
581
582fn lt_90(p0: Point, pivot: Point, p2: Point) -> bool {
583 (p0 - pivot).dot(p2 - pivot) >= 0.0
584}
585
586fn hair_cubic2(
587 points: &[Point; 4],
588 clip: Option<&ScreenIntRect>,
589 line_proc: LineProc,
590 blitter: &mut dyn Blitter,
591) {
592 let lines = compute_cubic_segments(points);
593 debug_assert!(lines > 0);
594 if lines == 1 {
595 line_proc(&[points[0], points[3]], clip, blitter);
596 return;
597 }
598
599 let coeff = path_geometry::CubicCoeff::from_points(points);
600
601 const MAX_POINTS: usize = (1 << MAX_CUBIC_SUBDIVIDE_LEVEL) + 1;
602 debug_assert!(lines < MAX_POINTS);
603 let mut tmp = [Point::zero(); MAX_POINTS];
604
605 let dt = f32x2::splat(1.0 / lines as f32);
606 let mut t = f32x2::default();
607
608 tmp[0] = points[0];
609 for i in 1..lines {
610 t = t + dt;
611 tmp[i] = Point::from_f32x2(((coeff.a * t + coeff.b) * t + coeff.c) * t + coeff.d);
612 }
613
614 if tmp.iter().all(|p| p.is_finite()) {
615 tmp[lines] = points[3];
616 line_proc(&tmp[0..lines + 1], clip, blitter);
617 } else {
618 // else some point(s) are non-finite, so don't draw
619 }
620}
621
622fn compute_cubic_segments(points: &[Point; 4]) -> usize {
623 let p0 = points[0].to_f32x2();
624 let p1 = points[1].to_f32x2();
625 let p2 = points[2].to_f32x2();
626 let p3 = points[3].to_f32x2();
627
628 let one_third = f32x2::splat(1.0 / 3.0);
629 let two_third = f32x2::splat(2.0 / 3.0);
630
631 let p13 = one_third * p3 + two_third * p0;
632 let p23 = one_third * p0 + two_third * p3;
633
634 let diff = (p1 - p13).abs().max((p2 - p23).abs()).max_component();
635 let mut tol = 1.0 / 8.0;
636
637 for i in 0..MAX_CUBIC_SUBDIVIDE_LEVEL {
638 if diff < tol {
639 return 1 << i;
640 }
641
642 tol *= 4.0;
643 }
644
645 1 << MAX_CUBIC_SUBDIVIDE_LEVEL
646}
647