[go: nahoru, domu]
Google Git
Sign in
android / platform / external / chromium_org / third_party / skia / src / 007593e0c1f460ed7e6eb643aa34907d094670ed / . / core / SkGeometry.cpp
blob: 57ce2fdb10f1d5f141a1cb1a1bf6d25f525425ca [file] [log] [blame]
reed@android.combcd4d5a2008-12-17 15:59:43 +0000[diff] [blame]1/* libs/graphics/sgl/SkGeometry.cpp
2**
3** Copyright 2006, The Android Open Source Project
4**
5** Licensed under the Apache License, Version 2.0 (the "License");
6** you may not use this file except in compliance with the License.
7** You may obtain a copy of the License at
8**
9** http://www.apache.org/licenses/LICENSE-2.0
10**
11** Unless required by applicable law or agreed to in writing, software
12** distributed under the License is distributed on an "AS IS" BASIS,
13** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14** See the License for the specific language governing permissions and
15** limitations under the License.
16*/
17
18#include "SkGeometry.h"
19#include "Sk64.h"
20#include "SkMatrix.h"
21
kbr@chromium.orgc1b53332010-07-07 22:20:35 +0000[diff] [blame]22bool SkXRayCrossesLine(const SkXRay& pt, const SkPoint pts[2], bool* ambiguous) {
23 if (ambiguous) {
24 *ambiguous = false;
25 }
reed@android.com5b4541e2010-02-05 20:41:02 +0000[diff] [blame]26 // Determine quick discards.
27 // Consider query line going exactly through point 0 to not
28 // intersect, for symmetry with SkXRayCrossesMonotonicCubic.
kbr@chromium.orgc1b53332010-07-07 22:20:35 +0000[diff] [blame]29 if (pt.fY == pts[0].fY) {
30 if (ambiguous) {
31 *ambiguous = true;
32 }
reed@android.com5b4541e2010-02-05 20:41:02 +0000[diff] [blame]33 return false;
kbr@chromium.orgc1b53332010-07-07 22:20:35 +0000[diff] [blame]34 }
reed@android.com5b4541e2010-02-05 20:41:02 +0000[diff] [blame]35 if (pt.fY < pts[0].fY && pt.fY < pts[1].fY)
36 return false;
37 if (pt.fY > pts[0].fY && pt.fY > pts[1].fY)
38 return false;
39 if (pt.fX > pts[0].fX && pt.fX > pts[1].fX)
40 return false;
41 // Determine degenerate cases
42 if (SkScalarNearlyZero(pts[0].fY - pts[1].fY))
43 return false;
kbr@chromium.orgc1b53332010-07-07 22:20:35 +0000[diff] [blame]44 if (SkScalarNearlyZero(pts[0].fX - pts[1].fX)) {
reed@android.com5b4541e2010-02-05 20:41:02 +0000[diff] [blame]45 // We've already determined the query point lies within the
46 // vertical range of the line segment.
kbr@chromium.orgc1b53332010-07-07 22:20:35 +0000[diff] [blame]47 if (pt.fX <= pts[0].fX) {
48 if (ambiguous) {
49 *ambiguous = (pt.fY == pts[1].fY);
50 }
51 return true;
52 }
53 return false;
54 }
55 // Ambiguity check
56 if (pt.fY == pts[1].fY) {
57 if (pt.fX <= pts[1].fX) {
58 if (ambiguous) {
59 *ambiguous = true;
60 }
61 return true;
62 }
63 return false;
64 }
reed@android.com5b4541e2010-02-05 20:41:02 +0000[diff] [blame]65 // Full line segment evaluation
66 SkScalar delta_y = pts[1].fY - pts[0].fY;
67 SkScalar delta_x = pts[1].fX - pts[0].fX;
68 SkScalar slope = SkScalarDiv(delta_y, delta_x);
69 SkScalar b = pts[0].fY - SkScalarMul(slope, pts[0].fX);
70 // Solve for x coordinate at y = pt.fY
71 SkScalar x = SkScalarDiv(pt.fY - b, slope);
72 return pt.fX <= x;
73}
74
reed@android.combcd4d5a2008-12-17 15:59:43 +0000[diff] [blame]75/** If defined, this makes eval_quad and eval_cubic do more setup (sometimes
76 involving integer multiplies by 2 or 3, but fewer calls to SkScalarMul.
77 May also introduce overflow of fixed when we compute our setup.
78*/
79#ifdef SK_SCALAR_IS_FIXED
80 #define DIRECT_EVAL_OF_POLYNOMIALS
81#endif
82
83////////////////////////////////////////////////////////////////////////
84
85#ifdef SK_SCALAR_IS_FIXED
86 static int is_not_monotonic(int a, int b, int c, int d)
87 {
88 return (((a - b) | (b - c) | (c - d)) & ((b - a) | (c - b) | (d - c))) >> 31;
89 }
90
91 static int is_not_monotonic(int a, int b, int c)
92 {
93 return (((a - b) | (b - c)) & ((b - a) | (c - b))) >> 31;
94 }
95#else
96 static int is_not_monotonic(float a, float b, float c)
97 {
98 float ab = a - b;
99 float bc = b - c;
100 if (ab < 0)
101 bc = -bc;
102 return ab == 0 || bc < 0;
103 }
104#endif
105
106////////////////////////////////////////////////////////////////////////
107
108static bool is_unit_interval(SkScalar x)
109{
110 return x > 0 && x < SK_Scalar1;
111}
112
113static int valid_unit_divide(SkScalar numer, SkScalar denom, SkScalar* ratio)
114{
115 SkASSERT(ratio);
116
117 if (numer < 0)
118 {
119 numer = -numer;
120 denom = -denom;
121 }
122
123 if (denom == 0 || numer == 0 || numer >= denom)
124 return 0;
125
126 SkScalar r = SkScalarDiv(numer, denom);
reed@android.com7c83e1c2010-03-08 17:44:42 +0000[diff] [blame]127 if (SkScalarIsNaN(r)) {
128 return 0;
129 }
reed@android.combcd4d5a2008-12-17 15:59:43 +0000[diff] [blame]130 SkASSERT(r >= 0 && r < SK_Scalar1);
131 if (r == 0) // catch underflow if numer <<<< denom
132 return 0;
133 *ratio = r;
134 return 1;
135}
136
137/** From Numerical Recipes in C.
138
139 Q = -1/2 (B + sign(B) sqrt[B*B - 4*A*C])
140 x1 = Q / A
141 x2 = C / Q
142*/
143int SkFindUnitQuadRoots(SkScalar A, SkScalar B, SkScalar C, SkScalar roots[2])
144{
145 SkASSERT(roots);
146
147 if (A == 0)
148 return valid_unit_divide(-C, B, roots);
149
150 SkScalar* r = roots;
151
152#ifdef SK_SCALAR_IS_FLOAT
153 float R = B*B - 4*A*C;
reed@android.com7c83e1c2010-03-08 17:44:42 +0000[diff] [blame]154 if (R < 0 || SkScalarIsNaN(R)) { // complex roots
reed@android.combcd4d5a2008-12-17 15:59:43 +0000[diff] [blame]155 return 0;
reed@android.com7c83e1c2010-03-08 17:44:42 +0000[diff] [blame]156 }
reed@android.combcd4d5a2008-12-17 15:59:43 +0000[diff] [blame]157 R = sk_float_sqrt(R);
158#else
159 Sk64 RR, tmp;
160
161 RR.setMul(B,B);
162 tmp.setMul(A,C);
163 tmp.shiftLeft(2);
164 RR.sub(tmp);
165 if (RR.isNeg())
166 return 0;
167 SkFixed R = RR.getSqrt();
168#endif
169
170 SkScalar Q = (B < 0) ? -(B-R)/2 : -(B+R)/2;
171 r += valid_unit_divide(Q, A, r);
172 r += valid_unit_divide(C, Q, r);
173 if (r - roots == 2)
174 {
175 if (roots[0] > roots[1])
176 SkTSwap<SkScalar>(roots[0], roots[1]);
177 else if (roots[0] == roots[1]) // nearly-equal?
178 r -= 1; // skip the double root
179 }
180 return (int)(r - roots);
181}
182
183#ifdef SK_SCALAR_IS_FIXED
184/** Trim A/B/C down so that they are all <= 32bits
185 and then call SkFindUnitQuadRoots()
186*/
187static int Sk64FindFixedQuadRoots(const Sk64& A, const Sk64& B, const Sk64& C, SkFixed roots[2])
188{
189 int na = A.shiftToMake32();
190 int nb = B.shiftToMake32();
191 int nc = C.shiftToMake32();
192
193 int shift = SkMax32(na, SkMax32(nb, nc));
194 SkASSERT(shift >= 0);
195
196 return SkFindUnitQuadRoots(A.getShiftRight(shift), B.getShiftRight(shift), C.getShiftRight(shift), roots);
197}
198#endif
199
200/////////////////////////////////////////////////////////////////////////////////////
201/////////////////////////////////////////////////////////////////////////////////////
202
203static SkScalar eval_quad(const SkScalar src[], SkScalar t)
204{
205 SkASSERT(src);
206 SkASSERT(t >= 0 && t <= SK_Scalar1);
207
208#ifdef DIRECT_EVAL_OF_POLYNOMIALS
209 SkScalar C = src[0];
210 SkScalar A = src[4] - 2 * src[2] + C;
211 SkScalar B = 2 * (src[2] - C);
212 return SkScalarMulAdd(SkScalarMulAdd(A, t, B), t, C);
213#else
214 SkScalar ab = SkScalarInterp(src[0], src[2], t);
215 SkScalar bc = SkScalarInterp(src[2], src[4], t);
216 return SkScalarInterp(ab, bc, t);
217#endif
218}
219
220static SkScalar eval_quad_derivative(const SkScalar src[], SkScalar t)
221{
222 SkScalar A = src[4] - 2 * src[2] + src[0];
223 SkScalar B = src[2] - src[0];
224
225 return 2 * SkScalarMulAdd(A, t, B);
226}
227
228static SkScalar eval_quad_derivative_at_half(const SkScalar src[])
229{
230 SkScalar A = src[4] - 2 * src[2] + src[0];
231 SkScalar B = src[2] - src[0];
232 return A + 2 * B;
233}
234
235void SkEvalQuadAt(const SkPoint src[3], SkScalar t, SkPoint* pt, SkVector* tangent)
236{
237 SkASSERT(src);
238 SkASSERT(t >= 0 && t <= SK_Scalar1);
239
240 if (pt)
241 pt->set(eval_quad(&src[0].fX, t), eval_quad(&src[0].fY, t));
242 if (tangent)
243 tangent->set(eval_quad_derivative(&src[0].fX, t),
244 eval_quad_derivative(&src[0].fY, t));
245}
246
247void SkEvalQuadAtHalf(const SkPoint src[3], SkPoint* pt, SkVector* tangent)
248{
249 SkASSERT(src);
250
251 if (pt)
252 {
253 SkScalar x01 = SkScalarAve(src[0].fX, src[1].fX);
254 SkScalar y01 = SkScalarAve(src[0].fY, src[1].fY);
255 SkScalar x12 = SkScalarAve(src[1].fX, src[2].fX);
256 SkScalar y12 = SkScalarAve(src[1].fY, src[2].fY);
257 pt->set(SkScalarAve(x01, x12), SkScalarAve(y01, y12));
258 }
259 if (tangent)
260 tangent->set(eval_quad_derivative_at_half(&src[0].fX),
261 eval_quad_derivative_at_half(&src[0].fY));
262}
263
264static void interp_quad_coords(const SkScalar* src, SkScalar* dst, SkScalar t)
265{
266 SkScalar ab = SkScalarInterp(src[0], src[2], t);
267 SkScalar bc = SkScalarInterp(src[2], src[4], t);
268
269 dst[0] = src[0];
270 dst[2] = ab;
271 dst[4] = SkScalarInterp(ab, bc, t);
272 dst[6] = bc;
273 dst[8] = src[4];
274}
275
276void SkChopQuadAt(const SkPoint src[3], SkPoint dst[5], SkScalar t)
277{
278 SkASSERT(t > 0 && t < SK_Scalar1);
279
280 interp_quad_coords(&src[0].fX, &dst[0].fX, t);
281 interp_quad_coords(&src[0].fY, &dst[0].fY, t);
282}
283
284void SkChopQuadAtHalf(const SkPoint src[3], SkPoint dst[5])
285{
286 SkScalar x01 = SkScalarAve(src[0].fX, src[1].fX);
287 SkScalar y01 = SkScalarAve(src[0].fY, src[1].fY);
288 SkScalar x12 = SkScalarAve(src[1].fX, src[2].fX);
289 SkScalar y12 = SkScalarAve(src[1].fY, src[2].fY);
290
291 dst[0] = src[0];
292 dst[1].set(x01, y01);
293 dst[2].set(SkScalarAve(x01, x12), SkScalarAve(y01, y12));
294 dst[3].set(x12, y12);
295 dst[4] = src[2];
296}
297
298/** Quad'(t) = At + B, where
299 A = 2(a - 2b + c)
300 B = 2(b - a)
301 Solve for t, only if it fits between 0 < t < 1
302*/
303int SkFindQuadExtrema(SkScalar a, SkScalar b, SkScalar c, SkScalar tValue[1])
304{
305 /* At + B == 0
306 t = -B / A
307 */
308#ifdef SK_SCALAR_IS_FIXED
309 return is_not_monotonic(a, b, c) && valid_unit_divide(a - b, a - b - b + c, tValue);
310#else
311 return valid_unit_divide(a - b, a - b - b + c, tValue);
312#endif
313}
314
reed@android.come5dd6cd2009-01-15 14:38:33 +0000[diff] [blame]315static inline void flatten_double_quad_extrema(SkScalar coords[14])
reed@android.combcd4d5a2008-12-17 15:59:43 +0000[diff] [blame]316{
317 coords[2] = coords[6] = coords[4];
318}
319
reed@android.combcd4d5a2008-12-17 15:59:43 +0000[diff] [blame]320/* Returns 0 for 1 quad, and 1 for two quads, either way the answer is
reed@android.com001bd972009-11-17 18:47:52 +0000[diff] [blame]321 stored in dst[]. Guarantees that the 1/2 quads will be monotonic.
322 */
reed@android.combcd4d5a2008-12-17 15:59:43 +0000[diff] [blame]323int SkChopQuadAtYExtrema(const SkPoint src[3], SkPoint dst[5])
324{
325 SkASSERT(src);
326 SkASSERT(dst);
reed@android.com001bd972009-11-17 18:47:52 +0000[diff] [blame]327
reed@android.combcd4d5a2008-12-17 15:59:43 +0000[diff] [blame]328#if 0
329 static bool once = true;
330 if (once)
331 {
332 once = false;
333 SkPoint s[3] = { 0, 26398, 0, 26331, 0, 20621428 };
334 SkPoint d[6];
335
336 int n = SkChopQuadAtYExtrema(s, d);
337 SkDebugf("chop=%d, Y=[%x %x %x %x %x %x]\n", n, d[0].fY, d[1].fY, d[2].fY, d[3].fY, d[4].fY, d[5].fY);
338 }
339#endif
reed@android.com001bd972009-11-17 18:47:52 +0000[diff] [blame]340
reed@android.combcd4d5a2008-12-17 15:59:43 +0000[diff] [blame]341 SkScalar a = src[0].fY;
342 SkScalar b = src[1].fY;
343 SkScalar c = src[2].fY;
reed@android.com001bd972009-11-17 18:47:52 +0000[diff] [blame]344
reed@android.combcd4d5a2008-12-17 15:59:43 +0000[diff] [blame]345 if (is_not_monotonic(a, b, c))
346 {
347 SkScalar tValue;
348 if (valid_unit_divide(a - b, a - b - b + c, &tValue))
349 {
350 SkChopQuadAt(src, dst, tValue);
351 flatten_double_quad_extrema(&dst[0].fY);
352 return 1;
353 }
354 // if we get here, we need to force dst to be monotonic, even though
355 // we couldn't compute a unit_divide value (probably underflow).
356 b = SkScalarAbs(a - b) < SkScalarAbs(b - c) ? a : c;
357 }
358 dst[0].set(src[0].fX, a);
359 dst[1].set(src[1].fX, b);
360 dst[2].set(src[2].fX, c);
361 return 0;
362}
363
reed@android.com001bd972009-11-17 18:47:52 +0000[diff] [blame]364/* Returns 0 for 1 quad, and 1 for two quads, either way the answer is
365 stored in dst[]. Guarantees that the 1/2 quads will be monotonic.
366 */
367int SkChopQuadAtXExtrema(const SkPoint src[3], SkPoint dst[5])
368{
369 SkASSERT(src);
370 SkASSERT(dst);
371
372 SkScalar a = src[0].fX;
373 SkScalar b = src[1].fX;
374 SkScalar c = src[2].fX;
375
376 if (is_not_monotonic(a, b, c)) {
377 SkScalar tValue;
378 if (valid_unit_divide(a - b, a - b - b + c, &tValue)) {
379 SkChopQuadAt(src, dst, tValue);
380 flatten_double_quad_extrema(&dst[0].fX);
381 return 1;
382 }
383 // if we get here, we need to force dst to be monotonic, even though
384 // we couldn't compute a unit_divide value (probably underflow).
385 b = SkScalarAbs(a - b) < SkScalarAbs(b - c) ? a : c;
386 }
387 dst[0].set(a, src[0].fY);
388 dst[1].set(b, src[1].fY);
389 dst[2].set(c, src[2].fY);
390 return 0;
391}
392
reed@android.combcd4d5a2008-12-17 15:59:43 +0000[diff] [blame]393// F(t) = a (1 - t) ^ 2 + 2 b t (1 - t) + c t ^ 2
394// F'(t) = 2 (b - a) + 2 (a - 2b + c) t
395// F''(t) = 2 (a - 2b + c)
396//
397// A = 2 (b - a)
398// B = 2 (a - 2b + c)
399//
400// Maximum curvature for a quadratic means solving
401// Fx' Fx'' + Fy' Fy'' = 0
402//
403// t = - (Ax Bx + Ay By) / (Bx ^ 2 + By ^ 2)
404//
405int SkChopQuadAtMaxCurvature(const SkPoint src[3], SkPoint dst[5])
406{
407 SkScalar Ax = src[1].fX - src[0].fX;
408 SkScalar Ay = src[1].fY - src[0].fY;
409 SkScalar Bx = src[0].fX - src[1].fX - src[1].fX + src[2].fX;
410 SkScalar By = src[0].fY - src[1].fY - src[1].fY + src[2].fY;
411 SkScalar t = 0; // 0 means don't chop
412
413#ifdef SK_SCALAR_IS_FLOAT
414 (void)valid_unit_divide(-(Ax * Bx + Ay * By), Bx * Bx + By * By, &t);
415#else
416 // !!! should I use SkFloat here? seems like it
417 Sk64 numer, denom, tmp;
418
419 numer.setMul(Ax, -Bx);
420 tmp.setMul(Ay, -By);
421 numer.add(tmp);
422
423 if (numer.isPos()) // do nothing if numer <= 0
424 {
425 denom.setMul(Bx, Bx);
426 tmp.setMul(By, By);
427 denom.add(tmp);
428 SkASSERT(!denom.isNeg());
429 if (numer < denom)
430 {
431 t = numer.getFixedDiv(denom);
432 SkASSERT(t >= 0 && t <= SK_Fixed1); // assert that we're numerically stable (ha!)
433 if ((unsigned)t >= SK_Fixed1) // runtime check for numerical stability
434 t = 0; // ignore the chop
435 }
436 }
437#endif
438
439 if (t == 0)
440 {
441 memcpy(dst, src, 3 * sizeof(SkPoint));
442 return 1;
443 }
444 else
445 {
446 SkChopQuadAt(src, dst, t);
447 return 2;
448 }
449}
450
reed@google.com007593e2011-07-27 13:54:36 +0000[diff] [blame^]451#ifdef SK_SCALAR_IS_FLOAT
452 #define SK_ScalarTwoThirds (0.666666666f)
453#else
454 #define SK_ScalarTwoThirds ((SkFixed)(43691))
455#endif
456
457void SkConvertQuadToCubic(const SkPoint src[3], SkPoint dst[4]) {
458 const SkScalar scale = SK_ScalarTwoThirds;
459 dst[0] = src[0];
460 dst[1].set(src[0].fX + SkScalarMul(src[1].fX - src[0].fX, scale),
461 src[0].fY + SkScalarMul(src[1].fY - src[0].fY, scale));
462 dst[2].set(src[2].fX + SkScalarMul(src[1].fX - src[2].fX, scale),
463 src[2].fY + SkScalarMul(src[1].fY - src[2].fY, scale));
464 dst[3] = src[2];
reed@android.com5b4541e2010-02-05 20:41:02 +0000[diff] [blame]465}
466
reed@android.combcd4d5a2008-12-17 15:59:43 +0000[diff] [blame]467////////////////////////////////////////////////////////////////////////////////////////
468///// CUBICS // CUBICS // CUBICS // CUBICS // CUBICS // CUBICS // CUBICS // CUBICS /////
469////////////////////////////////////////////////////////////////////////////////////////
470
471static void get_cubic_coeff(const SkScalar pt[], SkScalar coeff[4])
472{
473 coeff[0] = pt[6] + 3*(pt[2] - pt[4]) - pt[0];
474 coeff[1] = 3*(pt[4] - pt[2] - pt[2] + pt[0]);
475 coeff[2] = 3*(pt[2] - pt[0]);
476 coeff[3] = pt[0];
477}
478
479void SkGetCubicCoeff(const SkPoint pts[4], SkScalar cx[4], SkScalar cy[4])
480{
481 SkASSERT(pts);
482
483 if (cx)
484 get_cubic_coeff(&pts[0].fX, cx);
485 if (cy)
486 get_cubic_coeff(&pts[0].fY, cy);
487}
488
489static SkScalar eval_cubic(const SkScalar src[], SkScalar t)
490{
491 SkASSERT(src);
492 SkASSERT(t >= 0 && t <= SK_Scalar1);
493
494 if (t == 0)
495 return src[0];
496
497#ifdef DIRECT_EVAL_OF_POLYNOMIALS
498 SkScalar D = src[0];
499 SkScalar A = src[6] + 3*(src[2] - src[4]) - D;
500 SkScalar B = 3*(src[4] - src[2] - src[2] + D);
501 SkScalar C = 3*(src[2] - D);
502
503 return SkScalarMulAdd(SkScalarMulAdd(SkScalarMulAdd(A, t, B), t, C), t, D);
504#else
505 SkScalar ab = SkScalarInterp(src[0], src[2], t);
506 SkScalar bc = SkScalarInterp(src[2], src[4], t);
507 SkScalar cd = SkScalarInterp(src[4], src[6], t);
508 SkScalar abc = SkScalarInterp(ab, bc, t);
509 SkScalar bcd = SkScalarInterp(bc, cd, t);
510 return SkScalarInterp(abc, bcd, t);
511#endif
512}
513
514/** return At^2 + Bt + C
515*/
516static SkScalar eval_quadratic(SkScalar A, SkScalar B, SkScalar C, SkScalar t)
517{
518 SkASSERT(t >= 0 && t <= SK_Scalar1);
519
520 return SkScalarMulAdd(SkScalarMulAdd(A, t, B), t, C);
521}
522
523static SkScalar eval_cubic_derivative(const SkScalar src[], SkScalar t)
524{
525 SkScalar A = src[6] + 3*(src[2] - src[4]) - src[0];
526 SkScalar B = 2*(src[4] - 2 * src[2] + src[0]);
527 SkScalar C = src[2] - src[0];
528
529 return eval_quadratic(A, B, C, t);
530}
531
532static SkScalar eval_cubic_2ndDerivative(const SkScalar src[], SkScalar t)
533{
534 SkScalar A = src[6] + 3*(src[2] - src[4]) - src[0];
535 SkScalar B = src[4] - 2 * src[2] + src[0];
536
537 return SkScalarMulAdd(A, t, B);
538}
539
540void SkEvalCubicAt(const SkPoint src[4], SkScalar t, SkPoint* loc, SkVector* tangent, SkVector* curvature)
541{
542 SkASSERT(src);
543 SkASSERT(t >= 0 && t <= SK_Scalar1);
544
545 if (loc)
546 loc->set(eval_cubic(&src[0].fX, t), eval_cubic(&src[0].fY, t));
547 if (tangent)
548 tangent->set(eval_cubic_derivative(&src[0].fX, t),
549 eval_cubic_derivative(&src[0].fY, t));
550 if (curvature)
551 curvature->set(eval_cubic_2ndDerivative(&src[0].fX, t),
552 eval_cubic_2ndDerivative(&src[0].fY, t));
553}
554
555/** Cubic'(t) = At^2 + Bt + C, where
556 A = 3(-a + 3(b - c) + d)
557 B = 6(a - 2b + c)
558 C = 3(b - a)
559 Solve for t, keeping only those that fit betwee 0 < t < 1
560*/
561int SkFindCubicExtrema(SkScalar a, SkScalar b, SkScalar c, SkScalar d, SkScalar tValues[2])
562{
563#ifdef SK_SCALAR_IS_FIXED
564 if (!is_not_monotonic(a, b, c, d))
565 return 0;
566#endif
567
568 // we divide A,B,C by 3 to simplify
569 SkScalar A = d - a + 3*(b - c);
570 SkScalar B = 2*(a - b - b + c);
571 SkScalar C = b - a;
572
573 return SkFindUnitQuadRoots(A, B, C, tValues);
574}
575
576static void interp_cubic_coords(const SkScalar* src, SkScalar* dst, SkScalar t)
577{
578 SkScalar ab = SkScalarInterp(src[0], src[2], t);
579 SkScalar bc = SkScalarInterp(src[2], src[4], t);
580 SkScalar cd = SkScalarInterp(src[4], src[6], t);
581 SkScalar abc = SkScalarInterp(ab, bc, t);
582 SkScalar bcd = SkScalarInterp(bc, cd, t);
583 SkScalar abcd = SkScalarInterp(abc, bcd, t);
584
585 dst[0] = src[0];
586 dst[2] = ab;
587 dst[4] = abc;
588 dst[6] = abcd;
589 dst[8] = bcd;
590 dst[10] = cd;
591 dst[12] = src[6];
592}
593
594void SkChopCubicAt(const SkPoint src[4], SkPoint dst[7], SkScalar t)
595{
596 SkASSERT(t > 0 && t < SK_Scalar1);
597
598 interp_cubic_coords(&src[0].fX, &dst[0].fX, t);
599 interp_cubic_coords(&src[0].fY, &dst[0].fY, t);
600}
601
reed@android.com17bdc092009-08-28 20:06:54 +0000[diff] [blame]602/* http://code.google.com/p/skia/issues/detail?id=32
603
604 This test code would fail when we didn't check the return result of
605 valid_unit_divide in SkChopCubicAt(... tValues[], int roots). The reason is
606 that after the first chop, the parameters to valid_unit_divide are equal
607 (thanks to finite float precision and rounding in the subtracts). Thus
608 even though the 2nd tValue looks < 1.0, after we renormalize it, we end
609 up with 1.0, hence the need to check and just return the last cubic as
610 a degenerate clump of 4 points in the sampe place.
611
612 static void test_cubic() {
613 SkPoint src[4] = {
614 { 556.25000, 523.03003 },
615 { 556.23999, 522.96002 },
616 { 556.21997, 522.89001 },
617 { 556.21997, 522.82001 }
618 };
619 SkPoint dst[10];
620 SkScalar tval[] = { 0.33333334f, 0.99999994f };
621 SkChopCubicAt(src, dst, tval, 2);
622 }
623 */
624
reed@android.combcd4d5a2008-12-17 15:59:43 +0000[diff] [blame]625void SkChopCubicAt(const SkPoint src[4], SkPoint dst[], const SkScalar tValues[], int roots)
626{
627#ifdef SK_DEBUG
628 {
629 for (int i = 0; i < roots - 1; i++)
630 {
631 SkASSERT(is_unit_interval(tValues[i]));
632 SkASSERT(is_unit_interval(tValues[i+1]));
633 SkASSERT(tValues[i] < tValues[i+1]);
634 }
635 }
636#endif
637
638 if (dst)
639 {
640 if (roots == 0) // nothing to chop
641 memcpy(dst, src, 4*sizeof(SkPoint));
642 else
643 {
644 SkScalar t = tValues[0];
645 SkPoint tmp[4];
646
647 for (int i = 0; i < roots; i++)
648 {
649 SkChopCubicAt(src, dst, t);
650 if (i == roots - 1)
651 break;
652
reed@android.combcd4d5a2008-12-17 15:59:43 +0000[diff] [blame]653 dst += 3;
reed@android.com17bdc092009-08-28 20:06:54 +0000[diff] [blame]654 // have src point to the remaining cubic (after the chop)
reed@android.combcd4d5a2008-12-17 15:59:43 +0000[diff] [blame]655 memcpy(tmp, dst, 4 * sizeof(SkPoint));
656 src = tmp;
reed@android.com17bdc092009-08-28 20:06:54 +0000[diff] [blame]657
658 // watch out in case the renormalized t isn't in range
659 if (!valid_unit_divide(tValues[i+1] - tValues[i],
660 SK_Scalar1 - tValues[i], &t)) {
661 // if we can't, just create a degenerate cubic
662 dst[4] = dst[5] = dst[6] = src[3];
663 break;
664 }
reed@android.combcd4d5a2008-12-17 15:59:43 +0000[diff] [blame]665 }
666 }
667 }
668}
669
670void SkChopCubicAtHalf(const SkPoint src[4], SkPoint dst[7])
671{
672 SkScalar x01 = SkScalarAve(src[0].fX, src[1].fX);
673 SkScalar y01 = SkScalarAve(src[0].fY, src[1].fY);
674 SkScalar x12 = SkScalarAve(src[1].fX, src[2].fX);
675 SkScalar y12 = SkScalarAve(src[1].fY, src[2].fY);
676 SkScalar x23 = SkScalarAve(src[2].fX, src[3].fX);
677 SkScalar y23 = SkScalarAve(src[2].fY, src[3].fY);
678
679 SkScalar x012 = SkScalarAve(x01, x12);
680 SkScalar y012 = SkScalarAve(y01, y12);
681 SkScalar x123 = SkScalarAve(x12, x23);
682 SkScalar y123 = SkScalarAve(y12, y23);
683
684 dst[0] = src[0];
685 dst[1].set(x01, y01);
686 dst[2].set(x012, y012);
687 dst[3].set(SkScalarAve(x012, x123), SkScalarAve(y012, y123));
688 dst[4].set(x123, y123);
689 dst[5].set(x23, y23);
690 dst[6] = src[3];
691}
692
693static void flatten_double_cubic_extrema(SkScalar coords[14])
694{
695 coords[4] = coords[8] = coords[6];
696}
697
698/** Given 4 points on a cubic bezier, chop it into 1, 2, 3 beziers such that
699 the resulting beziers are monotonic in Y. This is called by the scan converter.
700 Depending on what is returned, dst[] is treated as follows
701 0 dst[0..3] is the original cubic
702 1 dst[0..3] and dst[3..6] are the two new cubics
703 2 dst[0..3], dst[3..6], dst[6..9] are the three new cubics
704 If dst == null, it is ignored and only the count is returned.
705*/
reed@android.com68779c32009-11-18 13:47:40 +0000[diff] [blame]706int SkChopCubicAtYExtrema(const SkPoint src[4], SkPoint dst[10]) {
reed@android.combcd4d5a2008-12-17 15:59:43 +0000[diff] [blame]707 SkScalar tValues[2];
reed@android.com68779c32009-11-18 13:47:40 +0000[diff] [blame]708 int roots = SkFindCubicExtrema(src[0].fY, src[1].fY, src[2].fY,
709 src[3].fY, tValues);
710
reed@android.combcd4d5a2008-12-17 15:59:43 +0000[diff] [blame]711 SkChopCubicAt(src, dst, tValues, roots);
reed@android.com68779c32009-11-18 13:47:40 +0000[diff] [blame]712 if (dst && roots > 0) {
reed@android.combcd4d5a2008-12-17 15:59:43 +0000[diff] [blame]713 // we do some cleanup to ensure our Y extrema are flat
714 flatten_double_cubic_extrema(&dst[0].fY);
reed@android.com68779c32009-11-18 13:47:40 +0000[diff] [blame]715 if (roots == 2) {
reed@android.combcd4d5a2008-12-17 15:59:43 +0000[diff] [blame]716 flatten_double_cubic_extrema(&dst[3].fY);
reed@android.com68779c32009-11-18 13:47:40 +0000[diff] [blame]717 }
718 }
719 return roots;
720}
721
722int SkChopCubicAtXExtrema(const SkPoint src[4], SkPoint dst[10]) {
723 SkScalar tValues[2];
724 int roots = SkFindCubicExtrema(src[0].fX, src[1].fX, src[2].fX,
725 src[3].fX, tValues);
726
727 SkChopCubicAt(src, dst, tValues, roots);
728 if (dst && roots > 0) {
729 // we do some cleanup to ensure our Y extrema are flat
730 flatten_double_cubic_extrema(&dst[0].fX);
731 if (roots == 2) {
732 flatten_double_cubic_extrema(&dst[3].fX);
733 }
reed@android.combcd4d5a2008-12-17 15:59:43 +0000[diff] [blame]734 }
735 return roots;
736}
737
738/** http://www.faculty.idc.ac.il/arik/quality/appendixA.html
739
740 Inflection means that curvature is zero.
741 Curvature is [F' x F''] / [F'^3]
742 So we solve F'x X F''y - F'y X F''y == 0
743 After some canceling of the cubic term, we get
744 A = b - a
745 B = c - 2b + a
746 C = d - 3c + 3b - a
747 (BxCy - ByCx)t^2 + (AxCy - AyCx)t + AxBy - AyBx == 0
748*/
749int SkFindCubicInflections(const SkPoint src[4], SkScalar tValues[])
750{
751 SkScalar Ax = src[1].fX - src[0].fX;
752 SkScalar Ay = src[1].fY - src[0].fY;
753 SkScalar Bx = src[2].fX - 2 * src[1].fX + src[0].fX;
754 SkScalar By = src[2].fY - 2 * src[1].fY + src[0].fY;
755 SkScalar Cx = src[3].fX + 3 * (src[1].fX - src[2].fX) - src[0].fX;
756 SkScalar Cy = src[3].fY + 3 * (src[1].fY - src[2].fY) - src[0].fY;
757 int count;
758
759#ifdef SK_SCALAR_IS_FLOAT
760 count = SkFindUnitQuadRoots(Bx*Cy - By*Cx, Ax*Cy - Ay*Cx, Ax*By - Ay*Bx, tValues);
761#else
762 Sk64 A, B, C, tmp;
763
764 A.setMul(Bx, Cy);
765 tmp.setMul(By, Cx);
766 A.sub(tmp);
767
768 B.setMul(Ax, Cy);
769 tmp.setMul(Ay, Cx);
770 B.sub(tmp);
771
772 C.setMul(Ax, By);
773 tmp.setMul(Ay, Bx);
774 C.sub(tmp);
775
776 count = Sk64FindFixedQuadRoots(A, B, C, tValues);
777#endif
778
779 return count;
780}
781
782int SkChopCubicAtInflections(const SkPoint src[], SkPoint dst[10])
783{
784 SkScalar tValues[2];
785 int count = SkFindCubicInflections(src, tValues);
786
787 if (dst)
788 {
789 if (count == 0)
790 memcpy(dst, src, 4 * sizeof(SkPoint));
791 else
792 SkChopCubicAt(src, dst, tValues, count);
793 }
794 return count + 1;
795}
796
797template <typename T> void bubble_sort(T array[], int count)
798{
799 for (int i = count - 1; i > 0; --i)
800 for (int j = i; j > 0; --j)
801 if (array[j] < array[j-1])
802 {
803 T tmp(array[j]);
804 array[j] = array[j-1];
805 array[j-1] = tmp;
806 }
807}
808
809#include "SkFP.h"
810
811// newton refinement
812#if 0
813static SkScalar refine_cubic_root(const SkFP coeff[4], SkScalar root)
814{
815 // x1 = x0 - f(t) / f'(t)
816
817 SkFP T = SkScalarToFloat(root);
818 SkFP N, D;
819
820 // f' = 3*coeff[0]*T^2 + 2*coeff[1]*T + coeff[2]
821 D = SkFPMul(SkFPMul(coeff[0], SkFPMul(T,T)), 3);
822 D = SkFPAdd(D, SkFPMulInt(SkFPMul(coeff[1], T), 2));
823 D = SkFPAdd(D, coeff[2]);
824
825 if (D == 0)
826 return root;
827
828 // f = coeff[0]*T^3 + coeff[1]*T^2 + coeff[2]*T + coeff[3]
829 N = SkFPMul(SkFPMul(SkFPMul(T, T), T), coeff[0]);
830 N = SkFPAdd(N, SkFPMul(SkFPMul(T, T), coeff[1]));
831 N = SkFPAdd(N, SkFPMul(T, coeff[2]));
832 N = SkFPAdd(N, coeff[3]);
833
834 if (N)
835 {
836 SkScalar delta = SkFPToScalar(SkFPDiv(N, D));
837
838 if (delta)
839 root -= delta;
840 }
841 return root;
842}
843#endif
844
845#if defined _WIN32 && _MSC_VER >= 1300 && defined SK_SCALAR_IS_FIXED // disable warning : unreachable code if building fixed point for windows desktop
846#pragma warning ( disable : 4702 )
847#endif
848
849/* Solve coeff(t) == 0, returning the number of roots that
850 lie withing 0 < t < 1.
851 coeff[0]t^3 + coeff[1]t^2 + coeff[2]t + coeff[3]
852*/
853static int solve_cubic_polynomial(const SkFP coeff[4], SkScalar tValues[3])
854{
855#ifndef SK_SCALAR_IS_FLOAT
856 return 0; // this is not yet implemented for software float
857#endif
858
859 if (SkScalarNearlyZero(coeff[0])) // we're just a quadratic
860 {
861 return SkFindUnitQuadRoots(coeff[1], coeff[2], coeff[3], tValues);
862 }
863
864 SkFP a, b, c, Q, R;
865
866 {
867 SkASSERT(coeff[0] != 0);
868
869 SkFP inva = SkFPInvert(coeff[0]);
870 a = SkFPMul(coeff[1], inva);
871 b = SkFPMul(coeff[2], inva);
872 c = SkFPMul(coeff[3], inva);
873 }
874 Q = SkFPDivInt(SkFPSub(SkFPMul(a,a), SkFPMulInt(b, 3)), 9);
875// R = (2*a*a*a - 9*a*b + 27*c) / 54;
876 R = SkFPMulInt(SkFPMul(SkFPMul(a, a), a), 2);
877 R = SkFPSub(R, SkFPMulInt(SkFPMul(a, b), 9));
878 R = SkFPAdd(R, SkFPMulInt(c, 27));
879 R = SkFPDivInt(R, 54);
880
881 SkFP Q3 = SkFPMul(SkFPMul(Q, Q), Q);
882 SkFP R2MinusQ3 = SkFPSub(SkFPMul(R,R), Q3);
883 SkFP adiv3 = SkFPDivInt(a, 3);
884
885 SkScalar* roots = tValues;
886 SkScalar r;
887
888 if (SkFPLT(R2MinusQ3, 0)) // we have 3 real roots
889 {
890#ifdef SK_SCALAR_IS_FLOAT
891 float theta = sk_float_acos(R / sk_float_sqrt(Q3));
892 float neg2RootQ = -2 * sk_float_sqrt(Q);
893
894 r = neg2RootQ * sk_float_cos(theta/3) - adiv3;
895 if (is_unit_interval(r))
896 *roots++ = r;
897
898 r = neg2RootQ * sk_float_cos((theta + 2*SK_ScalarPI)/3) - adiv3;
899 if (is_unit_interval(r))
900 *roots++ = r;
901
902 r = neg2RootQ * sk_float_cos((theta - 2*SK_ScalarPI)/3) - adiv3;
903 if (is_unit_interval(r))
904 *roots++ = r;
905
906 // now sort the roots
907 bubble_sort(tValues, (int)(roots - tValues));
908#endif
909 }
910 else // we have 1 real root
911 {
912 SkFP A = SkFPAdd(SkFPAbs(R), SkFPSqrt(R2MinusQ3));
913 A = SkFPCubeRoot(A);
914 if (SkFPGT(R, 0))
915 A = SkFPNeg(A);
916
917 if (A != 0)
918 A = SkFPAdd(A, SkFPDiv(Q, A));
919 r = SkFPToScalar(SkFPSub(A, adiv3));
920 if (is_unit_interval(r))
921 *roots++ = r;
922 }
923
924 return (int)(roots - tValues);
925}
926
927/* Looking for F' dot F'' == 0
928
929 A = b - a
930 B = c - 2b + a
931 C = d - 3c + 3b - a
932
933 F' = 3Ct^2 + 6Bt + 3A
934 F'' = 6Ct + 6B
935
936 F' dot F'' -> CCt^3 + 3BCt^2 + (2BB + CA)t + AB
937*/
938static void formulate_F1DotF2(const SkScalar src[], SkFP coeff[4])
939{
940 SkScalar a = src[2] - src[0];
941 SkScalar b = src[4] - 2 * src[2] + src[0];
942 SkScalar c = src[6] + 3 * (src[2] - src[4]) - src[0];
943
944 SkFP A = SkScalarToFP(a);
945 SkFP B = SkScalarToFP(b);
946 SkFP C = SkScalarToFP(c);
947
948 coeff[0] = SkFPMul(C, C);
949 coeff[1] = SkFPMulInt(SkFPMul(B, C), 3);
950 coeff[2] = SkFPMulInt(SkFPMul(B, B), 2);
951 coeff[2] = SkFPAdd(coeff[2], SkFPMul(C, A));
952 coeff[3] = SkFPMul(A, B);
953}
954
955// EXPERIMENTAL: can set this to zero to accept all t-values 0 < t < 1
956//#define kMinTValueForChopping (SK_Scalar1 / 256)
957#define kMinTValueForChopping 0
958
959/* Looking for F' dot F'' == 0
960
961 A = b - a
962 B = c - 2b + a
963 C = d - 3c + 3b - a
964
965 F' = 3Ct^2 + 6Bt + 3A
966 F'' = 6Ct + 6B
967
968 F' dot F'' -> CCt^3 + 3BCt^2 + (2BB + CA)t + AB
969*/
970int SkFindCubicMaxCurvature(const SkPoint src[4], SkScalar tValues[3])
971{
972 SkFP coeffX[4], coeffY[4];
973 int i;
974
975 formulate_F1DotF2(&src[0].fX, coeffX);
976 formulate_F1DotF2(&src[0].fY, coeffY);
977
978 for (i = 0; i < 4; i++)
979 coeffX[i] = SkFPAdd(coeffX[i],coeffY[i]);
980
981 SkScalar t[3];
982 int count = solve_cubic_polynomial(coeffX, t);
983 int maxCount = 0;
984
985 // now remove extrema where the curvature is zero (mins)
986 // !!!! need a test for this !!!!
987 for (i = 0; i < count; i++)
988 {
989 // if (not_min_curvature())
990 if (t[i] > kMinTValueForChopping && t[i] < SK_Scalar1 - kMinTValueForChopping)
991 tValues[maxCount++] = t[i];
992 }
993 return maxCount;
994}
995
996int SkChopCubicAtMaxCurvature(const SkPoint src[4], SkPoint dst[13], SkScalar tValues[3])
997{
998 SkScalar t_storage[3];
999
1000 if (tValues == NULL)
1001 tValues = t_storage;
1002
1003 int count = SkFindCubicMaxCurvature(src, tValues);
1004
1005 if (dst)
1006 {
1007 if (count == 0)
1008 memcpy(dst, src, 4 * sizeof(SkPoint));
1009 else
1010 SkChopCubicAt(src, dst, tValues, count);
1011 }
1012 return count + 1;
1013}
1014
kbr@chromium.orgc1b53332010-07-07 22:20:35 +0000[diff] [blame]1015bool SkXRayCrossesMonotonicCubic(const SkXRay& pt, const SkPoint cubic[4], bool* ambiguous) {
1016 if (ambiguous) {
1017 *ambiguous = false;
1018 }
1019
reed@android.com5b4541e2010-02-05 20:41:02 +0000[diff] [blame]1020 // Find the minimum and maximum y of the extrema, which are the
1021 // first and last points since this cubic is monotonic
1022 SkScalar min_y = SkMinScalar(cubic[0].fY, cubic[3].fY);
1023 SkScalar max_y = SkMaxScalar(cubic[0].fY, cubic[3].fY);
1024
1025 if (pt.fY == cubic[0].fY
1026 || pt.fY < min_y
1027 || pt.fY > max_y) {
1028 // The query line definitely does not cross the curve
kbr@chromium.orgc1b53332010-07-07 22:20:35 +0000[diff] [blame]1029 if (ambiguous) {
1030 *ambiguous = (pt.fY == cubic[0].fY);
1031 }
reed@android.com5b4541e2010-02-05 20:41:02 +0000[diff] [blame]1032 return false;
1033 }
1034
kbr@chromium.orgc1b53332010-07-07 22:20:35 +0000[diff] [blame]1035 bool pt_at_extremum = (pt.fY == cubic[3].fY);
1036
reed@android.com5b4541e2010-02-05 20:41:02 +0000[diff] [blame]1037 SkScalar min_x =
1038 SkMinScalar(
1039 SkMinScalar(
1040 SkMinScalar(cubic[0].fX, cubic[1].fX),
1041 cubic[2].fX),
1042 cubic[3].fX);
1043 if (pt.fX < min_x) {
1044 // The query line definitely crosses the curve
kbr@chromium.orgc1b53332010-07-07 22:20:35 +0000[diff] [blame]1045 if (ambiguous) {
1046 *ambiguous = pt_at_extremum;
1047 }
reed@android.com5b4541e2010-02-05 20:41:02 +0000[diff] [blame]1048 return true;
1049 }
1050
1051 SkScalar max_x =
1052 SkMaxScalar(
1053 SkMaxScalar(
1054 SkMaxScalar(cubic[0].fX, cubic[1].fX),
1055 cubic[2].fX),
1056 cubic[3].fX);
1057 if (pt.fX > max_x) {
1058 // The query line definitely does not cross the curve
1059 return false;
1060 }
1061
1062 // Do a binary search to find the parameter value which makes y as
1063 // close as possible to the query point. See whether the query
1064 // line's origin is to the left of the associated x coordinate.
1065
1066 // kMaxIter is chosen as the number of mantissa bits for a float,
1067 // since there's no way we are going to get more precision by
1068 // iterating more times than that.
1069 const int kMaxIter = 23;
1070 SkPoint eval;
1071 int iter = 0;
1072 SkScalar upper_t;
1073 SkScalar lower_t;
1074 // Need to invert direction of t parameter if cubic goes up
1075 // instead of down
1076 if (cubic[3].fY > cubic[0].fY) {
1077 upper_t = SK_Scalar1;
1078 lower_t = SkFloatToScalar(0);
1079 } else {
1080 upper_t = SkFloatToScalar(0);
1081 lower_t = SK_Scalar1;
1082 }
1083 do {
1084 SkScalar t = SkScalarAve(upper_t, lower_t);
1085 SkEvalCubicAt(cubic, t, &eval, NULL, NULL);
1086 if (pt.fY > eval.fY) {
1087 lower_t = t;
1088 } else {
1089 upper_t = t;
1090 }
1091 } while (++iter < kMaxIter
1092 && !SkScalarNearlyZero(eval.fY - pt.fY));
1093 if (pt.fX <= eval.fX) {
kbr@chromium.orgc1b53332010-07-07 22:20:35 +0000[diff] [blame]1094 if (ambiguous) {
1095 *ambiguous = pt_at_extremum;
1096 }
reed@android.com5b4541e2010-02-05 20:41:02 +0000[diff] [blame]1097 return true;
1098 }
1099 return false;
1100}
1101
kbr@chromium.orgc1b53332010-07-07 22:20:35 +0000[diff] [blame]1102int SkNumXRayCrossingsForCubic(const SkXRay& pt, const SkPoint cubic[4], bool* ambiguous) {
reed@android.com5b4541e2010-02-05 20:41:02 +0000[diff] [blame]1103 int num_crossings = 0;
1104 SkPoint monotonic_cubics[10];
1105 int num_monotonic_cubics = SkChopCubicAtYExtrema(cubic, monotonic_cubics);
kbr@chromium.orgc1b53332010-07-07 22:20:35 +0000[diff] [blame]1106 if (ambiguous) {
1107 *ambiguous = false;
1108 }
1109 bool locally_ambiguous;
1110 if (SkXRayCrossesMonotonicCubic(pt, &monotonic_cubics[0], &locally_ambiguous))
reed@android.com5b4541e2010-02-05 20:41:02 +0000[diff] [blame]1111 ++num_crossings;
kbr@chromium.orgc1b53332010-07-07 22:20:35 +0000[diff] [blame]1112 if (ambiguous) {
1113 *ambiguous |= locally_ambiguous;
1114 }
reed@android.com5b4541e2010-02-05 20:41:02 +0000[diff] [blame]1115 if (num_monotonic_cubics > 0)
kbr@chromium.orgc1b53332010-07-07 22:20:35 +0000[diff] [blame]1116 if (SkXRayCrossesMonotonicCubic(pt, &monotonic_cubics[3], &locally_ambiguous))
reed@android.com5b4541e2010-02-05 20:41:02 +0000[diff] [blame]1117 ++num_crossings;
kbr@chromium.orgc1b53332010-07-07 22:20:35 +0000[diff] [blame]1118 if (ambiguous) {
1119 *ambiguous |= locally_ambiguous;
1120 }
reed@android.com5b4541e2010-02-05 20:41:02 +0000[diff] [blame]1121 if (num_monotonic_cubics > 1)
kbr@chromium.orgc1b53332010-07-07 22:20:35 +0000[diff] [blame]1122 if (SkXRayCrossesMonotonicCubic(pt, &monotonic_cubics[6], &locally_ambiguous))
reed@android.com5b4541e2010-02-05 20:41:02 +0000[diff] [blame]1123 ++num_crossings;
kbr@chromium.orgc1b53332010-07-07 22:20:35 +0000[diff] [blame]1124 if (ambiguous) {
1125 *ambiguous |= locally_ambiguous;
1126 }
reed@android.com5b4541e2010-02-05 20:41:02 +0000[diff] [blame]1127 return num_crossings;
1128}
1129
reed@android.combcd4d5a2008-12-17 15:59:43 +0000[diff] [blame]1130////////////////////////////////////////////////////////////////////////////////
1131
1132/* Find t value for quadratic [a, b, c] = d.
1133 Return 0 if there is no solution within [0, 1)
1134*/
1135static SkScalar quad_solve(SkScalar a, SkScalar b, SkScalar c, SkScalar d)
1136{
1137 // At^2 + Bt + C = d
1138 SkScalar A = a - 2 * b + c;
1139 SkScalar B = 2 * (b - a);
1140 SkScalar C = a - d;
1141
1142 SkScalar roots[2];
1143 int count = SkFindUnitQuadRoots(A, B, C, roots);
1144
1145 SkASSERT(count <= 1);
1146 return count == 1 ? roots[0] : 0;
1147}
1148
1149/* given a quad-curve and a point (x,y), chop the quad at that point and return
1150 the new quad's offCurve point. Should only return false if the computed pos
1151 is the start of the curve (i.e. root == 0)
1152*/
1153static bool quad_pt2OffCurve(const SkPoint quad[3], SkScalar x, SkScalar y, SkPoint* offCurve)
1154{
1155 const SkScalar* base;
1156 SkScalar value;
1157
1158 if (SkScalarAbs(x) < SkScalarAbs(y)) {
1159 base = &quad[0].fX;
1160 value = x;
1161 } else {
1162 base = &quad[0].fY;
1163 value = y;
1164 }
1165
1166 // note: this returns 0 if it thinks value is out of range, meaning the
1167 // root might return something outside of [0, 1)
1168 SkScalar t = quad_solve(base[0], base[2], base[4], value);
1169
1170 if (t > 0)
1171 {
1172 SkPoint tmp[5];
1173 SkChopQuadAt(quad, tmp, t);
1174 *offCurve = tmp[1];
1175 return true;
1176 } else {
1177 /* t == 0 means either the value triggered a root outside of [0, 1)
1178 For our purposes, we can ignore the <= 0 roots, but we want to
1179 catch the >= 1 roots (which given our caller, will basically mean
1180 a root of 1, give-or-take numerical instability). If we are in the
1181 >= 1 case, return the existing offCurve point.
1182
1183 The test below checks to see if we are close to the "end" of the
1184 curve (near base[4]). Rather than specifying a tolerance, I just
1185 check to see if value is on to the right/left of the middle point
1186 (depending on the direction/sign of the end points).
1187 */
1188 if ((base[0] < base[4] && value > base[2]) ||
1189 (base[0] > base[4] && value < base[2])) // should root have been 1
1190 {
1191 *offCurve = quad[1];
1192 return true;
1193 }
1194 }
1195 return false;
1196}
1197
1198static const SkPoint gQuadCirclePts[kSkBuildQuadArcStorage] = {
1199 { SK_Scalar1, 0 },
1200 { SK_Scalar1, SK_ScalarTanPIOver8 },
1201 { SK_ScalarRoot2Over2, SK_ScalarRoot2Over2 },
1202 { SK_ScalarTanPIOver8, SK_Scalar1 },
1203
1204 { 0, SK_Scalar1 },
1205 { -SK_ScalarTanPIOver8, SK_Scalar1 },
1206 { -SK_ScalarRoot2Over2, SK_ScalarRoot2Over2 },
1207 { -SK_Scalar1, SK_ScalarTanPIOver8 },
1208
1209 { -SK_Scalar1, 0 },
1210 { -SK_Scalar1, -SK_ScalarTanPIOver8 },
1211 { -SK_ScalarRoot2Over2, -SK_ScalarRoot2Over2 },
1212 { -SK_ScalarTanPIOver8, -SK_Scalar1 },
1213
1214 { 0, -SK_Scalar1 },
1215 { SK_ScalarTanPIOver8, -SK_Scalar1 },
1216 { SK_ScalarRoot2Over2, -SK_ScalarRoot2Over2 },
1217 { SK_Scalar1, -SK_ScalarTanPIOver8 },
1218
1219 { SK_Scalar1, 0 }
1220};
1221
1222int SkBuildQuadArc(const SkVector& uStart, const SkVector& uStop,
1223 SkRotationDirection dir, const SkMatrix* userMatrix,
1224 SkPoint quadPoints[])
1225{
1226 // rotate by x,y so that uStart is (1.0)
1227 SkScalar x = SkPoint::DotProduct(uStart, uStop);
1228 SkScalar y = SkPoint::CrossProduct(uStart, uStop);
1229
1230 SkScalar absX = SkScalarAbs(x);
1231 SkScalar absY = SkScalarAbs(y);
1232
1233 int pointCount;
1234
1235 // check for (effectively) coincident vectors
1236 // this can happen if our angle is nearly 0 or nearly 180 (y == 0)
1237 // ... we use the dot-prod to distinguish between 0 and 180 (x > 0)
1238 if (absY <= SK_ScalarNearlyZero && x > 0 &&
1239 ((y >= 0 && kCW_SkRotationDirection == dir) ||
1240 (y <= 0 && kCCW_SkRotationDirection == dir))) {
1241
1242 // just return the start-point
1243 quadPoints[0].set(SK_Scalar1, 0);
1244 pointCount = 1;
1245 } else {
1246 if (dir == kCCW_SkRotationDirection)
1247 y = -y;
1248
1249 // what octant (quadratic curve) is [xy] in?
1250 int oct = 0;
1251 bool sameSign = true;
1252
1253 if (0 == y)
1254 {
1255 oct = 4; // 180
1256 SkASSERT(SkScalarAbs(x + SK_Scalar1) <= SK_ScalarNearlyZero);
1257 }
1258 else if (0 == x)
1259 {
1260 SkASSERT(absY - SK_Scalar1 <= SK_ScalarNearlyZero);
1261 if (y > 0)
1262 oct = 2; // 90
1263 else
1264 oct = 6; // 270
1265 }
1266 else
1267 {
1268 if (y < 0)
1269 oct += 4;
1270 if ((x < 0) != (y < 0))
1271 {
1272 oct += 2;
1273 sameSign = false;
1274 }
1275 if ((absX < absY) == sameSign)
1276 oct += 1;
1277 }
1278
1279 int wholeCount = oct << 1;
1280 memcpy(quadPoints, gQuadCirclePts, (wholeCount + 1) * sizeof(SkPoint));
1281
1282 const SkPoint* arc = &gQuadCirclePts[wholeCount];
1283 if (quad_pt2OffCurve(arc, x, y, &quadPoints[wholeCount + 1]))
1284 {
1285 quadPoints[wholeCount + 2].set(x, y);
1286 wholeCount += 2;
1287 }
1288 pointCount = wholeCount + 1;
1289 }
1290
1291 // now handle counter-clockwise and the initial unitStart rotation
1292 SkMatrix matrix;
1293 matrix.setSinCos(uStart.fY, uStart.fX);
1294 if (dir == kCCW_SkRotationDirection) {
1295 matrix.preScale(SK_Scalar1, -SK_Scalar1);
1296 }
1297 if (userMatrix) {
1298 matrix.postConcat(*userMatrix);
1299 }
1300 matrix.mapPoints(quadPoints, pointCount);
1301 return pointCount;
1302}
1303