orange/detail/BvhBuilder.hh

0001 //------------------------------- -*- C++ -*- -------------------------------//
0002 // Copyright Celeritas contributors: see top-level COPYRIGHT file for details
0003 // SPDX-License-Identifier: (Apache-2.0 OR MIT)
0004 //---------------------------------------------------------------------------//
0005 //! \file orange/detail/BvhBuilder.hh
0006 //---------------------------------------------------------------------------//
0007 #pragma once
0008
0009 #include <set>
0010 #include <utility>
0011 #include <variant>
0012 #include <vector>
0013
0014 #include "corecel/Types.hh"
0015 #include "corecel/cont/Array.hh"
0016 #include "corecel/data/CollectionBuilder.hh"
0017 #include "geocel/BoundingBox.hh"  // IWYU pragma: keep
0018 #include "orange/OrangeTypes.hh"
0019 #include "orange/detail/BvhData.hh"
0020
0021 #include "../inp/Bvh.hh"
0022
0023 namespace celeritas
0024 {
0025 namespace detail
0026 {
0027 //---------------------------------------------------------------------------//
0028 /*!
0029  * Create a bounding volume hierarchy (BVH) from the supplied bounding boxes.
0030  *
0031  * The class builds a Bounting Volume Hierarchy \citet{ericson-collision-2004,
0032  * https://www.taylorfrancis.com/books/9780080474144} ) using a top-down,
0033  * recursive construction method. Leaf nodes are created when one of the
0034  * following criteria are met:
0035  *
0036  * 1) the number of remaining bounding boxes is max_leaf_size or fewer,
0037  * 2) the remaining bounding boxes are non-partitionable (i.e., they all have
0038  *    the same center),
0039  * 3) the current recursion depth has reached the `depth_limit`.
0040  *
0041  * Any bounding boxes that have at least one infinite dimension are not stored
0042  * on the tree, but rather a separate `inf_vols` structure. In the event that
0043  * all bounding boxes are infinite, the tree will consist of a single empty
0044  * leaf node with all volumes in the stored `inf_vols`. This final case should
0045  * not occur unless an ORANGE geometry is created via a method where volume
0046  * bounding boxes are not available.
0047  *
0048  * Bounding boxes supplied to this builder should "bumped," i.e. expanded
0049  * outward by at least floating-point epsilson from the volumes they bound.
0050  * This eliminates the possibility of accidentally missing a volume during
0051  * tracking.
0052  */
0053 class BvhBuilder
0054 {
0055   public:
0056     //!@{
0057     //! \name Type aliases
0058     using VecBBox = std::vector<FastBBox>;
0059     using Storage = BvhTreeData<Ownership::value, MemSpace::host>;
0060     using SetLocalVolId = std::set<LocalVolumeId>;
0061     using Input = inp::BvhBuilder;
0062     //!@}
0063
0064   public:
0065     // Construct from Storage and Input objects
0066     BvhBuilder(Storage* storage, Input inp);
0067
0068     // Create BVH Nodes
0069     BvhTreeRecord operator()(VecBBox&& bboxes,
0070                              SetLocalVolId const& implicit_vol_id);
0071
0072   private:
0073     /// TYPES ///
0074
0075     using Real3 = Array<fast_real_type, 3>;
0076     using VecIndices = std::vector<LocalVolumeId>;
0077     using VecNodes = std::vector<std::variant<BvhInternalNode, BvhLeafNode>>;
0078     using VecInnerNodes = std::vector<BvhInternalNode>;
0079     using VecLeafNodes = std::vector<BvhLeafNode>;
0080     using ArrangedNodes = std::pair<VecInnerNodes, VecLeafNodes>;
0081
0082     struct Temporaries
0083     {
0084         VecBBox bboxes;
0085         std::vector<Real3> centers;
0086     };
0087
0088     //// DATA ////
0089     Temporaries temp_;
0090
0091     CollectionBuilder<FastBBox> bboxes_;
0092     CollectionBuilder<LocalVolumeId> local_volume_ids_;
0093     CollectionBuilder<BvhInternalNode> internal_nodes_;
0094     CollectionBuilder<BvhLeafNode> leaf_nodes_;
0095
0096     Input inp_;
0097
0098     //// HELPER FUNCTIONS ////
0099
0100     // Recursively construct BVH nodes for a vector of bbox indices
0101     void construct_tree(VecIndices const& indices,
0102                         VecNodes* nodes,
0103                         size_type current_depth,
0104                         size_type& depth);
0105
0106     // Separate nodes into inner and leaf vectors and renumber accordingly
0107     ArrangedNodes arrange_nodes(VecNodes const& nodes) const;
0108 };
0109
0110 //---------------------------------------------------------------------------//
0111 }  // namespace detail
0112 }  // namespace celeritas