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