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