1#ifndef BVH_V2_MINI_TREE_BUILDER_H
2#define BVH_V2_MINI_TREE_BUILDER_H
23template <
typename Node,
typename MortonCode = u
int32_t>
49 std::span<const BBox> bboxes,
50 std::span<const Vec> centers,
55 if (config.enable_pruning)
64 std::vector<size_t>
ids;
85 for (
size_t i = 0; i <
bins.size();) {
95 [] (
const Bin& bin) { return bin.ids.empty(); }) -
bins.begin());
100 for (
size_t i = 0,
n = std::min(
bins.size(),
other.bins.size()); i <
n; ++i)
129 for (
size_t i = 0; i <
prim_ids.size(); ++i) {
137 for (
size_t i = 0; i <
bvh.prim_ids.size(); ++i)
149 std::span<const BBox> bboxes,
150 std::span<const Vec> centers,
157 assert(bboxes.size() == centers.size());
163 [
this] (
BBox& bbox,
size_t begin,
size_t end) {
164 for (size_t i = begin; i < end; ++i)
165 bbox.extend(centers_[i]);
178 local_bins.bins.resize(bin_count);
179 for (size_t i = begin; i < end; ++i) {
180 auto p = robust_max(fast_mul_add(centers_[i], grid_scale, grid_offset), Vec(0));
181 auto x = std::min(grid_dim - 1, static_cast<size_t>(p[0]));
182 auto y = std::min(grid_dim - 1, static_cast<size_t>(p[1]));
183 auto z = std::min(grid_dim - 1, static_cast<size_t>(p[2]));
184 local_bins[morton_encode(x, y, z) & (bin_count - 1)].add(i);
198 for (
size_t i = 0; i <
final_bins.bins.size(); ++i) {
216 std::stack<size_t> stack;
218 for (
size_t i = 0; i <
mini_trees.size(); ++i) {
221 while (!stack.empty()) {
222 auto node_id = stack.top();
225 if (node.get_bbox().get_half_area() <
threshold || node.is_leaf()) {
228 stack.push(node.index.first_id());
229 stack.push(node.index.first_id() + 1);
237 [&] (
size_t begin,
size_t end) {
238 for (size_t i = begin; i < end; ++i) {
239 if (pruned_roots[i].second == 0)
240 pruned_trees[i] = std::move(mini_trees[pruned_roots[i].first]);
242 pruned_trees[i] = mini_trees[pruned_roots[i].first]
243 .extract_bvh(pruned_roots[i].second);
253 for (
size_t i = 0; i <
mini_trees.size(); ++i) {
254 bboxes[i] =
mini_trees[i].get_root().get_bbox();
255 centers[i] = bboxes[i].get_center();
266 size_t prim_count = 0;
267 for (
size_t i = 0; i <
mini_trees.size(); ++i) {
282 for (
auto& node :
bvh.nodes) {
285 assert(node.index.prim_count() == 1);
286 size_t tree_id =
bvh.prim_ids[node.index.first_id()];
291 bvh.prim_ids.resize(prim_count);
293 [&] (
size_t begin,
size_t end) {
294 for (size_t i = begin; i < end; ++i) {
295 auto& mini_tree = mini_trees[i];
299 for (size_t j = 1; j < mini_tree.nodes.size(); ++j)
300 copy_node(i, bvh.nodes[node_offsets[i] + j], mini_tree.nodes[j]);
303 mini_tree.prim_ids.begin(),
304 mini_tree.prim_ids.end(),
305 bvh.prim_ids.begin() + prim_offsets[i]);
ROOT::Detail::TRangeCast< T, true > TRangeDynCast
TRangeDynCast is an adapter class that allows the typed iteration through a TCollection.
Option_t Option_t TPoint TPoint const char GetTextMagnitude GetFillStyle GetLineColor GetLineWidth GetMarkerStyle GetTextAlign GetTextColor GetTextSize void char Point_t Rectangle_t WindowAttributes_t Float_t Float_t Float_t Int_t Int_t UInt_t UInt_t Rectangle_t result
const_iterator begin() const
const_iterator end() const
Multi-threaded top-down builder that partitions primitives using a grid.
static BVH_ALWAYS_INLINE Bvh< Node > build(ThreadPool &thread_pool, std::span< const BBox > bboxes, std::span< const Vec > centers, const Config &config={})
Starts building a BVH with the given primitive data.
std::span< const BBox > bboxes_
std::span< const Vec > centers_
std::vector< Bvh< Node > > build_mini_trees()
std::vector< Bvh< Node > > prune_mini_trees(std::vector< Bvh< Node > > &&mini_trees)
ParallelExecutor executor_
BVH_ALWAYS_INLINE MiniTreeBuilder(ThreadPool &thread_pool, std::span< const BBox > bboxes, std::span< const Vec > centers, const Config &config)
bvh::v2::Vec< Scalar, Node::dimension > Vec
Bvh< Node > build_top_bvh(std::vector< Bvh< Node > > &mini_trees)
typename Node::Scalar Scalar
Single-threaded top-down builder that partitions primitives based on the Surface Area Heuristic (SAH)...
Base class for all SAH-based, top-down builders.
BVH_ALWAYS_INLINE T safe_inverse(T x)
Computes the inverse of the given value, always returning a finite value.
static BVH_ALWAYS_INLINE constexpr BBox make_empty()
std::vector< size_t > ids
BVH_ALWAYS_INLINE void merge(Bin &&other)
BVH_ALWAYS_INLINE void add(size_t id)
std::vector< BBox > bboxes
BuildTask(MiniTreeBuilder *builder, Bvh< Node > &bvh, std::vector< size_t > &&prim_ids)
MiniTreeBuilder * builder
std::vector< Vec > centers
BVH_ALWAYS_INLINE void run()
std::vector< size_t > prim_ids
size_t log2_grid_dim
Log of the dimension of the grid used to split the workload horizontally.
Scalar pruning_area_ratio
Threshold on the area of a mini-tree node above which it is pruned, expressed in fraction of the area...
bool enable_pruning
Flag that turns on/off mini-tree pruning.
size_t parallel_threshold
Minimum number of primitives per parallel task.
BVH_ALWAYS_INLINE void merge_small_bins(size_t threshold)
BVH_ALWAYS_INLINE Bin & operator[](size_t i)
BVH_ALWAYS_INLINE void remove_empty_bins()
BVH_ALWAYS_INLINE void merge(LocalBins &&other)
Binary BVH node, containing its bounds and an index into its children or the primitives it contains.
static constexpr size_t dimension
Executor that executes in parallel using the given thread pool.
T reduce(size_t begin, size_t end, const T &init, const Reduce &reduce, const Join &join)
void for_each(size_t begin, size_t end, const Loop &loop)
size_t min_leaf_size
Nodes containing less than this amount of primitives will not be split.
size_t max_leaf_size
Nodes that cannot be split based on the SAH and have a number of primitives larger than this will be ...