orange/detail/BIHPartitioner.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/BIHPartitioner.hh
0006 //---------------------------------------------------------------------------//
0007 #pragma once
0008
0009 #include <vector>
0010
0011 #include "corecel/cont/EnumArray.hh"
0012 #include "geocel/BoundingBox.hh"
0013
0014 #include "../OrangeData.hh"
0015
0016 namespace celeritas
0017 {
0018 namespace detail
0019 {
0020 //---------------------------------------------------------------------------//
0021 /*!
0022  * Partition bounding boxes using a surface area heuristic.
0023  *
0024  * The class take a vector of bounding boxes as an input, and outputs a
0025  * Partition object describing the optional partition. To find the optimal
0026  * partition, all possible candidate partitions along the x, y, and z axis are
0027  * evaluated using a cost function. The cost function is based on a standard
0028  * surface area heuristic.
0029  */
0030 class BIHPartitioner
0031 {
0032   public:
0033     //!@{
0034     //! \name Type aliases
0035     using Real3 = Array<fast_real_type, 3>;
0036     using VecBBox = std::vector<FastBBox>;
0037     using VecReal3 = std::vector<Real3>;
0038     using VecIndices = std::vector<LocalVolumeId>;
0039     using Side = BIHInnerNode::Side;
0040
0041     struct Partition
0042     {
0043         Axis axis = Axis::size_;
0044         real_type position = std::numeric_limits<real_type>::infinity();
0045
0046         EnumArray<Side, VecIndices> indices;
0047         EnumArray<Side, FastBBox> bboxes;
0048
0049         explicit operator bool() const
0050         {
0051             return axis != Axis::size_ && std::isfinite(position)
0052                    && !indices[Side::left].empty()
0053                    && !indices[Side::right].empty() && bboxes[Side::left]
0054                    && bboxes[Side::right];
0055         }
0056     };
0057
0058     //!@}
0059
0060   public:
0061     //! Default constructor
0062     BIHPartitioner() = default;
0063
0064     // Construct from vector of bounding boxes and respective centers.
0065     explicit BIHPartitioner(VecBBox const* bboxes, VecReal3 const* centers);
0066
0067     explicit inline operator bool() const
0068     {
0069         return bboxes_ != nullptr && centers_ != nullptr;
0070     }
0071
0072     // Find a suitable partition for the given bounding boxes
0073     Partition operator()(VecIndices const& indicies) const;
0074
0075   private:
0076     /// TYPES ///
0077     using AxesCenters = std::vector<std::vector<real_type>>;
0078
0079     //// DATA ////
0080     VecBBox const* bboxes_{nullptr};
0081     VecReal3 const* centers_{nullptr};
0082     static constexpr size_type candidates_per_axis_{3};
0083
0084     //// HELPER FUNCTIONS ////
0085
0086     // Create sorted and uniquified X, Y, Z values of bbox centers
0087     AxesCenters calc_axes_centers(VecIndices const& indices) const;
0088
0089     // Create a partition object
0090     Partition make_partition(VecIndices const& indices,
0091                              Axis axis,
0092                              real_type position) const;
0093
0094     // Calculate the cost of partition using a surface area heuristic
0095     real_type calc_cost(Partition const& partition) const;
0096 };
0097
0098 //---------------------------------------------------------------------------//
0099 }  // namespace detail
0100 }  // namespace celeritas