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 "src/core/SkCubicClipper.h" |
10 | #include "src/core/SkGeometry.h" |
11 | |
12 | #include <utility> |
13 | |
14 | SkCubicClipper::SkCubicClipper() { |
15 | fClip.setEmpty(); |
16 | } |
17 | |
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 | |
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 | |
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 | |