Point Cloud Library (PCL)  1.8.1
octree_iterator.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_ITERATOR_H
40 #define PCL_OCTREE_ITERATOR_H
41 
42 #include <cstddef>
43 #include <vector>
44 #include <deque>
45 
46 #include <pcl/octree/octree_nodes.h>
47 #include <pcl/octree/octree_key.h>
48 
49 #include <iterator>
50 
51 // Ignore warnings in the above headers
52 #ifdef __GNUC__
53 #pragma GCC system_header
54 #endif
55 
56 namespace pcl
57 {
58  namespace octree
59  {
60 
61  // Octree iterator state pushed on stack/list
62  struct IteratorState{
65  unsigned char depth_;
66  };
67 
68 
69  /** \brief @b Abstract octree iterator class
70  * \note Octree iterator base class
71  * \ingroup octree
72  * \author Julius Kammerl (julius@kammerl.de)
73  */
74  template<typename OctreeT>
75  class OctreeIteratorBase : public std::iterator<std::forward_iterator_tag, const OctreeNode, void,
76  const OctreeNode*, const OctreeNode&>
77  {
78  public:
79 
80  typedef typename OctreeT::LeafNode LeafNode;
81  typedef typename OctreeT::BranchNode BranchNode;
82 
83  typedef typename OctreeT::LeafContainer LeafContainer;
84  typedef typename OctreeT::BranchContainer BranchContainer;
85 
86  /** \brief Empty constructor.
87  */
88  explicit
89  OctreeIteratorBase (unsigned int max_depth_arg = 0) :
90  octree_ (0), current_state_(0), max_octree_depth_(max_depth_arg)
91  {
92  this->reset ();
93  }
94 
95  /** \brief Constructor.
96  * \param[in] octree_arg Octree to be iterated. Initially the iterator is set to its root node.
97  * \param[in] max_depth_arg Depth limitation during traversal
98  */
99  explicit
100  OctreeIteratorBase (OctreeT* octree_arg, unsigned int max_depth_arg = 0) :
101  octree_ (octree_arg), current_state_(0), max_octree_depth_(max_depth_arg)
102  {
103  this->reset ();
104  }
105 
106  /** \brief Copy constructor.
107  * \param[in] src the iterator to copy into this
108  * \param[in] max_depth_arg Depth limitation during traversal
109  */
110  OctreeIteratorBase (const OctreeIteratorBase& src, unsigned int max_depth_arg = 0) :
111  octree_ (src.octree_), current_state_(0), max_octree_depth_(max_depth_arg)
112  {
113  }
114 
115  /** \brief Copy operator.
116  * \param[in] src the iterator to copy into this
117  */
118  inline OctreeIteratorBase&
120  {
121  octree_ = src.octree_;
124  return (*this);
125  }
126 
127  /** \brief Empty deconstructor. */
128  virtual
130  {
131  }
132 
133  /** \brief Equal comparison operator
134  * \param[in] other OctreeIteratorBase to compare with
135  */
136  bool operator==(const OctreeIteratorBase& other) const
137  {
138  return (( octree_ ==other.octree_) &&
139  ( current_state_ == other.current_state_) &&
140  ( max_octree_depth_ == other.max_octree_depth_) );
141  }
142 
143  /** \brief Inequal comparison operator
144  * \param[in] other OctreeIteratorBase to compare with
145  */
146  bool operator!=(const OctreeIteratorBase& other) const
147  {
148  return (( octree_ !=other.octree_) &&
149  ( current_state_ != other.current_state_) &&
150  ( max_octree_depth_ != other.max_octree_depth_) );
151  }
152 
153  /** \brief Reset iterator */
154  inline void reset ()
155  {
156  current_state_ = 0;
157  if (octree_ && (!max_octree_depth_))
158  {
159  max_octree_depth_ = octree_->getTreeDepth();
160  }
161  }
162 
163  /** \brief Get octree key for the current iterator octree node
164  * \return octree key of current node
165  */
166  inline const OctreeKey&
168  {
169  assert(octree_!=0);
170  assert(current_state_!=0);
171 
172  return (current_state_->key_);
173  }
174 
175  /** \brief Get the current depth level of octree
176  * \return depth level
177  */
178  inline unsigned int
180  {
181  assert(octree_!=0);
182  assert(current_state_!=0);
183 
184  return (current_state_->depth_);
185  }
186 
187  /** \brief Get the current octree node
188  * \return pointer to current octree node
189  */
190  inline OctreeNode*
192  {
193  assert(octree_!=0);
194  assert(current_state_!=0);
195 
196  return (current_state_->node_);
197  }
198 
199 
200  /** \brief check if current node is a branch node
201  * \return true if current node is a branch node, false otherwise
202  */
203  inline bool
204  isBranchNode () const
205  {
206  assert(octree_!=0);
207  assert(current_state_!=0);
208 
209  return (current_state_->node_->getNodeType () == BRANCH_NODE);
210  }
211 
212  /** \brief check if current node is a branch node
213  * \return true if current node is a branch node, false otherwise
214  */
215  inline bool
216  isLeafNode () const
217  {
218  assert(octree_!=0);
219  assert(current_state_!=0);
220 
221  return (current_state_->node_->getNodeType () == LEAF_NODE);
222  }
223 
224  /** \brief *operator.
225  * \return pointer to the current octree node
226  */
227  inline OctreeNode*
228  operator* () const
229  { // return designated object
230  if (octree_ && current_state_)
231  {
232  return (current_state_->node_);
233  } else
234  {
235  return 0;
236  }
237  }
238 
239  /** \brief Get bit pattern of children configuration of current node
240  * \return bit pattern (byte) describing the existence of 8 children of the current node
241  */
242  inline char
244  {
245  char ret = 0;
246 
247  assert(octree_!=0);
248  assert(current_state_!=0);
249 
250  if (isBranchNode ())
251  {
252 
253  // current node is a branch node
254  const BranchNode* current_branch = static_cast<const BranchNode*> (current_state_->node_);
255 
256  // get child configuration bit pattern
257  ret = octree_->getBranchBitPattern (*current_branch);
258 
259  }
260 
261  return (ret);
262  }
263 
264  /** \brief Method for retrieving a single leaf container from the octree leaf node
265  * \return Reference to container class of leaf node.
266  */
267  const LeafContainer&
269  {
270  assert(octree_!=0);
271  assert(current_state_!=0);
272  assert(this->isLeafNode());
273 
274  LeafNode* leaf_node = static_cast<LeafNode*>(current_state_->node_);
275 
276  return leaf_node->getContainer();
277  }
278 
279  /** \brief Method for retrieving a single leaf container from the octree leaf node
280  * \return Reference to container class of leaf node.
281  */
284  {
285  assert(octree_!=0);
286  assert(current_state_!=0);
287  assert(this->isLeafNode());
288 
289  LeafNode* leaf_node = static_cast<LeafNode*>(current_state_->node_);
290 
291  return leaf_node->getContainer();
292  }
293 
294  /** \brief Method for retrieving the container from an octree branch node
295  * \return BranchContainer.
296  */
297  const BranchContainer&
299  {
300  assert(octree_!=0);
301  assert(current_state_!=0);
302  assert(this->isBranchNode());
303 
304  BranchNode* branch_node = static_cast<BranchNode*>(current_state_->node_);
305 
306  return branch_node->getContainer();
307  }
308 
309  /** \brief Method for retrieving the container from an octree branch node
310  * \return BranchContainer.
311  */
314  {
315  assert(octree_!=0);
316  assert(current_state_!=0);
317  assert(this->isBranchNode());
318 
319  BranchNode* branch_node = static_cast<BranchNode*>(current_state_->node_);
320 
321  return branch_node->getContainer();
322  }
323 
324  /** \brief get a integer identifier for current node (note: identifier depends on tree depth).
325  * \return node id.
326  */
327  virtual unsigned long
328  getNodeID () const
329  {
330  unsigned long id = 0;
331 
332  assert(octree_!=0);
333  assert(current_state_!=0);
334 
335  if (current_state_)
336  {
337  const OctreeKey& key = getCurrentOctreeKey();
338  // calculate integer id with respect to octree key
339  unsigned int depth = octree_->getTreeDepth ();
340  id = static_cast<unsigned long> (key.x) << (depth * 2)
341  | static_cast<unsigned long> (key.y) << (depth * 1)
342  | static_cast<unsigned long> (key.z) << (depth * 0);
343  }
344 
345  return id;
346  }
347 
348  protected:
349  /** \brief Reference to octree class. */
350  OctreeT* octree_;
351 
352  /** \brief Pointer to current iterator state. */
354 
355  /** \brief Maximum octree depth */
356  unsigned int max_octree_depth_;
357  };
358 
359  //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
360  /** \brief @b Octree iterator class
361  * \note This class implements a forward iterator for traversing octrees in a depth-first manner.
362  * \ingroup octree
363  * \author Julius Kammerl (julius@kammerl.de)
364  */
365  template<typename OctreeT>
367  {
368 
369  public:
370 
373 
374  /** \brief Empty constructor.
375  * \param[in] max_depth_arg Depth limitation during traversal
376  */
377  explicit
378  OctreeDepthFirstIterator (unsigned int max_depth_arg = 0);
379 
380  /** \brief Constructor.
381  * \param[in] octree_arg Octree to be iterated. Initially the iterator is set to its root node.
382  * \param[in] max_depth_arg Depth limitation during traversal
383  */
384  explicit
385  OctreeDepthFirstIterator (OctreeT* octree_arg, unsigned int max_depth_arg = 0);
386 
387  /** \brief Empty deconstructor. */
388  virtual
390 
391  /** \brief Copy operator.
392  * \param[in] src the iterator to copy into this
393  */
396  {
397 
399 
400  stack_ = src.stack_;
401 
402  if (stack_.size())
403  {
404  this->current_state_ = &stack_.back();
405  } else
406  {
407  this->current_state_ = 0;
408  }
409 
410  return (*this);
411  }
412 
413  /** \brief Reset the iterator to the root node of the octree
414  */
415  virtual void
416  reset ();
417 
418  /** \brief Preincrement operator.
419  * \note recursively step to next octree node
420  */
422  operator++ ();
423 
424  /** \brief postincrement operator.
425  * \note recursively step to next octree node
426  */
429  {
430  OctreeDepthFirstIterator _Tmp = *this;
431  ++*this;
432  return (_Tmp);
433  }
434 
435  /** \brief Skip all child voxels of current node and return to parent node.
436  */
437  void
438  skipChildVoxels ();
439 
440  protected:
441  /** Stack structure. */
442  std::vector<IteratorState> stack_;
443  };
444 
445  //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
446  /** \brief @b Octree iterator class
447  * \note This class implements a forward iterator for traversing octrees in a breadth-first manner.
448  * \ingroup octree
449  * \author Julius Kammerl (julius@kammerl.de)
450  */
451  template<typename OctreeT>
453  {
454  // public typedefs
457 
458 
459  public:
460  /** \brief Empty constructor.
461  * \param[in] max_depth_arg Depth limitation during traversal
462  */
463  explicit
464  OctreeBreadthFirstIterator (unsigned int max_depth_arg = 0);
465 
466  /** \brief Constructor.
467  * \param[in] octree_arg Octree to be iterated. Initially the iterator is set to its root node.
468  * \param[in] max_depth_arg Depth limitation during traversal
469  */
470  explicit
471  OctreeBreadthFirstIterator (OctreeT* octree_arg, unsigned int max_depth_arg = 0);
472 
473  /** \brief Empty deconstructor. */
474  virtual
476 
477  /** \brief Copy operator.
478  * \param[in] src the iterator to copy into this
479  */
482  {
483 
485 
486  FIFO_ = src.FIFO_;
487 
488  if (FIFO_.size())
489  {
490  this->current_state_ = &FIFO_.front();
491  } else
492  {
493  this->current_state_ = 0;
494  }
495 
496  return (*this);
497  }
498 
499  /** \brief Reset the iterator to the root node of the octree
500  */
501  void
502  reset ();
503 
504  /** \brief Preincrement operator.
505  * \note step to next octree node
506  */
508  operator++ ();
509 
510  /** \brief postincrement operator.
511  * \note step to next octree node
512  */
515  {
516  OctreeBreadthFirstIterator _Tmp = *this;
517  ++*this;
518  return (_Tmp);
519  }
520 
521  protected:
522  /** FIFO list */
523  std::deque<IteratorState> FIFO_;
524  };
525 
526  //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
527  /** \brief Octree leaf node iterator class
528  * \note This class implements a forward iterator for traversing the leaf nodes of an octree data structure.
529  * \ingroup octree
530  * \author Julius Kammerl (julius@kammerl.de)
531  */
532  //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
533  template<typename OctreeT>
535  {
538 
539  public:
540  /** \brief Empty constructor.
541  * \param[in] max_depth_arg Depth limitation during traversal
542  */
543  explicit
544  OctreeLeafNodeIterator (unsigned int max_depth_arg = 0) :
545  OctreeDepthFirstIterator<OctreeT> (max_depth_arg)
546  {
547  reset ();
548  }
549 
550  /** \brief Constructor.
551  * \param[in] octree_arg Octree to be iterated. Initially the iterator is set to its root node.
552  * \param[in] max_depth_arg Depth limitation during traversal
553  */
554  explicit
555  OctreeLeafNodeIterator (OctreeT* octree_arg, unsigned int max_depth_arg = 0) :
556  OctreeDepthFirstIterator<OctreeT> (octree_arg, max_depth_arg)
557  {
558  reset ();
559  }
560 
561  /** \brief Empty deconstructor. */
562  virtual
564  {
565  }
566 
567  /** \brief Reset the iterator to the root node of the octree
568  */
569  inline void
570  reset ()
571  {
573  this->operator++ ();
574  }
575 
576  /** \brief Preincrement operator.
577  * \note recursively step to next octree leaf node
578  */
579  inline OctreeLeafNodeIterator&
581  {
582  do
583  {
585  } while ((this->current_state_) && (this->current_state_->node_->getNodeType () != LEAF_NODE));
586 
587  return (*this);
588  }
589 
590  /** \brief postincrement operator.
591  * \note step to next octree node
592  */
595  {
596  OctreeLeafNodeIterator _Tmp = *this;
597  ++*this;
598  return (_Tmp);
599  }
600 
601  /** \brief *operator.
602  * \return pointer to the current octree leaf node
603  */
604  OctreeNode*
605  operator* () const
606  {
607  // return designated object
608  OctreeNode* ret = 0;
609 
610  if (this->current_state_ && (this->current_state_->node_->getNodeType () == LEAF_NODE))
611  ret = this->current_state_->node_;
612  return (ret);
613  }
614  };
615 
616  }
617 }
618 
619 /*
620  * Note: Since octree iterators depend on octrees, don't precompile them.
621  */
622 #include <pcl/octree/impl/octree_iterator.hpp>
623 
624 #endif
625 
bool isLeafNode() const
check if current node is a branch node
OctreeBreadthFirstIterator & operator=(const OctreeBreadthFirstIterator &src)
Copy operator.
const BranchContainer & getBranchContainer() const
Method for retrieving the container from an octree branch node.
OctreeLeafNodeIterator & operator++()
Preincrement operator.
OctreeIteratorBase(const OctreeIteratorBase &src, unsigned int max_depth_arg=0)
Copy constructor.
OctreeIteratorBase & operator=(const OctreeIteratorBase &src)
Copy operator.
virtual node_type_t getNodeType() const =0
Pure virtual method for receiving the type of octree node (branch or leaf)
OctreeT::LeafContainer LeafContainer
std::deque< IteratorState > FIFO_
FIFO list.
bool isBranchNode() const
check if current node is a branch node
OctreeNode * operator*() const
*operator.
const LeafContainer & getLeafContainer() const
Method for retrieving a single leaf container from the octree leaf node.
std::vector< IteratorState > stack_
Stack structure.
IteratorState * current_state_
Pointer to current iterator state.
OctreeNode * operator*() const
*operator.
Octree leaf node iterator class.
OctreeT::BranchNode BranchNode
LeafContainer & getLeafContainer()
Method for retrieving a single leaf container from the octree leaf node.
unsigned int max_octree_depth_
Maximum octree depth.
void reset()
Reset the iterator to the root node of the octree.
virtual void reset()
Reset the iterator to the root node of the octree.
OctreeT::BranchContainer BranchContainer
unsigned int getCurrentOctreeDepth() const
Get the current depth level of octree.
OctreeIteratorBase< OctreeT >::LeafNode LeafNode
OctreeIteratorBase< OctreeT >::BranchNode BranchNode
bool operator!=(const OctreeIteratorBase &other) const
Inequal comparison operator.
OctreeIteratorBase(unsigned int max_depth_arg=0)
Empty constructor.
OctreeNode * getCurrentOctreeNode() const
Get the current octree node.
OctreeLeafNodeIterator(unsigned int max_depth_arg=0)
Empty constructor.
char getNodeConfiguration() const
Get bit pattern of children configuration of current node.
OctreeDepthFirstIterator(unsigned int max_depth_arg=0)
Empty constructor.
void skipChildVoxels()
Skip all child voxels of current node and return to parent node.
virtual ~OctreeBreadthFirstIterator()
Empty deconstructor.
virtual unsigned long getNodeID() const
get a integer identifier for current node (note: identifier depends on tree depth).
Octree key class
Definition: octree_key.h:51
OctreeLeafNodeIterator(OctreeT *octree_arg, unsigned int max_depth_arg=0)
Constructor.
const OctreeKey & getCurrentOctreeKey() const
Get octree key for the current iterator octree node.
virtual ~OctreeLeafNodeIterator()
Empty deconstructor.
void reset()
Reset the iterator to the root node of the octree.
OctreeBreadthFirstIterator & operator++()
Preincrement operator.
OctreeT * octree_
Reference to octree class.
OctreeDepthFirstIterator & operator++()
Preincrement operator.
Abstract octree iterator class
OctreeDepthFirstIterator & operator=(const OctreeDepthFirstIterator &src)
Copy operator.
virtual ~OctreeIteratorBase()
Empty deconstructor.
bool operator==(const OctreeIteratorBase &other) const
Equal comparison operator.
virtual ~OctreeDepthFirstIterator()
Empty deconstructor.
Abstract octree node class
Definition: octree_nodes.h:68
OctreeIteratorBase(OctreeT *octree_arg, unsigned int max_depth_arg=0)
Constructor.
BranchContainer & getBranchContainer()
Method for retrieving the container from an octree branch node.
OctreeBreadthFirstIterator(unsigned int max_depth_arg=0)
Empty constructor.