Point Cloud Library (PCL)  1.8.1
octree_base.h
1 /*
2  * Software License Agreement (BSD License)
3  *
4  * Point Cloud Library (PCL) - www.pointclouds.org
5  * Copyright (c) 2010-2012, Willow Garage, Inc.
6  *
7  * All rights reserved.
8  *
9  * Redistribution and use in source and binary forms, with or without
10  * modification, are permitted provided that the following conditions
11  * are met:
12  *
13  * * Redistributions of source code must retain the above copyright
14  * notice, this list of conditions and the following disclaimer.
15  * * Redistributions in binary form must reproduce the above
16  * copyright notice, this list of conditions and the following
17  * disclaimer in the documentation and/or other materials provided
18  * with the distribution.
19  * * Neither the name of Willow Garage, Inc. nor the names of its
20  * contributors may be used to endorse or promote products derived
21  * from this software without specific prior written permission.
22  *
23  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
24  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
25  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
26  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
27  * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
28  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
29  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
30  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
31  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
32  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
33  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
34  * POSSIBILITY OF SUCH DAMAGE.
35  *
36  * $Id$
37  */
38 
39 #ifndef PCL_OCTREE_TREE_BASE_H
40 #define PCL_OCTREE_TREE_BASE_H
41 
42 #include <vector>
43 
44 #include <pcl/octree/octree_nodes.h>
45 #include <pcl/octree/octree_container.h>
46 #include <pcl/octree/octree_key.h>
47 #include <pcl/octree/octree_iterator.h>
48 
49 namespace pcl
50 {
51  namespace octree
52  {
53  /** \brief Octree class
54  * \note The tree depth defines the maximum amount of octree voxels / leaf nodes (should be initially defined).
55  * \note All leaf nodes are addressed by integer indices.
56  * \note Note: The tree depth equates to the bit length of the voxel indices.
57  * \ingroup octree
58  * \author Julius Kammerl (julius@kammerl.de)
59  */
60  template<typename LeafContainerT = int,
61  typename BranchContainerT = OctreeContainerEmpty >
62  class OctreeBase
63  {
64 
65  public:
66 
68 
71 
72  typedef BranchContainerT BranchContainer;
73  typedef LeafContainerT LeafContainer;
74 
75  // iterators are friends
76  friend class OctreeIteratorBase<OctreeT> ;
77  friend class OctreeDepthFirstIterator<OctreeT> ;
78  friend class OctreeBreadthFirstIterator<OctreeT> ;
79  friend class OctreeLeafNodeIterator<OctreeT> ;
80 
81  // Octree default iterators
84  Iterator begin(unsigned int max_depth_arg = 0) {return Iterator(this, max_depth_arg);};
85  const Iterator end() {return Iterator();};
86 
87  // Octree leaf node iterators
90  LeafNodeIterator leaf_begin(unsigned int max_depth_arg = 0) {return LeafNodeIterator(this, max_depth_arg);};
91  const LeafNodeIterator leaf_end() {return LeafNodeIterator();};
92 
93  // Octree depth-first iterators
96  DepthFirstIterator depth_begin(unsigned int max_depth_arg = 0) {return DepthFirstIterator(this, max_depth_arg);};
97  const DepthFirstIterator depth_end() {return DepthFirstIterator();};
98 
99  // Octree breadth-first iterators
102  BreadthFirstIterator breadth_begin(unsigned int max_depth_arg = 0) {return BreadthFirstIterator(this, max_depth_arg);};
103  const BreadthFirstIterator breadth_end() {return BreadthFirstIterator();};
104 
105 
106  /** \brief Empty constructor. */
107  OctreeBase ();
108 
109  /** \brief Empty deconstructor. */
110  virtual
111  ~OctreeBase ();
112 
113  /** \brief Copy constructor. */
114  OctreeBase (const OctreeBase& source) :
115  leaf_count_ (source.leaf_count_),
116  branch_count_ (source.branch_count_),
117  root_node_ (new (BranchNode) (*(source.root_node_))),
118  depth_mask_ (source.depth_mask_),
119  octree_depth_ (source.octree_depth_),
121  max_key_ (source.max_key_)
122  {
123  }
124 
125  /** \brief Copy operator. */
126  OctreeBase&
127  operator = (const OctreeBase &source)
128  {
129  leaf_count_ = source.leaf_count_;
130  branch_count_ = source.branch_count_;
131  root_node_ = new (BranchNode) (*(source.root_node_));
132  depth_mask_ = source.depth_mask_;
133  max_key_ = source.max_key_;
134  octree_depth_ = source.octree_depth_;
135  return (*this);
136  }
137 
138  /** \brief Set the maximum amount of voxels per dimension.
139  * \param[in] max_voxel_index_arg maximum amount of voxels per dimension
140  */
141  void
142  setMaxVoxelIndex (unsigned int max_voxel_index_arg);
143 
144  /** \brief Set the maximum depth of the octree.
145  * \param max_depth_arg: maximum depth of octree
146  * */
147  void
148  setTreeDepth (unsigned int max_depth_arg);
149 
150  /** \brief Get the maximum depth of the octree.
151  * \return depth_arg: maximum depth of octree
152  * */
153  unsigned int
154  getTreeDepth () const
155  {
156  return this->octree_depth_;
157  }
158 
159  /** \brief Create new leaf node at (idx_x_arg, idx_y_arg, idx_z_arg).
160  * \note If leaf node already exist, this method returns the existing node
161  * \param idx_x_arg: index of leaf node in the X axis.
162  * \param idx_y_arg: index of leaf node in the Y axis.
163  * \param idx_z_arg: index of leaf node in the Z axis.
164  * \return pointer to new leaf node container.
165  * */
166  LeafContainerT*
167  createLeaf (unsigned int idx_x_arg, unsigned int idx_y_arg, unsigned int idx_z_arg);
168 
169  /** \brief Find leaf node at (idx_x_arg, idx_y_arg, idx_z_arg).
170  * \note If leaf node already exist, this method returns the existing node
171  * \param idx_x_arg: index of leaf node in the X axis.
172  * \param idx_y_arg: index of leaf node in the Y axis.
173  * \param idx_z_arg: index of leaf node in the Z axis.
174  * \return pointer to leaf node container if found, null pointer otherwise.
175  * */
176  LeafContainerT*
177  findLeaf (unsigned int idx_x_arg, unsigned int idx_y_arg, unsigned int idx_z_arg);
178 
179  /** \brief idx_x_arg for the existence of leaf node at (idx_x_arg, idx_y_arg, idx_z_arg).
180  * \param idx_x_arg: index of leaf node in the X axis.
181  * \param idx_y_arg: index of leaf node in the Y axis.
182  * \param idx_z_arg: index of leaf node in the Z axis.
183  * \return "true" if leaf node search is successful, otherwise it returns "false".
184  * */
185  bool
186  existLeaf (unsigned int idx_x_arg, unsigned int idx_y_arg, unsigned int idx_z_arg) const ;
187 
188  /** \brief Remove leaf node at (idx_x_arg, idx_y_arg, idx_z_arg).
189  * \param idx_x_arg: index of leaf node in the X axis.
190  * \param idx_y_arg: index of leaf node in the Y axis.
191  * \param idx_z_arg: index of leaf node in the Z axis.
192  * */
193  void
194  removeLeaf (unsigned int idx_x_arg, unsigned int idx_y_arg, unsigned int idx_z_arg);
195 
196  /** \brief Return the amount of existing leafs in the octree.
197  * \return amount of registered leaf nodes.
198  * */
199  std::size_t
200  getLeafCount () const
201  {
202  return leaf_count_;
203  }
204 
205  /** \brief Return the amount of existing branch nodes in the octree.
206  * \return amount of branch nodes.
207  * */
208  std::size_t
209  getBranchCount () const
210  {
211  return branch_count_;
212  }
213 
214  /** \brief Delete the octree structure and its leaf nodes.
215  * */
216  void
217  deleteTree ( );
218 
219  /** \brief Serialize octree into a binary output vector describing its branch node structure.
220  * \param binary_tree_out_arg: reference to output vector for writing binary tree structure.
221  * */
222  void
223  serializeTree (std::vector<char>& binary_tree_out_arg);
224 
225  /** \brief Serialize octree into a binary output vector describing its branch node structure and push all LeafContainerT elements stored in the octree to a vector.
226  * \param binary_tree_out_arg: reference to output vector for writing binary tree structure.
227  * \param leaf_container_vector_arg: pointer to all LeafContainerT objects in the octree
228  * */
229  void
230  serializeTree (std::vector<char>& binary_tree_out_arg, std::vector<LeafContainerT*>& leaf_container_vector_arg);
231 
232  /** \brief Outputs a vector of all LeafContainerT elements that are stored within the octree leaf nodes.
233  * \param leaf_container_vector_arg: pointers to LeafContainerT vector that receives a copy of all LeafContainerT objects in the octree.
234  * */
235  void
236  serializeLeafs (std::vector<LeafContainerT*>& leaf_container_vector_arg);
237 
238  /** \brief Deserialize a binary octree description vector and create a corresponding octree structure. Leaf nodes are initialized with getDataTByKey(..).
239  * \param binary_tree_input_arg: reference to input vector for reading binary tree structure.
240  * */
241  void
242  deserializeTree (std::vector<char>& binary_tree_input_arg);
243 
244  /** \brief Deserialize a binary octree description and create a corresponding octree structure. Leaf nodes are initialized with LeafContainerT elements from the dataVector.
245  * \param binary_tree_input_arg: reference to input vector for reading binary tree structure.
246  * \param leaf_container_vector_arg: pointer to container vector.
247  * */
248  void
249  deserializeTree (std::vector<char>& binary_tree_input_arg, std::vector<LeafContainerT*>& leaf_container_vector_arg);
250 
251  protected:
252 
253  //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
254  // Protected octree methods based on octree keys
255  //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
256 
257  /** \brief Create a leaf node
258  * \param key_arg: octree key addressing a leaf node.
259  * \return pointer to leaf node
260  * */
261  LeafContainerT*
262  createLeaf (const OctreeKey& key_arg)
263  {
264 
265  LeafNode* leaf_node;
266  BranchNode* leaf_node_parent;
267 
268  createLeafRecursive (key_arg, depth_mask_ ,root_node_, leaf_node, leaf_node_parent);
269 
270  LeafContainerT* ret = leaf_node->getContainerPtr();
271 
272  return ret;
273  }
274 
275  /** \brief Find leaf node
276  * \param key_arg: octree key addressing a leaf node.
277  * \return pointer to leaf node. If leaf node is not found, this pointer returns 0.
278  * */
279  LeafContainerT*
280  findLeaf (const OctreeKey& key_arg) const
281  {
282  LeafContainerT* result = 0;
283  findLeafRecursive (key_arg, depth_mask_, root_node_, result);
284  return result;
285  }
286 
287  /** \brief Check for existance of a leaf node in the octree
288  * \param key_arg: octree key addressing a leaf node.
289  * \return "true" if leaf node is found; "false" otherwise
290  * */
291  bool
292  existLeaf (const OctreeKey& key_arg) const
293  {
294  return (findLeaf(key_arg) != 0);
295  }
296 
297  /** \brief Remove leaf node from octree
298  * \param key_arg: octree key addressing a leaf node.
299  * */
300  void
301  removeLeaf (const OctreeKey& key_arg)
302  {
303  if (key_arg <= max_key_)
305  }
306 
307  //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
308  // Branch node access functions
309  //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
310 
311  /** \brief Retrieve root node */
312  OctreeNode*
313  getRootNode () const
314  {
315  return this->root_node_;
316  }
317 
318  /** \brief Check if branch is pointing to a particular child node
319  * \param branch_arg: reference to octree branch class
320  * \param child_idx_arg: index to child node
321  * \return "true" if pointer to child node exists; "false" otherwise
322  * */
323  bool
324  branchHasChild (const BranchNode& branch_arg,
325  unsigned char child_idx_arg) const
326  {
327  // test occupancyByte for child existence
328  return (branch_arg.getChildPtr(child_idx_arg) != 0);
329  }
330 
331  /** \brief Retrieve a child node pointer for child node at child_idx.
332  * \param branch_arg: reference to octree branch class
333  * \param child_idx_arg: index to child node
334  * \return pointer to octree child node class
335  */
336  OctreeNode*
337  getBranchChildPtr (const BranchNode& branch_arg,
338  unsigned char child_idx_arg) const
339  {
340  return branch_arg.getChildPtr(child_idx_arg);
341  }
342 
343  /** \brief Assign new child node to branch
344  * \param branch_arg: reference to octree branch class
345  * \param child_idx_arg: index to child node
346  * \param new_child_arg: pointer to new child node
347  * */
348  void setBranchChildPtr (BranchNode& branch_arg,
349  unsigned char child_idx_arg,
350  OctreeNode* new_child_arg)
351  {
352  branch_arg[child_idx_arg] = new_child_arg;
353  }
354 
355  /** \brief Generate bit pattern reflecting the existence of child node pointers
356  * \param branch_arg: reference to octree branch class
357  * \return a single byte with 8 bits of child node information
358  * */
359  char
360  getBranchBitPattern (const BranchNode& branch_arg) const
361  {
362  unsigned char i;
363  char node_bits;
364 
365  // create bit pattern
366  node_bits = 0;
367  for (i = 0; i < 8; i++) {
368  const OctreeNode* child = branch_arg.getChildPtr(i);
369  node_bits |= static_cast<char> ((!!child) << i);
370  }
371 
372  return (node_bits);
373  }
374 
375  /** \brief Delete child node and all its subchilds from octree
376  * \param branch_arg: reference to octree branch class
377  * \param child_idx_arg: index to child node
378  * */
379  void
380  deleteBranchChild (BranchNode& branch_arg, unsigned char child_idx_arg)
381  {
382  if (branch_arg.hasChild(child_idx_arg))
383  {
384  OctreeNode* branch_child = branch_arg[child_idx_arg];
385 
386  switch (branch_child->getNodeType ())
387  {
388  case BRANCH_NODE:
389  {
390  // free child branch recursively
391  deleteBranch (*static_cast<BranchNode*> (branch_child));
392  // delete branch node
393  delete branch_child;
394  }
395  break;
396 
397  case LEAF_NODE:
398  {
399  // delete leaf node
400  delete branch_child;
401  break;
402  }
403  default:
404  break;
405  }
406 
407  // set branch child pointer to 0
408  branch_arg[child_idx_arg] = 0;
409  }
410  }
411 
412  /** \brief Delete branch and all its subchilds from octree
413  * \param branch_arg: reference to octree branch class
414  * */
415  void
416  deleteBranch (BranchNode& branch_arg)
417  {
418  char i;
419 
420  // delete all branch node children
421  for (i = 0; i < 8; i++)
422  deleteBranchChild (branch_arg, i);
423  }
424 
425  /** \brief Create and add a new branch child to a branch class
426  * \param branch_arg: reference to octree branch class
427  * \param child_idx_arg: index to child node
428  * \return pointer of new branch child to this reference
429  * */
430  BranchNode* createBranchChild (BranchNode& branch_arg,
431  unsigned char child_idx_arg)
432  {
433  BranchNode* new_branch_child = new BranchNode();
434  branch_arg[child_idx_arg] = static_cast<OctreeNode*> (new_branch_child);
435 
436  return new_branch_child;
437  }
438 
439  /** \brief Create and add a new leaf child to a branch class
440  * \param branch_arg: reference to octree branch class
441  * \param child_idx_arg: index to child node
442  * \return pointer of new leaf child to this reference
443  * */
444  LeafNode*
445  createLeafChild (BranchNode& branch_arg, unsigned char child_idx_arg)
446  {
447  LeafNode* new_leaf_child = new LeafNode();
448  branch_arg[child_idx_arg] = static_cast<OctreeNode*> (new_leaf_child);
449 
450  return new_leaf_child;
451  }
452 
453  //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
454  // Recursive octree methods
455  //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
456 
457  /** \brief Create a leaf node at octree key. If leaf node does already exist, it is returned.
458  * \param key_arg: reference to an octree key
459  * \param depth_mask_arg: depth mask used for octree key analysis and for branch depth indicator
460  * \param branch_arg: current branch node
461  * \param return_leaf_arg: return pointer to leaf node
462  * \param parent_of_leaf_arg: return pointer to parent of leaf node
463  * \return depth mask at which leaf node was created
464  **/
465  unsigned int
466  createLeafRecursive (const OctreeKey& key_arg,
467  unsigned int depth_mask_arg,
468  BranchNode* branch_arg,
469  LeafNode*& return_leaf_arg,
470  BranchNode*& parent_of_leaf_arg);
471 
472  /** \brief Recursively search for a given leaf node and return a pointer.
473  * \note If leaf node does not exist, a 0 pointer is returned.
474  * \param key_arg: reference to an octree key
475  * \param depth_mask_arg: depth mask used for octree key analysis and for branch depth indicator
476  * \param branch_arg: current branch node
477  * \param result_arg: pointer to leaf node class
478  **/
479  void
480  findLeafRecursive (const OctreeKey& key_arg,
481  unsigned int depth_mask_arg,
482  BranchNode* branch_arg,
483  LeafContainerT*& result_arg) const;
484 
485  /** \brief Recursively search and delete leaf node
486  * \param key_arg: reference to an octree key
487  * \param depth_mask_arg: depth mask used for octree key analysis and branch depth indicator
488  * \param branch_arg: current branch node
489  * \return "true" if branch does not contain any childs; "false" otherwise. This indicates if current branch can be deleted, too.
490  **/
491  bool
492  deleteLeafRecursive (const OctreeKey& key_arg,
493  unsigned int depth_mask_arg,
494  BranchNode* branch_arg);
495 
496  /** \brief Recursively explore the octree and output binary octree description together with a vector of leaf node LeafContainerTs.
497  * \param branch_arg: current branch node
498  * \param key_arg: reference to an octree key
499  * \param binary_tree_out_arg: binary output vector
500  * \param leaf_container_vector_arg: writes LeafContainerT pointers to this LeafContainerT* vector.
501  **/
502  void
503  serializeTreeRecursive (const BranchNode* branch_arg,
504  OctreeKey& key_arg,
505  std::vector<char>* binary_tree_out_arg,
506  typename std::vector<LeafContainerT*>* leaf_container_vector_arg) const;
507 
508  /** \brief Recursive method for deserializing octree structure
509  * \param branch_arg: current branch node
510  * \param depth_mask_arg: depth mask used for octree key analysis and branch depth indicator
511  * \param key_arg: reference to an octree key
512  * \param binary_tree_input_it_arg: iterator to binary input vector
513  * \param binary_tree_input_it_end_arg: end iterator of binary input vector
514  * \param leaf_container_vector_it_arg: iterator pointing to current LeafContainerT object to be added to a leaf node
515  * \param leaf_container_vector_it_end_arg: iterator pointing to last object in LeafContainerT input vector.
516  **/
517  void
518  deserializeTreeRecursive (BranchNode* branch_arg, unsigned int depth_mask_arg, OctreeKey& key_arg,
519  typename std::vector<char>::const_iterator& binary_tree_input_it_arg,
520  typename std::vector<char>::const_iterator& binary_tree_input_it_end_arg,
521  typename std::vector<LeafContainerT*>::const_iterator* leaf_container_vector_it_arg,
522  typename std::vector<LeafContainerT*>::const_iterator* leaf_container_vector_it_end_arg);
523 
524 
525  //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
526  // Serialization callbacks
527  //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
528 
529  /** \brief Callback executed for every leaf node during serialization
530  **/
531  virtual void
532  serializeTreeCallback (LeafContainerT&, const OctreeKey &) const
533  {
534 
535  }
536 
537  /** \brief Callback executed for every leaf node during deserialization
538  **/
539  virtual void
540  deserializeTreeCallback (LeafContainerT&, const OctreeKey&)
541  {
542 
543  }
544 
545  //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
546  // Helpers
547  //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
548 
549  /** \brief Helper function to calculate the binary logarithm
550  * \param n_arg: some value
551  * \return binary logarithm (log2) of argument n_arg
552  */
553  double
554  Log2 (double n_arg)
555  {
556  return log( n_arg ) / log( 2.0 );
557  }
558 
559  /** \brief Test if octree is able to dynamically change its depth. This is required for adaptive bounding box adjustment.
560  * \return "true"
561  **/
562  bool
564  {
565  return (true);
566  }
567 
568  //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
569  // Globals
570  //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
571 
572  /** \brief Amount of leaf nodes **/
573  std::size_t leaf_count_;
574 
575  /** \brief Amount of branch nodes **/
576  std::size_t branch_count_;
577 
578  /** \brief Pointer to root branch node of octree **/
579  BranchNode* root_node_;
580 
581  /** \brief Depth mask based on octree depth **/
582  unsigned int depth_mask_;
583 
584  /** \brief Octree depth */
585  unsigned int octree_depth_;
586 
587  /** \brief Enable dynamic_depth **/
589 
590  /** \brief key range */
592  };
593  }
594 }
595 
596 #ifdef PCL_NO_PRECOMPILE
597 #include <pcl/octree/impl/octree_base.hpp>
598 #endif
599 
600 #endif
601 
bool hasChild(unsigned char child_idx_arg) const
Check if branch is pointing to a particular child node.
Definition: octree_nodes.h:292
LeafContainerT * createLeaf(unsigned int idx_x_arg, unsigned int idx_y_arg, unsigned int idx_z_arg)
Create new leaf node at (idx_x_arg, idx_y_arg, idx_z_arg).
const DepthFirstIterator depth_end()
Definition: octree_base.h:97
OctreeBreadthFirstIterator< OctreeT > BreadthFirstIterator
Definition: octree_base.h:97
void deleteTree()
Delete the octree structure and its leaf nodes.
const OctreeLeafNodeIterator< OctreeT > ConstLeafNodeIterator
Definition: octree_base.h:89
void setMaxVoxelIndex(unsigned int max_voxel_index_arg)
Set the maximum amount of voxels per dimension.
Definition: octree_base.hpp:75
void serializeTreeRecursive(const BranchNode *branch_arg, OctreeKey &key_arg, std::vector< char > *binary_tree_out_arg, typename std::vector< LeafContainerT *> *leaf_container_vector_arg) const
Recursively explore the octree and output binary octree description together with a vector of leaf no...
Octree class.
Definition: octree_base.h:62
void deserializeTree(std::vector< char > &binary_tree_input_arg)
Deserialize a binary octree description vector and create a corresponding octree structure.
void deserializeTreeRecursive(BranchNode *branch_arg, unsigned int depth_mask_arg, OctreeKey &key_arg, typename std::vector< char >::const_iterator &binary_tree_input_it_arg, typename std::vector< char >::const_iterator &binary_tree_input_it_end_arg, typename std::vector< LeafContainerT *>::const_iterator *leaf_container_vector_it_arg, typename std::vector< LeafContainerT *>::const_iterator *leaf_container_vector_it_end_arg)
Recursive method for deserializing octree structure.
void serializeLeafs(std::vector< LeafContainerT *> &leaf_container_vector_arg)
Outputs a vector of all LeafContainerT elements that are stored within the octree leaf nodes...
bool branchHasChild(const BranchNode &branch_arg, unsigned char child_idx_arg) const
Check if branch is pointing to a particular child node.
Definition: octree_base.h:324
BreadthFirstIterator breadth_begin(unsigned int max_depth_arg=0)
Definition: octree_base.h:102
bool deleteLeafRecursive(const OctreeKey &key_arg, unsigned int depth_mask_arg, BranchNode *branch_arg)
Recursively search and delete leaf node.
virtual node_type_t getNodeType() const =0
Pure virtual method for receiving the type of octree node (branch or leaf)
virtual ~OctreeBase()
Empty deconstructor.
Definition: octree_base.hpp:65
Iterator begin(unsigned int max_depth_arg=0)
Definition: octree_base.h:84
void deleteBranch(BranchNode &branch_arg)
Delete branch and all its subchilds from octree.
Definition: octree_base.h:416
BranchContainerT BranchContainer
Definition: octree_base.h:72
OctreeBase & operator=(const OctreeBase &source)
Copy operator.
Definition: octree_base.h:127
void setTreeDepth(unsigned int max_depth_arg)
Set the maximum depth of the octree.
Definition: octree_base.hpp:91
OctreeNode * getChildPtr(unsigned char child_idx_arg) const
Get pointer to child.
Definition: octree_nodes.h:272
OctreeBase()
Empty constructor.
Definition: octree_base.hpp:52
OctreeBase(const OctreeBase &source)
Copy constructor.
Definition: octree_base.h:114
LeafNode * createLeafChild(BranchNode &branch_arg, unsigned char child_idx_arg)
Create and add a new leaf child to a branch class.
Definition: octree_base.h:445
bool existLeaf(unsigned int idx_x_arg, unsigned int idx_y_arg, unsigned int idx_z_arg) const
idx_x_arg for the existence of leaf node at (idx_x_arg, idx_y_arg, idx_z_arg).
unsigned int octree_depth_
Octree depth.
Definition: octree_base.h:585
Octree leaf node iterator class.
LeafContainerT * findLeaf(const OctreeKey &key_arg) const
Find leaf node.
Definition: octree_base.h:280
const OctreeBreadthFirstIterator< OctreeT > ConstBreadthFirstIterator
Definition: octree_base.h:101
unsigned int createLeafRecursive(const OctreeKey &key_arg, unsigned int depth_mask_arg, BranchNode *branch_arg, LeafNode *&return_leaf_arg, BranchNode *&parent_of_leaf_arg)
Create a leaf node at octree key.
void serializeTree(std::vector< char > &binary_tree_out_arg)
Serialize octree into a binary output vector describing its branch node structure.
void removeLeaf(unsigned int idx_x_arg, unsigned int idx_y_arg, unsigned int idx_z_arg)
Remove leaf node at (idx_x_arg, idx_y_arg, idx_z_arg).
LeafNodeIterator leaf_begin(unsigned int max_depth_arg=0)
Definition: octree_base.h:90
OctreeLeafNodeIterator< OctreeT > LeafNodeIterator
Definition: octree_base.h:85
OctreeBase< LeafContainerT, BranchContainerT > OctreeT
Definition: octree_base.h:67
BranchNode * createBranchChild(BranchNode &branch_arg, unsigned char child_idx_arg)
Create and add a new branch child to a branch class.
Definition: octree_base.h:430
OctreeKey max_key_
key range
Definition: octree_base.h:591
const Iterator end()
Definition: octree_base.h:85
bool octreeCanResize()
Test if octree is able to dynamically change its depth.
Definition: octree_base.h:563
OctreeBranchNode< BranchContainerT > BranchNode
Definition: octree_base.h:69
virtual void serializeTreeCallback(LeafContainerT &, const OctreeKey &) const
Callback executed for every leaf node during serialization.
Definition: octree_base.h:532
BranchNode * root_node_
Pointer to root branch node of octree.
Definition: octree_base.h:579
OctreeNode * getRootNode() const
Retrieve root node.
Definition: octree_base.h:313
OctreeDepthFirstIterator< OctreeT > DepthFirstIterator
Definition: octree_base.h:91
LeafContainerT * findLeaf(unsigned int idx_x_arg, unsigned int idx_y_arg, unsigned int idx_z_arg)
Find leaf node at (idx_x_arg, idx_y_arg, idx_z_arg).
std::size_t getLeafCount() const
Return the amount of existing leafs in the octree.
Definition: octree_base.h:200
void removeLeaf(const OctreeKey &key_arg)
Remove leaf node from octree.
Definition: octree_base.h:301
virtual void deserializeTreeCallback(LeafContainerT &, const OctreeKey &)
Callback executed for every leaf node during deserialization.
Definition: octree_base.h:540
bool dynamic_depth_enabled_
Enable dynamic_depth.
Definition: octree_base.h:588
LeafContainerT LeafContainer
Definition: octree_base.h:73
LeafContainerT * createLeaf(const OctreeKey &key_arg)
Create a leaf node.
Definition: octree_base.h:262
Octree key class
Definition: octree_key.h:51
unsigned int getTreeDepth() const
Get the maximum depth of the octree.
Definition: octree_base.h:154
Abstract octree leaf class
Definition: octree_nodes.h:97
OctreeLeafNode< LeafContainerT > LeafNode
Definition: octree_base.h:70
char getBranchBitPattern(const BranchNode &branch_arg) const
Generate bit pattern reflecting the existence of child node pointers.
Definition: octree_base.h:360
void findLeafRecursive(const OctreeKey &key_arg, unsigned int depth_mask_arg, BranchNode *branch_arg, LeafContainerT *&result_arg) const
Recursively search for a given leaf node and return a pointer.
const LeafNodeIterator leaf_end()
Definition: octree_base.h:91
void setBranchChildPtr(BranchNode &branch_arg, unsigned char child_idx_arg, OctreeNode *new_child_arg)
Assign new child node to branch.
Definition: octree_base.h:348
const ContainerT * getContainerPtr() const
Get const pointer to container.
Definition: octree_nodes.h:178
Abstract octree iterator class
bool existLeaf(const OctreeKey &key_arg) const
Check for existance of a leaf node in the octree.
Definition: octree_base.h:292
const OctreeDepthFirstIterator< OctreeT > ConstIterator
Definition: octree_base.h:83
const OctreeDepthFirstIterator< OctreeT > ConstDepthFirstIterator
Definition: octree_base.h:95
Abstract octree branch class
Definition: octree_nodes.h:204
std::size_t leaf_count_
Amount of leaf nodes.
Definition: octree_base.h:573
const BreadthFirstIterator breadth_end()
Definition: octree_base.h:103
Abstract octree node class
Definition: octree_nodes.h:68
DepthFirstIterator depth_begin(unsigned int max_depth_arg=0)
Definition: octree_base.h:96
std::size_t getBranchCount() const
Return the amount of existing branch nodes in the octree.
Definition: octree_base.h:209
unsigned int depth_mask_
Depth mask based on octree depth.
Definition: octree_base.h:582
double Log2(double n_arg)
Helper function to calculate the binary logarithm.
Definition: octree_base.h:554
OctreeDepthFirstIterator< OctreeT > Iterator
Definition: octree_base.h:82
std::size_t branch_count_
Amount of branch nodes.
Definition: octree_base.h:576
OctreeNode * getBranchChildPtr(const BranchNode &branch_arg, unsigned char child_idx_arg) const
Retrieve a child node pointer for child node at child_idx.
Definition: octree_base.h:337
void deleteBranchChild(BranchNode &branch_arg, unsigned char child_idx_arg)
Delete child node and all its subchilds from octree.
Definition: octree_base.h:380