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