Point Cloud Library (PCL)  1.7.1
octree2buf_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_2BUF_BASE_H
40 #define PCL_OCTREE_TREE_2BUF_BASE_H
41 
42 #include <vector>
43 
44 #include "octree_nodes.h"
45 #include "octree_container.h"
46 #include "octree_key.h"
47 #include "octree_iterator.h"
48 
49 #include <stdio.h>
50 #include <string.h>
51 
52 namespace pcl
53 {
54  namespace octree
55  {
56 
57  template<typename ContainerT>
59  {
60 
61  public:
62  /** \brief Empty constructor. */
64  {
65  reset ();
66  }
67 
68  /** \brief Copy constructor. */
70  {
71  *this = source;
72  }
73 
74  /** \brief Copy operator. */
75  inline BufferedBranchNode&
76  operator = (const BufferedBranchNode &source_arg)
77  {
78 
79  unsigned char i, b;
80 
81  memset (child_node_array_, 0, sizeof(child_node_array_));
82 
83  for (b = 0; b < 2; ++b)
84  for (i = 0; i < 8; ++i)
85  if (source_arg.child_node_array_[b][i])
86  child_node_array_[b][i] = source_arg.child_node_array_[b][i]->deepCopy ();
87 
88  return (*this);
89 
90  }
91 
92  /** \brief Empty constructor. */
94  {
95  }
96 
97  /** \brief Method to perform a deep copy of the octree */
98  virtual BufferedBranchNode*
99  deepCopy () const
100  {
101  return new BufferedBranchNode (*this);
102  }
103 
104  /** \brief Get child pointer in current branch node
105  * \param buffer_arg: buffer selector
106  * \param index_arg: index of child in node
107  * \return pointer to child node
108  * */
109  inline OctreeNode*
110  getChildPtr (unsigned char buffer_arg, unsigned char index_arg) const
111  {
112  assert( (buffer_arg<2) && (index_arg<8));
113  return child_node_array_[buffer_arg][index_arg];
114  }
115 
116  /** \brief Set child pointer in current branch node
117  * \param buffer_arg: buffer selector
118  * \param index_arg: index of child in node
119  * \param newNode_arg: pointer to new child node
120  * */
121  inline void setChildPtr (unsigned char buffer_arg, unsigned char index_arg,
122  OctreeNode* newNode_arg)
123  {
124  assert( (buffer_arg<2) && (index_arg<8));
125  child_node_array_[buffer_arg][index_arg] = newNode_arg;
126  }
127 
128  /** \brief Check if branch is pointing to a particular child node
129  * \param buffer_arg: buffer selector
130  * \param index_arg: index of child in node
131  * \return "true" if pointer to child node exists; "false" otherwise
132  * */
133  inline bool hasChild (unsigned char buffer_arg, unsigned char index_arg) const
134  {
135  assert( (buffer_arg<2) && (index_arg<8));
136  return (child_node_array_[buffer_arg][index_arg] != 0);
137  }
138 
139  /** \brief Get the type of octree node. Returns LEAVE_NODE type */
140  virtual node_type_t getNodeType () const
141  {
142  return BRANCH_NODE;
143  }
144 
145  /** \brief Reset branch node container for every branch buffer. */
146  inline void reset ()
147  {
148  memset (&child_node_array_[0][0], 0, sizeof(OctreeNode*) * 8 * 2);
149  }
150 
151  /** \brief Get const pointer to container */
152  const ContainerT*
153  operator->() const
154  {
155  return &container_;
156  }
157 
158  /** \brief Get pointer to container */
159  ContainerT*
161  {
162  return &container_;
163  }
164 
165  /** \brief Get const reference to container */
166  const ContainerT&
167  operator* () const
168  {
169  return container_;
170  }
171 
172  /** \brief Get reference to container */
173  ContainerT&
175  {
176  return container_;
177  }
178 
179  /** \brief Get const reference to container */
180  const ContainerT&
181  getContainer () const
182  {
183  return container_;
184  }
185 
186  /** \brief Get reference to container */
187  ContainerT&
189  {
190  return container_;
191  }
192 
193  /** \brief Get const pointer to container */
194  const ContainerT*
196  {
197  return &container_;
198  }
199 
200  /** \brief Get pointer to container */
201  ContainerT*
203  {
204  return &container_;
205  }
206 
207  protected:
208  ContainerT container_;
209 
211  };
212 
213  /** \brief @b Octree double buffer class
214  *
215  * \note This octree implementation keeps two separate octree structures
216  * in memory.
217  *
218  * \note This allows for differentially compare the octree structures (change detection, differential encoding).
219  * \note The tree depth defines the maximum amount of octree voxels / leaf nodes (should be initially defined).
220  * \note All leaf nodes are addressed by integer indices.
221  * \note Note: The tree depth equates to the bit length of the voxel indices.
222  * \ingroup octree
223  * \author Julius Kammerl (julius@kammerl.de)
224  */
225  template<typename LeafContainerT = int,
226  typename BranchContainerT = OctreeContainerEmpty >
228  {
229 
230  public:
231 
233 
234  // iterators are friends
235  friend class OctreeIteratorBase<OctreeT> ;
239 
242 
243  typedef BranchContainerT BranchContainer;
244  typedef LeafContainerT LeafContainer;
245 
246  // Octree default iterators
249  Iterator begin(unsigned int max_depth_arg = 0) {return Iterator(this, max_depth_arg);};
250  const Iterator end() {return Iterator();};
251 
252  // Octree leaf node iterators
255  LeafNodeIterator leaf_begin(unsigned int max_depth_arg = 0) {return LeafNodeIterator(this, max_depth_arg);};
257 
258  // Octree depth-first iterators
261  DepthFirstIterator depth_begin(unsigned int maxDepth_arg = 0) {return DepthFirstIterator(this, maxDepth_arg);};
263 
264  // Octree breadth-first iterators
267  BreadthFirstIterator breadth_begin(unsigned int max_depth_arg = 0) {return BreadthFirstIterator(this, max_depth_arg);};
269 
270  /** \brief Empty constructor. */
271  Octree2BufBase ();
272 
273  /** \brief Empty deconstructor. */
274  virtual
275  ~Octree2BufBase ();
276 
277  /** \brief Copy constructor. */
278  Octree2BufBase (const Octree2BufBase& source) :
279  leaf_count_ (source.leaf_count_),
280  branch_count_ (source.branch_count_),
281  root_node_ (new (BranchNode) (*(source.root_node_))),
282  depth_mask_ (source.depth_mask_),
283  max_key_ (source.max_key_),
286  octree_depth_ (source.octree_depth_),
288  {
289  }
290 
291  /** \brief Copy constructor. */
292  inline Octree2BufBase&
294  {
295  leaf_count_ = source.leaf_count_;
296  branch_count_ = source.branch_count_;
297  root_node_ = new (BranchNode) (* (source.root_node_));
298  depth_mask_ = source.depth_mask_;
299  max_key_ = source.max_key_;
302  octree_depth_ = source.octree_depth_;
304  return (*this);
305  }
306 
307  /** \brief Set the maximum amount of voxels per dimension.
308  * \param max_voxel_index_arg: maximum amount of voxels per dimension
309  * */
310  void
311  setMaxVoxelIndex (unsigned int max_voxel_index_arg);
312 
313  /** \brief Set the maximum depth of the octree.
314  * \param depth_arg: maximum depth of octree
315  * */
316  void
317  setTreeDepth (unsigned int depth_arg);
318 
319  /** \brief Get the maximum depth of the octree.
320  * \return depth_arg: maximum depth of octree
321  * */
322  inline unsigned int getTreeDepth () const
323  {
324  return this->octree_depth_;
325  }
326 
327  /** \brief Create new leaf node at (idx_x_arg, idx_y_arg, idx_z_arg).
328  * \note If leaf node already exist, this method returns the existing node
329  * \param idx_x_arg: index of leaf node in the X axis.
330  * \param idx_y_arg: index of leaf node in the Y axis.
331  * \param idx_z_arg: index of leaf node in the Z axis.
332  * \return pointer to new leaf node container.
333  * */
334  LeafContainerT*
335  createLeaf (unsigned int idx_x_arg, unsigned int idx_y_arg, unsigned int idx_z_arg);
336 
337  /** \brief Find leaf node at (idx_x_arg, idx_y_arg, idx_z_arg).
338  * \note If leaf node already exist, this method returns the existing node
339  * \param idx_x_arg: index of leaf node in the X axis.
340  * \param idx_y_arg: index of leaf node in the Y axis.
341  * \param idx_z_arg: index of leaf node in the Z axis.
342  * \return pointer to leaf node container if found, null pointer otherwise.
343  * */
344  LeafContainerT*
345  findLeaf (unsigned int idx_x_arg, unsigned int idx_y_arg, unsigned int idx_z_arg);
346 
347  /** \brief Check for the existence of leaf node at (idx_x_arg, idx_y_arg, idx_z_arg).
348  * \param idx_x_arg: index of leaf node in the X axis.
349  * \param idx_y_arg: index of leaf node in the Y axis.
350  * \param idx_z_arg: index of leaf node in the Z axis.
351  * \return "true" if leaf node search is successful, otherwise it returns "false".
352  * */
353  bool
354  existLeaf (unsigned int idx_x_arg, unsigned int idx_y_arg, unsigned int idx_z_arg) const;
355 
356  /** \brief Remove leaf node at (idx_x_arg, idx_y_arg, idx_z_arg).
357  * \param idx_x_arg: index of leaf node in the X axis.
358  * \param idx_y_arg: index of leaf node in the Y axis.
359  * \param idx_z_arg: index of leaf node in the Z axis.
360  * */
361  void
362  removeLeaf (unsigned int idx_x_arg, unsigned int idx_y_arg, unsigned int idx_z_arg);
363 
364  /** \brief Return the amount of existing leafs in the octree.
365  * \return amount of registered leaf nodes.
366  * */
367  inline std::size_t getLeafCount () const
368  {
369  return (leaf_count_);
370  }
371 
372  /** \brief Return the amount of existing branches in the octree.
373  * \return amount of branch nodes.
374  * */
375  inline std::size_t getBranchCount () const
376  {
377  return (branch_count_);
378  }
379 
380  /** \brief Delete the octree structure and its leaf nodes.
381  * */
382  void
383  deleteTree ();
384 
385  /** \brief Delete octree structure of previous buffer. */
386  inline void deletePreviousBuffer ()
387  {
389  }
390 
391  /** \brief Delete the octree structure in the current buffer. */
392  inline void deleteCurrentBuffer ()
393  {
396  leaf_count_ = 0;
397  }
398 
399  /** \brief Switch buffers and reset current octree structure. */
400  void
401  switchBuffers ();
402 
403  /** \brief Serialize octree into a binary output vector describing its branch node structure.
404  * \param binary_tree_out_arg: reference to output vector for writing binary tree structure.
405  * \param do_XOR_encoding_arg: select if binary tree structure should be generated based on current octree (false) of based on a XOR comparison between current and previous octree
406  * */
407  void
408  serializeTree (std::vector<char>& binary_tree_out_arg,
409  bool do_XOR_encoding_arg = false);
410 
411  /** \brief Serialize octree into a binary output vector describing its branch node structure and and push all DataT elements stored in the octree to a vector.
412  * \param binary_tree_out_arg: reference to output vector for writing binary tree structure.
413  * \param leaf_container_vector_arg: pointer to all LeafContainerT objects in the octree
414  * \param do_XOR_encoding_arg: select if binary tree structure should be generated based on current octree (false) of based on a XOR comparison between current and previous octree
415  * */
416  void
417  serializeTree (std::vector<char>& binary_tree_out_arg,
418  std::vector<LeafContainerT*>& leaf_container_vector_arg,
419  bool do_XOR_encoding_arg = false);
420 
421  /** \brief Outputs a vector of all DataT elements that are stored within the octree leaf nodes.
422  * \param leaf_container_vector_arg: vector of pointers to all LeafContainerT objects in the octree
423  * */
424  void
425  serializeLeafs (std::vector<LeafContainerT*>& leaf_container_vector_arg);
426 
427  /** \brief Outputs a vector of all DataT elements from leaf nodes, that do not exist in the previous octree buffer.
428  * \param leaf_container_vector_arg: vector of pointers to all LeafContainerT objects in the octree
429  * */
430  void
431  serializeNewLeafs (std::vector<LeafContainerT*>& leaf_container_vector_arg);
432 
433  /** \brief Deserialize a binary octree description vector and create a corresponding octree structure. Leaf nodes are initialized with getDataTByKey(..).
434  * \param binary_tree_in_arg: reference to input vector for reading binary tree structure.
435  * \param do_XOR_decoding_arg: select if binary tree structure is based on current octree (false) of based on a XOR comparison between current and previous octree
436  * */
437  void
438  deserializeTree (std::vector<char>& binary_tree_in_arg,
439  bool do_XOR_decoding_arg = false);
440 
441  /** \brief Deserialize a binary octree description and create a corresponding octree structure. Leaf nodes are initialized with DataT elements from the dataVector.
442  * \param binary_tree_in_arg: reference to inpvectoream for reading binary tree structure.
443  * \param leaf_container_vector_arg: vector of pointers to all LeafContainerT objects in the octree
444  * \param do_XOR_decoding_arg: select if binary tree structure is based on current octree (false) of based on a XOR comparison between current and previous octree
445  * */
446  void
447  deserializeTree (std::vector<char>& binary_tree_in_arg,
448  std::vector<LeafContainerT*>& leaf_container_vector_arg,
449  bool do_XOR_decoding_arg = false);
450 
451  protected:
452 
453  //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
454  // Protected octree methods based on octree keys
455  //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
456 
457  /** \brief Retrieve root node */
458  OctreeNode*
459  getRootNode () const
460  {
461  return (this->root_node_);
462  }
463 
464  /** \brief Find leaf node
465  * \param key_arg: octree key addressing a leaf node.
466  * \return pointer to leaf container. If leaf node is not found, this pointer returns 0.
467  * */
468  inline LeafContainerT*
469  findLeaf (const OctreeKey& key_arg) const
470  {
471  LeafContainerT* result = 0;
472  findLeafRecursive (key_arg, depth_mask_, root_node_, result);
473  return result;
474  }
475 
476  /** \brief Create a leaf node.
477  * \note If the leaf node at the given octree node does not exist, it will be created and added to the tree.
478  * \param key_arg: octree key addressing a leaf node.
479  * \return pointer to an existing or created leaf container.
480  * */
481  inline LeafContainerT*
482  createLeaf (const OctreeKey& key_arg)
483  {
484  LeafNode* leaf_node;
485  BranchNode* leaf_node_parent;
486 
487  createLeafRecursive (key_arg, depth_mask_ ,root_node_, leaf_node, leaf_node_parent, false);
488 
489  LeafContainerT* ret = leaf_node->getContainerPtr();
490 
491  return ret;
492  }
493 
494  /** \brief Check for leaf not existance in the octree
495  * \param key_arg: octree key addressing a leaf node.
496  * \return "true" if leaf node is found; "false" otherwise
497  * */
498  inline bool existLeaf (const OctreeKey& key_arg) const
499  {
500  return (findLeaf(key_arg) != 0);
501  }
502 
503  /** \brief Remove leaf node from octree
504  * \param key_arg: octree key addressing a leaf node.
505  * */
506  inline void removeLeaf (const OctreeKey& key_arg)
507  {
508  if (key_arg <= max_key_)
509  {
511 
512  // we changed the octree structure -> dirty
513  tree_dirty_flag_ = true;
514  }
515  }
516 
517  //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
518  // Branch node accessor inline functions
519  //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
520 
521  /** \brief Check if branch is pointing to a particular child node
522  * \param branch_arg: reference to octree branch class
523  * \param child_idx_arg: index to child node
524  * \return "true" if pointer to child node exists; "false" otherwise
525  * */
526  inline bool
527  branchHasChild (const BranchNode& branch_arg, unsigned char child_idx_arg) const
528  {
529  // test occupancyByte for child existence
530  return (branch_arg.getChildPtr(buffer_selector_, child_idx_arg) != 0);
531  }
532 
533  /** \brief Retrieve a child node pointer for child node at child_idx.
534  * \param branch_arg: reference to octree branch class
535  * \param child_idx_arg: index to child node
536  * \return pointer to octree child node class
537  */
538  inline OctreeNode*
539  getBranchChildPtr (const BranchNode& branch_arg,
540  unsigned char child_idx_arg) const
541  {
542  return branch_arg.getChildPtr(buffer_selector_, child_idx_arg);
543  }
544 
545  /** \brief Assign new child node to branch
546  * \param branch_arg: reference to octree branch class
547  * \param child_idx_arg: index to child node
548  * \param new_child_arg: pointer to new child node
549  * */
550  inline void
551  setBranchChildPtr (BranchNode& branch_arg, unsigned char child_idx_arg, OctreeNode* new_child_arg)
552  {
553  branch_arg.setChildPtr (buffer_selector_, child_idx_arg, new_child_arg);
554  }
555 
556  /** \brief Generate bit pattern reflecting the existence of child node pointers for current buffer
557  * \param branch_arg: reference to octree branch class
558  * \return a single byte with 8 bits of child node information
559  * */
560  inline char getBranchBitPattern (const BranchNode& branch_arg) const
561  {
562  unsigned char i;
563  char node_bits;
564 
565  // create bit pattern
566  node_bits = 0;
567  for (i = 0; i < 8; i++)
568  {
569  const OctreeNode* child = branch_arg.getChildPtr(buffer_selector_, i);
570  node_bits |= static_cast<char> ( (!!child) << i);
571  }
572 
573  return (node_bits);
574  }
575 
576  /** \brief Generate bit pattern reflecting the existence of child node pointers in specific buffer
577  * \param branch_arg: reference to octree branch class
578  * \param bufferSelector_arg: buffer selector
579  * \return a single byte with 8 bits of child node information
580  * */
581  inline char getBranchBitPattern (const BranchNode& branch_arg,
582  unsigned char bufferSelector_arg) const
583  {
584  unsigned char i;
585  char node_bits;
586 
587  // create bit pattern
588  node_bits = 0;
589  for (i = 0; i < 8; i++)
590  {
591  const OctreeNode* child = branch_arg.getChildPtr(bufferSelector_arg, i);
592  node_bits |= static_cast<char> ( (!!child) << i);
593  }
594 
595  return (node_bits);
596  }
597 
598  /** \brief Generate XOR bit pattern reflecting differences between the two octree buffers
599  * \param branch_arg: reference to octree branch class
600  * \return a single byte with 8 bits of child node XOR difference information
601  * */
603  const BranchNode& branch_arg) const
604  {
605  unsigned char i;
606  char node_bits[2];
607 
608  // create bit pattern for both buffers
609  node_bits[0] = node_bits[1] = 0;
610 
611  for (i = 0; i < 8; i++)
612  {
613  const OctreeNode* childA = branch_arg.getChildPtr(0, i);
614  const OctreeNode* childB = branch_arg.getChildPtr(1, i);
615 
616  node_bits[0] |= static_cast<char> ( (!!childA) << i);
617  node_bits[1] |= static_cast<char> ( (!!childB) << i);
618  }
619 
620  return node_bits[0] ^ node_bits[1];
621  }
622 
623  /** \brief Test if branch changed between previous and current buffer
624  * \param branch_arg: reference to octree branch class
625  * \return "true", if child node information differs between current and previous octree buffer
626  * */
627  inline bool hasBranchChanges (const BranchNode& branch_arg) const
628  {
629  return (getBranchXORBitPattern (branch_arg) > 0);
630  }
631 
632  /** \brief Delete child node and all its subchilds from octree in specific buffer
633  * \param branch_arg: reference to octree branch class
634  * \param buffer_selector_arg: buffer selector
635  * \param child_idx_arg: index to child node
636  * */
637  inline void deleteBranchChild (BranchNode& branch_arg,
638  unsigned char buffer_selector_arg,
639  unsigned char child_idx_arg)
640  {
641  if (branch_arg.hasChild(buffer_selector_arg, child_idx_arg))
642  {
643  OctreeNode* branchChild = branch_arg.getChildPtr(buffer_selector_arg, child_idx_arg);
644 
645  switch (branchChild->getNodeType ())
646  {
647  case BRANCH_NODE:
648  {
649  // free child branch recursively
650  deleteBranch (*static_cast<BranchNode*> (branchChild));
651 
652  // delete unused branch
653  delete (branchChild);
654  break;
655  }
656 
657  case LEAF_NODE:
658  {
659  // push unused leaf to branch pool
660  delete (branchChild);
661  break;
662  }
663  default:
664  break;
665  }
666 
667  // set branch child pointer to 0
668  branch_arg.setChildPtr(buffer_selector_arg, child_idx_arg, 0);
669  }
670  }
671 
672  /** \brief Delete child node and all its subchilds from octree in current buffer
673  * \param branch_arg: reference to octree branch class
674  * \param child_idx_arg: index to child node
675  * */
676  inline void deleteBranchChild (BranchNode& branch_arg, unsigned char child_idx_arg)
677  {
678  deleteBranchChild(branch_arg, buffer_selector_, child_idx_arg);
679  }
680 
681  /** \brief Delete branch and all its subchilds from octree (both buffers)
682  * \param branch_arg: reference to octree branch class
683  * */
684  inline void deleteBranch (BranchNode& branch_arg)
685  {
686  char i;
687 
688  // delete all branch node children
689  for (i = 0; i < 8; i++)
690  {
691 
692  if (branch_arg.getChildPtr(0, i) == branch_arg.getChildPtr(1, i))
693  {
694  // reference was copied - there is only one child instance to be deleted
695  deleteBranchChild (branch_arg, 0, i);
696 
697  // remove pointers from both buffers
698  branch_arg.setChildPtr(0, i, 0);
699  branch_arg.setChildPtr(1, i, 0);
700  }
701  else
702  {
703  deleteBranchChild (branch_arg, 0, i);
704  deleteBranchChild (branch_arg, 1, i);
705  }
706  }
707  }
708 
709  /** \brief Fetch and add a new branch child to a branch class in current buffer
710  * \param branch_arg: reference to octree branch class
711  * \param child_idx_arg: index to child node
712  * \return pointer of new branch child to this reference
713  * */
715  unsigned char child_idx_arg)
716  {
717  BranchNode* new_branch_child = new BranchNode();
718 
719  branch_arg.setChildPtr (buffer_selector_, child_idx_arg,
720  static_cast<OctreeNode*> (new_branch_child));
721 
722  return new_branch_child;
723  }
724 
725  /** \brief Fetch and add a new leaf child to a branch class
726  * \param branch_arg: reference to octree branch class
727  * \param child_idx_arg: index to child node
728  * \return pointer of new leaf child to this reference
729  * */
730  inline LeafNode*
731  createLeafChild (BranchNode& branch_arg, unsigned char child_idx_arg)
732  {
733  LeafNode* new_leaf_child = new LeafNode();
734 
735  branch_arg.setChildPtr(buffer_selector_, child_idx_arg, new_leaf_child);
736 
737  return new_leaf_child;
738  }
739 
740  //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
741  // Recursive octree methods
742  //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
743 
744  /** \brief Create a leaf node at octree key. If leaf node does already exist, it is returned.
745  * \param key_arg: reference to an octree key
746  * \param depth_mask_arg: depth mask used for octree key analysis and for branch depth indicator
747  * \param branch_arg: current branch node
748  * \param return_leaf_arg: return pointer to leaf container
749  * \param parent_of_leaf_arg: return pointer to parent of leaf node
750  * \param branch_reset_arg: Reset pointer array of current branch
751  * \return depth mask at which leaf node was created/found
752  **/
753  unsigned int
754  createLeafRecursive (const OctreeKey& key_arg,
755  unsigned int depth_mask_arg,
756  BranchNode* branch_arg,
757  LeafNode*& return_leaf_arg,
758  BranchNode*& parent_of_leaf_arg,
759  bool branch_reset_arg = false);
760 
761 
762  /** \brief Recursively search for a given leaf node and return a pointer.
763  * \note If leaf node does not exist, a 0 pointer is returned.
764  * \param key_arg: reference to an octree key
765  * \param depth_mask_arg: depth mask used for octree key analysis and for branch depth indicator
766  * \param branch_arg: current branch node
767  * \param result_arg: pointer to leaf container class
768  **/
769  void
770  findLeafRecursive (const OctreeKey& key_arg,
771  unsigned int depth_mask_arg,
772  BranchNode* branch_arg,
773  LeafContainerT*& result_arg) const;
774 
775 
776  /** \brief Recursively search and delete leaf node
777  * \param key_arg: reference to an octree key
778  * \param depth_mask_arg: depth mask used for octree key analysis and branch depth indicator
779  * \param branch_arg: current branch node
780  * \return "true" if branch does not contain any childs; "false" otherwise. This indicates if current branch can be deleted.
781  **/
782  bool
783  deleteLeafRecursive (const OctreeKey& key_arg,
784  unsigned int depth_mask_arg,
785  BranchNode* branch_arg);
786 
787  /** \brief Recursively explore the octree and output binary octree description together with a vector of leaf node DataT content.
788  * \param branch_arg: current branch node
789  * \param key_arg: reference to an octree key
790  * \param binary_tree_out_arg: binary output vector
791  * \param leaf_container_vector_arg: vector to return pointers to all leaf container in the tree.
792  * \param do_XOR_encoding_arg: select if binary tree structure should be generated based on current octree (false) of based on a XOR comparison between current and previous octree
793  * \param new_leafs_filter_arg: execute callback only for leaf nodes that did not exist in preceding buffer
794  **/
795  void
796  serializeTreeRecursive (BranchNode* branch_arg,
797  OctreeKey& key_arg,
798  std::vector<char>* binary_tree_out_arg,
799  typename std::vector<LeafContainerT*>* leaf_container_vector_arg,
800  bool do_XOR_encoding_arg = false,
801  bool new_leafs_filter_arg = false);
802 
803  /** \brief Rebuild an octree based on binary XOR octree description and DataT objects for leaf node initialization.
804  * \param branch_arg: current branch node
805  * \param depth_mask_arg: depth mask used for octree key analysis and branch depth indicator
806  * \param key_arg: reference to an octree key
807  * \param binary_tree_in_it_arg iterator of binary input data
808  * \param leaf_container_vector__it_end_arg end iterator of binary input data
809  * \param leaf_container_vector_it_arg: iterator pointing to leaf containter pointers to be added to a leaf node
810  * \param leaf_container_vector_it_end_arg: iterator pointing to leaf containter pointers pointing to last object in input container.
811  * \param branch_reset_arg: Reset pointer array of current branch
812  * \param do_XOR_decoding_arg: select if binary tree structure is based on current octree (false) of based on a XOR comparison between current and previous octree
813  **/
814  void
816  unsigned int depth_mask_arg,
817  OctreeKey& key_arg,
818  typename std::vector<char>::const_iterator& binary_tree_in_it_arg,
819  typename std::vector<char>::const_iterator& binary_tree_in_it_end_arg,
820  typename std::vector<LeafContainerT*>::const_iterator* leaf_container_vector_it_arg,
821  typename std::vector<LeafContainerT*>::const_iterator* leaf_container_vector_it_end_arg,
822  bool branch_reset_arg = false,
823  bool do_XOR_decoding_arg = false);
824 
825 
826  //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
827  // Serialization callbacks
828  //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
829 
830  /** \brief Callback executed for every leaf node data during serialization
831  **/
832  virtual void serializeTreeCallback (LeafContainerT &, const OctreeKey &)
833  {
834 
835  }
836 
837  /** \brief Callback executed for every leaf node data during deserialization
838  **/
839  virtual void deserializeTreeCallback (LeafContainerT&, const OctreeKey&)
840  {
841 
842  }
843 
844  //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
845  // Helpers
846  //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
847 
848  /** \brief Recursively explore the octree and remove unused branch and leaf nodes
849  * \param branch_arg: current branch node
850  **/
851  void
852  treeCleanUpRecursive (BranchNode* branch_arg);
853 
854  /** \brief Helper function to calculate the binary logarithm
855  * \param n_arg: some value
856  * \return binary logarithm (log2) of argument n_arg
857  */
858  inline double Log2 (double n_arg)
859  {
860  return log (n_arg) / log (2.0);
861  }
862 
863  /** \brief Test if octree is able to dynamically change its depth. This is required for adaptive bounding box adjustment.
864  * \return "false" - not resizeable due to XOR serialization
865  **/
866  inline bool octreeCanResize ()
867  {
868  return (false);
869  }
870 
871  /** \brief Prints binary representation of a byte - used for debugging
872  * \param data_arg - byte to be printed to stdout
873  **/
874  inline void printBinary (char data_arg)
875  {
876  unsigned char mask = 1; // Bit mask
877 
878  // Extract the bits
879  for (int i = 0; i < 8; i++)
880  {
881  // Mask each bit in the byte and print it
882  std::cout << ((data_arg & (mask << i)) ? "1" : "0");
883  }
884  std::cout << std::endl;
885  }
886 
887  //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
888  // Globals
889  //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
890 
891  /** \brief Amount of leaf nodes **/
892  std::size_t leaf_count_;
893 
894  /** \brief Amount of branch nodes **/
895  std::size_t branch_count_;
896 
897  /** \brief Pointer to root branch node of octree **/
899 
900  /** \brief Depth mask based on octree depth **/
901  unsigned int depth_mask_;
902 
903  /** \brief key range */
905 
906  /** \brief Currently active octree buffer **/
907  unsigned char buffer_selector_;
908 
909  // flags indicating if unused branches and leafs might exist in previous buffer
911 
912  /** \brief Octree depth */
913  unsigned int octree_depth_;
914 
915  /** \brief Enable dynamic_depth
916  * \note Note that this parameter is ignored in octree2buf! */
918 
919  };
920  }
921 }
922 
923 //#include "impl/octree2buf_base.hpp"
924 
925 #endif
926 
BranchNode * root_node_
Pointer to root branch node of octree.
OctreeLeafNodeIterator< OctreeT > LeafNodeIterator
const ContainerT & operator*() const
Get const reference to container.
void switchBuffers()
Switch buffers and reset current octree structure.
char getBranchBitPattern(const BranchNode &branch_arg) const
Generate bit pattern reflecting the existence of child node pointers for current buffer.
Octree2BufBase(const Octree2BufBase &source)
Copy constructor.
std::size_t branch_count_
Amount of branch nodes.
const ContainerT & getContainer() const
Get const reference to container.
Iterator begin(unsigned int max_depth_arg=0)
BranchContainerT BranchContainer
std::size_t getBranchCount() const
Return the amount of existing branches in the octree.
virtual OctreeNode * deepCopy() const =0
Pure virtual method to perform a deep copy of the octree.
const OctreeBreadthFirstIterator< OctreeT > ConstBreadthFirstIterator
OctreeDepthFirstIterator< OctreeT > Iterator
void deserializeTree(std::vector< char > &binary_tree_in_arg, bool do_XOR_decoding_arg=false)
Deserialize a binary octree description vector and create a corresponding octree structure.
BranchNode * createBranchChild(BranchNode &branch_arg, unsigned char child_idx_arg)
Fetch and add a new branch child to a branch class in current buffer.
bool deleteLeafRecursive(const OctreeKey &key_arg, unsigned int depth_mask_arg, BranchNode *branch_arg)
Recursively search and delete leaf node.
const ContainerT * getContainerPtr() const
Get const pointer to container.
Definition: octree_nodes.h:179
const ContainerT * getContainerPtr() const
Get const pointer to container.
BufferedBranchNode & operator=(const BufferedBranchNode &source_arg)
Copy operator.
const LeafNodeIterator leaf_end()
Abstract octree leaf class
Definition: octree_nodes.h:98
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).
BufferedBranchNode()
Empty constructor.
char getBranchXORBitPattern(const BranchNode &branch_arg) const
Generate XOR bit pattern reflecting differences between the two octree buffers.
double Log2(double n_arg)
Helper function to calculate the binary logarithm.
void setChildPtr(unsigned char buffer_arg, unsigned char index_arg, OctreeNode *newNode_arg)
Set child pointer in current branch node.
const OctreeDepthFirstIterator< OctreeT > ConstDepthFirstIterator
LeafNodeIterator leaf_begin(unsigned int max_depth_arg=0)
void setBranchChildPtr(BranchNode &branch_arg, unsigned char child_idx_arg, OctreeNode *new_child_arg)
Assign new child node to branch.
bool existLeaf(unsigned int idx_x_arg, unsigned int idx_y_arg, unsigned int idx_z_arg) const
Check for the existence of leaf node at (idx_x_arg, idx_y_arg, idx_z_arg).
void serializeTree(std::vector< char > &binary_tree_out_arg, bool do_XOR_encoding_arg=false)
Serialize octree into a binary output vector describing its branch node structure.
void serializeLeafs(std::vector< LeafContainerT * > &leaf_container_vector_arg)
Outputs a vector of all DataT elements that are stored within the octree leaf nodes.
bool hasChild(unsigned char buffer_arg, unsigned char index_arg) const
Check if branch is pointing to a particular child node.
virtual void serializeTreeCallback(LeafContainerT &, const OctreeKey &)
Callback executed for every leaf node data during serialization.
char getBranchBitPattern(const BranchNode &branch_arg, unsigned char bufferSelector_arg) const
Generate bit pattern reflecting the existence of child node pointers in specific buffer.
unsigned int octree_depth_
Octree depth.
DepthFirstIterator depth_begin(unsigned int maxDepth_arg=0)
bool existLeaf(const OctreeKey &key_arg) const
Check for leaf not existance in the octree.
virtual node_type_t getNodeType() const =0
Pure virtual method for receiving the type of octree node (branch or leaf)
Abstract octree node class
Definition: octree_nodes.h:69
OctreeNode * getChildPtr(unsigned char buffer_arg, unsigned char index_arg) const
Get child pointer in current branch node.
void setTreeDepth(unsigned int depth_arg)
Set the maximum depth of the octree.
void printBinary(char data_arg)
Prints binary representation of a byte - used for debugging.
unsigned int getTreeDepth() const
Get the maximum depth of the octree.
OctreeNode * getRootNode() const
Retrieve root node.
Octree key class
Definition: octree_key.h:53
const DepthFirstIterator depth_end()
LeafContainerT * createLeaf(const OctreeKey &key_arg)
Create a leaf node.
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.
const OctreeLeafNodeIterator< OctreeT > ConstLeafNodeIterator
OctreeKey max_key_
key range
bool octreeCanResize()
Test if octree is able to dynamically change its depth.
void treeCleanUpRecursive(BranchNode *branch_arg)
Recursively explore the octree and remove unused branch and leaf nodes.
std::size_t leaf_count_
Amount of leaf nodes.
void setMaxVoxelIndex(unsigned int max_voxel_index_arg)
Set the maximum amount of voxels per dimension.
virtual BufferedBranchNode * deepCopy() const
Method to perform a deep copy of the octree.
virtual ~Octree2BufBase()
Empty deconstructor.
Octree2BufBase()
Empty constructor.
OctreeLeafNode< LeafContainerT > LeafNode
LeafNode * createLeafChild(BranchNode &branch_arg, unsigned char child_idx_arg)
Fetch and add a new leaf child to a branch class.
const ContainerT * operator->() const
Get const pointer to container.
OctreeDepthFirstIterator< OctreeT > DepthFirstIterator
std::size_t getLeafCount() const
Return the amount of existing leafs in the octree.
bool branchHasChild(const BranchNode &branch_arg, unsigned char child_idx_arg) const
Check if branch is pointing to a particular child node.
void serializeNewLeafs(std::vector< LeafContainerT * > &leaf_container_vector_arg)
Outputs a vector of all DataT elements from leaf nodes, that do not exist in the previous octree buff...
void reset()
Reset branch node container for every branch buffer.
void deserializeTreeRecursive(BranchNode *branch_arg, unsigned int depth_mask_arg, OctreeKey &key_arg, typename std::vector< char >::const_iterator &binary_tree_in_it_arg, typename std::vector< char >::const_iterator &binary_tree_in_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, bool branch_reset_arg=false, bool do_XOR_decoding_arg=false)
Rebuild an octree based on binary XOR octree description and DataT objects for leaf node initializati...
Abstract octree iterator class
void deleteBranchChild(BranchNode &branch_arg, unsigned char child_idx_arg)
Delete child node and all its subchilds from octree in current buffer.
Octree2BufBase< LeafContainerT, BranchContainerT > OctreeT
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).
ContainerT * getContainerPtr()
Get pointer to container.
ContainerT & getContainer()
Get reference to container.
virtual ~BufferedBranchNode()
Empty constructor.
BufferedBranchNode(const BufferedBranchNode &source)
Copy constructor.
OctreeNode * getBranchChildPtr(const BranchNode &branch_arg, unsigned char child_idx_arg) const
Retrieve a child node pointer for child node at child_idx.
unsigned int depth_mask_
Depth mask based on octree depth.
void deleteCurrentBuffer()
Delete the octree structure in the current buffer.
Octree leaf node iterator class.
unsigned char buffer_selector_
Currently active octree buffer.
BreadthFirstIterator breadth_begin(unsigned int max_depth_arg=0)
const BreadthFirstIterator breadth_end()
BufferedBranchNode< BranchContainerT > BranchNode
void serializeTreeRecursive(BranchNode *branch_arg, OctreeKey &key_arg, std::vector< char > *binary_tree_out_arg, typename std::vector< LeafContainerT * > *leaf_container_vector_arg, bool do_XOR_encoding_arg=false, bool new_leafs_filter_arg=false)
Recursively explore the octree and output binary octree description together with a vector of leaf no...
void deleteBranchChild(BranchNode &branch_arg, unsigned char buffer_selector_arg, unsigned char child_idx_arg)
Delete child node and all its subchilds from octree in specific buffer.
void deleteTree()
Delete the octree structure and its leaf nodes.
void deletePreviousBuffer()
Delete octree structure of previous buffer.
OctreeNode * child_node_array_[2][8]
virtual void deserializeTreeCallback(LeafContainerT &, const OctreeKey &)
Callback executed for every leaf node data during deserialization.
void deleteBranch(BranchNode &branch_arg)
Delete branch and all its subchilds from octree (both buffers)
Octree container class that does not store any information.
bool hasBranchChanges(const BranchNode &branch_arg) const
Test if branch changed between previous and current buffer.
unsigned int createLeafRecursive(const OctreeKey &key_arg, unsigned int depth_mask_arg, BranchNode *branch_arg, LeafNode *&return_leaf_arg, BranchNode *&parent_of_leaf_arg, bool branch_reset_arg=false)
Create a leaf node at octree key.
const OctreeDepthFirstIterator< OctreeT > ConstIterator
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).
Octree2BufBase & operator=(const Octree2BufBase &source)
Copy constructor.
OctreeBreadthFirstIterator< OctreeT > BreadthFirstIterator
bool dynamic_depth_enabled_
Enable dynamic_depth.
virtual node_type_t getNodeType() const
Get the type of octree node.
void removeLeaf(const OctreeKey &key_arg)
Remove leaf node from octree.
LeafContainerT * findLeaf(const OctreeKey &key_arg) const
Find leaf node.
Octree double buffer class