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