| OLD | NEW | 
|---|
| 1 /* | 1 /* | 
| 2  * Copyright 2006 The Android Open Source Project | 2  * Copyright 2006 The Android Open Source Project | 
| 3  * | 3  * | 
| 4  * Use of this source code is governed by a BSD-style license that can be | 4  * Use of this source code is governed by a BSD-style license that can be | 
| 5  * found in the LICENSE file. | 5  * found in the LICENSE file. | 
| 6  */ | 6  */ | 
| 7 | 7 | 
| 8 #include "SkGeometry.h" | 8 #include "SkGeometry.h" | 
| 9 #include "SkMatrix.h" | 9 #include "SkMatrix.h" | 
| 10 | 10 | 
| (...skipping 51 matching lines...) Expand 10 before | Expand all | Expand 10 after  Loading... | 
| 62 } | 62 } | 
| 63 | 63 | 
| 64 /** If defined, this makes eval_quad and eval_cubic do more setup (sometimes | 64 /** If defined, this makes eval_quad and eval_cubic do more setup (sometimes | 
| 65     involving integer multiplies by 2 or 3, but fewer calls to SkScalarMul. | 65     involving integer multiplies by 2 or 3, but fewer calls to SkScalarMul. | 
| 66     May also introduce overflow of fixed when we compute our setup. | 66     May also introduce overflow of fixed when we compute our setup. | 
| 67 */ | 67 */ | 
| 68 //    #define DIRECT_EVAL_OF_POLYNOMIALS | 68 //    #define DIRECT_EVAL_OF_POLYNOMIALS | 
| 69 | 69 | 
| 70 //////////////////////////////////////////////////////////////////////// | 70 //////////////////////////////////////////////////////////////////////// | 
| 71 | 71 | 
| 72 static int is_not_monotonic(float a, float b, float c) { | 72 static int is_not_monotonic(SkScalar a, SkScalar b, SkScalar c) { | 
| 73     float ab = a - b; | 73     SkScalar ab = a - b; | 
| 74     float bc = b - c; | 74     SkScalar bc = b - c; | 
| 75     if (ab < 0) { | 75     if (ab < 0) { | 
| 76         bc = -bc; | 76         bc = -bc; | 
| 77     } | 77     } | 
| 78     return ab == 0 || bc < 0; | 78     return ab == 0 || bc < 0; | 
| 79 } | 79 } | 
| 80 | 80 | 
| 81 //////////////////////////////////////////////////////////////////////// | 81 //////////////////////////////////////////////////////////////////////// | 
| 82 | 82 | 
| 83 static bool is_unit_interval(SkScalar x) | 83 static bool is_unit_interval(SkScalar x) { | 
| 84 { |  | 
| 85     return x > 0 && x < SK_Scalar1; | 84     return x > 0 && x < SK_Scalar1; | 
| 86 } | 85 } | 
| 87 | 86 | 
| 88 static int valid_unit_divide(SkScalar numer, SkScalar denom, SkScalar* ratio) | 87 static int valid_unit_divide(SkScalar numer, SkScalar denom, SkScalar* ratio) { | 
| 89 { |  | 
| 90     SkASSERT(ratio); | 88     SkASSERT(ratio); | 
| 91 | 89 | 
| 92     if (numer < 0) | 90     if (numer < 0) { | 
| 93     { |  | 
| 94         numer = -numer; | 91         numer = -numer; | 
| 95         denom = -denom; | 92         denom = -denom; | 
| 96     } | 93     } | 
| 97 | 94 | 
| 98     if (denom == 0 || numer == 0 || numer >= denom) | 95     if (denom == 0 || numer == 0 || numer >= denom) { | 
| 99         return 0; | 96         return 0; | 
|  | 97     } | 
| 100 | 98 | 
| 101     SkScalar r = SkScalarDiv(numer, denom); | 99     SkScalar r = SkScalarDiv(numer, denom); | 
| 102     if (SkScalarIsNaN(r)) { | 100     if (SkScalarIsNaN(r)) { | 
| 103         return 0; | 101         return 0; | 
| 104     } | 102     } | 
| 105     SkASSERT(r >= 0 && r < SK_Scalar1); | 103     SkASSERT(r >= 0 && r < SK_Scalar1); | 
| 106     if (r == 0) // catch underflow if numer <<<< denom | 104     if (r == 0) { // catch underflow if numer <<<< denom | 
| 107         return 0; | 105         return 0; | 
|  | 106     } | 
| 108     *ratio = r; | 107     *ratio = r; | 
| 109     return 1; | 108     return 1; | 
| 110 } | 109 } | 
| 111 | 110 | 
| 112 /** From Numerical Recipes in C. | 111 /** From Numerical Recipes in C. | 
| 113 | 112 | 
| 114     Q = -1/2 (B + sign(B) sqrt[B*B - 4*A*C]) | 113     Q = -1/2 (B + sign(B) sqrt[B*B - 4*A*C]) | 
| 115     x1 = Q / A | 114     x1 = Q / A | 
| 116     x2 = C / Q | 115     x2 = C / Q | 
| 117 */ | 116 */ | 
| 118 int SkFindUnitQuadRoots(SkScalar A, SkScalar B, SkScalar C, SkScalar roots[2]) | 117 int SkFindUnitQuadRoots(SkScalar A, SkScalar B, SkScalar C, SkScalar roots[2]) { | 
| 119 { |  | 
| 120     SkASSERT(roots); | 118     SkASSERT(roots); | 
| 121 | 119 | 
| 122     if (A == 0) | 120     if (A == 0) { | 
| 123         return valid_unit_divide(-C, B, roots); | 121         return valid_unit_divide(-C, B, roots); | 
|  | 122     } | 
| 124 | 123 | 
| 125     SkScalar* r = roots; | 124     SkScalar* r = roots; | 
| 126 | 125 | 
| 127     float R = B*B - 4*A*C; | 126     SkScalar R = B*B - 4*A*C; | 
| 128     if (R < 0 || SkScalarIsNaN(R)) {  // complex roots | 127     if (R < 0 || SkScalarIsNaN(R)) {  // complex roots | 
| 129         return 0; | 128         return 0; | 
| 130     } | 129     } | 
| 131     R = sk_float_sqrt(R); | 130     R = SkScalarSqrt(R); | 
| 132 | 131 | 
| 133     SkScalar Q = (B < 0) ? -(B-R)/2 : -(B+R)/2; | 132     SkScalar Q = (B < 0) ? -(B-R)/2 : -(B+R)/2; | 
| 134     r += valid_unit_divide(Q, A, r); | 133     r += valid_unit_divide(Q, A, r); | 
| 135     r += valid_unit_divide(C, Q, r); | 134     r += valid_unit_divide(C, Q, r); | 
| 136     if (r - roots == 2) | 135     if (r - roots == 2) { | 
| 137     { |  | 
| 138         if (roots[0] > roots[1]) | 136         if (roots[0] > roots[1]) | 
| 139             SkTSwap<SkScalar>(roots[0], roots[1]); | 137             SkTSwap<SkScalar>(roots[0], roots[1]); | 
| 140         else if (roots[0] == roots[1])  // nearly-equal? | 138         else if (roots[0] == roots[1])  // nearly-equal? | 
| 141             r -= 1; // skip the double root | 139             r -= 1; // skip the double root | 
| 142     } | 140     } | 
| 143     return (int)(r - roots); | 141     return (int)(r - roots); | 
| 144 } | 142 } | 
| 145 | 143 | 
| 146 /////////////////////////////////////////////////////////////////////////////// | 144 /////////////////////////////////////////////////////////////////////////////// | 
| 147 /////////////////////////////////////////////////////////////////////////////// | 145 /////////////////////////////////////////////////////////////////////////////// | 
| 148 | 146 | 
| 149 static SkScalar eval_quad(const SkScalar src[], SkScalar t) | 147 static SkScalar eval_quad(const SkScalar src[], SkScalar t) { | 
| 150 { |  | 
| 151     SkASSERT(src); | 148     SkASSERT(src); | 
| 152     SkASSERT(t >= 0 && t <= SK_Scalar1); | 149     SkASSERT(t >= 0 && t <= SK_Scalar1); | 
| 153 | 150 | 
| 154 #ifdef DIRECT_EVAL_OF_POLYNOMIALS | 151 #ifdef DIRECT_EVAL_OF_POLYNOMIALS | 
| 155     SkScalar    C = src[0]; | 152     SkScalar    C = src[0]; | 
| 156     SkScalar    A = src[4] - 2 * src[2] + C; | 153     SkScalar    A = src[4] - 2 * src[2] + C; | 
| 157     SkScalar    B = 2 * (src[2] - C); | 154     SkScalar    B = 2 * (src[2] - C); | 
| 158     return SkScalarMulAdd(SkScalarMulAdd(A, t, B), t, C); | 155     return SkScalarMulAdd(SkScalarMulAdd(A, t, B), t, C); | 
| 159 #else | 156 #else | 
| 160     SkScalar    ab = SkScalarInterp(src[0], src[2], t); | 157     SkScalar    ab = SkScalarInterp(src[0], src[2], t); | 
| 161     SkScalar    bc = SkScalarInterp(src[2], src[4], t); | 158     SkScalar    bc = SkScalarInterp(src[2], src[4], t); | 
| 162     return SkScalarInterp(ab, bc, t); | 159     return SkScalarInterp(ab, bc, t); | 
| 163 #endif | 160 #endif | 
| 164 } | 161 } | 
| 165 | 162 | 
| 166 static SkScalar eval_quad_derivative(const SkScalar src[], SkScalar t) | 163 static SkScalar eval_quad_derivative(const SkScalar src[], SkScalar t) { | 
| 167 { |  | 
| 168     SkScalar A = src[4] - 2 * src[2] + src[0]; | 164     SkScalar A = src[4] - 2 * src[2] + src[0]; | 
| 169     SkScalar B = src[2] - src[0]; | 165     SkScalar B = src[2] - src[0]; | 
| 170 | 166 | 
| 171     return 2 * SkScalarMulAdd(A, t, B); | 167     return 2 * SkScalarMulAdd(A, t, B); | 
| 172 } | 168 } | 
| 173 | 169 | 
| 174 static SkScalar eval_quad_derivative_at_half(const SkScalar src[]) | 170 static SkScalar eval_quad_derivative_at_half(const SkScalar src[]) { | 
| 175 { |  | 
| 176     SkScalar A = src[4] - 2 * src[2] + src[0]; | 171     SkScalar A = src[4] - 2 * src[2] + src[0]; | 
| 177     SkScalar B = src[2] - src[0]; | 172     SkScalar B = src[2] - src[0]; | 
| 178     return A + 2 * B; | 173     return A + 2 * B; | 
| 179 } | 174 } | 
| 180 | 175 | 
| 181 void SkEvalQuadAt(const SkPoint src[3], SkScalar t, SkPoint* pt, SkVector* tange
      nt) | 176 void SkEvalQuadAt(const SkPoint src[3], SkScalar t, SkPoint* pt, | 
| 182 { | 177                   SkVector* tangent) { | 
| 183     SkASSERT(src); | 178     SkASSERT(src); | 
| 184     SkASSERT(t >= 0 && t <= SK_Scalar1); | 179     SkASSERT(t >= 0 && t <= SK_Scalar1); | 
| 185 | 180 | 
| 186     if (pt) | 181     if (pt) { | 
| 187         pt->set(eval_quad(&src[0].fX, t), eval_quad(&src[0].fY, t)); | 182         pt->set(eval_quad(&src[0].fX, t), eval_quad(&src[0].fY, t)); | 
| 188     if (tangent) | 183     } | 
|  | 184     if (tangent) { | 
| 189         tangent->set(eval_quad_derivative(&src[0].fX, t), | 185         tangent->set(eval_quad_derivative(&src[0].fX, t), | 
| 190                      eval_quad_derivative(&src[0].fY, t)); | 186                      eval_quad_derivative(&src[0].fY, t)); | 
|  | 187     } | 
| 191 } | 188 } | 
| 192 | 189 | 
| 193 void SkEvalQuadAtHalf(const SkPoint src[3], SkPoint* pt, SkVector* tangent) | 190 void SkEvalQuadAtHalf(const SkPoint src[3], SkPoint* pt, SkVector* tangent) { | 
| 194 { |  | 
| 195     SkASSERT(src); | 191     SkASSERT(src); | 
| 196 | 192 | 
| 197     if (pt) | 193     if (pt) { | 
| 198     { |  | 
| 199         SkScalar x01 = SkScalarAve(src[0].fX, src[1].fX); | 194         SkScalar x01 = SkScalarAve(src[0].fX, src[1].fX); | 
| 200         SkScalar y01 = SkScalarAve(src[0].fY, src[1].fY); | 195         SkScalar y01 = SkScalarAve(src[0].fY, src[1].fY); | 
| 201         SkScalar x12 = SkScalarAve(src[1].fX, src[2].fX); | 196         SkScalar x12 = SkScalarAve(src[1].fX, src[2].fX); | 
| 202         SkScalar y12 = SkScalarAve(src[1].fY, src[2].fY); | 197         SkScalar y12 = SkScalarAve(src[1].fY, src[2].fY); | 
| 203         pt->set(SkScalarAve(x01, x12), SkScalarAve(y01, y12)); | 198         pt->set(SkScalarAve(x01, x12), SkScalarAve(y01, y12)); | 
| 204     } | 199     } | 
| 205     if (tangent) | 200     if (tangent) { | 
| 206         tangent->set(eval_quad_derivative_at_half(&src[0].fX), | 201         tangent->set(eval_quad_derivative_at_half(&src[0].fX), | 
| 207                      eval_quad_derivative_at_half(&src[0].fY)); | 202                      eval_quad_derivative_at_half(&src[0].fY)); | 
|  | 203     } | 
| 208 } | 204 } | 
| 209 | 205 | 
| 210 static void interp_quad_coords(const SkScalar* src, SkScalar* dst, SkScalar t) | 206 static void interp_quad_coords(const SkScalar* src, SkScalar* dst, SkScalar t) { | 
| 211 { |  | 
| 212     SkScalar    ab = SkScalarInterp(src[0], src[2], t); | 207     SkScalar    ab = SkScalarInterp(src[0], src[2], t); | 
| 213     SkScalar    bc = SkScalarInterp(src[2], src[4], t); | 208     SkScalar    bc = SkScalarInterp(src[2], src[4], t); | 
| 214 | 209 | 
| 215     dst[0] = src[0]; | 210     dst[0] = src[0]; | 
| 216     dst[2] = ab; | 211     dst[2] = ab; | 
| 217     dst[4] = SkScalarInterp(ab, bc, t); | 212     dst[4] = SkScalarInterp(ab, bc, t); | 
| 218     dst[6] = bc; | 213     dst[6] = bc; | 
| 219     dst[8] = src[4]; | 214     dst[8] = src[4]; | 
| 220 } | 215 } | 
| 221 | 216 | 
| 222 void SkChopQuadAt(const SkPoint src[3], SkPoint dst[5], SkScalar t) | 217 void SkChopQuadAt(const SkPoint src[3], SkPoint dst[5], SkScalar t) { | 
| 223 { |  | 
| 224     SkASSERT(t > 0 && t < SK_Scalar1); | 218     SkASSERT(t > 0 && t < SK_Scalar1); | 
| 225 | 219 | 
| 226     interp_quad_coords(&src[0].fX, &dst[0].fX, t); | 220     interp_quad_coords(&src[0].fX, &dst[0].fX, t); | 
| 227     interp_quad_coords(&src[0].fY, &dst[0].fY, t); | 221     interp_quad_coords(&src[0].fY, &dst[0].fY, t); | 
| 228 } | 222 } | 
| 229 | 223 | 
| 230 void SkChopQuadAtHalf(const SkPoint src[3], SkPoint dst[5]) | 224 void SkChopQuadAtHalf(const SkPoint src[3], SkPoint dst[5]) { | 
| 231 { |  | 
| 232     SkScalar x01 = SkScalarAve(src[0].fX, src[1].fX); | 225     SkScalar x01 = SkScalarAve(src[0].fX, src[1].fX); | 
| 233     SkScalar y01 = SkScalarAve(src[0].fY, src[1].fY); | 226     SkScalar y01 = SkScalarAve(src[0].fY, src[1].fY); | 
| 234     SkScalar x12 = SkScalarAve(src[1].fX, src[2].fX); | 227     SkScalar x12 = SkScalarAve(src[1].fX, src[2].fX); | 
| 235     SkScalar y12 = SkScalarAve(src[1].fY, src[2].fY); | 228     SkScalar y12 = SkScalarAve(src[1].fY, src[2].fY); | 
| 236 | 229 | 
| 237     dst[0] = src[0]; | 230     dst[0] = src[0]; | 
| 238     dst[1].set(x01, y01); | 231     dst[1].set(x01, y01); | 
| 239     dst[2].set(SkScalarAve(x01, x12), SkScalarAve(y01, y12)); | 232     dst[2].set(SkScalarAve(x01, x12), SkScalarAve(y01, y12)); | 
| 240     dst[3].set(x12, y12); | 233     dst[3].set(x12, y12); | 
| 241     dst[4] = src[2]; | 234     dst[4] = src[2]; | 
| 242 } | 235 } | 
| 243 | 236 | 
| 244 /** Quad'(t) = At + B, where | 237 /** Quad'(t) = At + B, where | 
| 245     A = 2(a - 2b + c) | 238     A = 2(a - 2b + c) | 
| 246     B = 2(b - a) | 239     B = 2(b - a) | 
| 247     Solve for t, only if it fits between 0 < t < 1 | 240     Solve for t, only if it fits between 0 < t < 1 | 
| 248 */ | 241 */ | 
| 249 int SkFindQuadExtrema(SkScalar a, SkScalar b, SkScalar c, SkScalar tValue[1]) | 242 int SkFindQuadExtrema(SkScalar a, SkScalar b, SkScalar c, SkScalar tValue[1]) { | 
| 250 { |  | 
| 251     /*  At + B == 0 | 243     /*  At + B == 0 | 
| 252         t = -B / A | 244         t = -B / A | 
| 253     */ | 245     */ | 
| 254     return valid_unit_divide(a - b, a - b - b + c, tValue); | 246     return valid_unit_divide(a - b, a - b - b + c, tValue); | 
| 255 } | 247 } | 
| 256 | 248 | 
| 257 static inline void flatten_double_quad_extrema(SkScalar coords[14]) | 249 static inline void flatten_double_quad_extrema(SkScalar coords[14]) { | 
| 258 { |  | 
| 259     coords[2] = coords[6] = coords[4]; | 250     coords[2] = coords[6] = coords[4]; | 
| 260 } | 251 } | 
| 261 | 252 | 
| 262 /*  Returns 0 for 1 quad, and 1 for two quads, either way the answer is | 253 /*  Returns 0 for 1 quad, and 1 for two quads, either way the answer is | 
| 263  stored in dst[]. Guarantees that the 1/2 quads will be monotonic. | 254  stored in dst[]. Guarantees that the 1/2 quads will be monotonic. | 
| 264  */ | 255  */ | 
| 265 int SkChopQuadAtYExtrema(const SkPoint src[3], SkPoint dst[5]) | 256 int SkChopQuadAtYExtrema(const SkPoint src[3], SkPoint dst[5]) { | 
| 266 { |  | 
| 267     SkASSERT(src); | 257     SkASSERT(src); | 
| 268     SkASSERT(dst); | 258     SkASSERT(dst); | 
| 269 | 259 | 
| 270 #if 0 |  | 
| 271     static bool once = true; |  | 
| 272     if (once) |  | 
| 273     { |  | 
| 274         once = false; |  | 
| 275         SkPoint s[3] = { 0, 26398, 0, 26331, 0, 20621428 }; |  | 
| 276         SkPoint d[6]; |  | 
| 277 |  | 
| 278         int n = SkChopQuadAtYExtrema(s, d); |  | 
| 279         SkDebugf("chop=%d, Y=[%x %x %x %x %x %x]\n", n, d[0].fY, d[1].fY, d[2].f
      Y, d[3].fY, d[4].fY, d[5].fY); |  | 
| 280     } |  | 
| 281 #endif |  | 
| 282 |  | 
| 283     SkScalar a = src[0].fY; | 260     SkScalar a = src[0].fY; | 
| 284     SkScalar b = src[1].fY; | 261     SkScalar b = src[1].fY; | 
| 285     SkScalar c = src[2].fY; | 262     SkScalar c = src[2].fY; | 
| 286 | 263 | 
| 287     if (is_not_monotonic(a, b, c)) | 264     if (is_not_monotonic(a, b, c)) { | 
| 288     { |  | 
| 289         SkScalar    tValue; | 265         SkScalar    tValue; | 
| 290         if (valid_unit_divide(a - b, a - b - b + c, &tValue)) | 266         if (valid_unit_divide(a - b, a - b - b + c, &tValue)) { | 
| 291         { |  | 
| 292             SkChopQuadAt(src, dst, tValue); | 267             SkChopQuadAt(src, dst, tValue); | 
| 293             flatten_double_quad_extrema(&dst[0].fY); | 268             flatten_double_quad_extrema(&dst[0].fY); | 
| 294             return 1; | 269             return 1; | 
| 295         } | 270         } | 
| 296         // if we get here, we need to force dst to be monotonic, even though | 271         // if we get here, we need to force dst to be monotonic, even though | 
| 297         // we couldn't compute a unit_divide value (probably underflow). | 272         // we couldn't compute a unit_divide value (probably underflow). | 
| 298         b = SkScalarAbs(a - b) < SkScalarAbs(b - c) ? a : c; | 273         b = SkScalarAbs(a - b) < SkScalarAbs(b - c) ? a : c; | 
| 299     } | 274     } | 
| 300     dst[0].set(src[0].fX, a); | 275     dst[0].set(src[0].fX, a); | 
| 301     dst[1].set(src[1].fX, b); | 276     dst[1].set(src[1].fX, b); | 
| 302     dst[2].set(src[2].fX, c); | 277     dst[2].set(src[2].fX, c); | 
| 303     return 0; | 278     return 0; | 
| 304 } | 279 } | 
| 305 | 280 | 
| 306 /*  Returns 0 for 1 quad, and 1 for two quads, either way the answer is | 281 /*  Returns 0 for 1 quad, and 1 for two quads, either way the answer is | 
| 307     stored in dst[]. Guarantees that the 1/2 quads will be monotonic. | 282     stored in dst[]. Guarantees that the 1/2 quads will be monotonic. | 
| 308  */ | 283  */ | 
| 309 int SkChopQuadAtXExtrema(const SkPoint src[3], SkPoint dst[5]) | 284 int SkChopQuadAtXExtrema(const SkPoint src[3], SkPoint dst[5]) { | 
| 310 { |  | 
| 311     SkASSERT(src); | 285     SkASSERT(src); | 
| 312     SkASSERT(dst); | 286     SkASSERT(dst); | 
| 313 | 287 | 
| 314     SkScalar a = src[0].fX; | 288     SkScalar a = src[0].fX; | 
| 315     SkScalar b = src[1].fX; | 289     SkScalar b = src[1].fX; | 
| 316     SkScalar c = src[2].fX; | 290     SkScalar c = src[2].fX; | 
| 317 | 291 | 
| 318     if (is_not_monotonic(a, b, c)) { | 292     if (is_not_monotonic(a, b, c)) { | 
| 319         SkScalar tValue; | 293         SkScalar tValue; | 
| 320         if (valid_unit_divide(a - b, a - b - b + c, &tValue)) { | 294         if (valid_unit_divide(a - b, a - b - b + c, &tValue)) { | 
| (...skipping 16 matching lines...) Expand all  Loading... | 
| 337 //  F''(t)  = 2 (a - 2b + c) | 311 //  F''(t)  = 2 (a - 2b + c) | 
| 338 // | 312 // | 
| 339 //  A = 2 (b - a) | 313 //  A = 2 (b - a) | 
| 340 //  B = 2 (a - 2b + c) | 314 //  B = 2 (a - 2b + c) | 
| 341 // | 315 // | 
| 342 //  Maximum curvature for a quadratic means solving | 316 //  Maximum curvature for a quadratic means solving | 
| 343 //  Fx' Fx'' + Fy' Fy'' = 0 | 317 //  Fx' Fx'' + Fy' Fy'' = 0 | 
| 344 // | 318 // | 
| 345 //  t = - (Ax Bx + Ay By) / (Bx ^ 2 + By ^ 2) | 319 //  t = - (Ax Bx + Ay By) / (Bx ^ 2 + By ^ 2) | 
| 346 // | 320 // | 
| 347 float SkFindQuadMaxCurvature(const SkPoint src[3]) { | 321 SkScalar SkFindQuadMaxCurvature(const SkPoint src[3]) { | 
| 348     SkScalar    Ax = src[1].fX - src[0].fX; | 322     SkScalar    Ax = src[1].fX - src[0].fX; | 
| 349     SkScalar    Ay = src[1].fY - src[0].fY; | 323     SkScalar    Ay = src[1].fY - src[0].fY; | 
| 350     SkScalar    Bx = src[0].fX - src[1].fX - src[1].fX + src[2].fX; | 324     SkScalar    Bx = src[0].fX - src[1].fX - src[1].fX + src[2].fX; | 
| 351     SkScalar    By = src[0].fY - src[1].fY - src[1].fY + src[2].fY; | 325     SkScalar    By = src[0].fY - src[1].fY - src[1].fY + src[2].fY; | 
| 352     SkScalar    t = 0;  // 0 means don't chop | 326     SkScalar    t = 0;  // 0 means don't chop | 
| 353 | 327 | 
| 354     (void)valid_unit_divide(-(Ax * Bx + Ay * By), Bx * Bx + By * By, &t); | 328     (void)valid_unit_divide(-(Ax * Bx + Ay * By), Bx * Bx + By * By, &t); | 
| 355     return t; | 329     return t; | 
| 356 } | 330 } | 
| 357 | 331 | 
| 358 int SkChopQuadAtMaxCurvature(const SkPoint src[3], SkPoint dst[5]) | 332 int SkChopQuadAtMaxCurvature(const SkPoint src[3], SkPoint dst[5]) { | 
| 359 { |  | 
| 360     SkScalar t = SkFindQuadMaxCurvature(src); | 333     SkScalar t = SkFindQuadMaxCurvature(src); | 
| 361     if (t == 0) { | 334     if (t == 0) { | 
| 362         memcpy(dst, src, 3 * sizeof(SkPoint)); | 335         memcpy(dst, src, 3 * sizeof(SkPoint)); | 
| 363         return 1; | 336         return 1; | 
| 364     } else { | 337     } else { | 
| 365         SkChopQuadAt(src, dst, t); | 338         SkChopQuadAt(src, dst, t); | 
| 366         return 2; | 339         return 2; | 
| 367     } | 340     } | 
| 368 } | 341 } | 
| 369 | 342 | 
| 370 #define SK_ScalarTwoThirds  (0.666666666f) | 343 #define SK_ScalarTwoThirds  (0.666666666f) | 
| 371 | 344 | 
| 372 void SkConvertQuadToCubic(const SkPoint src[3], SkPoint dst[4]) { | 345 void SkConvertQuadToCubic(const SkPoint src[3], SkPoint dst[4]) { | 
| 373     const SkScalar scale = SK_ScalarTwoThirds; | 346     const SkScalar scale = SK_ScalarTwoThirds; | 
| 374     dst[0] = src[0]; | 347     dst[0] = src[0]; | 
| 375     dst[1].set(src[0].fX + SkScalarMul(src[1].fX - src[0].fX, scale), | 348     dst[1].set(src[0].fX + SkScalarMul(src[1].fX - src[0].fX, scale), | 
| 376                src[0].fY + SkScalarMul(src[1].fY - src[0].fY, scale)); | 349                src[0].fY + SkScalarMul(src[1].fY - src[0].fY, scale)); | 
| 377     dst[2].set(src[2].fX + SkScalarMul(src[1].fX - src[2].fX, scale), | 350     dst[2].set(src[2].fX + SkScalarMul(src[1].fX - src[2].fX, scale), | 
| 378                src[2].fY + SkScalarMul(src[1].fY - src[2].fY, scale)); | 351                src[2].fY + SkScalarMul(src[1].fY - src[2].fY, scale)); | 
| 379     dst[3] = src[2]; | 352     dst[3] = src[2]; | 
| 380 } | 353 } | 
| 381 | 354 | 
| 382 ////////////////////////////////////////////////////////////////////////////////
      //////// | 355 ////////////////////////////////////////////////////////////////////////////// | 
| 383 ///// CUBICS // CUBICS // CUBICS // CUBICS // CUBICS // CUBICS // CUBICS // CUBI
      CS ///// | 356 ///// CUBICS // CUBICS // CUBICS // CUBICS // CUBICS // CUBICS // CUBICS ///// | 
| 384 ////////////////////////////////////////////////////////////////////////////////
      //////// | 357 ////////////////////////////////////////////////////////////////////////////// | 
| 385 | 358 | 
| 386 static void get_cubic_coeff(const SkScalar pt[], SkScalar coeff[4]) | 359 static void get_cubic_coeff(const SkScalar pt[], SkScalar coeff[4]) { | 
| 387 { |  | 
| 388     coeff[0] = pt[6] + 3*(pt[2] - pt[4]) - pt[0]; | 360     coeff[0] = pt[6] + 3*(pt[2] - pt[4]) - pt[0]; | 
| 389     coeff[1] = 3*(pt[4] - pt[2] - pt[2] + pt[0]); | 361     coeff[1] = 3*(pt[4] - pt[2] - pt[2] + pt[0]); | 
| 390     coeff[2] = 3*(pt[2] - pt[0]); | 362     coeff[2] = 3*(pt[2] - pt[0]); | 
| 391     coeff[3] = pt[0]; | 363     coeff[3] = pt[0]; | 
| 392 } | 364 } | 
| 393 | 365 | 
| 394 void SkGetCubicCoeff(const SkPoint pts[4], SkScalar cx[4], SkScalar cy[4]) | 366 void SkGetCubicCoeff(const SkPoint pts[4], SkScalar cx[4], SkScalar cy[4]) { | 
| 395 { |  | 
| 396     SkASSERT(pts); | 367     SkASSERT(pts); | 
| 397 | 368 | 
| 398     if (cx) | 369     if (cx) { | 
| 399         get_cubic_coeff(&pts[0].fX, cx); | 370         get_cubic_coeff(&pts[0].fX, cx); | 
| 400     if (cy) | 371     } | 
|  | 372     if (cy) { | 
| 401         get_cubic_coeff(&pts[0].fY, cy); | 373         get_cubic_coeff(&pts[0].fY, cy); | 
|  | 374     } | 
| 402 } | 375 } | 
| 403 | 376 | 
| 404 static SkScalar eval_cubic(const SkScalar src[], SkScalar t) | 377 static SkScalar eval_cubic(const SkScalar src[], SkScalar t) { | 
| 405 { |  | 
| 406     SkASSERT(src); | 378     SkASSERT(src); | 
| 407     SkASSERT(t >= 0 && t <= SK_Scalar1); | 379     SkASSERT(t >= 0 && t <= SK_Scalar1); | 
| 408 | 380 | 
| 409     if (t == 0) | 381     if (t == 0) { | 
| 410         return src[0]; | 382         return src[0]; | 
|  | 383     } | 
| 411 | 384 | 
| 412 #ifdef DIRECT_EVAL_OF_POLYNOMIALS | 385 #ifdef DIRECT_EVAL_OF_POLYNOMIALS | 
| 413     SkScalar D = src[0]; | 386     SkScalar D = src[0]; | 
| 414     SkScalar A = src[6] + 3*(src[2] - src[4]) - D; | 387     SkScalar A = src[6] + 3*(src[2] - src[4]) - D; | 
| 415     SkScalar B = 3*(src[4] - src[2] - src[2] + D); | 388     SkScalar B = 3*(src[4] - src[2] - src[2] + D); | 
| 416     SkScalar C = 3*(src[2] - D); | 389     SkScalar C = 3*(src[2] - D); | 
| 417 | 390 | 
| 418     return SkScalarMulAdd(SkScalarMulAdd(SkScalarMulAdd(A, t, B), t, C), t, D); | 391     return SkScalarMulAdd(SkScalarMulAdd(SkScalarMulAdd(A, t, B), t, C), t, D); | 
| 419 #else | 392 #else | 
| 420     SkScalar    ab = SkScalarInterp(src[0], src[2], t); | 393     SkScalar    ab = SkScalarInterp(src[0], src[2], t); | 
| 421     SkScalar    bc = SkScalarInterp(src[2], src[4], t); | 394     SkScalar    bc = SkScalarInterp(src[2], src[4], t); | 
| 422     SkScalar    cd = SkScalarInterp(src[4], src[6], t); | 395     SkScalar    cd = SkScalarInterp(src[4], src[6], t); | 
| 423     SkScalar    abc = SkScalarInterp(ab, bc, t); | 396     SkScalar    abc = SkScalarInterp(ab, bc, t); | 
| 424     SkScalar    bcd = SkScalarInterp(bc, cd, t); | 397     SkScalar    bcd = SkScalarInterp(bc, cd, t); | 
| 425     return SkScalarInterp(abc, bcd, t); | 398     return SkScalarInterp(abc, bcd, t); | 
| 426 #endif | 399 #endif | 
| 427 } | 400 } | 
| 428 | 401 | 
| 429 /** return At^2 + Bt + C | 402 /** return At^2 + Bt + C | 
| 430 */ | 403 */ | 
| 431 static SkScalar eval_quadratic(SkScalar A, SkScalar B, SkScalar C, SkScalar t) | 404 static SkScalar eval_quadratic(SkScalar A, SkScalar B, SkScalar C, SkScalar t) { | 
| 432 { |  | 
| 433     SkASSERT(t >= 0 && t <= SK_Scalar1); | 405     SkASSERT(t >= 0 && t <= SK_Scalar1); | 
| 434 | 406 | 
| 435     return SkScalarMulAdd(SkScalarMulAdd(A, t, B), t, C); | 407     return SkScalarMulAdd(SkScalarMulAdd(A, t, B), t, C); | 
| 436 } | 408 } | 
| 437 | 409 | 
| 438 static SkScalar eval_cubic_derivative(const SkScalar src[], SkScalar t) | 410 static SkScalar eval_cubic_derivative(const SkScalar src[], SkScalar t) { | 
| 439 { |  | 
| 440     SkScalar A = src[6] + 3*(src[2] - src[4]) - src[0]; | 411     SkScalar A = src[6] + 3*(src[2] - src[4]) - src[0]; | 
| 441     SkScalar B = 2*(src[4] - 2 * src[2] + src[0]); | 412     SkScalar B = 2*(src[4] - 2 * src[2] + src[0]); | 
| 442     SkScalar C = src[2] - src[0]; | 413     SkScalar C = src[2] - src[0]; | 
| 443 | 414 | 
| 444     return eval_quadratic(A, B, C, t); | 415     return eval_quadratic(A, B, C, t); | 
| 445 } | 416 } | 
| 446 | 417 | 
| 447 static SkScalar eval_cubic_2ndDerivative(const SkScalar src[], SkScalar t) | 418 static SkScalar eval_cubic_2ndDerivative(const SkScalar src[], SkScalar t) { | 
| 448 { |  | 
| 449     SkScalar A = src[6] + 3*(src[2] - src[4]) - src[0]; | 419     SkScalar A = src[6] + 3*(src[2] - src[4]) - src[0]; | 
| 450     SkScalar B = src[4] - 2 * src[2] + src[0]; | 420     SkScalar B = src[4] - 2 * src[2] + src[0]; | 
| 451 | 421 | 
| 452     return SkScalarMulAdd(A, t, B); | 422     return SkScalarMulAdd(A, t, B); | 
| 453 } | 423 } | 
| 454 | 424 | 
| 455 void SkEvalCubicAt(const SkPoint src[4], SkScalar t, SkPoint* loc, SkVector* tan
      gent, SkVector* curvature) | 425 void SkEvalCubicAt(const SkPoint src[4], SkScalar t, SkPoint* loc, | 
| 456 { | 426                    SkVector* tangent, SkVector* curvature) { | 
| 457     SkASSERT(src); | 427     SkASSERT(src); | 
| 458     SkASSERT(t >= 0 && t <= SK_Scalar1); | 428     SkASSERT(t >= 0 && t <= SK_Scalar1); | 
| 459 | 429 | 
| 460     if (loc) | 430     if (loc) { | 
| 461         loc->set(eval_cubic(&src[0].fX, t), eval_cubic(&src[0].fY, t)); | 431         loc->set(eval_cubic(&src[0].fX, t), eval_cubic(&src[0].fY, t)); | 
| 462     if (tangent) | 432     } | 
|  | 433     if (tangent) { | 
| 463         tangent->set(eval_cubic_derivative(&src[0].fX, t), | 434         tangent->set(eval_cubic_derivative(&src[0].fX, t), | 
| 464                      eval_cubic_derivative(&src[0].fY, t)); | 435                      eval_cubic_derivative(&src[0].fY, t)); | 
| 465     if (curvature) | 436     } | 
|  | 437     if (curvature) { | 
| 466         curvature->set(eval_cubic_2ndDerivative(&src[0].fX, t), | 438         curvature->set(eval_cubic_2ndDerivative(&src[0].fX, t), | 
| 467                        eval_cubic_2ndDerivative(&src[0].fY, t)); | 439                        eval_cubic_2ndDerivative(&src[0].fY, t)); | 
|  | 440     } | 
| 468 } | 441 } | 
| 469 | 442 | 
| 470 /** Cubic'(t) = At^2 + Bt + C, where | 443 /** Cubic'(t) = At^2 + Bt + C, where | 
| 471     A = 3(-a + 3(b - c) + d) | 444     A = 3(-a + 3(b - c) + d) | 
| 472     B = 6(a - 2b + c) | 445     B = 6(a - 2b + c) | 
| 473     C = 3(b - a) | 446     C = 3(b - a) | 
| 474     Solve for t, keeping only those that fit betwee 0 < t < 1 | 447     Solve for t, keeping only those that fit betwee 0 < t < 1 | 
| 475 */ | 448 */ | 
| 476 int SkFindCubicExtrema(SkScalar a, SkScalar b, SkScalar c, SkScalar d, SkScalar 
      tValues[2]) | 449 int SkFindCubicExtrema(SkScalar a, SkScalar b, SkScalar c, SkScalar d, | 
| 477 { | 450                        SkScalar tValues[2]) { | 
| 478     // we divide A,B,C by 3 to simplify | 451     // we divide A,B,C by 3 to simplify | 
| 479     SkScalar A = d - a + 3*(b - c); | 452     SkScalar A = d - a + 3*(b - c); | 
| 480     SkScalar B = 2*(a - b - b + c); | 453     SkScalar B = 2*(a - b - b + c); | 
| 481     SkScalar C = b - a; | 454     SkScalar C = b - a; | 
| 482 | 455 | 
| 483     return SkFindUnitQuadRoots(A, B, C, tValues); | 456     return SkFindUnitQuadRoots(A, B, C, tValues); | 
| 484 } | 457 } | 
| 485 | 458 | 
| 486 static void interp_cubic_coords(const SkScalar* src, SkScalar* dst, SkScalar t) | 459 static void interp_cubic_coords(const SkScalar* src, SkScalar* dst, | 
| 487 { | 460                                 SkScalar t) { | 
| 488     SkScalar    ab = SkScalarInterp(src[0], src[2], t); | 461     SkScalar    ab = SkScalarInterp(src[0], src[2], t); | 
| 489     SkScalar    bc = SkScalarInterp(src[2], src[4], t); | 462     SkScalar    bc = SkScalarInterp(src[2], src[4], t); | 
| 490     SkScalar    cd = SkScalarInterp(src[4], src[6], t); | 463     SkScalar    cd = SkScalarInterp(src[4], src[6], t); | 
| 491     SkScalar    abc = SkScalarInterp(ab, bc, t); | 464     SkScalar    abc = SkScalarInterp(ab, bc, t); | 
| 492     SkScalar    bcd = SkScalarInterp(bc, cd, t); | 465     SkScalar    bcd = SkScalarInterp(bc, cd, t); | 
| 493     SkScalar    abcd = SkScalarInterp(abc, bcd, t); | 466     SkScalar    abcd = SkScalarInterp(abc, bcd, t); | 
| 494 | 467 | 
| 495     dst[0] = src[0]; | 468     dst[0] = src[0]; | 
| 496     dst[2] = ab; | 469     dst[2] = ab; | 
| 497     dst[4] = abc; | 470     dst[4] = abc; | 
| 498     dst[6] = abcd; | 471     dst[6] = abcd; | 
| 499     dst[8] = bcd; | 472     dst[8] = bcd; | 
| 500     dst[10] = cd; | 473     dst[10] = cd; | 
| 501     dst[12] = src[6]; | 474     dst[12] = src[6]; | 
| 502 } | 475 } | 
| 503 | 476 | 
| 504 void SkChopCubicAt(const SkPoint src[4], SkPoint dst[7], SkScalar t) | 477 void SkChopCubicAt(const SkPoint src[4], SkPoint dst[7], SkScalar t) { | 
| 505 { |  | 
| 506     SkASSERT(t > 0 && t < SK_Scalar1); | 478     SkASSERT(t > 0 && t < SK_Scalar1); | 
| 507 | 479 | 
| 508     interp_cubic_coords(&src[0].fX, &dst[0].fX, t); | 480     interp_cubic_coords(&src[0].fX, &dst[0].fX, t); | 
| 509     interp_cubic_coords(&src[0].fY, &dst[0].fY, t); | 481     interp_cubic_coords(&src[0].fY, &dst[0].fY, t); | 
| 510 } | 482 } | 
| 511 | 483 | 
| 512 /*  http://code.google.com/p/skia/issues/detail?id=32 | 484 /*  http://code.google.com/p/skia/issues/detail?id=32 | 
| 513 | 485 | 
| 514     This test code would fail when we didn't check the return result of | 486     This test code would fail when we didn't check the return result of | 
| 515     valid_unit_divide in SkChopCubicAt(... tValues[], int roots). The reason is | 487     valid_unit_divide in SkChopCubicAt(... tValues[], int roots). The reason is | 
| 516     that after the first chop, the parameters to valid_unit_divide are equal | 488     that after the first chop, the parameters to valid_unit_divide are equal | 
| 517     (thanks to finite float precision and rounding in the subtracts). Thus | 489     (thanks to finite float precision and rounding in the subtracts). Thus | 
| 518     even though the 2nd tValue looks < 1.0, after we renormalize it, we end | 490     even though the 2nd tValue looks < 1.0, after we renormalize it, we end | 
| 519     up with 1.0, hence the need to check and just return the last cubic as | 491     up with 1.0, hence the need to check and just return the last cubic as | 
| 520     a degenerate clump of 4 points in the sampe place. | 492     a degenerate clump of 4 points in the sampe place. | 
| 521 | 493 | 
| 522     static void test_cubic() { | 494     static void test_cubic() { | 
| 523         SkPoint src[4] = { | 495         SkPoint src[4] = { | 
| 524             { 556.25000, 523.03003 }, | 496             { 556.25000, 523.03003 }, | 
| 525             { 556.23999, 522.96002 }, | 497             { 556.23999, 522.96002 }, | 
| 526             { 556.21997, 522.89001 }, | 498             { 556.21997, 522.89001 }, | 
| 527             { 556.21997, 522.82001 } | 499             { 556.21997, 522.82001 } | 
| 528         }; | 500         }; | 
| 529         SkPoint dst[10]; | 501         SkPoint dst[10]; | 
| 530         SkScalar tval[] = { 0.33333334f, 0.99999994f }; | 502         SkScalar tval[] = { 0.33333334f, 0.99999994f }; | 
| 531         SkChopCubicAt(src, dst, tval, 2); | 503         SkChopCubicAt(src, dst, tval, 2); | 
| 532     } | 504     } | 
| 533  */ | 505  */ | 
| 534 | 506 | 
| 535 void SkChopCubicAt(const SkPoint src[4], SkPoint dst[], const SkScalar tValues[]
      , int roots) | 507 void SkChopCubicAt(const SkPoint src[4], SkPoint dst[], | 
| 536 { | 508                    const SkScalar tValues[], int roots) { | 
| 537 #ifdef SK_DEBUG | 509 #ifdef SK_DEBUG | 
| 538     { | 510     { | 
| 539         for (int i = 0; i < roots - 1; i++) | 511         for (int i = 0; i < roots - 1; i++) | 
| 540         { | 512         { | 
| 541             SkASSERT(is_unit_interval(tValues[i])); | 513             SkASSERT(is_unit_interval(tValues[i])); | 
| 542             SkASSERT(is_unit_interval(tValues[i+1])); | 514             SkASSERT(is_unit_interval(tValues[i+1])); | 
| 543             SkASSERT(tValues[i] < tValues[i+1]); | 515             SkASSERT(tValues[i] < tValues[i+1]); | 
| 544         } | 516         } | 
| 545     } | 517     } | 
| 546 #endif | 518 #endif | 
| 547 | 519 | 
| 548     if (dst) | 520     if (dst) { | 
| 549     { | 521         if (roots == 0) { // nothing to chop | 
| 550         if (roots == 0) // nothing to chop |  | 
| 551             memcpy(dst, src, 4*sizeof(SkPoint)); | 522             memcpy(dst, src, 4*sizeof(SkPoint)); | 
| 552         else | 523         } else { | 
| 553         { |  | 
| 554             SkScalar    t = tValues[0]; | 524             SkScalar    t = tValues[0]; | 
| 555             SkPoint     tmp[4]; | 525             SkPoint     tmp[4]; | 
| 556 | 526 | 
| 557             for (int i = 0; i < roots; i++) | 527             for (int i = 0; i < roots; i++) { | 
| 558             { |  | 
| 559                 SkChopCubicAt(src, dst, t); | 528                 SkChopCubicAt(src, dst, t); | 
| 560                 if (i == roots - 1) | 529                 if (i == roots - 1) { | 
| 561                     break; | 530                     break; | 
|  | 531                 } | 
| 562 | 532 | 
| 563                 dst += 3; | 533                 dst += 3; | 
| 564                 // have src point to the remaining cubic (after the chop) | 534                 // have src point to the remaining cubic (after the chop) | 
| 565                 memcpy(tmp, dst, 4 * sizeof(SkPoint)); | 535                 memcpy(tmp, dst, 4 * sizeof(SkPoint)); | 
| 566                 src = tmp; | 536                 src = tmp; | 
| 567 | 537 | 
| 568                 // watch out in case the renormalized t isn't in range | 538                 // watch out in case the renormalized t isn't in range | 
| 569                 if (!valid_unit_divide(tValues[i+1] - tValues[i], | 539                 if (!valid_unit_divide(tValues[i+1] - tValues[i], | 
| 570                                        SK_Scalar1 - tValues[i], &t)) { | 540                                        SK_Scalar1 - tValues[i], &t)) { | 
| 571                     // if we can't, just create a degenerate cubic | 541                     // if we can't, just create a degenerate cubic | 
| 572                     dst[4] = dst[5] = dst[6] = src[3]; | 542                     dst[4] = dst[5] = dst[6] = src[3]; | 
| 573                     break; | 543                     break; | 
| 574                 } | 544                 } | 
| 575             } | 545             } | 
| 576         } | 546         } | 
| 577     } | 547     } | 
| 578 } | 548 } | 
| 579 | 549 | 
| 580 void SkChopCubicAtHalf(const SkPoint src[4], SkPoint dst[7]) | 550 void SkChopCubicAtHalf(const SkPoint src[4], SkPoint dst[7]) { | 
| 581 { |  | 
| 582     SkScalar x01 = SkScalarAve(src[0].fX, src[1].fX); | 551     SkScalar x01 = SkScalarAve(src[0].fX, src[1].fX); | 
| 583     SkScalar y01 = SkScalarAve(src[0].fY, src[1].fY); | 552     SkScalar y01 = SkScalarAve(src[0].fY, src[1].fY); | 
| 584     SkScalar x12 = SkScalarAve(src[1].fX, src[2].fX); | 553     SkScalar x12 = SkScalarAve(src[1].fX, src[2].fX); | 
| 585     SkScalar y12 = SkScalarAve(src[1].fY, src[2].fY); | 554     SkScalar y12 = SkScalarAve(src[1].fY, src[2].fY); | 
| 586     SkScalar x23 = SkScalarAve(src[2].fX, src[3].fX); | 555     SkScalar x23 = SkScalarAve(src[2].fX, src[3].fX); | 
| 587     SkScalar y23 = SkScalarAve(src[2].fY, src[3].fY); | 556     SkScalar y23 = SkScalarAve(src[2].fY, src[3].fY); | 
| 588 | 557 | 
| 589     SkScalar x012 = SkScalarAve(x01, x12); | 558     SkScalar x012 = SkScalarAve(x01, x12); | 
| 590     SkScalar y012 = SkScalarAve(y01, y12); | 559     SkScalar y012 = SkScalarAve(y01, y12); | 
| 591     SkScalar x123 = SkScalarAve(x12, x23); | 560     SkScalar x123 = SkScalarAve(x12, x23); | 
| 592     SkScalar y123 = SkScalarAve(y12, y23); | 561     SkScalar y123 = SkScalarAve(y12, y23); | 
| 593 | 562 | 
| 594     dst[0] = src[0]; | 563     dst[0] = src[0]; | 
| 595     dst[1].set(x01, y01); | 564     dst[1].set(x01, y01); | 
| 596     dst[2].set(x012, y012); | 565     dst[2].set(x012, y012); | 
| 597     dst[3].set(SkScalarAve(x012, x123), SkScalarAve(y012, y123)); | 566     dst[3].set(SkScalarAve(x012, x123), SkScalarAve(y012, y123)); | 
| 598     dst[4].set(x123, y123); | 567     dst[4].set(x123, y123); | 
| 599     dst[5].set(x23, y23); | 568     dst[5].set(x23, y23); | 
| 600     dst[6] = src[3]; | 569     dst[6] = src[3]; | 
| 601 } | 570 } | 
| 602 | 571 | 
| 603 static void flatten_double_cubic_extrema(SkScalar coords[14]) | 572 static void flatten_double_cubic_extrema(SkScalar coords[14]) { | 
| 604 { |  | 
| 605     coords[4] = coords[8] = coords[6]; | 573     coords[4] = coords[8] = coords[6]; | 
| 606 } | 574 } | 
| 607 | 575 | 
| 608 /** Given 4 points on a cubic bezier, chop it into 1, 2, 3 beziers such that | 576 /** Given 4 points on a cubic bezier, chop it into 1, 2, 3 beziers such that | 
| 609     the resulting beziers are monotonic in Y. This is called by the scan convert
      er. | 577     the resulting beziers are monotonic in Y. This is called by the scan convert
      er. | 
| 610     Depending on what is returned, dst[] is treated as follows | 578     Depending on what is returned, dst[] is treated as follows | 
| 611     0   dst[0..3] is the original cubic | 579     0   dst[0..3] is the original cubic | 
| 612     1   dst[0..3] and dst[3..6] are the two new cubics | 580     1   dst[0..3] and dst[3..6] are the two new cubics | 
| 613     2   dst[0..3], dst[3..6], dst[6..9] are the three new cubics | 581     2   dst[0..3], dst[3..6], dst[6..9] are the three new cubics | 
| 614     If dst == null, it is ignored and only the count is returned. | 582     If dst == null, it is ignored and only the count is returned. | 
| (...skipping 34 matching lines...) Expand 10 before | Expand all | Expand 10 after  Loading... | 
| 649 | 617 | 
| 650     Inflection means that curvature is zero. | 618     Inflection means that curvature is zero. | 
| 651     Curvature is [F' x F''] / [F'^3] | 619     Curvature is [F' x F''] / [F'^3] | 
| 652     So we solve F'x X F''y - F'y X F''y == 0 | 620     So we solve F'x X F''y - F'y X F''y == 0 | 
| 653     After some canceling of the cubic term, we get | 621     After some canceling of the cubic term, we get | 
| 654     A = b - a | 622     A = b - a | 
| 655     B = c - 2b + a | 623     B = c - 2b + a | 
| 656     C = d - 3c + 3b - a | 624     C = d - 3c + 3b - a | 
| 657     (BxCy - ByCx)t^2 + (AxCy - AyCx)t + AxBy - AyBx == 0 | 625     (BxCy - ByCx)t^2 + (AxCy - AyCx)t + AxBy - AyBx == 0 | 
| 658 */ | 626 */ | 
| 659 int SkFindCubicInflections(const SkPoint src[4], SkScalar tValues[]) | 627 int SkFindCubicInflections(const SkPoint src[4], SkScalar tValues[]) { | 
| 660 { |  | 
| 661     SkScalar    Ax = src[1].fX - src[0].fX; | 628     SkScalar    Ax = src[1].fX - src[0].fX; | 
| 662     SkScalar    Ay = src[1].fY - src[0].fY; | 629     SkScalar    Ay = src[1].fY - src[0].fY; | 
| 663     SkScalar    Bx = src[2].fX - 2 * src[1].fX + src[0].fX; | 630     SkScalar    Bx = src[2].fX - 2 * src[1].fX + src[0].fX; | 
| 664     SkScalar    By = src[2].fY - 2 * src[1].fY + src[0].fY; | 631     SkScalar    By = src[2].fY - 2 * src[1].fY + src[0].fY; | 
| 665     SkScalar    Cx = src[3].fX + 3 * (src[1].fX - src[2].fX) - src[0].fX; | 632     SkScalar    Cx = src[3].fX + 3 * (src[1].fX - src[2].fX) - src[0].fX; | 
| 666     SkScalar    Cy = src[3].fY + 3 * (src[1].fY - src[2].fY) - src[0].fY; | 633     SkScalar    Cy = src[3].fY + 3 * (src[1].fY - src[2].fY) - src[0].fY; | 
| 667 | 634 | 
| 668     return SkFindUnitQuadRoots(Bx*Cy - By*Cx, Ax*Cy - Ay*Cx, Ax*By - Ay*Bx, tVal
      ues); | 635     return SkFindUnitQuadRoots(Bx*Cy - By*Cx, Ax*Cy - Ay*Cx, Ax*By - Ay*Bx, tVal
      ues); | 
| 669 } | 636 } | 
| 670 | 637 | 
| 671 int SkChopCubicAtInflections(const SkPoint src[], SkPoint dst[10]) | 638 int SkChopCubicAtInflections(const SkPoint src[], SkPoint dst[10]) { | 
| 672 { |  | 
| 673     SkScalar    tValues[2]; | 639     SkScalar    tValues[2]; | 
| 674     int         count = SkFindCubicInflections(src, tValues); | 640     int         count = SkFindCubicInflections(src, tValues); | 
| 675 | 641 | 
| 676     if (dst) | 642     if (dst) { | 
| 677     { | 643         if (count == 0) { | 
| 678         if (count == 0) |  | 
| 679             memcpy(dst, src, 4 * sizeof(SkPoint)); | 644             memcpy(dst, src, 4 * sizeof(SkPoint)); | 
| 680         else | 645         } else { | 
| 681             SkChopCubicAt(src, dst, tValues, count); | 646             SkChopCubicAt(src, dst, tValues, count); | 
|  | 647         } | 
| 682     } | 648     } | 
| 683     return count + 1; | 649     return count + 1; | 
| 684 } | 650 } | 
| 685 | 651 | 
| 686 template <typename T> void bubble_sort(T array[], int count) | 652 template <typename T> void bubble_sort(T array[], int count) { | 
| 687 { |  | 
| 688     for (int i = count - 1; i > 0; --i) | 653     for (int i = count - 1; i > 0; --i) | 
| 689         for (int j = i; j > 0; --j) | 654         for (int j = i; j > 0; --j) | 
| 690             if (array[j] < array[j-1]) | 655             if (array[j] < array[j-1]) | 
| 691             { | 656             { | 
| 692                 T   tmp(array[j]); | 657                 T   tmp(array[j]); | 
| 693                 array[j] = array[j-1]; | 658                 array[j] = array[j-1]; | 
| 694                 array[j-1] = tmp; | 659                 array[j-1] = tmp; | 
| 695             } | 660             } | 
| 696 } | 661 } | 
| 697 | 662 | 
| 698 // newton refinement |  | 
| 699 #if 0 |  | 
| 700 static SkScalar refine_cubic_root(const SkFP coeff[4], SkScalar root) |  | 
| 701 { |  | 
| 702     //  x1 = x0 - f(t) / f'(t) |  | 
| 703 |  | 
| 704     SkFP    T = SkScalarToFloat(root); |  | 
| 705     SkFP    N, D; |  | 
| 706 |  | 
| 707     // f' = 3*coeff[0]*T^2 + 2*coeff[1]*T + coeff[2] |  | 
| 708     D = SkFPMul(SkFPMul(coeff[0], SkFPMul(T,T)), 3); |  | 
| 709     D = SkFPAdd(D, SkFPMulInt(SkFPMul(coeff[1], T), 2)); |  | 
| 710     D = SkFPAdd(D, coeff[2]); |  | 
| 711 |  | 
| 712     if (D == 0) |  | 
| 713         return root; |  | 
| 714 |  | 
| 715     // f = coeff[0]*T^3 + coeff[1]*T^2 + coeff[2]*T + coeff[3] |  | 
| 716     N = SkFPMul(SkFPMul(SkFPMul(T, T), T), coeff[0]); |  | 
| 717     N = SkFPAdd(N, SkFPMul(SkFPMul(T, T), coeff[1])); |  | 
| 718     N = SkFPAdd(N, SkFPMul(T, coeff[2])); |  | 
| 719     N = SkFPAdd(N, coeff[3]); |  | 
| 720 |  | 
| 721     if (N) |  | 
| 722     { |  | 
| 723         SkScalar delta = SkFPToScalar(SkFPDiv(N, D)); |  | 
| 724 |  | 
| 725         if (delta) |  | 
| 726             root -= delta; |  | 
| 727     } |  | 
| 728     return root; |  | 
| 729 } |  | 
| 730 #endif |  | 
| 731 |  | 
| 732 /** | 663 /** | 
| 733  *  Given an array and count, remove all pair-wise duplicates from the array, | 664  *  Given an array and count, remove all pair-wise duplicates from the array, | 
| 734  *  keeping the existing sorting, and return the new count | 665  *  keeping the existing sorting, and return the new count | 
| 735  */ | 666  */ | 
| 736 static int collaps_duplicates(float array[], int count) { | 667 static int collaps_duplicates(SkScalar array[], int count) { | 
| 737     for (int n = count; n > 1; --n) { | 668     for (int n = count; n > 1; --n) { | 
| 738         if (array[0] == array[1]) { | 669         if (array[0] == array[1]) { | 
| 739             for (int i = 1; i < n; ++i) { | 670             for (int i = 1; i < n; ++i) { | 
| 740                 array[i - 1] = array[i]; | 671                 array[i - 1] = array[i]; | 
| 741             } | 672             } | 
| 742             count -= 1; | 673             count -= 1; | 
| 743         } else { | 674         } else { | 
| 744             array += 1; | 675             array += 1; | 
| 745         } | 676         } | 
| 746     } | 677     } | 
| 747     return count; | 678     return count; | 
| 748 } | 679 } | 
| 749 | 680 | 
| 750 #ifdef SK_DEBUG | 681 #ifdef SK_DEBUG | 
| 751 | 682 | 
| 752 #define TEST_COLLAPS_ENTRY(array)   array, SK_ARRAY_COUNT(array) | 683 #define TEST_COLLAPS_ENTRY(array)   array, SK_ARRAY_COUNT(array) | 
| 753 | 684 | 
| 754 static void test_collaps_duplicates() { | 685 static void test_collaps_duplicates() { | 
| 755     static bool gOnce; | 686     static bool gOnce; | 
| 756     if (gOnce) { return; } | 687     if (gOnce) { return; } | 
| 757     gOnce = true; | 688     gOnce = true; | 
| 758     const float src0[] = { 0 }; | 689     const SkScalar src0[] = { 0 }; | 
| 759     const float src1[] = { 0, 0 }; | 690     const SkScalar src1[] = { 0, 0 }; | 
| 760     const float src2[] = { 0, 1 }; | 691     const SkScalar src2[] = { 0, 1 }; | 
| 761     const float src3[] = { 0, 0, 0 }; | 692     const SkScalar src3[] = { 0, 0, 0 }; | 
| 762     const float src4[] = { 0, 0, 1 }; | 693     const SkScalar src4[] = { 0, 0, 1 }; | 
| 763     const float src5[] = { 0, 1, 1 }; | 694     const SkScalar src5[] = { 0, 1, 1 }; | 
| 764     const float src6[] = { 0, 1, 2 }; | 695     const SkScalar src6[] = { 0, 1, 2 }; | 
| 765     const struct { | 696     const struct { | 
| 766         const float* fData; | 697         const SkScalar* fData; | 
| 767         int fCount; | 698         int fCount; | 
| 768         int fCollapsedCount; | 699         int fCollapsedCount; | 
| 769     } data[] = { | 700     } data[] = { | 
| 770         { TEST_COLLAPS_ENTRY(src0), 1 }, | 701         { TEST_COLLAPS_ENTRY(src0), 1 }, | 
| 771         { TEST_COLLAPS_ENTRY(src1), 1 }, | 702         { TEST_COLLAPS_ENTRY(src1), 1 }, | 
| 772         { TEST_COLLAPS_ENTRY(src2), 2 }, | 703         { TEST_COLLAPS_ENTRY(src2), 2 }, | 
| 773         { TEST_COLLAPS_ENTRY(src3), 1 }, | 704         { TEST_COLLAPS_ENTRY(src3), 1 }, | 
| 774         { TEST_COLLAPS_ENTRY(src4), 2 }, | 705         { TEST_COLLAPS_ENTRY(src4), 2 }, | 
| 775         { TEST_COLLAPS_ENTRY(src5), 2 }, | 706         { TEST_COLLAPS_ENTRY(src5), 2 }, | 
| 776         { TEST_COLLAPS_ENTRY(src6), 3 }, | 707         { TEST_COLLAPS_ENTRY(src6), 3 }, | 
| 777     }; | 708     }; | 
| 778     for (size_t i = 0; i < SK_ARRAY_COUNT(data); ++i) { | 709     for (size_t i = 0; i < SK_ARRAY_COUNT(data); ++i) { | 
| 779         float dst[3]; | 710         SkScalar dst[3]; | 
| 780         memcpy(dst, data[i].fData, data[i].fCount * sizeof(dst[0])); | 711         memcpy(dst, data[i].fData, data[i].fCount * sizeof(dst[0])); | 
| 781         int count = collaps_duplicates(dst, data[i].fCount); | 712         int count = collaps_duplicates(dst, data[i].fCount); | 
| 782         SkASSERT(data[i].fCollapsedCount == count); | 713         SkASSERT(data[i].fCollapsedCount == count); | 
| 783         for (int j = 1; j < count; ++j) { | 714         for (int j = 1; j < count; ++j) { | 
| 784             SkASSERT(dst[j-1] < dst[j]); | 715             SkASSERT(dst[j-1] < dst[j]); | 
| 785         } | 716         } | 
| 786     } | 717     } | 
| 787 } | 718 } | 
| 788 #endif | 719 #endif | 
| 789 | 720 | 
| 790 static SkScalar SkScalarCubeRoot(SkScalar x) { | 721 static SkScalar SkScalarCubeRoot(SkScalar x) { | 
| 791     return sk_float_pow(x, 0.3333333f); | 722     return SkScalarPow(x, 0.3333333f); | 
| 792 } | 723 } | 
| 793 | 724 | 
| 794 /*  Solve coeff(t) == 0, returning the number of roots that | 725 /*  Solve coeff(t) == 0, returning the number of roots that | 
| 795     lie withing 0 < t < 1. | 726     lie withing 0 < t < 1. | 
| 796     coeff[0]t^3 + coeff[1]t^2 + coeff[2]t + coeff[3] | 727     coeff[0]t^3 + coeff[1]t^2 + coeff[2]t + coeff[3] | 
| 797 | 728 | 
| 798     Eliminates repeated roots (so that all tValues are distinct, and are always | 729     Eliminates repeated roots (so that all tValues are distinct, and are always | 
| 799     in increasing order. | 730     in increasing order. | 
| 800 */ | 731 */ | 
| 801 static int solve_cubic_polynomial(const SkScalar coeff[4], SkScalar tValues[3]) | 732 static int solve_cubic_poly(const SkScalar coeff[4], SkScalar tValues[3]) { | 
| 802 { | 733     if (SkScalarNearlyZero(coeff[0])) {  // we're just a quadratic | 
| 803     if (SkScalarNearlyZero(coeff[0]))   // we're just a quadratic |  | 
| 804     { |  | 
| 805         return SkFindUnitQuadRoots(coeff[1], coeff[2], coeff[3], tValues); | 734         return SkFindUnitQuadRoots(coeff[1], coeff[2], coeff[3], tValues); | 
| 806     } | 735     } | 
| 807 | 736 | 
| 808     SkScalar a, b, c, Q, R; | 737     SkScalar a, b, c, Q, R; | 
| 809 | 738 | 
| 810     { | 739     { | 
| 811         SkASSERT(coeff[0] != 0); | 740         SkASSERT(coeff[0] != 0); | 
| 812 | 741 | 
| 813         SkScalar inva = SkScalarInvert(coeff[0]); | 742         SkScalar inva = SkScalarInvert(coeff[0]); | 
| 814         a = coeff[1] * inva; | 743         a = coeff[1] * inva; | 
| 815         b = coeff[2] * inva; | 744         b = coeff[2] * inva; | 
| 816         c = coeff[3] * inva; | 745         c = coeff[3] * inva; | 
| 817     } | 746     } | 
| 818     Q = (a*a - b*3) / 9; | 747     Q = (a*a - b*3) / 9; | 
| 819     R = (2*a*a*a - 9*a*b + 27*c) / 54; | 748     R = (2*a*a*a - 9*a*b + 27*c) / 54; | 
| 820 | 749 | 
| 821     SkScalar Q3 = Q * Q * Q; | 750     SkScalar Q3 = Q * Q * Q; | 
| 822     SkScalar R2MinusQ3 = R * R - Q3; | 751     SkScalar R2MinusQ3 = R * R - Q3; | 
| 823     SkScalar adiv3 = a / 3; | 752     SkScalar adiv3 = a / 3; | 
| 824 | 753 | 
| 825     SkScalar*   roots = tValues; | 754     SkScalar*   roots = tValues; | 
| 826     SkScalar    r; | 755     SkScalar    r; | 
| 827 | 756 | 
| 828     if (R2MinusQ3 < 0)   // we have 3 real roots | 757     if (R2MinusQ3 < 0) { // we have 3 real roots | 
| 829     { | 758         SkScalar theta = SkScalarACos(R / SkScalarSqrt(Q3)); | 
| 830         float theta = sk_float_acos(R / sk_float_sqrt(Q3)); | 759         SkScalar neg2RootQ = -2 * SkScalarSqrt(Q); | 
| 831         float neg2RootQ = -2 * sk_float_sqrt(Q); |  | 
| 832 | 760 | 
| 833         r = neg2RootQ * sk_float_cos(theta/3) - adiv3; | 761         r = neg2RootQ * SkScalarCos(theta/3) - adiv3; | 
| 834         if (is_unit_interval(r)) | 762         if (is_unit_interval(r)) { | 
| 835             *roots++ = r; | 763             *roots++ = r; | 
| 836 | 764         } | 
| 837         r = neg2RootQ * sk_float_cos((theta + 2*SK_ScalarPI)/3) - adiv3; | 765         r = neg2RootQ * SkScalarCos((theta + 2*SK_ScalarPI)/3) - adiv3; | 
| 838         if (is_unit_interval(r)) | 766         if (is_unit_interval(r)) { | 
| 839             *roots++ = r; | 767             *roots++ = r; | 
| 840 | 768         } | 
| 841         r = neg2RootQ * sk_float_cos((theta - 2*SK_ScalarPI)/3) - adiv3; | 769         r = neg2RootQ * SkScalarCos((theta - 2*SK_ScalarPI)/3) - adiv3; | 
| 842         if (is_unit_interval(r)) | 770         if (is_unit_interval(r)) { | 
| 843             *roots++ = r; | 771             *roots++ = r; | 
| 844 | 772         } | 
| 845         SkDEBUGCODE(test_collaps_duplicates();) | 773         SkDEBUGCODE(test_collaps_duplicates();) | 
| 846 | 774 | 
| 847         // now sort the roots | 775         // now sort the roots | 
| 848         int count = (int)(roots - tValues); | 776         int count = (int)(roots - tValues); | 
| 849         SkASSERT((unsigned)count <= 3); | 777         SkASSERT((unsigned)count <= 3); | 
| 850         bubble_sort(tValues, count); | 778         bubble_sort(tValues, count); | 
| 851         count = collaps_duplicates(tValues, count); | 779         count = collaps_duplicates(tValues, count); | 
| 852         roots = tValues + count;    // so we compute the proper count below | 780         roots = tValues + count;    // so we compute the proper count below | 
| 853     } | 781     } else {              // we have 1 real root | 
| 854     else                // we have 1 real root |  | 
| 855     { |  | 
| 856         SkScalar A = SkScalarAbs(R) + SkScalarSqrt(R2MinusQ3); | 782         SkScalar A = SkScalarAbs(R) + SkScalarSqrt(R2MinusQ3); | 
| 857         A = SkScalarCubeRoot(A); | 783         A = SkScalarCubeRoot(A); | 
| 858         if (R > 0) | 784         if (R > 0) { | 
| 859             A = -A; | 785             A = -A; | 
| 860 | 786         } | 
| 861         if (A != 0) | 787         if (A != 0) { | 
| 862             A += Q / A; | 788             A += Q / A; | 
|  | 789         } | 
| 863         r = A - adiv3; | 790         r = A - adiv3; | 
| 864         if (is_unit_interval(r)) | 791         if (is_unit_interval(r)) { | 
| 865             *roots++ = r; | 792             *roots++ = r; | 
|  | 793         } | 
| 866     } | 794     } | 
| 867 | 795 | 
| 868     return (int)(roots - tValues); | 796     return (int)(roots - tValues); | 
| 869 } | 797 } | 
| 870 | 798 | 
| 871 /*  Looking for F' dot F'' == 0 | 799 /*  Looking for F' dot F'' == 0 | 
| 872 | 800 | 
| 873     A = b - a | 801     A = b - a | 
| 874     B = c - 2b + a | 802     B = c - 2b + a | 
| 875     C = d - 3c + 3b - a | 803     C = d - 3c + 3b - a | 
| 876 | 804 | 
| 877     F' = 3Ct^2 + 6Bt + 3A | 805     F' = 3Ct^2 + 6Bt + 3A | 
| 878     F'' = 6Ct + 6B | 806     F'' = 6Ct + 6B | 
| 879 | 807 | 
| 880     F' dot F'' -> CCt^3 + 3BCt^2 + (2BB + CA)t + AB | 808     F' dot F'' -> CCt^3 + 3BCt^2 + (2BB + CA)t + AB | 
| 881 */ | 809 */ | 
| 882 static void formulate_F1DotF2(const SkScalar src[], SkScalar coeff[4]) | 810 static void formulate_F1DotF2(const SkScalar src[], SkScalar coeff[4]) { | 
| 883 { |  | 
| 884     SkScalar    a = src[2] - src[0]; | 811     SkScalar    a = src[2] - src[0]; | 
| 885     SkScalar    b = src[4] - 2 * src[2] + src[0]; | 812     SkScalar    b = src[4] - 2 * src[2] + src[0]; | 
| 886     SkScalar    c = src[6] + 3 * (src[2] - src[4]) - src[0]; | 813     SkScalar    c = src[6] + 3 * (src[2] - src[4]) - src[0]; | 
| 887 | 814 | 
| 888     coeff[0] = c * c; | 815     coeff[0] = c * c; | 
| 889     coeff[1] = 3 * b * c; | 816     coeff[1] = 3 * b * c; | 
| 890     coeff[2] = 2 * b * b + c * a; | 817     coeff[2] = 2 * b * b + c * a; | 
| 891     coeff[3] = a * b; | 818     coeff[3] = a * b; | 
| 892 } | 819 } | 
| 893 | 820 | 
| 894 // EXPERIMENTAL: can set this to zero to accept all t-values 0 < t < 1 |  | 
| 895 //#define kMinTValueForChopping (SK_Scalar1 / 256) |  | 
| 896 #define kMinTValueForChopping   0 |  | 
| 897 |  | 
| 898 /*  Looking for F' dot F'' == 0 | 821 /*  Looking for F' dot F'' == 0 | 
| 899 | 822 | 
| 900     A = b - a | 823     A = b - a | 
| 901     B = c - 2b + a | 824     B = c - 2b + a | 
| 902     C = d - 3c + 3b - a | 825     C = d - 3c + 3b - a | 
| 903 | 826 | 
| 904     F' = 3Ct^2 + 6Bt + 3A | 827     F' = 3Ct^2 + 6Bt + 3A | 
| 905     F'' = 6Ct + 6B | 828     F'' = 6Ct + 6B | 
| 906 | 829 | 
| 907     F' dot F'' -> CCt^3 + 3BCt^2 + (2BB + CA)t + AB | 830     F' dot F'' -> CCt^3 + 3BCt^2 + (2BB + CA)t + AB | 
| 908 */ | 831 */ | 
| 909 int SkFindCubicMaxCurvature(const SkPoint src[4], SkScalar tValues[3]) | 832 int SkFindCubicMaxCurvature(const SkPoint src[4], SkScalar tValues[3]) { | 
| 910 { |  | 
| 911     SkScalar coeffX[4], coeffY[4]; | 833     SkScalar coeffX[4], coeffY[4]; | 
| 912     int      i; | 834     int      i; | 
| 913 | 835 | 
| 914     formulate_F1DotF2(&src[0].fX, coeffX); | 836     formulate_F1DotF2(&src[0].fX, coeffX); | 
| 915     formulate_F1DotF2(&src[0].fY, coeffY); | 837     formulate_F1DotF2(&src[0].fY, coeffY); | 
| 916 | 838 | 
| 917     for (i = 0; i < 4; i++) | 839     for (i = 0; i < 4; i++) { | 
| 918         coeffX[i] += coeffY[i]; | 840         coeffX[i] += coeffY[i]; | 
|  | 841     } | 
| 919 | 842 | 
| 920     SkScalar    t[3]; | 843     SkScalar    t[3]; | 
| 921     int         count = solve_cubic_polynomial(coeffX, t); | 844     int         count = solve_cubic_poly(coeffX, t); | 
| 922     int         maxCount = 0; | 845     int         maxCount = 0; | 
| 923 | 846 | 
| 924     // now remove extrema where the curvature is zero (mins) | 847     // now remove extrema where the curvature is zero (mins) | 
| 925     // !!!! need a test for this !!!! | 848     // !!!! need a test for this !!!! | 
| 926     for (i = 0; i < count; i++) | 849     for (i = 0; i < count; i++) { | 
| 927     { |  | 
| 928         // if (not_min_curvature()) | 850         // if (not_min_curvature()) | 
| 929         if (t[i] > kMinTValueForChopping && t[i] < SK_Scalar1 - kMinTValueForCho
      pping) | 851         if (t[i] > 0 && t[i] < SK_Scalar1) { | 
| 930             tValues[maxCount++] = t[i]; | 852             tValues[maxCount++] = t[i]; | 
|  | 853         } | 
| 931     } | 854     } | 
| 932     return maxCount; | 855     return maxCount; | 
| 933 } | 856 } | 
| 934 | 857 | 
| 935 int SkChopCubicAtMaxCurvature(const SkPoint src[4], SkPoint dst[13], SkScalar tV
      alues[3]) | 858 int SkChopCubicAtMaxCurvature(const SkPoint src[4], SkPoint dst[13], | 
| 936 { | 859                               SkScalar tValues[3]) { | 
| 937     SkScalar    t_storage[3]; | 860     SkScalar    t_storage[3]; | 
| 938 | 861 | 
| 939     if (tValues == NULL) | 862     if (tValues == NULL) { | 
| 940         tValues = t_storage; | 863         tValues = t_storage; | 
|  | 864     } | 
| 941 | 865 | 
| 942     int count = SkFindCubicMaxCurvature(src, tValues); | 866     int count = SkFindCubicMaxCurvature(src, tValues); | 
| 943 | 867 | 
| 944     if (dst) { | 868     if (dst) { | 
| 945         if (count == 0) | 869         if (count == 0) { | 
| 946             memcpy(dst, src, 4 * sizeof(SkPoint)); | 870             memcpy(dst, src, 4 * sizeof(SkPoint)); | 
| 947         else | 871         } else { | 
| 948             SkChopCubicAt(src, dst, tValues, count); | 872             SkChopCubicAt(src, dst, tValues, count); | 
|  | 873         } | 
| 949     } | 874     } | 
| 950     return count + 1; | 875     return count + 1; | 
| 951 } | 876 } | 
| 952 | 877 | 
| 953 bool SkXRayCrossesMonotonicCubic(const SkXRay& pt, const SkPoint cubic[4], bool*
       ambiguous) { | 878 bool SkXRayCrossesMonotonicCubic(const SkXRay& pt, const SkPoint cubic[4], | 
|  | 879                                  bool* ambiguous) { | 
| 954     if (ambiguous) { | 880     if (ambiguous) { | 
| 955         *ambiguous = false; | 881         *ambiguous = false; | 
| 956     } | 882     } | 
| 957 | 883 | 
| 958     // Find the minimum and maximum y of the extrema, which are the | 884     // Find the minimum and maximum y of the extrema, which are the | 
| 959     // first and last points since this cubic is monotonic | 885     // first and last points since this cubic is monotonic | 
| 960     SkScalar min_y = SkMinScalar(cubic[0].fY, cubic[3].fY); | 886     SkScalar min_y = SkMinScalar(cubic[0].fY, cubic[3].fY); | 
| 961     SkScalar max_y = SkMaxScalar(cubic[0].fY, cubic[3].fY); | 887     SkScalar max_y = SkMaxScalar(cubic[0].fY, cubic[3].fY); | 
| 962 | 888 | 
| 963     if (pt.fY == cubic[0].fY | 889     if (pt.fY == cubic[0].fY | 
| (...skipping 93 matching lines...) Expand 10 before | Expand all | Expand 10 after  Loading... | 
| 1057         *ambiguous |= locally_ambiguous; | 983         *ambiguous |= locally_ambiguous; | 
| 1058     } | 984     } | 
| 1059     if (num_monotonic_cubics > 1) | 985     if (num_monotonic_cubics > 1) | 
| 1060         if (SkXRayCrossesMonotonicCubic(pt, &monotonic_cubics[6], &locally_ambig
      uous)) | 986         if (SkXRayCrossesMonotonicCubic(pt, &monotonic_cubics[6], &locally_ambig
      uous)) | 
| 1061             ++num_crossings; | 987             ++num_crossings; | 
| 1062     if (ambiguous) { | 988     if (ambiguous) { | 
| 1063         *ambiguous |= locally_ambiguous; | 989         *ambiguous |= locally_ambiguous; | 
| 1064     } | 990     } | 
| 1065     return num_crossings; | 991     return num_crossings; | 
| 1066 } | 992 } | 
| 1067 //////////////////////////////////////////////////////////////////////////////// | 993 | 
|  | 994 /////////////////////////////////////////////////////////////////////////////// | 
| 1068 | 995 | 
| 1069 /*  Find t value for quadratic [a, b, c] = d. | 996 /*  Find t value for quadratic [a, b, c] = d. | 
| 1070     Return 0 if there is no solution within [0, 1) | 997     Return 0 if there is no solution within [0, 1) | 
| 1071 */ | 998 */ | 
| 1072 static SkScalar quad_solve(SkScalar a, SkScalar b, SkScalar c, SkScalar d) | 999 static SkScalar quad_solve(SkScalar a, SkScalar b, SkScalar c, SkScalar d) { | 
| 1073 { |  | 
| 1074     // At^2 + Bt + C = d | 1000     // At^2 + Bt + C = d | 
| 1075     SkScalar A = a - 2 * b + c; | 1001     SkScalar A = a - 2 * b + c; | 
| 1076     SkScalar B = 2 * (b - a); | 1002     SkScalar B = 2 * (b - a); | 
| 1077     SkScalar C = a - d; | 1003     SkScalar C = a - d; | 
| 1078 | 1004 | 
| 1079     SkScalar    roots[2]; | 1005     SkScalar    roots[2]; | 
| 1080     int         count = SkFindUnitQuadRoots(A, B, C, roots); | 1006     int         count = SkFindUnitQuadRoots(A, B, C, roots); | 
| 1081 | 1007 | 
| 1082     SkASSERT(count <= 1); | 1008     SkASSERT(count <= 1); | 
| 1083     return count == 1 ? roots[0] : 0; | 1009     return count == 1 ? roots[0] : 0; | 
| 1084 } | 1010 } | 
| 1085 | 1011 | 
| 1086 /*  given a quad-curve and a point (x,y), chop the quad at that point and place | 1012 /*  given a quad-curve and a point (x,y), chop the quad at that point and place | 
| 1087     the new off-curve point and endpoint into 'dest'. | 1013     the new off-curve point and endpoint into 'dest'. | 
| 1088     Should only return false if the computed pos is the start of the curve | 1014     Should only return false if the computed pos is the start of the curve | 
| 1089     (i.e. root == 0) | 1015     (i.e. root == 0) | 
| 1090 */ | 1016 */ | 
| 1091 static bool truncate_last_curve(const SkPoint quad[3], SkScalar x, SkScalar y, S
      kPoint* dest) | 1017 static bool truncate_last_curve(const SkPoint quad[3], SkScalar x, SkScalar y, | 
| 1092 { | 1018                                 SkPoint* dest) { | 
| 1093     const SkScalar* base; | 1019     const SkScalar* base; | 
| 1094     SkScalar        value; | 1020     SkScalar        value; | 
| 1095 | 1021 | 
| 1096     if (SkScalarAbs(x) < SkScalarAbs(y)) { | 1022     if (SkScalarAbs(x) < SkScalarAbs(y)) { | 
| 1097         base = &quad[0].fX; | 1023         base = &quad[0].fX; | 
| 1098         value = x; | 1024         value = x; | 
| 1099     } else { | 1025     } else { | 
| 1100         base = &quad[0].fY; | 1026         base = &quad[0].fY; | 
| 1101         value = y; | 1027         value = y; | 
| 1102     } | 1028     } | 
| 1103 | 1029 | 
| 1104     // note: this returns 0 if it thinks value is out of range, meaning the | 1030     // note: this returns 0 if it thinks value is out of range, meaning the | 
| 1105     // root might return something outside of [0, 1) | 1031     // root might return something outside of [0, 1) | 
| 1106     SkScalar t = quad_solve(base[0], base[2], base[4], value); | 1032     SkScalar t = quad_solve(base[0], base[2], base[4], value); | 
| 1107 | 1033 | 
| 1108     if (t > 0) | 1034     if (t > 0) { | 
| 1109     { |  | 
| 1110         SkPoint tmp[5]; | 1035         SkPoint tmp[5]; | 
| 1111         SkChopQuadAt(quad, tmp, t); | 1036         SkChopQuadAt(quad, tmp, t); | 
| 1112         dest[0] = tmp[1]; | 1037         dest[0] = tmp[1]; | 
| 1113         dest[1].set(x, y); | 1038         dest[1].set(x, y); | 
| 1114         return true; | 1039         return true; | 
| 1115     } else { | 1040     } else { | 
| 1116         /*  t == 0 means either the value triggered a root outside of [0, 1) | 1041         /*  t == 0 means either the value triggered a root outside of [0, 1) | 
| 1117             For our purposes, we can ignore the <= 0 roots, but we want to | 1042             For our purposes, we can ignore the <= 0 roots, but we want to | 
| 1118             catch the >= 1 roots (which given our caller, will basically mean | 1043             catch the >= 1 roots (which given our caller, will basically mean | 
| 1119             a root of 1, give-or-take numerical instability). If we are in the | 1044             a root of 1, give-or-take numerical instability). If we are in the | 
| (...skipping 40 matching lines...) Expand 10 before | Expand all | Expand 10 after  Loading... | 
| 1160     { SK_ScalarTanPIOver8,   -SK_Scalar1            }, | 1085     { SK_ScalarTanPIOver8,   -SK_Scalar1            }, | 
| 1161     { SK_MID_RRECT_OFFSET,   -SK_MID_RRECT_OFFSET   }, | 1086     { SK_MID_RRECT_OFFSET,   -SK_MID_RRECT_OFFSET   }, | 
| 1162     { SK_Scalar1,            -SK_ScalarTanPIOver8   }, | 1087     { SK_Scalar1,            -SK_ScalarTanPIOver8   }, | 
| 1163 | 1088 | 
| 1164     { SK_Scalar1,            0                      } | 1089     { SK_Scalar1,            0                      } | 
| 1165 #undef SK_MID_RRECT_OFFSET | 1090 #undef SK_MID_RRECT_OFFSET | 
| 1166 }; | 1091 }; | 
| 1167 | 1092 | 
| 1168 int SkBuildQuadArc(const SkVector& uStart, const SkVector& uStop, | 1093 int SkBuildQuadArc(const SkVector& uStart, const SkVector& uStop, | 
| 1169                    SkRotationDirection dir, const SkMatrix* userMatrix, | 1094                    SkRotationDirection dir, const SkMatrix* userMatrix, | 
| 1170                    SkPoint quadPoints[]) | 1095                    SkPoint quadPoints[]) { | 
| 1171 { |  | 
| 1172     // rotate by x,y so that uStart is (1.0) | 1096     // rotate by x,y so that uStart is (1.0) | 
| 1173     SkScalar x = SkPoint::DotProduct(uStart, uStop); | 1097     SkScalar x = SkPoint::DotProduct(uStart, uStop); | 
| 1174     SkScalar y = SkPoint::CrossProduct(uStart, uStop); | 1098     SkScalar y = SkPoint::CrossProduct(uStart, uStop); | 
| 1175 | 1099 | 
| 1176     SkScalar absX = SkScalarAbs(x); | 1100     SkScalar absX = SkScalarAbs(x); | 
| 1177     SkScalar absY = SkScalarAbs(y); | 1101     SkScalar absY = SkScalarAbs(y); | 
| 1178 | 1102 | 
| 1179     int pointCount; | 1103     int pointCount; | 
| 1180 | 1104 | 
| 1181     // check for (effectively) coincident vectors | 1105     // check for (effectively) coincident vectors | 
| 1182     // this can happen if our angle is nearly 0 or nearly 180 (y == 0) | 1106     // this can happen if our angle is nearly 0 or nearly 180 (y == 0) | 
| 1183     // ... we use the dot-prod to distinguish between 0 and 180 (x > 0) | 1107     // ... we use the dot-prod to distinguish between 0 and 180 (x > 0) | 
| 1184     if (absY <= SK_ScalarNearlyZero && x > 0 && | 1108     if (absY <= SK_ScalarNearlyZero && x > 0 && | 
| 1185         ((y >= 0 && kCW_SkRotationDirection == dir) || | 1109         ((y >= 0 && kCW_SkRotationDirection == dir) || | 
| 1186          (y <= 0 && kCCW_SkRotationDirection == dir))) { | 1110          (y <= 0 && kCCW_SkRotationDirection == dir))) { | 
| 1187 | 1111 | 
| 1188         // just return the start-point | 1112         // just return the start-point | 
| 1189         quadPoints[0].set(SK_Scalar1, 0); | 1113         quadPoints[0].set(SK_Scalar1, 0); | 
| 1190         pointCount = 1; | 1114         pointCount = 1; | 
| 1191     } else { | 1115     } else { | 
| 1192         if (dir == kCCW_SkRotationDirection) | 1116         if (dir == kCCW_SkRotationDirection) { | 
| 1193             y = -y; | 1117             y = -y; | 
| 1194 | 1118         } | 
| 1195         // what octant (quadratic curve) is [xy] in? | 1119         // what octant (quadratic curve) is [xy] in? | 
| 1196         int oct = 0; | 1120         int oct = 0; | 
| 1197         bool sameSign = true; | 1121         bool sameSign = true; | 
| 1198 | 1122 | 
| 1199         if (0 == y) | 1123         if (0 == y) { | 
| 1200         { |  | 
| 1201             oct = 4;        // 180 | 1124             oct = 4;        // 180 | 
| 1202             SkASSERT(SkScalarAbs(x + SK_Scalar1) <= SK_ScalarNearlyZero); | 1125             SkASSERT(SkScalarAbs(x + SK_Scalar1) <= SK_ScalarNearlyZero); | 
| 1203         } | 1126         } else if (0 == x) { | 
| 1204         else if (0 == x) |  | 
| 1205         { |  | 
| 1206             SkASSERT(absY - SK_Scalar1 <= SK_ScalarNearlyZero); | 1127             SkASSERT(absY - SK_Scalar1 <= SK_ScalarNearlyZero); | 
| 1207             if (y > 0) | 1128             oct = y > 0 ? 2 : 6; // 90 : 270 | 
| 1208                 oct = 2;    // 90 | 1129         } else { | 
| 1209             else | 1130             if (y < 0) { | 
| 1210                 oct = 6;    // 270 |  | 
| 1211         } |  | 
| 1212         else |  | 
| 1213         { |  | 
| 1214             if (y < 0) |  | 
| 1215                 oct += 4; | 1131                 oct += 4; | 
| 1216             if ((x < 0) != (y < 0)) | 1132             } | 
| 1217             { | 1133             if ((x < 0) != (y < 0)) { | 
| 1218                 oct += 2; | 1134                 oct += 2; | 
| 1219                 sameSign = false; | 1135                 sameSign = false; | 
| 1220             } | 1136             } | 
| 1221             if ((absX < absY) == sameSign) | 1137             if ((absX < absY) == sameSign) { | 
| 1222                 oct += 1; | 1138                 oct += 1; | 
|  | 1139             } | 
| 1223         } | 1140         } | 
| 1224 | 1141 | 
| 1225         int wholeCount = oct << 1; | 1142         int wholeCount = oct << 1; | 
| 1226         memcpy(quadPoints, gQuadCirclePts, (wholeCount + 1) * sizeof(SkPoint)); | 1143         memcpy(quadPoints, gQuadCirclePts, (wholeCount + 1) * sizeof(SkPoint)); | 
| 1227 | 1144 | 
| 1228         const SkPoint* arc = &gQuadCirclePts[wholeCount]; | 1145         const SkPoint* arc = &gQuadCirclePts[wholeCount]; | 
| 1229         if (truncate_last_curve(arc, x, y, &quadPoints[wholeCount + 1])) | 1146         if (truncate_last_curve(arc, x, y, &quadPoints[wholeCount + 1])) { | 
| 1230         { |  | 
| 1231             wholeCount += 2; | 1147             wholeCount += 2; | 
| 1232         } | 1148         } | 
| 1233         pointCount = wholeCount + 1; | 1149         pointCount = wholeCount + 1; | 
| 1234     } | 1150     } | 
| 1235 | 1151 | 
| 1236     // now handle counter-clockwise and the initial unitStart rotation | 1152     // now handle counter-clockwise and the initial unitStart rotation | 
| 1237     SkMatrix    matrix; | 1153     SkMatrix    matrix; | 
| 1238     matrix.setSinCos(uStart.fY, uStart.fX); | 1154     matrix.setSinCos(uStart.fY, uStart.fX); | 
| 1239     if (dir == kCCW_SkRotationDirection) { | 1155     if (dir == kCCW_SkRotationDirection) { | 
| 1240         matrix.preScale(SK_Scalar1, -SK_Scalar1); | 1156         matrix.preScale(SK_Scalar1, -SK_Scalar1); | 
| (...skipping 278 matching lines...) Expand 10 before | Expand all | Expand 10 after  Loading... | 
| 1519     } | 1435     } | 
| 1520     if (this->findYExtrema(&t)) { | 1436     if (this->findYExtrema(&t)) { | 
| 1521         this->evalAt(t, &pts[count++]); | 1437         this->evalAt(t, &pts[count++]); | 
| 1522     } | 1438     } | 
| 1523     bounds->set(pts, count); | 1439     bounds->set(pts, count); | 
| 1524 } | 1440 } | 
| 1525 | 1441 | 
| 1526 void SkConic::computeFastBounds(SkRect* bounds) const { | 1442 void SkConic::computeFastBounds(SkRect* bounds) const { | 
| 1527     bounds->set(fPts, 3); | 1443     bounds->set(fPts, 3); | 
| 1528 } | 1444 } | 
| OLD | NEW | 
|---|