Line data Source code
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 0 : SkCubicClipper::SkCubicClipper() {
13 0 : fClip.setEmpty();
14 0 : }
15 :
16 0 : void SkCubicClipper::setClip(const SkIRect& clip) {
17 : // conver to scalars, since that's where we'll see the points
18 0 : fClip.set(clip);
19 0 : }
20 :
21 :
22 0 : bool SkCubicClipper::ChopMonoAtY(const SkPoint pts[4], SkScalar y, SkScalar* t) {
23 : SkScalar ycrv[4];
24 0 : ycrv[0] = pts[0].fY - y;
25 0 : ycrv[1] = pts[1].fY - y;
26 0 : ycrv[2] = pts[2].fY - y;
27 0 : 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 0 : if (ycrv[0] < 0) {
68 0 : if (ycrv[3] < 0)
69 0 : return false;
70 0 : tNeg = 0;
71 0 : tPos = SK_Scalar1;
72 0 : } else if (ycrv[0] > 0) {
73 0 : if (ycrv[3] > 0)
74 0 : return false;
75 0 : tNeg = SK_Scalar1;
76 0 : tPos = 0;
77 : } else {
78 0 : *t = 0;
79 0 : return true;
80 : }
81 :
82 0 : const SkScalar tol = SK_Scalar1 / 65536; // 1 for fixed, 1e-5 for float.
83 0 : int iters = 0;
84 0 : do {
85 0 : SkScalar tMid = (tPos + tNeg) / 2;
86 0 : SkScalar y01 = SkScalarInterp(ycrv[0], ycrv[1], tMid);
87 0 : SkScalar y12 = SkScalarInterp(ycrv[1], ycrv[2], tMid);
88 0 : SkScalar y23 = SkScalarInterp(ycrv[2], ycrv[3], tMid);
89 0 : SkScalar y012 = SkScalarInterp(y01, y12, tMid);
90 0 : SkScalar y123 = SkScalarInterp(y12, y23, tMid);
91 0 : SkScalar y0123 = SkScalarInterp(y012, y123, tMid);
92 0 : if (y0123 == 0) {
93 0 : *t = tMid;
94 0 : return true;
95 : }
96 0 : if (y0123 < 0) tNeg = tMid;
97 0 : else tPos = tMid;
98 0 : ++iters;
99 0 : } while (!(SkScalarAbs(tPos - tNeg) <= tol)); // Nan-safe
100 :
101 0 : *t = (tNeg + tPos) / 2;
102 0 : return true;
103 : #endif // BISECTION
104 : }
105 :
106 :
107 0 : 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 0 : if (srcPts[0].fY > srcPts[3].fY) {
112 0 : dst[0] = srcPts[3];
113 0 : dst[1] = srcPts[2];
114 0 : dst[2] = srcPts[1];
115 0 : dst[3] = srcPts[0];
116 0 : reverse = true;
117 : } else {
118 0 : memcpy(dst, srcPts, 4 * sizeof(SkPoint));
119 0 : reverse = false;
120 : }
121 :
122 : // are we completely above or below
123 0 : const SkScalar ctop = fClip.fTop;
124 0 : const SkScalar cbot = fClip.fBottom;
125 0 : if (dst[3].fY <= ctop || dst[0].fY >= cbot) {
126 0 : return false;
127 : }
128 :
129 : SkScalar t;
130 : SkPoint tmp[7]; // for SkChopCubicAt
131 :
132 : // are we partially above
133 0 : if (dst[0].fY < ctop && ChopMonoAtY(dst, ctop, &t)) {
134 0 : SkChopCubicAt(dst, tmp, t);
135 0 : dst[0] = tmp[3];
136 0 : dst[1] = tmp[4];
137 0 : dst[2] = tmp[5];
138 : }
139 :
140 : // are we partially below
141 0 : if (dst[3].fY > cbot && ChopMonoAtY(dst, cbot, &t)) {
142 0 : SkChopCubicAt(dst, tmp, t);
143 0 : dst[1] = tmp[1];
144 0 : dst[2] = tmp[2];
145 0 : dst[3] = tmp[3];
146 : }
147 :
148 0 : if (reverse) {
149 0 : SkTSwap<SkPoint>(dst[0], dst[3]);
150 0 : SkTSwap<SkPoint>(dst[1], dst[2]);
151 : }
152 0 : return true;
153 : }
|
