1 // Copyright (c) 2017-2021, Lawrence Livermore National Security, LLC and 2 // other Axom Project Developers. See the top-level LICENSE file for details. 3 // 4 // SPDX-License-Identifier: (BSD-3-Clause) 5 6 #ifndef AXOM_SPIN_RADIXTREE_HPP_ 7 #define AXOM_SPIN_RADIXTREE_HPP_ 8 9 #include "axom/core/memory_management.hpp" 10 11 #include "axom/core/utilities/AnnotationMacros.hpp" // for annotations 12 13 #include "axom/primal/geometry/BoundingBox.hpp" 14 15 namespace axom 16 { 17 namespace spin 18 { 19 namespace internal 20 { 21 namespace linear_bvh 22 { 23 /*! 24 * \brief RadixTree provides a binary radix tree representation that stores a 25 * list of axis-aligned bounding boxes sorted according to their Morton code. 26 * 27 * \note This data-structure provides an intermediate representation that serves 28 * as the building-block to construct a BVH in parallel. 29 */ 30 template <typename FloatType, int NDIMS> 31 struct RadixTree 32 { 33 using BoxType = primal::BoundingBox<FloatType, NDIMS>; 34 35 int32 m_size; 36 int32 m_inner_size; 37 38 int32* m_left_children; 39 int32* m_right_children; 40 int32* m_parents; 41 BoxType* m_inner_aabbs; 42 43 int32* m_leafs; 44 uint32* m_mcodes; 45 BoxType* m_leaf_aabbs; 46 allocateaxom::spin::internal::linear_bvh::RadixTree47 void allocate(int32 size, int allocID) 48 { 49 AXOM_PERF_MARK_FUNCTION("RadixTree::allocate"); 50 51 m_size = size; 52 m_inner_size = m_size - 1; 53 54 m_left_children = axom::allocate<int32>(m_inner_size, allocID); 55 m_right_children = axom::allocate<int32>(m_inner_size, allocID); 56 m_parents = axom::allocate<int32>((m_size + m_inner_size), allocID); 57 m_inner_aabbs = axom::allocate<BoxType>(m_inner_size, allocID); 58 59 m_leafs = axom::allocate<int32>(m_size, allocID); 60 m_mcodes = axom::allocate<uint32>(m_size, allocID); 61 m_leaf_aabbs = axom::allocate<BoxType>(m_size, allocID); 62 } 63 deallocateaxom::spin::internal::linear_bvh::RadixTree64 void deallocate() 65 { 66 AXOM_PERF_MARK_FUNCTION("RadixTree::deallocate"); 67 68 m_inner_size = 0; 69 m_size = 0; 70 71 axom::deallocate(m_left_children); 72 axom::deallocate(m_right_children); 73 axom::deallocate(m_parents); 74 axom::deallocate(m_inner_aabbs); 75 76 axom::deallocate(m_leafs); 77 axom::deallocate(m_mcodes); 78 axom::deallocate(m_leaf_aabbs); 79 } 80 }; 81 82 } /* namespace linear_bvh */ 83 } /* namespace internal */ 84 } /* namespace spin */ 85 } /* namespace axom */ 86 87 #endif /* AXOM_RADIXTREE_HPP_ */ 88