GCC Code Coverage Report

chrono_batch_render/
Coverage:
low: ≥ 0%
medium: ≥ 75.0%
high: ≥ 90.0%
Lines:
175 / 179
97.8%
Branches:
140 / 151
92.7%
Functions:
8 / 8
100.0%
bvh/inspect.cpp
Line Branch Exec Source
1 // SPDX-License-Identifier: BSD-3-Clause
2 #include "chrono_batch_render/bvh/inspect.h"
3
4 #include <algorithm>
5 #include <bit>
6 #include <cmath>
7 #include <cstdint>
8 #include <cstring>
9 #include <string>
10 #include <vector>
11
12 #include <fmt/format.h>
13
14 namespace chrono::batch_render::bvh {
15
16 namespace {
17
18 constexpr size_t kMaxErrors = 32;
19
20 14933 BvhBox Intersect(const BvhBox& a, const BvhBox& b) {
21 14933 BvhBox box;
22
2/2
✓ Branch 0 taken 44799 times.
✓ Branch 1 taken 14933 times.
 59732 for (int i = 0; i < 3; ++i) {
23
2/2
✓ Branch 0 taken 33562 times.
✓ Branch 1 taken 11237 times.
 44799 box.lower[i] = std::max(a.lower[i], b.lower[i]);
24
2/2
✓ Branch 0 taken 32816 times.
✓ Branch 1 taken 11983 times.
 77615 box.upper[i] = std::min(a.upper[i], b.upper[i]);
25 }
26 14933 return box;
27 }
28
29 class Walker {
30 public:
31 65 Walker(std::span<const std::byte> bytes, std::span<const BvhBox> boxes, Inspection& found)
32 65 : m_bytes(bytes), m_boxes(boxes), m_found(found) {}
33
34 65 void Run() {
35
2/2
✓ Branch 0 taken 1 time.
✓ Branch 1 taken 64 times.
 65 if (m_bytes.size() < sizeof(BvhHeader)) {
36
1/1
✓ Branch 1 taken 1 time.
 1 Fail(fmt::format("it has {} bytes, fewer than its header's {}", m_bytes.size(),
37 1 sizeof(BvhHeader)));
38 7 return;
39 }
40
2/2
✓ Branch 0 taken 1 time.
✓ Branch 1 taken 63 times.
 64 std::memcpy(&m_header, m_bytes.data(), sizeof(m_header));
41
2/2
✓ Branch 0 taken 1 time.
✓ Branch 1 taken 63 times.
 64 if (m_header.version != kBvhVersion) {
42
1/1
✓ Branch 1 taken 1 time.
 1 Fail(fmt::format("its format is version {}; Chrono Batch Render reads version {}",
43 1 m_header.version, kBvhVersion));
44 1 return;
45 }
46
2/2
✓ Branch 0 taken 1 time.
✓ Branch 1 taken 62 times.
 63 if (m_header.kind != kBvhTriangles && m_header.kind != kBvhInstances &&
47 m_header.kind != kBvhBoxes) {
48
1/1
✓ Branch 1 taken 1 time.
 1 Fail(fmt::format("its leaf records are of kind {}: not triangles, instances or boxes",
49 1 m_header.kind));
50 1 return;
51 }
52
2/2
✓ Branch 0 taken 44 times.
✓ Branch 1 taken 18 times.
 62 m_words = BvhRecordWords(m_header.kind);
53
3/4
✓ Branch 1 taken 61 times.
✓ Branch 2 taken 1 time.
✗ Branch 3 not taken.
✓ Branch 4 taken 61 times.
 123 if (!Fits("nodes", m_header.nodes, m_header.nodeCount, sizeof(BvhNode)) ||
54 61 !Fits("leaf records", m_header.leaves, m_header.leafCount, uint64_t(m_words) * 16)) {
55 1 return;
56 }
57 61 const uint64_t nodesEnd = m_header.nodes + uint64_t(m_header.nodeCount) * sizeof(BvhNode);
58 61 const uint64_t leavesEnd = m_header.leaves + uint64_t(m_header.leafCount) * m_words * 16;
59
4/6
✓ Branch 0 taken 61 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 61 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 60 times.
✓ Branch 5 taken 1 time.
 61 if (m_header.nodes < sizeof(BvhHeader) || m_header.leaves < sizeof(BvhHeader) ||
60
2/2
✓ Branch 0 taken 1 time.
✓ Branch 1 taken 59 times.
 60 (m_header.nodes < leavesEnd && m_header.leaves < nodesEnd)) {
61
1/1
✓ Branch 1 taken 1 time.
 1 Fail(fmt::format("its nodes, bytes {} to {}, and leaf records, bytes {} to {}, overlap "
62 "each other or its header",
63 1 m_header.nodes, nodesEnd, m_header.leaves, leavesEnd));
64 1 return;
65 }
66
6/6
✓ Branch 0 taken 18 times.
✓ Branch 1 taken 42 times.
✓ Branch 2 taken 15 times.
✓ Branch 3 taken 3 times.
✓ Branch 4 taken 14 times.
✓ Branch 5 taken 1 time.
 60 if (m_header.kind == kBvhInstances && !m_boxes.empty() &&
67
2/2
✓ Branch 0 taken 14 times.
✓ Branch 1 taken 1 time.
 15 m_boxes.size() != m_header.primitives) {
68
1/1
✓ Branch 1 taken 1 time.
 1 Fail(fmt::format("it has {} instances, but {} boxes were given", m_header.primitives,
69 1 m_boxes.size()));
70 1 return;
71 }
72
73 59 m_reached.assign(m_header.primitives, 0);
74 59 m_visited.assign(m_header.nodeCount, false);
75
2/2
✓ Branch 0 taken 54 times.
✓ Branch 1 taken 5 times.
 59 if (m_header.primitives > 0) {
76
2/2
✓ Branch 0 taken 1 time.
✓ Branch 1 taken 53 times.
 54 if (m_header.nodeCount == 0) {
77
1/1
✓ Branch 2 taken 1 time.
 1 Fail(fmt::format("it has {} primitives but no nodes", m_header.primitives));
78 1 return;
79 }
80 53 BvhBox bounds;
81 53 std::memcpy(bounds.lower, m_header.lower, sizeof(bounds.lower));
82 53 std::memcpy(bounds.upper, m_header.upper, sizeof(bounds.upper));
83 53 m_rootArea = BvhArea(bounds);
84 53 double extent = 0;
85
2/2
✓ Branch 0 taken 159 times.
✓ Branch 1 taken 53 times.
 212 for (int i = 0; i < 3; ++i) {
86
2/2
✓ Branch 0 taken 77 times.
✓ Branch 1 taken 82 times.
 159 extent = std::max(extent, double(bounds.upper[i]) - bounds.lower[i]);
87 159 extent = std::max(
88 159 {extent, std::abs(double(bounds.lower[i])), std::abs(double(bounds.upper[i]))});
89 }
90 53 m_slack = float(extent * 1e-5);
91
92 53 m_found.sahCost = 1;
93 53 m_found.nodeCost = 1;
94 53 m_pending.push_back({0, bounds, 1});
95
2/2
✓ Branch 0 taken 2696 times.
✓ Branch 1 taken 53 times.
 2749 while (!m_pending.empty()) {
96 2696 const Pending next = m_pending.back();
97 2696 m_pending.pop_back();
98 2696 Visit(next.index, next.within, next.depth);
99 }
100 }
101
102
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 34 times.
 58 const uint32_t least = m_header.kind == kBvhTriangles ? 1 : 0;
103
2/2
✓ Branch 0 taken 27670 times.
✓ Branch 1 taken 58 times.
 27728 for (uint32_t i = 0; i < m_header.primitives; ++i) {
104
4/4
✓ Branch 0 taken 27527 times.
✓ Branch 1 taken 143 times.
✓ Branch 2 taken 2 times.
✓ Branch 3 taken 27525 times.
 27670 if (m_reached[i] < least || m_reached[i] > 1) {
105
1/1
✓ Branch 2 taken 145 times.
 290 Fail(fmt::format("primitive {} is in {} leaf records, not one", i, m_reached[i]));
106 }
107 }
108
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 52 times.
 58 if (m_found.records != m_header.leafCount) {
109
1/1
✓ Branch 1 taken 6 times.
 12 Fail(fmt::format("it has {} leaf records, but its leaves hold {}", m_header.leafCount,
110 6 m_found.records));
111 }
112
2/2
✓ Branch 0 taken 2700 times.
✓ Branch 1 taken 58 times.
 2758 for (uint32_t i = 0; i < m_header.nodeCount; ++i) {
113
2/2
✓ Branch 1 taken 6 times.
✓ Branch 2 taken 2694 times.
 2700 if (!m_visited[i]) {
114
2/2
✓ Branch 1 taken 6 times.
✓ Branch 4 taken 6 times.
 12 Fail(fmt::format("node {} is never reached from the root", i));
115 }
116 }
117
118
2/2
✓ Branch 0 taken 53 times.
✓ Branch 1 taken 5 times.
 58 if (m_found.nodes > 0) {
119 53 m_found.childrenPerNode = double(m_slots) / m_found.nodes;
120 }
121
2/2
✓ Branch 0 taken 53 times.
✓ Branch 1 taken 5 times.
 58 if (m_found.leaves > 0) {
122 53 m_found.recordsPerLeaf = double(m_found.records) / m_found.leaves;
123 }
124
2/2
✓ Branch 0 taken 1 time.
✓ Branch 1 taken 57 times.
 58 if (m_dropped > 0) {
125 2 m_found.errors.push_back(fmt::format("and {} more faults", m_dropped));
126 }
127 }
128
129 private:
130 196 void Fail(std::string message) {
131
2/2
✓ Branch 0 taken 128 times.
✓ Branch 1 taken 68 times.
 196 if (m_found.errors.size() < kMaxErrors) {
132 128 m_found.errors.push_back(std::move(message));
133 } else {
134 68 ++m_dropped;
135 }
136 196 }
137
138 123 bool Fits(const char* what, uint64_t offset, uint64_t count, uint64_t bytes) {
139
4/6
✓ Branch 0 taken 123 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 123 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 1 time.
✓ Branch 5 taken 122 times.
 123 if (offset % 16 != 0 || offset > m_bytes.size() ||
140
2/2
✓ Branch 0 taken 1 time.
✓ Branch 1 taken 122 times.
 123 count > (m_bytes.size() - offset) / bytes) {
141
1/1
✓ Branch 1 taken 1 time.
 1 Fail(fmt::format("its {} at byte {}, {} of {} bytes, run past its {} bytes", what,
142 1 offset, count, bytes, m_bytes.size()));
143 1 return false;
144 }
145 return true;
146 }
147
148 30053 template <class T> T Read(uint64_t offset) const {
149 T value;
150 30053 std::memcpy(&value, m_bytes.data() + offset, sizeof(T));
151 return value;
152 }
153
154 2696 void Visit(uint32_t index, const BvhBox& within, uint32_t depth) {
155
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 2694 times.
 2696 if (index >= m_header.nodeCount) {
156
1/1
✓ Branch 1 taken 2 times.
 2 Fail(fmt::format("a node's child is node {}, past its {} nodes", index,
157 2 m_header.nodeCount));
158 2 return;
159 }
160
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 2694 times.
 2694 if (m_visited[index]) {
161
0/1
✗ Branch 2 not taken.
 ✗ Fail(fmt::format("node {} is reached more than once", index));
162 ✗ return;
163 }
164
165
2/2
✓ Branch 1 taken 126 times.
✓ Branch 2 taken 2568 times.
 2694 m_visited[index] = true;
166 2694 ++m_found.nodes;
167
2/2
✓ Branch 0 taken 126 times.
✓ Branch 1 taken 2568 times.
 2694 m_found.depth = std::max(m_found.depth, depth);
168
169 2694 BvhNode node = Read<BvhNode>(m_header.nodes + uint64_t(index) * sizeof(BvhNode));
170 2694 const uint32_t imask = node.exponents >> 24;
171 2694 uint32_t internal = 0;
172
2/2
✓ Branch 0 taken 21552 times.
✓ Branch 1 taken 2694 times.
 24246 for (uint32_t slot = 0; slot < kBvhWidth; ++slot) {
173
2/2
✓ Branch 0 taken 6619 times.
✓ Branch 1 taken 14933 times.
 21552 const uint32_t meta = BvhByte(node.meta, slot);
174 21552 const bool isInternal = (imask >> slot & 1) != 0;
175
2/2
✓ Branch 0 taken 6619 times.
✓ Branch 1 taken 14933 times.
 21552 if (meta == 0) {
176
2/2
✓ Branch 0 taken 1 time.
✓ Branch 1 taken 6618 times.
 6619 if (isInternal) {
177
1/1
✓ Branch 2 taken 1 time.
 2 Fail(fmt::format("node {}'s slot {} is empty but in its imask", index, slot));
178 }
179 9272 continue;
180 }
181 14933 ++m_slots;
182 14933 const BvhBox box = BvhChildBox(node, slot);
183
2/2
✓ Branch 0 taken 12544 times.
✓ Branch 1 taken 2389 times.
 14933 const double weight = m_rootArea > 0 ? double(BvhArea(box)) / m_rootArea : 1;
184 14933 const BvhBox inside = Intersect(within, box);
185
2/2
✓ Branch 0 taken 2645 times.
✓ Branch 1 taken 12288 times.
 14933 if (isInternal) {
186
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 2643 times.
 2645 if (meta != BvhInternalMeta(slot)) {
187
1/1
✓ Branch 1 taken 2 times.
 2 Fail(
188 2 fmt::format("node {}'s slot {} is in its imask, but its meta byte is {:#x}",
189 index, slot, meta));
190 2 continue;
191 }
192 2643 m_found.sahCost += weight;
193 2643 m_found.nodeCost += weight;
194 2643 m_pending.push_back({node.firstChild + internal++, inside, depth + 1});
195 2643 continue;
196 }
197
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 12286 times.
 12288 if (meta == BvhInternalMeta(slot)) {
198
1/1
✓ Branch 1 taken 2 times.
 2 Fail(
199 2 fmt::format("node {}'s slot {} has an internal child's meta byte, but isn't in "
200 "its imask",
201 index, slot));
202 2 continue;
203 }
204
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 12280 times.
 12286 const uint32_t count = std::popcount(meta >> 5);
205
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 12280 times.
 12286 if ((meta >> 5) != (1u << count) - 1) {
206
1/1
✓ Branch 2 taken 6 times.
 6 Fail(fmt::format("node {}'s slot {} has meta byte {:#x}: neither empty, internal "
207 "nor a leaf's",
208 index, slot, meta));
209 6 continue;
210 }
211 12280 ++m_found.leaves;
212 12280 m_found.sahCost += weight * count;
213 12280 m_found.recordCost += weight * count;
214
2/2
✓ Branch 0 taken 27360 times.
✓ Branch 1 taken 12280 times.
 39640 for (uint32_t i = 0; i < count; ++i) {
215 27360 VisitRecord(index, node.firstLeaf + m_words * ((meta & 31) + i), inside);
216 }
217 }
218 }
219
220 27360 void VisitRecord(uint32_t node, uint32_t word, const BvhBox& within) {
221
3/4
✓ Branch 0 taken 27360 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 1 time.
✓ Branch 3 taken 27359 times.
 27360 if (word % m_words != 0 || word / m_words >= m_header.leafCount) {
222
1/1
✓ Branch 1 taken 1 time.
 1 Fail(fmt::format("node {} has a leaf record at word {}, not one of its {} records",
223 1 node, word, m_header.leafCount));
224 19 return;
225 }
226 27359 ++m_found.records;
227 27359 const uint64_t at = m_header.leaves + uint64_t(word) * 16;
228
229 27359 uint32_t primitive;
230 27359 BvhBox box;
231
2/2
✓ Branch 0 taken 353 times.
✓ Branch 1 taken 27006 times.
 27359 if (m_header.kind == kBvhInstances) {
232
1/2
✓ Branch 0 taken 353 times.
✗ Branch 1 not taken.
 353 primitive = Read<BvhInstance>(at).index & kBvhIndexMask;
233
2/4
✓ Branch 0 taken 353 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 353 times.
 353 if (m_boxes.empty() || primitive >= m_boxes.size()) {
234 ✗ box = within;
235 } else {
236 353 box = m_boxes[primitive];
237 }
238
2/2
✓ Branch 0 taken 1536 times.
✓ Branch 1 taken 25470 times.
 27006 } else if (m_header.kind == kBvhBoxes) {
239 1536 const auto record = Read<BvhBoxRecord>(at);
240 1536 primitive = record.index;
241 1536 std::memcpy(box.lower, record.lower, sizeof(box.lower));
242 1536 std::memcpy(box.upper, record.upper, sizeof(box.upper));
243 } else {
244 25470 const auto triangle = Read<BvhTriangle>(at);
245 25470 primitive = triangle.index;
246 25470 BvhCorners corners;
247
2/2
✓ Branch 0 taken 76410 times.
✓ Branch 1 taken 25470 times.
 101880 for (int i = 0; i < 3; ++i) {
248 76410 corners.a[i] = triangle.a[i];
249 76410 corners.b[i] = triangle.a[i] + triangle.edgeB[i];
250 76410 corners.c[i] = triangle.a[i] + triangle.edgeC[i];
251 }
252 25470 box = BvhTriangleBox(corners);
253 }
254
255
2/2
✓ Branch 0 taken 1 time.
✓ Branch 1 taken 27358 times.
 27359 if (primitive >= m_header.primitives) {
256
1/1
✓ Branch 1 taken 1 time.
 1 Fail(fmt::format("node {} has primitive {}, past its {} primitives", node, primitive,
257 1 m_header.primitives));
258 1 return;
259 }
260 27358 ++m_reached[primitive];
261
2/2
✓ Branch 0 taken 82040 times.
✓ Branch 1 taken 27341 times.
 109381 for (int i = 0; i < 3; ++i) {
262
2/2
✓ Branch 0 taken 82024 times.
✓ Branch 1 taken 16 times.
 82040 if (box.lower[i] < within.lower[i] - m_slack ||
263
2/2
✓ Branch 0 taken 1 time.
✓ Branch 1 taken 82023 times.
 82024 box.upper[i] > within.upper[i] + m_slack) {
264
1/1
✓ Branch 2 taken 17 times.
 17 Fail(fmt::format("primitive {} of node {} lies outside the boxes above it",
265 primitive, node));
266 17 return;
267 }
268 }
269 }
270
271 struct Pending {
272 uint32_t index;
273 BvhBox within;
274 uint32_t depth;
275 };
276
277 std::span<const std::byte> m_bytes;
278 std::span<const BvhBox> m_boxes;
279 Inspection& m_found;
280 std::vector<Pending> m_pending;
281 BvhHeader m_header{};
282 uint32_t m_words = 0;
283 std::vector<uint32_t> m_reached;
284 std::vector<bool> m_visited;
285 double m_rootArea = 0;
286 float m_slack = 0;
287 uint64_t m_slots = 0;
288 size_t m_dropped = 0;
289 };
290
291 }
292
293 65 Inspection Inspect(std::span<const std::byte> bytes, std::span<const BvhBox> boxes) {
294 65 Inspection found;
295
1/1
✓ Branch 2 taken 65 times.
 65 Walker(bytes, boxes, found).Run();
296 65 return found;
297 ✗ }
298
299 }
300