The Tor Browser / file comparison
comparison: gfx/skia/trunk/src/core/SkCubicClipper.cpp
gfx/skia/trunk/src/core/SkCubicClipper.cpp
- branch
- TOR_BUG_9701
- changeset 15
- b8a032363ba2
equal
deleted
inserted
replaced
| -1:000000000000 | 0:e6bdfc1aafb5 |
|---|---|
| 1 | |
| 2 /* | |
| 3 * Copyright 2009 The Android Open Source Project | |
| 4 * | |
| 5 * Use of this source code is governed by a BSD-style license that can be | |
| 6 * found in the LICENSE file. | |
| 7 */ | |
| 8 | |
| 9 | |
| 10 #include "SkCubicClipper.h" | |
| 11 #include "SkGeometry.h" | |
| 12 | |
| 13 SkCubicClipper::SkCubicClipper() { | |
| 14 fClip.setEmpty(); | |
| 15 } | |
| 16 | |
| 17 void SkCubicClipper::setClip(const SkIRect& clip) { | |
| 18 // conver to scalars, since that's where we'll see the points | |
| 19 fClip.set(clip); | |
| 20 } | |
| 21 | |
| 22 | |
| 23 static bool chopMonoCubicAtY(SkPoint pts[4], SkScalar y, SkScalar* t) { | |
| 24 SkScalar ycrv[4]; | |
| 25 ycrv[0] = pts[0].fY - y; | |
| 26 ycrv[1] = pts[1].fY - y; | |
| 27 ycrv[2] = pts[2].fY - y; | |
| 28 ycrv[3] = pts[3].fY - y; | |
| 29 | |
| 30 #ifdef NEWTON_RAPHSON // Quadratic convergence, typically <= 3 iterations. | |
| 31 // Initial guess. | |
| 32 // TODO(turk): Check for zero denominator? Shouldn't happen unless the curve | |
| 33 // is not only monotonic but degenerate. | |
| 34 SkScalar t1 = ycrv[0] / (ycrv[0] - ycrv[3]); | |
| 35 | |
| 36 // Newton's iterations. | |
| 37 const SkScalar tol = SK_Scalar1 / 16384; // This leaves 2 fixed noise bits. | |
| 38 SkScalar t0; | |
| 39 const int maxiters = 5; | |
| 40 int iters = 0; | |
| 41 bool converged; | |
| 42 do { | |
| 43 t0 = t1; | |
| 44 SkScalar y01 = SkScalarInterp(ycrv[0], ycrv[1], t0); | |
| 45 SkScalar y12 = SkScalarInterp(ycrv[1], ycrv[2], t0); | |
| 46 SkScalar y23 = SkScalarInterp(ycrv[2], ycrv[3], t0); | |
| 47 SkScalar y012 = SkScalarInterp(y01, y12, t0); | |
| 48 SkScalar y123 = SkScalarInterp(y12, y23, t0); | |
| 49 SkScalar y0123 = SkScalarInterp(y012, y123, t0); | |
| 50 SkScalar yder = (y123 - y012) * 3; | |
| 51 // TODO(turk): check for yder==0: horizontal. | |
| 52 t1 -= y0123 / yder; | |
| 53 converged = SkScalarAbs(t1 - t0) <= tol; // NaN-safe | |
| 54 ++iters; | |
| 55 } while (!converged && (iters < maxiters)); | |
| 56 *t = t1; // Return the result. | |
| 57 | |
| 58 // The result might be valid, even if outside of the range [0, 1], but | |
| 59 // we never evaluate a Bezier outside this interval, so we return false. | |
| 60 if (t1 < 0 || t1 > SK_Scalar1) | |
| 61 return false; // This shouldn't happen, but check anyway. | |
| 62 return converged; | |
| 63 | |
| 64 #else // BISECTION // Linear convergence, typically 16 iterations. | |
| 65 | |
| 66 // Check that the endpoints straddle zero. | |
| 67 SkScalar tNeg, tPos; // Negative and positive function parameters. | |
| 68 if (ycrv[0] < 0) { | |
| 69 if (ycrv[3] < 0) | |
| 70 return false; | |
| 71 tNeg = 0; | |
| 72 tPos = SK_Scalar1; | |
| 73 } else if (ycrv[0] > 0) { | |
| 74 if (ycrv[3] > 0) | |
| 75 return false; | |
| 76 tNeg = SK_Scalar1; | |
| 77 tPos = 0; | |
| 78 } else { | |
| 79 *t = 0; | |
| 80 return true; | |
| 81 } | |
| 82 | |
| 83 const SkScalar tol = SK_Scalar1 / 65536; // 1 for fixed, 1e-5 for float. | |
| 84 int iters = 0; | |
| 85 do { | |
| 86 SkScalar tMid = (tPos + tNeg) / 2; | |
| 87 SkScalar y01 = SkScalarInterp(ycrv[0], ycrv[1], tMid); | |
| 88 SkScalar y12 = SkScalarInterp(ycrv[1], ycrv[2], tMid); | |
| 89 SkScalar y23 = SkScalarInterp(ycrv[2], ycrv[3], tMid); | |
| 90 SkScalar y012 = SkScalarInterp(y01, y12, tMid); | |
| 91 SkScalar y123 = SkScalarInterp(y12, y23, tMid); | |
| 92 SkScalar y0123 = SkScalarInterp(y012, y123, tMid); | |
| 93 if (y0123 == 0) { | |
| 94 *t = tMid; | |
| 95 return true; | |
| 96 } | |
| 97 if (y0123 < 0) tNeg = tMid; | |
| 98 else tPos = tMid; | |
| 99 ++iters; | |
| 100 } while (!(SkScalarAbs(tPos - tNeg) <= tol)); // Nan-safe | |
| 101 | |
| 102 *t = (tNeg + tPos) / 2; | |
| 103 return true; | |
| 104 #endif // BISECTION | |
| 105 } | |
| 106 | |
| 107 | |
| 108 bool SkCubicClipper::clipCubic(const SkPoint srcPts[4], SkPoint dst[4]) { | |
| 109 bool reverse; | |
| 110 | |
| 111 // we need the data to be monotonically descending in Y | |
| 112 if (srcPts[0].fY > srcPts[3].fY) { | |
| 113 dst[0] = srcPts[3]; | |
| 114 dst[1] = srcPts[2]; | |
| 115 dst[2] = srcPts[1]; | |
| 116 dst[3] = srcPts[0]; | |
| 117 reverse = true; | |
| 118 } else { | |
| 119 memcpy(dst, srcPts, 4 * sizeof(SkPoint)); | |
| 120 reverse = false; | |
| 121 } | |
| 122 | |
| 123 // are we completely above or below | |
| 124 const SkScalar ctop = fClip.fTop; | |
| 125 const SkScalar cbot = fClip.fBottom; | |
| 126 if (dst[3].fY <= ctop || dst[0].fY >= cbot) { | |
| 127 return false; | |
| 128 } | |
| 129 | |
| 130 SkScalar t; | |
| 131 SkPoint tmp[7]; // for SkChopCubicAt | |
| 132 | |
| 133 // are we partially above | |
| 134 if (dst[0].fY < ctop && chopMonoCubicAtY(dst, ctop, &t)) { | |
| 135 SkChopCubicAt(dst, tmp, t); | |
| 136 dst[0] = tmp[3]; | |
| 137 dst[1] = tmp[4]; | |
| 138 dst[2] = tmp[5]; | |
| 139 } | |
| 140 | |
| 141 // are we partially below | |
| 142 if (dst[3].fY > cbot && chopMonoCubicAtY(dst, cbot, &t)) { | |
| 143 SkChopCubicAt(dst, tmp, t); | |
| 144 dst[1] = tmp[1]; | |
| 145 dst[2] = tmp[2]; | |
| 146 dst[3] = tmp[3]; | |
| 147 } | |
| 148 | |
| 149 if (reverse) { | |
| 150 SkTSwap<SkPoint>(dst[0], dst[3]); | |
| 151 SkTSwap<SkPoint>(dst[1], dst[2]); | |
| 152 } | |
| 153 return true; | |
| 154 } |
