Shamrock 2025.10.0
Astrophysical Code
Loading...
Searching...
No Matches
CompressedLeafBVH.cpp
Go to the documentation of this file.
1// -------------------------------------------------------//
2//
3// SHAMROCK code for hydrodynamics
4// Copyright (c) 2021-2026 Timothée David--Cléris <tim.shamrock@proton.me>
5// SPDX-License-Identifier: CeCILL Free Software License Agreement v2.1
6// Shamrock is licensed under the CeCILL 2.1 License, see LICENSE for more information
7//
8// -------------------------------------------------------//
9
15
17#include "shambase/integer.hpp"
21
22template<class Tmorton, class Tvec, u32 dim>
24 make_empty(sham::DeviceScheduler_ptr dev_sched) {
25 StackEntry stack_loc{};
26 return {
27 MortonReducedSet<Tmorton, Tvec, dim>::make_empty(dev_sched),
28 KarrasRadixTree::make_empty(dev_sched),
29 KarrasRadixTreeAABB<Tvec>::make_empty(dev_sched)};
30}
31
32template<class Tmorton, class Tvec, u32 dim>
33void shamtree::CompressedLeafBVH<Tmorton, Tvec, dim>::internal_rebuild_from_positions_no_aabb(
34 sham::DeviceBuffer<Tvec> &positions,
35 u32 obj_cnt,
36 const shammath::AABB<Tvec> &bounding_box,
37 u32 compression_level) {
39
40 if (obj_cnt == 0) {
42 "obj_cnt is 0, cannot build a CompressedLeafBVH");
43 }
44
45 auto dev_sched = shamsys::instance::get_compute_scheduler_ptr();
46
47 u32 roundup_pow2 = shambase::roundup_pow2(obj_cnt);
48
50 dev_sched,
51 bounding_box,
52 positions,
53 obj_cnt,
54 roundup_pow2,
55 std::move(reduced_morton_set.morton_codes_set.sorted_morton_codes));
56
57 auto sorted_set = shamtree::sort_morton_set(
58 dev_sched,
59 std::move(set),
60 std::move(reduced_morton_set.morton_codes_set.map_morton_id_to_obj_id));
61
62 auto reduced_set = shamtree::reduce_morton_set(
63 dev_sched,
64 std::move(sorted_set),
65 compression_level,
66 std::move(reduced_morton_set.buf_reduc_index_map),
67 std::move(reduced_morton_set.reduced_morton_codes));
68
70 dev_sched,
71 reduced_set.reduced_morton_codes.get_size(),
72 reduced_set.reduced_morton_codes,
73 std::move(structure));
74
75 this->reduced_morton_set = std::move(reduced_set);
76 this->structure = std::move(tree);
77}
78
79template<class Tmorton, class Tvec, u32 dim>
81 sham::DeviceBuffer<Tvec> &positions,
82 u32 obj_cnt,
83 const shammath::AABB<Tvec> &bounding_box,
84 u32 compression_level) {
85
86 this->internal_rebuild_from_positions_no_aabb(
87 positions, obj_cnt, bounding_box, compression_level);
88
90 this->structure,
91 this->reduced_morton_set.get_leaf_cell_iterator(),
92 std::move(this->aabbs),
93 positions);
94
95 this->aabbs = std::move(tree_aabbs);
96}
97
98template<class Tmorton, class Tvec, u32 dim>
99void shamtree::CompressedLeafBVH<Tmorton, Tvec, dim>::rebuild_from_position_range(
102 u32 obj_cnt,
103 shammath::AABB<Tvec> &bounding_box,
104 u32 compression_level) {
105
106 this->internal_rebuild_from_positions_no_aabb(min, obj_cnt, bounding_box, compression_level);
107
109 this->structure,
110 this->reduced_morton_set.get_leaf_cell_iterator(),
111 std::move(this->aabbs),
112 min,
113 max);
114
115 this->aabbs = std::move(tree_aabbs);
116}
117
118template<class Tmorton, class Tvec, u32 dim>
120 sham::DeviceBuffer<Tvec> &positions,
121 const shammath::AABB<Tvec> &bounding_box,
122 u32 compression_level) {
123 this->rebuild_from_positions(positions, positions.get_size(), bounding_box, compression_level);
124}
125
126template<class Tmorton, class Tvec, u32 dim>
127void shamtree::CompressedLeafBVH<Tmorton, Tvec, dim>::rebuild_from_position_range(
130 shammath::AABB<Tvec> &bounding_box,
131 u32 compression_level) {
132 if (min.get_size() != max.get_size()) {
134 "min and max must have the same size");
135 }
136 this->rebuild_from_position_range(min, max, min.get_size(), bounding_box, compression_level);
137}
138
139template<class Tmorton, class Tvec, u32 dim>
142
143 // a single leaf root (or an empty tree) has no edge to walk
144 if (is_empty() || structure.is_root_leaf()) {
145 return 0;
146 }
147
148 auto dev_sched = shamsys::instance::get_compute_scheduler_ptr();
149 auto &q = dev_sched->get_queue();
150
151 u32 int_cell_count = structure.get_internal_cell_count();
152
153 // height of every cell (internal cells first then leaves, leaves are at height 0)
154 sham::DeviceBuffer<u32> height(structure.get_total_cell_count(), dev_sched);
155 height.fill(0);
156
157 auto traverser = structure.get_structure_traverser();
158
159 // Heights only ever grow towards their exact value, so racing on the in-place updates within
160 // a pass is harmless. Each pass propagates the heights up by at least one level, so after
161 // tree_depth (an upper bound of the real depth) passes the exact height has reached the root.
162 // No convergence check is done to avoid a device to host read back after every pass.
163 for (u32 i = 0; i < structure.tree_depth; i++) {
165 q,
166 sham::MultiRef{traverser},
167 sham::MultiRef{height},
168 int_cell_count,
169 [](u32 gid, auto tree_traverser, u32 *height) {
170 u32 hl = height[tree_traverser.get_left_child(gid)];
171 u32 hr = height[tree_traverser.get_right_child(gid)];
172
173 height[gid] = 1 + sycl::max(hl, hr);
174 });
175 }
176
177 // the root of a Karras tree is always the cell 0
178 return height.get_val_at_idx(0);
179}
180
KarrasRadixTreeAABB< Tvec > compute_tree_aabb_from_position_ranges(const KarrasRadixTree &tree, const LeafCellIterator &cell_it, KarrasRadixTreeAABB< Tvec > &&recycled_tree_aabb, sham::DeviceBuffer< Tvec > &min, sham::DeviceBuffer< Tvec > &max)
same but for position ranges
KarrasRadixTreeAABB< Tvec > compute_tree_aabb_from_positions(const KarrasRadixTree &tree, const LeafCellIterator &cell_it, KarrasRadixTreeAABB< Tvec > &&recycled_tree_aabb, sham::DeviceBuffer< Tvec > &positions)
Compute the AABB of all cells in the tree from positions.
KarrasRadixTree karras_tree_from_morton_set(sham::DeviceScheduler_ptr dev_sched, u32 morton_count, sham::DeviceBuffer< Tmorton > &morton_codes, KarrasRadixTree &&recycled_tree)
Constructs a KarrasRadixTree from a set of reduced Morton codes.
MortonCodeSet< Tmorton, Tvec, dim > morton_code_set_from_positions(const sham::DeviceScheduler_ptr &dev_sched, shammath::AABB< Tvec > bounding_box, sham::DeviceBuffer< Tvec > &pos_buf, u32 cnt_obj, u32 morton_count, sham::DeviceBuffer< Tmorton > &&cache_buf_morton_codes)
Generate a set of Morton codes from a buffer of positions.
MortonCodeSortedSet< Tmorton, Tvec, dim > sort_morton_set(const sham::DeviceScheduler_ptr &dev_sched, MortonCodeSet< Tmorton, Tvec, dim > &&morton_codes_set)
Sorts a set of Morton codes and creates a new MortonCodeSortedSet object with the sorted codes and th...
MortonReducedSet< Tmorton, Tvec, dim > reduce_morton_set(const sham::DeviceScheduler_ptr &dev_sched, MortonCodeSortedSet< Tmorton, Tvec, dim > &&morton_codes_set, u32 reduction_level)
Reduces the given Morton code set by grouping together Morton codes that are close to each other in t...
std::uint32_t u32
32 bit unsigned integer
A buffer allocated in USM (Unified Shared Memory).
void fill(T value, std::array< size_t, 2 > idx_range)
Fill a subpart of the buffer with a given value.
T get_val_at_idx(size_t idx) const
Get the value at a given index in the buffer.
size_t get_size() const
Gets the number of elements in the buffer.
A Compressed Leaf Bounding Volume Hierarchy (CLBVH) for neighborhood queries.
bool is_empty() const
is the BVH empty ?
u32 get_exact_tree_depth() const
Compute the exact depth of the tree.
KarrasRadixTreeAABB< Tvec > aabbs
The bounding box of the tree cells.
MortonReducedSet< Tmorton, Tvec, dim > reduced_morton_set
The reduced set of Morton codes.
void rebuild_from_positions(sham::DeviceBuffer< Tvec > &positions, const shammath::AABB< Tvec > &bounding_box, u32 compression_level)
rebuild the BVH from the given positions
KarrasRadixTree structure
The tree structure.
static CompressedLeafBVH make_empty(sham::DeviceScheduler_ptr dev_sched)
make an empty BVH
This header file contains utility functions related to exception handling in the code.
void kernel_call(sham::DeviceQueue &q, RefIn in, RefOut in_out, u32 n, Functor &&func, SourceLocation &&callsite=SourceLocation{})
Submit a kernel to a SYCL queue.
constexpr T roundup_pow2(T v) noexcept
round up to the next power of two Source : https://graphics.stanford.edu/~seander/bithacks....
Definition integer.hpp:92
ExcptTypes make_except_with_loc(std::string message, SourceLocation loc=SourceLocation{})
Create an exception with a message and a location.
This file contains the definition for the stacktrace related functionality.
#define __shamrock_stack_entry()
Macro to create a stack entry.
shambase::details::BasicStackEntry StackEntry
Alias for shambase::details::BasicStackEntry.
A class that references multiple buffers or similar objects.
Definition MultiRef.hpp:33
Axis-Aligned bounding box.
Definition AABB.hpp:99