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 #include "src/core/SkCubicClipper.h"
9
10 #include "include/core/SkPoint.h"
11 #include "src/core/SkGeometry.h"
12
13 #include <cstring>
14 #include <utility>
15
SkCubicClipper()16 SkCubicClipper::SkCubicClipper() {
17 fClip.setEmpty();
18 }
19
setClip(const SkIRect & clip)20 void SkCubicClipper::setClip(const SkIRect& clip) {
21 // conver to scalars, since that's where we'll see the points
22 fClip.set(clip);
23 }
24
25
ChopMonoAtY(const SkPoint pts[4],SkScalar y,SkScalar * t)26 bool SkCubicClipper::ChopMonoAtY(const SkPoint pts[4], SkScalar y, SkScalar* t) {
27 SkScalar ycrv[4];
28 ycrv[0] = pts[0].fY - y;
29 ycrv[1] = pts[1].fY - y;
30 ycrv[2] = pts[2].fY - y;
31 ycrv[3] = pts[3].fY - y;
32
33 #ifdef NEWTON_RAPHSON // Quadratic convergence, typically <= 3 iterations.
34 // Initial guess.
35 // TODO(turk): Check for zero denominator? Shouldn't happen unless the curve
36 // is not only monotonic but degenerate.
37 SkScalar t1 = ycrv[0] / (ycrv[0] - ycrv[3]);
38
39 // Newton's iterations.
40 const SkScalar tol = SK_Scalar1 / 16384; // This leaves 2 fixed noise bits.
41 SkScalar t0;
42 const int maxiters = 5;
43 int iters = 0;
44 bool converged;
45 do {
46 t0 = t1;
47 SkScalar y01 = SkScalarInterp(ycrv[0], ycrv[1], t0);
48 SkScalar y12 = SkScalarInterp(ycrv[1], ycrv[2], t0);
49 SkScalar y23 = SkScalarInterp(ycrv[2], ycrv[3], t0);
50 SkScalar y012 = SkScalarInterp(y01, y12, t0);
51 SkScalar y123 = SkScalarInterp(y12, y23, t0);
52 SkScalar y0123 = SkScalarInterp(y012, y123, t0);
53 SkScalar yder = (y123 - y012) * 3;
54 // TODO(turk): check for yder==0: horizontal.
55 t1 -= y0123 / yder;
56 converged = SkScalarAbs(t1 - t0) <= tol; // NaN-safe
57 ++iters;
58 } while (!converged && (iters < maxiters));
59 *t = t1; // Return the result.
60
61 // The result might be valid, even if outside of the range [0, 1], but
62 // we never evaluate a Bezier outside this interval, so we return false.
63 if (t1 < 0 || t1 > SK_Scalar1)
64 return false; // This shouldn't happen, but check anyway.
65 return converged;
66
67 #else // BISECTION // Linear convergence, typically 16 iterations.
68
69 // Check that the endpoints straddle zero.
70 SkScalar tNeg, tPos; // Negative and positive function parameters.
71 if (ycrv[0] < 0) {
72 if (ycrv[3] < 0)
73 return false;
74 tNeg = 0;
75 tPos = SK_Scalar1;
76 } else if (ycrv[0] > 0) {
77 if (ycrv[3] > 0)
78 return false;
79 tNeg = SK_Scalar1;
80 tPos = 0;
81 } else {
82 *t = 0;
83 return true;
84 }
85
86 const SkScalar tol = SK_Scalar1 / 65536; // 1 for fixed, 1e-5 for float.
87 do {
88 SkScalar tMid = (tPos + tNeg) / 2;
89 SkScalar y01 = SkScalarInterp(ycrv[0], ycrv[1], tMid);
90 SkScalar y12 = SkScalarInterp(ycrv[1], ycrv[2], tMid);
91 SkScalar y23 = SkScalarInterp(ycrv[2], ycrv[3], tMid);
92 SkScalar y012 = SkScalarInterp(y01, y12, tMid);
93 SkScalar y123 = SkScalarInterp(y12, y23, tMid);
94 SkScalar y0123 = SkScalarInterp(y012, y123, tMid);
95 if (y0123 == 0) {
96 *t = tMid;
97 return true;
98 }
99 if (y0123 < 0) tNeg = tMid;
100 else tPos = tMid;
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