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