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
22namespace skgpu {
23
24using CubicPatch = PatchWriter::CubicPatch;
25using ConicPatch = PatchWriter::ConicPatch;
26using TrianglePatch = PatchWriter::TrianglePatch;
27
28int 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
36void 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
134void 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
168void 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
214GR_DECLARE_STATIC_UNIQUE_KEY(gFixedVertexBufferKey);
215GR_DECLARE_STATIC_UNIQUE_KEY(gFixedIndexBufferKey);
216
217void 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
235void 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
242void 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
253void 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