| 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 |