1 /*
2 Copyright 2011 Google Inc.
3
4 Licensed under the Apache License, Version 2.0 (the "License");
5 you may not use this file except in compliance with the License.
6 You may obtain a copy of the License at
7
8 http://www.apache.org/licenses/LICENSE-2.0
9
10 Unless required by applicable law or agreed to in writing, software
11 distributed under the License is distributed on an "AS IS" BASIS,
12 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 See the License for the specific language governing permissions and
14 limitations under the License.
15 */
16
17 #include "GrPathUtils.h"
18 #include "GrPoint.h"
19
20 const GrScalar GrPathUtils::gTolerance = GR_Scalar1;
21
22 static const uint32_t MAX_POINTS_PER_CURVE = 1 << 10;
23
quadraticPointCount(const GrPoint points[],GrScalar tol)24 uint32_t GrPathUtils::quadraticPointCount(const GrPoint points[],
25 GrScalar tol) {
26 GrScalar d = points[1].distanceToLineSegmentBetween(points[0], points[2]);
27 if (d < tol) {
28 return 1;
29 } else {
30 // Each time we subdivide, d should be cut in 4. So we need to
31 // subdivide x = log4(d/tol) times. x subdivisions creates 2^(x)
32 // points.
33 // 2^(log4(x)) = sqrt(x);
34 int temp = SkScalarCeil(SkScalarSqrt(SkScalarDiv(d, tol)));
35 return GrMin(GrNextPow2(temp), MAX_POINTS_PER_CURVE);
36 }
37 }
38
generateQuadraticPoints(const GrPoint & p0,const GrPoint & p1,const GrPoint & p2,GrScalar tolSqd,GrPoint ** points,uint32_t pointsLeft)39 uint32_t GrPathUtils::generateQuadraticPoints(const GrPoint& p0,
40 const GrPoint& p1,
41 const GrPoint& p2,
42 GrScalar tolSqd,
43 GrPoint** points,
44 uint32_t pointsLeft) {
45 if (pointsLeft < 2 ||
46 (p1.distanceToLineSegmentBetweenSqd(p0, p2)) < tolSqd) {
47 (*points)[0] = p2;
48 *points += 1;
49 return 1;
50 }
51
52 GrPoint q[] = {
53 { GrScalarAve(p0.fX, p1.fX), GrScalarAve(p0.fY, p1.fY) },
54 { GrScalarAve(p1.fX, p2.fX), GrScalarAve(p1.fY, p2.fY) },
55 };
56 GrPoint r = { GrScalarAve(q[0].fX, q[1].fX), GrScalarAve(q[0].fY, q[1].fY) };
57
58 pointsLeft >>= 1;
59 uint32_t a = generateQuadraticPoints(p0, q[0], r, tolSqd, points, pointsLeft);
60 uint32_t b = generateQuadraticPoints(r, q[1], p2, tolSqd, points, pointsLeft);
61 return a + b;
62 }
63
cubicPointCount(const GrPoint points[],GrScalar tol)64 uint32_t GrPathUtils::cubicPointCount(const GrPoint points[],
65 GrScalar tol) {
66 GrScalar d = GrMax(points[1].distanceToLineSegmentBetweenSqd(points[0], points[3]),
67 points[2].distanceToLineSegmentBetweenSqd(points[0], points[3]));
68 d = SkScalarSqrt(d);
69 if (d < tol) {
70 return 1;
71 } else {
72 int temp = SkScalarCeil(SkScalarSqrt(SkScalarDiv(d, tol)));
73 return GrMin(GrNextPow2(temp), MAX_POINTS_PER_CURVE);
74 }
75 }
76
generateCubicPoints(const GrPoint & p0,const GrPoint & p1,const GrPoint & p2,const GrPoint & p3,GrScalar tolSqd,GrPoint ** points,uint32_t pointsLeft)77 uint32_t GrPathUtils::generateCubicPoints(const GrPoint& p0,
78 const GrPoint& p1,
79 const GrPoint& p2,
80 const GrPoint& p3,
81 GrScalar tolSqd,
82 GrPoint** points,
83 uint32_t pointsLeft) {
84 if (pointsLeft < 2 ||
85 (p1.distanceToLineSegmentBetweenSqd(p0, p3) < tolSqd &&
86 p2.distanceToLineSegmentBetweenSqd(p0, p3) < tolSqd)) {
87 (*points)[0] = p3;
88 *points += 1;
89 return 1;
90 }
91 GrPoint q[] = {
92 { GrScalarAve(p0.fX, p1.fX), GrScalarAve(p0.fY, p1.fY) },
93 { GrScalarAve(p1.fX, p2.fX), GrScalarAve(p1.fY, p2.fY) },
94 { GrScalarAve(p2.fX, p3.fX), GrScalarAve(p2.fY, p3.fY) }
95 };
96 GrPoint r[] = {
97 { GrScalarAve(q[0].fX, q[1].fX), GrScalarAve(q[0].fY, q[1].fY) },
98 { GrScalarAve(q[1].fX, q[2].fX), GrScalarAve(q[1].fY, q[2].fY) }
99 };
100 GrPoint s = { GrScalarAve(r[0].fX, r[1].fX), GrScalarAve(r[0].fY, r[1].fY) };
101 pointsLeft >>= 1;
102 uint32_t a = generateCubicPoints(p0, q[0], r[0], s, tolSqd, points, pointsLeft);
103 uint32_t b = generateCubicPoints(s, r[1], q[2], p3, tolSqd, points, pointsLeft);
104 return a + b;
105 }
106
worstCasePointCount(const GrPath & path,int * subpaths,GrScalar tol)107 int GrPathUtils::worstCasePointCount(const GrPath& path, int* subpaths,
108 GrScalar tol) {
109 int pointCount = 0;
110 *subpaths = 1;
111
112 bool first = true;
113
114 SkPath::Iter iter(path, true);
115 GrPathCmd cmd;
116
117 GrPoint pts[4];
118 while ((cmd = (GrPathCmd)iter.next(pts)) != kEnd_PathCmd) {
119
120 switch (cmd) {
121 case kLine_PathCmd:
122 pointCount += 1;
123 break;
124 case kQuadratic_PathCmd:
125 pointCount += quadraticPointCount(pts, tol);
126 break;
127 case kCubic_PathCmd:
128 pointCount += cubicPointCount(pts, tol);
129 break;
130 case kMove_PathCmd:
131 pointCount += 1;
132 if (!first) {
133 ++(*subpaths);
134 }
135 break;
136 default:
137 break;
138 }
139 first = false;
140 }
141 return pointCount;
142 }
143