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 crate::Point;
8
9use crate::fixed_point::{fdot16, fdot6, FDot16, FDot6};
10use crate::math::left_shift;
11
12/// We store 1<<shift in a (signed) byte, so its maximum value is 1<<6 == 64.
13///
14/// Note that this limits the number of lines we use to approximate a curve.
15/// If we need to increase this, we need to store curve_count in something
16/// larger than i8.
17const MAX_COEFF_SHIFT: i32 = 6;
18
19#[derive(Clone, Debug)]
20pub enum Edge {
21 Line(LineEdge),
22 Quadratic(QuadraticEdge),
23 Cubic(CubicEdge),
24}
25
26impl Edge {
27 pub fn as_line(&self) -> &LineEdge {
28 match self {
29 Edge::Line(line: &LineEdge) => line,
30 Edge::Quadratic(quad: &QuadraticEdge) => &quad.line,
31 Edge::Cubic(cubic: &CubicEdge) => &cubic.line,
32 }
33 }
34
35 pub fn as_line_mut(&mut self) -> &mut LineEdge {
36 match self {
37 Edge::Line(line: &mut LineEdge) => line,
38 Edge::Quadratic(quad: &mut QuadraticEdge) => &mut quad.line,
39 Edge::Cubic(cubic: &mut CubicEdge) => &mut cubic.line,
40 }
41 }
42}
43
44impl core::ops::Deref for Edge {
45 type Target = LineEdge;
46
47 fn deref(&self) -> &Self::Target {
48 self.as_line()
49 }
50}
51
52impl core::ops::DerefMut for Edge {
53 fn deref_mut(&mut self) -> &mut Self::Target {
54 self.as_line_mut()
55 }
56}
57
58#[derive(Clone, Default, Debug)]
59pub struct LineEdge {
60 // Imitate a linked list.
61 pub prev: Option<u32>,
62 pub next: Option<u32>,
63
64 pub x: FDot16,
65 pub dx: FDot16,
66 pub first_y: i32,
67 pub last_y: i32,
68 pub winding: i8, // 1 or -1
69}
70
71impl LineEdge {
72 pub fn new(p0: Point, p1: Point, shift: i32) -> Option<Self> {
73 let scale = (1 << (shift + 6)) as f32;
74 let mut x0 = (p0.x * scale) as i32;
75 let mut y0 = (p0.y * scale) as i32;
76 let mut x1 = (p1.x * scale) as i32;
77 let mut y1 = (p1.y * scale) as i32;
78
79 let mut winding = 1;
80
81 if y0 > y1 {
82 core::mem::swap(&mut x0, &mut x1);
83 core::mem::swap(&mut y0, &mut y1);
84 winding = -1;
85 }
86
87 let top = fdot6::round(y0);
88 let bottom = fdot6::round(y1);
89
90 // are we a zero-height line?
91 if top == bottom {
92 return None;
93 }
94
95 let slope = fdot6::div(x1 - x0, y1 - y0);
96 let dy = compute_dy(top, y0);
97
98 Some(LineEdge {
99 next: None,
100 prev: None,
101 x: fdot6::to_fdot16(x0 + fdot16::mul(slope, dy)),
102 dx: slope,
103 first_y: top,
104 last_y: bottom - 1,
105 winding,
106 })
107 }
108
109 pub fn is_vertical(&self) -> bool {
110 self.dx == 0
111 }
112
113 fn update(&mut self, mut x0: FDot16, mut y0: FDot16, mut x1: FDot16, mut y1: FDot16) -> bool {
114 debug_assert!(self.winding == 1 || self.winding == -1);
115
116 y0 >>= 10;
117 y1 >>= 10;
118
119 debug_assert!(y0 <= y1);
120
121 let top = fdot6::round(y0);
122 let bottom = fdot6::round(y1);
123
124 // are we a zero-height line?
125 if top == bottom {
126 return false;
127 }
128
129 x0 >>= 10;
130 x1 >>= 10;
131
132 let slope = fdot6::div(x1 - x0, y1 - y0);
133 let dy = compute_dy(top, y0);
134
135 self.x = fdot6::to_fdot16(x0 + fdot16::mul(slope, dy));
136 self.dx = slope;
137 self.first_y = top;
138 self.last_y = bottom - 1;
139
140 true
141 }
142}
143
144#[derive(Clone, Debug)]
145pub struct QuadraticEdge {
146 pub line: LineEdge,
147 pub curve_count: i8,
148 curve_shift: u8, // applied to all dx/ddx/dddx
149 qx: FDot16,
150 qy: FDot16,
151 qdx: FDot16,
152 qdy: FDot16,
153 qddx: FDot16,
154 qddy: FDot16,
155 q_last_x: FDot16,
156 q_last_y: FDot16,
157}
158
159impl QuadraticEdge {
160 pub fn new(points: &[Point], shift: i32) -> Option<Self> {
161 let mut quad = Self::new2(points, shift)?;
162 if quad.update() {
163 Some(quad)
164 } else {
165 None
166 }
167 }
168
169 fn new2(points: &[Point], mut shift: i32) -> Option<Self> {
170 let scale = (1 << (shift + 6)) as f32;
171 let mut x0 = (points[0].x * scale) as i32;
172 let mut y0 = (points[0].y * scale) as i32;
173 let x1 = (points[1].x * scale) as i32;
174 let y1 = (points[1].y * scale) as i32;
175 let mut x2 = (points[2].x * scale) as i32;
176 let mut y2 = (points[2].y * scale) as i32;
177
178 let mut winding = 1;
179 if y0 > y2 {
180 core::mem::swap(&mut x0, &mut x2);
181 core::mem::swap(&mut y0, &mut y2);
182 winding = -1;
183 }
184 debug_assert!(y0 <= y1 && y1 <= y2);
185
186 let top = fdot6::round(y0);
187 let bottom = fdot6::round(y2);
188
189 // are we a zero-height quad (line)?
190 if top == bottom {
191 return None;
192 }
193
194 // compute number of steps needed (1 << shift)
195 {
196 let dx = (left_shift(x1, 1) - x0 - x2) >> 2;
197 let dy = (left_shift(y1, 1) - y0 - y2) >> 2;
198 // This is a little confusing:
199 // before this line, shift is the scale up factor for AA;
200 // after this line, shift is the fCurveShift.
201 shift = diff_to_shift(dx, dy, shift);
202 debug_assert!(shift >= 0);
203 }
204
205 // need at least 1 subdivision for our bias trick
206 if shift == 0 {
207 shift = 1;
208 } else if shift > MAX_COEFF_SHIFT {
209 shift = MAX_COEFF_SHIFT;
210 }
211
212 let curve_count = (1 << shift) as i8;
213
214 // We want to reformulate into polynomial form, to make it clear how we
215 // should forward-difference.
216 //
217 // p0 (1 - t)^2 + p1 t(1 - t) + p2 t^2 ==> At^2 + Bt + C
218 //
219 // A = p0 - 2p1 + p2
220 // B = 2(p1 - p0)
221 // C = p0
222 //
223 // Our caller must have constrained our inputs (p0..p2) to all fit into
224 // 16.16. However, as seen above, we sometimes compute values that can be
225 // larger (e.g. B = 2*(p1 - p0)). To guard against overflow, we will store
226 // A and B at 1/2 of their actual value, and just apply a 2x scale during
227 // application in updateQuadratic(). Hence we store (shift - 1) in
228 // curve_shift.
229
230 let curve_shift = (shift - 1) as u8;
231
232 let mut a = fdot6_to_fixed_div2(x0 - x1 - x1 + x2); // 1/2 the real value
233 let mut b = fdot6::to_fdot16(x1 - x0); // 1/2 the real value
234
235 let qx = fdot6::to_fdot16(x0);
236 let qdx = b + (a >> shift); // biased by shift
237 let qddx = a >> (shift - 1); // biased by shift
238
239 a = fdot6_to_fixed_div2(y0 - y1 - y1 + y2); // 1/2 the real value
240 b = fdot6::to_fdot16(y1 - y0); // 1/2 the real value
241
242 let qy = fdot6::to_fdot16(y0);
243 let qdy = b + (a >> shift); // biased by shift
244 let qddy = a >> (shift - 1); // biased by shift
245
246 let q_last_x = fdot6::to_fdot16(x2);
247 let q_last_y = fdot6::to_fdot16(y2);
248
249 Some(QuadraticEdge {
250 line: LineEdge {
251 next: None,
252 prev: None,
253 x: 0,
254 dx: 0,
255 first_y: 0,
256 last_y: 0,
257 winding,
258 },
259 curve_count,
260 curve_shift,
261 qx,
262 qy,
263 qdx,
264 qdy,
265 qddx,
266 qddy,
267 q_last_x,
268 q_last_y,
269 })
270 }
271
272 pub fn update(&mut self) -> bool {
273 let mut success;
274 let mut count = self.curve_count;
275 let mut oldx = self.qx;
276 let mut oldy = self.qy;
277 let mut dx = self.qdx;
278 let mut dy = self.qdy;
279 let mut newx;
280 let mut newy;
281 let shift = self.curve_shift;
282
283 debug_assert!(count > 0);
284
285 loop {
286 count -= 1;
287 if count > 0 {
288 newx = oldx + (dx >> shift);
289 dx += self.qddx;
290 newy = oldy + (dy >> shift);
291 dy += self.qddy;
292 } else {
293 // last segment
294 newx = self.q_last_x;
295 newy = self.q_last_y;
296 }
297 success = self.line.update(oldx, oldy, newx, newy);
298 oldx = newx;
299 oldy = newy;
300
301 if count == 0 || success {
302 break;
303 }
304 }
305
306 self.qx = newx;
307 self.qy = newy;
308 self.qdx = dx;
309 self.qdy = dy;
310 self.curve_count = count;
311
312 success
313 }
314}
315
316#[derive(Clone, Debug)]
317pub struct CubicEdge {
318 pub line: LineEdge,
319 pub curve_count: i8,
320 curve_shift: u8, // applied to all dx/ddx/dddx except for dshift exception
321 dshift: u8, // applied to cdx and cdy
322 cx: FDot16,
323 cy: FDot16,
324 cdx: FDot16,
325 cdy: FDot16,
326 cddx: FDot16,
327 cddy: FDot16,
328 cdddx: FDot16,
329 cdddy: FDot16,
330 c_last_x: FDot16,
331 c_last_y: FDot16,
332}
333
334impl CubicEdge {
335 pub fn new(points: &[Point], shift: i32) -> Option<Self> {
336 let mut cubic = Self::new2(points, shift, true)?;
337 if cubic.update() {
338 Some(cubic)
339 } else {
340 None
341 }
342 }
343
344 fn new2(points: &[Point], mut shift: i32, sort_y: bool) -> Option<Self> {
345 let scale = (1 << (shift + 6)) as f32;
346 let mut x0 = (points[0].x * scale) as i32;
347 let mut y0 = (points[0].y * scale) as i32;
348 let mut x1 = (points[1].x * scale) as i32;
349 let mut y1 = (points[1].y * scale) as i32;
350 let mut x2 = (points[2].x * scale) as i32;
351 let mut y2 = (points[2].y * scale) as i32;
352 let mut x3 = (points[3].x * scale) as i32;
353 let mut y3 = (points[3].y * scale) as i32;
354
355 let mut winding = 1;
356 if sort_y && y0 > y3 {
357 core::mem::swap(&mut x0, &mut x3);
358 core::mem::swap(&mut x1, &mut x2);
359 core::mem::swap(&mut y0, &mut y3);
360 core::mem::swap(&mut y1, &mut y2);
361 winding = -1;
362 }
363
364 let top = fdot6::round(y0);
365 let bot = fdot6::round(y3);
366
367 // are we a zero-height cubic (line)?
368 if sort_y && top == bot {
369 return None;
370 }
371
372 // compute number of steps needed (1 << shift)
373 {
374 // Can't use (center of curve - center of baseline), since center-of-curve
375 // need not be the max delta from the baseline (it could even be coincident)
376 // so we try just looking at the two off-curve points
377 let dx = cubic_delta_from_line(x0, x1, x2, x3);
378 let dy = cubic_delta_from_line(y0, y1, y2, y3);
379 // add 1 (by observation)
380 shift = diff_to_shift(dx, dy, 2) + 1;
381 }
382 // need at least 1 subdivision for our bias trick
383 debug_assert!(shift > 0);
384 if shift > MAX_COEFF_SHIFT {
385 shift = MAX_COEFF_SHIFT;
386 }
387
388 // Since our in coming data is initially shifted down by 10 (or 8 in
389 // antialias). That means the most we can shift up is 8. However, we
390 // compute coefficients with a 3*, so the safest upshift is really 6
391 let mut up_shift = 6; // largest safe value
392 let mut down_shift = shift + up_shift - 10;
393 if down_shift < 0 {
394 down_shift = 0;
395 up_shift = 10 - shift;
396 }
397
398 let curve_count = left_shift(-1, shift) as i8;
399 let curve_shift = shift as u8;
400 let dshift = down_shift as u8;
401
402 let mut b = fdot6_up_shift(3 * (x1 - x0), up_shift);
403 let mut c = fdot6_up_shift(3 * (x0 - x1 - x1 + x2), up_shift);
404 let mut d = fdot6_up_shift(x3 + 3 * (x1 - x2) - x0, up_shift);
405
406 let cx = fdot6::to_fdot16(x0);
407 let cdx = b + (c >> shift) + (d >> (2 * shift)); // biased by shift
408 let cddx = 2 * c + ((3 * d) >> (shift - 1)); // biased by 2*shift
409 let cdddx = (3 * d) >> (shift - 1); // biased by 2*shift
410
411 b = fdot6_up_shift(3 * (y1 - y0), up_shift);
412 c = fdot6_up_shift(3 * (y0 - y1 - y1 + y2), up_shift);
413 d = fdot6_up_shift(y3 + 3 * (y1 - y2) - y0, up_shift);
414
415 let cy = fdot6::to_fdot16(y0);
416 let cdy = b + (c >> shift) + (d >> (2 * shift)); // biased by shift
417 let cddy = 2 * c + ((3 * d) >> (shift - 1)); // biased by 2*shift
418 let cdddy = (3 * d) >> (shift - 1); // biased by 2*shift
419
420 let c_last_x = fdot6::to_fdot16(x3);
421 let c_last_y = fdot6::to_fdot16(y3);
422
423 Some(CubicEdge {
424 line: LineEdge {
425 next: None,
426 prev: None,
427 x: 0,
428 dx: 0,
429 first_y: 0,
430 last_y: 0,
431 winding,
432 },
433 curve_count,
434 curve_shift,
435 dshift,
436 cx,
437 cy,
438 cdx,
439 cdy,
440 cddx,
441 cddy,
442 cdddx,
443 cdddy,
444 c_last_x,
445 c_last_y,
446 })
447 }
448
449 pub fn update(&mut self) -> bool {
450 let mut success;
451 let mut count = self.curve_count;
452 let mut oldx = self.cx;
453 let mut oldy = self.cy;
454 let mut newx;
455 let mut newy;
456 let ddshift = self.curve_shift;
457 let dshift = self.dshift;
458
459 debug_assert!(count < 0);
460
461 loop {
462 count += 1;
463 if count < 0 {
464 newx = oldx + (self.cdx >> dshift);
465 self.cdx += self.cddx >> ddshift;
466 self.cddx += self.cdddx;
467
468 newy = oldy + (self.cdy >> dshift);
469 self.cdy += self.cddy >> ddshift;
470 self.cddy += self.cdddy;
471 } else {
472 // last segment
473 newx = self.c_last_x;
474 newy = self.c_last_y;
475 }
476
477 // we want to say debug_assert(oldy <= newy), but our finite fixedpoint
478 // doesn't always achieve that, so we have to explicitly pin it here.
479 if newy < oldy {
480 newy = oldy;
481 }
482
483 success = self.line.update(oldx, oldy, newx, newy);
484 oldx = newx;
485 oldy = newy;
486
487 if count == 0 || success {
488 break;
489 }
490 }
491
492 self.cx = newx;
493 self.cy = newy;
494 self.curve_count = count;
495
496 success
497 }
498}
499
500// This correctly favors the lower-pixel when y0 is on a 1/2 pixel boundary
501fn compute_dy(top: FDot6, y0: FDot6) -> FDot6 {
502 left_shift(value:top, shift:6) + 32 - y0
503}
504
505fn diff_to_shift(dx: FDot6, dy: FDot6, shift_aa: i32) -> i32 {
506 // cheap calc of distance from center of p0-p2 to the center of the curve
507 let mut dist: i32 = cheap_distance(dx, dy);
508
509 // shift down dist (it is currently in dot6)
510 // down by 3 should give us 1/8 pixel accuracy (assuming our dist is accurate...)
511 // this is chosen by heuristic: make it as big as possible (to minimize segments)
512 // ... but small enough so that our curves still look smooth
513 // When shift > 0, we're using AA and everything is scaled up so we can
514 // lower the accuracy.
515 dist = (dist + (1 << 4)) >> (3 + shift_aa);
516
517 // each subdivision (shift value) cuts this dist (error) by 1/4
518 (32 - dist.leading_zeros() as i32) >> 1
519}
520
521fn cheap_distance(mut dx: FDot6, mut dy: FDot6) -> FDot6 {
522 dx = dx.abs();
523 dy = dy.abs();
524 // return max + min/2
525 if dx > dy {
526 dx + (dy >> 1)
527 } else {
528 dy + (dx >> 1)
529 }
530}
531
532// In LineEdge::new, QuadraticEdge::new, CubicEdge::new, the first thing we do is to convert
533// the points into FDot6. This is modulated by the shift parameter, which
534// will either be 0, or something like 2 for antialiasing.
535//
536// In the float case, we want to turn the float into .6 by saying pt * 64,
537// or pt * 256 for antialiasing. This is implemented as 1 << (shift + 6).
538//
539// In the fixed case, we want to turn the fixed into .6 by saying pt >> 10,
540// or pt >> 8 for antialiasing. This is implemented as pt >> (10 - shift).
541fn fdot6_to_fixed_div2(value: FDot6) -> FDot16 {
542 // we want to return SkFDot6ToFixed(value >> 1), but we don't want to throw
543 // away data in value, so just perform a modify up-shift
544 left_shift(value, shift:16 - 6 - 1)
545}
546
547fn fdot6_up_shift(x: FDot6, up_shift: i32) -> i32 {
548 debug_assert!((left_shift(x, up_shift) >> up_shift) == x);
549 left_shift(value:x, up_shift)
550}
551
552// f(1/3) = (8a + 12b + 6c + d) / 27
553// f(2/3) = (a + 6b + 12c + 8d) / 27
554//
555// f(1/3)-b = (8a - 15b + 6c + d) / 27
556// f(2/3)-c = (a + 6b - 15c + 8d) / 27
557//
558// use 16/512 to approximate 1/27
559fn cubic_delta_from_line(a: FDot6, b: FDot6, c: FDot6, d: FDot6) -> FDot6 {
560 // since our parameters may be negative, we don't use <<
561 let one_third: i32 = ((a * 8 - b * 15 + 6 * c + d) * 19) >> 9;
562 let two_third: i32 = ((a + 6 * b - c * 15 + d * 8) * 19) >> 9;
563
564 one_third.abs().max(two_third.abs())
565}
566