orange/detail/BIHBuilder.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/BIHBuilder.hh
0006 //---------------------------------------------------------------------------//
0007 #pragma once
0008
0009 #include <set>
0010 #include <variant>
0011 #include <vector>
0012
0013 #include "corecel/cont/Range.hh"
0014 #include "corecel/data/CollectionBuilder.hh"
0015 #include "geocel/BoundingBox.hh"
0016
0017 #include "BIHPartitioner.hh"
0018 #include "../OrangeData.hh"
0019
0020 namespace celeritas
0021 {
0022 namespace detail
0023 {
0024 //---------------------------------------------------------------------------//
0025 /*!
0026  * Create a bounding interval hierarchy from supplied bounding boxes.
0027  *
0028  * This implementation matches the structure proposed in the original
0029  * paper \citep{wachter-bih-2006, https://doi.org/10.2312/EGWR/EGSR06/139-149}.
0030  * Partitioning is done on the basis of bounding box centers using the "longest
0031  * dimension" heuristic. All leaf nodes contain either a single volume id, or
0032  * multiple volume ids if the volumes have bounding boxes that share the same
0033  * center. A tree may consist of a single leaf node if the tree contains only 1
0034  * volume, or multiple non-partitionable volumes. In the event that all
0035  * bounding boxes are infinite, the tree will consist of a single empty leaf
0036  * node with all volumes in the stored inf_vols. This final case is useful in
0037  * the event that an ORANGE geometry is created via a method where volume
0038  * bounding boxes are not availible.
0039  *
0040  * Bounding boxes supplied to this builder should "bumped," i.e. expanded
0041  * outward by at least floating-point epsilson from the volumes they bound.
0042  * This eliminates the possiblity of accidently missing a volume during
0043  * tracking.
0044  */
0045 class BIHBuilder
0046 {
0047   public:
0048     //!@{
0049     //! \name Type aliases
0050     using VecBBox = std::vector<FastBBox>;
0051     using Storage = BIHTreeData<Ownership::value, MemSpace::host>;
0052     using SetLocalVolId = std::set<LocalVolumeId>;
0053     //!@}
0054
0055   public:
0056     // Construct from a Storage object
0057     explicit BIHBuilder(Storage* storage);
0058
0059     // Create BIH Nodes
0060     BIHTree operator()(VecBBox&& bboxes, SetLocalVolId const& implicit_vol_ids);
0061
0062   private:
0063     /// TYPES ///
0064
0065     using Real3 = Array<fast_real_type, 3>;
0066     using VecIndices = std::vector<LocalVolumeId>;
0067     using VecNodes = std::vector<std::variant<BIHInnerNode, BIHLeafNode>>;
0068     using VecInnerNodes = std::vector<BIHInnerNode>;
0069     using VecLeafNodes = std::vector<BIHLeafNode>;
0070     using ArrangedNodes = std::pair<VecInnerNodes, VecLeafNodes>;
0071
0072     struct Temporaries
0073     {
0074         VecBBox bboxes;
0075         std::vector<Real3> centers;
0076     };
0077
0078     //// DATA ////
0079
0080     Temporaries temp_;
0081
0082     CollectionBuilder<FastBBox> bboxes_;
0083     CollectionBuilder<LocalVolumeId> local_volume_ids_;
0084     CollectionBuilder<BIHInnerNode> inner_nodes_;
0085     CollectionBuilder<BIHLeafNode> leaf_nodes_;
0086
0087     //// HELPER FUNCTIONS ////
0088
0089     // Recursively construct BIH nodes for a vector of bbox indices
0090     void construct_tree(VecIndices const& indices,
0091                         VecNodes* nodes,
0092                         BIHNodeId parent,
0093                         FastBBox const& bbox);
0094
0095     // Seperate nodes into inner and leaf vectors and renumber accordingly
0096     ArrangedNodes arrange_nodes(VecNodes const& nodes) const;
0097 };
0098
0099 //---------------------------------------------------------------------------//
0100 }  // namespace detail
0101 }  // namespace celeritas