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/GrPathTessellator.h"
9
10 #include "src/gpu/GrEagerVertexAllocator.h"
11 #include "src/gpu/GrGpu.h"
12 #include "src/gpu/geometry/GrPathUtils.h"
13 #include "src/gpu/geometry/GrWangsFormula.h"
14 #include "src/gpu/tessellate/GrMiddleOutPolygonTriangulator.h"
15 #include "src/gpu/tessellate/GrMidpointContourParser.h"
16 #include "src/gpu/tessellate/GrStencilPathShader.h"
17
GrPathIndirectTessellator(const SkMatrix & viewMatrix,const SkPath & path,DrawInnerFan drawInnerFan)18 GrPathIndirectTessellator::GrPathIndirectTessellator(const SkMatrix& viewMatrix, const SkPath& path,
19 DrawInnerFan drawInnerFan)
20 : fDrawInnerFan(drawInnerFan != DrawInnerFan::kNo) {
21 // Count the number of instances at each resolveLevel.
22 GrVectorXform xform(viewMatrix);
23 for (auto [verb, pts, w] : SkPathPriv::Iterate(path)) {
24 int level;
25 switch (verb) {
26 case SkPathVerb::kConic:
27 level = GrWangsFormula::conic_log2(1.f / kLinearizationPrecision, pts, *w, xform);
28 break;
29 case SkPathVerb::kQuad:
30 level = GrWangsFormula::quadratic_log2(kLinearizationPrecision, pts, xform);
31 break;
32 case SkPathVerb::kCubic:
33 level = GrWangsFormula::cubic_log2(kLinearizationPrecision, pts, xform);
34 break;
35 default:
36 continue;
37 }
38 SkASSERT(level >= 0);
39 // Instances with 2^0=1 segments are empty (zero area). We ignore them completely.
40 if (level > 0) {
41 level = std::min(level, kMaxResolveLevel);
42 ++fResolveLevelCounts[level];
43 ++fOuterCurveInstanceCount;
44 }
45 }
46 }
47
prepare(GrMeshDrawOp::Target * target,const SkMatrix & viewMatrix,const SkPath & path,const BreadcrumbTriangleList * breadcrumbTriangleList)48 void GrPathIndirectTessellator::prepare(GrMeshDrawOp::Target* target, const SkMatrix& viewMatrix,
49 const SkPath& path,
50 const BreadcrumbTriangleList* breadcrumbTriangleList) {
51 SkASSERT(fTotalInstanceCount == 0);
52 SkASSERT(fIndirectDrawCount == 0);
53 SkASSERT(target->caps().drawInstancedSupport());
54
55 int instanceLockCount = fOuterCurveInstanceCount;
56 if (fDrawInnerFan) {
57 // No initial moveTo, plus an implicit close at the end; n-2 triangles fill an n-gon.
58 int maxInnerTriangles = path.countVerbs() - 1;
59 instanceLockCount += maxInnerTriangles;
60 }
61 if (breadcrumbTriangleList) {
62 instanceLockCount += breadcrumbTriangleList->count();
63 }
64 if (instanceLockCount == 0) {
65 return;
66 }
67
68 // Allocate a buffer to store the instance data.
69 GrEagerDynamicVertexAllocator vertexAlloc(target, &fInstanceBuffer, &fBaseInstance);
70 SkPoint* instanceData = static_cast<SkPoint*>(vertexAlloc.lock(sizeof(SkPoint) * 4,
71 instanceLockCount));
72 if (!instanceData) {
73 return;
74 }
75
76 // Write out any triangles at the beginning of the cubic data.
77 int numTrianglesAtBeginningOfData = 0;
78 if (fDrawInnerFan) {
79 numTrianglesAtBeginningOfData = GrMiddleOutPolygonTriangulator::WritePathInnerFan(
80 instanceData + numTrianglesAtBeginningOfData * 4, 4/*stride*/, path);
81 }
82 if (breadcrumbTriangleList) {
83 SkDEBUGCODE(int count = 0;)
84 for (const auto* tri = breadcrumbTriangleList->head(); tri; tri = tri->fNext) {
85 SkDEBUGCODE(++count;)
86 const SkPoint* p = tri->fPts;
87 if ((p[0].fX == p[1].fX && p[1].fX == p[2].fX) ||
88 (p[0].fY == p[1].fY && p[1].fY == p[2].fY)) {
89 // Completely degenerate triangles have undefined winding. And T-junctions shouldn't
90 // happen on axis-aligned edges.
91 continue;
92 }
93 SkPoint* breadcrumbData = instanceData + numTrianglesAtBeginningOfData * 4;
94 memcpy(breadcrumbData, p, sizeof(SkPoint) * 3);
95 // Duplicate the final point since it will also be used by the convex hull shader.
96 breadcrumbData[3] = p[2];
97 ++numTrianglesAtBeginningOfData;
98 }
99 SkASSERT(count == breadcrumbTriangleList->count());
100 }
101
102 fIndirectIndexBuffer = GrMiddleOutCubicShader::FindOrMakeMiddleOutIndexBuffer(
103 target->resourceProvider());
104 if (!fIndirectIndexBuffer) {
105 vertexAlloc.unlock(0);
106 return;
107 }
108
109 // Allocate space for the GrDrawIndexedIndirectCommand structs. Allocate enough for each
110 // possible resolve level (kMaxResolveLevel; resolveLevel=0 never has any instances), plus one
111 // more for the optional inner fan triangles.
112 int indirectLockCnt = kMaxResolveLevel + 1;
113 GrDrawIndexedIndirectWriter indirectWriter = target->makeDrawIndexedIndirectSpace(
114 indirectLockCnt, &fIndirectDrawBuffer, &fIndirectDrawOffset);
115 if (!indirectWriter) {
116 SkASSERT(!fIndirectDrawBuffer);
117 vertexAlloc.unlock(0);
118 return;
119 }
120
121 // Fill out the GrDrawIndexedIndirectCommand structs and determine the starting instance data
122 // location at each resolve level.
123 SkPoint* instanceLocations[kMaxResolveLevel + 1];
124 int runningInstanceCount = 0;
125 if (numTrianglesAtBeginningOfData) {
126 // The caller has already packed "triangleInstanceCount" triangles into 4-point instances
127 // at the beginning of the instance buffer. Add a special-case indirect draw here that will
128 // emit the triangles [P0, P1, P2] from these 4-point instances.
129 SkASSERT(fIndirectDrawCount < indirectLockCnt);
130 GrMiddleOutCubicShader::WriteDrawTrianglesIndirectCmd(&indirectWriter,
131 numTrianglesAtBeginningOfData,
132 fBaseInstance);
133 ++fIndirectDrawCount;
134 runningInstanceCount = numTrianglesAtBeginningOfData;
135 }
136 SkASSERT(fResolveLevelCounts[0] == 0);
137 for (int resolveLevel = 1; resolveLevel <= kMaxResolveLevel; ++resolveLevel) {
138 int instanceCountAtCurrLevel = fResolveLevelCounts[resolveLevel];
139 if (!instanceCountAtCurrLevel) {
140 SkDEBUGCODE(instanceLocations[resolveLevel] = nullptr;)
141 continue;
142 }
143 instanceLocations[resolveLevel] = instanceData + runningInstanceCount * 4;
144 SkASSERT(fIndirectDrawCount < indirectLockCnt);
145 GrMiddleOutCubicShader::WriteDrawCubicsIndirectCmd(&indirectWriter, resolveLevel,
146 instanceCountAtCurrLevel,
147 fBaseInstance + runningInstanceCount);
148 ++fIndirectDrawCount;
149 runningInstanceCount += instanceCountAtCurrLevel;
150 }
151
152 target->putBackIndirectDraws(indirectLockCnt - fIndirectDrawCount);
153
154 #ifdef SK_DEBUG
155 SkASSERT(runningInstanceCount == numTrianglesAtBeginningOfData + fOuterCurveInstanceCount);
156
157 SkPoint* endLocations[kMaxResolveLevel + 1];
158 int lastResolveLevel = 0;
159 for (int resolveLevel = 1; resolveLevel <= kMaxResolveLevel; ++resolveLevel) {
160 if (!instanceLocations[resolveLevel]) {
161 endLocations[resolveLevel] = nullptr;
162 continue;
163 }
164 endLocations[lastResolveLevel] = instanceLocations[resolveLevel];
165 lastResolveLevel = resolveLevel;
166 }
167 int totalInstanceCount = numTrianglesAtBeginningOfData + fOuterCurveInstanceCount;
168 endLocations[lastResolveLevel] = instanceData + totalInstanceCount * 4;
169 #endif
170
171 fTotalInstanceCount = numTrianglesAtBeginningOfData;
172
173 // Write out the cubic instances.
174 if (fOuterCurveInstanceCount) {
175 GrVectorXform xform(viewMatrix);
176 for (auto [verb, pts, w] : SkPathPriv::Iterate(path)) {
177 int level;
178 switch (verb) {
179 default:
180 continue;
181 case SkPathVerb::kConic:
182 level = GrWangsFormula::conic_log2(1.f / kLinearizationPrecision, pts, *w,
183 xform);
184 break;
185 case SkPathVerb::kQuad:
186 level = GrWangsFormula::quadratic_log2(kLinearizationPrecision, pts, xform);
187 break;
188 case SkPathVerb::kCubic:
189 level = GrWangsFormula::cubic_log2(kLinearizationPrecision, pts, xform);
190 break;
191 }
192 if (level == 0) {
193 continue;
194 }
195 level = std::min(level, kMaxResolveLevel);
196 switch (verb) {
197 case SkPathVerb::kQuad:
198 GrPathUtils::convertQuadToCubic(pts, instanceLocations[level]);
199 break;
200 case SkPathVerb::kCubic:
201 memcpy(instanceLocations[level], pts, sizeof(SkPoint) * 4);
202 break;
203 case SkPathVerb::kConic:
204 GrPathShader::WriteConicPatch(pts, *w, instanceLocations[level]);
205 break;
206 default:
207 SkUNREACHABLE;
208 }
209 instanceLocations[level] += 4;
210 ++fTotalInstanceCount;
211 }
212 }
213
214 #ifdef SK_DEBUG
215 for (int i = 1; i <= kMaxResolveLevel; ++i) {
216 SkASSERT(instanceLocations[i] == endLocations[i]);
217 }
218 SkASSERT(fTotalInstanceCount == numTrianglesAtBeginningOfData + fOuterCurveInstanceCount);
219 #endif
220
221 vertexAlloc.unlock(fTotalInstanceCount);
222 }
223
draw(GrOpFlushState * flushState) const224 void GrPathIndirectTessellator::draw(GrOpFlushState* flushState) const {
225 if (fIndirectDrawCount) {
226 flushState->bindBuffers(fIndirectIndexBuffer, fInstanceBuffer, nullptr);
227 flushState->drawIndexedIndirect(fIndirectDrawBuffer.get(), fIndirectDrawOffset,
228 fIndirectDrawCount);
229 }
230 }
231
drawHullInstances(GrOpFlushState * flushState) const232 void GrPathIndirectTessellator::drawHullInstances(GrOpFlushState* flushState) const {
233 if (fTotalInstanceCount) {
234 flushState->bindBuffers(nullptr, fInstanceBuffer, nullptr);
235 flushState->drawInstanced(fTotalInstanceCount, fBaseInstance, 4, 0);
236 }
237 }
238
prepare(GrMeshDrawOp::Target * target,const SkMatrix & matrix,const SkPath & path,const BreadcrumbTriangleList * breadcrumbTriangleList)239 void GrPathOuterCurveTessellator::prepare(GrMeshDrawOp::Target* target, const SkMatrix& matrix,
240 const SkPath& path,
241 const BreadcrumbTriangleList* breadcrumbTriangleList) {
242 SkASSERT(target->caps().shaderCaps()->tessellationSupport());
243 SkASSERT(!breadcrumbTriangleList);
244 SkASSERT(!fPatchBuffer);
245 SkASSERT(fPatchVertexCount == 0);
246
247 int vertexLockCount = path.countVerbs() * 4;
248 GrEagerDynamicVertexAllocator vertexAlloc(target, &fPatchBuffer, &fBasePatchVertex);
249 auto* vertexData = vertexAlloc.lock<SkPoint>(vertexLockCount);
250 if (!vertexData) {
251 return;
252 }
253
254 for (auto [verb, pts, w] : SkPathPriv::Iterate(path)) {
255 switch (verb) {
256 default:
257 continue;
258 case SkPathVerb::kQuad:
259 SkASSERT(fPatchVertexCount + 4 <= vertexLockCount);
260 GrPathUtils::convertQuadToCubic(pts, vertexData + fPatchVertexCount);
261 break;
262 case SkPathVerb::kCubic:
263 SkASSERT(fPatchVertexCount + 4 <= vertexLockCount);
264 memcpy(vertexData + fPatchVertexCount, pts, sizeof(SkPoint) * 4);
265 break;
266 case SkPathVerb::kConic:
267 SkASSERT(fPatchVertexCount + 4 <= vertexLockCount);
268 GrPathShader::WriteConicPatch(pts, *w, vertexData + fPatchVertexCount);
269 break;
270 }
271 fPatchVertexCount += 4;
272 }
273
274 vertexAlloc.unlock(fPatchVertexCount);
275 }
276
prepare(GrMeshDrawOp::Target * target,const SkMatrix & matrix,const SkPath & path,const BreadcrumbTriangleList * breadcrumbTriangleList)277 void GrPathWedgeTessellator::prepare(GrMeshDrawOp::Target* target, const SkMatrix& matrix,
278 const SkPath& path,
279 const BreadcrumbTriangleList* breadcrumbTriangleList) {
280 SkASSERT(target->caps().shaderCaps()->tessellationSupport());
281 SkASSERT(!breadcrumbTriangleList);
282 SkASSERT(!fPatchBuffer);
283 SkASSERT(fPatchVertexCount == 0);
284
285 // No initial moveTo, one wedge per verb, plus an implicit close at the end.
286 // Each wedge has 5 vertices.
287 int maxVertices = (path.countVerbs() + 1) * 5;
288
289 GrEagerDynamicVertexAllocator vertexAlloc(target, &fPatchBuffer, &fBasePatchVertex);
290 auto* vertexData = vertexAlloc.lock<SkPoint>(maxVertices);
291 if (!vertexData) {
292 return;
293 }
294
295 GrMidpointContourParser parser(path);
296 while (parser.parseNextContour()) {
297 SkPoint midpoint = parser.currentMidpoint();
298 SkPoint startPoint = {0, 0};
299 SkPoint lastPoint = startPoint;
300 for (auto [verb, pts, w] : parser.currentContour()) {
301 switch (verb) {
302 case SkPathVerb::kMove:
303 startPoint = lastPoint = pts[0];
304 continue;
305 case SkPathVerb::kClose:
306 continue; // Ignore. We can assume an implicit close at the end.
307 case SkPathVerb::kLine:
308 GrPathUtils::convertLineToCubic(pts[0], pts[1], vertexData + fPatchVertexCount);
309 lastPoint = pts[1];
310 break;
311 case SkPathVerb::kQuad:
312 GrPathUtils::convertQuadToCubic(pts, vertexData + fPatchVertexCount);
313 lastPoint = pts[2];
314 break;
315 case SkPathVerb::kCubic:
316 memcpy(vertexData + fPatchVertexCount, pts, sizeof(SkPoint) * 4);
317 lastPoint = pts[3];
318 break;
319 case SkPathVerb::kConic:
320 GrPathShader::WriteConicPatch(pts, *w, vertexData + fPatchVertexCount);
321 lastPoint = pts[2];
322 break;
323 }
324 vertexData[fPatchVertexCount + 4] = midpoint;
325 fPatchVertexCount += 5;
326 }
327 if (lastPoint != startPoint) {
328 GrPathUtils::convertLineToCubic(lastPoint, startPoint, vertexData + fPatchVertexCount);
329 vertexData[fPatchVertexCount + 4] = midpoint;
330 fPatchVertexCount += 5;
331 }
332 }
333
334 vertexAlloc.unlock(fPatchVertexCount);
335 }
336
draw(GrOpFlushState * flushState) const337 void GrPathHardwareTessellator::draw(GrOpFlushState* flushState) const {
338 if (fPatchVertexCount) {
339 flushState->bindBuffers(nullptr, nullptr, fPatchBuffer);
340 flushState->draw(fPatchVertexCount, fBasePatchVertex);
341 if (flushState->caps().requiresManualFBBarrierAfterTessellatedStencilDraw()) {
342 flushState->gpu()->insertManualFramebufferBarrier(); // http://skbug.com/9739
343 }
344 }
345 }
346