Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(1233)

Side by Side Diff: src/core/SkGeometry.cpp

Issue 174683002: update for coding style, remove explicit floats (Closed) Base URL: https://skia.googlesource.com/skia.git@master
Patch Set: Created 6 years, 10 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
« no previous file with comments | « no previous file | no next file » | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
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
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
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
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
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
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
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 }
OLDNEW
« no previous file with comments | « no previous file | no next file » | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698