Point Cloud Library (PCL) 1.12.0
Loading...
Searching...
No Matches
octree_base.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#pragma once
40
41#include <pcl/octree/octree_container.h>
42#include <pcl/octree/octree_iterator.h>
43#include <pcl/octree/octree_key.h>
44#include <pcl/octree/octree_nodes.h>
45#include <pcl/pcl_macros.h>
46
47#include <vector>
48
49namespace pcl {
50namespace octree {
51
52/** \brief Octree class
53 * \note The tree depth defines the maximum amount of octree voxels / leaf nodes (should
54 * be initially defined).
55 * \note All leaf nodes are addressed by integer indices.
56 * \note The tree depth equates to the bit length of the voxel indices.
57 * \ingroup octree
58 * \author Julius Kammerl (julius@kammerl.de)
59 */
60template <typename LeafContainerT = index_t,
61 typename BranchContainerT = OctreeContainerEmpty>
63public:
65
68
69 using BranchContainer = BranchContainerT;
70 using LeafContainer = LeafContainerT;
71
72protected:
73 ///////////////////////////////////////////////////////////////////////
74 // Members
75 ///////////////////////////////////////////////////////////////////////
76
77 /** \brief Amount of leaf nodes **/
78 std::size_t leaf_count_;
79
80 /** \brief Amount of branch nodes **/
81 std::size_t branch_count_;
82
83 /** \brief Pointer to root branch node of octree **/
85
86 /** \brief Depth mask based on octree depth **/
88
89 /** \brief Octree depth */
91
92 /** \brief Enable dynamic_depth **/
94
95 /** \brief key range */
97
98public:
99 // iterators are friends
100 friend class OctreeIteratorBase<OctreeT>;
101 friend class OctreeDepthFirstIterator<OctreeT>;
103 friend class OctreeFixedDepthIterator<OctreeT>;
106
107 // Octree default iterators
110
112 begin(uindex_t max_depth_arg = 0u)
113 {
114 return Iterator(this, max_depth_arg ? max_depth_arg : this->octree_depth_);
115 };
116
117 const Iterator
119 {
120 return Iterator(this, 0, nullptr);
121 };
122
123 // Octree leaf node iterators
124 // The previous deprecated names
125 // LeafNodeIterator and ConstLeafNodeIterator are deprecated.
126 // Please use LeafNodeDepthFirstIterator and ConstLeafNodeDepthFirstIterator instead.
129
130 // The currently valide names
134
136 leaf_depth_begin(uindex_t max_depth_arg = 0u)
137 {
139 this, max_depth_arg ? max_depth_arg : this->octree_depth_);
140 };
141
144 {
145 return LeafNodeDepthFirstIterator(this, 0, nullptr);
146 };
147
148 // Octree depth-first iterators
151
153 depth_begin(uindex_t max_depth_arg = 0u)
154 {
155 return DepthFirstIterator(this,
156 max_depth_arg ? max_depth_arg : this->octree_depth_);
157 };
158
161 {
162 return DepthFirstIterator(this, 0, nullptr);
163 };
164
165 // Octree breadth-first iterators
168
170 breadth_begin(uindex_t max_depth_arg = 0u)
171 {
172 return BreadthFirstIterator(this,
173 max_depth_arg ? max_depth_arg : this->octree_depth_);
174 };
175
178 {
179 return BreadthFirstIterator(this, 0, nullptr);
180 };
181
182 // Octree breadth iterators at a given depth
185
187 fixed_depth_begin(uindex_t fixed_depth_arg = 0u)
188 {
189 return FixedDepthIterator(this, fixed_depth_arg);
190 };
191
194 {
195 return FixedDepthIterator(this, 0, nullptr);
196 };
197
198 // Octree leaf node iterators
202
204 leaf_breadth_begin(uindex_t max_depth_arg = 0u)
205 {
207 this, max_depth_arg ? max_depth_arg : this->octree_depth_);
208 };
209
212 {
213 return LeafNodeBreadthFirstIterator(this, 0, nullptr);
214 };
215
216 /** \brief Empty constructor. */
217 OctreeBase();
218
219 /** \brief Empty deconstructor. */
220 virtual ~OctreeBase();
221
222 /** \brief Copy constructor. */
223 OctreeBase(const OctreeBase& source)
224 : leaf_count_(source.leaf_count_)
226 , root_node_(new (BranchNode)(*(source.root_node_)))
227 , depth_mask_(source.depth_mask_)
230 , max_key_(source.max_key_)
231 {}
232
233 /** \brief Copy operator. */
235 operator=(const OctreeBase& source)
236 {
237 leaf_count_ = source.leaf_count_;
239 delete root_node_;
240
241 root_node_ = new (BranchNode)(*(source.root_node_));
242 depth_mask_ = source.depth_mask_;
243 max_key_ = source.max_key_;
245 return (*this);
246 }
247
248 /** \brief Set the maximum amount of voxels per dimension.
249 * \param[in] max_voxel_index_arg maximum amount of voxels per dimension
250 */
251 void
252 setMaxVoxelIndex(uindex_t max_voxel_index_arg);
253
254 /** \brief Set the maximum depth of the octree.
255 * \param max_depth_arg: maximum depth of octree
256 */
257 void
258 setTreeDepth(uindex_t max_depth_arg);
259
260 /** \brief Get the maximum depth of the octree.
261 * \return depth_arg: maximum depth of octree
262 */
265 {
266 return this->octree_depth_;
267 }
268
269 /** \brief Create new leaf node at (idx_x_arg, idx_y_arg, idx_z_arg).
270 * \note If leaf node already exist, this method returns the existing node
271 * \param idx_x_arg: index of leaf node in the X axis.
272 * \param idx_y_arg: index of leaf node in the Y axis.
273 * \param idx_z_arg: index of leaf node in the Z axis.
274 * \return pointer to new leaf node container.
275 */
276 LeafContainerT*
277 createLeaf(uindex_t idx_x_arg, uindex_t idx_y_arg, uindex_t idx_z_arg);
278
279 /** \brief Find leaf node at (idx_x_arg, idx_y_arg, idx_z_arg).
280 * \note If leaf node already exist, this method returns the existing node
281 * \param idx_x_arg: index of leaf node in the X axis.
282 * \param idx_y_arg: index of leaf node in the Y axis.
283 * \param idx_z_arg: index of leaf node in the Z axis.
284 * \return pointer to leaf node container if found, null pointer otherwise.
285 */
286 LeafContainerT*
287 findLeaf(uindex_t idx_x_arg, uindex_t idx_y_arg, uindex_t idx_z_arg);
288
289 /** \brief idx_x_arg for the existence of leaf node at (idx_x_arg, idx_y_arg,
290 * idx_z_arg).
291 * \param idx_x_arg: index of leaf node in the X axis.
292 * \param idx_y_arg: index of leaf node in the Y axis.
293 * \param idx_z_arg: index of leaf node in the Z axis.
294 * \return "true" if leaf node search is successful, otherwise it returns "false".
295 */
296 bool
297 existLeaf(uindex_t idx_x_arg, uindex_t idx_y_arg, uindex_t idx_z_arg) const;
298
299 /** \brief Remove leaf node at (idx_x_arg, idx_y_arg, idx_z_arg).
300 * \param idx_x_arg: index of leaf node in the X axis.
301 * \param idx_y_arg: index of leaf node in the Y axis.
302 * \param idx_z_arg: index of leaf node in the Z axis.
303 */
304 void
305 removeLeaf(uindex_t idx_x_arg, uindex_t idx_y_arg, uindex_t idx_z_arg);
306
307 /** \brief Return the amount of existing leafs in the octree.
308 * \return amount of registered leaf nodes.
309 */
310 std::size_t
312 {
313 return leaf_count_;
314 }
315
316 /** \brief Return the amount of existing branch nodes in the octree.
317 * \return amount of branch nodes.
318 */
319 std::size_t
321 {
322 return branch_count_;
323 }
324
325 /** \brief Delete the octree structure and its leaf nodes.
326 */
327 void
328 deleteTree();
329
330 /** \brief Serialize octree into a binary output vector describing its branch node
331 * structure.
332 * \param binary_tree_out_arg: reference to output vector for writing binary tree
333 * structure.
334 */
335 void
336 serializeTree(std::vector<char>& binary_tree_out_arg);
337
338 /** \brief Serialize octree into a binary output vector describing its branch node
339 * structure and push all LeafContainerT elements stored in the octree to a vector.
340 * \param binary_tree_out_arg: reference to output vector for writing binary tree
341 * structure.
342 * \param leaf_container_vector_arg: pointer to all LeafContainerT objects in the
343 * octree
344 */
345 void
346 serializeTree(std::vector<char>& binary_tree_out_arg,
347 std::vector<LeafContainerT*>& leaf_container_vector_arg);
348
349 /** \brief Outputs a vector of all LeafContainerT elements that are stored within the
350 * octree leaf nodes.
351 * \param leaf_container_vector_arg: pointers to LeafContainerT vector that receives a
352 * copy of all LeafContainerT objects in the octree.
353 */
354 void
355 serializeLeafs(std::vector<LeafContainerT*>& leaf_container_vector_arg);
356
357 /** \brief Deserialize a binary octree description vector and create a corresponding
358 * octree structure. Leaf nodes are initialized with getDataTByKey(..).
359 * \param binary_tree_input_arg: reference to input vector for reading binary tree
360 * structure.
361 */
362 void
363 deserializeTree(std::vector<char>& binary_tree_input_arg);
364
365 /** \brief Deserialize a binary octree description and create a corresponding octree
366 * structure. Leaf nodes are initialized with LeafContainerT elements from the
367 * dataVector.
368 * \param binary_tree_input_arg: reference to input vector for reading binary tree
369 * structure. \param leaf_container_vector_arg: pointer to container vector.
370 */
371 void
372 deserializeTree(std::vector<char>& binary_tree_input_arg,
373 std::vector<LeafContainerT*>& leaf_container_vector_arg);
374
375protected:
376 //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
377 // Protected octree methods based on octree keys
378 //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
379
380 /** \brief Create a leaf node
381 * \param key_arg: octree key addressing a leaf node.
382 * \return pointer to leaf node
383 */
384 LeafContainerT*
385 createLeaf(const OctreeKey& key_arg)
386 {
387
388 LeafNode* leaf_node = nullptr;
389 BranchNode* leaf_node_parent;
390
391 createLeafRecursive(key_arg, depth_mask_, root_node_, leaf_node, leaf_node_parent);
392
393 LeafContainerT* ret = leaf_node->getContainerPtr();
394
395 return ret;
396 }
397
398 /** \brief Find leaf node
399 * \param key_arg: octree key addressing a leaf node.
400 * \return pointer to leaf node. If leaf node is not found, this pointer returns 0.
401 */
402 LeafContainerT*
403 findLeaf(const OctreeKey& key_arg) const
404 {
405 LeafContainerT* result = nullptr;
406 findLeafRecursive(key_arg, depth_mask_, root_node_, result);
407 return result;
408 }
409
410 /** \brief Check for existence of a leaf node in the octree
411 * \param key_arg: octree key addressing a leaf node.
412 * \return "true" if leaf node is found; "false" otherwise
413 */
414 bool
415 existLeaf(const OctreeKey& key_arg) const
416 {
417 return (findLeaf(key_arg) != nullptr);
418 }
419
420 /** \brief Remove leaf node from octree
421 * \param key_arg: octree key addressing a leaf node.
422 */
423 void
424 removeLeaf(const OctreeKey& key_arg)
425 {
426 if (key_arg <= max_key_)
428 }
429
430 //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
431 // Branch node access functions
432 //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
433
434 /** \brief Retrieve root node */
437 {
438 return this->root_node_;
439 }
440
441 /** \brief Check if branch is pointing to a particular child node
442 * \param branch_arg: reference to octree branch class
443 * \param child_idx_arg: index to child node
444 * \return "true" if pointer to child node exists; "false" otherwise
445 */
446 bool
447 branchHasChild(const BranchNode& branch_arg, unsigned char child_idx_arg) const
448 {
449 // test occupancyByte for child existence
450 return (branch_arg.getChildPtr(child_idx_arg) != nullptr);
451 }
452
453 /** \brief Retrieve a child node pointer for child node at child_idx.
454 * \param branch_arg: reference to octree branch class
455 * \param child_idx_arg: index to child node
456 * \return pointer to octree child node class
457 */
459 getBranchChildPtr(const BranchNode& branch_arg, unsigned char child_idx_arg) const
460 {
461 return branch_arg.getChildPtr(child_idx_arg);
462 }
463
464 /** \brief Assign new child node to branch
465 * \param branch_arg: reference to octree branch class
466 * \param child_idx_arg: index to child node
467 * \param new_child_arg: pointer to new child node
468 */
469 void
471 unsigned char child_idx_arg,
472 OctreeNode* new_child_arg)
473 {
474 branch_arg[child_idx_arg] = new_child_arg;
475 }
476
477 /** \brief Generate bit pattern reflecting the existence of child node pointers
478 * \param branch_arg: reference to octree branch class
479 * \return a single byte with 8 bits of child node information
480 */
481 char
482 getBranchBitPattern(const BranchNode& branch_arg) const
483 {
484 char node_bits;
485
486 // create bit pattern
487 node_bits = 0;
488 for (unsigned char i = 0; i < 8; i++) {
489 const OctreeNode* child = branch_arg.getChildPtr(i);
490 node_bits |= static_cast<char>((!!child) << i);
491 }
492
493 return (node_bits);
494 }
495
496 /** \brief Delete child node and all its subchilds from octree
497 * \param branch_arg: reference to octree branch class
498 * \param child_idx_arg: index to child node
499 */
500 void
501 deleteBranchChild(BranchNode& branch_arg, unsigned char child_idx_arg)
502 {
503 if (branch_arg.hasChild(child_idx_arg)) {
504 OctreeNode* branch_child = branch_arg[child_idx_arg];
505
506 switch (branch_child->getNodeType()) {
507 case BRANCH_NODE: {
508 // free child branch recursively
509 deleteBranch(*static_cast<BranchNode*>(branch_child));
510 // delete branch node
511 delete branch_child;
512 } break;
513
514 case LEAF_NODE: {
515 // delete leaf node
516 delete branch_child;
517 break;
518 }
519 default:
520 break;
521 }
522
523 // set branch child pointer to 0
524 branch_arg[child_idx_arg] = nullptr;
525 }
526 }
527
528 /** \brief Delete branch and all its subchilds from octree
529 * \param branch_arg: reference to octree branch class
530 */
531 void
533 {
534 // delete all branch node children
535 for (char i = 0; i < 8; i++)
536 deleteBranchChild(branch_arg, i);
537 }
538
539 /** \brief Create and add a new branch child to a branch class
540 * \param branch_arg: reference to octree branch class
541 * \param child_idx_arg: index to child node
542 * \return pointer of new branch child to this reference
543 */
545 createBranchChild(BranchNode& branch_arg, unsigned char child_idx_arg)
546 {
547 BranchNode* new_branch_child = new BranchNode();
548 branch_arg[child_idx_arg] = static_cast<OctreeNode*>(new_branch_child);
549
550 return new_branch_child;
551 }
552
553 /** \brief Create and add a new leaf child to a branch class
554 * \param branch_arg: reference to octree branch class
555 * \param child_idx_arg: index to child node
556 * \return pointer of new leaf child to this reference
557 */
558 LeafNode*
559 createLeafChild(BranchNode& branch_arg, unsigned char child_idx_arg)
560 {
561 LeafNode* new_leaf_child = new LeafNode();
562 branch_arg[child_idx_arg] = static_cast<OctreeNode*>(new_leaf_child);
563
564 return new_leaf_child;
565 }
566
567 //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
568 // Recursive octree methods
569 //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
570
571 /** \brief Create a leaf node at octree key. If leaf node does already exist, it is
572 * returned.
573 * \param key_arg: reference to an octree key
574 * \param depth_mask_arg: depth mask used for octree key analysis and for branch depth
575 * indicator
576 * \param branch_arg: current branch node
577 * \param return_leaf_arg: return pointer to leaf node
578 * \param parent_of_leaf_arg: return pointer to parent of leaf node
579 * \return depth mask at which leaf node was created
580 **/
582 createLeafRecursive(const OctreeKey& key_arg,
583 uindex_t depth_mask_arg,
584 BranchNode* branch_arg,
585 LeafNode*& return_leaf_arg,
586 BranchNode*& parent_of_leaf_arg);
587
588 /** \brief Recursively search for a given leaf node and return a pointer.
589 * \note If leaf node does not exist, a 0 pointer is returned.
590 * \param key_arg: reference to an octree key
591 * \param depth_mask_arg: depth mask used for octree key analysis and for branch
592 * depth indicator
593 * \param branch_arg: current branch node
594 * \param result_arg: pointer to leaf node class
595 **/
596 void
597 findLeafRecursive(const OctreeKey& key_arg,
598 uindex_t depth_mask_arg,
599 BranchNode* branch_arg,
600 LeafContainerT*& result_arg) const;
601
602 /** \brief Recursively search and delete leaf node
603 * \param key_arg: reference to an octree key
604 * \param depth_mask_arg: depth mask used for octree key analysis and branch depth
605 * indicator
606 * \param branch_arg: current branch node
607 * \return "true" if branch does not contain any childs; "false" otherwise. This
608 * indicates if current branch can be deleted, too.
609 **/
610 bool
611 deleteLeafRecursive(const OctreeKey& key_arg,
612 uindex_t depth_mask_arg,
613 BranchNode* branch_arg);
614
615 /** \brief Recursively explore the octree and output binary octree description
616 * together with a vector of leaf node LeafContainerTs.
617 * \param branch_arg: current branch node
618 * \param key_arg: reference to an octree key
619 * \param binary_tree_out_arg: binary output vector
620 * \param leaf_container_vector_arg: writes LeafContainerT pointers to this
621 *LeafContainerT* vector.
622 **/
623 void
625 const BranchNode* branch_arg,
626 OctreeKey& key_arg,
627 std::vector<char>* binary_tree_out_arg,
628 typename std::vector<LeafContainerT*>* leaf_container_vector_arg) const;
629
630 /** \brief Recursive method for deserializing octree structure
631 * \param branch_arg: current branch node
632 * \param depth_mask_arg: depth mask used for octree key analysis and branch depth
633 * indicator
634 * \param key_arg: reference to an octree key
635 * \param binary_tree_input_it_arg: iterator to binary input vector
636 * \param binary_tree_input_it_end_arg: end iterator of binary input vector
637 * \param leaf_container_vector_it_arg: iterator pointing to current LeafContainerT
638 * object to be added to a leaf node
639 * \param leaf_container_vector_it_end_arg: iterator pointing to last object in
640 * LeafContainerT input vector.
641 **/
642 void
644 BranchNode* branch_arg,
645 uindex_t depth_mask_arg,
646 OctreeKey& key_arg,
647 typename std::vector<char>::const_iterator& binary_tree_input_it_arg,
648 typename std::vector<char>::const_iterator& binary_tree_input_it_end_arg,
649 typename std::vector<LeafContainerT*>::const_iterator*
650 leaf_container_vector_it_arg,
651 typename std::vector<LeafContainerT*>::const_iterator*
652 leaf_container_vector_it_end_arg);
653
654 //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
655 // Serialization callbacks
656 //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
657
658 /** \brief Callback executed for every leaf node during serialization
659 **/
660 virtual void
661 serializeTreeCallback(LeafContainerT&, const OctreeKey&) const
662 {}
663
664 /** \brief Callback executed for every leaf node during deserialization
665 **/
666 virtual void
667 deserializeTreeCallback(LeafContainerT&, const OctreeKey&)
668 {}
669
670 //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
671 // Helpers
672 //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
673
674 /** \brief Test if octree is able to dynamically change its depth. This is required
675 *for adaptive bounding box adjustment.
676 * \return "true"
677 **/
678 bool
680 {
681 return (true);
682 }
683};
684} // namespace octree
685} // namespace pcl
686
687#ifdef PCL_NO_PRECOMPILE
688#include <pcl/octree/impl/octree_base.hpp>
689#endif
void findLeafRecursive(const OctreeKey &key_arg, uindex_t depth_mask_arg, BranchNode *branch_arg, LeafContainerT *&result_arg) const
Recursively search for a given leaf node and return a pointer.
LeafContainerT * findLeaf(const OctreeKey &key_arg) const
Find leaf node.
virtual void serializeTreeCallback(LeafContainerT &, const OctreeKey &) const
Callback executed for every leaf node during serialization.
void setTreeDepth(uindex_t max_depth_arg)
Set the maximum depth of the octree.
const LeafNodeBreadthFirstIterator leaf_breadth_end()
void deserializeTreeRecursive(BranchNode *branch_arg, uindex_t depth_mask_arg, OctreeKey &key_arg, typename std::vector< char >::const_iterator &binary_tree_input_it_arg, typename std::vector< char >::const_iterator &binary_tree_input_it_end_arg, typename std::vector< LeafContainerT * >::const_iterator *leaf_container_vector_it_arg, typename std::vector< LeafContainerT * >::const_iterator *leaf_container_vector_it_end_arg)
Recursive method for deserializing octree structure.
LeafContainerT LeafContainer
Definition octree_base.h:70
OctreeFixedDepthIterator< OctreeT > FixedDepthIterator
OctreeDepthFirstIterator< OctreeT > Iterator
FixedDepthIterator fixed_depth_begin(uindex_t fixed_depth_arg=0u)
void serializeLeafs(std::vector< LeafContainerT * > &leaf_container_vector_arg)
Outputs a vector of all LeafContainerT elements that are stored within the octree leaf nodes.
LeafContainerT * createLeaf(uindex_t idx_x_arg, uindex_t idx_y_arg, uindex_t idx_z_arg)
Create new leaf node at (idx_x_arg, idx_y_arg, idx_z_arg).
std::size_t leaf_count_
Amount of leaf nodes
Definition octree_base.h:78
BranchNode * root_node_
Pointer to root branch node of octree
Definition octree_base.h:84
virtual ~OctreeBase()
Empty deconstructor.
uindex_t depth_mask_
Depth mask based on octree depth
Definition octree_base.h:87
bool branchHasChild(const BranchNode &branch_arg, unsigned char child_idx_arg) const
Check if branch is pointing to a particular child node.
BranchContainerT BranchContainer
Definition octree_base.h:69
const BreadthFirstIterator breadth_end()
void deleteBranch(BranchNode &branch_arg)
Delete branch and all its subchilds from octree.
bool octreeCanResize()
Test if octree is able to dynamically change its depth.
LeafContainerT * findLeaf(uindex_t idx_x_arg, uindex_t idx_y_arg, uindex_t idx_z_arg)
Find leaf node at (idx_x_arg, idx_y_arg, idx_z_arg).
void removeLeaf(const OctreeKey &key_arg)
Remove leaf node from octree.
DepthFirstIterator depth_begin(uindex_t max_depth_arg=0u)
std::size_t branch_count_
Amount of branch nodes
Definition octree_base.h:81
bool deleteLeafRecursive(const OctreeKey &key_arg, uindex_t depth_mask_arg, BranchNode *branch_arg)
Recursively search and delete leaf node.
bool dynamic_depth_enabled_
Enable dynamic_depth.
Definition octree_base.h:93
Iterator begin(uindex_t max_depth_arg=0u)
void setBranchChildPtr(BranchNode &branch_arg, unsigned char child_idx_arg, OctreeNode *new_child_arg)
Assign new child node to branch.
std::size_t getBranchCount() const
Return the amount of existing branch nodes in the octree.
uindex_t createLeafRecursive(const OctreeKey &key_arg, uindex_t depth_mask_arg, BranchNode *branch_arg, LeafNode *&return_leaf_arg, BranchNode *&parent_of_leaf_arg)
Create a leaf node at octree key.
LeafNodeDepthFirstIterator leaf_depth_begin(uindex_t max_depth_arg=0u)
OctreeNode * getRootNode() const
Retrieve root node.
void deserializeTree(std::vector< char > &binary_tree_input_arg)
Deserialize a binary octree description vector and create a corresponding octree structure.
const FixedDepthIterator fixed_depth_end()
uindex_t getTreeDepth() const
Get the maximum depth of the octree.
BranchNode * createBranchChild(BranchNode &branch_arg, unsigned char child_idx_arg)
Create and add a new branch child to a branch class.
OctreeBranchNode< BranchContainerT > BranchNode
Definition octree_base.h:66
void deleteTree()
Delete the octree structure and its leaf nodes.
OctreeDepthFirstIterator< OctreeT > DepthFirstIterator
void serializeTree(std::vector< char > &binary_tree_out_arg)
Serialize octree into a binary output vector describing its branch node structure.
const Iterator end()
uindex_t octree_depth_
Octree depth.
Definition octree_base.h:90
OctreeLeafNodeBreadthFirstIterator< OctreeT > LeafNodeBreadthFirstIterator
bool existLeaf(uindex_t idx_x_arg, uindex_t idx_y_arg, uindex_t idx_z_arg) const
idx_x_arg for the existence of leaf node at (idx_x_arg, idx_y_arg, idx_z_arg).
OctreeBase & operator=(const OctreeBase &source)
Copy operator.
const LeafNodeDepthFirstIterator leaf_depth_end()
void serializeTreeRecursive(const BranchNode *branch_arg, OctreeKey &key_arg, std::vector< char > *binary_tree_out_arg, typename std::vector< LeafContainerT * > *leaf_container_vector_arg) const
Recursively explore the octree and output binary octree description together with a vector of leaf no...
LeafContainerT * createLeaf(const OctreeKey &key_arg)
Create a leaf node.
char getBranchBitPattern(const BranchNode &branch_arg) const
Generate bit pattern reflecting the existence of child node pointers.
std::size_t getLeafCount() const
Return the amount of existing leafs in the octree.
void removeLeaf(uindex_t idx_x_arg, uindex_t idx_y_arg, uindex_t idx_z_arg)
Remove leaf node at (idx_x_arg, idx_y_arg, idx_z_arg).
LeafNodeBreadthFirstIterator leaf_breadth_begin(uindex_t max_depth_arg=0u)
void setMaxVoxelIndex(uindex_t max_voxel_index_arg)
Set the maximum amount of voxels per dimension.
OctreeLeafNodeDepthFirstIterator< OctreeT > LeafNodeDepthFirstIterator
OctreeBase(const OctreeBase &source)
Copy constructor.
BreadthFirstIterator breadth_begin(uindex_t max_depth_arg=0u)
OctreeBreadthFirstIterator< OctreeT > BreadthFirstIterator
OctreeKey max_key_
key range
Definition octree_base.h:96
LeafNode * createLeafChild(BranchNode &branch_arg, unsigned char child_idx_arg)
Create and add a new leaf child to a branch class.
bool existLeaf(const OctreeKey &key_arg) const
Check for existence of a leaf node in the octree.
OctreeBase()
Empty constructor.
OctreeNode * getBranchChildPtr(const BranchNode &branch_arg, unsigned char child_idx_arg) const
Retrieve a child node pointer for child node at child_idx.
const DepthFirstIterator depth_end()
void deleteBranchChild(BranchNode &branch_arg, unsigned char child_idx_arg)
Delete child node and all its subchilds from octree.
OctreeLeafNode< LeafContainerT > LeafNode
Definition octree_base.h:67
virtual void deserializeTreeCallback(LeafContainerT &, const OctreeKey &)
Callback executed for every leaf node during deserialization.
Abstract octree branch class
bool hasChild(unsigned char child_idx_arg) const
Check if branch is pointing to a particular child node.
OctreeNode * getChildPtr(unsigned char child_idx_arg) const
Get pointer to child.
Abstract octree iterator class
Octree key class
Definition octree_key.h:52
Abstract octree leaf class
const ContainerT * getContainerPtr() const
Get const pointer to container.
Abstract octree node class
virtual node_type_t getNodeType() const =0
Pure virtual method for receiving the type of octree node (branch or leaf)
detail::int_type_t< detail::index_type_size, false > uindex_t
Type used for an unsigned index in PCL.
Definition types.h:120
detail::int_type_t< detail::index_type_size, detail::index_type_signed > index_t
Type used for an index in PCL.
Definition types.h:112
Defines all the PCL and non-PCL macros used.