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
SkCubicClipper()12 SkCubicClipper::SkCubicClipper() {
13 fClip.setEmpty();
14 }
15
setClip(const SkIRect & clip)16 void 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
ChopMonoAtY(const SkPoint pts[4],SkScalar y,SkScalar * t)22 bool 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
clipCubic(const SkPoint srcPts[4],SkPoint dst[4])107 bool 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