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
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
|
/*
* Copyright 2011 Google Inc.
*
* Use of this source code is governed by a BSD-style license that can be
* found in the LICENSE file.
*/
#include "GrPathUtils.h"
#include "GrPoint.h"
GrScalar GrPathUtils::scaleToleranceToSrc(GrScalar devTol,
const GrMatrix& viewM,
const GrRect& pathBounds) {
// In order to tesselate the path we get a bound on how much the matrix can
// stretch when mapping to screen coordinates.
GrScalar stretch = viewM.getMaxStretch();
GrScalar srcTol = devTol;
if (stretch < 0) {
// take worst case mapRadius amoung four corners.
// (less than perfect)
for (int i = 0; i < 4; ++i) {
GrMatrix mat;
mat.setTranslate((i % 2) ? pathBounds.fLeft : pathBounds.fRight,
(i < 2) ? pathBounds.fTop : pathBounds.fBottom);
mat.postConcat(viewM);
stretch = SkMaxScalar(stretch, mat.mapRadius(SK_Scalar1));
}
}
srcTol = GrScalarDiv(srcTol, stretch);
return srcTol;
}
static const int MAX_POINTS_PER_CURVE = 1 << 10;
static const GrScalar gMinCurveTol = GrFloatToScalar(0.0001f);
uint32_t GrPathUtils::quadraticPointCount(const GrPoint points[],
GrScalar tol) {
if (tol < gMinCurveTol) {
tol = gMinCurveTol;
}
GrAssert(tol > 0);
GrScalar d = points[1].distanceToLineSegmentBetween(points[0], points[2]);
if (d <= tol) {
return 1;
} else {
// Each time we subdivide, d should be cut in 4. So we need to
// subdivide x = log4(d/tol) times. x subdivisions creates 2^(x)
// points.
// 2^(log4(x)) = sqrt(x);
int temp = SkScalarCeil(SkScalarSqrt(SkScalarDiv(d, tol)));
int pow2 = GrNextPow2(temp);
// Because of NaNs & INFs we can wind up with a degenerate temp
// such that pow2 comes out negative. Also, our point generator
// will always output at least one pt.
if (pow2 < 1) {
pow2 = 1;
}
return GrMin(pow2, MAX_POINTS_PER_CURVE);
}
}
uint32_t GrPathUtils::generateQuadraticPoints(const GrPoint& p0,
const GrPoint& p1,
const GrPoint& p2,
GrScalar tolSqd,
GrPoint** points,
uint32_t pointsLeft) {
if (pointsLeft < 2 ||
(p1.distanceToLineSegmentBetweenSqd(p0, p2)) < tolSqd) {
(*points)[0] = p2;
*points += 1;
return 1;
}
GrPoint q[] = {
{ GrScalarAve(p0.fX, p1.fX), GrScalarAve(p0.fY, p1.fY) },
{ GrScalarAve(p1.fX, p2.fX), GrScalarAve(p1.fY, p2.fY) },
};
GrPoint r = { GrScalarAve(q[0].fX, q[1].fX), GrScalarAve(q[0].fY, q[1].fY) };
pointsLeft >>= 1;
uint32_t a = generateQuadraticPoints(p0, q[0], r, tolSqd, points, pointsLeft);
uint32_t b = generateQuadraticPoints(r, q[1], p2, tolSqd, points, pointsLeft);
return a + b;
}
uint32_t GrPathUtils::cubicPointCount(const GrPoint points[],
GrScalar tol) {
if (tol < gMinCurveTol) {
tol = gMinCurveTol;
}
GrAssert(tol > 0);
GrScalar d = GrMax(
points[1].distanceToLineSegmentBetweenSqd(points[0], points[3]),
points[2].distanceToLineSegmentBetweenSqd(points[0], points[3]));
d = SkScalarSqrt(d);
if (d <= tol) {
return 1;
} else {
int temp = SkScalarCeil(SkScalarSqrt(SkScalarDiv(d, tol)));
int pow2 = GrNextPow2(temp);
// Because of NaNs & INFs we can wind up with a degenerate temp
// such that pow2 comes out negative. Also, our point generator
// will always output at least one pt.
if (pow2 < 1) {
pow2 = 1;
}
return GrMin(pow2, MAX_POINTS_PER_CURVE);
}
}
uint32_t GrPathUtils::generateCubicPoints(const GrPoint& p0,
const GrPoint& p1,
const GrPoint& p2,
const GrPoint& p3,
GrScalar tolSqd,
GrPoint** points,
uint32_t pointsLeft) {
if (pointsLeft < 2 ||
(p1.distanceToLineSegmentBetweenSqd(p0, p3) < tolSqd &&
p2.distanceToLineSegmentBetweenSqd(p0, p3) < tolSqd)) {
(*points)[0] = p3;
*points += 1;
return 1;
}
GrPoint q[] = {
{ GrScalarAve(p0.fX, p1.fX), GrScalarAve(p0.fY, p1.fY) },
{ GrScalarAve(p1.fX, p2.fX), GrScalarAve(p1.fY, p2.fY) },
{ GrScalarAve(p2.fX, p3.fX), GrScalarAve(p2.fY, p3.fY) }
};
GrPoint r[] = {
{ GrScalarAve(q[0].fX, q[1].fX), GrScalarAve(q[0].fY, q[1].fY) },
{ GrScalarAve(q[1].fX, q[2].fX), GrScalarAve(q[1].fY, q[2].fY) }
};
GrPoint s = { GrScalarAve(r[0].fX, r[1].fX), GrScalarAve(r[0].fY, r[1].fY) };
pointsLeft >>= 1;
uint32_t a = generateCubicPoints(p0, q[0], r[0], s, tolSqd, points, pointsLeft);
uint32_t b = generateCubicPoints(s, r[1], q[2], p3, tolSqd, points, pointsLeft);
return a + b;
}
int GrPathUtils::worstCasePointCount(const GrPath& path, int* subpaths,
GrScalar tol) {
if (tol < gMinCurveTol) {
tol = gMinCurveTol;
}
GrAssert(tol > 0);
int pointCount = 0;
*subpaths = 1;
bool first = true;
SkPath::Iter iter(path, false);
GrPathCmd cmd;
GrPoint pts[4];
while ((cmd = (GrPathCmd)iter.next(pts)) != kEnd_PathCmd) {
switch (cmd) {
case kLine_PathCmd:
pointCount += 1;
break;
case kQuadratic_PathCmd:
pointCount += quadraticPointCount(pts, tol);
break;
case kCubic_PathCmd:
pointCount += cubicPointCount(pts, tol);
break;
case kMove_PathCmd:
pointCount += 1;
if (!first) {
++(*subpaths);
}
break;
default:
break;
}
first = false;
}
return pointCount;
}
|
