Point Cloud Library (PCL)  1.7.1
octree_base.h
1 /*
2  * Software License Agreement (BSD License)
3  *
4  * Point Cloud Library (PCL) - www.pointclouds.org
5  * Copyright (c) 2010-2012, Willow Garage, Inc.
6  *
7  * All rights reserved.
8  *
9  * Redistribution and use in source and binary forms, with or without
10  * modification, are permitted provided that the following conditions
11  * are met:
12  *
13  * * Redistributions of source code must retain the above copyright
14  * notice, this list of conditions and the following disclaimer.
15  * * Redistributions in binary form must reproduce the above
16  * copyright notice, this list of conditions and the following
17  * disclaimer in the documentation and/or other materials provided
18  * with the distribution.
19  * * Neither the name of Willow Garage, Inc. nor the names of its
20  * contributors may be used to endorse or promote products derived
21  * from this software without specific prior written permission.
22  *
23  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
24  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
25  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
26  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
27  * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
28  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
29  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
30  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
31  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
32  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
33  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
34  * POSSIBILITY OF SUCH DAMAGE.
35  *
36  * $Id$
37  */
38 
39 #ifndef PCL_OCTREE_TREE_BASE_H
40 #define PCL_OCTREE_TREE_BASE_H
41 
42 #include <cstddef>
43 #include <vector>
44 
45 #include "octree_nodes.h"
46 #include "octree_container.h"
47 #include "octree_key.h"
48 #include "octree_iterator.h"
49 
50 namespace pcl
51 {
52  namespace octree
53  {
54  /** \brief Octree class
55  * \note The tree depth defines the maximum amount of octree voxels / leaf nodes (should be initially defined).
56  * \note All leaf nodes are addressed by integer indices.
57  * \note Note: The tree depth equates to the bit length of the voxel indices.
58  * \ingroup octree
59  * \author Julius Kammerl (julius@kammerl.de)
60  */
61  template<typename LeafContainerT = int,
62  typename BranchContainerT = OctreeContainerEmpty >
63  class OctreeBase
64  {
65 
66  public:
67 
69 
72 
73  typedef BranchContainerT BranchContainer;
74  typedef LeafContainerT LeafContainer;
75 
76  // iterators are friends
77  friend class OctreeIteratorBase<OctreeT> ;
81 
82  // Octree default iterators
85  Iterator begin(unsigned int max_depth_arg = 0) {return Iterator(this, max_depth_arg);};
86  const Iterator end() {return Iterator();};
87 
88  // Octree leaf node iterators
91  LeafNodeIterator leaf_begin(unsigned int max_depth_arg = 0) {return LeafNodeIterator(this, max_depth_arg);};
93 
94  // Octree depth-first iterators
97  DepthFirstIterator depth_begin(unsigned int max_depth_arg = 0) {return DepthFirstIterator(this, max_depth_arg);};
99 
100  // Octree breadth-first iterators
103  BreadthFirstIterator breadth_begin(unsigned int max_depth_arg = 0) {return BreadthFirstIterator(this, max_depth_arg);};
105 
106 
107  /** \brief Empty constructor. */
108  OctreeBase ();
109 
110  /** \brief Empty deconstructor. */
111  virtual
112  ~OctreeBase ();
113 
114  /** \brief Copy constructor. */
115  OctreeBase (const OctreeBase& source) :
116  leaf_count_ (source.leaf_count_),
117  branch_count_ (source.branch_count_),
118  root_node_ (new (BranchNode) (*(source.root_node_))),
119  depth_mask_ (source.depth_mask_),
120  octree_depth_ (source.octree_depth_),
122  max_key_ (source.max_key_)
123  {
124  }
125 
126  /** \brief Copy operator. */
127  OctreeBase&
128  operator = (const OctreeBase &source)
129  {
130  leaf_count_ = source.leaf_count_;
131  branch_count_ = source.branch_count_;
132  root_node_ = new (BranchNode) (*(source.root_node_));
133  depth_mask_ = source.depth_mask_;
134  max_key_ = source.max_key_;
135  octree_depth_ = source.octree_depth_;
136  return (*this);
137  }
138 
139  /** \brief Set the maximum amount of voxels per dimension.
140  * \param[in] max_voxel_index_arg maximum amount of voxels per dimension
141  */
142  void
143  setMaxVoxelIndex (unsigned int max_voxel_index_arg);
144 
145  /** \brief Set the maximum depth of the octree.
146  * \param max_depth_arg: maximum depth of octree
147  * */
148  void
149  setTreeDepth (unsigned int max_depth_arg);
150 
151  /** \brief Get the maximum depth of the octree.
152  * \return depth_arg: maximum depth of octree
153  * */
154  unsigned int
155  getTreeDepth () const
156  {
157  return this->octree_depth_;
158  }
159 
160  /** \brief Create new leaf node at (idx_x_arg, idx_y_arg, idx_z_arg).
161  * \note If leaf node already exist, this method returns the existing node
162  * \param idx_x_arg: index of leaf node in the X axis.
163  * \param idx_y_arg: index of leaf node in the Y axis.
164  * \param idx_z_arg: index of leaf node in the Z axis.
165  * \return pointer to new leaf node container.
166  * */
167  LeafContainerT*
168  createLeaf (unsigned int idx_x_arg, unsigned int idx_y_arg, unsigned int idx_z_arg);
169 
170  /** \brief Find leaf node at (idx_x_arg, idx_y_arg, idx_z_arg).
171  * \note If leaf node already exist, this method returns the existing node
172  * \param idx_x_arg: index of leaf node in the X axis.
173  * \param idx_y_arg: index of leaf node in the Y axis.
174  * \param idx_z_arg: index of leaf node in the Z axis.
175  * \return pointer to leaf node container if found, null pointer otherwise.
176  * */
177  LeafContainerT*
178  findLeaf (unsigned int idx_x_arg, unsigned int idx_y_arg, unsigned int idx_z_arg);
179 
180  /** \brief idx_x_arg for the existence of leaf node at (idx_x_arg, idx_y_arg, idx_z_arg).
181  * \param idx_x_arg: index of leaf node in the X axis.
182  * \param idx_y_arg: index of leaf node in the Y axis.
183  * \param idx_z_arg: index of leaf node in the Z axis.
184  * \return "true" if leaf node search is successful, otherwise it returns "false".
185  * */
186  bool
187  existLeaf (unsigned int idx_x_arg, unsigned int idx_y_arg, unsigned int idx_z_arg) const ;
188 
189  /** \brief Remove leaf node at (idx_x_arg, idx_y_arg, idx_z_arg).
190  * \param idx_x_arg: index of leaf node in the X axis.
191  * \param idx_y_arg: index of leaf node in the Y axis.
192  * \param idx_z_arg: index of leaf node in the Z axis.
193  * */
194  void
195  removeLeaf (unsigned int idx_x_arg, unsigned int idx_y_arg, unsigned int idx_z_arg);
196 
197  /** \brief Return the amount of existing leafs in the octree.
198  * \return amount of registered leaf nodes.
199  * */
200  std::size_t
201  getLeafCount () const
202  {
203  return leaf_count_;
204  }
205 
206  /** \brief Return the amount of existing branch nodes in the octree.
207  * \return amount of branch nodes.
208  * */
209  std::size_t
210  getBranchCount () const
211  {
212  return branch_count_;
213  }
214 
215  /** \brief Delete the octree structure and its leaf nodes.
216  * */
217  void
218  deleteTree ( );
219 
220  /** \brief Serialize octree into a binary output vector describing its branch node structure.
221  * \param binary_tree_out_arg: reference to output vector for writing binary tree structure.
222  * */
223  void
224  serializeTree (std::vector<char>& binary_tree_out_arg);
225 
226  /** \brief Serialize octree into a binary output vector describing its branch node structure and push all LeafContainerT elements stored in the octree to a vector.
227  * \param binary_tree_out_arg: reference to output vector for writing binary tree structure.
228  * \param leaf_container_vector_arg: pointer to all LeafContainerT objects in the octree
229  * */
230  void
231  serializeTree (std::vector<char>& binary_tree_out_arg, std::vector<LeafContainerT*>& leaf_container_vector_arg);
232 
233  /** \brief Outputs a vector of all LeafContainerT elements that are stored within the octree leaf nodes.
234  * \param leaf_container_vector_arg: pointers to LeafContainerT vector that receives a copy of all LeafContainerT objects in the octree.
235  * */
236  void
237  serializeLeafs (std::vector<LeafContainerT*>& leaf_container_vector_arg);
238 
239  /** \brief Deserialize a binary octree description vector and create a corresponding octree structure. Leaf nodes are initialized with getDataTByKey(..).
240  * \param binary_tree_input_arg: reference to input vector for reading binary tree structure.
241  * */
242  void
243  deserializeTree (std::vector<char>& binary_tree_input_arg);
244 
245  /** \brief Deserialize a binary octree description and create a corresponding octree structure. Leaf nodes are initialized with LeafContainerT elements from the dataVector.
246  * \param binary_tree_input_arg: reference to input vector for reading binary tree structure.
247  * \param leaf_container_vector_arg: pointer to container vector.
248  * */
249  void
250  deserializeTree (std::vector<char>& binary_tree_input_arg, std::vector<LeafContainerT*>& leaf_container_vector_arg);
251 
252  protected:
253 
254  //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
255  // Protected octree methods based on octree keys
256  //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
257 
258  /** \brief Create a leaf node
259  * \param key_arg: octree key addressing a leaf node.
260  * \return pointer to leaf node
261  * */
262  LeafContainerT*
263  createLeaf (const OctreeKey& key_arg)
264  {
265 
266  LeafNode* leaf_node;
267  BranchNode* leaf_node_parent;
268 
269  createLeafRecursive (key_arg, depth_mask_ ,root_node_, leaf_node, leaf_node_parent);
270 
271  LeafContainerT* ret = leaf_node->getContainerPtr();
272 
273  return ret;
274  }
275 
276  /** \brief Find leaf node
277  * \param key_arg: octree key addressing a leaf node.
278  * \return pointer to leaf node. If leaf node is not found, this pointer returns 0.
279  * */
280  LeafContainerT*
281  findLeaf (const OctreeKey& key_arg) const
282  {
283  LeafContainerT* result = 0;
284  findLeafRecursive (key_arg, depth_mask_, root_node_, result);
285  return result;
286  }
287 
288  /** \brief Check for existance of a leaf node in the octree
289  * \param key_arg: octree key addressing a leaf node.
290  * \return "true" if leaf node is found; "false" otherwise
291  * */
292  bool
293  existLeaf (const OctreeKey& key_arg) const
294  {
295  return (findLeaf(key_arg) != 0);
296  }
297 
298  /** \brief Remove leaf node from octree
299  * \param key_arg: octree key addressing a leaf node.
300  * */
301  void
302  removeLeaf (const OctreeKey& key_arg)
303  {
304  if (key_arg <= max_key_)
306  }
307 
308  //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
309  // Branch node access functions
310  //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
311 
312  /** \brief Retrieve root node */
313  OctreeNode*
314  getRootNode () const
315  {
316  return this->root_node_;
317  }
318 
319  /** \brief Check if branch is pointing to a particular child node
320  * \param branch_arg: reference to octree branch class
321  * \param child_idx_arg: index to child node
322  * \return "true" if pointer to child node exists; "false" otherwise
323  * */
324  bool
325  branchHasChild (const BranchNode& branch_arg,
326  unsigned char child_idx_arg) const
327  {
328  // test occupancyByte for child existence
329  return (branch_arg.getChildPtr(child_idx_arg) != 0);
330  }
331 
332  /** \brief Retrieve a child node pointer for child node at child_idx.
333  * \param branch_arg: reference to octree branch class
334  * \param child_idx_arg: index to child node
335  * \return pointer to octree child node class
336  */
337  OctreeNode*
338  getBranchChildPtr (const BranchNode& branch_arg,
339  unsigned char child_idx_arg) const
340  {
341  return branch_arg.getChildPtr(child_idx_arg);
342  }
343 
344  /** \brief Assign new child node to branch
345  * \param branch_arg: reference to octree branch class
346  * \param child_idx_arg: index to child node
347  * \param new_child_arg: pointer to new child node
348  * */
349  void setBranchChildPtr (BranchNode& branch_arg,
350  unsigned char child_idx_arg,
351  OctreeNode* new_child_arg)
352  {
353  branch_arg[child_idx_arg] = new_child_arg;
354  }
355 
356  /** \brief Generate bit pattern reflecting the existence of child node pointers
357  * \param branch_arg: reference to octree branch class
358  * \return a single byte with 8 bits of child node information
359  * */
360  char
361  getBranchBitPattern (const BranchNode& branch_arg) const
362  {
363  unsigned char i;
364  char node_bits;
365 
366  // create bit pattern
367  node_bits = 0;
368  for (i = 0; i < 8; i++) {
369  const OctreeNode* child = branch_arg.getChildPtr(i);
370  node_bits |= static_cast<char> ((!!child) << i);
371  }
372 
373  return (node_bits);
374  }
375 
376  /** \brief Delete child node and all its subchilds from octree
377  * \param branch_arg: reference to octree branch class
378  * \param child_idx_arg: index to child node
379  * */
380  void
381  deleteBranchChild (BranchNode& branch_arg, unsigned char child_idx_arg)
382  {
383  if (branch_arg.hasChild(child_idx_arg))
384  {
385  OctreeNode* branch_child = branch_arg[child_idx_arg];
386 
387  switch (branch_child->getNodeType ())
388  {
389  case BRANCH_NODE:
390  {
391  // free child branch recursively
392  deleteBranch (*static_cast<BranchNode*> (branch_child));
393  // delete branch node
394  delete branch_child;
395  }
396  break;
397 
398  case LEAF_NODE:
399  {
400  // delete leaf node
401  delete branch_child;
402  break;
403  }
404  default:
405  break;
406  }
407 
408  // set branch child pointer to 0
409  branch_arg[child_idx_arg] = 0;
410  }
411  }
412 
413  /** \brief Delete branch and all its subchilds from octree
414  * \param branch_arg: reference to octree branch class
415  * */
416  void
417  deleteBranch (BranchNode& branch_arg)
418  {
419  char i;
420 
421  // delete all branch node children
422  for (i = 0; i < 8; i++)
423  deleteBranchChild (branch_arg, i);
424  }
425 
426  /** \brief Create and add a new branch child to a branch class
427  * \param branch_arg: reference to octree branch class
428  * \param child_idx_arg: index to child node
429  * \return pointer of new branch child to this reference
430  * */
432  unsigned char child_idx_arg)
433  {
434  BranchNode* new_branch_child = new BranchNode();
435  branch_arg[child_idx_arg] = static_cast<OctreeNode*> (new_branch_child);
436 
437  return new_branch_child;
438  }
439 
440  /** \brief Create and add a new leaf child to a branch class
441  * \param branch_arg: reference to octree branch class
442  * \param child_idx_arg: index to child node
443  * \return pointer of new leaf child to this reference
444  * */
445  LeafNode*
446  createLeafChild (BranchNode& branch_arg, unsigned char child_idx_arg)
447  {
448  LeafNode* new_leaf_child = new LeafNode();
449  branch_arg[child_idx_arg] = static_cast<OctreeNode*> (new_leaf_child);
450 
451  return new_leaf_child;
452  }
453 
454  //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
455  // Recursive octree methods
456  //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
457 
458  /** \brief Create a leaf node at octree key. If leaf node does already exist, it is returned.
459  * \param key_arg: reference to an octree key
460  * \param depth_mask_arg: depth mask used for octree key analysis and for branch depth indicator
461  * \param branch_arg: current branch node
462  * \param return_leaf_arg: return pointer to leaf node
463  * \param parent_of_leaf_arg: return pointer to parent of leaf node
464  * \return depth mask at which leaf node was created
465  **/
466  unsigned int
467  createLeafRecursive (const OctreeKey& key_arg,
468  unsigned int depth_mask_arg,
469  BranchNode* branch_arg,
470  LeafNode*& return_leaf_arg,
471  BranchNode*& parent_of_leaf_arg);
472 
473  /** \brief Recursively search for a given leaf node and return a pointer.
474  * \note If leaf node does not exist, a 0 pointer is returned.
475  * \param key_arg: reference to an octree key
476  * \param depth_mask_arg: depth mask used for octree key analysis and for branch depth indicator
477  * \param branch_arg: current branch node
478  * \param result_arg: pointer to leaf node class
479  **/
480  void
481  findLeafRecursive (const OctreeKey& key_arg,
482  unsigned int depth_mask_arg,
483  BranchNode* branch_arg,
484  LeafContainerT*& result_arg) const;
485 
486  /** \brief Recursively search and delete leaf node
487  * \param key_arg: reference to an octree key
488  * \param depth_mask_arg: depth mask used for octree key analysis and branch depth indicator
489  * \param branch_arg: current branch node
490  * \return "true" if branch does not contain any childs; "false" otherwise. This indicates if current branch can be deleted, too.
491  **/
492  bool
493  deleteLeafRecursive (const OctreeKey& key_arg,
494  unsigned int depth_mask_arg,
495  BranchNode* branch_arg);
496 
497  /** \brief Recursively explore the octree and output binary octree description together with a vector of leaf node LeafContainerTs.
498  * \param branch_arg: current branch node
499  * \param key_arg: reference to an octree key
500  * \param binary_tree_out_arg: binary output vector
501  * \param leaf_container_vector_arg: writes LeafContainerT pointers to this LeafContainerT* vector.
502  **/
503  void
504  serializeTreeRecursive (const BranchNode* branch_arg,
505  OctreeKey& key_arg,
506  std::vector<char>* binary_tree_out_arg,
507  typename std::vector<LeafContainerT*>* leaf_container_vector_arg) const;
508 
509  /** \brief Recursive method for deserializing octree structure
510  * \param branch_arg: current branch node
511  * \param depth_mask_arg: depth mask used for octree key analysis and branch depth indicator
512  * \param key_arg: reference to an octree key
513  * \param binary_tree_input_it_arg: iterator to binary input vector
514  * \param binary_tree_input_it_end_arg: end iterator of binary input vector
515  * \param leaf_container_vector_it_arg: iterator pointing to current LeafContainerT object to be added to a leaf node
516  * \param leaf_container_vector_it_end_arg: iterator pointing to last object in LeafContainerT input vector.
517  **/
518  void
519  deserializeTreeRecursive (BranchNode* branch_arg, unsigned int depth_mask_arg, OctreeKey& key_arg,
520  typename std::vector<char>::const_iterator& binary_tree_input_it_arg,
521  typename std::vector<char>::const_iterator& binary_tree_input_it_end_arg,
522  typename std::vector<LeafContainerT*>::const_iterator* leaf_container_vector_it_arg,
523  typename std::vector<LeafContainerT*>::const_iterator* leaf_container_vector_it_end_arg);
524 
525 
526  //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
527  // Serialization callbacks
528  //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
529 
530  /** \brief Callback executed for every leaf node during serialization
531  **/
532  virtual void
533  serializeTreeCallback (LeafContainerT&, const OctreeKey &) const
534  {
535 
536  }
537 
538  /** \brief Callback executed for every leaf node during deserialization
539  **/
540  virtual void
541  deserializeTreeCallback (LeafContainerT&, const OctreeKey&)
542  {
543 
544  }
545 
546  //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
547  // Helpers
548  //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
549 
550  /** \brief Helper function to calculate the binary logarithm
551  * \param n_arg: some value
552  * \return binary logarithm (log2) of argument n_arg
553  */
554  double
555  Log2 (double n_arg)
556  {
557  return log( n_arg ) / log( 2.0 );
558  }
559 
560  /** \brief Test if octree is able to dynamically change its depth. This is required for adaptive bounding box adjustment.
561  * \return "true"
562  **/
563  bool
565  {
566  return (true);
567  }
568 
569  //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
570  // Globals
571  //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
572 
573  /** \brief Amount of leaf nodes **/
574  std::size_t leaf_count_;
575 
576  /** \brief Amount of branch nodes **/
577  std::size_t branch_count_;
578 
579  /** \brief Pointer to root branch node of octree **/
581 
582  /** \brief Depth mask based on octree depth **/
583  unsigned int depth_mask_;
584 
585  /** \brief Octree depth */
586  unsigned int octree_depth_;
587 
588  /** \brief Enable dynamic_depth **/
590 
591  /** \brief key range */
593  };
594  }
595 }
596 
597 //#include "impl/octree_base.hpp"
598 
599 #endif
600 
OctreeBase()
Empty constructor.
Definition: octree_base.hpp:54
const OctreeBreadthFirstIterator< OctreeT > ConstBreadthFirstIterator
Definition: octree_base.h:102
OctreeKey max_key_
key range
Definition: octree_base.h:592
Iterator begin(unsigned int max_depth_arg=0)
Definition: octree_base.h:85
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:431
void removeLeaf(const OctreeKey &key_arg)
Remove leaf node from octree.
Definition: octree_base.h:302
OctreeBase(const OctreeBase &source)
Copy constructor.
Definition: octree_base.h:115
BreadthFirstIterator breadth_begin(unsigned int max_depth_arg=0)
Definition: octree_base.h:103
LeafContainerT * createLeaf(const OctreeKey &key_arg)
Create a leaf node.
Definition: octree_base.h:263
const ContainerT * getContainerPtr() const
Get const pointer to container.
Definition: octree_nodes.h:179
LeafContainerT * findLeaf(const OctreeKey &key_arg) const
Find leaf node.
Definition: octree_base.h:281
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).
unsigned int depth_mask_
Depth mask based on octree depth.
Definition: octree_base.h:583
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).
Abstract octree leaf class
Definition: octree_nodes.h:98
bool deleteLeafRecursive(const OctreeKey &key_arg, unsigned int depth_mask_arg, BranchNode *branch_arg)
Recursively search and delete leaf node.
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:338
const OctreeDepthFirstIterator< OctreeT > ConstDepthFirstIterator
Definition: octree_base.h:96
std::size_t branch_count_
Amount of branch nodes.
Definition: octree_base.h:577
OctreeNode * getRootNode() const
Retrieve root node.
Definition: octree_base.h:314
Abstract octree branch class
Definition: octree_nodes.h:201
virtual void serializeTreeCallback(LeafContainerT &, const OctreeKey &) const
Callback executed for every leaf node during serialization.
Definition: octree_base.h:533
void deserializeTree(std::vector< char > &binary_tree_input_arg)
Deserialize a binary octree description vector and create a corresponding octree structure.
void setBranchChildPtr(BranchNode &branch_arg, unsigned char child_idx_arg, OctreeNode *new_child_arg)
Assign new child node to branch.
Definition: octree_base.h:349
OctreeDepthFirstIterator< OctreeT > DepthFirstIterator
Definition: octree_base.h:92
const BreadthFirstIterator breadth_end()
Definition: octree_base.h:104
BranchNode * root_node_
Pointer to root branch node of octree.
Definition: octree_base.h:580
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.
virtual void deserializeTreeCallback(LeafContainerT &, const OctreeKey &)
Callback executed for every leaf node during deserialization.
Definition: octree_base.h:541
bool hasChild(unsigned char child_idx_arg) const
Check if branch is pointing to a particular child node.
Definition: octree_nodes.h:289
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:446
virtual node_type_t getNodeType() const =0
Pure virtual method for receiving the type of octree node (branch or leaf)
OctreeNode * getChildPtr(unsigned char child_idx_arg) const
Get pointer to child.
Definition: octree_nodes.h:269
bool octreeCanResize()
Test if octree is able to dynamically change its depth.
Definition: octree_base.h:564
DepthFirstIterator depth_begin(unsigned int max_depth_arg=0)
Definition: octree_base.h:97
Abstract octree node class
Definition: octree_nodes.h:69
const DepthFirstIterator depth_end()
Definition: octree_base.h:98
OctreeBase & operator=(const OctreeBase &source)
Copy operator.
Definition: octree_base.h:128
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:325
OctreeLeafNodeIterator< OctreeT > LeafNodeIterator
Definition: octree_base.h:86
Octree key class
Definition: octree_key.h:53
bool dynamic_depth_enabled_
Enable dynamic_depth.
Definition: octree_base.h:589
void setTreeDepth(unsigned int max_depth_arg)
Set the maximum depth of the octree.
Definition: octree_base.hpp:93
std::size_t leaf_count_
Amount of leaf nodes.
Definition: octree_base.h:574
void serializeTree(std::vector< char > &binary_tree_out_arg)
Serialize octree into a binary output vector describing its branch node structure.
Octree class.
Definition: octree_base.h:63
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).
const OctreeLeafNodeIterator< OctreeT > ConstLeafNodeIterator
Definition: octree_base.h:90
void serializeLeafs(std::vector< LeafContainerT * > &leaf_container_vector_arg)
Outputs a vector of all LeafContainerT elements that are stored within the octree leaf nodes...
const OctreeDepthFirstIterator< OctreeT > ConstIterator
Definition: octree_base.h:84
BranchContainerT BranchContainer
Definition: octree_base.h:73
std::size_t getBranchCount() const
Return the amount of existing branch nodes in the octree.
Definition: octree_base.h:210
LeafContainerT LeafContainer
Definition: octree_base.h:74
double Log2(double n_arg)
Helper function to calculate the binary logarithm.
Definition: octree_base.h:555
Abstract octree iterator class
void deleteBranch(BranchNode &branch_arg)
Delete branch and all its subchilds from octree.
Definition: octree_base.h:417
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.
unsigned int octree_depth_
Octree depth.
Definition: octree_base.h:586
const LeafNodeIterator leaf_end()
Definition: octree_base.h:92
OctreeBase< LeafContainerT, BranchContainerT > OctreeT
Definition: octree_base.h:68
virtual ~OctreeBase()
Empty deconstructor.
Definition: octree_base.hpp:67
void setMaxVoxelIndex(unsigned int max_voxel_index_arg)
Set the maximum amount of voxels per dimension.
Definition: octree_base.hpp:77
void deleteTree()
Delete the octree structure and its leaf nodes.
std::size_t getLeafCount() const
Return the amount of existing leafs in the octree.
Definition: octree_base.h:201
Octree leaf node iterator class.
unsigned int getTreeDepth() const
Get the maximum depth of the octree.
Definition: octree_base.h:155
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).
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...
OctreeLeafNode< LeafContainerT > LeafNode
Definition: octree_base.h:71
const Iterator end()
Definition: octree_base.h:86
OctreeBreadthFirstIterator< OctreeT > BreadthFirstIterator
Definition: octree_base.h:98
OctreeDepthFirstIterator< OctreeT > Iterator
Definition: octree_base.h:83
void deleteBranchChild(BranchNode &branch_arg, unsigned char child_idx_arg)
Delete child node and all its subchilds from octree.
Definition: octree_base.h:381
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.
OctreeBranchNode< BranchContainerT > BranchNode
Definition: octree_base.h:70
bool existLeaf(const OctreeKey &key_arg) const
Check for existance of a leaf node in the octree.
Definition: octree_base.h:293
char getBranchBitPattern(const BranchNode &branch_arg) const
Generate bit pattern reflecting the existence of child node pointers.
Definition: octree_base.h:361
LeafNodeIterator leaf_begin(unsigned int max_depth_arg=0)
Definition: octree_base.h:91