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