GCC Code Coverage Report

ernie/
Coverage:
low: ≥ 0%
medium: ≥ 75.0%
high: ≥ 90.0%
Lines:
433 / 461
93.9%
Branches:
250 / 395
63.3%
Functions:
49 / 49
100.0%
render/transform_graph.cpp
Line Branch Exec Source
1 // SPDX-License-Identifier: BSD-3-Clause
2 /// @file transform_graph.cpp
3 /// @brief Keeping the transform graph in step with the scene's changes, and evaluating and
4 /// composing it on the device.
5 #include "ernie/render/transform_graph.h"
6
7 #include "ernie/scene/schema/geom.h"
8 #include "ernie/scene/tokens.h"
9 #include "ernie/shaders/device/buffer_ref.h"
10 #include "ernie/shaders/math/affine.h"
11 #include "ernie/shaders/math/double_float.h"
12 #include "ernie/shaders/scene/transform.h"
13 #include "ernie/util/math.h"
14
15 #include <glm/gtc/matrix_transform.hpp>
16
17 #include <algorithm>
18 #include <stdexcept>
19 #include <string>
20 #include <utility>
21
22 namespace ernie {
23 namespace {
24
25 using shaders::ComposeParameters;
26 using shaders::LocalParameters;
27
28 // The shaders tell op kinds apart by these, so `XformOpKind` keeps its order.
29 static_assert(TransformGraph::OpKind(XformOpKind::Translate) == shaders::kTranslate);
30 static_assert(TransformGraph::OpKind(XformOpKind::Scale) == shaders::kScale);
31 static_assert(TransformGraph::OpKind(XformOpKind::RotateX) == shaders::kRotateX);
32 static_assert(TransformGraph::OpKind(XformOpKind::RotateXYZ) == shaders::kRotateXYZ);
33 static_assert(TransformGraph::OpKind(XformOpKind::Orient) == shaders::kOrient);
34
35 /// @return A transform's top three rows, each value split exactly into a high and a low float.
36 5892 TransformGraph::SplitRows Split(const glm::dmat4& m) {
37 5892 TransformGraph::SplitRows rows{};
38
2/2
✓ Branch 0 taken 17676 times.
✓ Branch 1 taken 5892 times.
 23568 for (int r = 0; r < 3; ++r) {
39
2/2
✓ Branch 0 taken 70704 times.
✓ Branch 1 taken 17676 times.
 88380 for (int c = 0; c < 4; ++c) {
40
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 70704 times.
 70704 const double value = m[c][r];
41 70704 const auto high = static_cast<float>(value);
42 70704 rows.high[r][c] = high;
43 70704 rows.low[r][c] = static_cast<float>(value - static_cast<double>(high));
44 }
45 }
46 5892 return rows;
47 }
48
49 const TransformGraph::SplitRows kIdentity = Split(glm::dmat4(1.0));
50
51 /// @return Whether a bound column's rows of `floats` floats can hold the op's value.
52 6 bool TakesFloats(XformOpKind kind, std::int64_t floats) {
53
3/5
✓ Branch 0 taken 1 time.
✗ Branch 1 not taken.
✓ Branch 2 taken 1 time.
✗ Branch 3 not taken.
✓ Branch 4 taken 4 times.
 6 switch (kind) {
54 1 case XformOpKind::Scale:
55 1 return floats == 1 || floats == 3;
56 ✗ case XformOpKind::RotateX:
57 ✗ case XformOpKind::RotateY:
58 ✗ case XformOpKind::RotateZ:
59 ✗ return floats == 1;
60 1 case XformOpKind::Orient:
61 1 return floats == 4;
62 ✗ case XformOpKind::Transform:
63 ✗ return floats == 16;
64 4 default:
65 4 return floats == 3;
66 }
67 }
68
69 /// @return The floats a row of a float column holds.
70 1612 std::int64_t CountFloats(const DeviceColumn& column) {
71 1612 return static_cast<std::int64_t>(column.RowBytes() / sizeof(float));
72 }
73
74 85 glm::uvec3 Groups(std::size_t threads) {
75 85 return {static_cast<std::uint32_t>(DivideRoundUp<std::size_t>(threads, 64)), 1, 1};
76 }
77
78 } // namespace
79
80 23 TransformGraph::TransformGraph(DeviceContext& context, Arenas& arenas, const Scene& scene,
81 23 const ShaderCompiler& compiler)
82 23 : context_(context), arenas_(arenas), scene_(scene), uploader_(context, context.Main()),
83
3/6
✓ Branch 1 taken 23 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 23 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 23 times.
✗ Branch 8 not taken.
 23 local_(context, compiler.Spirv(WorldModules(), "Local"), "local transforms",
84 sizeof(LocalParameters)),
85
3/6
✓ Branch 1 taken 23 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 23 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 23 times.
✗ Branch 8 not taken.
 23 compose_(context, compiler.Spirv(WorldModules(), "Compose"), "world transforms",
86
1/2
✓ Branch 1 taken 23 times.
✗ Branch 2 not taken.
 23 sizeof(ComposeParameters)) {
87 138 const auto column = [&](std::string_view name, DType type, std::vector<std::int64_t> element) {
88
3/6
✓ Branch 1 taken 23 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 23 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 23 times.
✗ Branch 8 not taken.
 69 return std::make_unique<DeviceColumn>(arenas, name, type, std::move(element), 0);
89 23 };
90
1/2
✓ Branch 1 taken 23 times.
✗ Branch 2 not taken.
 23 parentColumn_ = column("parents", DType::UInt32, {});
91
3/6
✓ Branch 1 taken 23 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 23 times.
✗ Branch 5 not taken.
✓ Branch 10 taken 23 times.
✗ Branch 11 not taken.
 23 localColumn_ = column("locals", DType::Float32, {2, 3, 4});
92 23 programColumn_ =
93
3/6
✓ Branch 1 taken 23 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 23 times.
✗ Branch 5 not taken.
✓ Branch 10 taken 23 times.
✗ Branch 11 not taken.
 23 column("programs", DType::UInt32, {kMaxOps, sizeof(DeviceOp) / sizeof(std::uint32_t)});
94
1/2
✓ Branch 1 taken 23 times.
✗ Branch 2 not taken.
 23 lengthColumn_ = column("program lengths", DType::UInt32, {});
95
3/6
✓ Branch 1 taken 23 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 23 times.
✗ Branch 5 not taken.
✓ Branch 10 taken 23 times.
✗ Branch 11 not taken.
 23 worlds_ = column("worlds", DType::Float32, {2, 3, 4});
96
1/2
✓ Branch 1 taken 23 times.
✗ Branch 2 not taken.
 23 programmed_.device = column("programmed", DType::UInt32, {});
97 23 }
98
99 92 TransformGraph::~TransformGraph() = default;
100
101 6 void TransformGraph::Bind(BucketId bucket, std::string_view attribute, const DeviceColumn& column) {
102 6 const std::optional<XformOpKind> kind = ParseXformOpKind(attribute);
103
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 6 times.
 6 if (!kind) {
104
0/4
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
 ✗ throw std::invalid_argument(std::string(attribute) + " is no transform op");
105 }
106 6 const PrimStore& store = scene_.Store();
107 6 const std::optional<Token> token = store.Tokens().Find(attribute);
108
3/6
✓ Branch 0 taken 6 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 6 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 6 times.
✗ Branch 5 not taken.
 6 if (column.Type() != DType::Float32 || !TakesFloats(*kind, CountFloats(column)) ||
109
3/6
✓ Branch 0 taken 6 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 6 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✓ Branch 5 taken 6 times.
 12 column.Rows() != store.GetBucket(bucket).Rows() || !token) {
110
0/4
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
 ✗ throw std::invalid_argument(column.Name() + " does not hold the bucket's " +
111
0/4
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
 ✗ std::string(attribute) + " rows");
112 }
113
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 6 times.
 6 if (FindBinding(bucket, token) != nullptr) {
114
0/4
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
 ✗ throw std::invalid_argument(std::string(attribute) + " is bound already");
115 }
116 6 bindings_.push_back({bucket, *token, &column, column.Address()});
117 // Its prims compose on the device now.
118 6 RefreshBucket(bucket);
119 6 }
120
121 4 void TransformGraph::SetOrigin(const glm::dvec3& origin) {
122
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 4 times.
 4 if (origin == origin_) {
123 return;
124 }
125 4 origin_ = origin;
126 // Level 0 lists the roots.
127
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 2 times.
 4 if (!levels_.empty()) {
128
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 2 times.
 4 for (const std::uint32_t root : levels_[0].slots) {
129 2 Refresh(root);
130 }
131 }
132 }
133
134 79 std::span<const ShaderModule> TransformGraph::WorldModules() {
135 79 static const std::array modules{shaders::kBufferRef, shaders::kAffine, shaders::kDoubleFloat,
136
7/14
✓ Branch 0 taken 25 times.
✓ Branch 1 taken 54 times.
✓ Branch 3 taken 25 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 25 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 25 times.
✗ Branch 10 not taken.
✓ Branch 12 taken 25 times.
✗ Branch 13 not taken.
✓ Branch 15 taken 25 times.
✗ Branch 16 not taken.
✗ Branch 19 not taken.
✗ Branch 20 not taken.
 79 shaders::kTransform};
137 79 return modules;
138 }
139
140 35 glm::dmat4 TransformGraph::ReadWorld(std::span<const float> worlds, std::uint32_t slot) {
141 35 const std::span<const float> rows = worlds.subspan(std::size_t{slot} * 24, 24);
142 35 glm::dmat4 m(1.0);
143
2/2
✓ Branch 0 taken 105 times.
✓ Branch 1 taken 35 times.
 140 for (int r = 0; r < 3; ++r) {
144
2/2
✓ Branch 0 taken 420 times.
✓ Branch 1 taken 105 times.
 525 for (int c = 0; c < 4; ++c) {
145 420 const auto at = static_cast<std::size_t>(r * 4 + c);
146
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 420 times.
 420 m[c][r] = static_cast<double>(rows[at]) + static_cast<double>(rows[12 + at]);
147 }
148 }
149 35 return m;
150 }
151
152 5290 std::optional<std::uint32_t> TransformGraph::Node(PrimId prim) const {
153
4/4
✓ Branch 0 taken 5220 times.
✓ Branch 1 taken 70 times.
✓ Branch 2 taken 4935 times.
✓ Branch 3 taken 285 times.
 5290 if (prim.slot >= nodes_.size() || !nodes_[prim.slot].live ||
154
1/2
✓ Branch 0 taken 4935 times.
✗ Branch 1 not taken.
 4935 !(nodes_[prim.slot].prim == prim)) {
155 356 return std::nullopt;
156 }
157 4934 return prim.slot;
158 }
159
160 1510 void TransformGraph::EnsureSlots(std::uint32_t slots) {
161
2/2
✓ Branch 0 taken 29 times.
✓ Branch 1 taken 1481 times.
 1510 if (slots <= nodes_.size()) {
162 return;
163 }
164 29 const std::size_t size = std::max<std::size_t>({slots, 2 * nodes_.size(), 64});
165 29 nodes_.resize(size);
166 29 parents_.resize(size, kNone);
167 29 locals_.resize(size, kIdentity);
168
2/2
✓ Branch 0 taken 87 times.
✓ Branch 1 taken 29 times.
 116 for (DeviceColumn* column : {parentColumn_.get(), localColumn_.get(), worlds_.get()}) {
169 87 column->Resize(size, context_.Main());
170 }
171 }
172
173 1771 std::uint32_t TransformGraph::Insert(SlotList& list, std::uint32_t slot) {
174 1771 const auto position = static_cast<std::uint32_t>(list.slots.size());
175 1771 list.slots.push_back(slot);
176 1771 list.dirty.push_back(position);
177 1771 return position;
178 }
179
180 17 std::uint32_t TransformGraph::Unlist(SlotList& list, std::uint32_t NodeState::* position,
181 std::uint32_t slot) {
182 17 const std::uint32_t at = std::exchange(nodes_[slot].*position, kNone);
183 17 const std::uint32_t last = list.slots.back();
184 17 list.slots.pop_back();
185
2/2
✓ Branch 0 taken 15 times.
✓ Branch 1 taken 2 times.
 17 if (at != list.slots.size()) {
186 // The last slot moves into the gap.
187 15 list.slots[at] = last;
188 15 list.dirty.push_back(at);
189 15 nodes_[last].*position = at;
190 }
191 17 return at;
192 }
193
194 4 void TransformGraph::Unprogram(std::uint32_t slot) {
195 4 const std::uint32_t at = Unlist(programmed_, &NodeState::programPosition, slot);
196
1/2
✓ Branch 0 taken 4 times.
✗ Branch 1 not taken.
 4 if (at != programs_.size() - 1) {
197 4 programs_[at] = programs_.back();
198 4 lengths_[at] = lengths_.back();
199 4 dirtyPrograms_.Mark(at);
200 }
201 4 programs_.pop_back();
202 4 lengths_.pop_back();
203 4 }
204
205 6189 const TransformGraph::Binding* TransformGraph::FindBinding(BucketId bucket,
206 std::optional<Token> attribute) const {
207
2/2
✓ Branch 0 taken 6178 times.
✓ Branch 1 taken 11 times.
 6189 if (!attribute) {
208 return nullptr;
209 }
210 6178 const auto found = std::ranges::find_if(bindings_, [&](const Binding& binding) {
211
3/4
✗ Branch 0 not taken.
✓ Branch 1 taken 2593 times.
✓ Branch 2 taken 987 times.
✓ Branch 3 taken 1606 times.
 2593 return binding.bucket == bucket && binding.attribute == *attribute;
212 });
213
2/2
✓ Branch 0 taken 1606 times.
✓ Branch 1 taken 4572 times.
 6178 return found == bindings_.end() ? nullptr : &*found;
214 }
215
216 3367 std::uint32_t TransformGraph::ParentSlot(std::uint32_t slot) const {
217
2/2
✓ Branch 0 taken 3363 times.
✓ Branch 1 taken 4 times.
 3367 if (nodes_[slot].resets) {
218 return kNone;
219 }
220 3363 const PrimStore& store = scene_.Store();
221 3363 const PathTable& paths = store.Paths();
222
2/2
✓ Branch 1 taken 3364 times.
✓ Branch 2 taken 2475 times.
 5839 for (PathId above = paths.Parent(store.PrimPath(nodes_[slot].prim)); above != kNoPath;
223
2/2
✓ Branch 0 taken 1 time.
✓ Branch 1 taken 2475 times.
 2476 above = above == kRootPath ? kNoPath : paths.Parent(above)) {
224
2/2
✓ Branch 1 taken 889 times.
✓ Branch 2 taken 2475 times.
 3364 if (const std::optional<PrimId> parent = store.Find(above)) {
225
2/2
✓ Branch 0 taken 888 times.
✓ Branch 1 taken 1 time.
 889 if (Node(*parent)) {
226 888 return parent->slot;
227 }
228 }
229 }
230 return kNone;
231 }
232
233 1514 void TransformGraph::SetLevel(std::uint32_t slot, std::uint32_t level) {
234
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 1510 times.
 1514 NodeState& node = nodes_[slot];
235
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 1510 times.
 1514 if (node.position != kNone) {
236
1/2
✓ Branch 0 taken 4 times.
✗ Branch 1 not taken.
 4 if (node.level == level) {
237 return;
238 }
239 4 Unlist(levels_[node.level], &NodeState::position, slot);
240 }
241
2/2
✓ Branch 0 taken 40 times.
✓ Branch 1 taken 1514 times.
 1554 while (levels_.size() <= level) {
242 40 levels_.push_back({{},
243 40 std::make_unique<DeviceColumn>(arenas_, "level", DType::UInt32,
244 40 std::vector<std::int64_t>{}, 0)});
245 }
246 1514 node.level = level;
247 1514 node.position = Insert(levels_[level], slot);
248
2/2
✓ Branch 0 taken 1 time.
✓ Branch 1 taken 1514 times.
 1515 for (const std::uint32_t child : node.children) {
249 1 SetLevel(child, level + 1);
250 }
251
2/6
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 40 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
 40 }
252
253 1513 void TransformGraph::Attach(std::uint32_t slot, std::uint32_t parent) {
254 1513 nodes_[slot].parent = parent;
255 1513 parents_[slot] = parent;
256 1513 dirtyParents_.Mark(slot);
257
2/2
✓ Branch 0 taken 353 times.
✓ Branch 1 taken 1160 times.
 1513 if (parent != kNone) {
258 353 std::vector<std::uint32_t>& children = nodes_[parent].children;
259 353 nodes_[slot].siblingPosition = static_cast<std::uint32_t>(children.size());
260 353 children.push_back(slot);
261 }
262 1513 SetLevel(slot, parent == kNone ? 0 : nodes_[parent].level + 1);
263 1513 }
264
265 12 void TransformGraph::Detach(std::uint32_t slot) {
266
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 8 times.
 12 NodeState& node = nodes_[slot];
267
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 8 times.
 12 if (node.parent == kNone) {
268 return;
269 }
270 // The last sibling moves into the gap.
271 4 std::vector<std::uint32_t>& siblings = nodes_[node.parent].children;
272 4 const std::uint32_t at = std::exchange(node.siblingPosition, kNone);
273 4 siblings[at] = siblings.back();
274 4 nodes_[siblings[at]].siblingPosition = at;
275 4 siblings.pop_back();
276 }
277
278 2 void TransformGraph::Reparent(std::uint32_t slot, std::uint32_t parent) {
279 2 Detach(slot);
280 2 Attach(slot, parent);
281
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 2 times.
 2 if (nodes_[slot].rooted != (parent == kNone)) {
282 ✗ Refresh(slot);
283 }
284 2 }
285
286 1510 void TransformGraph::AdoptDescendants(std::uint32_t slot) {
287
1/2
✓ Branch 1 taken 1510 times.
✗ Branch 2 not taken.
 1510 const PrimStore& store = scene_.Store();
288
1/2
✓ Branch 1 taken 1510 times.
✗ Branch 2 not taken.
 1510 const PathTable& paths = store.Paths();
289 1510 std::vector<PathId> stack;
290
1/2
✓ Branch 1 taken 1510 times.
✗ Branch 2 not taken.
 1510 paths.ForEachChild(store.PrimPath(nodes_[slot].prim),
291
1/2
✓ Branch 2 taken 1510 times.
✗ Branch 3 not taken.
 1862 [&](PathId child) { stack.push_back(child); });
292
2/2
✓ Branch 0 taken 352 times.
✓ Branch 1 taken 1510 times.
 1862 while (!stack.empty()) {
293 352 const PathId path = stack.back();
294 352 stack.pop_back();
295
1/2
✓ Branch 1 taken 352 times.
✗ Branch 2 not taken.
 352 const std::optional<PrimId> prim = store.Find(path);
296
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 352 times.
 352 if (!prim) {
297
0/2
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 ✗ paths.ForEachChild(path, [&](PathId child) { stack.push_back(child); });
298
4/6
✓ Branch 0 taken 1 time.
✓ Branch 1 taken 351 times.
✓ Branch 2 taken 1 time.
✗ Branch 3 not taken.
✓ Branch 4 taken 1 time.
✗ Branch 5 not taken.
 353 } else if (Node(*prim) && nodes_[prim->slot].parent != slot &&
299
1/2
✓ Branch 1 taken 1 time.
✗ Branch 2 not taken.
 1 ParentSlot(prim->slot) == slot) {
300 // Below it was an ancestor further up; its subtree follows it to the new prim.
301
1/2
✓ Branch 1 taken 1 time.
✗ Branch 2 not taken.
 1 Reparent(prim->slot, slot);
302 }
303 }
304 1510 }
305
306 1510 void TransformGraph::AddNode(PrimId prim) {
307 1510 EnsureSlots(prim.slot + 1);
308 1510 nodes_[prim.slot] = {.prim = prim, .live = true, .position = kNone};
309 1510 ParseOps(prim.slot);
310 1510 Attach(prim.slot, ParentSlot(prim.slot));
311 1510 AdoptDescendants(prim.slot);
312 1510 Refresh(prim.slot);
313 // The device holds nothing for the slot yet, whatever the host's copies compare equal to.
314
2/2
✓ Branch 0 taken 1253 times.
✓ Branch 1 taken 257 times.
 1510 if (nodes_[prim.slot].programPosition == kNone) {
315 1253 dirtyLocals_.Mark(prim.slot);
316 }
317 1510 }
318
319 9 void TransformGraph::RemoveNode(std::uint32_t slot) {
320 9 NodeState& node = nodes_[slot];
321 9 node.live = false;
322 9 Detach(slot);
323 9 Unlist(levels_[node.level], &NodeState::position, slot);
324
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 5 times.
 9 if (node.programPosition != kNone) {
325 4 Unprogram(slot);
326 }
327 // Children the scene keeps hang from the nearest ancestor left; removed ones go next.
328 9 const std::vector<std::uint32_t> orphans = std::move(node.children);
329 9 node.children.clear();
330 9 node.ops.clear();
331
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 9 times.
 13 for (const std::uint32_t orphan : orphans) {
332
2/2
✓ Branch 0 taken 1 time.
✓ Branch 1 taken 3 times.
 4 nodes_[orphan].parent = kNone;
333 4 nodes_[orphan].siblingPosition = kNone;
334
2/2
✓ Branch 0 taken 1 time.
✓ Branch 1 taken 3 times.
 4 if (nodes_[orphan].live) {
335
2/4
✓ Branch 1 taken 1 time.
✗ Branch 2 not taken.
✓ Branch 4 taken 1 time.
✗ Branch 5 not taken.
 1 Reparent(orphan, ParentSlot(orphan));
336 }
337 }
338 9 }
339
340 3365 void TransformGraph::ParseOps(std::uint32_t slot) {
341 3365 NodeState& node = nodes_[slot];
342 3365 node.ops.clear();
343 3365 node.resets = false;
344
2/2
✓ Branch 3 taken 3358 times.
✓ Branch 4 taken 7 times.
 3365 if (!IsA(scene_.Schema(node.prim), Xformable::Definition())) {
345 return;
346 }
347 3358 node.resets = ResetsXformStack(scene_, node.prim);
348 3358 node.ops = XformOpsInOrder(scene_, node.prim);
349 }
350
351 5512 TransformGraph::Built TransformGraph::BuildProgram(std::uint32_t slot) const {
352 5512 const NodeState& node = nodes_[slot];
353 5512 const PrimStore& store = scene_.Store();
354 5512 const BucketId bucket = store.PrimBucket(node.prim);
355 5512 const std::uint32_t row = store.PrimRow(node.prim);
356 5512 Built built;
357 // A root's local moves it by the origin first, in double, so every world stays near it.
358 5512 glm::dmat4 folded =
359
2/2
✓ Branch 0 taken 3941 times.
✓ Branch 1 taken 1571 times.
 5512 node.parent == kNone ? glm::translate(glm::dmat4(1.0), -origin_) : glm::dmat4(1.0);
360 7443 const auto push = [&](const DeviceOp& op) {
361
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1931 times.
 1931 if (built.length == kMaxOps) {
362
0/4
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
 ✗ throw std::invalid_argument("'" + scene_.PrimPath(node.prim).String() +
363
0/2
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 ✗ "' has more than " + std::to_string(kMaxOps) +
364
0/2
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 ✗ " ops for the device");
365 }
366 1931 built.program[built.length++] = op;
367 1931 };
368 // Runs of the host's ops become one matrix each.
369 12630 const auto fold = [&] {
370
4/4
✓ Branch 1 taken 4532 times.
✓ Branch 2 taken 2586 times.
✓ Branch 3 taken 325 times.
✓ Branch 4 taken 4207 times.
 7118 if (folded != glm::dmat4(1.0) && built.onDevice) {
371 325 push({.kind = shaders::kConstant, .constant = Split(folded)});
372 325 folded = glm::dmat4(1.0);
373 }
374 12630 };
375
2/2
✓ Branch 0 taken 6183 times.
✓ Branch 1 taken 5512 times.
 11695 for (const XformOp& op : node.ops) {
376 6183 const Binding* bound = FindBinding(bucket, op.token);
377
2/2
✓ Branch 0 taken 4577 times.
✓ Branch 1 taken 1606 times.
 6183 if (bound == nullptr) {
378 4577 folded = folded * XformOpMatrix(scene_, node.prim, op);
379 4577 continue;
380 }
381 1606 built.onDevice = true;
382 1606 fold();
383 1606 const DeviceColumn& column = *bound->column;
384 1606 const auto floats = static_cast<std::uint32_t>(CountFloats(column));
385
1/2
✓ Branch 0 taken 1606 times.
✗ Branch 1 not taken.
 3212 push({.kind = OpKind(op.kind),
386
1/2
✓ Branch 0 taken 1606 times.
✗ Branch 1 not taken.
 1606 .flags = (op.invert ? shaders::kInvert : 0u) | floats << shaders::kFloatsShift,
387 1606 .source = {bound->address + row * column.RowBytes()}});
388 }
389 5512 fold();
390 5512 built.local = Split(folded);
391 5512 return built;
392 }
393
394 5512 void TransformGraph::Refresh(std::uint32_t slot) {
395 5512 const Built built = BuildProgram(slot);
396
2/2
✓ Branch 0 taken 4231 times.
✓ Branch 1 taken 1281 times.
 5512 NodeState& node = nodes_[slot];
397 5512 node.rooted = node.parent == kNone;
398
2/2
✓ Branch 0 taken 4231 times.
✓ Branch 1 taken 1281 times.
 5512 if (!built.onDevice) {
399
2/2
✓ Branch 1 taken 1242 times.
✓ Branch 2 taken 2989 times.
 4231 if (locals_[slot] != built.local) {
400 1242 locals_[slot] = built.local;
401 1242 dirtyLocals_.Mark(slot);
402 }
403
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 4231 times.
 4231 if (node.programPosition != kNone) {
404 ✗ Unprogram(slot);
405 // The device's last local stands until the upload replaces it.
406 ✗ dirtyLocals_.Mark(slot);
407 }
408 4231 return;
409 }
410
2/2
✓ Branch 0 taken 257 times.
✓ Branch 1 taken 1024 times.
 1281 if (node.programPosition == kNone) {
411 257 node.programPosition = Insert(programmed_, slot);
412 257 programs_.emplace_back();
413 257 lengths_.push_back(0);
414 257 dirtyPrograms_.Mark(node.programPosition);
415 }
416 1281 const std::uint32_t at = node.programPosition;
417
3/4
✓ Branch 1 taken 1020 times.
✓ Branch 2 taken 261 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 1020 times.
 1281 if (programs_[at] != built.program || lengths_[at] != built.length) {
418 261 programs_[at] = built.program;
419 261 lengths_[at] = built.length;
420 261 dirtyPrograms_.Mark(at);
421 }
422 }
423
424 6 void TransformGraph::RefreshBucket(BucketId bucket) {
425
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 6 times.
 6 for (const PrimId prim : rows_.Bucket(bucket)) {
426
0/2
✗ Branch 0 not taken.
✗ Branch 1 not taken.
 ✗ if (Node(prim)) {
427 ✗ ParseOps(prim.slot);
428 ✗ Refresh(prim.slot);
429 }
430 }
431 6 }
432
433 43 void TransformGraph::Replay(const ChangeSet& changes) {
434 43 ERNIE_ZONE("Follow the hierarchy's changes");
435
1/2
✓ Branch 1 taken 43 times.
✗ Branch 2 not taken.
 43 PrimRows::Changes followed = rows_.Follow(scene_.Store(), changes);
436 // Removals first, as an added prim may take a removed one's slot. Every removed node dies
437 // before any is taken out, so none is reattached only to be removed after.
438 43 std::erase_if(followed.removed, [&](PrimId prim) { return !Node(prim); });
439
2/2
✓ Branch 0 taken 9 times.
✓ Branch 1 taken 43 times.
 52 for (const PrimId prim : followed.removed) {
440 9 nodes_[prim.slot].live = false;
441 }
442
2/2
✓ Branch 0 taken 9 times.
✓ Branch 1 taken 43 times.
 52 for (const PrimId prim : followed.removed) {
443
1/2
✓ Branch 1 taken 9 times.
✗ Branch 2 not taken.
 9 RemoveNode(prim.slot);
444 }
445
2/2
✓ Branch 0 taken 1510 times.
✓ Branch 1 taken 43 times.
 1553 for (const PrimId prim : followed.added) {
446
1/2
✓ Branch 1 taken 1510 times.
✗ Branch 2 not taken.
 1510 AddNode(prim);
447 }
448 // Bound ops read their rows in place: moved rows read from their new places.
449
2/2
✓ Branch 0 taken 7 times.
✓ Branch 1 taken 43 times.
 50 for (const PrimId prim : followed.moved) {
450
1/2
✓ Branch 0 taken 7 times.
✗ Branch 1 not taken.
 7 if (Node(prim)) {
451
1/2
✓ Branch 1 taken 7 times.
✗ Branch 2 not taken.
 7 Refresh(prim.slot);
452 }
453 }
454 43 }
455
456 43 void TransformGraph::RefreshAuthored(const ChangeSet& changes) {
457 43 const PrimStore& store = scene_.Store();
458 43 const std::optional<Token> order = store.Tokens().Find(tokens::kXformOpOrder);
459
2/2
✓ Branch 0 taken 162 times.
✓ Branch 1 taken 43 times.
 205 for (const ChangeSet::Values& values : changes.values) {
460
2/2
✓ Branch 1 taken 73 times.
✓ Branch 2 taken 89 times.
 162 if (!Any(scene_.Classify(values), Dirty::Transform)) {
461 73 continue;
462 }
463
1/2
✓ Branch 0 taken 89 times.
✗ Branch 1 not taken.
 89 const bool reordered = values.attribute == order;
464 89 const Bucket& bucket = store.GetBucket(values.bucket);
465
2/2
✓ Branch 0 taken 91 times.
✓ Branch 1 taken 89 times.
 180 for (const RowRange& range : values.rows) {
466
3/4
✗ Branch 0 not taken.
✓ Branch 1 taken 4084 times.
✓ Branch 2 taken 3993 times.
✓ Branch 3 taken 91 times.
 4084 for (std::uint32_t row = range.begin; row < std::min(range.end, bucket.Rows()); ++row) {
467
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 3993 times.
 3993 const PrimId prim = bucket.prims[row];
468
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 3993 times.
 3993 if (!Node(prim)) {
469 ✗ continue;
470 }
471 // Only a new order can reset the stack.
472
2/2
✓ Branch 0 taken 1855 times.
✓ Branch 1 taken 2138 times.
 3993 if (reordered) {
473 1855 ParseOps(prim.slot);
474 1855 const std::uint32_t parent = ParentSlot(prim.slot);
475
2/2
✓ Branch 0 taken 1 time.
✓ Branch 1 taken 1854 times.
 1855 if (parent != nodes_[prim.slot].parent) {
476 1 Detach(prim.slot);
477 1 Attach(prim.slot, parent);
478 }
479 }
480 3993 Refresh(prim.slot);
481 }
482 }
483 }
484 43 }
485
486 43 void TransformGraph::UploadDirty() {
487 129 const auto uploadMarked = [&](DirtySlots& dirty, const DeviceColumn& column, const auto& host) {
488
6/6
auto ernie::TransformGraph::UploadDirty()::{lambda(ernie::TransformGraph::DirtySlots&, ernie::DeviceColumn const&, auto:1 const&)#1}::operator()<std::vector<ernie::shaders::SplitRows, std::allocator<ernie::shaders::SplitRows> > >(ernie::TransformGraph::DirtySlots&, ernie::DeviceColumn const&, std::vector<ernie::shaders::SplitRows, std::allocator<ernie::shaders::SplitRows> > const&) const:
✓ Branch 0 taken 1258 times.
✓ Branch 1 taken 43 times.
auto ernie::TransformGraph::UploadDirty()::{lambda(ernie::TransformGraph::DirtySlots&, ernie::DeviceColumn const&, auto:1 const&)#1}::operator()<std::vector<std::array<ernie::shaders::Op, 8ul>, std::allocator<std::array<ernie::shaders::Op, 8ul> > > >(ernie::TransformGraph::DirtySlots&, ernie::DeviceColumn const&, std::vector<std::array<ernie::shaders::Op, 8ul>, std::allocator<std::array<ernie::shaders::Op, 8ul> > > const&) const:
✓ Branch 0 taken 261 times.
✓ Branch 1 taken 43 times.
auto ernie::TransformGraph::UploadDirty()::{lambda(ernie::TransformGraph::DirtySlots&, ernie::DeviceColumn const&, auto:1 const&)#1}::operator()<std::vector<unsigned int, std::allocator<unsigned int> > >(ernie::TransformGraph::DirtySlots&, ernie::DeviceColumn const&, std::vector<unsigned int, std::allocator<unsigned int> > const&) const:
✓ Branch 0 taken 1512 times.
✓ Branch 1 taken 43 times.
 3160 for (const std::uint32_t slot : dirty.slots) {
489 3031 dirty.marked[slot] = false;
490 }
491 129 StageRows(uploader_, column, host, dirty.slots);
492 129 dirty.slots.clear();
493 129 };
494 43 uploadMarked(dirtyParents_, *parentColumn_, parents_);
495 43 uploadMarked(dirtyLocals_, *localColumn_, locals_);
496 43 programColumn_->Resize(programs_.size(), context_.Main());
497 43 lengthColumn_->Resize(lengths_.size(), context_.Main());
498 // A program's length changes with it: both upload from the same rows.
499 43 StageRows(uploader_, *lengthColumn_, lengths_, dirtyPrograms_.slots);
500 43 uploadMarked(dirtyPrograms_, *programColumn_, programs_);
501 163 const auto uploadList = [&](SlotList& list) {
502 120 list.device->Resize(list.slots.size(), context_.Main());
503 120 StageRows(uploader_, *list.device, list.slots, list.dirty);
504 120 list.dirty.clear();
505 163 };
506 43 uploadList(programmed_);
507
2/2
✓ Branch 0 taken 77 times.
✓ Branch 1 taken 43 times.
 120 for (SlotList& level : levels_) {
508 77 uploadList(level);
509 }
510 43 }
511
512 8 void TransformGraph::DispatchLocals(VkCommandBuffer commands) const {
513 16 local_.Dispatch(commands, Groups(programmed_.slots.size()),
514 16 LocalParameters{ToBufferRef<shaders::uint>(*programmed_.device),
515 8 ToBufferRef<DeviceOp>(*programColumn_),
516 8 ToBufferRef<shaders::uint>(*lengthColumn_),
517 8 ToBufferRef<shaders::float4>(*localColumn_),
518 8 static_cast<std::uint32_t>(programmed_.slots.size())});
519 8 }
520
521 77 void TransformGraph::DispatchLevel(VkCommandBuffer commands, const SlotList& level) const {
522 154 compose_.Dispatch(commands, Groups(level.slots.size()),
523 154 ComposeParameters{ToBufferRef<shaders::uint>(*level.device),
524 77 ToBufferRef<shaders::uint>(*parentColumn_),
525 77 ToBufferRef<shaders::float4>(*localColumn_),
526 77 ToBufferRef<shaders::float4>(*worlds_),
527 77 static_cast<std::uint32_t>(level.slots.size())});
528 77 }
529
530 14 Ticket TransformGraph::Update(std::span<const Ticket> waits) {
531 14 ERNIE_ZONE("Update transforms");
532
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 Prepare();
533
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 std::vector<Ticket> after(waits.begin(), waits.end());
534
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 after.push_back(uploader_.Flush(waits));
535
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 return context_.Main().Submit(
536
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 28 [&](VkCommandBuffer commands) {
537 14 ERNIE_GPU_ZONE(context_, commands, "Transforms");
538 // After earlier readers of the worlds and writers of the bound columns.
539
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 ComputeBarrier(commands);
540
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 10 times.
 14 if (!programmed_.slots.empty()) {
541
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 ERNIE_GPU_ZONE(context_, commands, "Local transforms");
542
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 DispatchLocals(commands);
543 4 }
544
2/2
✓ Branch 0 taken 38 times.
✓ Branch 1 taken 14 times.
 52 for (const SlotList& level : levels_) {
545
1/2
✓ Branch 0 taken 38 times.
✗ Branch 1 not taken.
 38 if (!level.slots.empty()) {
546
1/2
✓ Branch 1 taken 38 times.
✗ Branch 2 not taken.
 38 ComputeBarrier(commands);
547
1/2
✓ Branch 1 taken 38 times.
✗ Branch 2 not taken.
 38 ERNIE_GPU_ZONE(context_, commands, "World transforms");
548
1/2
✓ Branch 1 taken 38 times.
✗ Branch 2 not taken.
 38 DispatchLevel(commands, level);
549 38 }
550 }
551 14 },
552 14 after);
553 14 }
554
555 /// The columns an update uploads come first in `uploaded`, in this order, then each level's slots.
556 26 struct TransformGraph::GraphColumns {
557 enum Uploaded : std::size_t { kParents, kLocals, kPrograms, kLengths, kProgrammed, kLevels };
558 std::vector<graph::Buffer> uploaded;
559 graph::Buffer worlds;
560 std::vector<graph::Buffer> bound;
561
562 39 graph::Buffer& Level(std::size_t level) {
563 39 return uploaded[kLevels + level];
564 }
565 };
566
567 29 void TransformGraph::AddUpdate(graph::Graph& graph) {
568 29 ERNIE_ZONE("Update transforms");
569
1/2
✓ Branch 1 taken 29 times.
✗ Branch 2 not taken.
 29 Prepare();
570
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 26 times.
 29 if (nodes_.empty()) {
571 3 return;
572 }
573
1/2
✓ Branch 1 taken 26 times.
✗ Branch 2 not taken.
 26 GraphColumns columns = ImportColumns(graph);
574
1/2
✓ Branch 1 taken 26 times.
✗ Branch 2 not taken.
 26 const graph::Graph::ScopeGuard scope = graph.Scope("Transforms");
575
1/2
✓ Branch 1 taken 26 times.
✗ Branch 2 not taken.
 26 graph::AddUploadPass(graph, "Upload transforms", uploader_, columns.uploaded);
576
1/2
✓ Branch 1 taken 26 times.
✗ Branch 2 not taken.
 26 AddLocalPass(graph, columns);
577
1/2
✓ Branch 1 taken 26 times.
✗ Branch 2 not taken.
 26 AddLevelPasses(graph, columns);
578 55 }
579
580 26 TransformGraph::GraphColumns TransformGraph::ImportColumns(graph::Graph& graph) const {
581 // Empty columns hold nothing to read or write: their handles stay invalid.
582 225 const auto import = [&](const DeviceColumn& column) {
583
2/2
✓ Branch 0 taken 66 times.
✓ Branch 1 taken 133 times.
 199 return column.Rows() == 0 ? graph::Buffer{} : graph.Import(column);
584 26 };
585 26 GraphColumns columns;
586 286 for (const DeviceColumn* column :
587 26 {parentColumn_.get(), localColumn_.get(), programColumn_.get(), lengthColumn_.get(),
588
2/2
✓ Branch 0 taken 130 times.
✓ Branch 1 taken 26 times.
 156 programmed_.device.get()}) {
589
1/2
✓ Branch 1 taken 130 times.
✗ Branch 2 not taken.
 260 columns.uploaded.push_back(import(*column));
590 }
591
2/2
✓ Branch 0 taken 39 times.
✓ Branch 1 taken 26 times.
 65 for (const SlotList& level : levels_) {
592
1/2
✓ Branch 1 taken 39 times.
✗ Branch 2 not taken.
 78 columns.uploaded.push_back(import(*level.device));
593 }
594
1/2
✓ Branch 1 taken 26 times.
✗ Branch 2 not taken.
 26 columns.worlds = import(*worlds_);
595
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 26 times.
 30 for (const Binding& binding : bindings_) {
596
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 8 columns.bound.push_back(import(*binding.column));
597 }
598 26 return columns;
599 ✗ }
600
601 26 void TransformGraph::AddLocalPass(graph::Graph& graph, GraphColumns& columns) const {
602
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 22 times.
 26 if (programmed_.slots.empty()) {
603 return;
604 }
605 4 std::vector<graph::Buffer>& uploaded = columns.uploaded;
606 8 graph.Add(
607 "Local transforms", graph::Kind::Compute,
608 12 [&](graph::PassBuilder& pass) {
609 12 for (const std::size_t read :
610
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 4 times.
 16 {GraphColumns::kProgrammed, GraphColumns::kPrograms, GraphColumns::kLengths}) {
611 12 pass.ReadAddress(uploaded[read]);
612 }
613 // Bound columns are read in place, after the passes that write them.
614
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 4 times.
 8 for (const graph::Buffer& column : columns.bound) {
615 4 pass.ReadAddress(column);
616 }
617 4 uploaded[GraphColumns::kLocals] = pass.WriteAddress(uploaded[GraphColumns::kLocals]);
618 4 },
619 8 [this](graph::PassContext& pass) { DispatchLocals(pass.commands); });
620 }
621
622 26 void TransformGraph::AddLevelPasses(graph::Graph& graph, GraphColumns& columns) const {
623
2/2
✓ Branch 0 taken 39 times.
✓ Branch 1 taken 26 times.
 65 for (std::size_t l = 0; l < levels_.size(); ++l) {
624
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 39 times.
 39 if (levels_[l].slots.empty()) {
625 ✗ continue;
626 }
627 // Each level reads the worlds the level above wrote.
628 78 graph.Add(
629 "World transforms", graph::Kind::Compute,
630 117 [&](graph::PassBuilder& pass) {
631 117 for (const graph::Buffer& read :
632 39 {columns.Level(l), columns.uploaded[GraphColumns::kParents],
633
2/2
✓ Branch 0 taken 117 times.
✓ Branch 1 taken 39 times.
 156 columns.uploaded[GraphColumns::kLocals]}) {
634 117 pass.ReadAddress(read);
635 }
636 39 columns.worlds = pass.WriteAddress(columns.worlds);
637 39 },
638 39 [this, &level = levels_[l]](graph::PassContext& pass) {
639 39 DispatchLevel(pass.commands, level);
640 });
641 }
642 26 }
643
644 43 void TransformGraph::Prepare() {
645 43 const PrimStore& store = scene_.Store();
646 // A bound column that moved to a larger range moves its programs' sources.
647 43 std::vector<BucketId> moved;
648
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 43 times.
 55 for (Binding& binding : bindings_) {
649
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 12 times.
 12 if (binding.column->Rows() != store.GetBucket(binding.bucket).Rows()) {
650
0/2
✗ Branch 1 not taken.
✗ Branch 2 not taken.
 ✗ throw std::logic_error("Sync " + binding.column->Name() +
651
0/2
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 ✗ " with its bucket before updating transforms");
652 }
653
2/4
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 12 times.
 12 if (const VkDeviceAddress address = binding.column->Address(); address != binding.address) {
654 ✗ binding.address = address;
655
0/2
✗ Branch 1 not taken.
✗ Branch 2 not taken.
 ✗ moved.push_back(binding.bucket);
656 }
657 }
658
1/2
✓ Branch 1 taken 43 times.
✗ Branch 2 not taken.
 43 const ChangeSet changes = store.ChangesSince(cursor_);
659 43 cursor_ = changes.version;
660
1/2
✓ Branch 1 taken 43 times.
✗ Branch 2 not taken.
 43 Replay(changes);
661
1/2
✓ Branch 1 taken 43 times.
✗ Branch 2 not taken.
 43 RefreshAuthored(changes);
662
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 43 times.
 43 for (const BucketId bucket : moved) {
663
0/2
✗ Branch 1 not taken.
✗ Branch 2 not taken.
 ✗ RefreshBucket(bucket);
664 }
665
1/2
✓ Branch 1 taken 43 times.
✗ Branch 2 not taken.
 43 UploadDirty();
666 43 }
667
668 } // namespace ernie
669