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