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 
Octree2BufBase< LeafContainerT, BranchContainerT > OctreeT
const ContainerT & operator*() const
Get const reference to container.
virtual void deserializeTreeCallback(LeafContainerT &, const OctreeKey &)
Callback executed for every leaf node data during deserialization.
OctreeNode * getBranchChildPtr(const BranchNode &branch_arg, unsigned char child_idx_arg) const
Retrieve a child node pointer for child node at child_idx.
LeafContainerT * findLeaf(const OctreeKey &key_arg) const
Find leaf node.
void serializeLeafs(std::vector< LeafContainerT * > &leaf_container_vector_arg)
Outputs a vector of all DataT elements that are stored within the octree leaf nodes.
void deleteCurrentBuffer()
Delete the octree structure in the current buffer.
const ContainerT & getContainer() const
Get const reference to container.
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).
OctreeBreadthFirstIterator< OctreeT > BreadthFirstIterator
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).
void deletePreviousBuffer()
Delete octree structure of previous buffer.
void removeLeaf(const OctreeKey &key_arg)
Remove leaf node from octree.
Octree double buffer class
const ContainerT * getContainerPtr() const
Get const pointer to container.
bool branchHasChild(const BranchNode &branch_arg, unsigned char child_idx_arg) const
Check if branch is pointing to a particular child node.
BufferedBranchNode & operator=(const BufferedBranchNode &source_arg)
Copy operator.
BranchNode * root_node_
Pointer to root branch node of octree.
Octree container class that does not store any information.
std::size_t getBranchCount() const
Return the amount of existing branches in the octree.
DepthFirstIterator depth_begin(unsigned int maxDepth_arg=0)
void switchBuffers()
Switch buffers and reset current octree structure.
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.
std::size_t getLeafCount() const
Return the amount of existing leafs in the octree.
BufferedBranchNode()
Empty constructor.
void setChildPtr(unsigned char buffer_arg, unsigned char index_arg, OctreeNode *newNode_arg)
Set child pointer in current branch node.
unsigned int octree_depth_
Octree depth.
OctreeLeafNodeIterator< OctreeT > LeafNodeIterator
void printBinary(char data_arg)
Prints binary representation of a byte - used for debugging.
const OctreeBreadthFirstIterator< OctreeT > ConstBreadthFirstIterator
void deleteTree()
Delete the octree structure and its leaf nodes.
Abstract octree node class
Definition: octree_nodes.h:69
std::size_t leaf_count_
Amount of leaf nodes.
bool deleteLeafRecursive(const OctreeKey &key_arg, unsigned int depth_mask_arg, BranchNode *branch_arg)
Recursively search and delete leaf node.
std::size_t branch_count_
Amount of branch nodes.
void deleteBranch(BranchNode &branch_arg)
Delete branch and all its subchilds from octree (both buffers)
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.
bool hasChild(unsigned char buffer_arg, unsigned char index_arg) const
Check if branch is pointing to a particular child node.
void treeCleanUpRecursive(BranchNode *branch_arg)
Recursively explore the octree and remove unused branch and leaf nodes.
virtual ~Octree2BufBase()
Empty deconstructor.
virtual void serializeTreeCallback(LeafContainerT &, const OctreeKey &)
Callback executed for every leaf node data during serialization.
const OctreeDepthFirstIterator< OctreeT > ConstDepthFirstIterator
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
OctreeNode * getChildPtr(unsigned char buffer_arg, unsigned char index_arg) const
Get child pointer in current branch node.
OctreeKey max_key_
key range
virtual OctreeNode * deepCopy() const =0
Pure virtual method to perform a deep copy of the octree.
LeafNode * createLeafChild(BranchNode &branch_arg, unsigned char child_idx_arg)
Fetch and add a new leaf child to a branch class.
bool existLeaf(const OctreeKey &key_arg) const
Check for leaf not existance in the octree.
char getBranchXORBitPattern(const BranchNode &branch_arg) const
Generate XOR bit pattern reflecting differences between the two octree buffers.
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 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...
const BreadthFirstIterator breadth_end()
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 setBranchChildPtr(BranchNode &branch_arg, unsigned char child_idx_arg, OctreeNode *new_child_arg)
Assign new child node to branch.
void deleteBranchChild(BranchNode &branch_arg, unsigned char child_idx_arg)
Delete child node and all its subchilds from octree in current buffer.
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.
const ContainerT * getContainerPtr() const
Get const pointer to container.
Definition: octree_nodes.h:179
Octree2BufBase(const Octree2BufBase &source)
Copy constructor.
virtual BufferedBranchNode * deepCopy() const
Method to perform a deep copy of the octree.
const LeafNodeIterator leaf_end()
void setTreeDepth(unsigned int depth_arg)
Set the maximum depth of the octree.
Octree leaf node iterator class.
unsigned int getTreeDepth() const
Get the maximum depth of the octree.
Octree key class
Definition: octree_key.h:53
const ContainerT * operator->() const
Get const pointer to container.
OctreeNode * getRootNode() const
Retrieve root node.
bool hasBranchChanges(const BranchNode &branch_arg) const
Test if branch changed between previous and current buffer.
void reset()
Reset branch node container for every branch buffer.
const OctreeDepthFirstIterator< OctreeT > ConstIterator
LeafContainerT * createLeaf(const OctreeKey &key_arg)
Create a leaf node.
LeafNodeIterator leaf_begin(unsigned int max_depth_arg=0)
bool dynamic_depth_enabled_
Enable dynamic_depth.
bool octreeCanResize()
Test if octree is able to dynamically change its depth.
ContainerT * getContainerPtr()
Get pointer to container.
ContainerT & getContainer()
Get reference to container.
virtual ~BufferedBranchNode()
Empty constructor.
void setMaxVoxelIndex(unsigned int max_voxel_index_arg)
Set the maximum amount of voxels per dimension.
char getBranchBitPattern(const BranchNode &branch_arg) const
Generate bit pattern reflecting the existence of child node pointers for current buffer.
BufferedBranchNode(const BufferedBranchNode &source)
Copy constructor.
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.
double Log2(double n_arg)
Helper function to calculate the binary logarithm.
Iterator begin(unsigned int max_depth_arg=0)
const DepthFirstIterator depth_end()
Octree2BufBase & operator=(const Octree2BufBase &source)
Copy constructor.
char getBranchBitPattern(const BranchNode &branch_arg, unsigned char bufferSelector_arg) const
Generate bit pattern reflecting the existence of child node pointers in specific buffer.
BranchContainerT BranchContainer
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).
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).
OctreeNode * child_node_array_[2][8]
Abstract octree leaf class
Definition: octree_nodes.h:98
unsigned int depth_mask_
Depth mask based on octree depth.
Octree2BufBase()
Empty constructor.
OctreeLeafNode< LeafContainerT > LeafNode
unsigned char buffer_selector_
Currently active octree buffer.
Abstract octree iterator class
BufferedBranchNode< BranchContainerT > BranchNode
virtual node_type_t getNodeType() const
Get the type of octree node.
OctreeDepthFirstIterator< OctreeT > Iterator
virtual node_type_t getNodeType() const =0
Pure virtual method for receiving the type of octree node (branch or leaf)
OctreeDepthFirstIterator< OctreeT > DepthFirstIterator
BranchNode * createBranchChild(BranchNode &branch_arg, unsigned char child_idx_arg)
Fetch and add a new branch child to a branch class in current buffer.
BreadthFirstIterator breadth_begin(unsigned int max_depth_arg=0)