1 /*
2 * Copyright 2021 Google LLC.
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/PathWedgeTessellator.h"
9
10 #include "src/gpu/tessellate/AffineMatrix.h"
11 #include "src/gpu/tessellate/PatchWriter.h"
12 #include "src/gpu/tessellate/PathCurveTessellator.h"
13 #include "src/gpu/tessellate/WangsFormula.h"
14
15 #if SK_GPU_V1
16 #include "src/gpu/GrMeshDrawTarget.h"
17 #include "src/gpu/GrOpFlushState.h"
18 #include "src/gpu/GrResourceProvider.h"
19 #endif
20
21 namespace skgpu {
22
23 using CubicPatch = PatchWriter::CubicPatch;
24 using ConicPatch = PatchWriter::ConicPatch;
25
26 namespace {
27
28 // Parses out each contour in a path and tracks the midpoint. Example usage:
29 //
30 // SkTPathContourParser parser;
31 // while (parser.parseNextContour()) {
32 // SkPoint midpoint = parser.currentMidpoint();
33 // for (auto [verb, pts] : parser.currentContour()) {
34 // ...
35 // }
36 // }
37 //
38 class MidpointContourParser {
39 public:
MidpointContourParser(const SkPath & path)40 MidpointContourParser(const SkPath& path)
41 : fPath(path)
42 , fVerbs(SkPathPriv::VerbData(fPath))
43 , fNumRemainingVerbs(fPath.countVerbs())
44 , fPoints(SkPathPriv::PointData(fPath))
45 , fWeights(SkPathPriv::ConicWeightData(fPath)) {}
46 // Advances the internal state to the next contour in the path. Returns false if there are no
47 // more contours.
parseNextContour()48 bool parseNextContour() {
49 bool hasGeometry = false;
50 for (; fVerbsIdx < fNumRemainingVerbs; ++fVerbsIdx) {
51 switch (fVerbs[fVerbsIdx]) {
52 case SkPath::kMove_Verb:
53 if (!hasGeometry) {
54 fMidpoint = {0,0};
55 fMidpointWeight = 0;
56 this->advance(); // Resets fPtsIdx to 0 and advances fPoints.
57 fPtsIdx = 1; // Increment fPtsIdx past the kMove.
58 continue;
59 }
60 if (fPoints[0] != fPoints[fPtsIdx - 1]) {
61 // There's an implicit close at the end. Add the start point to our mean.
62 fMidpoint += fPoints[0];
63 ++fMidpointWeight;
64 }
65 return true;
66 default:
67 continue;
68 case SkPath::kLine_Verb:
69 ++fPtsIdx;
70 break;
71 case SkPath::kConic_Verb:
72 ++fWtsIdx;
73 [[fallthrough]];
74 case SkPath::kQuad_Verb:
75 fPtsIdx += 2;
76 break;
77 case SkPath::kCubic_Verb:
78 fPtsIdx += 3;
79 break;
80 }
81 fMidpoint += fPoints[fPtsIdx - 1];
82 ++fMidpointWeight;
83 hasGeometry = true;
84 }
85 if (hasGeometry && fPoints[0] != fPoints[fPtsIdx - 1]) {
86 // There's an implicit close at the end. Add the start point to our mean.
87 fMidpoint += fPoints[0];
88 ++fMidpointWeight;
89 }
90 return hasGeometry;
91 }
92
93 // Allows for iterating the current contour using a range-for loop.
currentContour()94 SkPathPriv::Iterate currentContour() {
95 return SkPathPriv::Iterate(fVerbs, fVerbs + fVerbsIdx, fPoints, fWeights);
96 }
97
currentMidpoint()98 SkPoint currentMidpoint() { return fMidpoint * (1.f / fMidpointWeight); }
99
100 private:
advance()101 void advance() {
102 fVerbs += fVerbsIdx;
103 fNumRemainingVerbs -= fVerbsIdx;
104 fVerbsIdx = 0;
105 fPoints += fPtsIdx;
106 fPtsIdx = 0;
107 fWeights += fWtsIdx;
108 fWtsIdx = 0;
109 }
110
111 const SkPath& fPath;
112
113 const uint8_t* fVerbs;
114 int fNumRemainingVerbs = 0;
115 int fVerbsIdx = 0;
116
117 const SkPoint* fPoints;
118 int fPtsIdx = 0;
119
120 const float* fWeights;
121 int fWtsIdx = 0;
122
123 SkPoint fMidpoint;
124 int fMidpointWeight;
125 };
126
127 } // namespace
128
patchPreallocCount(int totalCombinedPathVerbCnt) const129 int PathWedgeTessellator::patchPreallocCount(int totalCombinedPathVerbCnt) const {
130 // Over-allocate enough wedges for 1 in 4 to chop.
131 int maxWedges = MaxCombinedFanEdgesInPathDrawList(totalCombinedPathVerbCnt);
132 return (maxWedges * 5 + 3) / 4; // i.e., ceil(maxWedges * 5/4)
133 }
134
writePatches(PatchWriter & patchWriter,int maxTessellationSegments,const SkMatrix & shaderMatrix,const PathDrawList & pathDrawList)135 void PathWedgeTessellator::writePatches(PatchWriter& patchWriter,
136 int maxTessellationSegments,
137 const SkMatrix& shaderMatrix,
138 const PathDrawList& pathDrawList) {
139 float maxSegments_pow2 = pow2(maxTessellationSegments);
140 float maxSegments_pow4 = pow2(maxSegments_pow2);
141
142 // If using fixed count, this is the number of segments we need to emit per instance. Always
143 // emit at least 1 segment.
144 float numFixedSegments_pow4 = 1;
145
146 for (auto [pathMatrix, path, color] : pathDrawList) {
147 AffineMatrix m(pathMatrix);
148 wangs_formula::VectorXform totalXform(SkMatrix::Concat(shaderMatrix, pathMatrix));
149 if (fAttribs & PatchAttribs::kColor) {
150 patchWriter.updateColorAttrib(color);
151 }
152 MidpointContourParser parser(path);
153 while (parser.parseNextContour()) {
154 patchWriter.updateFanPointAttrib(m.mapPoint(parser.currentMidpoint()));
155 SkPoint lastPoint = {0, 0};
156 SkPoint startPoint = {0, 0};
157 for (auto [verb, pts, w] : parser.currentContour()) {
158 switch (verb) {
159 case SkPathVerb::kMove: {
160 startPoint = lastPoint = pts[0];
161 break;
162 }
163
164 case SkPathVerb::kLine: {
165 CubicPatch(patchWriter) << LineToCubic{m.map2Points(pts)};
166 lastPoint = pts[1];
167 break;
168 }
169
170 case SkPathVerb::kQuad: {
171 auto [p0, p1] = m.map2Points(pts);
172 auto p2 = m.map1Point(pts+2);
173 float n4 = wangs_formula::quadratic_pow4(kTessellationPrecision,
174 pts,
175 totalXform);
176 if (n4 <= maxSegments_pow4) {
177 // This quad already fits in "maxTessellationSegments".
178 CubicPatch(patchWriter) << QuadToCubic{p0, p1, p2};
179 } else {
180 // Chop until each quad tessellation requires "maxSegments" or fewer.
181 int numPatches =
182 SkScalarCeilToInt(wangs_formula::root4(n4/maxSegments_pow4));
183 patchWriter.chopAndWriteQuads(p0, p1, p2, numPatches);
184 }
185 numFixedSegments_pow4 = std::max(n4, numFixedSegments_pow4);
186 lastPoint = pts[2];
187 break;
188 }
189
190 case SkPathVerb::kConic: {
191 auto [p0, p1] = m.map2Points(pts);
192 auto p2 = m.map1Point(pts+2);
193 float n2 = wangs_formula::conic_pow2(kTessellationPrecision,
194 pts,
195 *w,
196 totalXform);
197 if (n2 <= maxSegments_pow2) {
198 // This conic already fits in "maxTessellationSegments".
199 ConicPatch(patchWriter) << p0 << p1 << p2 << *w;
200 } else {
201 // Chop until each conic tessellation requires "maxSegments" or fewer.
202 int numPatches = SkScalarCeilToInt(sqrtf(n2/maxSegments_pow2));
203 patchWriter.chopAndWriteConics(p0, p1, p2, *w, numPatches);
204 }
205 numFixedSegments_pow4 = std::max(n2*n2, numFixedSegments_pow4);
206 lastPoint = pts[2];
207 break;
208 }
209
210 case SkPathVerb::kCubic: {
211 auto [p0, p1] = m.map2Points(pts);
212 auto [p2, p3] = m.map2Points(pts+2);
213 float n4 = wangs_formula::cubic_pow4(kTessellationPrecision,
214 pts,
215 totalXform);
216 if (n4 <= maxSegments_pow4) {
217 // This cubic already fits in "maxTessellationSegments".
218 CubicPatch(patchWriter) << p0 << p1 << p2 << p3;
219 } else {
220 // Chop until each cubic tessellation requires "maxSegments" or fewer.
221 int numPatches =
222 SkScalarCeilToInt(wangs_formula::root4(n4/maxSegments_pow4));
223 patchWriter.chopAndWriteCubics(p0, p1, p2, p3, numPatches);
224 }
225 numFixedSegments_pow4 = std::max(n4, numFixedSegments_pow4);
226 lastPoint = pts[3];
227 break;
228 }
229
230 case SkPathVerb::kClose: {
231 break; // Ignore. We can assume an implicit close at the end.
232 }
233 }
234 }
235 if (lastPoint != startPoint) {
236 SkPoint pts[2] = {lastPoint, startPoint};
237 CubicPatch(patchWriter) << LineToCubic{m.map2Points(pts)};
238 }
239 }
240 }
241
242 // log16(n^4) == log2(n).
243 // We already chopped curves to make sure none needed a higher resolveLevel than
244 // kMaxFixedResolveLevel.
245 fFixedResolveLevel = SkTPin(wangs_formula::nextlog16(numFixedSegments_pow4),
246 fFixedResolveLevel,
247 int(kMaxFixedResolveLevel));
248 }
249
WriteFixedVertexBuffer(VertexWriter vertexWriter,size_t bufferSize)250 void PathWedgeTessellator::WriteFixedVertexBuffer(VertexWriter vertexWriter, size_t bufferSize) {
251 SkASSERT(bufferSize >= sizeof(SkPoint));
252
253 // Start out with the fan point. A negative resolve level indicates the fan point.
254 vertexWriter << -1.f/*resolveLevel*/ << -1.f/*idx*/;
255
256 // The rest is the same as for curves.
257 PathCurveTessellator::WriteFixedVertexBuffer(std::move(vertexWriter),
258 bufferSize - sizeof(SkPoint));
259 }
260
WriteFixedIndexBuffer(VertexWriter vertexWriter,size_t bufferSize)261 void PathWedgeTessellator::WriteFixedIndexBuffer(VertexWriter vertexWriter, size_t bufferSize) {
262 SkASSERT(bufferSize >= sizeof(uint16_t) * 3);
263
264 // Start out with the fan triangle.
265 vertexWriter << (uint16_t)0 << (uint16_t)1 << (uint16_t)2;
266
267 // The rest is the same as for curves, with a baseIndex of 1.
268 PathCurveTessellator::WriteFixedIndexBufferBaseIndex(std::move(vertexWriter),
269 bufferSize - sizeof(uint16_t) * 3,
270 1);
271 }
272
273 #if SK_GPU_V1
274
275 GR_DECLARE_STATIC_UNIQUE_KEY(gFixedVertexBufferKey);
276 GR_DECLARE_STATIC_UNIQUE_KEY(gFixedIndexBufferKey);
277
prepareFixedCountBuffers(GrMeshDrawTarget * target)278 void PathWedgeTessellator::prepareFixedCountBuffers(GrMeshDrawTarget* target) {
279 GrResourceProvider* rp = target->resourceProvider();
280
281 GR_DEFINE_STATIC_UNIQUE_KEY(gFixedVertexBufferKey);
282
283 fFixedVertexBuffer = rp->findOrMakeStaticBuffer(GrGpuBufferType::kVertex,
284 FixedVertexBufferSize(kMaxFixedResolveLevel),
285 gFixedVertexBufferKey,
286 WriteFixedVertexBuffer);
287
288 GR_DEFINE_STATIC_UNIQUE_KEY(gFixedIndexBufferKey);
289
290 fFixedIndexBuffer = rp->findOrMakeStaticBuffer(GrGpuBufferType::kIndex,
291 FixedIndexBufferSize(kMaxFixedResolveLevel),
292 gFixedIndexBufferKey,
293 WriteFixedIndexBuffer);
294 }
295
drawTessellated(GrOpFlushState * flushState) const296 void PathWedgeTessellator::drawTessellated(GrOpFlushState* flushState) const {
297 for (const GrVertexChunk& chunk : fVertexChunkArray) {
298 flushState->bindBuffers(nullptr, nullptr, chunk.fBuffer);
299 flushState->draw(chunk.fCount * 5, chunk.fBase * 5);
300 }
301 }
302
drawFixedCount(GrOpFlushState * flushState) const303 void PathWedgeTessellator::drawFixedCount(GrOpFlushState* flushState) const {
304 if (!fFixedVertexBuffer || !fFixedIndexBuffer) {
305 return;
306 }
307 // Emit 3 vertices per curve triangle, plus 3 more for the fan triangle.
308 int fixedIndexCount = (NumCurveTrianglesAtResolveLevel(fFixedResolveLevel) + 1) * 3;
309 for (const GrVertexChunk& chunk : fVertexChunkArray) {
310 flushState->bindBuffers(fFixedIndexBuffer, chunk.fBuffer, fFixedVertexBuffer);
311 flushState->drawIndexedInstanced(fixedIndexCount, 0, chunk.fCount, chunk.fBase, 0);
312 }
313 }
314
315 #endif
316
317 } // namespace skgpu
318