1 // This is brl/bseg/boct/boct_bit_tree.h 2 #ifndef boct_bit_tree_h_ 3 #define boct_bit_tree_h_ 4 //: 5 // \file 6 // \brief Test octree implementation using an implicit bit-array to denote tree 7 // structure. 8 // Data structure is currently float 16. 9 // 10 // \author Andrew Miller 11 // \date August 11, 2010 12 // \verbatim 13 // Modifications 14 // <none yet> 15 // \endverbatim 16 17 #include <bitset> 18 #include <cmath> 19 #include <iosfwd> 20 #include <iostream> 21 #include <vector> 22 #include <vgl/vgl_box_3d.h> 23 #include <vgl/vgl_point_3d.h> 24 #include <vnl/vnl_vector_fixed.h> 25 26 class boct_bit_tree { 27 public: 28 typedef vnl_vector_fixed<unsigned char, 16> uchar16; 29 30 // These constructor are owning 31 //: default constructor boct_bit_tree()32 boct_bit_tree() 33 : is_owning_(true), bits_(new unsigned char[16]()), num_levels_(4) {} 34 boct_bit_tree(const unsigned char *bits, int num_levels = 4); 35 // Copy constructor -- copies ownership type as well, and if other is owning, 36 // then creates and owns a copy of the data. 37 boct_bit_tree(const boct_bit_tree &other); 38 // non-owning constructors 39 boct_bit_tree(unsigned char *bits, int num_levels = 4) is_owning_(false)40 : is_owning_(false), bits_(bits), num_levels_(num_levels) {} 41 boct_bit_tree(uchar16 &bits, int num_levels = 4) is_owning_(false)42 : is_owning_(false) 43 , bits_(reinterpret_cast<unsigned char *>(&bits)) 44 , num_levels_(num_levels) {} 45 //: constructor with all parameters 46 // This creates a tree that wraps, and optionally owns, the bits pointed to. boct_bit_tree(unsigned char * bits,bool is_owning,int num_levels)47 boct_bit_tree(unsigned char *bits, bool is_owning, int num_levels) 48 : is_owning_(is_owning), bits_(bits), num_levels_(num_levels) {} 49 50 //: Destructor ~boct_bit_tree()51 ~boct_bit_tree() { 52 if (is_owning_ && bits_) { 53 delete[] bits_; 54 bits_ = nullptr; 55 } 56 } 57 58 // Copy assignment operator 59 boct_bit_tree &operator=(boct_bit_tree that); 60 61 //: Returns index of data for given bit 62 int get_data_index(int bit_index, bool is_random = false) const; 63 64 //: returns bit index assuming root data is located at 0 65 int get_relative_index(int bit_index) const; 66 67 //: traverse tree to get leaf index that contains point. If full is 68 // true, this ignored whether bits are refined or not and just goes 69 // down to the lowest level. 70 int traverse(const vgl_point_3d<double> p, 71 int deepest = 4, 72 bool full = false); 73 74 //: traverse tree to get leaf index that contains point 75 int traverse_to_level(const vgl_point_3d<double> p, int deepest = 4); 76 77 //: gets the cell center (octree is assumed to be [0,1]x[0,1]x[0,1] 78 vgl_point_3d<double> cell_center(int bit_index); 79 80 //: gets the cell bounding box (octree is assumed to be [0,1]x[0,1]x[0,1] 81 vgl_box_3d<double> 82 cell_box(int bit_index, 83 vgl_point_3d<double> orig = vgl_point_3d<double>(0, 0, 0), 84 double len = 1.0); 85 86 //: returns octree cell length on one side (assumed [0,1]^3) 87 double cell_len(int bit_index) const; 88 89 //: tells you if a valid cell is at bit_index (if and only if its parent is 1) 90 bool valid_cell(int bit_index) const; 91 92 //: tells you if the bit_index is a leaf 93 bool is_leaf(int bit_index) const; 94 95 //: Return the maximum number of levels, which is root_level+1 number_levels()96 unsigned short number_levels() const { return num_levels_; } 97 98 //: Return number of cells in this tree 99 int num_cells() const; 100 101 // returns the number of leaf cells 102 int num_leaves() const; 103 104 //: return maximum number of cells in this tree 105 int max_num_cells(); 106 int max_num_inner_cells(); 107 108 //: returns depth (0,1,2,3) at given index 109 // Note that cumulative nodes = (1/7) * (8^(n+1) -1) 110 int depth_at(int index) const; 111 112 //: returns depth of tree 113 int depth(); 114 115 //: returns value (0 or 1) of bit at given index (0,73); 116 unsigned char bit_at(int index) const; 117 118 //: sets bit at given index with bool value 119 void set_bit_at(int index, bool val); 120 121 // Sets the bit at the given index to 'true', and also set every 122 // parent bit to true. If index <0, does nothing. 123 void set_bit_and_parents_to_true(int index); 124 125 // get bits and data get_bits()126 unsigned char *get_bits() { return bits_; } get_bits()127 const unsigned char *get_bits() const { return bits_; } 128 129 //: gets pointers stored in bits 10, 11, 12, 13 130 int get_data_ptr(bool is_random = false); 131 132 //: sets pointers stored in bits 10, 11, 12, 13 133 void set_data_ptr(int ptr, bool is_random = false); 134 135 //: returns bit indices of leaf nodes under rootBit 136 std::vector<int> get_leaf_bits(int rootBit = 0) const; 137 std::vector<int> get_leaf_bits(int rootBit, int depth) const; 138 139 //: returns bit indices of every node under rootBit 140 std::vector<int> get_cell_bits(int rootBit = 0) const; 141 142 //: returns parent index (invalid for bit_index = 0) parent_index(int bit_index)143 int parent_index(int bit_index) { return (bit_index - 1) >> 3; } 144 145 //: returns bit index of first child child_index(int bit_index)146 int child_index(int bit_index) { return (bit_index << 3) + 1; } 147 148 //: wrap a const reference in a const, non-owning bit tree. 149 static const boct_bit_tree wrap_const(const uchar16 &data, int num_levels = 4); 150 151 //: Compares structure bits of the two trees same_structure(const boct_bit_tree & t1,const boct_bit_tree & t2)152 static bool same_structure(const boct_bit_tree &t1, const boct_bit_tree &t2) { 153 return std::memcmp(t1.get_bits(), t2.get_bits(), 10) == 0; 154 } 155 156 // cached arrays are public - make em const too 157 static unsigned char bit_lookup[256]; 158 static float centerX[585]; 159 static float centerY[585]; 160 static float centerZ[585]; 161 162 private: 163 // Whether this tree owns the underlying buffer and should delete it on 164 // destruction. 165 bool is_owning_; 166 //: Tree structure stored as "bits" = really a char array 167 unsigned char *bits_; 168 //: Maximum number of levels in the octree 169 unsigned short num_levels_; 170 }; 171 172 std::ostream &operator<<(std::ostream &s, const boct_bit_tree &t); 173 174 #endif // boct_bit_tree_h_ 175