1#ifndef BVH_V2_REINSERTION_OPTIMIZER_H
2#define BVH_V2_REINSERTION_OPTIMIZER_H
13template <
typename Node>
65 template <
typename Derived>
71 template <
typename Derived>
75 executor.for_each(0,
bvh.nodes.size(),
76 [&] (
size_t begin,
size_t end) {
77 for (size_t i = begin; i < end; ++i) {
78 auto& node = bvh.nodes[i];
79 if (!node.is_leaf()) {
80 parents[node.index.first_id() + 0] = i;
81 parents[node.index.first_id() + 1] = i;
96 for (
size_t i =
node_count; i < bvh_.nodes.size(); ++i) {
97 auto cost = bvh_.nodes[i].get_bbox().get_half_area();
140 auto node_area = bvh_.nodes[node_id].get_bbox().get_half_area();
141 auto parent_area = bvh_.nodes[parents_[node_id]].get_bbox().get_half_area();
148 std::vector<std::pair<Scalar, size_t>> stack;
152 while (!stack.empty()) {
153 auto top = stack.back();
158 auto&
dst_node = bvh_.nodes[top.second];
159 auto merged_area =
dst_node.get_bbox().extend(bvh_.nodes[node_id].get_bbox()).get_half_area();
177 area_diff += bvh_.nodes[
pivot_id].get_bbox().get_half_area() -
pivot_bbox.get_half_area();
217 auto& node = bvh_.nodes[
index];
218 if (!node.is_leaf()) {
220 bvh_.nodes[node.index.first_id() + 0].get_bbox().extend(
221 bvh_.nodes[node.index.first_id() + 1].get_bbox()));
224 }
while (
index != 0);
228 return std::array<size_t, 5> {
236 template <
typename Derived>
238 auto batch_size = std::max(
size_t{1},
241 std::vector<bool>
touched(bvh_.nodes.size());
244 auto candidates = find_candidates(batch_size);
249 [&] (
size_t begin,
size_t end) {
250 for (size_t i = begin; i < end; ++i)
251 reinsertions[i] = find_reinsertion(candidates[i].node_id);
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 r
Option_t Option_t TPoint TPoint const char GetTextMagnitude GetFillStyle GetLineColor GetLineWidth GetMarkerStyle GetTextAlign GetTextColor GetTextSize void char Point_t Rectangle_t WindowAttributes_t index
const_iterator begin() const
const_iterator end() const
static std::vector< size_t > compute_parents(Executor< Derived > &executor, const Bvh< Node > &bvh)
BVH_ALWAYS_INLINE std::vector< Candidate > find_candidates(size_t target_count)
Reinsertion find_reinsertion(size_t node_id)
typename Node::Scalar Scalar
BVH_ALWAYS_INLINE auto get_conflicts(size_t from, size_t to)
BVH_ALWAYS_INLINE void reinsert_node(size_t from, size_t to)
void optimize(Executor< Derived > &executor, const Config &config)
std::vector< size_t > parents_
BVH_ALWAYS_INLINE void refit_from(size_t index)
static void optimize(Bvh< Node > &bvh, const Config &config={})
ReinsertionOptimizer(Bvh< Node > &bvh, std::vector< size_t > &&parents)
static void optimize(Executor< Derived > &executor, Bvh< Node > &bvh, const Config &config)
static void optimize(ThreadPool &thread_pool, Bvh< Node > &bvh, const Config &config={})
static BVH_ALWAYS_INLINE size_t get_sibling_id(size_t node_id)
Returns the index of a sibling of a node.
static BVH_ALWAYS_INLINE Index make_inner(size_t first_child)
Executor that executes in parallel using the given thread pool.
BVH_ALWAYS_INLINE bool operator>(const Candidate &other) const
size_t max_iter_count
Maximum number of iterations.
Scalar batch_size_ratio
Fraction of the number of nodes to optimize per iteration.
BVH_ALWAYS_INLINE bool operator>(const Reinsertion &other) const
Executor that executes serially.