Home | History | Annotate | Download | only in core 
      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 bool SkCubicClipper::ChopMonoAtY(const 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 && ChopMonoAtY(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 && ChopMonoAtY(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 }
    155