orange/detail/BIHEnclosingVolFinder.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/BIHEnclosingVolFinder.hh
0006 //---------------------------------------------------------------------------//
0007 #pragma once
0008
0009 #include "BIHView.hh"
0010
0011 namespace celeritas
0012 {
0013 namespace detail
0014 {
0015 //---------------------------------------------------------------------------//
0016 /*!
0017  * Traverse the BIH tree to find a volume that contains a point.
0018  *
0019  * Traversal is carried out using a depth-first search and terminated as soon
0020  * as a suitable volume is found. When visiting a leaf node, the bounding boxes
0021  * of leaf volumes are tested (inexpensive) before testing the leaf volumes
0022  * themselves (expensive). Determining if the point is enclosed by the volume
0023  * itself is done with a supplied predicate, which can also be used to exclude
0024  * volumes based on more stringent criteria. For example, for surface crossing
0025  * operations, a predicate that excludes the volume a particle is in prior to
0026  * the crossing may be used.
0027  *
0028  * \todo move to top-level orange directory out of detail namespace
0029  */
0030 class BIHEnclosingVolFinder
0031 {
0032   public:
0033     //!@{
0034     //! \name Type aliases
0035     using Storage = NativeCRef<BIHTreeData>;
0036     //!@}
0037
0038     // Construct from vector of bounding boxes and storage for LocalVolumeIds
0039     inline CELER_FUNCTION
0040     BIHEnclosingVolFinder(BIHTree const& tree, Storage const& storage);
0041
0042     // Find a volume that satisfies is_inside
0043     template<class F>
0044     inline CELER_FUNCTION LocalVolumeId operator()(Real3 const& pos,
0045                                                    F&& is_inside) const;
0046
0047   private:
0048     //// DATA ////
0049     BIHView view_;
0050
0051     //// HELPER FUNCTIONS ////
0052
0053     // Get the ID of the next node in the traversal sequence
0054     inline CELER_FUNCTION BIHNodeId next_node(BIHNodeId current_id,
0055                                               BIHNodeId previous_id,
0056                                               Real3 const& pos) const;
0057
0058     // Determine if traversal shall proceed down a given edge
0059     inline CELER_FUNCTION bool visit_edge(BIHInnerNode const& node,
0060                                           BIHInnerNode::Side side,
0061                                           Real3 const& pos) const;
0062
0063     // Determine if any leaf node volumes contain the point
0064     template<class F>
0065     inline CELER_FUNCTION LocalVolumeId visit_leaf(BIHLeafNode const& leaf_node,
0066                                                    Real3 const& pos,
0067                                                    F&& is_inside) const;
0068
0069     // Determine if any inf_vols contain the point
0070     template<class F>
0071     inline CELER_FUNCTION LocalVolumeId visit_inf_vols(F&& is_inside) const;
0072
0073     // Determine if a single bbox contains the point
0074     inline CELER_FUNCTION bool
0075     visit_bbox(LocalVolumeId const& id, Real3 const& pos) const;
0076 };
0077
0078 //---------------------------------------------------------------------------//
0079 // INLINE DEFINITIONS
0080 //---------------------------------------------------------------------------//
0081 /*!
0082  * Construct from vector of bounding boxes and storage.
0083  */
0084 CELER_FUNCTION
0085 BIHEnclosingVolFinder::BIHEnclosingVolFinder(BIHTree const& tree,
0086                                              Storage const& storage)
0087     : view_(tree, storage)
0088 {
0089 }
0090
0091 //---------------------------------------------------------------------------//
0092 /*!
0093  * Find a volume that satisfies is_inside.
0094  */
0095 template<class F>
0096 CELER_FUNCTION LocalVolumeId
0097 BIHEnclosingVolFinder::operator()(Real3 const& pos, F&& is_inside) const
0098 {
0099     BIHNodeId previous_node;
0100     BIHNodeId current_node{0};
0101     LocalVolumeId id;
0102
0103     // Depth-first search
0104     do
0105     {
0106         if (!view_.is_inner(current_node))
0107         {
0108             id = this->visit_leaf(
0109                 view_.leaf_node(current_node), pos, is_inside);
0110
0111             if (id)
0112             {
0113                 return id;
0114             }
0115         }
0116
0117         previous_node = exchange(
0118             current_node, this->next_node(current_node, previous_node, pos));
0119
0120     } while (current_node);
0121
0122     return this->visit_inf_vols(is_inside);
0123 }
0124
0125 //---------------------------------------------------------------------------//
0126 // HELPER FUNCTIONS
0127 //---------------------------------------------------------------------------//
0128 /*!
0129  *  Get the ID of the next node in the traversal sequence.
0130  */
0131 CELER_FUNCTION
0132 BIHNodeId BIHEnclosingVolFinder::next_node(BIHNodeId current_id,
0133                                            BIHNodeId previous_id,
0134                                            Real3 const& pos) const
0135 {
0136     using Side = BIHInnerNode::Side;
0137
0138     BIHNodeId next_id;
0139
0140     if (view_.is_inner(current_id))
0141     {
0142         auto const& current_node = view_.inner_node(current_id);
0143         if (previous_id == current_node.parent)
0144         {
0145             // Visiting this inner node for the first time; go down either left
0146             // or right edge
0147             if (this->visit_edge(current_node, Side::left, pos))
0148             {
0149                 next_id = current_node.edges[Side::left].child;
0150             }
0151             else
0152             {
0153                 next_id = current_node.edges[Side::right].child;
0154             }
0155         }
0156         else if (previous_id == current_node.edges[Side::left].child)
0157         {
0158             // Visiting this inner node for the second time; go down right edge
0159             // or return to parent
0160             if (this->visit_edge(current_node, Side::right, pos))
0161             {
0162                 next_id = current_node.edges[Side::right].child;
0163             }
0164             else
0165             {
0166                 next_id = current_node.parent;
0167             }
0168         }
0169         else
0170         {
0171             // Visiting this inner node for the third time; return to parent
0172             CELER_EXPECT(previous_id == current_node.edges[Side::right].child);
0173             next_id = current_node.parent;
0174         }
0175     }
0176     else
0177     {
0178         // Leaf node; return to parent
0179         CELER_EXPECT(previous_id == view_.leaf_node(current_id).parent);
0180         next_id = previous_id;
0181     }
0182
0183     return next_id;
0184 }
0185
0186 //---------------------------------------------------------------------------//
0187 /*!
0188  * Determine if traversal shall proceed down a given edge.
0189  */
0190 CELER_FUNCTION
0191 bool BIHEnclosingVolFinder::visit_edge(BIHInnerNode const& node,
0192                                        BIHInnerNode::Side side,
0193                                        Real3 const& pos) const
0194 {
0195     CELER_EXPECT(side < BIHInnerNode::Side::size_);
0196
0197     auto bp_pos = node.edges[side].bounding_plane_pos;
0198     auto p = pos[to_int(node.axis)];
0199
0200     return (side == BIHInnerNode::Side::left) ? (p < bp_pos) : (bp_pos < p);
0201 }
0202
0203 //---------------------------------------------------------------------------//
0204 /*!
0205  * Determine if any leaf node volumes contain the point.
0206  */
0207 template<class F>
0208 CELER_FUNCTION LocalVolumeId BIHEnclosingVolFinder::visit_leaf(
0209     BIHLeafNode const& leaf_node, Real3 const& pos, F&& is_inside) const
0210 {
0211     for (auto id : view_.leaf_vol_ids(leaf_node))
0212     {
0213         if (this->visit_bbox(id, pos) && is_inside(id))
0214         {
0215             return id;
0216         }
0217     }
0218     return LocalVolumeId{};
0219 }
0220
0221 //---------------------------------------------------------------------------//
0222 /*!
0223  * Determine if any volumes in inf_vols contain the point.
0224  */
0225 template<class F>
0226 CELER_FUNCTION LocalVolumeId
0227 BIHEnclosingVolFinder::visit_inf_vols(F&& is_inside) const
0228 {
0229     for (auto id : view_.inf_vol_ids())
0230     {
0231         if (is_inside(id))
0232         {
0233             return id;
0234         }
0235     }
0236     return LocalVolumeId{};
0237 }
0238
0239 //---------------------------------------------------------------------------//
0240 /*!
0241  * Determinate if a single bbox contains the point.
0242  */
0243 CELER_FUNCTION
0244 bool BIHEnclosingVolFinder::visit_bbox(LocalVolumeId const& id,
0245                                        Real3 const& point) const
0246 {
0247     return is_inside(view_.bbox(id), point);
0248 }
0249
0250 //---------------------------------------------------------------------------//
0251 }  // namespace detail
0252 }  // namespace celeritas