orange/detail/BvhPartitioner.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/BvhPartitioner.hh
0006 //---------------------------------------------------------------------------//
0007 #pragma once
0008
0009 #include <vector>
0010
0011 #include "corecel/cont/EnumArray.hh"
0012 #include "geocel/BoundingBox.hh"  // IWYU pragma: keep
0013
0014 #include "BvhData.hh"
0015 #include "../OrangeTypes.hh"
0016
0017 namespace celeritas
0018 {
0019 namespace detail
0020 {
0021 //---------------------------------------------------------------------------//
0022 /*!
0023  * Partition bounding boxes using a surface area heuristic.
0024  *
0025  * This class takes a vector of bounding boxes as an input, and outputs a
0026  * Partition object describing the optional partition (among those tested). To
0027  * find the optimal partition, candidate partitions along the x, y, and z axes
0028  * are evaluated using a cost function. The cost function is based on a
0029  * surface area heuristic \citep{wald-fastconstruction-2007,
0030  * https://10.1109/RT.2007.4342588}.
0031  */
0032 class BvhPartitioner
0033 {
0034   public:
0035     //!@{
0036     //! \name Type aliases
0037     using Real3 = Array<fast_real_type, 3>;
0038     using VecBBox = std::vector<FastBBox>;
0039     using VecReal3 = std::vector<Real3>;
0040     using VecIndices = std::vector<LocalVolumeId>;
0041     using Side = BvhInternalNode::Side;
0042
0043     //! Output struct specifying the indices and bboxes of the left and right
0044     //! sides of the partition
0045     struct Partition
0046     {
0047         Axis axis = Axis::size_;
0048         fast_real_type position{};
0049
0050         EnumArray<Side, VecIndices> indices;
0051         EnumArray<Side, FastBBox> bboxes;
0052
0053         explicit operator bool() const
0054         {
0055             return axis != Axis::size_ && std::isfinite(position)
0056                    && !indices[Side::left].empty()
0057                    && !indices[Side::right].empty() && bboxes[Side::left]
0058                    && bboxes[Side::right];
0059         }
0060     };
0061     //!@}
0062
0063   public:
0064     // Construct from all bounding bounding boxes in a universe
0065     explicit BvhPartitioner(VecBBox const& bboxes,
0066                             VecReal3 const& centers,
0067                             size_type num_part_cands);
0068
0069     // Find a suitable partition for the given subset of bounding boxes
0070     Partition operator()(VecIndices const& indices) const;
0071
0072   private:
0073     /// TYPES ///
0074     using AxesCenters = std::vector<std::vector<fast_real_type>>;
0075
0076     //// DATA ////
0077
0078     //! All bounding boxes to be partitioned
0079     VecBBox const& bboxes_;
0080     //! The centers of each bounding box
0081     VecReal3 const& centers_;
0082     //! The number of partition candidates to check per axis
0083     size_type num_part_cands_{0};
0084     //! Min num vols to consider discarding partition based on overlap fraction
0085     static constexpr size_type volume_threshold_ = 2;
0086     //! Threshold for discarding partitions that yield overlapping children
0087     static constexpr real_type overlap_threshold_ = real_type{0.5};
0088
0089     //// HELPER FUNCTIONS ////
0090
0091     // Create sorted and uniquified x, y, z values of bbox centers
0092     AxesCenters calc_axes_centers(VecIndices const& indices) const;
0093
0094     // Create a partition object
0095     Partition make_partition(
0096         VecIndices const& indices, Axis axis, real_type position) const;
0097
0098     // Calculate the cost of partition using a surface area heuristic
0099     real_type calc_cost(Partition const& partition) const;
0100 };
0101
0102 //---------------------------------------------------------------------------//
0103 }  // namespace detail
0104 }  // namespace celeritas