1/*
2 * Copyright 2020 Google Inc.
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#include "src/gpu/tessellate/GrPathParser.h"
9
10#include "include/private/SkTArray.h"
11#include "src/core/SkPathPriv.h"
12#include "src/gpu/GrEagerVertexAllocator.h"
13
14static SkPoint lerp(const SkPoint& a, const SkPoint& b, float T) {
15 SkASSERT(1 != T); // The below does not guarantee lerp(a, b, 1) === b.
16 return (b - a) * T + a;
17}
18
19static SkPoint write_line_as_cubic(SkPoint* data, const SkPoint& p0, const SkPoint& p1) {
20 data[0] = p0;
21 data[1] = lerp(p0, p1, 1/3.f);
22 data[2] = lerp(p0, p1, 2/3.f);
23 data[3] = p1;
24 return data[3];
25}
26
27static SkPoint write_quadratic_as_cubic(SkPoint* data, const SkPoint& p0, const SkPoint& p1,
28 const SkPoint& p2) {
29 data[0] = p0;
30 data[1] = lerp(p0, p1, 2/3.f);
31 data[2] = lerp(p1, p2, 1/3.f);
32 data[3] = p2;
33 return data[3];
34}
35
36static SkPoint write_cubic(SkPoint* data, const SkPoint& p0, const SkPoint& p1, const SkPoint& p2,
37 const SkPoint& p3) {
38 data[0] = p0;
39 data[1] = p1;
40 data[2] = p2;
41 data[3] = p3;
42 return data[3];
43}
44
45// SkTPathContourParser specialization that calculates the contour's midpoint.
46class MidpointContourParser : public SkTPathContourParser<MidpointContourParser> {
47public:
48 MidpointContourParser(const SkPath& path) : SkTPathContourParser(path) {}
49
50 bool parseNextContour() {
51 if (!this->SkTPathContourParser::parseNextContour()) {
52 return false;
53 }
54 if (fMidpointWeight > 1) {
55 fMidpoint *= 1.f / fMidpointWeight;
56 fMidpointWeight = 1;
57 }
58 return true;
59 }
60
61 SkPoint midpoint() const { SkASSERT(1 == fMidpointWeight); return fMidpoint; }
62
63private:
64 friend class SkTPathContourParser<MidpointContourParser>;
65
66 void resetGeometry(const SkPoint& startPoint) {
67 fMidpoint = startPoint;
68 fMidpointWeight = 1;
69 }
70
71 void geometryTo(SkPathVerb, const SkPoint& endpoint) {
72 fMidpoint += endpoint;
73 ++fMidpointWeight;
74 }
75
76 SkPoint fMidpoint;
77 int fMidpointWeight;
78};
79
80constexpr int max_wedge_vertex_count(int numPathVerbs) {
81 // No initial moveTo, one wedge per verb, plus an implicit close at the end.
82 // Each wedge has 5 vertices.
83 return (numPathVerbs + 1) * 5;
84}
85
86int GrPathParser::EmitCenterWedgePatches(const SkPath& path, GrEagerVertexAllocator* vertexAlloc) {
87 int maxVertices = max_wedge_vertex_count(path.countVerbs());
88 auto* vertexData = vertexAlloc->lock<SkPoint>(maxVertices);
89 if (!vertexData) {
90 return 0;
91 }
92
93 int vertexCount = 0;
94 MidpointContourParser parser(path);
95 while (parser.parseNextContour()) {
96 int ptsIdx = 0;
97 SkPoint lastPoint = parser.startPoint();
98 for (int i = 0; i < parser.countVerbs(); ++i) {
99 switch (parser.atVerb(i)) {
100 case SkPathVerb::kClose:
101 case SkPathVerb::kDone:
102 if (parser.startPoint() != lastPoint) {
103 lastPoint = write_line_as_cubic(
104 vertexData + vertexCount, lastPoint, parser.startPoint());
105 break;
106 } // fallthru
107 default:
108 continue;
109
110 case SkPathVerb::kConic:
111 SK_ABORT("Conics are not yet supported.");
112 continue;
113
114 case SkPathVerb::kLine:
115 lastPoint = write_line_as_cubic(vertexData + vertexCount, lastPoint,
116 parser.atPoint(ptsIdx));
117 ++ptsIdx;
118 break;
119 case SkPathVerb::kQuad:
120 lastPoint = write_quadratic_as_cubic(vertexData + vertexCount, lastPoint,
121 parser.atPoint(ptsIdx),
122 parser.atPoint(ptsIdx + 1));
123 ptsIdx += 2;
124 break;
125 case SkPathVerb::kCubic:
126 lastPoint = write_cubic(vertexData + vertexCount, lastPoint,
127 parser.atPoint(ptsIdx), parser.atPoint(ptsIdx + 1),
128 parser.atPoint(ptsIdx + 2));
129 ptsIdx += 3;
130 break;
131 }
132 vertexData[vertexCount + 4] = parser.midpoint();
133 vertexCount += 5;
134 }
135 }
136
137 vertexAlloc->unlock(vertexCount);
138 return vertexCount;
139}
140
141// Triangulates the polygon defined by the points in the range [first..last] inclusive.
142// Called by InnerPolygonContourParser::emitInnerPolygon() (and recursively).
143static int emit_subpolygon(const SkPoint* points, int first, int last, SkPoint* vertexData) {
144 if (last - first < 2) {
145 return 0;
146 }
147
148 // For sub-polygons we subdivide the points in two and connect the endpoints.
149 int mid = (first + last) / 2;
150 vertexData[0] = points[first];
151 vertexData[1] = points[mid];
152 vertexData[2] = points[last];
153
154 // Emit the sub-polygon at each outer-edge of our new triangle.
155 int vertexCount = 3;
156 vertexCount += emit_subpolygon(points, first, mid, vertexData + vertexCount);
157 vertexCount += emit_subpolygon(points, mid, last, vertexData + vertexCount);
158 return vertexCount;
159}
160
161class InnerPolygonContourParser : public SkTPathContourParser<InnerPolygonContourParser> {
162public:
163 InnerPolygonContourParser(const SkPath& path, int vertexReserveCount)
164 : SkTPathContourParser(path)
165 , fPolyPoints(vertexReserveCount) {
166 }
167
168 int emitInnerPolygon(SkPoint* vertexData) {
169 if (fPolyPoints.size() < 3) {
170 return 0;
171 }
172
173 // For the first triangle in the polygon, subdivide our points into thirds.
174 int i1 = fPolyPoints.size() / 3;
175 int i2 = (2 * fPolyPoints.size()) / 3;
176 vertexData[0] = fPolyPoints[0];
177 vertexData[1] = fPolyPoints[i1];
178 vertexData[2] = fPolyPoints[i2];
179
180 // Emit the sub-polygons at all three edges of our first triangle.
181 int vertexCount = 3;
182 vertexCount += emit_subpolygon(fPolyPoints.begin(), 0, i1, vertexData + vertexCount);
183 vertexCount += emit_subpolygon(fPolyPoints.begin(), i1, i2, vertexData + vertexCount);
184 int i3 = fPolyPoints.size();
185 fPolyPoints.push_back(fPolyPoints.front());
186 vertexCount += emit_subpolygon(fPolyPoints.begin(), i2, i3, vertexData + vertexCount);
187 fPolyPoints.pop_back();
188
189 return vertexCount;
190 }
191
192 int numCurves() const { return fNumCurves; }
193
194private:
195 friend class SkTPathContourParser<InnerPolygonContourParser>;
196
197 void resetGeometry(const SkPoint& startPoint) {
198 fPolyPoints.pop_back_n(fPolyPoints.count());
199 fPolyPoints.push_back(startPoint);
200 fNumCurves = 0;
201 }
202
203 void geometryTo(SkPathVerb verb, const SkPoint& endpoint) {
204 fPolyPoints.push_back(endpoint);
205 if (SkPathVerb::kLine != verb) {
206 ++fNumCurves;
207 }
208 }
209
210 SkSTArray<128, SkPoint> fPolyPoints;
211 int fNumCurves;
212};
213
214constexpr int max_inner_poly_vertex_count(int numPathVerbs) {
215 // No initial moveTo, plus an implicit close at the end; n-2 trianles fill an n-gon.
216 // Each triangle has 3 vertices.
217 return (numPathVerbs - 1) * 3;
218}
219
220int GrPathParser::EmitInnerPolygonTriangles(const SkPath& path,
221 GrEagerVertexAllocator* vertexAlloc) {
222 int maxVertices = max_inner_poly_vertex_count(path.countVerbs());
223 InnerPolygonContourParser parser(path, maxVertices);
224 auto* vertexData = vertexAlloc->lock<SkPoint>(maxVertices);
225 if (!vertexData) {
226 return 0;
227 }
228
229 int vertexCount = 0;
230 while (parser.parseNextContour()) {
231 vertexCount += parser.emitInnerPolygon(vertexData + vertexCount);
232 }
233
234 vertexAlloc->unlock(vertexCount);
235 return vertexCount;
236}
237
238int GrPathParser::EmitCubicInstances(const SkPath& path, GrEagerVertexAllocator* vertexAlloc) {
239 auto* instanceData = vertexAlloc->lock<std::array<SkPoint, 4>>(path.countVerbs());
240 if (!instanceData) {
241 return 0;
242 }
243
244 int instanceCount = 0;
245 SkPath::Iter iter(path, false);
246 SkPath::Verb verb;
247 SkPoint pts[4];
248 while ((verb = iter.next(pts)) != SkPath::kDone_Verb) {
249 if (SkPath::kQuad_Verb == verb) {
250 write_quadratic_as_cubic(instanceData[instanceCount++].data(), pts[0], pts[1], pts[2]);
251 continue;
252 }
253 if (SkPath::kCubic_Verb == verb) {
254 instanceData[instanceCount++] = {pts[0], pts[1], pts[2], pts[3]};
255 continue;
256 }
257 }
258
259 vertexAlloc->unlock(instanceCount);
260 return instanceCount;
261}
262