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