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