Point Cloud Library (PCL)  1.7.1
octree_nodes.h
1 /*
2  * Software License Agreement (BSD License)
3  *
4  * Point Cloud Library (PCL) - www.pointclouds.org
5  * Copyright (c) 2010-2011, 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_NODE_H
40 #define PCL_OCTREE_NODE_H
41 
42 #include <cstddef>
43 
44 #include <assert.h>
45 #include <cstring>
46 
47 #include <string.h>
48 
49 #include <pcl/pcl_macros.h>
50 
51 #include "octree_container.h"
52 
53 namespace pcl
54 {
55  namespace octree
56  {
57 
58  // enum of node types within the octree
60  {
62  };
63 
64  //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
65  /** \brief @b Abstract octree node class
66  * \note Every octree node should implement the getNodeType () method
67  * \author Julius Kammerl (julius@kammerl.de)
68  */
69  class PCL_EXPORTS OctreeNode
70  {
71  public:
72 
74  {
75  }
76 
77  virtual
79  {
80  }
81  /** \brief Pure virtual method for receiving the type of octree node (branch or leaf) */
82  virtual node_type_t
83  getNodeType () const = 0;
84 
85  /** \brief Pure virtual method to perform a deep copy of the octree */
86  virtual OctreeNode*
87  deepCopy () const = 0;
88 
89  };
90 
91  //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
92  /** \brief @b Abstract octree leaf class
93  * \note Octree leafs may collect data of type DataT
94  * \author Julius Kammerl (julius@kammerl.de)
95  */
96 
97  template<typename ContainerT>
98  class OctreeLeafNode : public OctreeNode
99  {
100  public:
101 
102  /** \brief Empty constructor. */
104  OctreeNode ()
105  {
106  }
107 
108  /** \brief Copy constructor. */
109  OctreeLeafNode (const OctreeLeafNode& source) :
110  OctreeNode ()
111  {
112  container_ = source.container_;
113  }
114 
115  /** \brief Empty deconstructor. */
116  virtual
118  {
119  }
120 
121  /** \brief Method to perform a deep copy of the octree */
123  deepCopy () const
124  {
125  return new OctreeLeafNode<ContainerT> (*this);
126  }
127 
128  /** \brief Get the type of octree node. Returns LEAVE_NODE type */
129  virtual node_type_t
130  getNodeType () const
131  {
132  return LEAF_NODE;
133  }
134 
135  /** \brief Get const pointer to container */
136  const ContainerT*
137  operator->() const
138  {
139  return &container_;
140  }
141 
142  /** \brief Get pointer to container */
143  ContainerT*
145  {
146  return &container_;
147  }
148 
149  /** \brief Get const reference to container */
150  const ContainerT&
151  operator* () const
152  {
153  return container_;
154  }
155 
156  /** \brief Get reference to container */
157  ContainerT&
159  {
160  return container_;
161  }
162 
163  /** \brief Get const reference to container */
164  const ContainerT&
165  getContainer () const
166  {
167  return container_;
168  }
169 
170  /** \brief Get reference to container */
171  ContainerT&
173  {
174  return container_;
175  }
176 
177  /** \brief Get const pointer to container */
178  const ContainerT*
180  {
181  return &container_;
182  }
183 
184  /** \brief Get pointer to container */
185  ContainerT*
187  {
188  return &container_;
189  }
190 
191  protected:
192  ContainerT container_;
193  };
194 
195  //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
196  /** \brief @b Abstract octree branch class
197  * \note Octree branch classes may collect data of type DataT
198  * \author Julius Kammerl (julius@kammerl.de)
199  */
200  template<typename ContainerT>
202  {
203  public:
204 
205  /** \brief Empty constructor. */
207  OctreeNode()
208  {
209  // reset pointer to child node vectors
210  memset (child_node_array_, 0, sizeof(child_node_array_));
211  }
212 
213  /** \brief Empty constructor. */
215  OctreeNode()
216  {
217  unsigned char i;
218 
219  memset (child_node_array_, 0, sizeof(child_node_array_));
220 
221  for (i = 0; i < 8; ++i)
222  if (source.child_node_array_[i])
223  child_node_array_[i] = source.child_node_array_[i]->deepCopy ();
224  }
225 
226  /** \brief Copy operator. */
227  inline OctreeBranchNode&
229  {
230  unsigned char i;
231 
232  memset (child_node_array_, 0, sizeof(child_node_array_));
233 
234  for (i = 0; i < 8; ++i)
235  if (source.child_node_array_[i])
236  child_node_array_[i] = source.child_node_array_[i]->deepCopy ();
237  return (*this);
238  }
239 
240  /** \brief Octree deep copy method */
241  virtual OctreeBranchNode*
242  deepCopy () const
243  {
244  return (new OctreeBranchNode<ContainerT> (*this));
245  }
246 
247  /** \brief Empty deconstructor. */
248  virtual
250  {
251  }
252 
253  /** \brief Access operator.
254  * \param child_idx_arg: index to child node
255  * \return OctreeNode pointer
256  * */
257  inline OctreeNode*&
258  operator[] (unsigned char child_idx_arg)
259  {
260  assert(child_idx_arg < 8);
261  return child_node_array_[child_idx_arg];
262  }
263 
264  /** \brief Get pointer to child
265  * \param child_idx_arg: index to child node
266  * \return OctreeNode pointer
267  * */
268  inline OctreeNode*
269  getChildPtr (unsigned char child_idx_arg) const
270  {
271  assert(child_idx_arg < 8);
272  return child_node_array_[child_idx_arg];
273  }
274 
275  /** \brief Get pointer to child
276  * \return OctreeNode pointer
277  * */
278  inline void setChildPtr (OctreeNode* child, unsigned char index)
279  {
280  assert(index < 8);
281  child_node_array_[index] = child;
282  }
283 
284 
285  /** \brief Check if branch is pointing to a particular child node
286  * \param child_idx_arg: index to child node
287  * \return "true" if pointer to child node exists; "false" otherwise
288  * */
289  inline bool hasChild (unsigned char child_idx_arg) const
290  {
291  return (child_node_array_[child_idx_arg] != 0);
292  }
293 
294 
295  /** \brief Check if branch can be pruned
296  * \note if all children are leaf nodes AND contain identical containers, branch can be pruned
297  * \return "true" if branch can be pruned; "false" otherwise
298  * */
299  /* inline bool isPrunable () const
300  {
301  const OctreeNode* firstChild = child_node_array_[0];
302  if (!firstChild || firstChild->getNodeType()==BRANCH_NODE)
303  return false;
304 
305  bool prunable = true;
306  for (unsigned char i = 1; i < 8 && prunable; ++i)
307  {
308  const OctreeNode* child = child_node_array_[i];
309  if ( (!child) ||
310  (child->getNodeType()==BRANCH_NODE) ||
311  ((*static_cast<const OctreeContainerBase*>(child)) == (*static_cast<const OctreeContainerBase*>(child)) ) )
312  prunable = false;
313  }
314 
315  return prunable;
316  }*/
317 
318  /** \brief Get the type of octree node. Returns LEAVE_NODE type */
319  virtual node_type_t
320  getNodeType () const
321  {
322  return BRANCH_NODE;
323  }
324 
325  // reset node
326  void reset()
327  {
328  memset(child_node_array_, 0, sizeof(child_node_array_));
329  container_.reset();
330  }
331 
332 
333  /** \brief Get const pointer to container */
334  const ContainerT*
335  operator->() const
336  {
337  return &container_;
338  }
339 
340  /** \brief Get pointer to container */
341  ContainerT*
343  {
344  return &container_;
345  }
346 
347  /** \brief Get const reference to container */
348  const ContainerT&
349  operator* () const
350  {
351  return container_;
352  }
353 
354  /** \brief Get reference to container */
355  ContainerT&
357  {
358  return container_;
359  }
360 
361  /** \brief Get const reference to container */
362  const ContainerT&
363  getContainer () const
364  {
365  return container_;
366  }
367 
368  /** \brief Get reference to container */
369  ContainerT&
371  {
372  return container_;
373  }
374 
375  /** \brief Get const pointer to container */
376  const ContainerT*
378  {
379  return &container_;
380  }
381 
382  /** \brief Get pointer to container */
383  ContainerT*
385  {
386  return &container_;
387  }
388 
389  protected:
391 
392  ContainerT container_;
393  };
394  }
395 }
396 
397 #endif