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