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/PathCurveTessellator.h"
9
10 #include "src/gpu/geometry/GrPathUtils.h"
11 #include "src/gpu/tessellate/AffineMatrix.h"
12 #include "src/gpu/tessellate/MiddleOutPolygonTriangulator.h"
13 #include "src/gpu/tessellate/PatchWriter.h"
14 #include "src/gpu/tessellate/WangsFormula.h"
15
16 #if SK_GPU_V1
17 #include "src/gpu/GrMeshDrawTarget.h"
18 #include "src/gpu/GrOpFlushState.h"
19 #include "src/gpu/GrResourceProvider.h"
20 #endif
21
22 namespace skgpu {
23
24 using CubicPatch = PatchWriter::CubicPatch;
25 using ConicPatch = PatchWriter::ConicPatch;
26 using TrianglePatch = PatchWriter::TrianglePatch;
27
patchPreallocCount(int totalCombinedPathVerbCnt) const28 int PathCurveTessellator::patchPreallocCount(int totalCombinedPathVerbCnt) const {
29 // Over-allocate enough curves for 1 in 4 to chop.
30 int approxNumChops = (totalCombinedPathVerbCnt + 3) / 4;
31 // Every chop introduces 2 new patches: another curve patch and a triangle patch that glues the
32 // two chops together.
33 return totalCombinedPathVerbCnt + approxNumChops * 2;
34 }
35
writePatches(PatchWriter & patchWriter,int maxTessellationSegments,const SkMatrix & shaderMatrix,const PathDrawList & pathDrawList)36 void PathCurveTessellator::writePatches(PatchWriter& patchWriter,
37 int maxTessellationSegments,
38 const SkMatrix& shaderMatrix,
39 const PathDrawList& pathDrawList) {
40 float maxSegments_pow2 = pow2(maxTessellationSegments);
41 float maxSegments_pow4 = pow2(maxSegments_pow2);
42
43 // If using fixed count, this is the number of segments we need to emit per instance. Always
44 // emit at least 2 segments so we can support triangles.
45 float numFixedSegments_pow4 = 2*2*2*2;
46
47 for (auto [pathMatrix, path, color] : pathDrawList) {
48 AffineMatrix m(pathMatrix);
49 wangs_formula::VectorXform totalXform(SkMatrix::Concat(shaderMatrix, pathMatrix));
50 if (fAttribs & PatchAttribs::kColor) {
51 patchWriter.updateColorAttrib(color);
52 }
53 for (auto [verb, pts, w] : SkPathPriv::Iterate(path)) {
54 switch (verb) {
55 case SkPathVerb::kQuad: {
56 auto [p0, p1] = m.map2Points(pts);
57 auto p2 = m.map1Point(pts+2);
58 float n4 = wangs_formula::quadratic_pow4(kTessellationPrecision,
59 pts,
60 totalXform);
61 if (n4 <= 1) {
62 break; // This quad only needs 1 segment, which is empty.
63 }
64 if (n4 <= maxSegments_pow4) {
65 // This quad already fits in "maxTessellationSegments".
66 CubicPatch(patchWriter) << QuadToCubic{p0, p1, p2};
67 } else {
68 // Chop until each quad tessellation requires "maxSegments" or fewer.
69 int numPatches =
70 SkScalarCeilToInt(wangs_formula::root4(n4/maxSegments_pow4));
71 patchWriter.chopAndWriteQuads(p0, p1, p2, numPatches);
72 }
73 numFixedSegments_pow4 = std::max(n4, numFixedSegments_pow4);
74 break;
75 }
76
77 case SkPathVerb::kConic: {
78 auto [p0, p1] = m.map2Points(pts);
79 auto p2 = m.map1Point(pts+2);
80 float n2 = wangs_formula::conic_pow2(kTessellationPrecision,
81 pts,
82 *w,
83 totalXform);
84 if (n2 <= 1) {
85 break; // This conic only needs 1 segment, which is empty.
86 }
87 if (n2 <= maxSegments_pow2) {
88 // This conic already fits in "maxTessellationSegments".
89 ConicPatch(patchWriter) << p0 << p1 << p2 << *w;
90 } else {
91 // Chop until each conic tessellation requires "maxSegments" or fewer.
92 int numPatches = SkScalarCeilToInt(sqrtf(n2/maxSegments_pow2));
93 patchWriter.chopAndWriteConics(p0, p1, p2, *w, numPatches);
94 }
95 numFixedSegments_pow4 = std::max(n2*n2, numFixedSegments_pow4);
96 break;
97 }
98
99 case SkPathVerb::kCubic: {
100 auto [p0, p1] = m.map2Points(pts);
101 auto [p2, p3] = m.map2Points(pts+2);
102 float n4 = wangs_formula::cubic_pow4(kTessellationPrecision,
103 pts,
104 totalXform);
105 if (n4 <= 1) {
106 break; // This cubic only needs 1 segment, which is empty.
107 }
108 if (n4 <= maxSegments_pow4) {
109 // This cubic already fits in "maxTessellationSegments".
110 CubicPatch(patchWriter) << p0 << p1 << p2 << p3;
111 } else {
112 // Chop until each cubic tessellation requires "maxSegments" or fewer.
113 int numPatches =
114 SkScalarCeilToInt(wangs_formula::root4(n4/maxSegments_pow4));
115 patchWriter.chopAndWriteCubics(p0, p1, p2, p3, numPatches);
116 }
117 numFixedSegments_pow4 = std::max(n4, numFixedSegments_pow4);
118 break;
119 }
120
121 default: break;
122 }
123 }
124 }
125
126 // log16(n^4) == log2(n).
127 // We already chopped curves to make sure none needed a higher resolveLevel than
128 // kMaxFixedResolveLevel.
129 fFixedResolveLevel = SkTPin(wangs_formula::nextlog16(numFixedSegments_pow4),
130 fFixedResolveLevel,
131 int(kMaxFixedResolveLevel));
132 }
133
WriteFixedVertexBuffer(VertexWriter vertexWriter,size_t bufferSize)134 void PathCurveTessellator::WriteFixedVertexBuffer(VertexWriter vertexWriter, size_t bufferSize) {
135 SkASSERT(bufferSize >= sizeof(SkPoint) * 2);
136 SkASSERT(bufferSize % sizeof(SkPoint) == 0);
137 int vertexCount = bufferSize / sizeof(SkPoint);
138 SkASSERT(vertexCount > 3);
139 SkDEBUGCODE(VertexWriter end = vertexWriter.makeOffset(vertexCount * sizeof(SkPoint));)
140
141 // Lay out the vertices in "middle-out" order:
142 //
143 // T= 0/1, 1/1, ; resolveLevel=0
144 // 1/2, ; resolveLevel=1 (0/2 and 2/2 are already in resolveLevel 0)
145 // 1/4, 3/4, ; resolveLevel=2 (2/4 is already in resolveLevel 1)
146 // 1/8, 3/8, 5/8, 7/8, ; resolveLevel=3 (2/8 and 6/8 are already in resolveLevel 2)
147 // ... ; resolveLevel=...
148 //
149 // Resolve level 0 is just the beginning and ending vertices.
150 vertexWriter << (float)0/*resolveLevel*/ << (float)0/*idx*/;
151 vertexWriter << (float)0/*resolveLevel*/ << (float)1/*idx*/;
152
153 // Resolve levels 1..kMaxResolveLevel.
154 int maxResolveLevel = SkPrevLog2(vertexCount - 1);
155 SkASSERT((1 << maxResolveLevel) + 1 == vertexCount);
156 for (int resolveLevel = 1; resolveLevel <= maxResolveLevel; ++resolveLevel) {
157 int numSegmentsInResolveLevel = 1 << resolveLevel;
158 // Write out the odd vertices in this resolveLevel. The even vertices were already written
159 // out in previous resolveLevels and will be indexed from there.
160 for (int i = 1; i < numSegmentsInResolveLevel; i += 2) {
161 vertexWriter << (float)resolveLevel << (float)i;
162 }
163 }
164
165 SkASSERT(vertexWriter == end);
166 }
167
WriteFixedIndexBufferBaseIndex(VertexWriter vertexWriter,size_t bufferSize,uint16_t baseIndex)168 void PathCurveTessellator::WriteFixedIndexBufferBaseIndex(VertexWriter vertexWriter,
169 size_t bufferSize,
170 uint16_t baseIndex) {
171 SkASSERT(bufferSize % (sizeof(uint16_t) * 3) == 0);
172 int triangleCount = bufferSize / (sizeof(uint16_t) * 3);
173 SkASSERT(triangleCount >= 1);
174 SkTArray<std::array<uint16_t, 3>> indexData(triangleCount);
175
176 // Connect the vertices with a middle-out triangulation. Refer to InitFixedCountVertexBuffer()
177 // for the exact vertex ordering.
178 //
179 // Resolve level 1 is just a single triangle at T=[0, 1/2, 1].
180 const auto* neighborInLastResolveLevel = &indexData.push_back({baseIndex,
181 (uint16_t)(baseIndex + 2),
182 (uint16_t)(baseIndex + 1)});
183
184 // Resolve levels 2..maxResolveLevel
185 int maxResolveLevel = SkPrevLog2(triangleCount + 1);
186 uint16_t nextIndex = baseIndex + 3;
187 SkASSERT(NumCurveTrianglesAtResolveLevel(maxResolveLevel) == triangleCount);
188 for (int resolveLevel = 2; resolveLevel <= maxResolveLevel; ++resolveLevel) {
189 SkDEBUGCODE(auto* firstTriangleInCurrentResolveLevel = indexData.end());
190 int numOuterTrianglelsInResolveLevel = 1 << (resolveLevel - 1);
191 SkASSERT(numOuterTrianglelsInResolveLevel % 2 == 0);
192 int numTrianglePairsInResolveLevel = numOuterTrianglelsInResolveLevel >> 1;
193 for (int i = 0; i < numTrianglePairsInResolveLevel; ++i) {
194 // First triangle shares the left edge of "neighborInLastResolveLevel".
195 indexData.push_back({(*neighborInLastResolveLevel)[0],
196 nextIndex++,
197 (*neighborInLastResolveLevel)[1]});
198 // Second triangle shares the right edge of "neighborInLastResolveLevel".
199 indexData.push_back({(*neighborInLastResolveLevel)[1],
200 nextIndex++,
201 (*neighborInLastResolveLevel)[2]});
202 ++neighborInLastResolveLevel;
203 }
204 SkASSERT(neighborInLastResolveLevel == firstTriangleInCurrentResolveLevel);
205 }
206 SkASSERT(indexData.count() == triangleCount);
207 SkASSERT(nextIndex == baseIndex + triangleCount + 2);
208
209 vertexWriter.writeArray(indexData.data(), indexData.count());
210 }
211
212 #if SK_GPU_V1
213
214 GR_DECLARE_STATIC_UNIQUE_KEY(gFixedVertexBufferKey);
215 GR_DECLARE_STATIC_UNIQUE_KEY(gFixedIndexBufferKey);
216
prepareFixedCountBuffers(GrMeshDrawTarget * target)217 void PathCurveTessellator::prepareFixedCountBuffers(GrMeshDrawTarget* target) {
218 GrResourceProvider* rp = target->resourceProvider();
219
220 GR_DEFINE_STATIC_UNIQUE_KEY(gFixedVertexBufferKey);
221
222 fFixedVertexBuffer = rp->findOrMakeStaticBuffer(GrGpuBufferType::kVertex,
223 FixedVertexBufferSize(kMaxFixedResolveLevel),
224 gFixedVertexBufferKey,
225 WriteFixedVertexBuffer);
226
227 GR_DEFINE_STATIC_UNIQUE_KEY(gFixedIndexBufferKey);
228
229 fFixedIndexBuffer = rp->findOrMakeStaticBuffer(GrGpuBufferType::kIndex,
230 FixedIndexBufferSize(kMaxFixedResolveLevel),
231 gFixedIndexBufferKey,
232 WriteFixedIndexBuffer);
233 }
234
drawTessellated(GrOpFlushState * flushState) const235 void PathCurveTessellator::drawTessellated(GrOpFlushState* flushState) const {
236 for (const GrVertexChunk& chunk : fVertexChunkArray) {
237 flushState->bindBuffers(nullptr, nullptr, chunk.fBuffer);
238 flushState->draw(chunk.fCount * 4, chunk.fBase * 4);
239 }
240 }
241
drawFixedCount(GrOpFlushState * flushState) const242 void PathCurveTessellator::drawFixedCount(GrOpFlushState* flushState) const {
243 if (!fFixedVertexBuffer || !fFixedIndexBuffer) {
244 return;
245 }
246 int fixedIndexCount = NumCurveTrianglesAtResolveLevel(fFixedResolveLevel) * 3;
247 for (const GrVertexChunk& chunk : fVertexChunkArray) {
248 flushState->bindBuffers(fFixedIndexBuffer, chunk.fBuffer, fFixedVertexBuffer);
249 flushState->drawIndexedInstanced(fixedIndexCount, 0, chunk.fCount, chunk.fBase, 0);
250 }
251 }
252
drawHullInstances(GrOpFlushState * flushState,sk_sp<const GrGpuBuffer> vertexBufferIfNeeded) const253 void PathCurveTessellator::drawHullInstances(GrOpFlushState* flushState,
254 sk_sp<const GrGpuBuffer> vertexBufferIfNeeded) const {
255 for (const GrVertexChunk& chunk : fVertexChunkArray) {
256 flushState->bindBuffers(nullptr, chunk.fBuffer, vertexBufferIfNeeded);
257 flushState->drawInstanced(chunk.fCount, chunk.fBase, 4, 0);
258 }
259 }
260
261 #endif
262
263 } // namespace skgpu
264