Point Cloud Library (PCL)  1.10.1
octree_base.h
1 /*
2  * Software License Agreement (BSD License)
3  *
4  * Point Cloud Library (PCL) - www.pointclouds.org
5  * Copyright (c) 2010-2012, Willow Garage, Inc.
6  *
7  * All rights reserved.
8  *
9  * Redistribution and use in source and binary forms, with or without
10  * modification, are permitted provided that the following conditions
11  * are met:
12  *
13  * * Redistributions of source code must retain the above copyright
14  * notice, this list of conditions and the following disclaimer.
15  * * Redistributions in binary form must reproduce the above
16  * copyright notice, this list of conditions and the following
17  * disclaimer in the documentation and/or other materials provided
18  * with the distribution.
19  * * Neither the name of Willow Garage, Inc. nor the names of its
20  * contributors may be used to endorse or promote products derived
21  * from this software without specific prior written permission.
22  *
23  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
24  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
25  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
26  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
27  * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
28  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
29  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
30  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
31  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
32  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
33  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
34  * POSSIBILITY OF SUCH DAMAGE.
35  *
36  * $Id$
37  */
38 
39 #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("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("use leaf_depth_end() instead") const LeafNodeIterator leaf_end()
137  {
138  return LeafNodeIterator(this, 0, nullptr);
139  };
140 
141  // The currently valide names
145 
147  leaf_depth_begin(unsigned int max_depth_arg = 0u)
148  {
150  this, max_depth_arg ? max_depth_arg : this->octree_depth_);
151  };
152 
155  {
156  return LeafNodeDepthFirstIterator(this, 0, nullptr);
157  };
158 
159  // Octree depth-first iterators
162 
164  depth_begin(unsigned int max_depth_arg = 0u)
165  {
166  return DepthFirstIterator(this,
167  max_depth_arg ? max_depth_arg : this->octree_depth_);
168  };
169 
170  const DepthFirstIterator
172  {
173  return DepthFirstIterator(this, 0, nullptr);
174  };
175 
176  // Octree breadth-first iterators
179 
181  breadth_begin(unsigned int max_depth_arg = 0u)
182  {
183  return BreadthFirstIterator(this,
184  max_depth_arg ? max_depth_arg : this->octree_depth_);
185  };
186 
189  {
190  return BreadthFirstIterator(this, 0, nullptr);
191  };
192 
193  // Octree breadth iterators at a given depth
196 
198  fixed_depth_begin(unsigned int fixed_depth_arg = 0u)
199  {
200  return FixedDepthIterator(this, fixed_depth_arg);
201  };
202 
203  const FixedDepthIterator
205  {
206  return FixedDepthIterator(this, 0, nullptr);
207  };
208 
209  // Octree leaf node iterators
213 
215  leaf_breadth_begin(unsigned int max_depth_arg = 0u)
216  {
218  this, max_depth_arg ? max_depth_arg : this->octree_depth_);
219  };
220 
223  {
224  return LeafNodeBreadthFirstIterator(this, 0, nullptr);
225  };
226 
227  /** \brief Empty constructor. */
228  OctreeBase();
229 
230  /** \brief Empty deconstructor. */
231  virtual ~OctreeBase();
232 
233  /** \brief Copy constructor. */
234  OctreeBase(const OctreeBase& source)
235  : leaf_count_(source.leaf_count_)
236  , branch_count_(source.branch_count_)
237  , root_node_(new (BranchNode)(*(source.root_node_)))
238  , depth_mask_(source.depth_mask_)
239  , octree_depth_(source.octree_depth_)
241  , max_key_(source.max_key_)
242  {}
243 
244  /** \brief Copy operator. */
245  OctreeBase&
246  operator=(const OctreeBase& source)
247  {
248  leaf_count_ = source.leaf_count_;
249  branch_count_ = source.branch_count_;
250  root_node_ = new (BranchNode)(*(source.root_node_));
251  depth_mask_ = source.depth_mask_;
252  max_key_ = source.max_key_;
253  octree_depth_ = source.octree_depth_;
254  return (*this);
255  }
256 
257  /** \brief Set the maximum amount of voxels per dimension.
258  * \param[in] max_voxel_index_arg maximum amount of voxels per dimension
259  */
260  void
261  setMaxVoxelIndex(unsigned int max_voxel_index_arg);
262 
263  /** \brief Set the maximum depth of the octree.
264  * \param max_depth_arg: maximum depth of octree
265  */
266  void
267  setTreeDepth(unsigned int max_depth_arg);
268 
269  /** \brief Get the maximum depth of the octree.
270  * \return depth_arg: maximum depth of octree
271  */
272  unsigned int
273  getTreeDepth() const
274  {
275  return this->octree_depth_;
276  }
277 
278  /** \brief Create new leaf node at (idx_x_arg, idx_y_arg, idx_z_arg).
279  * \note If leaf node already exist, this method returns the existing node
280  * \param idx_x_arg: index of leaf node in the X axis.
281  * \param idx_y_arg: index of leaf node in the Y axis.
282  * \param idx_z_arg: index of leaf node in the Z axis.
283  * \return pointer to new leaf node container.
284  */
285  LeafContainerT*
286  createLeaf(unsigned int idx_x_arg, unsigned int idx_y_arg, unsigned int idx_z_arg);
287 
288  /** \brief Find leaf node at (idx_x_arg, idx_y_arg, idx_z_arg).
289  * \note If leaf node already exist, this method returns the existing node
290  * \param idx_x_arg: index of leaf node in the X axis.
291  * \param idx_y_arg: index of leaf node in the Y axis.
292  * \param idx_z_arg: index of leaf node in the Z axis.
293  * \return pointer to leaf node container if found, null pointer otherwise.
294  */
295  LeafContainerT*
296  findLeaf(unsigned int idx_x_arg, unsigned int idx_y_arg, unsigned int idx_z_arg);
297 
298  /** \brief idx_x_arg for the existence of leaf node at (idx_x_arg, idx_y_arg,
299  * idx_z_arg).
300  * \param idx_x_arg: index of leaf node in the X axis.
301  * \param idx_y_arg: index of leaf node in the Y axis.
302  * \param idx_z_arg: index of leaf node in the Z axis.
303  * \return "true" if leaf node search is successful, otherwise it returns "false".
304  */
305  bool
306  existLeaf(unsigned int idx_x_arg,
307  unsigned int idx_y_arg,
308  unsigned int idx_z_arg) const;
309 
310  /** \brief Remove leaf node at (idx_x_arg, idx_y_arg, idx_z_arg).
311  * \param idx_x_arg: index of leaf node in the X axis.
312  * \param idx_y_arg: index of leaf node in the Y axis.
313  * \param idx_z_arg: index of leaf node in the Z axis.
314  */
315  void
316  removeLeaf(unsigned int idx_x_arg, unsigned int idx_y_arg, unsigned int idx_z_arg);
317 
318  /** \brief Return the amount of existing leafs in the octree.
319  * \return amount of registered leaf nodes.
320  */
321  std::size_t
322  getLeafCount() const
323  {
324  return leaf_count_;
325  }
326 
327  /** \brief Return the amount of existing branch nodes in the octree.
328  * \return amount of branch nodes.
329  */
330  std::size_t
332  {
333  return branch_count_;
334  }
335 
336  /** \brief Delete the octree structure and its leaf nodes.
337  */
338  void
339  deleteTree();
340 
341  /** \brief Serialize octree into a binary output vector describing its branch node
342  * structure.
343  * \param binary_tree_out_arg: reference to output vector for writing binary tree
344  * structure.
345  */
346  void
347  serializeTree(std::vector<char>& binary_tree_out_arg);
348 
349  /** \brief Serialize octree into a binary output vector describing its branch node
350  * structure and push all LeafContainerT elements stored in the octree to a vector.
351  * \param binary_tree_out_arg: reference to output vector for writing binary tree
352  * structure.
353  * \param leaf_container_vector_arg: pointer to all LeafContainerT objects in the
354  * octree
355  */
356  void
357  serializeTree(std::vector<char>& binary_tree_out_arg,
358  std::vector<LeafContainerT*>& leaf_container_vector_arg);
359 
360  /** \brief Outputs a vector of all LeafContainerT elements that are stored within the
361  * octree leaf nodes.
362  * \param leaf_container_vector_arg: pointers to LeafContainerT vector that receives a
363  * copy of all LeafContainerT objects in the octree.
364  */
365  void
366  serializeLeafs(std::vector<LeafContainerT*>& leaf_container_vector_arg);
367 
368  /** \brief Deserialize a binary octree description vector and create a corresponding
369  * octree structure. Leaf nodes are initialized with getDataTByKey(..).
370  * \param binary_tree_input_arg: reference to input vector for reading binary tree
371  * structure.
372  */
373  void
374  deserializeTree(std::vector<char>& binary_tree_input_arg);
375 
376  /** \brief Deserialize a binary octree description and create a corresponding octree
377  * structure. Leaf nodes are initialized with LeafContainerT elements from the
378  * dataVector.
379  * \param binary_tree_input_arg: reference to input vector for reading binary tree
380  * structure. \param leaf_container_vector_arg: pointer to container vector.
381  */
382  void
383  deserializeTree(std::vector<char>& binary_tree_input_arg,
384  std::vector<LeafContainerT*>& leaf_container_vector_arg);
385 
386 protected:
387  //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
388  // Protected octree methods based on octree keys
389  //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
390 
391  /** \brief Create a leaf node
392  * \param key_arg: octree key addressing a leaf node.
393  * \return pointer to leaf node
394  */
395  LeafContainerT*
396  createLeaf(const OctreeKey& key_arg)
397  {
398 
399  LeafNode* leaf_node;
400  BranchNode* leaf_node_parent;
401 
402  createLeafRecursive(key_arg, depth_mask_, root_node_, leaf_node, leaf_node_parent);
403 
404  LeafContainerT* ret = leaf_node->getContainerPtr();
405 
406  return ret;
407  }
408 
409  /** \brief Find leaf node
410  * \param key_arg: octree key addressing a leaf node.
411  * \return pointer to leaf node. If leaf node is not found, this pointer returns 0.
412  */
413  LeafContainerT*
414  findLeaf(const OctreeKey& key_arg) const
415  {
416  LeafContainerT* result = nullptr;
417  findLeafRecursive(key_arg, depth_mask_, root_node_, result);
418  return result;
419  }
420 
421  /** \brief Check for existence of a leaf node in the octree
422  * \param key_arg: octree key addressing a leaf node.
423  * \return "true" if leaf node is found; "false" otherwise
424  */
425  bool
426  existLeaf(const OctreeKey& key_arg) const
427  {
428  return (findLeaf(key_arg) != nullptr);
429  }
430 
431  /** \brief Remove leaf node from octree
432  * \param key_arg: octree key addressing a leaf node.
433  */
434  void
435  removeLeaf(const OctreeKey& key_arg)
436  {
437  if (key_arg <= max_key_)
439  }
440 
441  //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
442  // Branch node access functions
443  //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
444 
445  /** \brief Retrieve root node */
446  OctreeNode*
447  getRootNode() const
448  {
449  return this->root_node_;
450  }
451 
452  /** \brief Check if branch is pointing to a particular child node
453  * \param branch_arg: reference to octree branch class
454  * \param child_idx_arg: index to child node
455  * \return "true" if pointer to child node exists; "false" otherwise
456  */
457  bool
458  branchHasChild(const BranchNode& branch_arg, unsigned char child_idx_arg) const
459  {
460  // test occupancyByte for child existence
461  return (branch_arg.getChildPtr(child_idx_arg) != nullptr);
462  }
463 
464  /** \brief Retrieve a child node pointer for child node at child_idx.
465  * \param branch_arg: reference to octree branch class
466  * \param child_idx_arg: index to child node
467  * \return pointer to octree child node class
468  */
469  OctreeNode*
470  getBranchChildPtr(const BranchNode& branch_arg, unsigned char child_idx_arg) const
471  {
472  return branch_arg.getChildPtr(child_idx_arg);
473  }
474 
475  /** \brief Assign new child node to branch
476  * \param branch_arg: reference to octree branch class
477  * \param child_idx_arg: index to child node
478  * \param new_child_arg: pointer to new child node
479  */
480  void
482  unsigned char child_idx_arg,
483  OctreeNode* new_child_arg)
484  {
485  branch_arg[child_idx_arg] = new_child_arg;
486  }
487 
488  /** \brief Generate bit pattern reflecting the existence of child node pointers
489  * \param branch_arg: reference to octree branch class
490  * \return a single byte with 8 bits of child node information
491  */
492  char
493  getBranchBitPattern(const BranchNode& branch_arg) const
494  {
495  char node_bits;
496 
497  // create bit pattern
498  node_bits = 0;
499  for (unsigned char i = 0; i < 8; i++) {
500  const OctreeNode* child = branch_arg.getChildPtr(i);
501  node_bits |= static_cast<char>((!!child) << i);
502  }
503 
504  return (node_bits);
505  }
506 
507  /** \brief Delete child node and all its subchilds from octree
508  * \param branch_arg: reference to octree branch class
509  * \param child_idx_arg: index to child node
510  */
511  void
512  deleteBranchChild(BranchNode& branch_arg, unsigned char child_idx_arg)
513  {
514  if (branch_arg.hasChild(child_idx_arg)) {
515  OctreeNode* branch_child = branch_arg[child_idx_arg];
516 
517  switch (branch_child->getNodeType()) {
518  case BRANCH_NODE: {
519  // free child branch recursively
520  deleteBranch(*static_cast<BranchNode*>(branch_child));
521  // delete branch node
522  delete branch_child;
523  } break;
524 
525  case LEAF_NODE: {
526  // delete leaf node
527  delete branch_child;
528  break;
529  }
530  default:
531  break;
532  }
533 
534  // set branch child pointer to 0
535  branch_arg[child_idx_arg] = nullptr;
536  }
537  }
538 
539  /** \brief Delete branch and all its subchilds from octree
540  * \param branch_arg: reference to octree branch class
541  */
542  void
544  {
545  // delete all branch node children
546  for (char i = 0; i < 8; i++)
547  deleteBranchChild(branch_arg, i);
548  }
549 
550  /** \brief Create and add a new branch child to a branch class
551  * \param branch_arg: reference to octree branch class
552  * \param child_idx_arg: index to child node
553  * \return pointer of new branch child to this reference
554  */
555  BranchNode*
556  createBranchChild(BranchNode& branch_arg, unsigned char child_idx_arg)
557  {
558  BranchNode* new_branch_child = new BranchNode();
559  branch_arg[child_idx_arg] = static_cast<OctreeNode*>(new_branch_child);
560 
561  return new_branch_child;
562  }
563 
564  /** \brief Create and add a new leaf child to a branch class
565  * \param branch_arg: reference to octree branch class
566  * \param child_idx_arg: index to child node
567  * \return pointer of new leaf child to this reference
568  */
569  LeafNode*
570  createLeafChild(BranchNode& branch_arg, unsigned char child_idx_arg)
571  {
572  LeafNode* new_leaf_child = new LeafNode();
573  branch_arg[child_idx_arg] = static_cast<OctreeNode*>(new_leaf_child);
574 
575  return new_leaf_child;
576  }
577 
578  //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
579  // Recursive octree methods
580  //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
581 
582  /** \brief Create a leaf node at octree key. If leaf node does already exist, it is
583  * returned.
584  * \param key_arg: reference to an octree key
585  * \param depth_mask_arg: depth mask used for octree key analysis and for branch depth
586  * indicator
587  * \param branch_arg: current branch node
588  * \param return_leaf_arg: return pointer to leaf node
589  * \param parent_of_leaf_arg: return pointer to parent of leaf node
590  * \return depth mask at which leaf node was created
591  **/
592  unsigned int
593  createLeafRecursive(const OctreeKey& key_arg,
594  unsigned int depth_mask_arg,
595  BranchNode* branch_arg,
596  LeafNode*& return_leaf_arg,
597  BranchNode*& parent_of_leaf_arg);
598 
599  /** \brief Recursively search for a given leaf node and return a pointer.
600  * \note If leaf node does not exist, a 0 pointer is returned.
601  * \param key_arg: reference to an octree key
602  * \param depth_mask_arg: depth mask used for octree key analysis and for branch
603  * depth indicator
604  * \param branch_arg: current branch node
605  * \param result_arg: pointer to leaf node class
606  **/
607  void
608  findLeafRecursive(const OctreeKey& key_arg,
609  unsigned int depth_mask_arg,
610  BranchNode* branch_arg,
611  LeafContainerT*& result_arg) const;
612 
613  /** \brief Recursively search and delete leaf node
614  * \param key_arg: reference to an octree key
615  * \param depth_mask_arg: depth mask used for octree key analysis and branch depth
616  * indicator
617  * \param branch_arg: current branch node
618  * \return "true" if branch does not contain any childs; "false" otherwise. This
619  * indicates if current branch can be deleted, too.
620  **/
621  bool
622  deleteLeafRecursive(const OctreeKey& key_arg,
623  unsigned int depth_mask_arg,
624  BranchNode* branch_arg);
625 
626  /** \brief Recursively explore the octree and output binary octree description
627  * together with a vector of leaf node LeafContainerTs.
628  * \param branch_arg: current branch node
629  * \param key_arg: reference to an octree key
630  * \param binary_tree_out_arg: binary output vector
631  * \param leaf_container_vector_arg: writes LeafContainerT pointers to this
632  *LeafContainerT* vector.
633  **/
634  void
636  const BranchNode* branch_arg,
637  OctreeKey& key_arg,
638  std::vector<char>* binary_tree_out_arg,
639  typename std::vector<LeafContainerT*>* leaf_container_vector_arg) const;
640 
641  /** \brief Recursive method for deserializing octree structure
642  * \param branch_arg: current branch node
643  * \param depth_mask_arg: depth mask used for octree key analysis and branch depth
644  * indicator
645  * \param key_arg: reference to an octree key
646  * \param binary_tree_input_it_arg: iterator to binary input vector
647  * \param binary_tree_input_it_end_arg: end iterator of binary input vector
648  * \param leaf_container_vector_it_arg: iterator pointing to current LeafContainerT
649  * object to be added to a leaf node
650  * \param leaf_container_vector_it_end_arg: iterator pointing to last object in
651  * LeafContainerT input vector.
652  **/
653  void
655  BranchNode* branch_arg,
656  unsigned int depth_mask_arg,
657  OctreeKey& key_arg,
658  typename std::vector<char>::const_iterator& binary_tree_input_it_arg,
659  typename std::vector<char>::const_iterator& binary_tree_input_it_end_arg,
660  typename std::vector<LeafContainerT*>::const_iterator*
661  leaf_container_vector_it_arg,
662  typename std::vector<LeafContainerT*>::const_iterator*
663  leaf_container_vector_it_end_arg);
664 
665  //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
666  // Serialization callbacks
667  //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
668 
669  /** \brief Callback executed for every leaf node during serialization
670  **/
671  virtual void
672  serializeTreeCallback(LeafContainerT&, const OctreeKey&) const
673  {}
674 
675  /** \brief Callback executed for every leaf node during deserialization
676  **/
677  virtual void
678  deserializeTreeCallback(LeafContainerT&, const OctreeKey&)
679  {}
680 
681  //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
682  // Helpers
683  //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
684 
685  /** \brief Helper function to calculate the binary logarithm
686  * \param n_arg: some value
687  * \return binary logarithm (log2) of argument n_arg
688  */
689  PCL_DEPRECATED("use std::log2 instead") double Log2(double n_arg)
690  {
691  return std::log2(n_arg);
692  }
693 
694  /** \brief Test if octree is able to dynamically change its depth. This is required
695  *for adaptive bounding box adjustment.
696  * \return "true"
697  **/
698  bool
700  {
701  return (true);
702  }
703 };
704 } // namespace octree
705 } // namespace pcl
706 
707 #ifdef PCL_NO_PRECOMPILE
708 #include <pcl/octree/impl/octree_base.hpp>
709 #endif
pcl::octree::OctreeBase::setMaxVoxelIndex
void setMaxVoxelIndex(unsigned int max_voxel_index_arg)
Set the maximum amount of voxels per dimension.
Definition: octree_base.hpp:71
pcl::octree::OctreeBase::Iterator
OctreeDepthFirstIterator< OctreeT > Iterator
Definition: octree_base.h:107
pcl::octree::OctreeBase::createLeaf
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).
Definition: octree_base.hpp:121
pcl_macros.h
Defines all the PCL and non-PCL macros used.
pcl::octree::OctreeBase::getBranchChildPtr
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:470
pcl::octree::OctreeBase::depth_mask_
unsigned int depth_mask_
Depth mask based on octree depth
Definition: octree_base.h:86
pcl
This file defines compatibility wrappers for low level I/O functions.
Definition: convolution.h:45
pcl::octree::OctreeBase::LeafNodeIterator
OctreeLeafNodeDepthFirstIterator< OctreeT > LeafNodeIterator
Definition: octree_base.h:126
pcl::octree::OctreeBase::deserializeTree
void deserializeTree(std::vector< char > &binary_tree_input_arg)
Deserialize a binary octree description vector and create a corresponding octree structure.
Definition: octree_base.hpp:230
pcl::octree::OctreeBase::deleteTree
void deleteTree()
Delete the octree structure and its leaf nodes.
Definition: octree_base.hpp:163
pcl::octree::OctreeNode::getNodeType
virtual node_type_t getNodeType() const =0
Pure virtual method for receiving the type of octree node (branch or leaf)
pcl::octree::OctreeBase::depth_end
const DepthFirstIterator depth_end()
Definition: octree_base.h:171
pcl::octree::OctreeBase::deleteLeafRecursive
bool deleteLeafRecursive(const OctreeKey &key_arg, unsigned int depth_mask_arg, BranchNode *branch_arg)
Recursively search and delete leaf node.
Definition: octree_base.hpp:385
pcl::octree::OctreeBase::fixed_depth_end
const FixedDepthIterator fixed_depth_end()
Definition: octree_base.h:204
pcl::octree::OctreeBase::branchHasChild
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:458
pcl::octree::OctreeBase::operator=
OctreeBase & operator=(const OctreeBase &source)
Copy operator.
Definition: octree_base.h:246
pcl::octree::OctreeBase::setTreeDepth
void setTreeDepth(unsigned int max_depth_arg)
Set the maximum depth of the octree.
Definition: octree_base.hpp:90
pcl::octree::OctreeBase::begin
Iterator begin(unsigned int max_depth_arg=0u)
Definition: octree_base.h:111
pcl::octree::OctreeBase::OctreeBase
OctreeBase()
Empty constructor.
Definition: octree_base.hpp:50
pcl::octree::OctreeBase::leaf_breadth_end
const LeafNodeBreadthFirstIterator leaf_breadth_end()
Definition: octree_base.h:222
pcl::octree::OctreeBase::leaf_depth_end
const LeafNodeDepthFirstIterator leaf_depth_end()
Definition: octree_base.h:154
pcl::octree::OctreeBase::~OctreeBase
virtual ~OctreeBase()
Empty deconstructor.
Definition: octree_base.hpp:61
pcl::octree::OctreeBase::createLeafChild
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:570
pcl::octree::OctreeBase::octree_depth_
unsigned int octree_depth_
Octree depth.
Definition: octree_base.h:89
pcl::octree::OctreeKey
Octree key class
Definition: octree_key.h:51
pcl::octree::OctreeBase::deleteBranch
void deleteBranch(BranchNode &branch_arg)
Delete branch and all its subchilds from octree.
Definition: octree_base.h:543
pcl::octree::OctreeContainerPointIndices
Octree container class that does store a vector of point indices.
Definition: octree_container.h:251
pcl::octree::OctreeBase::findLeaf
LeafContainerT * findLeaf(const OctreeKey &key_arg) const
Find leaf node.
Definition: octree_base.h:414
pcl::octree::OctreeBase::OctreeBase
OctreeBase(const OctreeBase &source)
Copy constructor.
Definition: octree_base.h:234
pcl::octree::OctreeNode
Abstract octree node class
Definition: octree_nodes.h:62
pcl::octree::OctreeBase::existLeaf
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).
Definition: octree_base.hpp:135
pcl::octree::LEAF_NODE
Definition: octree_nodes.h:55
pcl::octree::OctreeBase::createBranchChild
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:556
pcl::octree::OctreeLeafNode
Abstract octree leaf class
Definition: octree_nodes.h:84
pcl::octree::OctreeBase::PCL_DEPRECATED
PCL_DEPRECATED("use leaf_depth_end() instead") const LeafNodeIterator leaf_end()
Definition: octree_base.h:136
pcl::octree::OctreeBase::breadth_begin
BreadthFirstIterator breadth_begin(unsigned int max_depth_arg=0u)
Definition: octree_base.h:181
pcl::octree::BRANCH_NODE
Definition: octree_nodes.h:55
pcl::octree::OctreeBase::end
const Iterator end()
Definition: octree_base.h:117
pcl::octree::OctreeBase::serializeTree
void serializeTree(std::vector< char > &binary_tree_out_arg)
Serialize octree into a binary output vector describing its branch node structure.
Definition: octree_base.hpp:177
pcl::octree::OctreeBase::serializeTreeCallback
virtual void serializeTreeCallback(LeafContainerT &, const OctreeKey &) const
Callback executed for every leaf node during serialization.
Definition: octree_base.h:672
pcl::octree::OctreeBase::createLeafRecursive
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.
Definition: octree_base.hpp:287
pcl::octree::OctreeBase::root_node_
BranchNode * root_node_
Pointer to root branch node of octree
Definition: octree_base.h:83
pcl::octree::OctreeBase::removeLeaf
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).
Definition: octree_base.hpp:149
pcl::octree::OctreeBase::serializeLeafs
void serializeLeafs(std::vector< LeafContainerT * > &leaf_container_vector_arg)
Outputs a vector of all LeafContainerT elements that are stored within the octree leaf nodes.
Definition: octree_base.hpp:214
pcl::octree::OctreeBase
Octree class.
Definition: octree_base.h:61
pcl::octree::OctreeBase::findLeaf
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).
Definition: octree_base.hpp:107
pcl::octree::OctreeBase::LeafNode
OctreeLeafNode< LeafContainerT > LeafNode
Definition: octree_base.h:66
pcl::octree::OctreeBranchNode
Abstract octree branch class
Definition: octree_nodes.h:167
pcl::octree::OctreeBase::DepthFirstIterator
OctreeDepthFirstIterator< OctreeT > DepthFirstIterator
Definition: octree_base.h:160
pcl::octree::OctreeBase::octreeCanResize
bool octreeCanResize()
Test if octree is able to dynamically change its depth.
Definition: octree_base.h:699
pcl::octree::OctreeBase::getLeafCount
std::size_t getLeafCount() const
Return the amount of existing leafs in the octree.
Definition: octree_base.h:322
pcl::octree::OctreeBase::deserializeTreeCallback
virtual void deserializeTreeCallback(LeafContainerT &, const OctreeKey &)
Callback executed for every leaf node during deserialization.
Definition: octree_base.h:678
pcl::octree::OctreeIteratorBase
Abstract octree iterator class
Definition: octree_iterator.h:72
pcl::octree::OctreeBreadthFirstIterator
Octree iterator class
Definition: octree_iterator.h:463
pcl::octree::OctreeBase::dynamic_depth_enabled_
bool dynamic_depth_enabled_
Enable dynamic_depth.
Definition: octree_base.h:92
pcl::octree::OctreeBase::max_key_
OctreeKey max_key_
key range
Definition: octree_base.h:95
pcl::octree::OctreeBase::BranchNode
OctreeBranchNode< BranchContainerT > BranchNode
Definition: octree_base.h:65
pcl::octree::OctreeBase::BreadthFirstIterator
OctreeBreadthFirstIterator< OctreeT > BreadthFirstIterator
Definition: octree_base.h:177
pcl::octree::OctreeBase::getRootNode
OctreeNode * getRootNode() const
Retrieve root node.
Definition: octree_base.h:447
pcl::octree::OctreeBase::LeafNodeBreadthFirstIterator
OctreeLeafNodeBreadthFirstIterator< OctreeT > LeafNodeBreadthFirstIterator
Definition: octree_base.h:210
pcl::octree::OctreeBase::removeLeaf
void removeLeaf(const OctreeKey &key_arg)
Remove leaf node from octree.
Definition: octree_base.h:435
pcl::octree::OctreeBase::getTreeDepth
unsigned int getTreeDepth() const
Get the maximum depth of the octree.
Definition: octree_base.h:273
pcl::octree::OctreeBase::leaf_depth_begin
LeafNodeDepthFirstIterator leaf_depth_begin(unsigned int max_depth_arg=0u)
Definition: octree_base.h:147
pcl::octree::OctreeBase::LeafNodeDepthFirstIterator
OctreeLeafNodeDepthFirstIterator< OctreeT > LeafNodeDepthFirstIterator
Definition: octree_base.h:142
pcl::octree::OctreeBase::PCL_DEPRECATED
PCL_DEPRECATED("use std::log2 instead") double Log2(double n_arg)
Helper function to calculate the binary logarithm.
Definition: octree_base.h:689
pcl::octree::OctreeLeafNodeDepthFirstIterator
Octree leaf node iterator class.
Definition: octree_iterator.h:652
pcl::octree::OctreeDepthFirstIterator
Octree iterator class
Definition: octree_iterator.h:358
pcl::octree::OctreeBase::createLeaf
LeafContainerT * createLeaf(const OctreeKey &key_arg)
Create a leaf node.
Definition: octree_base.h:396
pcl::octree::OctreeBase::depth_begin
DepthFirstIterator depth_begin(unsigned int max_depth_arg=0u)
Definition: octree_base.h:164
pcl::octree::OctreeFixedDepthIterator
Octree iterator class
Definition: octree_iterator.h:563
pcl::octree::OctreeBase::deserializeTreeRecursive
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.
Definition: octree_base.hpp:494
pcl::octree::OctreeBranchNode::getChildPtr
OctreeNode * getChildPtr(unsigned char child_idx_arg) const
Get pointer to child.
Definition: octree_nodes.h:224
pcl::octree::OctreeLeafNodeBreadthFirstIterator
Octree leaf node iterator class.
Definition: octree_iterator.h:753
pcl::octree::OctreeBase::fixed_depth_begin
FixedDepthIterator fixed_depth_begin(unsigned int fixed_depth_arg=0u)
Definition: octree_base.h:198
pcl::octree::OctreeBase::getBranchBitPattern
char getBranchBitPattern(const BranchNode &branch_arg) const
Generate bit pattern reflecting the existence of child node pointers.
Definition: octree_base.h:493
pcl::octree::OctreeBase::findLeafRecursive
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.
Definition: octree_base.hpp:347
pcl::octree::OctreeBranchNode::hasChild
bool hasChild(unsigned char child_idx_arg) const
Check if branch is pointing to a particular child node.
Definition: octree_nodes.h:245
pcl::octree::OctreeBase::setBranchChildPtr
void setBranchChildPtr(BranchNode &branch_arg, unsigned char child_idx_arg, OctreeNode *new_child_arg)
Assign new child node to branch.
Definition: octree_base.h:481
pcl::octree::OctreeBase::leaf_breadth_begin
LeafNodeBreadthFirstIterator leaf_breadth_begin(unsigned int max_depth_arg=0u)
Definition: octree_base.h:215
pcl::octree::OctreeBase::leaf_count_
std::size_t leaf_count_
Amount of leaf nodes
Definition: octree_base.h:77
pcl::octree::OctreeBase::existLeaf
bool existLeaf(const OctreeKey &key_arg) const
Check for existence of a leaf node in the octree.
Definition: octree_base.h:426
pcl::octree::OctreeBase::leaf_begin
LeafNodeIterator leaf_begin(unsigned int max_depth_arg=0u)
Definition: octree_base.h:131
pcl::octree::OctreeBase::FixedDepthIterator
OctreeFixedDepthIterator< OctreeT > FixedDepthIterator
Definition: octree_base.h:194
pcl::octree::OctreeBase::breadth_end
const BreadthFirstIterator breadth_end()
Definition: octree_base.h:188
pcl::octree::OctreeBase::serializeTreeRecursive
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...
Definition: octree_base.hpp:437
pcl::octree::OctreeBase::getBranchCount
std::size_t getBranchCount() const
Return the amount of existing branch nodes in the octree.
Definition: octree_base.h:331
pcl::octree::OctreeBase::branch_count_
std::size_t branch_count_
Amount of branch nodes
Definition: octree_base.h:80
pcl::octree::OctreeLeafNode::getContainerPtr
const ContainerT * getContainerPtr() const
Get const pointer to container.
Definition: octree_nodes.h:141
pcl::octree::OctreeBase::deleteBranchChild
void deleteBranchChild(BranchNode &branch_arg, unsigned char child_idx_arg)
Delete child node and all its subchilds from octree.
Definition: octree_base.h:512
pcl::octree::OctreeContainerEmpty
Octree container class that does not store any information.
Definition: octree_container.h:116