[go: nahoru, domu]
Google Git
Sign in
android / platform / external / chromium_org / third_party / skia / src / c1b5333cdd9d14ac84609ec3dc6aa479cb7597cb / . / core / SkGeometry.cpp
blob: 3c9e9f90f0ed94b63ee475b09ffc83d2c88c9b90 [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@android.com5b4541e2010-02-05 20:41:02 +0000[diff] [blame]451void SkConvertQuadToCubic(const SkPoint src[3], SkPoint dst[4])
452{
453 SkScalar two = SkIntToScalar(2);
454 SkScalar one_third = SkScalarDiv(SK_Scalar1, SkIntToScalar(3));
455 dst[0].set(src[0].fX, src[0].fY);
456 dst[1].set(
457 SkScalarMul(SkScalarMulAdd(src[1].fX, two, src[0].fX), one_third),
458 SkScalarMul(SkScalarMulAdd(src[1].fY, two, src[0].fY), one_third));
459 dst[2].set(
460 SkScalarMul(SkScalarMulAdd(src[1].fX, two, src[2].fX), one_third),
461 SkScalarMul(SkScalarMulAdd(src[1].fY, two, src[2].fY), one_third));
462 dst[3].set(src[2].fX, src[2].fY);
463}
464
reed@android.combcd4d5a2008-12-17 15:59:43 +0000[diff] [blame]465////////////////////////////////////////////////////////////////////////////////////////
466///// CUBICS // CUBICS // CUBICS // CUBICS // CUBICS // CUBICS // CUBICS // CUBICS /////
467////////////////////////////////////////////////////////////////////////////////////////
468
469static void get_cubic_coeff(const SkScalar pt[], SkScalar coeff[4])
470{
471 coeff[0] = pt[6] + 3*(pt[2] - pt[4]) - pt[0];
472 coeff[1] = 3*(pt[4] - pt[2] - pt[2] + pt[0]);
473 coeff[2] = 3*(pt[2] - pt[0]);
474 coeff[3] = pt[0];
475}
476
477void SkGetCubicCoeff(const SkPoint pts[4], SkScalar cx[4], SkScalar cy[4])
478{
479 SkASSERT(pts);
480
481 if (cx)
482 get_cubic_coeff(&pts[0].fX, cx);
483 if (cy)
484 get_cubic_coeff(&pts[0].fY, cy);
485}
486
487static SkScalar eval_cubic(const SkScalar src[], SkScalar t)
488{
489 SkASSERT(src);
490 SkASSERT(t >= 0 && t <= SK_Scalar1);
491
492 if (t == 0)
493 return src[0];
494
495#ifdef DIRECT_EVAL_OF_POLYNOMIALS
496 SkScalar D = src[0];
497 SkScalar A = src[6] + 3*(src[2] - src[4]) - D;
498 SkScalar B = 3*(src[4] - src[2] - src[2] + D);
499 SkScalar C = 3*(src[2] - D);
500
501 return SkScalarMulAdd(SkScalarMulAdd(SkScalarMulAdd(A, t, B), t, C), t, D);
502#else
503 SkScalar ab = SkScalarInterp(src[0], src[2], t);
504 SkScalar bc = SkScalarInterp(src[2], src[4], t);
505 SkScalar cd = SkScalarInterp(src[4], src[6], t);
506 SkScalar abc = SkScalarInterp(ab, bc, t);
507 SkScalar bcd = SkScalarInterp(bc, cd, t);
508 return SkScalarInterp(abc, bcd, t);
509#endif
510}
511
512/** return At^2 + Bt + C
513*/
514static SkScalar eval_quadratic(SkScalar A, SkScalar B, SkScalar C, SkScalar t)
515{
516 SkASSERT(t >= 0 && t <= SK_Scalar1);
517
518 return SkScalarMulAdd(SkScalarMulAdd(A, t, B), t, C);
519}
520
521static SkScalar eval_cubic_derivative(const SkScalar src[], SkScalar t)
522{
523 SkScalar A = src[6] + 3*(src[2] - src[4]) - src[0];
524 SkScalar B = 2*(src[4] - 2 * src[2] + src[0]);
525 SkScalar C = src[2] - src[0];
526
527 return eval_quadratic(A, B, C, t);
528}
529
530static SkScalar eval_cubic_2ndDerivative(const SkScalar src[], SkScalar t)
531{
532 SkScalar A = src[6] + 3*(src[2] - src[4]) - src[0];
533 SkScalar B = src[4] - 2 * src[2] + src[0];
534
535 return SkScalarMulAdd(A, t, B);
536}
537
538void SkEvalCubicAt(const SkPoint src[4], SkScalar t, SkPoint* loc, SkVector* tangent, SkVector* curvature)
539{
540 SkASSERT(src);
541 SkASSERT(t >= 0 && t <= SK_Scalar1);
542
543 if (loc)
544 loc->set(eval_cubic(&src[0].fX, t), eval_cubic(&src[0].fY, t));
545 if (tangent)
546 tangent->set(eval_cubic_derivative(&src[0].fX, t),
547 eval_cubic_derivative(&src[0].fY, t));
548 if (curvature)
549 curvature->set(eval_cubic_2ndDerivative(&src[0].fX, t),
550 eval_cubic_2ndDerivative(&src[0].fY, t));
551}
552
553/** Cubic'(t) = At^2 + Bt + C, where
554 A = 3(-a + 3(b - c) + d)
555 B = 6(a - 2b + c)
556 C = 3(b - a)
557 Solve for t, keeping only those that fit betwee 0 < t < 1
558*/
559int SkFindCubicExtrema(SkScalar a, SkScalar b, SkScalar c, SkScalar d, SkScalar tValues[2])
560{
561#ifdef SK_SCALAR_IS_FIXED
562 if (!is_not_monotonic(a, b, c, d))
563 return 0;
564#endif
565
566 // we divide A,B,C by 3 to simplify
567 SkScalar A = d - a + 3*(b - c);
568 SkScalar B = 2*(a - b - b + c);
569 SkScalar C = b - a;
570
571 return SkFindUnitQuadRoots(A, B, C, tValues);
572}
573
574static void interp_cubic_coords(const SkScalar* src, SkScalar* dst, SkScalar t)
575{
576 SkScalar ab = SkScalarInterp(src[0], src[2], t);
577 SkScalar bc = SkScalarInterp(src[2], src[4], t);
578 SkScalar cd = SkScalarInterp(src[4], src[6], t);
579 SkScalar abc = SkScalarInterp(ab, bc, t);
580 SkScalar bcd = SkScalarInterp(bc, cd, t);
581 SkScalar abcd = SkScalarInterp(abc, bcd, t);
582
583 dst[0] = src[0];
584 dst[2] = ab;
585 dst[4] = abc;
586 dst[6] = abcd;
587 dst[8] = bcd;
588 dst[10] = cd;
589 dst[12] = src[6];
590}
591
592void SkChopCubicAt(const SkPoint src[4], SkPoint dst[7], SkScalar t)
593{
594 SkASSERT(t > 0 && t < SK_Scalar1);
595
596 interp_cubic_coords(&src[0].fX, &dst[0].fX, t);
597 interp_cubic_coords(&src[0].fY, &dst[0].fY, t);
598}
599
reed@android.com17bdc092009-08-28 20:06:54 +0000[diff] [blame]600/* http://code.google.com/p/skia/issues/detail?id=32
601
602 This test code would fail when we didn't check the return result of
603 valid_unit_divide in SkChopCubicAt(... tValues[], int roots). The reason is
604 that after the first chop, the parameters to valid_unit_divide are equal
605 (thanks to finite float precision and rounding in the subtracts). Thus
606 even though the 2nd tValue looks < 1.0, after we renormalize it, we end
607 up with 1.0, hence the need to check and just return the last cubic as
608 a degenerate clump of 4 points in the sampe place.
609
610 static void test_cubic() {
611 SkPoint src[4] = {
612 { 556.25000, 523.03003 },
613 { 556.23999, 522.96002 },
614 { 556.21997, 522.89001 },
615 { 556.21997, 522.82001 }
616 };
617 SkPoint dst[10];
618 SkScalar tval[] = { 0.33333334f, 0.99999994f };
619 SkChopCubicAt(src, dst, tval, 2);
620 }
621 */
622
reed@android.combcd4d5a2008-12-17 15:59:43 +0000[diff] [blame]623void SkChopCubicAt(const SkPoint src[4], SkPoint dst[], const SkScalar tValues[], int roots)
624{
625#ifdef SK_DEBUG
626 {
627 for (int i = 0; i < roots - 1; i++)
628 {
629 SkASSERT(is_unit_interval(tValues[i]));
630 SkASSERT(is_unit_interval(tValues[i+1]));
631 SkASSERT(tValues[i] < tValues[i+1]);
632 }
633 }
634#endif
635
636 if (dst)
637 {
638 if (roots == 0) // nothing to chop
639 memcpy(dst, src, 4*sizeof(SkPoint));
640 else
641 {
642 SkScalar t = tValues[0];
643 SkPoint tmp[4];
644
645 for (int i = 0; i < roots; i++)
646 {
647 SkChopCubicAt(src, dst, t);
648 if (i == roots - 1)
649 break;
650
reed@android.combcd4d5a2008-12-17 15:59:43 +0000[diff] [blame]651 dst += 3;
reed@android.com17bdc092009-08-28 20:06:54 +0000[diff] [blame]652 // have src point to the remaining cubic (after the chop)
reed@android.combcd4d5a2008-12-17 15:59:43 +0000[diff] [blame]653 memcpy(tmp, dst, 4 * sizeof(SkPoint));
654 src = tmp;
reed@android.com17bdc092009-08-28 20:06:54 +0000[diff] [blame]655
656 // watch out in case the renormalized t isn't in range
657 if (!valid_unit_divide(tValues[i+1] - tValues[i],
658 SK_Scalar1 - tValues[i], &t)) {
659 // if we can't, just create a degenerate cubic
660 dst[4] = dst[5] = dst[6] = src[3];
661 break;
662 }
reed@android.combcd4d5a2008-12-17 15:59:43 +0000[diff] [blame]663 }
664 }
665 }
666}
667
668void SkChopCubicAtHalf(const SkPoint src[4], SkPoint dst[7])
669{
670 SkScalar x01 = SkScalarAve(src[0].fX, src[1].fX);
671 SkScalar y01 = SkScalarAve(src[0].fY, src[1].fY);
672 SkScalar x12 = SkScalarAve(src[1].fX, src[2].fX);
673 SkScalar y12 = SkScalarAve(src[1].fY, src[2].fY);
674 SkScalar x23 = SkScalarAve(src[2].fX, src[3].fX);
675 SkScalar y23 = SkScalarAve(src[2].fY, src[3].fY);
676
677 SkScalar x012 = SkScalarAve(x01, x12);
678 SkScalar y012 = SkScalarAve(y01, y12);
679 SkScalar x123 = SkScalarAve(x12, x23);
680 SkScalar y123 = SkScalarAve(y12, y23);
681
682 dst[0] = src[0];
683 dst[1].set(x01, y01);
684 dst[2].set(x012, y012);
685 dst[3].set(SkScalarAve(x012, x123), SkScalarAve(y012, y123));
686 dst[4].set(x123, y123);
687 dst[5].set(x23, y23);
688 dst[6] = src[3];
689}
690
691static void flatten_double_cubic_extrema(SkScalar coords[14])
692{
693 coords[4] = coords[8] = coords[6];
694}
695
696/** Given 4 points on a cubic bezier, chop it into 1, 2, 3 beziers such that
697 the resulting beziers are monotonic in Y. This is called by the scan converter.
698 Depending on what is returned, dst[] is treated as follows
699 0 dst[0..3] is the original cubic
700 1 dst[0..3] and dst[3..6] are the two new cubics
701 2 dst[0..3], dst[3..6], dst[6..9] are the three new cubics
702 If dst == null, it is ignored and only the count is returned.
703*/
reed@android.com68779c32009-11-18 13:47:40 +0000[diff] [blame]704int SkChopCubicAtYExtrema(const SkPoint src[4], SkPoint dst[10]) {
reed@android.combcd4d5a2008-12-17 15:59:43 +0000[diff] [blame]705 SkScalar tValues[2];
reed@android.com68779c32009-11-18 13:47:40 +0000[diff] [blame]706 int roots = SkFindCubicExtrema(src[0].fY, src[1].fY, src[2].fY,
707 src[3].fY, tValues);
708
reed@android.combcd4d5a2008-12-17 15:59:43 +0000[diff] [blame]709 SkChopCubicAt(src, dst, tValues, roots);
reed@android.com68779c32009-11-18 13:47:40 +0000[diff] [blame]710 if (dst && roots > 0) {
reed@android.combcd4d5a2008-12-17 15:59:43 +0000[diff] [blame]711 // we do some cleanup to ensure our Y extrema are flat
712 flatten_double_cubic_extrema(&dst[0].fY);
reed@android.com68779c32009-11-18 13:47:40 +0000[diff] [blame]713 if (roots == 2) {
reed@android.combcd4d5a2008-12-17 15:59:43 +0000[diff] [blame]714 flatten_double_cubic_extrema(&dst[3].fY);
reed@android.com68779c32009-11-18 13:47:40 +0000[diff] [blame]715 }
716 }
717 return roots;
718}
719
720int SkChopCubicAtXExtrema(const SkPoint src[4], SkPoint dst[10]) {
721 SkScalar tValues[2];
722 int roots = SkFindCubicExtrema(src[0].fX, src[1].fX, src[2].fX,
723 src[3].fX, tValues);
724
725 SkChopCubicAt(src, dst, tValues, roots);
726 if (dst && roots > 0) {
727 // we do some cleanup to ensure our Y extrema are flat
728 flatten_double_cubic_extrema(&dst[0].fX);
729 if (roots == 2) {
730 flatten_double_cubic_extrema(&dst[3].fX);
731 }
reed@android.combcd4d5a2008-12-17 15:59:43 +0000[diff] [blame]732 }
733 return roots;
734}
735
736/** http://www.faculty.idc.ac.il/arik/quality/appendixA.html
737
738 Inflection means that curvature is zero.
739 Curvature is [F' x F''] / [F'^3]
740 So we solve F'x X F''y - F'y X F''y == 0
741 After some canceling of the cubic term, we get
742 A = b - a
743 B = c - 2b + a
744 C = d - 3c + 3b - a
745 (BxCy - ByCx)t^2 + (AxCy - AyCx)t + AxBy - AyBx == 0
746*/
747int SkFindCubicInflections(const SkPoint src[4], SkScalar tValues[])
748{
749 SkScalar Ax = src[1].fX - src[0].fX;
750 SkScalar Ay = src[1].fY - src[0].fY;
751 SkScalar Bx = src[2].fX - 2 * src[1].fX + src[0].fX;
752 SkScalar By = src[2].fY - 2 * src[1].fY + src[0].fY;
753 SkScalar Cx = src[3].fX + 3 * (src[1].fX - src[2].fX) - src[0].fX;
754 SkScalar Cy = src[3].fY + 3 * (src[1].fY - src[2].fY) - src[0].fY;
755 int count;
756
757#ifdef SK_SCALAR_IS_FLOAT
758 count = SkFindUnitQuadRoots(Bx*Cy - By*Cx, Ax*Cy - Ay*Cx, Ax*By - Ay*Bx, tValues);
759#else
760 Sk64 A, B, C, tmp;
761
762 A.setMul(Bx, Cy);
763 tmp.setMul(By, Cx);
764 A.sub(tmp);
765
766 B.setMul(Ax, Cy);
767 tmp.setMul(Ay, Cx);
768 B.sub(tmp);
769
770 C.setMul(Ax, By);
771 tmp.setMul(Ay, Bx);
772 C.sub(tmp);
773
774 count = Sk64FindFixedQuadRoots(A, B, C, tValues);
775#endif
776
777 return count;
778}
779
780int SkChopCubicAtInflections(const SkPoint src[], SkPoint dst[10])
781{
782 SkScalar tValues[2];
783 int count = SkFindCubicInflections(src, tValues);
784
785 if (dst)
786 {
787 if (count == 0)
788 memcpy(dst, src, 4 * sizeof(SkPoint));
789 else
790 SkChopCubicAt(src, dst, tValues, count);
791 }
792 return count + 1;
793}
794
795template <typename T> void bubble_sort(T array[], int count)
796{
797 for (int i = count - 1; i > 0; --i)
798 for (int j = i; j > 0; --j)
799 if (array[j] < array[j-1])
800 {
801 T tmp(array[j]);
802 array[j] = array[j-1];
803 array[j-1] = tmp;
804 }
805}
806
807#include "SkFP.h"
808
809// newton refinement
810#if 0
811static SkScalar refine_cubic_root(const SkFP coeff[4], SkScalar root)
812{
813 // x1 = x0 - f(t) / f'(t)
814
815 SkFP T = SkScalarToFloat(root);
816 SkFP N, D;
817
818 // f' = 3*coeff[0]*T^2 + 2*coeff[1]*T + coeff[2]
819 D = SkFPMul(SkFPMul(coeff[0], SkFPMul(T,T)), 3);
820 D = SkFPAdd(D, SkFPMulInt(SkFPMul(coeff[1], T), 2));
821 D = SkFPAdd(D, coeff[2]);
822
823 if (D == 0)
824 return root;
825
826 // f = coeff[0]*T^3 + coeff[1]*T^2 + coeff[2]*T + coeff[3]
827 N = SkFPMul(SkFPMul(SkFPMul(T, T), T), coeff[0]);
828 N = SkFPAdd(N, SkFPMul(SkFPMul(T, T), coeff[1]));
829 N = SkFPAdd(N, SkFPMul(T, coeff[2]));
830 N = SkFPAdd(N, coeff[3]);
831
832 if (N)
833 {
834 SkScalar delta = SkFPToScalar(SkFPDiv(N, D));
835
836 if (delta)
837 root -= delta;
838 }
839 return root;
840}
841#endif
842
843#if defined _WIN32 && _MSC_VER >= 1300 && defined SK_SCALAR_IS_FIXED // disable warning : unreachable code if building fixed point for windows desktop
844#pragma warning ( disable : 4702 )
845#endif
846
847/* Solve coeff(t) == 0, returning the number of roots that
848 lie withing 0 < t < 1.
849 coeff[0]t^3 + coeff[1]t^2 + coeff[2]t + coeff[3]
850*/
851static int solve_cubic_polynomial(const SkFP coeff[4], SkScalar tValues[3])
852{
853#ifndef SK_SCALAR_IS_FLOAT
854 return 0; // this is not yet implemented for software float
855#endif
856
857 if (SkScalarNearlyZero(coeff[0])) // we're just a quadratic
858 {
859 return SkFindUnitQuadRoots(coeff[1], coeff[2], coeff[3], tValues);
860 }
861
862 SkFP a, b, c, Q, R;
863
864 {
865 SkASSERT(coeff[0] != 0);
866
867 SkFP inva = SkFPInvert(coeff[0]);
868 a = SkFPMul(coeff[1], inva);
869 b = SkFPMul(coeff[2], inva);
870 c = SkFPMul(coeff[3], inva);
871 }
872 Q = SkFPDivInt(SkFPSub(SkFPMul(a,a), SkFPMulInt(b, 3)), 9);
873// R = (2*a*a*a - 9*a*b + 27*c) / 54;
874 R = SkFPMulInt(SkFPMul(SkFPMul(a, a), a), 2);
875 R = SkFPSub(R, SkFPMulInt(SkFPMul(a, b), 9));
876 R = SkFPAdd(R, SkFPMulInt(c, 27));
877 R = SkFPDivInt(R, 54);
878
879 SkFP Q3 = SkFPMul(SkFPMul(Q, Q), Q);
880 SkFP R2MinusQ3 = SkFPSub(SkFPMul(R,R), Q3);
881 SkFP adiv3 = SkFPDivInt(a, 3);
882
883 SkScalar* roots = tValues;
884 SkScalar r;
885
886 if (SkFPLT(R2MinusQ3, 0)) // we have 3 real roots
887 {
888#ifdef SK_SCALAR_IS_FLOAT
889 float theta = sk_float_acos(R / sk_float_sqrt(Q3));
890 float neg2RootQ = -2 * sk_float_sqrt(Q);
891
892 r = neg2RootQ * sk_float_cos(theta/3) - adiv3;
893 if (is_unit_interval(r))
894 *roots++ = r;
895
896 r = neg2RootQ * sk_float_cos((theta + 2*SK_ScalarPI)/3) - adiv3;
897 if (is_unit_interval(r))
898 *roots++ = r;
899
900 r = neg2RootQ * sk_float_cos((theta - 2*SK_ScalarPI)/3) - adiv3;
901 if (is_unit_interval(r))
902 *roots++ = r;
903
904 // now sort the roots
905 bubble_sort(tValues, (int)(roots - tValues));
906#endif
907 }
908 else // we have 1 real root
909 {
910 SkFP A = SkFPAdd(SkFPAbs(R), SkFPSqrt(R2MinusQ3));
911 A = SkFPCubeRoot(A);
912 if (SkFPGT(R, 0))
913 A = SkFPNeg(A);
914
915 if (A != 0)
916 A = SkFPAdd(A, SkFPDiv(Q, A));
917 r = SkFPToScalar(SkFPSub(A, adiv3));
918 if (is_unit_interval(r))
919 *roots++ = r;
920 }
921
922 return (int)(roots - tValues);
923}
924
925/* Looking for F' dot F'' == 0
926
927 A = b - a
928 B = c - 2b + a
929 C = d - 3c + 3b - a
930
931 F' = 3Ct^2 + 6Bt + 3A
932 F'' = 6Ct + 6B
933
934 F' dot F'' -> CCt^3 + 3BCt^2 + (2BB + CA)t + AB
935*/
936static void formulate_F1DotF2(const SkScalar src[], SkFP coeff[4])
937{
938 SkScalar a = src[2] - src[0];
939 SkScalar b = src[4] - 2 * src[2] + src[0];
940 SkScalar c = src[6] + 3 * (src[2] - src[4]) - src[0];
941
942 SkFP A = SkScalarToFP(a);
943 SkFP B = SkScalarToFP(b);
944 SkFP C = SkScalarToFP(c);
945
946 coeff[0] = SkFPMul(C, C);
947 coeff[1] = SkFPMulInt(SkFPMul(B, C), 3);
948 coeff[2] = SkFPMulInt(SkFPMul(B, B), 2);
949 coeff[2] = SkFPAdd(coeff[2], SkFPMul(C, A));
950 coeff[3] = SkFPMul(A, B);
951}
952
953// EXPERIMENTAL: can set this to zero to accept all t-values 0 < t < 1
954//#define kMinTValueForChopping (SK_Scalar1 / 256)
955#define kMinTValueForChopping 0
956
957/* Looking for F' dot F'' == 0
958
959 A = b - a
960 B = c - 2b + a
961 C = d - 3c + 3b - a
962
963 F' = 3Ct^2 + 6Bt + 3A
964 F'' = 6Ct + 6B
965
966 F' dot F'' -> CCt^3 + 3BCt^2 + (2BB + CA)t + AB
967*/
968int SkFindCubicMaxCurvature(const SkPoint src[4], SkScalar tValues[3])
969{
970 SkFP coeffX[4], coeffY[4];
971 int i;
972
973 formulate_F1DotF2(&src[0].fX, coeffX);
974 formulate_F1DotF2(&src[0].fY, coeffY);
975
976 for (i = 0; i < 4; i++)
977 coeffX[i] = SkFPAdd(coeffX[i],coeffY[i]);
978
979 SkScalar t[3];
980 int count = solve_cubic_polynomial(coeffX, t);
981 int maxCount = 0;
982
983 // now remove extrema where the curvature is zero (mins)
984 // !!!! need a test for this !!!!
985 for (i = 0; i < count; i++)
986 {
987 // if (not_min_curvature())
988 if (t[i] > kMinTValueForChopping && t[i] < SK_Scalar1 - kMinTValueForChopping)
989 tValues[maxCount++] = t[i];
990 }
991 return maxCount;
992}
993
994int SkChopCubicAtMaxCurvature(const SkPoint src[4], SkPoint dst[13], SkScalar tValues[3])
995{
996 SkScalar t_storage[3];
997
998 if (tValues == NULL)
999 tValues = t_storage;
1000
1001 int count = SkFindCubicMaxCurvature(src, tValues);
1002
1003 if (dst)
1004 {
1005 if (count == 0)
1006 memcpy(dst, src, 4 * sizeof(SkPoint));
1007 else
1008 SkChopCubicAt(src, dst, tValues, count);
1009 }
1010 return count + 1;
1011}
1012
kbr@chromium.orgc1b53332010-07-07 22:20:35 +0000[diff] [blame^]1013bool SkXRayCrossesMonotonicCubic(const SkXRay& pt, const SkPoint cubic[4], bool* ambiguous) {
1014 if (ambiguous) {
1015 *ambiguous = false;
1016 }
1017
reed@android.com5b4541e2010-02-05 20:41:02 +0000[diff] [blame]1018 // Find the minimum and maximum y of the extrema, which are the
1019 // first and last points since this cubic is monotonic
1020 SkScalar min_y = SkMinScalar(cubic[0].fY, cubic[3].fY);
1021 SkScalar max_y = SkMaxScalar(cubic[0].fY, cubic[3].fY);
1022
1023 if (pt.fY == cubic[0].fY
1024 || pt.fY < min_y
1025 || pt.fY > max_y) {
1026 // The query line definitely does not cross the curve
kbr@chromium.orgc1b53332010-07-07 22:20:35 +0000[diff] [blame^]1027 if (ambiguous) {
1028 *ambiguous = (pt.fY == cubic[0].fY);
1029 }
reed@android.com5b4541e2010-02-05 20:41:02 +0000[diff] [blame]1030 return false;
1031 }
1032
kbr@chromium.orgc1b53332010-07-07 22:20:35 +0000[diff] [blame^]1033 bool pt_at_extremum = (pt.fY == cubic[3].fY);
1034
reed@android.com5b4541e2010-02-05 20:41:02 +0000[diff] [blame]1035 SkScalar min_x =
1036 SkMinScalar(
1037 SkMinScalar(
1038 SkMinScalar(cubic[0].fX, cubic[1].fX),
1039 cubic[2].fX),
1040 cubic[3].fX);
1041 if (pt.fX < min_x) {
1042 // The query line definitely crosses the curve
kbr@chromium.orgc1b53332010-07-07 22:20:35 +0000[diff] [blame^]1043 if (ambiguous) {
1044 *ambiguous = pt_at_extremum;
1045 }
reed@android.com5b4541e2010-02-05 20:41:02 +0000[diff] [blame]1046 return true;
1047 }
1048
1049 SkScalar max_x =
1050 SkMaxScalar(
1051 SkMaxScalar(
1052 SkMaxScalar(cubic[0].fX, cubic[1].fX),
1053 cubic[2].fX),
1054 cubic[3].fX);
1055 if (pt.fX > max_x) {
1056 // The query line definitely does not cross the curve
1057 return false;
1058 }
1059
1060 // Do a binary search to find the parameter value which makes y as
1061 // close as possible to the query point. See whether the query
1062 // line's origin is to the left of the associated x coordinate.
1063
1064 // kMaxIter is chosen as the number of mantissa bits for a float,
1065 // since there's no way we are going to get more precision by
1066 // iterating more times than that.
1067 const int kMaxIter = 23;
1068 SkPoint eval;
1069 int iter = 0;
1070 SkScalar upper_t;
1071 SkScalar lower_t;
1072 // Need to invert direction of t parameter if cubic goes up
1073 // instead of down
1074 if (cubic[3].fY > cubic[0].fY) {
1075 upper_t = SK_Scalar1;
1076 lower_t = SkFloatToScalar(0);
1077 } else {
1078 upper_t = SkFloatToScalar(0);
1079 lower_t = SK_Scalar1;
1080 }
1081 do {
1082 SkScalar t = SkScalarAve(upper_t, lower_t);
1083 SkEvalCubicAt(cubic, t, &eval, NULL, NULL);
1084 if (pt.fY > eval.fY) {
1085 lower_t = t;
1086 } else {
1087 upper_t = t;
1088 }
1089 } while (++iter < kMaxIter
1090 && !SkScalarNearlyZero(eval.fY - pt.fY));
1091 if (pt.fX <= eval.fX) {
kbr@chromium.orgc1b53332010-07-07 22:20:35 +0000[diff] [blame^]1092 if (ambiguous) {
1093 *ambiguous = pt_at_extremum;
1094 }
reed@android.com5b4541e2010-02-05 20:41:02 +0000[diff] [blame]1095 return true;
1096 }
1097 return false;
1098}
1099
kbr@chromium.orgc1b53332010-07-07 22:20:35 +0000[diff] [blame^]1100int SkNumXRayCrossingsForCubic(const SkXRay& pt, const SkPoint cubic[4], bool* ambiguous) {
reed@android.com5b4541e2010-02-05 20:41:02 +0000[diff] [blame]1101 int num_crossings = 0;
1102 SkPoint monotonic_cubics[10];
1103 int num_monotonic_cubics = SkChopCubicAtYExtrema(cubic, monotonic_cubics);
kbr@chromium.orgc1b53332010-07-07 22:20:35 +0000[diff] [blame^]1104 if (ambiguous) {
1105 *ambiguous = false;
1106 }
1107 bool locally_ambiguous;
1108 if (SkXRayCrossesMonotonicCubic(pt, &monotonic_cubics[0], &locally_ambiguous))
reed@android.com5b4541e2010-02-05 20:41:02 +0000[diff] [blame]1109 ++num_crossings;
kbr@chromium.orgc1b53332010-07-07 22:20:35 +0000[diff] [blame^]1110 if (ambiguous) {
1111 *ambiguous |= locally_ambiguous;
1112 }
reed@android.com5b4541e2010-02-05 20:41:02 +0000[diff] [blame]1113 if (num_monotonic_cubics > 0)
kbr@chromium.orgc1b53332010-07-07 22:20:35 +0000[diff] [blame^]1114 if (SkXRayCrossesMonotonicCubic(pt, &monotonic_cubics[3], &locally_ambiguous))
reed@android.com5b4541e2010-02-05 20:41:02 +0000[diff] [blame]1115 ++num_crossings;
kbr@chromium.orgc1b53332010-07-07 22:20:35 +0000[diff] [blame^]1116 if (ambiguous) {
1117 *ambiguous |= locally_ambiguous;
1118 }
reed@android.com5b4541e2010-02-05 20:41:02 +0000[diff] [blame]1119 if (num_monotonic_cubics > 1)
kbr@chromium.orgc1b53332010-07-07 22:20:35 +0000[diff] [blame^]1120 if (SkXRayCrossesMonotonicCubic(pt, &monotonic_cubics[6], &locally_ambiguous))
reed@android.com5b4541e2010-02-05 20:41:02 +0000[diff] [blame]1121 ++num_crossings;
kbr@chromium.orgc1b53332010-07-07 22:20:35 +0000[diff] [blame^]1122 if (ambiguous) {
1123 *ambiguous |= locally_ambiguous;
1124 }
reed@android.com5b4541e2010-02-05 20:41:02 +0000[diff] [blame]1125 return num_crossings;
1126}
1127
reed@android.combcd4d5a2008-12-17 15:59:43 +0000[diff] [blame]1128////////////////////////////////////////////////////////////////////////////////
1129
1130/* Find t value for quadratic [a, b, c] = d.
1131 Return 0 if there is no solution within [0, 1)
1132*/
1133static SkScalar quad_solve(SkScalar a, SkScalar b, SkScalar c, SkScalar d)
1134{
1135 // At^2 + Bt + C = d
1136 SkScalar A = a - 2 * b + c;
1137 SkScalar B = 2 * (b - a);
1138 SkScalar C = a - d;
1139
1140 SkScalar roots[2];
1141 int count = SkFindUnitQuadRoots(A, B, C, roots);
1142
1143 SkASSERT(count <= 1);
1144 return count == 1 ? roots[0] : 0;
1145}
1146
1147/* given a quad-curve and a point (x,y), chop the quad at that point and return
1148 the new quad's offCurve point. Should only return false if the computed pos
1149 is the start of the curve (i.e. root == 0)
1150*/
1151static bool quad_pt2OffCurve(const SkPoint quad[3], SkScalar x, SkScalar y, SkPoint* offCurve)
1152{
1153 const SkScalar* base;
1154 SkScalar value;
1155
1156 if (SkScalarAbs(x) < SkScalarAbs(y)) {
1157 base = &quad[0].fX;
1158 value = x;
1159 } else {
1160 base = &quad[0].fY;
1161 value = y;
1162 }
1163
1164 // note: this returns 0 if it thinks value is out of range, meaning the
1165 // root might return something outside of [0, 1)
1166 SkScalar t = quad_solve(base[0], base[2], base[4], value);
1167
1168 if (t > 0)
1169 {
1170 SkPoint tmp[5];
1171 SkChopQuadAt(quad, tmp, t);
1172 *offCurve = tmp[1];
1173 return true;
1174 } else {
1175 /* t == 0 means either the value triggered a root outside of [0, 1)
1176 For our purposes, we can ignore the <= 0 roots, but we want to
1177 catch the >= 1 roots (which given our caller, will basically mean
1178 a root of 1, give-or-take numerical instability). If we are in the
1179 >= 1 case, return the existing offCurve point.
1180
1181 The test below checks to see if we are close to the "end" of the
1182 curve (near base[4]). Rather than specifying a tolerance, I just
1183 check to see if value is on to the right/left of the middle point
1184 (depending on the direction/sign of the end points).
1185 */
1186 if ((base[0] < base[4] && value > base[2]) ||
1187 (base[0] > base[4] && value < base[2])) // should root have been 1
1188 {
1189 *offCurve = quad[1];
1190 return true;
1191 }
1192 }
1193 return false;
1194}
1195
1196static const SkPoint gQuadCirclePts[kSkBuildQuadArcStorage] = {
1197 { SK_Scalar1, 0 },
1198 { SK_Scalar1, SK_ScalarTanPIOver8 },
1199 { SK_ScalarRoot2Over2, SK_ScalarRoot2Over2 },
1200 { SK_ScalarTanPIOver8, SK_Scalar1 },
1201
1202 { 0, SK_Scalar1 },
1203 { -SK_ScalarTanPIOver8, SK_Scalar1 },
1204 { -SK_ScalarRoot2Over2, SK_ScalarRoot2Over2 },
1205 { -SK_Scalar1, SK_ScalarTanPIOver8 },
1206
1207 { -SK_Scalar1, 0 },
1208 { -SK_Scalar1, -SK_ScalarTanPIOver8 },
1209 { -SK_ScalarRoot2Over2, -SK_ScalarRoot2Over2 },
1210 { -SK_ScalarTanPIOver8, -SK_Scalar1 },
1211
1212 { 0, -SK_Scalar1 },
1213 { SK_ScalarTanPIOver8, -SK_Scalar1 },
1214 { SK_ScalarRoot2Over2, -SK_ScalarRoot2Over2 },
1215 { SK_Scalar1, -SK_ScalarTanPIOver8 },
1216
1217 { SK_Scalar1, 0 }
1218};
1219
1220int SkBuildQuadArc(const SkVector& uStart, const SkVector& uStop,
1221 SkRotationDirection dir, const SkMatrix* userMatrix,
1222 SkPoint quadPoints[])
1223{
1224 // rotate by x,y so that uStart is (1.0)
1225 SkScalar x = SkPoint::DotProduct(uStart, uStop);
1226 SkScalar y = SkPoint::CrossProduct(uStart, uStop);
1227
1228 SkScalar absX = SkScalarAbs(x);
1229 SkScalar absY = SkScalarAbs(y);
1230
1231 int pointCount;
1232
1233 // check for (effectively) coincident vectors
1234 // this can happen if our angle is nearly 0 or nearly 180 (y == 0)
1235 // ... we use the dot-prod to distinguish between 0 and 180 (x > 0)
1236 if (absY <= SK_ScalarNearlyZero && x > 0 &&
1237 ((y >= 0 && kCW_SkRotationDirection == dir) ||
1238 (y <= 0 && kCCW_SkRotationDirection == dir))) {
1239
1240 // just return the start-point
1241 quadPoints[0].set(SK_Scalar1, 0);
1242 pointCount = 1;
1243 } else {
1244 if (dir == kCCW_SkRotationDirection)
1245 y = -y;
1246
1247 // what octant (quadratic curve) is [xy] in?
1248 int oct = 0;
1249 bool sameSign = true;
1250
1251 if (0 == y)
1252 {
1253 oct = 4; // 180
1254 SkASSERT(SkScalarAbs(x + SK_Scalar1) <= SK_ScalarNearlyZero);
1255 }
1256 else if (0 == x)
1257 {
1258 SkASSERT(absY - SK_Scalar1 <= SK_ScalarNearlyZero);
1259 if (y > 0)
1260 oct = 2; // 90
1261 else
1262 oct = 6; // 270
1263 }
1264 else
1265 {
1266 if (y < 0)
1267 oct += 4;
1268 if ((x < 0) != (y < 0))
1269 {
1270 oct += 2;
1271 sameSign = false;
1272 }
1273 if ((absX < absY) == sameSign)
1274 oct += 1;
1275 }
1276
1277 int wholeCount = oct << 1;
1278 memcpy(quadPoints, gQuadCirclePts, (wholeCount + 1) * sizeof(SkPoint));
1279
1280 const SkPoint* arc = &gQuadCirclePts[wholeCount];
1281 if (quad_pt2OffCurve(arc, x, y, &quadPoints[wholeCount + 1]))
1282 {
1283 quadPoints[wholeCount + 2].set(x, y);
1284 wholeCount += 2;
1285 }
1286 pointCount = wholeCount + 1;
1287 }
1288
1289 // now handle counter-clockwise and the initial unitStart rotation
1290 SkMatrix matrix;
1291 matrix.setSinCos(uStart.fY, uStart.fX);
1292 if (dir == kCCW_SkRotationDirection) {
1293 matrix.preScale(SK_Scalar1, -SK_Scalar1);
1294 }
1295 if (userMatrix) {
1296 matrix.postConcat(*userMatrix);
1297 }
1298 matrix.mapPoints(quadPoints, pointCount);
1299 return pointCount;
1300}
1301