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