1 /*
2 * Copyright 2022 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 #include "src/gpu/tessellate/FixedCountBufferUtils.h"
8
9 #include "include/private/base/SkAssert.h"
10 #include "include/private/base/SkDebug.h"
11 #include "include/private/base/SkPoint_impl.h"
12 #include "include/private/base/SkTArray.h"
13 #include "src/base/SkMathPriv.h"
14 #include "src/gpu/BufferWriter.h"
15
16 #include <array>
17 #include <utility>
18
19 using namespace skia_private;
20
21 namespace skgpu::tess {
22
23 namespace {
24
write_curve_index_buffer_base_index(VertexWriter vertexWriter,size_t bufferSize,uint16_t baseIndex)25 void write_curve_index_buffer_base_index(VertexWriter vertexWriter,
26 size_t bufferSize,
27 uint16_t baseIndex) {
28 int triangleCount = bufferSize / (sizeof(uint16_t) * 3);
29 SkASSERT(triangleCount >= 1);
30 TArray<std::array<uint16_t, 3>> indexData(triangleCount);
31
32 // Connect the vertices with a middle-out triangulation. Refer to InitFixedCountVertexBuffer()
33 // for the exact vertex ordering.
34 //
35 // Resolve level 1 is just a single triangle at T=[0, 1/2, 1].
36 const auto* neighborInLastResolveLevel = &indexData.push_back({baseIndex,
37 (uint16_t)(baseIndex + 2),
38 (uint16_t)(baseIndex + 1)});
39
40 // Resolve levels 2..maxResolveLevel
41 int maxResolveLevel = SkPrevLog2(triangleCount + 1);
42 uint16_t nextIndex = baseIndex + 3;
43 SkASSERT(NumCurveTrianglesAtResolveLevel(maxResolveLevel) == triangleCount);
44 for (int resolveLevel = 2; resolveLevel <= maxResolveLevel; ++resolveLevel) {
45 SkDEBUGCODE(auto* firstTriangleInCurrentResolveLevel = indexData.end());
46 int numOuterTrianglelsInResolveLevel = 1 << (resolveLevel - 1);
47 SkASSERT(numOuterTrianglelsInResolveLevel % 2 == 0);
48 int numTrianglePairsInResolveLevel = numOuterTrianglelsInResolveLevel >> 1;
49 for (int i = 0; i < numTrianglePairsInResolveLevel; ++i) {
50 // First triangle shares the left edge of "neighborInLastResolveLevel".
51 indexData.push_back({(*neighborInLastResolveLevel)[0],
52 nextIndex++,
53 (*neighborInLastResolveLevel)[1]});
54 // Second triangle shares the right edge of "neighborInLastResolveLevel".
55 indexData.push_back({(*neighborInLastResolveLevel)[1],
56 nextIndex++,
57 (*neighborInLastResolveLevel)[2]});
58 ++neighborInLastResolveLevel;
59 }
60 SkASSERT(neighborInLastResolveLevel == firstTriangleInCurrentResolveLevel);
61 }
62 SkASSERT(indexData.size() == triangleCount);
63 SkASSERT(nextIndex == baseIndex + triangleCount + 2);
64
65 vertexWriter << VertexWriter::Array(indexData.data(), indexData.size());
66 }
67
68 } // namespace
69
WriteVertexBuffer(VertexWriter vertexWriter,size_t bufferSize)70 void FixedCountCurves::WriteVertexBuffer(VertexWriter vertexWriter, size_t bufferSize) {
71 SkASSERT(bufferSize >= sizeof(SkPoint) * 2);
72 int vertexCount = bufferSize / sizeof(SkPoint);
73 SkASSERT(vertexCount > 3);
74 SkDEBUGCODE(auto end = vertexWriter.mark(vertexCount * sizeof(SkPoint));)
75
76 // Lay out the vertices in "middle-out" order:
77 //
78 // T= 0/1, 1/1, ; resolveLevel=0
79 // 1/2, ; resolveLevel=1 (0/2 and 2/2 are already in resolveLevel 0)
80 // 1/4, 3/4, ; resolveLevel=2 (2/4 is already in resolveLevel 1)
81 // 1/8, 3/8, 5/8, 7/8, ; resolveLevel=3 (2/8 and 6/8 are already in resolveLevel 2)
82 // ... ; resolveLevel=...
83 //
84 // Resolve level 0 is just the beginning and ending vertices.
85 vertexWriter << (float)0/*resolveLevel*/ << (float)0/*idx*/;
86 vertexWriter << (float)0/*resolveLevel*/ << (float)1/*idx*/;
87
88 // Resolve levels 1..kMaxResolveLevel.
89 int maxResolveLevel = SkPrevLog2(vertexCount - 1);
90 SkASSERT((1 << maxResolveLevel) + 1 == vertexCount);
91 for (int resolveLevel = 1; resolveLevel <= maxResolveLevel; ++resolveLevel) {
92 int numSegmentsInResolveLevel = 1 << resolveLevel;
93 // Write out the odd vertices in this resolveLevel. The even vertices were already written
94 // out in previous resolveLevels and will be indexed from there.
95 for (int i = 1; i < numSegmentsInResolveLevel; i += 2) {
96 vertexWriter << (float)resolveLevel << (float)i;
97 }
98 }
99
100 SkASSERT(vertexWriter.mark() == end);
101 }
102
WriteIndexBuffer(VertexWriter vertexWriter,size_t bufferSize)103 void FixedCountCurves::WriteIndexBuffer(VertexWriter vertexWriter, size_t bufferSize) {
104 write_curve_index_buffer_base_index(std::move(vertexWriter), bufferSize, /*baseIndex=*/0);
105 }
106
WriteVertexBuffer(VertexWriter vertexWriter,size_t bufferSize)107 void FixedCountWedges::WriteVertexBuffer(VertexWriter vertexWriter, size_t bufferSize) {
108 SkASSERT(bufferSize >= sizeof(SkPoint));
109
110 // Start out with the fan point. A negative resolve level indicates the fan point.
111 vertexWriter << -1.f/*resolveLevel*/ << -1.f/*idx*/;
112
113 // The rest is the same as for curves.
114 FixedCountCurves::WriteVertexBuffer(std::move(vertexWriter), bufferSize - sizeof(SkPoint));
115 }
116
WriteIndexBuffer(VertexWriter vertexWriter,size_t bufferSize)117 void FixedCountWedges::WriteIndexBuffer(VertexWriter vertexWriter, size_t bufferSize) {
118 SkASSERT(bufferSize >= sizeof(uint16_t) * 3);
119
120 // Start out with the fan triangle.
121 vertexWriter << (uint16_t)0 << (uint16_t)1 << (uint16_t)2;
122
123 // The rest is the same as for curves, with a baseIndex of 1.
124 write_curve_index_buffer_base_index(std::move(vertexWriter),
125 bufferSize - sizeof(uint16_t) * 3,
126 /*baseIndex=*/1);
127 }
128
WriteVertexBuffer(VertexWriter vertexWriter,size_t bufferSize)129 void FixedCountStrokes::WriteVertexBuffer(VertexWriter vertexWriter, size_t bufferSize) {
130 int edgeCount = bufferSize / (sizeof(float) * 2);
131 for (int i = 0; i < edgeCount; ++i) {
132 vertexWriter << (float)i << (float)-i;
133 }
134 }
135
136 } // namespace skgpu::tess
137