orange/detail/BIHBuilder.hh

0001 //----------------------------------*-C++-*----------------------------------//
0002 // Copyright 2022-2024 UT-Battelle, LLC, and other Celeritas developers.
0003 // See the top-level COPYRIGHT file for details.
0004 // SPDX-License-Identifier: (Apache-2.0 OR MIT)
0005 //---------------------------------------------------------------------------//
0006 //! \file orange/detail/BIHBuilder.hh
0007 //---------------------------------------------------------------------------//
0008 #pragma once
0009
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 [1]. Partitioning is done on the basis of bounding box centers using
0030  * the "longest dimension" heuristic. All leaf nodes contain either a single
0031  * volume id, or multiple volume ids if the volumes have bounding boxes that
0032  * share the same center. A tree may consist of a single leaf node if the
0033  * tree contains only 1 volume, or multiple non-partitionable volumes. In the
0034  * event that all bounding boxes are infinite, the tree will consist of a
0035  * single empty leaf node with all volumes in the stored inf_vols. This final
0036  * case is useful in the event that an ORANGE geometry is created via a method
0037  * where volume bounding boxes are not availible.
0038  *
0039  * [1] C. Wachter, Carsten and A. Keller, "Instant Ray Tracing: The Bounding
0040  * Interval Hierarchy" Eurographics Symposium on Rendering, 2006,
0041  * doi:10.2312/EGWR/EGSR06/139-149}
0042  */
0043 class BIHBuilder
0044 {
0045   public:
0046     //!@{
0047     //! \name Type aliases
0048     using VecBBox = std::vector<FastBBox>;
0049     using Storage = BIHTreeData<Ownership::value, MemSpace::host>;
0050     //!@}
0051
0052   public:
0053     // Construct from a Storage object
0054     explicit BIHBuilder(Storage* storage);
0055
0056     // Create BIH Nodes
0057     BIHTree operator()(VecBBox&& bboxes);
0058
0059   private:
0060     /// TYPES ///
0061
0062     using Real3 = Array<fast_real_type, 3>;
0063     using VecIndices = std::vector<LocalVolumeId>;
0064     using VecNodes = std::vector<std::variant<BIHInnerNode, BIHLeafNode>>;
0065     using VecInnerNodes = std::vector<BIHInnerNode>;
0066     using VecLeafNodes = std::vector<BIHLeafNode>;
0067     using ArrangedNodes = std::pair<VecInnerNodes, VecLeafNodes>;
0068
0069     struct Temporaries
0070     {
0071         VecBBox bboxes;
0072         std::vector<Real3> centers;
0073     };
0074
0075     //// DATA ////
0076
0077     Temporaries temp_;
0078
0079     CollectionBuilder<FastBBox> bboxes_;
0080     CollectionBuilder<LocalVolumeId> local_volume_ids_;
0081     CollectionBuilder<BIHInnerNode> inner_nodes_;
0082     CollectionBuilder<BIHLeafNode> leaf_nodes_;
0083
0084     //// HELPER FUNCTIONS ////
0085
0086     // Recursively construct BIH nodes for a vector of bbox indices
0087     void construct_tree(VecIndices const& indices,
0088                         VecNodes* nodes,
0089                         BIHNodeId parent);
0090
0091     // Seperate nodes into inner and leaf vectors and renumber accordingly
0092     ArrangedNodes arrange_nodes(VecNodes const& nodes) const;
0093 };
0094
0095 //---------------------------------------------------------------------------//
0096 }  // namespace detail
0097 }  // namespace celeritas