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 |