OLD | NEW |
1 | 1 |
2 /* | 2 /* |
3 * Copyright 2009 The Android Open Source Project | 3 * Copyright 2009 The Android Open Source Project |
4 * | 4 * |
5 * Use of this source code is governed by a BSD-style license that can be | 5 * Use of this source code is governed by a BSD-style license that can be |
6 * found in the LICENSE file. | 6 * found in the LICENSE file. |
7 */ | 7 */ |
8 | 8 |
9 | 9 |
10 #include "SkCubicClipper.h" | 10 #include "SkCubicClipper.h" |
(...skipping 13 matching lines...) Expand all Loading... |
24 SkScalar ycrv[4]; | 24 SkScalar ycrv[4]; |
25 ycrv[0] = pts[0].fY - y; | 25 ycrv[0] = pts[0].fY - y; |
26 ycrv[1] = pts[1].fY - y; | 26 ycrv[1] = pts[1].fY - y; |
27 ycrv[2] = pts[2].fY - y; | 27 ycrv[2] = pts[2].fY - y; |
28 ycrv[3] = pts[3].fY - y; | 28 ycrv[3] = pts[3].fY - y; |
29 | 29 |
30 #ifdef NEWTON_RAPHSON // Quadratic convergence, typically <= 3 iterations. | 30 #ifdef NEWTON_RAPHSON // Quadratic convergence, typically <= 3 iterations. |
31 // Initial guess. | 31 // Initial guess. |
32 // TODO(turk): Check for zero denominator? Shouldn't happen unless the curve | 32 // TODO(turk): Check for zero denominator? Shouldn't happen unless the curve |
33 // is not only monotonic but degenerate. | 33 // is not only monotonic but degenerate. |
34 #ifdef SK_SCALAR_IS_FLOAT | |
35 SkScalar t1 = ycrv[0] / (ycrv[0] - ycrv[3]); | 34 SkScalar t1 = ycrv[0] / (ycrv[0] - ycrv[3]); |
36 #else // !SK_SCALAR_IS_FLOAT | |
37 SkScalar t1 = SkDivBits(ycrv[0], ycrv[0] - ycrv[3], 16); | |
38 #endif // !SK_SCALAR_IS_FLOAT | |
39 | 35 |
40 // Newton's iterations. | 36 // Newton's iterations. |
41 const SkScalar tol = SK_Scalar1 / 16384; // This leaves 2 fixed noise bits. | 37 const SkScalar tol = SK_Scalar1 / 16384; // This leaves 2 fixed noise bits. |
42 SkScalar t0; | 38 SkScalar t0; |
43 const int maxiters = 5; | 39 const int maxiters = 5; |
44 int iters = 0; | 40 int iters = 0; |
45 bool converged; | 41 bool converged; |
46 do { | 42 do { |
47 t0 = t1; | 43 t0 = t1; |
48 SkScalar y01 = SkScalarInterp(ycrv[0], ycrv[1], t0); | 44 SkScalar y01 = SkScalarInterp(ycrv[0], ycrv[1], t0); |
49 SkScalar y12 = SkScalarInterp(ycrv[1], ycrv[2], t0); | 45 SkScalar y12 = SkScalarInterp(ycrv[1], ycrv[2], t0); |
50 SkScalar y23 = SkScalarInterp(ycrv[2], ycrv[3], t0); | 46 SkScalar y23 = SkScalarInterp(ycrv[2], ycrv[3], t0); |
51 SkScalar y012 = SkScalarInterp(y01, y12, t0); | 47 SkScalar y012 = SkScalarInterp(y01, y12, t0); |
52 SkScalar y123 = SkScalarInterp(y12, y23, t0); | 48 SkScalar y123 = SkScalarInterp(y12, y23, t0); |
53 SkScalar y0123 = SkScalarInterp(y012, y123, t0); | 49 SkScalar y0123 = SkScalarInterp(y012, y123, t0); |
54 SkScalar yder = (y123 - y012) * 3; | 50 SkScalar yder = (y123 - y012) * 3; |
55 // TODO(turk): check for yder==0: horizontal. | 51 // TODO(turk): check for yder==0: horizontal. |
56 #ifdef SK_SCALAR_IS_FLOAT | |
57 t1 -= y0123 / yder; | 52 t1 -= y0123 / yder; |
58 #else // !SK_SCALAR_IS_FLOAT | |
59 t1 -= SkDivBits(y0123, yder, 16); | |
60 #endif // !SK_SCALAR_IS_FLOAT | |
61 converged = SkScalarAbs(t1 - t0) <= tol; // NaN-safe | 53 converged = SkScalarAbs(t1 - t0) <= tol; // NaN-safe |
62 ++iters; | 54 ++iters; |
63 } while (!converged && (iters < maxiters)); | 55 } while (!converged && (iters < maxiters)); |
64 *t = t1; // Return the result. | 56 *t = t1; // Return the result. |
65 | 57 |
66 // The result might be valid, even if outside of the range [0, 1], but | 58 // The result might be valid, even if outside of the range [0, 1], but |
67 // we never evaluate a Bezier outside this interval, so we return false. | 59 // we never evaluate a Bezier outside this interval, so we return false. |
68 if (t1 < 0 || t1 > SK_Scalar1) | 60 if (t1 < 0 || t1 > SK_Scalar1) |
69 return false; // This shouldn't happen, but check anyway. | 61 return false; // This shouldn't happen, but check anyway. |
70 return converged; | 62 return converged; |
(...skipping 82 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
153 dst[2] = tmp[2]; | 145 dst[2] = tmp[2]; |
154 dst[3] = tmp[3]; | 146 dst[3] = tmp[3]; |
155 } | 147 } |
156 | 148 |
157 if (reverse) { | 149 if (reverse) { |
158 SkTSwap<SkPoint>(dst[0], dst[3]); | 150 SkTSwap<SkPoint>(dst[0], dst[3]); |
159 SkTSwap<SkPoint>(dst[1], dst[2]); | 151 SkTSwap<SkPoint>(dst[1], dst[2]); |
160 } | 152 } |
161 return true; | 153 return true; |
162 } | 154 } |
OLD | NEW |