GCC Code Coverage Report

chrono_batch_render/
Coverage:
low: ≥ 0%
medium: ≥ 75.0%
high: ≥ 90.0%
Lines:
173 / 173
100.0%
Branches:
134 / 144
93.1%
Functions:
10 / 10
100.0%
bvh/lbvh.cpp
Line Branch Exec Source
1 // SPDX-License-Identifier: BSD-3-Clause
2 #include "chrono_batch_render/bvh/lbvh.h"
3
4 #include <algorithm>
5 #include <bit>
6 #include <cstddef>
7 #include <cstdint>
8 #include <optional>
9 #include <variant>
10 #include <vector>
11
12 #include "chrono_batch_render/bvh/common.h"
13 #include "chrono_batch_render/bvh/kernels.h"
14 #include "chrono_batch_render/device/device.h"
15 #include "chrono_batch_render/device/kernels/shared.h"
16 #include "chrono_batch_render/device/program.h"
17 #include "chrono_batch_render/device/slang/dispatch.h"
18 #include "chrono_batch_render/util/error.h"
19 #include "chrono_batch_render/util/profiler.h"
20
21 namespace chrono::batch_render::bvh {
22
23 using device::Buffer;
24 using device::BufferRange;
25 using device::BufferUsage;
26 using device::CommandEncoder;
27 using device::Device;
28 using device::Kernel;
29
30 namespace {
31
32 2049 uint32_t KeyBits(uint32_t segments) {
33
1/2
✓ Branch 0 taken 2049 times.
✗ Branch 1 not taken.
 2049 return kLbvhCodeBits + uint32_t(std::bit_width(2 * segments - 1));
34 }
35
36 832 uint32_t KeyWords(uint32_t segments) {
37
2/2
✓ Branch 0 taken 72 times.
✓ Branch 1 taken 760 times.
 832 return KeyBits(segments) <= 32 ? 1 : 2;
38 }
39
40 class Layout {
41 public:
42 1664 explicit Layout(uint64_t alignment) : m_alignment(alignment) {}
43
44 1664 uint64_t Take(uint64_t bytes) {
45 1664 const uint64_t at = m_bytes;
46 1664 m_bytes += RoundUp(bytes, m_alignment);
47 1664 return at;
48 }
49
50 1664 uint64_t Bytes() const {
51 1664 return m_bytes;
52 }
53
54 private:
55 uint64_t m_alignment;
56 uint64_t m_bytes = 0;
57 };
58
59 834 uint32_t CheckedCapacity(uint32_t capacity, uint32_t segments) {
60
2/2
✓ Branch 0 taken 1 time.
✓ Branch 1 taken 833 times.
 834 if (capacity > LbvhBuilder::kMaxPrimitives) {
61 1 throw Error("LbvhBuilder of {} primitives; it builds at most {}", capacity,
62
1/1
✓ Branch 2 taken 1 time.
 1 LbvhBuilder::kMaxPrimitives);
63 }
64
2/2
✓ Branch 0 taken 1 time.
✓ Branch 1 taken 832 times.
 833 if (segments == 0) {
65
2/2
✓ Branch 2 taken 1 time.
✓ Branch 5 taken 1 time.
 2 throw Error("LbvhBuilder of no segments; it builds at least one");
66 }
67 832 return capacity;
68 }
69
70 }
71
72 834 LbvhBuilder::LbvhBuilder(Device& device, uint32_t capacity, uint32_t segments)
73 834 : m_capacity(CheckedCapacity(capacity, segments)), m_segments(segments),
74
3/3
✓ Branch 2 taken 832 times.
✓ Branch 5 taken 832 times.
✓ Branch 9 taken 832 times.
 1664 m_program(device.CreateProgram({.modules = {"chrono_batch_render.bvh.kernels.lbvh"},
75 .library = &kBvhKernels,
76 .entries = {"Prepare", "Morton", "Hierarchy", "FitBoxes",
77 "Seed", "Advance", "Collapse", "Finish"},
78
1/1
✓ Branch 1 taken 832 times.
 832 .label = "lbvh"})),
79
1/1
✓ Branch 1 taken 832 times.
 832 m_prepare(&m_program->Entry("Prepare")), m_morton(&m_program->Entry("Morton")),
80
2/2
✓ Branch 1 taken 832 times.
✓ Branch 4 taken 832 times.
 832 m_hierarchy(&m_program->Entry("Hierarchy")), m_fitBoxes(&m_program->Entry("FitBoxes")),
81
2/2
✓ Branch 1 taken 832 times.
✓ Branch 4 taken 832 times.
 832 m_seed(&m_program->Entry("Seed")), m_advance(&m_program->Entry("Advance")),
82
2/2
✓ Branch 1 taken 832 times.
✓ Branch 4 taken 832 times.
 832 m_collapse(&m_program->Entry("Collapse")), m_finish(&m_program->Entry("Finish")),
83
1/1
✓ Branch 1 taken 832 times.
 832 m_sort(device, capacity, 4 * KeyWords(segments)),
84
1/1
✓ Branch 1 taken 832 times.
 832 m_state(device.CreateBuffer(
85
1/1
✓ Branch 1 taken 832 times.
 832 {.bytes = sizeof(LbvhState), .usage = BufferUsage::Indirect, .label = "lbvh state"})) {
86 832 m_params.keyWords = KeyWords(segments);
87
88 1664 const uint64_t n = std::max(capacity, 1u);
89 832 Layout scratch(device::kBufferAlignment);
90
1/1
✓ Branch 1 taken 832 times.
 832 const uint64_t boxes = scratch.Take(6 * n * 4);
91 832 const uint64_t keys = scratch.Take(m_params.keyWords * n * 4);
92 832 const uint64_t order = scratch.Take(n * 4);
93 832 const uint64_t nodes = scratch.Take(kLbvhNodeWords * n * 4);
94 832 const uint64_t parents = scratch.Take(n * 4);
95 832 const uint64_t arrivals = scratch.Take(n * 4);
96 832 const uint64_t tasks = scratch.Take(2 * kLbvhTaskWords * n * 4);
97 832 const uint64_t bounds = scratch.Take(kLbvhBoundsWords * uint64_t(segments) * 4);
98 832 const uint64_t roots = scratch.Take(uint64_t(segments) * 4);
99 832 const uint64_t counters = scratch.Take(2 * uint64_t(segments) * 4);
100
2/3
✓ Branch 1 taken 832 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 832 times.
 832 m_scratch = device.CreateBuffer({.bytes = scratch.Bytes(), .label = "lbvh scratch"});
101
102 832 Layout layout(4);
103 832 const uint64_t headers = layout.Take(uint64_t(segments) * sizeof(uint64_t));
104 832 const uint64_t geometries = layout.Take(uint64_t(segments) * sizeof(LbvhGeometry));
105 832 const uint64_t offsets = layout.Take((uint64_t(segments) + 1) * sizeof(uint32_t));
106
3/4
✓ Branch 1 taken 832 times.
✓ Branch 4 taken 832 times.
✗ Branch 6 not taken.
✓ Branch 7 taken 832 times.
 832 m_layout = device.CreateBuffer({.bytes = layout.Bytes(), .label = "lbvh layout"});
107
108 832 const uint64_t base = m_scratch->Address();
109 832 m_params.boxes = {base + boxes};
110 832 m_params.keys = {base + keys};
111 832 m_params.order = {base + order};
112 832 m_params.nodes = {base + nodes};
113 832 m_params.parents = {base + parents};
114 832 m_params.arrivals = {base + arrivals};
115 832 m_params.tasks = {base + tasks};
116 832 m_params.queue = uint32_t(n);
117 832 m_params.bounds = {base + bounds};
118 832 m_params.roots = {base + roots};
119 832 m_params.counters = {base + counters};
120 832 m_params.headers = {m_layout->Address() + headers};
121 832 m_params.geometries = {m_layout->Address() + geometries};
122 832 m_params.offsets = {m_layout->Address() + offsets};
123 832 m_params.state = {m_state->Address()};
124 4992 }
125
126 737 LbvhGeometry LbvhEntry(device::Program& program, const char* what, const Geometry& geometry) {
127 737 LbvhGeometry entry{};
128
2/2
✓ Branch 0 taken 594 times.
✓ Branch 1 taken 143 times.
 737 if (const auto* set = std::get_if<device::AccelBoxes>(&geometry)) {
129 594 entry.data =
130 594 device::RequireRange<float>(program, what, set->boxes, uint64_t(set->count) * 6);
131 594 entry.stride = 6;
132 594 return entry;
133 }
134
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 143 times.
 143 const device::AccelTriangles& mesh = std::get<device::AccelTriangles>(geometry);
135
3/4
✓ Branch 0 taken 142 times.
✓ Branch 1 taken 1 time.
✗ Branch 2 not taken.
✓ Branch 3 taken 142 times.
 143 if (mesh.stride < 12 || mesh.stride % 4 != 0) {
136 1 throw Error("{} of a mesh of vertices {} bytes apart; they must be at least 12 and a "
137 "multiple of 4",
138
1/1
✓ Branch 2 taken 1 time.
 1 what, mesh.stride);
139 }
140
2/2
✓ Branch 0 taken 124 times.
✓ Branch 1 taken 18 times.
 142 const uint64_t corners = mesh.indices ? mesh.vertexCount : uint64_t(mesh.count) * 3;
141
2/2
✓ Branch 0 taken 141 times.
✓ Branch 1 taken 1 time.
 142 if (corners > 0) {
142 141 device::RequireRange<std::byte>(program, what, mesh.vertices,
143 141 (corners - 1) * mesh.stride + 12);
144 }
145
2/2
✓ Branch 0 taken 124 times.
✓ Branch 1 taken 18 times.
 142 entry.data = {mesh.vertices.Address()};
146 142 entry.stride = mesh.stride / 4;
147
2/2
✓ Branch 0 taken 124 times.
✓ Branch 1 taken 18 times.
 142 if (mesh.indices) {
148 124 entry.indices =
149 124 device::RequireRange<uint32_t>(program, what, *mesh.indices, uint64_t(mesh.count) * 3);
150 }
151 return entry;
152 }
153
154 8519 BufferRange LbvhBuilder::Words(uint64_t at, uint64_t words) const {
155 8519 return m_scratch->Slice(at - m_scratch->Address(), words * 4);
156 }
157
158 599 void LbvhBuilder::Build(CommandEncoder& encoder, std::span<const Geometry> geometries,
159 std::span<const BufferRange> outputs) const {
160 599 LbvhParams params = m_params;
161
2/2
✓ Branch 0 taken 598 times.
✓ Branch 1 taken 1 time.
 599 params.kind = geometries.empty() ? kBvhTriangles : Kind(geometries[0]);
162 599 std::vector<uint32_t> capacities;
163 599 std::vector<LbvhGeometry> table;
164
2/2
✓ Branch 0 taken 678 times.
✓ Branch 1 taken 597 times.
 1275 for (size_t i = 0; i < geometries.size(); ++i) {
165
3/3
✓ Branch 1 taken 678 times.
✓ Branch 3 taken 1 time.
✓ Branch 4 taken 677 times.
 678 if (Kind(geometries[i]) != params.kind) {
166
2/2
✓ Branch 2 taken 1 time.
✓ Branch 5 taken 1 time.
 2 throw Error("Build of both triangles and boxes; a build takes one or the other");
167 }
168
1/1
✓ Branch 1 taken 676 times.
 677 table.push_back(LbvhEntry(*m_program, "Build", geometries[i]));
169
2/2
✓ Branch 1 taken 676 times.
✓ Branch 4 taken 676 times.
 676 capacities.push_back(PrimitiveCount(geometries[i]));
170 }
171
172
1/1
✓ Branch 1 taken 592 times.
 597 Record(encoder, params, capacities, outputs, table);
173 606 }
174
175 625 void LbvhBuilder::Build(CommandEncoder& encoder, BufferRange instances,
176 std::span<const uint32_t> capacities, std::optional<BufferRange> counts,
177 std::span<const BufferRange> outputs) const {
178 625 const uint64_t total = Total(capacities);
179 625 LbvhParams params = m_params;
180 625 params.kind = kBvhInstances;
181 625 params.instances = device::RequireRange<InstanceRecord>(*m_program, "Build", instances, total);
182
2/2
✓ Branch 0 taken 622 times.
✓ Branch 1 taken 3 times.
 625 if (counts) {
183 622 params.counts =
184 622 device::RequireRange<uint32_t>(*m_program, "Build", *counts, capacities.size());
185 }
186 625 Record(encoder, params, capacities, outputs, {});
187 625 }
188
189 1222 void LbvhBuilder::Record(CommandEncoder& encoder, LbvhParams params,
190 std::span<const uint32_t> capacities, std::span<const BufferRange> outputs,
191 std::span<const LbvhGeometry> geometries) const {
192
4/5
✓ Branch 0 taken 7 times.
✓ Branch 1 taken 1215 times.
✓ Branch 3 taken 7 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 7 times.
 1222 CHRONO_BATCH_RENDER_ZONE("Bvh/Lbvh");
193
4/5
✓ Branch 0 taken 7 times.
✓ Branch 1 taken 1215 times.
✓ Branch 3 taken 7 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 7 times.
 1222 static const profiler::ZoneId zone = profiler::ZoneId::Named("Bvh/Lbvh");
194
2/2
✓ Branch 0 taken 1221 times.
✓ Branch 1 taken 1 time.
 1222 const auto segments = uint32_t(capacities.size());
195
4/4
✓ Branch 0 taken 1221 times.
✓ Branch 1 taken 1 time.
✓ Branch 2 taken 1 time.
✓ Branch 3 taken 1220 times.
 1222 if (segments == 0 || segments > m_segments) {
196
1/1
✓ Branch 2 taken 2 times.
 2 throw Error("Build of {} segments; it was made for 1 to {}", segments, m_segments);
197 }
198
2/2
✓ Branch 0 taken 1 time.
✓ Branch 1 taken 1219 times.
 1220 if (outputs.size() != segments) {
199
1/1
✓ Branch 2 taken 1 time.
 1 throw Error("Build of {} segments into {} outputs", segments, outputs.size());
200 }
201
1/1
✓ Branch 1 taken 1219 times.
 1219 const uint64_t total = Total(capacities);
202
2/2
✓ Branch 0 taken 1 time.
✓ Branch 1 taken 1218 times.
 1219 if (total > m_capacity) {
203
1/1
✓ Branch 2 taken 1 time.
 1 throw Error("Build of {} primitives; it was made for at most {}", total, m_capacity);
204 }
205
206 1218 std::vector<uint64_t> headers;
207
1/1
✓ Branch 1 taken 1218 times.
 1218 headers.reserve(segments);
208
2/2
✓ Branch 0 taken 1419 times.
✓ Branch 1 taken 1217 times.
 2636 for (uint32_t s = 0; s < segments; ++s) {
209
1/1
✓ Branch 1 taken 1418 times.
 2837 headers.push_back(device::RequireRange<std::byte>(*m_program, "Build", outputs[s],
210
1/1
✓ Branch 1 taken 1419 times.
 1419 StorageBytes(capacities[s], params.kind))
211 .address);
212 }
213
214 1217 params.total = uint32_t(total);
215 1217 params.segments = segments;
216
1/1
✓ Branch 1 taken 1217 times.
 1217 const device::ZoneScope scope(encoder, zone);
217
1/1
✓ Branch 1 taken 1217 times.
 1217 const std::vector<uint32_t> offsets = Offsets(capacities);
218 4868 const auto update = [&](uint64_t address, const void* data, uint64_t bytes) {
219 3651 const uint64_t offset = address - m_layout->Address();
220
2/2
✓ Branch 0 taken 3026 times.
✓ Branch 1 taken 3651 times.
 6677 for (uint64_t done = 0; done < bytes; done += CommandEncoder::kMaxUpdateBytes) {
221
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 3026 times.
 3026 const uint64_t part = std::min(bytes - done, CommandEncoder::kMaxUpdateBytes);
222 3026 encoder.Update(m_layout->Slice(offset + done, part),
223 static_cast<const std::byte*>(data) + done);
224 }
225 4868 };
226
227
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1217 times.
 1217 const uint32_t n = std::max(params.total, 1u);
228 1217 const LbvhState start{.parity = 1};
229
1/1
✓ Branch 1 taken 1217 times.
 1217 encoder.Barrier();
230
1/1
✓ Branch 1 taken 1217 times.
 1217 update(params.headers.address, headers.data(), headers.size() * 8);
231
1/1
✓ Branch 1 taken 1217 times.
 1217 update(params.geometries.address, geometries.data(), geometries.size() * sizeof(LbvhGeometry));
232
1/1
✓ Branch 1 taken 1217 times.
 1217 update(params.offsets.address, offsets.data(), offsets.size() * 4);
233
1/1
✓ Branch 1 taken 1217 times.
 1217 encoder.Update(*m_state, &start);
234
2/2
✓ Branch 1 taken 1217 times.
✓ Branch 4 taken 1217 times.
 1217 encoder.Fill(Words(params.bounds.address, uint64_t(kLbvhBoundsWords) * segments), 0xFFFFFFFF);
235
2/2
✓ Branch 1 taken 1217 times.
✓ Branch 4 taken 1217 times.
 1217 encoder.Fill(Words(params.roots.address, segments), kLbvhNone);
236
2/2
✓ Branch 1 taken 1217 times.
✓ Branch 4 taken 1217 times.
 1217 encoder.Fill(Words(params.counters.address, uint64_t(2) * segments), 0);
237
2/2
✓ Branch 1 taken 1217 times.
✓ Branch 4 taken 1217 times.
 1217 encoder.Fill(Words(params.parents.address, n), kLbvhNone);
238
2/2
✓ Branch 1 taken 1217 times.
✓ Branch 4 taken 1217 times.
 1217 encoder.Fill(Words(params.arrivals.address, n), 0);
239
240
1/2
✓ Branch 0 taken 1217 times.
✗ Branch 1 not taken.
 1217 if (params.total > 0) {
241
1/1
✓ Branch 1 taken 1217 times.
 1217 const device::Size3 each{.x = device::GroupCount(params.total, kLbvhThreads)};
242
1/1
✓ Branch 1 taken 1217 times.
 1217 encoder.Barrier();
243
1/1
✓ Branch 1 taken 1217 times.
 1217 encoder.Dispatch(*m_prepare, params, each);
244
1/1
✓ Branch 1 taken 1217 times.
 1217 encoder.Barrier();
245
1/1
✓ Branch 1 taken 1217 times.
 1217 encoder.Dispatch(*m_morton, params, each);
246
2/2
✓ Branch 1 taken 1217 times.
✓ Branch 4 taken 1217 times.
 1217 m_sort.Sort(encoder, Words(params.keys.address, uint64_t(params.keyWords) * n),
247
1/1
✓ Branch 1 taken 1217 times.
 1217 Words(params.order.address, n), params.total, KeyBits(segments));
248
1/1
✓ Branch 1 taken 1217 times.
 1217 encoder.Barrier();
249
1/1
✓ Branch 1 taken 1217 times.
 1217 encoder.Dispatch(*m_hierarchy, params, each);
250
1/1
✓ Branch 1 taken 1217 times.
 1217 encoder.Barrier();
251
1/1
✓ Branch 1 taken 1217 times.
 1217 encoder.Dispatch(*m_fitBoxes, params, each);
252
1/1
✓ Branch 1 taken 1217 times.
 1217 encoder.Barrier();
253
1/1
✓ Branch 1 taken 1217 times.
 1217 encoder.Dispatch(*m_seed, params, {.x = device::GroupCount(segments, kLbvhThreads)});
254
255 1217 const device::Size3 most{
256
2/2
✓ Branch 0 taken 821 times.
✓ Branch 1 taken 396 times.
 2038 .x = device::GroupCount(std::min(params.total, segments + params.total / 4),
257 1217 kLbvhThreads)};
258
2/2
✓ Branch 0 taken 77888 times.
✓ Branch 1 taken 1217 times.
 79105 for (uint32_t level = 0; level < kLbvhLevels; ++level) {
259
1/1
✓ Branch 1 taken 77888 times.
 77888 encoder.Barrier();
260
1/1
✓ Branch 1 taken 77888 times.
 77888 encoder.Dispatch(*m_advance, params, {});
261
1/1
✓ Branch 1 taken 77888 times.
 77888 encoder.Barrier();
262
1/1
✓ Branch 1 taken 77888 times.
 77888 encoder.Dispatch(*m_collapse, params, most,
263
1/1
✓ Branch 1 taken 77888 times.
 155776 m_state->Slice(offsetof(LbvhState, groups), 12));
264 }
265 }
266
267
1/1
✓ Branch 1 taken 1217 times.
 1217 encoder.Barrier();
268
1/1
✓ Branch 1 taken 1217 times.
 1217 encoder.Dispatch(*m_finish, params, {.x = device::GroupCount(segments, kLbvhThreads)});
269 1222 }
270
271 }
272