bvh/v2/top_down_sah_builder.h

0001 #ifndef BVH_V2_TOP_DOWN_SAH_BUILDER_H
0002 #define BVH_V2_TOP_DOWN_SAH_BUILDER_H
0003
0004 #include "bvh/v2/bvh.h"
0005 #include "bvh/v2/vec.h"
0006 #include "bvh/v2/bbox.h"
0007 #include "bvh/v2/split_heuristic.h"
0008 #include <stack>
0009 #if __has_include(<span>)
0010 #include <span>
0011 #else
0012 // Falling back to ROOT span
0013 #include "ROOT/span.hxx"
0014 #endif
0015 #include <algorithm>
0016 #include <optional>
0017 #include <numeric>
0018 #include <cassert>
0019
0020 namespace bvh::v2 {
0021
0022 /// Base class for all SAH-based, top-down builders.
0023 template <typename Node>
0024 class TopDownSahBuilder {
0025 protected:
0026     using Scalar = typename Node::Scalar;
0027     using Vec  = bvh::v2::Vec<Scalar, Node::dimension>;
0028     using BBox = bvh::v2::BBox<Scalar, Node::dimension>;
0029
0030 public:
0031     struct Config {
0032         /// SAH heuristic parameters that control how primitives are partitioned.
0033         SplitHeuristic<Scalar> sah;
0034
0035         /// Nodes containing less than this amount of primitives will not be split.
0036         /// This is mostly to speed up BVH construction, and using large values may lead to lower
0037         /// quality BVHs.
0038         size_t min_leaf_size = 1;
0039
0040         /// Nodes that cannot be split based on the SAH and have a number of primitives larger than
0041         /// this will be split using a fallback strategy. This should not happen often, but may
0042         /// happen in worst-case scenarios or poorly designed scenes.
0043         size_t max_leaf_size = 8;
0044     };
0045
0046 protected:
0047     struct WorkItem {
0048         size_t node_id;
0049         size_t begin;
0050         size_t end;
0051
0052         BVH_ALWAYS_INLINE size_t size() const { return end - begin; }
0053     };
0054
0055     std::span<const BBox> bboxes_;
0056     std::span<const Vec> centers_;
0057     const Config& config_;
0058
0059     BVH_ALWAYS_INLINE TopDownSahBuilder(
0060         std::span<const BBox> bboxes,
0061         std::span<const Vec> centers,
0062         const Config& config)
0063         : bboxes_(bboxes)
0064         , centers_(centers)
0065         , config_(config)
0066     {
0067         assert(bboxes.size() == centers.size());
0068         assert(config.min_leaf_size <= config.max_leaf_size);
0069     }
0070
0071     virtual std::vector<size_t>& get_prim_ids() = 0;
0072     virtual std::optional<size_t> try_split(const BBox& bbox, size_t begin, size_t end) = 0;
0073
0074     BVH_ALWAYS_INLINE const std::vector<size_t>& get_prim_ids() const {
0075         return const_cast<TopDownSahBuilder*>(this)->get_prim_ids();
0076     }
0077
0078     Bvh<Node> build() {
0079         const auto prim_count = bboxes_.size();
0080
0081         Bvh<Node> bvh;
0082         bvh.nodes.reserve((2 * prim_count) / config_.min_leaf_size);
0083         bvh.nodes.emplace_back();
0084         bvh.nodes.back().set_bbox(compute_bbox(0, prim_count));
0085
0086         std::stack<WorkItem> stack;
0087         stack.push(WorkItem { 0, 0, prim_count });
0088         while (!stack.empty()) {
0089             auto item = stack.top();
0090             stack.pop();
0091
0092             auto& node = bvh.nodes[item.node_id];
0093             if (item.size() > config_.min_leaf_size) {
0094                 if (auto split_pos = try_split(node.get_bbox(), item.begin, item.end)) {
0095                     auto first_child = bvh.nodes.size();
0096                     node.index = Node::Index::make_inner(first_child);
0097
0098                     bvh.nodes.resize(first_child + 2);
0099
0100                     auto first_bbox   = compute_bbox(item.begin, *split_pos);
0101                     auto second_bbox  = compute_bbox(*split_pos, item.end);
0102                     auto first_range  = std::make_pair(item.begin, *split_pos);
0103                     auto second_range = std::make_pair(*split_pos, item.end);
0104
0105                     // For "any-hit" queries, the left child is chosen first, so we make sure that
0106                     // it is the child with the largest area, as it is more likely to contain an
0107                     // an occluder. See "SATO: Surface Area Traversal Order for Shadow Ray Tracing",
0108                     // by J. Nah and D. Manocha.
0109                     if (first_bbox.get_half_area() < second_bbox.get_half_area()) {
0110                         std::swap(first_bbox, second_bbox);
0111                         std::swap(first_range, second_range);
0112                     }
0113
0114                     auto first_item  = WorkItem { first_child + 0, first_range.first, first_range.second };
0115                     auto second_item = WorkItem { first_child + 1, second_range.first, second_range.second };
0116                     bvh.nodes[first_child + 0].set_bbox(first_bbox);
0117                     bvh.nodes[first_child + 1].set_bbox(second_bbox);
0118
0119                     // Process the largest child item first, in order to minimize the stack size.
0120                     if (first_item.size() < second_item.size())
0121                         std::swap(first_item, second_item);
0122
0123                     stack.push(first_item);
0124                     stack.push(second_item);
0125                     continue;
0126                 }
0127             }
0128
0129             node.index = Node::Index::make_leaf(item.begin, item.size());
0130         }
0131
0132         bvh.prim_ids = std::move(get_prim_ids());
0133         bvh.nodes.shrink_to_fit();
0134         return bvh;
0135     }
0136
0137     BVH_ALWAYS_INLINE BBox compute_bbox(size_t begin, size_t end) const {
0138         const auto& prim_ids = get_prim_ids();
0139         auto bbox = BBox::make_empty();
0140         for (size_t i = begin; i < end; ++i)
0141             bbox.extend(bboxes_[prim_ids[i]]);
0142         return bbox;
0143     }
0144 };
0145
0146 } // namespace bvh::v2
0147
0148 #endif