1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/gfx/skia/trunk/src/core/SkCubicClipper.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,154 @@
1.4 +
1.5 +/*
1.6 + * Copyright 2009 The Android Open Source Project
1.7 + *
1.8 + * Use of this source code is governed by a BSD-style license that can be
1.9 + * found in the LICENSE file.
1.10 + */
1.11 +
1.12 +
1.13 +#include "SkCubicClipper.h"
1.14 +#include "SkGeometry.h"
1.15 +
1.16 +SkCubicClipper::SkCubicClipper() {
1.17 + fClip.setEmpty();
1.18 +}
1.19 +
1.20 +void SkCubicClipper::setClip(const SkIRect& clip) {
1.21 + // conver to scalars, since that's where we'll see the points
1.22 + fClip.set(clip);
1.23 +}
1.24 +
1.25 +
1.26 +static bool chopMonoCubicAtY(SkPoint pts[4], SkScalar y, SkScalar* t) {
1.27 + SkScalar ycrv[4];
1.28 + ycrv[0] = pts[0].fY - y;
1.29 + ycrv[1] = pts[1].fY - y;
1.30 + ycrv[2] = pts[2].fY - y;
1.31 + ycrv[3] = pts[3].fY - y;
1.32 +
1.33 +#ifdef NEWTON_RAPHSON // Quadratic convergence, typically <= 3 iterations.
1.34 + // Initial guess.
1.35 + // TODO(turk): Check for zero denominator? Shouldn't happen unless the curve
1.36 + // is not only monotonic but degenerate.
1.37 + SkScalar t1 = ycrv[0] / (ycrv[0] - ycrv[3]);
1.38 +
1.39 + // Newton's iterations.
1.40 + const SkScalar tol = SK_Scalar1 / 16384; // This leaves 2 fixed noise bits.
1.41 + SkScalar t0;
1.42 + const int maxiters = 5;
1.43 + int iters = 0;
1.44 + bool converged;
1.45 + do {
1.46 + t0 = t1;
1.47 + SkScalar y01 = SkScalarInterp(ycrv[0], ycrv[1], t0);
1.48 + SkScalar y12 = SkScalarInterp(ycrv[1], ycrv[2], t0);
1.49 + SkScalar y23 = SkScalarInterp(ycrv[2], ycrv[3], t0);
1.50 + SkScalar y012 = SkScalarInterp(y01, y12, t0);
1.51 + SkScalar y123 = SkScalarInterp(y12, y23, t0);
1.52 + SkScalar y0123 = SkScalarInterp(y012, y123, t0);
1.53 + SkScalar yder = (y123 - y012) * 3;
1.54 + // TODO(turk): check for yder==0: horizontal.
1.55 + t1 -= y0123 / yder;
1.56 + converged = SkScalarAbs(t1 - t0) <= tol; // NaN-safe
1.57 + ++iters;
1.58 + } while (!converged && (iters < maxiters));
1.59 + *t = t1; // Return the result.
1.60 +
1.61 + // The result might be valid, even if outside of the range [0, 1], but
1.62 + // we never evaluate a Bezier outside this interval, so we return false.
1.63 + if (t1 < 0 || t1 > SK_Scalar1)
1.64 + return false; // This shouldn't happen, but check anyway.
1.65 + return converged;
1.66 +
1.67 +#else // BISECTION // Linear convergence, typically 16 iterations.
1.68 +
1.69 + // Check that the endpoints straddle zero.
1.70 + SkScalar tNeg, tPos; // Negative and positive function parameters.
1.71 + if (ycrv[0] < 0) {
1.72 + if (ycrv[3] < 0)
1.73 + return false;
1.74 + tNeg = 0;
1.75 + tPos = SK_Scalar1;
1.76 + } else if (ycrv[0] > 0) {
1.77 + if (ycrv[3] > 0)
1.78 + return false;
1.79 + tNeg = SK_Scalar1;
1.80 + tPos = 0;
1.81 + } else {
1.82 + *t = 0;
1.83 + return true;
1.84 + }
1.85 +
1.86 + const SkScalar tol = SK_Scalar1 / 65536; // 1 for fixed, 1e-5 for float.
1.87 + int iters = 0;
1.88 + do {
1.89 + SkScalar tMid = (tPos + tNeg) / 2;
1.90 + SkScalar y01 = SkScalarInterp(ycrv[0], ycrv[1], tMid);
1.91 + SkScalar y12 = SkScalarInterp(ycrv[1], ycrv[2], tMid);
1.92 + SkScalar y23 = SkScalarInterp(ycrv[2], ycrv[3], tMid);
1.93 + SkScalar y012 = SkScalarInterp(y01, y12, tMid);
1.94 + SkScalar y123 = SkScalarInterp(y12, y23, tMid);
1.95 + SkScalar y0123 = SkScalarInterp(y012, y123, tMid);
1.96 + if (y0123 == 0) {
1.97 + *t = tMid;
1.98 + return true;
1.99 + }
1.100 + if (y0123 < 0) tNeg = tMid;
1.101 + else tPos = tMid;
1.102 + ++iters;
1.103 + } while (!(SkScalarAbs(tPos - tNeg) <= tol)); // Nan-safe
1.104 +
1.105 + *t = (tNeg + tPos) / 2;
1.106 + return true;
1.107 +#endif // BISECTION
1.108 +}
1.109 +
1.110 +
1.111 +bool SkCubicClipper::clipCubic(const SkPoint srcPts[4], SkPoint dst[4]) {
1.112 + bool reverse;
1.113 +
1.114 + // we need the data to be monotonically descending in Y
1.115 + if (srcPts[0].fY > srcPts[3].fY) {
1.116 + dst[0] = srcPts[3];
1.117 + dst[1] = srcPts[2];
1.118 + dst[2] = srcPts[1];
1.119 + dst[3] = srcPts[0];
1.120 + reverse = true;
1.121 + } else {
1.122 + memcpy(dst, srcPts, 4 * sizeof(SkPoint));
1.123 + reverse = false;
1.124 + }
1.125 +
1.126 + // are we completely above or below
1.127 + const SkScalar ctop = fClip.fTop;
1.128 + const SkScalar cbot = fClip.fBottom;
1.129 + if (dst[3].fY <= ctop || dst[0].fY >= cbot) {
1.130 + return false;
1.131 + }
1.132 +
1.133 + SkScalar t;
1.134 + SkPoint tmp[7]; // for SkChopCubicAt
1.135 +
1.136 + // are we partially above
1.137 + if (dst[0].fY < ctop && chopMonoCubicAtY(dst, ctop, &t)) {
1.138 + SkChopCubicAt(dst, tmp, t);
1.139 + dst[0] = tmp[3];
1.140 + dst[1] = tmp[4];
1.141 + dst[2] = tmp[5];
1.142 + }
1.143 +
1.144 + // are we partially below
1.145 + if (dst[3].fY > cbot && chopMonoCubicAtY(dst, cbot, &t)) {
1.146 + SkChopCubicAt(dst, tmp, t);
1.147 + dst[1] = tmp[1];
1.148 + dst[2] = tmp[2];
1.149 + dst[3] = tmp[3];
1.150 + }
1.151 +
1.152 + if (reverse) {
1.153 + SkTSwap<SkPoint>(dst[0], dst[3]);
1.154 + SkTSwap<SkPoint>(dst[1], dst[2]);
1.155 + }
1.156 + return true;
1.157 +}
