Point Cloud Library (PCL)  1.9.1-dev
outofcore_depth_first_iterator.hpp
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_OUTOFCORE_DEPTH_FIRST_ITERATOR_IMPL_H_
40 #define PCL_OUTOFCORE_DEPTH_FIRST_ITERATOR_IMPL_H_
41 
42 namespace pcl
43 {
44  namespace outofcore
45  {
46 
47  template<typename PointT, typename ContainerT>
49  : OutofcoreIteratorBase<PointT, ContainerT> (octree_arg)
50  , currentChildIdx_ (0)
51  , stack_ (0)
52  {
53  stack_.reserve (this->octree_.getTreeDepth ());
55  }
56 
57  ////////////////////////////////////////////////////////////////////////////////
58 
59  template<typename PointT, typename ContainerT>
61  {
62  }
63 
64  ////////////////////////////////////////////////////////////////////////////////
65 
66  template<typename PointT, typename ContainerT>
69  {
70  //when currentNode_ is 0, skip incrementing because it is already at the end
71  if (this->currentNode_)
72  {
73  bool bTreeUp = false;
75 
77  {
78  BranchNode* currentBranch = static_cast<BranchNode*> (this->currentNode_);
79 
80  if (currentChildIdx_ < 8)
81  {
82  itNode = this->octree_.getBranchChildPtr (*currentBranch, currentChildIdx_);
83 
84  //keep looking for a valid child until we've run out of children or a valid one is found
85  while ((currentChildIdx_ < 7) && !(itNode))
86  {
87  //find next existing child node
89  itNode = this->octree_.getBranchChildPtr (*currentBranch, currentChildIdx_);
90  }
91  //if no valid one was found, set flag to move back up the tree to the parent node
92  if (!itNode)
93  {
94  bTreeUp = true;
95  }
96  }
97  else
98  {
99  bTreeUp = true;
100  }
101  }
102  else
103  {
104  bTreeUp = true;
105  }
106 
107  if (bTreeUp)
108  {
109  if (!stack_.empty ())
110  {
111  std::pair<OutofcoreOctreeBaseNode<ContainerT, PointT>*, unsigned char>& stackEntry = stack_.back ();
112  stack_.pop_back ();
113 
114  this->currentNode_ = stackEntry.first;
115  currentChildIdx_ = stackEntry.second;
116 
117  //don't do anything with the keys here...
118  this->currentOctreeDepth_--;
119  }
120  else
121  {
122  this->currentNode_ = nullptr;
123  }
124 
125  }
126  else
127  {
128  std::pair<OutofcoreOctreeBaseNode<ContainerT, PointT>*, unsigned char> newStackEntry;
129  newStackEntry.first = this->currentNode_;
130  newStackEntry.second = static_cast<unsigned char> (currentChildIdx_+1);
131 
132  stack_.push_back (newStackEntry);
133 
134  //don't do anything with the keys here...
135 
136  this->currentOctreeDepth_++;
137  currentChildIdx_= 0;
138  this->currentNode_ = itNode;
139  }
140  }
141 
142  return (*this);
143  }
144 
145  ////////////////////////////////////////////////////////////////////////////////
146 
147  }//namesapce pcl
148 }//namespace outofcore
149 
150 #endif //PCL_OUTOFCORE_DEPTH_FIRST_ITERATOR_IMPL_H_
151 
OutofcoreNodeType * getBranchChildPtr(const BranchNode &branch_arg, unsigned char childIdx_arg) const
This file defines compatibility wrappers for low level I/O functions.
Definition: convolution.h:45
std::uint64_t getTreeDepth() const
Definition: octree_base.h:441
std::vector< std::pair< OctreeDiskNode *, unsigned char > > stack_
node_type_t getNodeType() const override
Pure virtual method for receiving the type of octree node (branch or leaf)
OutofcoreOctreeBaseNode Class internally representing nodes of an outofcore octree, with accessors to its data via the pcl::outofcore::OutofcoreOctreeDiskContainer class or pcl::outofcore::OutofcoreOctreeRamContainer class, whichever it is templated against.
Abstract octree iterator class.
A point structure representing Euclidean xyz coordinates, and the RGB color.
This code defines the octree used for point storage at Urban Robotics.
Definition: octree_base.h:150