Point Cloud Library (PCL)  1.8.1-dev
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  public:
65 
67 
70 
71  typedef BranchContainerT BranchContainer;
72  typedef LeafContainerT LeafContainer;
73 
74  protected:
75 
76  ///////////////////////////////////////////////////////////////////////
77  // Members
78  ///////////////////////////////////////////////////////////////////////
79 
80  /** \brief Amount of leaf nodes **/
81  std::size_t leaf_count_;
82 
83  /** \brief Amount of branch nodes **/
84  std::size_t branch_count_;
85 
86  /** \brief Pointer to root branch node of octree **/
88 
89  /** \brief Depth mask based on octree depth **/
90  unsigned int depth_mask_;
91 
92  /** \brief Octree depth */
93  unsigned int octree_depth_;
94 
95  /** \brief Enable dynamic_depth **/
97 
98  /** \brief key range */
100 
101  public:
102 
103  // iterators are friends
104  friend class OctreeIteratorBase<OctreeT> ;
108 
109  // Octree default iterators
112 
113  Iterator begin (unsigned int max_depth_arg = 0u)
114  {
115  return Iterator (this, max_depth_arg? max_depth_arg : this->octree_depth_);
116  };
117 
118  const Iterator end ()
119  {
120  return Iterator (this, 0, NULL);
121  };
122 
123  // Octree leaf node iterators
126 
127  LeafNodeIterator leaf_begin (unsigned int max_depth_arg = 0u)
128  {
129  return LeafNodeIterator (this, max_depth_arg? max_depth_arg : this->octree_depth_);
130  };
131 
133  {
134  return LeafNodeIterator (this, 0, NULL);
135  };
136 
137  // Octree depth-first iterators
140 
141  DepthFirstIterator depth_begin (unsigned int max_depth_arg = 0u)
142  {
143  return DepthFirstIterator (this, max_depth_arg? max_depth_arg : this->octree_depth_);
144  };
145 
147  {
148  return DepthFirstIterator (this, 0, NULL);
149  };
150 
151  // Octree breadth-first iterators
154 
155  BreadthFirstIterator breadth_begin (unsigned int max_depth_arg = 0u)
156  {
157  return BreadthFirstIterator (this, max_depth_arg? max_depth_arg : this->octree_depth_);
158  };
159 
161  {
162  return BreadthFirstIterator (this, 0, NULL);
163  };
164 
165 
166  /** \brief Empty constructor. */
167  OctreeBase ();
168 
169  /** \brief Empty deconstructor. */
170  virtual
171  ~OctreeBase ();
172 
173  /** \brief Copy constructor. */
174  OctreeBase (const OctreeBase& source) :
175  leaf_count_ (source.leaf_count_),
176  branch_count_ (source.branch_count_),
177  root_node_ (new (BranchNode) (*(source.root_node_))),
178  depth_mask_ (source.depth_mask_),
179  octree_depth_ (source.octree_depth_),
181  max_key_ (source.max_key_)
182  {
183  }
184 
185  /** \brief Copy operator. */
186  OctreeBase&
187  operator = (const OctreeBase &source)
188  {
189  leaf_count_ = source.leaf_count_;
190  branch_count_ = source.branch_count_;
191  root_node_ = new (BranchNode) (*(source.root_node_));
192  depth_mask_ = source.depth_mask_;
193  max_key_ = source.max_key_;
194  octree_depth_ = source.octree_depth_;
195  return (*this);
196  }
197 
198  /** \brief Set the maximum amount of voxels per dimension.
199  * \param[in] max_voxel_index_arg maximum amount of voxels per dimension
200  */
201  void
202  setMaxVoxelIndex (unsigned int max_voxel_index_arg);
203 
204  /** \brief Set the maximum depth of the octree.
205  * \param max_depth_arg: maximum depth of octree
206  * */
207  void
208  setTreeDepth (unsigned int max_depth_arg);
209 
210  /** \brief Get the maximum depth of the octree.
211  * \return depth_arg: maximum depth of octree
212  * */
213  unsigned int
214  getTreeDepth () const
215  {
216  return this->octree_depth_;
217  }
218 
219  /** \brief Create new leaf node at (idx_x_arg, idx_y_arg, idx_z_arg).
220  * \note If leaf node already exist, this method returns the existing node
221  * \param idx_x_arg: index of leaf node in the X axis.
222  * \param idx_y_arg: index of leaf node in the Y axis.
223  * \param idx_z_arg: index of leaf node in the Z axis.
224  * \return pointer to new leaf node container.
225  * */
226  LeafContainerT*
227  createLeaf (unsigned int idx_x_arg, unsigned int idx_y_arg, unsigned int idx_z_arg);
228 
229  /** \brief Find leaf node at (idx_x_arg, idx_y_arg, idx_z_arg).
230  * \note If leaf node already exist, this method returns the existing node
231  * \param idx_x_arg: index of leaf node in the X axis.
232  * \param idx_y_arg: index of leaf node in the Y axis.
233  * \param idx_z_arg: index of leaf node in the Z axis.
234  * \return pointer to leaf node container if found, null pointer otherwise.
235  * */
236  LeafContainerT*
237  findLeaf (unsigned int idx_x_arg, unsigned int idx_y_arg, unsigned int idx_z_arg);
238 
239  /** \brief idx_x_arg for the existence of leaf node at (idx_x_arg, idx_y_arg, idx_z_arg).
240  * \param idx_x_arg: index of leaf node in the X axis.
241  * \param idx_y_arg: index of leaf node in the Y axis.
242  * \param idx_z_arg: index of leaf node in the Z axis.
243  * \return "true" if leaf node search is successful, otherwise it returns "false".
244  * */
245  bool
246  existLeaf (unsigned int idx_x_arg, unsigned int idx_y_arg, unsigned int idx_z_arg) const ;
247 
248  /** \brief Remove leaf node at (idx_x_arg, idx_y_arg, idx_z_arg).
249  * \param idx_x_arg: index of leaf node in the X axis.
250  * \param idx_y_arg: index of leaf node in the Y axis.
251  * \param idx_z_arg: index of leaf node in the Z axis.
252  * */
253  void
254  removeLeaf (unsigned int idx_x_arg, unsigned int idx_y_arg, unsigned int idx_z_arg);
255 
256  /** \brief Return the amount of existing leafs in the octree.
257  * \return amount of registered leaf nodes.
258  * */
259  std::size_t
260  getLeafCount () const
261  {
262  return leaf_count_;
263  }
264 
265  /** \brief Return the amount of existing branch nodes in the octree.
266  * \return amount of branch nodes.
267  * */
268  std::size_t
269  getBranchCount () const
270  {
271  return branch_count_;
272  }
273 
274  /** \brief Delete the octree structure and its leaf nodes.
275  * */
276  void
277  deleteTree ( );
278 
279  /** \brief Serialize octree into a binary output vector describing its branch node structure.
280  * \param binary_tree_out_arg: reference to output vector for writing binary tree structure.
281  * */
282  void
283  serializeTree (std::vector<char>& binary_tree_out_arg);
284 
285  /** \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.
286  * \param binary_tree_out_arg: reference to output vector for writing binary tree structure.
287  * \param leaf_container_vector_arg: pointer to all LeafContainerT objects in the octree
288  * */
289  void
290  serializeTree (std::vector<char>& binary_tree_out_arg, std::vector<LeafContainerT*>& leaf_container_vector_arg);
291 
292  /** \brief Outputs a vector of all LeafContainerT elements that are stored within the octree leaf nodes.
293  * \param leaf_container_vector_arg: pointers to LeafContainerT vector that receives a copy of all LeafContainerT objects in the octree.
294  * */
295  void
296  serializeLeafs (std::vector<LeafContainerT*>& leaf_container_vector_arg);
297 
298  /** \brief Deserialize a binary octree description vector and create a corresponding octree structure. Leaf nodes are initialized with getDataTByKey(..).
299  * \param binary_tree_input_arg: reference to input vector for reading binary tree structure.
300  * */
301  void
302  deserializeTree (std::vector<char>& binary_tree_input_arg);
303 
304  /** \brief Deserialize a binary octree description and create a corresponding octree structure. Leaf nodes are initialized with LeafContainerT elements from the dataVector.
305  * \param binary_tree_input_arg: reference to input vector for reading binary tree structure.
306  * \param leaf_container_vector_arg: pointer to container vector.
307  * */
308  void
309  deserializeTree (std::vector<char>& binary_tree_input_arg, std::vector<LeafContainerT*>& leaf_container_vector_arg);
310 
311  protected:
312 
313  //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
314  // Protected octree methods based on octree keys
315  //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
316 
317  /** \brief Create a leaf node
318  * \param key_arg: octree key addressing a leaf node.
319  * \return pointer to leaf node
320  * */
321  LeafContainerT*
322  createLeaf (const OctreeKey& key_arg)
323  {
324 
325  LeafNode* leaf_node;
326  BranchNode* leaf_node_parent;
327 
328  createLeafRecursive (key_arg, depth_mask_ ,root_node_, leaf_node, leaf_node_parent);
329 
330  LeafContainerT* ret = leaf_node->getContainerPtr();
331 
332  return ret;
333  }
334 
335  /** \brief Find leaf node
336  * \param key_arg: octree key addressing a leaf node.
337  * \return pointer to leaf node. If leaf node is not found, this pointer returns 0.
338  * */
339  LeafContainerT*
340  findLeaf (const OctreeKey& key_arg) const
341  {
342  LeafContainerT* result = 0;
343  findLeafRecursive (key_arg, depth_mask_, root_node_, result);
344  return result;
345  }
346 
347  /** \brief Check for existence of a leaf node in the octree
348  * \param key_arg: octree key addressing a leaf node.
349  * \return "true" if leaf node is found; "false" otherwise
350  * */
351  bool
352  existLeaf (const OctreeKey& key_arg) const
353  {
354  return (findLeaf(key_arg) != 0);
355  }
356 
357  /** \brief Remove leaf node from octree
358  * \param key_arg: octree key addressing a leaf node.
359  * */
360  void
361  removeLeaf (const OctreeKey& key_arg)
362  {
363  if (key_arg <= max_key_)
365  }
366 
367  //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
368  // Branch node access functions
369  //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
370 
371  /** \brief Retrieve root node */
372  OctreeNode*
373  getRootNode () const
374  {
375  return this->root_node_;
376  }
377 
378  /** \brief Check if branch is pointing to a particular child node
379  * \param branch_arg: reference to octree branch class
380  * \param child_idx_arg: index to child node
381  * \return "true" if pointer to child node exists; "false" otherwise
382  * */
383  bool
384  branchHasChild (const BranchNode& branch_arg,
385  unsigned char child_idx_arg) const
386  {
387  // test occupancyByte for child existence
388  return (branch_arg.getChildPtr(child_idx_arg) != 0);
389  }
390 
391  /** \brief Retrieve a child node pointer for child node at child_idx.
392  * \param branch_arg: reference to octree branch class
393  * \param child_idx_arg: index to child node
394  * \return pointer to octree child node class
395  */
396  OctreeNode*
397  getBranchChildPtr (const BranchNode& branch_arg,
398  unsigned char child_idx_arg) const
399  {
400  return branch_arg.getChildPtr(child_idx_arg);
401  }
402 
403  /** \brief Assign new child node to branch
404  * \param branch_arg: reference to octree branch class
405  * \param child_idx_arg: index to child node
406  * \param new_child_arg: pointer to new child node
407  * */
408  void setBranchChildPtr (BranchNode& branch_arg,
409  unsigned char child_idx_arg,
410  OctreeNode* new_child_arg)
411  {
412  branch_arg[child_idx_arg] = new_child_arg;
413  }
414 
415  /** \brief Generate bit pattern reflecting the existence of child node pointers
416  * \param branch_arg: reference to octree branch class
417  * \return a single byte with 8 bits of child node information
418  * */
419  char
420  getBranchBitPattern (const BranchNode& branch_arg) const
421  {
422  unsigned char i;
423  char node_bits;
424 
425  // create bit pattern
426  node_bits = 0;
427  for (i = 0; i < 8; i++) {
428  const OctreeNode* child = branch_arg.getChildPtr(i);
429  node_bits |= static_cast<char> ((!!child) << i);
430  }
431 
432  return (node_bits);
433  }
434 
435  /** \brief Delete child node and all its subchilds from octree
436  * \param branch_arg: reference to octree branch class
437  * \param child_idx_arg: index to child node
438  * */
439  void
440  deleteBranchChild (BranchNode& branch_arg, unsigned char child_idx_arg)
441  {
442  if (branch_arg.hasChild(child_idx_arg))
443  {
444  OctreeNode* branch_child = branch_arg[child_idx_arg];
445 
446  switch (branch_child->getNodeType ())
447  {
448  case BRANCH_NODE:
449  {
450  // free child branch recursively
451  deleteBranch (*static_cast<BranchNode*> (branch_child));
452  // delete branch node
453  delete branch_child;
454  }
455  break;
456 
457  case LEAF_NODE:
458  {
459  // delete leaf node
460  delete branch_child;
461  break;
462  }
463  default:
464  break;
465  }
466 
467  // set branch child pointer to 0
468  branch_arg[child_idx_arg] = 0;
469  }
470  }
471 
472  /** \brief Delete branch and all its subchilds from octree
473  * \param branch_arg: reference to octree branch class
474  * */
475  void
476  deleteBranch (BranchNode& branch_arg)
477  {
478  char i;
479 
480  // delete all branch node children
481  for (i = 0; i < 8; i++)
482  deleteBranchChild (branch_arg, i);
483  }
484 
485  /** \brief Create and add a new branch child to a branch class
486  * \param branch_arg: reference to octree branch class
487  * \param child_idx_arg: index to child node
488  * \return pointer of new branch child to this reference
489  * */
491  unsigned char child_idx_arg)
492  {
493  BranchNode* new_branch_child = new BranchNode();
494  branch_arg[child_idx_arg] = static_cast<OctreeNode*> (new_branch_child);
495 
496  return new_branch_child;
497  }
498 
499  /** \brief Create and add a new leaf child to a branch class
500  * \param branch_arg: reference to octree branch class
501  * \param child_idx_arg: index to child node
502  * \return pointer of new leaf child to this reference
503  * */
504  LeafNode*
505  createLeafChild (BranchNode& branch_arg, unsigned char child_idx_arg)
506  {
507  LeafNode* new_leaf_child = new LeafNode();
508  branch_arg[child_idx_arg] = static_cast<OctreeNode*> (new_leaf_child);
509 
510  return new_leaf_child;
511  }
512 
513  //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
514  // Recursive octree methods
515  //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
516 
517  /** \brief Create a leaf node at octree key. If leaf node does already exist, it is returned.
518  * \param key_arg: reference to an octree key
519  * \param depth_mask_arg: depth mask used for octree key analysis and for branch depth indicator
520  * \param branch_arg: current branch node
521  * \param return_leaf_arg: return pointer to leaf node
522  * \param parent_of_leaf_arg: return pointer to parent of leaf node
523  * \return depth mask at which leaf node was created
524  **/
525  unsigned int
526  createLeafRecursive (const OctreeKey& key_arg,
527  unsigned int depth_mask_arg,
528  BranchNode* branch_arg,
529  LeafNode*& return_leaf_arg,
530  BranchNode*& parent_of_leaf_arg);
531 
532  /** \brief Recursively search for a given leaf node and return a pointer.
533  * \note If leaf node does not exist, a 0 pointer is returned.
534  * \param key_arg: reference to an octree key
535  * \param depth_mask_arg: depth mask used for octree key analysis and for branch depth indicator
536  * \param branch_arg: current branch node
537  * \param result_arg: pointer to leaf node class
538  **/
539  void
540  findLeafRecursive (const OctreeKey& key_arg,
541  unsigned int depth_mask_arg,
542  BranchNode* branch_arg,
543  LeafContainerT*& result_arg) const;
544 
545  /** \brief Recursively search and delete leaf node
546  * \param key_arg: reference to an octree key
547  * \param depth_mask_arg: depth mask used for octree key analysis and branch depth indicator
548  * \param branch_arg: current branch node
549  * \return "true" if branch does not contain any childs; "false" otherwise. This indicates if current branch can be deleted, too.
550  **/
551  bool
552  deleteLeafRecursive (const OctreeKey& key_arg,
553  unsigned int depth_mask_arg,
554  BranchNode* branch_arg);
555 
556  /** \brief Recursively explore the octree and output binary octree description together with a vector of leaf node LeafContainerTs.
557  * \param branch_arg: current branch node
558  * \param key_arg: reference to an octree key
559  * \param binary_tree_out_arg: binary output vector
560  * \param leaf_container_vector_arg: writes LeafContainerT pointers to this LeafContainerT* vector.
561  **/
562  void
563  serializeTreeRecursive (const BranchNode* branch_arg,
564  OctreeKey& key_arg,
565  std::vector<char>* binary_tree_out_arg,
566  typename std::vector<LeafContainerT*>* leaf_container_vector_arg) const;
567 
568  /** \brief Recursive method for deserializing octree structure
569  * \param branch_arg: current branch node
570  * \param depth_mask_arg: depth mask used for octree key analysis and branch depth indicator
571  * \param key_arg: reference to an octree key
572  * \param binary_tree_input_it_arg: iterator to binary input vector
573  * \param binary_tree_input_it_end_arg: end iterator of binary input vector
574  * \param leaf_container_vector_it_arg: iterator pointing to current LeafContainerT object to be added to a leaf node
575  * \param leaf_container_vector_it_end_arg: iterator pointing to last object in LeafContainerT input vector.
576  **/
577  void
578  deserializeTreeRecursive (BranchNode* branch_arg, unsigned int depth_mask_arg, OctreeKey& key_arg,
579  typename std::vector<char>::const_iterator& binary_tree_input_it_arg,
580  typename std::vector<char>::const_iterator& binary_tree_input_it_end_arg,
581  typename std::vector<LeafContainerT*>::const_iterator* leaf_container_vector_it_arg,
582  typename std::vector<LeafContainerT*>::const_iterator* leaf_container_vector_it_end_arg);
583 
584 
585  //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
586  // Serialization callbacks
587  //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
588 
589  /** \brief Callback executed for every leaf node during serialization
590  **/
591  virtual void
592  serializeTreeCallback (LeafContainerT&, const OctreeKey &) const
593  {
594 
595  }
596 
597  /** \brief Callback executed for every leaf node during deserialization
598  **/
599  virtual void
600  deserializeTreeCallback (LeafContainerT&, const OctreeKey&)
601  {
602 
603  }
604 
605  //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
606  // Helpers
607  //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
608 
609  /** \brief Helper function to calculate the binary logarithm
610  * \param n_arg: some value
611  * \return binary logarithm (log2) of argument n_arg
612  */
613  double
614  Log2 (double n_arg)
615  {
616  return log( n_arg ) / log( 2.0 );
617  }
618 
619  /** \brief Test if octree is able to dynamically change its depth. This is required for adaptive bounding box adjustment.
620  * \return "true"
621  **/
622  bool
624  {
625  return (true);
626  }
627  };
628  }
629 }
630 
631 #ifdef PCL_NO_PRECOMPILE
632 #include <pcl/octree/impl/octree_base.hpp>
633 #endif
634 
635 #endif
636 
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...
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:146
OctreeBreadthFirstIterator< OctreeT > BreadthFirstIterator
Definition: octree_base.h:149
void deleteTree()
Delete the octree structure and its 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:384
const OctreeLeafNodeIterator< OctreeT > ConstLeafNodeIterator
Definition: octree_base.h:125
void setMaxVoxelIndex(unsigned int max_voxel_index_arg)
Set the maximum amount of voxels per dimension.
Definition: octree_base.hpp:75
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.
virtual void serializeTreeCallback(LeafContainerT &, const OctreeKey &) const
Callback executed for every leaf node during serialization.
Definition: octree_base.h:592
bool deleteLeafRecursive(const OctreeKey &key_arg, unsigned int depth_mask_arg, BranchNode *branch_arg)
Recursively search and delete leaf node.
LeafContainerT * findLeaf(const OctreeKey &key_arg) const
Find leaf node.
Definition: octree_base.h:340
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
OctreeNode * getChildPtr(unsigned char child_idx_arg) const
Get pointer to child.
Definition: octree_nodes.h:272
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).
void deleteBranch(BranchNode &branch_arg)
Delete branch and all its subchilds from octree.
Definition: octree_base.h:476
BranchContainerT BranchContainer
Definition: octree_base.h:71
OctreeBase & operator=(const OctreeBase &source)
Copy operator.
Definition: octree_base.h:187
void setTreeDepth(unsigned int max_depth_arg)
Set the maximum depth of the octree.
Definition: octree_base.hpp:91
Iterator begin(unsigned int max_depth_arg=0u)
Definition: octree_base.h:113
OctreeBase()
Empty constructor.
Definition: octree_base.hpp:52
OctreeBase(const OctreeBase &source)
Copy constructor.
Definition: octree_base.h:174
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:397
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:505
unsigned int octree_depth_
Octree depth.
Definition: octree_base.h:93
Octree leaf node iterator class.
BreadthFirstIterator breadth_begin(unsigned int max_depth_arg=0u)
Definition: octree_base.h:155
const OctreeBreadthFirstIterator< OctreeT > ConstBreadthFirstIterator
Definition: octree_base.h:153
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).
bool hasChild(unsigned char child_idx_arg) const
Check if branch is pointing to a particular child node.
Definition: octree_nodes.h:292
OctreeLeafNodeIterator< OctreeT > LeafNodeIterator
Definition: octree_base.h:121
OctreeBase< LeafContainerT, BranchContainerT > OctreeT
Definition: octree_base.h:66
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:490
std::size_t getLeafCount() const
Return the amount of existing leafs in the octree.
Definition: octree_base.h:260
OctreeKey max_key_
key range
Definition: octree_base.h:99
const Iterator end()
Definition: octree_base.h:118
bool octreeCanResize()
Test if octree is able to dynamically change its depth.
Definition: octree_base.h:623
OctreeBranchNode< BranchContainerT > BranchNode
Definition: octree_base.h:68
BranchNode * root_node_
Pointer to root branch node of octree.
Definition: octree_base.h:87
void serializeLeafs(std::vector< LeafContainerT * > &leaf_container_vector_arg)
Outputs a vector of all LeafContainerT elements that are stored within the octree leaf nodes...
OctreeDepthFirstIterator< OctreeT > DepthFirstIterator
Definition: octree_base.h:135
const ContainerT * getContainerPtr() const
Get const pointer to container.
Definition: octree_nodes.h:178
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).
char getBranchBitPattern(const BranchNode &branch_arg) const
Generate bit pattern reflecting the existence of child node pointers.
Definition: octree_base.h:420
void removeLeaf(const OctreeKey &key_arg)
Remove leaf node from octree.
Definition: octree_base.h:361
virtual void deserializeTreeCallback(LeafContainerT &, const OctreeKey &)
Callback executed for every leaf node during deserialization.
Definition: octree_base.h:600
bool dynamic_depth_enabled_
Enable dynamic_depth.
Definition: octree_base.h:96
LeafContainerT LeafContainer
Definition: octree_base.h:72
LeafContainerT * createLeaf(const OctreeKey &key_arg)
Create a leaf node.
Definition: octree_base.h:322
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.
Octree key class
Definition: octree_key.h:51
Abstract octree leaf class
Definition: octree_nodes.h:97
unsigned int getTreeDepth() const
Get the maximum depth of the octree.
Definition: octree_base.h:214
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.
OctreeLeafNode< LeafContainerT > LeafNode
Definition: octree_base.h:69
std::size_t getBranchCount() const
Return the amount of existing branch nodes in the octree.
Definition: octree_base.h:269
const LeafNodeIterator leaf_end()
Definition: octree_base.h:132
bool existLeaf(const OctreeKey &key_arg) const
Check for existence of a leaf node in the octree.
Definition: octree_base.h:352
DepthFirstIterator depth_begin(unsigned int max_depth_arg=0u)
Definition: octree_base.h:141
void setBranchChildPtr(BranchNode &branch_arg, unsigned char child_idx_arg, OctreeNode *new_child_arg)
Assign new child node to branch.
Definition: octree_base.h:408
Abstract octree iterator class
LeafNodeIterator leaf_begin(unsigned int max_depth_arg=0u)
Definition: octree_base.h:127
OctreeNode * getRootNode() const
Retrieve root node.
Definition: octree_base.h:373
const OctreeDepthFirstIterator< OctreeT > ConstIterator
Definition: octree_base.h:111
const OctreeDepthFirstIterator< OctreeT > ConstDepthFirstIterator
Definition: octree_base.h:139
Abstract octree branch class
Definition: octree_nodes.h:204
std::size_t leaf_count_
Amount of leaf nodes.
Definition: octree_base.h:81
const BreadthFirstIterator breadth_end()
Definition: octree_base.h:160
Abstract octree node class
Definition: octree_nodes.h:68
unsigned int depth_mask_
Depth mask based on octree depth.
Definition: octree_base.h:90
double Log2(double n_arg)
Helper function to calculate the binary logarithm.
Definition: octree_base.h:614
OctreeDepthFirstIterator< OctreeT > Iterator
Definition: octree_base.h:110
std::size_t branch_count_
Amount of branch nodes.
Definition: octree_base.h:84
void deleteBranchChild(BranchNode &branch_arg, unsigned char child_idx_arg)
Delete child node and all its subchilds from octree.
Definition: octree_base.h:440