Point Cloud Library (PCL) 1.13.0
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 friend class OctreeIteratorBase<const OctreeT>;
107 friend class OctreeDepthFirstIterator<const OctreeT>;
108 friend class OctreeBreadthFirstIterator<const OctreeT>;
109 friend class OctreeFixedDepthIterator<const OctreeT>;
110 friend class OctreeLeafNodeDepthFirstIterator<const OctreeT>;
112
113 // Octree default iterators
116
118 begin(uindex_t max_depth_arg = 0u)
119 {
120 return Iterator(this, max_depth_arg ? max_depth_arg : this->octree_depth_);
121 };
122
124 begin(uindex_t max_depth_arg = 0u) const
125 {
126 return ConstIterator(this, max_depth_arg ? max_depth_arg : this->octree_depth_);
127 };
128
130 cbegin(uindex_t max_depth_arg = 0u) const
131 {
132 return ConstIterator(this, max_depth_arg ? max_depth_arg : this->octree_depth_);
133 };
134
135 const Iterator
137 {
138 return Iterator(this, 0, nullptr);
139 };
140
141 const ConstIterator
142 end() const
143 {
144 return ConstIterator(this, 0, nullptr);
145 };
146
147 const ConstIterator
148 cend() const
149 {
150 return ConstIterator(this, 0, nullptr);
151 };
152
153 // Octree leaf node iterators
154 // The previous deprecated names
155 // LeafNodeIterator and ConstLeafNodeIterator are deprecated.
156 // Please use LeafNodeDepthFirstIterator and ConstLeafNodeDepthFirstIterator instead.
159
160 // The currently valid names
164
166 leaf_depth_begin(uindex_t max_depth_arg = 0u)
167 {
169 this, max_depth_arg ? max_depth_arg : this->octree_depth_);
170 };
171
173 leaf_depth_begin(uindex_t max_depth_arg = 0u) const
174 {
176 this, max_depth_arg ? max_depth_arg : this->octree_depth_);
177 };
178
181 {
182 return LeafNodeDepthFirstIterator(this, 0, nullptr);
183 };
184
187 {
188 return ConstLeafNodeDepthFirstIterator(this, 0, nullptr);
189 };
190
191 // Octree depth-first iterators
194
196 depth_begin(uindex_t max_depth_arg = 0u)
197 {
198 return DepthFirstIterator(this,
199 max_depth_arg ? max_depth_arg : this->octree_depth_);
200 };
201
203 depth_begin(uindex_t max_depth_arg = 0u) const
204 {
205 return ConstDepthFirstIterator(this,
206 max_depth_arg ? max_depth_arg : this->octree_depth_);
207 };
208
211 {
212 return DepthFirstIterator(this, 0, nullptr);
213 };
214
216 depth_end() const
217 {
218 return ConstDepthFirstIterator(this, 0, nullptr);
219 };
220
221 // Octree breadth-first iterators
224
226 breadth_begin(uindex_t max_depth_arg = 0u)
227 {
228 return BreadthFirstIterator(this,
229 max_depth_arg ? max_depth_arg : this->octree_depth_);
230 };
231
233 breadth_begin(uindex_t max_depth_arg = 0u) const
234 {
236 this, max_depth_arg ? max_depth_arg : this->octree_depth_);
237 };
238
241 {
242 return BreadthFirstIterator(this, 0, nullptr);
243 };
244
247 {
248 return ConstBreadthFirstIterator(this, 0, nullptr);
249 };
250
251 // Octree breadth iterators at a given depth
254
256 fixed_depth_begin(uindex_t fixed_depth_arg = 0u)
257 {
258 return FixedDepthIterator(this, fixed_depth_arg);
259 };
260
262 fixed_depth_begin(uindex_t fixed_depth_arg = 0u) const
263 {
264 return ConstFixedDepthIterator(this, fixed_depth_arg);
265 };
266
269 {
270 return FixedDepthIterator(this, 0, nullptr);
271 };
272
275 {
276 return ConstFixedDepthIterator(this, 0, nullptr);
277 };
278
279 // Octree leaf node iterators
283
285 leaf_breadth_begin(uindex_t max_depth_arg = 0u)
286 {
288 this, max_depth_arg ? max_depth_arg : this->octree_depth_);
289 };
290
292 leaf_breadth_begin(uindex_t max_depth_arg = 0u) const
293 {
295 this, max_depth_arg ? max_depth_arg : this->octree_depth_);
296 };
297
300 {
301 return LeafNodeBreadthFirstIterator(this, 0, nullptr);
302 };
303
306 {
307 return ConstLeafNodeBreadthFirstIterator(this, 0, nullptr);
308 };
309
310 /** \brief Empty constructor. */
311 OctreeBase();
312
313 /** \brief Empty deconstructor. */
314 virtual ~OctreeBase();
315
316 /** \brief Copy constructor. */
317 OctreeBase(const OctreeBase& source)
318 : leaf_count_(source.leaf_count_)
320 , root_node_(new (BranchNode)(*(source.root_node_)))
321 , depth_mask_(source.depth_mask_)
324 , max_key_(source.max_key_)
325 {}
326
327 /** \brief Copy operator. */
329 operator=(const OctreeBase& source)
330 {
331 leaf_count_ = source.leaf_count_;
333 delete root_node_;
334
335 root_node_ = new (BranchNode)(*(source.root_node_));
336 depth_mask_ = source.depth_mask_;
337 max_key_ = source.max_key_;
340 return (*this);
341 }
342
343 /** \brief Set the maximum amount of voxels per dimension.
344 * \param[in] max_voxel_index_arg maximum amount of voxels per dimension
345 */
346 void
347 setMaxVoxelIndex(uindex_t max_voxel_index_arg);
348
349 /** \brief Set the maximum depth of the octree.
350 * \param max_depth_arg: maximum depth of octree
351 */
352 void
353 setTreeDepth(uindex_t max_depth_arg);
354
355 /** \brief Get the maximum depth of the octree.
356 * \return depth_arg: maximum depth of octree
357 */
360 {
361 return this->octree_depth_;
362 }
363
364 /** \brief Create new leaf node at (idx_x_arg, idx_y_arg, idx_z_arg).
365 * \note If leaf node already exist, this method returns the existing node
366 * \param idx_x_arg: index of leaf node in the X axis.
367 * \param idx_y_arg: index of leaf node in the Y axis.
368 * \param idx_z_arg: index of leaf node in the Z axis.
369 * \return pointer to new leaf node container.
370 */
371 LeafContainerT*
372 createLeaf(uindex_t idx_x_arg, uindex_t idx_y_arg, uindex_t idx_z_arg);
373
374 /** \brief Find leaf node at (idx_x_arg, idx_y_arg, idx_z_arg).
375 * \note If leaf node already exist, this method returns the existing node
376 * \param idx_x_arg: index of leaf node in the X axis.
377 * \param idx_y_arg: index of leaf node in the Y axis.
378 * \param idx_z_arg: index of leaf node in the Z axis.
379 * \return pointer to leaf node container if found, null pointer otherwise.
380 */
381 LeafContainerT*
382 findLeaf(uindex_t idx_x_arg, uindex_t idx_y_arg, uindex_t idx_z_arg) const;
383
384 /** \brief idx_x_arg for the existence of leaf node at (idx_x_arg, idx_y_arg,
385 * idx_z_arg).
386 * \param idx_x_arg: index of leaf node in the X axis.
387 * \param idx_y_arg: index of leaf node in the Y axis.
388 * \param idx_z_arg: index of leaf node in the Z axis.
389 * \return "true" if leaf node search is successful, otherwise it returns "false".
390 */
391 bool
392 existLeaf(uindex_t idx_x_arg, uindex_t idx_y_arg, uindex_t idx_z_arg) const;
393
394 /** \brief Remove leaf node at (idx_x_arg, idx_y_arg, idx_z_arg).
395 * \param idx_x_arg: index of leaf node in the X axis.
396 * \param idx_y_arg: index of leaf node in the Y axis.
397 * \param idx_z_arg: index of leaf node in the Z axis.
398 */
399 void
400 removeLeaf(uindex_t idx_x_arg, uindex_t idx_y_arg, uindex_t idx_z_arg);
401
402 /** \brief Return the amount of existing leafs in the octree.
403 * \return amount of registered leaf nodes.
404 */
405 std::size_t
407 {
408 return leaf_count_;
409 }
410
411 /** \brief Return the amount of existing branch nodes in the octree.
412 * \return amount of branch nodes.
413 */
414 std::size_t
416 {
417 return branch_count_;
418 }
419
420 /** \brief Delete the octree structure and its leaf nodes.
421 */
422 void
423 deleteTree();
424
425 /** \brief Serialize octree into a binary output vector describing its branch node
426 * structure.
427 * \param binary_tree_out_arg: reference to output vector for writing binary tree
428 * structure.
429 */
430 void
431 serializeTree(std::vector<char>& binary_tree_out_arg) const;
432
433 /** \brief Serialize octree into a binary output vector describing its branch node
434 * structure and push all LeafContainerT elements stored in the octree to a vector.
435 * \param binary_tree_out_arg: reference to output vector for writing binary tree
436 * structure.
437 * \param leaf_container_vector_arg: pointer to all LeafContainerT objects in the
438 * octree
439 */
440 void
441 serializeTree(std::vector<char>& binary_tree_out_arg,
442 std::vector<LeafContainerT*>& leaf_container_vector_arg) const;
443
444 /** \brief Outputs a vector of all LeafContainerT elements that are stored within the
445 * octree leaf nodes.
446 * \param leaf_container_vector_arg: pointers to LeafContainerT vector that receives a
447 * copy of all LeafContainerT objects in the octree.
448 */
449 void
450 serializeLeafs(std::vector<LeafContainerT*>& leaf_container_vector_arg);
451
452 /** \brief Deserialize a binary octree description vector and create a corresponding
453 * octree structure. Leaf nodes are initialized with getDataTByKey(..).
454 * \param binary_tree_input_arg: reference to input vector for reading binary tree
455 * structure.
456 */
457 void
458 deserializeTree(std::vector<char>& binary_tree_input_arg);
459
460 /** \brief Deserialize a binary octree description and create a corresponding octree
461 * structure. Leaf nodes are initialized with LeafContainerT elements from the
462 * dataVector.
463 * \param binary_tree_input_arg: reference to input vector for reading binary tree
464 * structure. \param leaf_container_vector_arg: pointer to container vector.
465 */
466 void
467 deserializeTree(std::vector<char>& binary_tree_input_arg,
468 std::vector<LeafContainerT*>& leaf_container_vector_arg);
469
470protected:
471 //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
472 // Protected octree methods based on octree keys
473 //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
474
475 /** \brief Create a leaf node
476 * \param key_arg: octree key addressing a leaf node.
477 * \return pointer to leaf node
478 */
479 LeafContainerT*
480 createLeaf(const OctreeKey& key_arg)
481 {
482
483 LeafNode* leaf_node = nullptr;
484 BranchNode* leaf_node_parent;
485
486 createLeafRecursive(key_arg, depth_mask_, root_node_, leaf_node, leaf_node_parent);
487
488 LeafContainerT* ret = leaf_node->getContainerPtr();
489
490 return ret;
491 }
492
493 /** \brief Find leaf node
494 * \param key_arg: octree key addressing a leaf node.
495 * \return pointer to leaf node. If leaf node is not found, this pointer returns 0.
496 */
497 LeafContainerT*
498 findLeaf(const OctreeKey& key_arg) const
499 {
500 LeafContainerT* result = nullptr;
501 findLeafRecursive(key_arg, depth_mask_, root_node_, result);
502 return result;
503 }
504
505 /** \brief Check for existence of a leaf node in the octree
506 * \param key_arg: octree key addressing a leaf node.
507 * \return "true" if leaf node is found; "false" otherwise
508 */
509 bool
510 existLeaf(const OctreeKey& key_arg) const
511 {
512 return (findLeaf(key_arg) != nullptr);
513 }
514
515 /** \brief Remove leaf node from octree
516 * \param key_arg: octree key addressing a leaf node.
517 */
518 void
519 removeLeaf(const OctreeKey& key_arg)
520 {
521 if (key_arg <= max_key_)
523 }
524
525 //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
526 // Branch node access functions
527 //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
528
529 /** \brief Retrieve root node */
532 {
533 return this->root_node_;
534 }
535
536 /** \brief Check if branch is pointing to a particular child node
537 * \param branch_arg: reference to octree branch class
538 * \param child_idx_arg: index to child node
539 * \return "true" if pointer to child node exists; "false" otherwise
540 */
541 bool
542 branchHasChild(const BranchNode& branch_arg, unsigned char child_idx_arg) const
543 {
544 // test occupancyByte for child existence
545 return (branch_arg.getChildPtr(child_idx_arg) != nullptr);
546 }
547
548 /** \brief Retrieve a child node pointer for child node at child_idx.
549 * \param branch_arg: reference to octree branch class
550 * \param child_idx_arg: index to child node
551 * \return pointer to octree child node class
552 */
554 getBranchChildPtr(const BranchNode& branch_arg, unsigned char child_idx_arg) const
555 {
556 return branch_arg.getChildPtr(child_idx_arg);
557 }
558
559 /** \brief Assign new child node to branch
560 * \param branch_arg: reference to octree branch class
561 * \param child_idx_arg: index to child node
562 * \param new_child_arg: pointer to new child node
563 */
564 void
566 unsigned char child_idx_arg,
567 OctreeNode* new_child_arg)
568 {
569 branch_arg[child_idx_arg] = new_child_arg;
570 }
571
572 /** \brief Generate bit pattern reflecting the existence of child node pointers
573 * \param branch_arg: reference to octree branch class
574 * \return a single byte with 8 bits of child node information
575 */
576 char
577 getBranchBitPattern(const BranchNode& branch_arg) const
578 {
579 char node_bits;
580
581 // create bit pattern
582 node_bits = 0;
583 for (unsigned char i = 0; i < 8; i++) {
584 const OctreeNode* child = branch_arg.getChildPtr(i);
585 node_bits |= static_cast<char>((!!child) << i);
586 }
587
588 return (node_bits);
589 }
590
591 /** \brief Delete child node and all its subchilds from octree
592 * \param branch_arg: reference to octree branch class
593 * \param child_idx_arg: index to child node
594 */
595 void
596 deleteBranchChild(BranchNode& branch_arg, unsigned char child_idx_arg)
597 {
598 if (branch_arg.hasChild(child_idx_arg)) {
599 OctreeNode* branch_child = branch_arg[child_idx_arg];
600
601 switch (branch_child->getNodeType()) {
602 case BRANCH_NODE: {
603 // free child branch recursively
604 deleteBranch(*static_cast<BranchNode*>(branch_child));
605 // delete branch node
606 delete branch_child;
607 } break;
608
609 case LEAF_NODE: {
610 // delete leaf node
611 delete branch_child;
612 break;
613 }
614 default:
615 break;
616 }
617
618 // set branch child pointer to 0
619 branch_arg[child_idx_arg] = nullptr;
620 }
621 }
622
623 /** \brief Delete branch and all its subchilds from octree
624 * \param branch_arg: reference to octree branch class
625 */
626 void
628 {
629 // delete all branch node children
630 for (char i = 0; i < 8; i++)
631 deleteBranchChild(branch_arg, i);
632 }
633
634 /** \brief Create and add a new branch child to a branch class
635 * \param branch_arg: reference to octree branch class
636 * \param child_idx_arg: index to child node
637 * \return pointer of new branch child to this reference
638 */
640 createBranchChild(BranchNode& branch_arg, unsigned char child_idx_arg)
641 {
642 auto* new_branch_child = new BranchNode();
643 branch_arg[child_idx_arg] = static_cast<OctreeNode*>(new_branch_child);
644
645 return new_branch_child;
646 }
647
648 /** \brief Create and add a new leaf child to a branch class
649 * \param branch_arg: reference to octree branch class
650 * \param child_idx_arg: index to child node
651 * \return pointer of new leaf child to this reference
652 */
653 LeafNode*
654 createLeafChild(BranchNode& branch_arg, unsigned char child_idx_arg)
655 {
656 auto* new_leaf_child = new LeafNode();
657 branch_arg[child_idx_arg] = static_cast<OctreeNode*>(new_leaf_child);
658
659 return new_leaf_child;
660 }
661
662 //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
663 // Recursive octree methods
664 //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
665
666 /** \brief Create a leaf node at octree key. If leaf node does already exist, it is
667 * returned.
668 * \param key_arg: reference to an octree key
669 * \param depth_mask_arg: depth mask used for octree key analysis and for branch depth
670 * indicator
671 * \param branch_arg: current branch node
672 * \param return_leaf_arg: return pointer to leaf node
673 * \param parent_of_leaf_arg: return pointer to parent of leaf node
674 * \return depth mask at which leaf node was created
675 **/
677 createLeafRecursive(const OctreeKey& key_arg,
678 uindex_t depth_mask_arg,
679 BranchNode* branch_arg,
680 LeafNode*& return_leaf_arg,
681 BranchNode*& parent_of_leaf_arg);
682
683 /** \brief Recursively search for a given leaf node and return a pointer.
684 * \note If leaf node does not exist, a 0 pointer is returned.
685 * \param key_arg: reference to an octree key
686 * \param depth_mask_arg: depth mask used for octree key analysis and for branch
687 * depth indicator
688 * \param branch_arg: current branch node
689 * \param result_arg: pointer to leaf node class
690 **/
691 void
692 findLeafRecursive(const OctreeKey& key_arg,
693 uindex_t depth_mask_arg,
694 BranchNode* branch_arg,
695 LeafContainerT*& result_arg) const;
696
697 /** \brief Recursively search and delete leaf node
698 * \param key_arg: reference to an octree key
699 * \param depth_mask_arg: depth mask used for octree key analysis and branch depth
700 * indicator
701 * \param branch_arg: current branch node
702 * \return "true" if current branch contains child(ren); "false" otherwise. If it's
703 * true, current branch cannot be deleted.
704 **/
705 bool
706 deleteLeafRecursive(const OctreeKey& key_arg,
707 uindex_t depth_mask_arg,
708 BranchNode* branch_arg);
709
710 /** \brief Recursively explore the octree and output binary octree description
711 * together with a vector of leaf node LeafContainerTs.
712 * \param branch_arg: current branch node
713 * \param key_arg: reference to an octree key
714 * \param binary_tree_out_arg: binary output vector
715 * \param leaf_container_vector_arg: writes LeafContainerT pointers to this
716 *LeafContainerT* vector.
717 **/
718 void
720 const BranchNode* branch_arg,
721 OctreeKey& key_arg,
722 std::vector<char>* binary_tree_out_arg,
723 typename std::vector<LeafContainerT*>* leaf_container_vector_arg) const;
724
725 /** \brief Recursive method for deserializing octree structure
726 * \param branch_arg: current branch node
727 * \param depth_mask_arg: depth mask used for octree key analysis and branch depth
728 * indicator
729 * \param key_arg: reference to an octree key
730 * \param binary_tree_input_it_arg: iterator to binary input vector
731 * \param binary_tree_input_it_end_arg: end iterator of binary input vector
732 * \param leaf_container_vector_it_arg: iterator pointing to current LeafContainerT
733 * object to be added to a leaf node
734 * \param leaf_container_vector_it_end_arg: iterator pointing to last object in
735 * LeafContainerT input vector.
736 **/
737 void
739 BranchNode* branch_arg,
740 uindex_t depth_mask_arg,
741 OctreeKey& key_arg,
742 typename std::vector<char>::const_iterator& binary_tree_input_it_arg,
743 typename std::vector<char>::const_iterator& binary_tree_input_it_end_arg,
744 typename std::vector<LeafContainerT*>::const_iterator*
745 leaf_container_vector_it_arg,
746 typename std::vector<LeafContainerT*>::const_iterator*
747 leaf_container_vector_it_end_arg);
748
749 //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
750 // Serialization callbacks
751 //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
752
753 /** \brief Callback executed for every leaf node during serialization
754 **/
755 virtual void
756 serializeTreeCallback(LeafContainerT&, const OctreeKey&) const
757 {}
758
759 /** \brief Callback executed for every leaf node during deserialization
760 **/
761 virtual void
762 deserializeTreeCallback(LeafContainerT&, const OctreeKey&)
763 {}
764
765 //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
766 // Helpers
767 //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
768
769 /** \brief Test if octree is able to dynamically change its depth. This is required
770 *for adaptive bounding box adjustment.
771 * \return "true"
772 **/
773 bool
775 {
776 return (true);
777 }
778};
779} // namespace octree
780} // namespace pcl
781
782#ifdef PCL_NO_PRECOMPILE
783#include <pcl/octree/impl/octree_base.hpp>
784#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.
ConstLeafNodeDepthFirstIterator leaf_depth_begin(uindex_t max_depth_arg=0u) const
Definition: octree_base.h:173
ConstLeafNodeBreadthFirstIterator leaf_breadth_begin(uindex_t max_depth_arg=0u) const
Definition: octree_base.h:292
LeafContainerT * findLeaf(const OctreeKey &key_arg) const
Find leaf node.
Definition: octree_base.h:498
virtual void serializeTreeCallback(LeafContainerT &, const OctreeKey &) const
Callback executed for every leaf node during serialization.
Definition: octree_base.h:756
void setTreeDepth(uindex_t max_depth_arg)
Set the maximum depth of the octree.
Definition: octree_base.hpp:87
OctreeDepthFirstIterator< const OctreeT > ConstIterator
Definition: octree_base.h:115
ConstIterator begin(uindex_t max_depth_arg=0u) const
Definition: octree_base.h:124
const LeafNodeBreadthFirstIterator leaf_breadth_end()
Definition: octree_base.h:299
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
Definition: octree_base.h:252
OctreeDepthFirstIterator< OctreeT > Iterator
Definition: octree_base.h:114
FixedDepthIterator fixed_depth_begin(uindex_t fixed_depth_arg=0u)
Definition: octree_base.h:256
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.
Definition: octree_base.hpp:59
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.
Definition: octree_base.h:542
BranchContainerT BranchContainer
Definition: octree_base.h:69
const BreadthFirstIterator breadth_end()
Definition: octree_base.h:240
OctreeFixedDepthIterator< const OctreeT > ConstFixedDepthIterator
Definition: octree_base.h:253
const ConstFixedDepthIterator fixed_depth_end() const
Definition: octree_base.h:274
void deleteBranch(BranchNode &branch_arg)
Delete branch and all its subchilds from octree.
Definition: octree_base.h:627
void removeLeaf(const OctreeKey &key_arg)
Remove leaf node from octree.
Definition: octree_base.h:519
const ConstIterator cend() const
Definition: octree_base.h:148
DepthFirstIterator depth_begin(uindex_t max_depth_arg=0u)
Definition: octree_base.h:196
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)
Definition: octree_base.h:118
void setBranchChildPtr(BranchNode &branch_arg, unsigned char child_idx_arg, OctreeNode *new_child_arg)
Assign new child node to branch.
Definition: octree_base.h:565
std::size_t getBranchCount() const
Return the amount of existing branch nodes in the octree.
Definition: octree_base.h:415
OctreeLeafNodeDepthFirstIterator< const OctreeT > ConstLeafNodeDepthFirstIterator
Definition: octree_base.h:163
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)
Definition: octree_base.h:166
OctreeNode * getRootNode() const
Retrieve root node.
Definition: octree_base.h:531
OctreeDepthFirstIterator< const OctreeT > ConstDepthFirstIterator
Definition: octree_base.h:193
void deserializeTree(std::vector< char > &binary_tree_input_arg)
Deserialize a binary octree description vector and create a corresponding octree structure.
const ConstLeafNodeDepthFirstIterator leaf_depth_end() const
Definition: octree_base.h:186
const ConstIterator end() const
Definition: octree_base.h:142
const FixedDepthIterator fixed_depth_end()
Definition: octree_base.h:268
uindex_t getTreeDepth() const
Get the maximum depth of the octree.
Definition: octree_base.h:359
OctreeLeafNodeBreadthFirstIterator< const OctreeT > ConstLeafNodeBreadthFirstIterator
Definition: octree_base.h:282
BranchNode * createBranchChild(BranchNode &branch_arg, unsigned char child_idx_arg)
Create and add a new branch child to a branch class.
Definition: octree_base.h:640
OctreeBranchNode< BranchContainerT > BranchNode
Definition: octree_base.h:66
const ConstLeafNodeBreadthFirstIterator leaf_breadth_end() const
Definition: octree_base.h:305
ConstDepthFirstIterator depth_begin(uindex_t max_depth_arg=0u) const
Definition: octree_base.h:203
void deleteTree()
Delete the octree structure and its leaf nodes.
OctreeDepthFirstIterator< OctreeT > DepthFirstIterator
Definition: octree_base.h:192
const Iterator end()
Definition: octree_base.h:136
OctreeBreadthFirstIterator< const OctreeT > ConstBreadthFirstIterator
Definition: octree_base.h:223
void serializeTree(std::vector< char > &binary_tree_out_arg) const
Serialize octree into a binary output vector describing its branch node structure.
ConstIterator cbegin(uindex_t max_depth_arg=0u) const
Definition: octree_base.h:130
uindex_t octree_depth_
Octree depth.
Definition: octree_base.h:90
OctreeLeafNodeBreadthFirstIterator< OctreeT > LeafNodeBreadthFirstIterator
Definition: octree_base.h:280
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.
Definition: octree_base.h:329
const LeafNodeDepthFirstIterator leaf_depth_end()
Definition: octree_base.h:180
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.
Definition: octree_base.h:480
LeafContainerT * findLeaf(uindex_t idx_x_arg, uindex_t idx_y_arg, uindex_t idx_z_arg) const
Find leaf node at (idx_x_arg, idx_y_arg, idx_z_arg).
char getBranchBitPattern(const BranchNode &branch_arg) const
Generate bit pattern reflecting the existence of child node pointers.
Definition: octree_base.h:577
std::size_t getLeafCount() const
Return the amount of existing leafs in the octree.
Definition: octree_base.h:406
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)
Definition: octree_base.h:285
void setMaxVoxelIndex(uindex_t max_voxel_index_arg)
Set the maximum amount of voxels per dimension.
Definition: octree_base.hpp:69
OctreeLeafNodeDepthFirstIterator< OctreeT > LeafNodeDepthFirstIterator
Definition: octree_base.h:161
OctreeBase(const OctreeBase &source)
Copy constructor.
Definition: octree_base.h:317
bool octreeCanResize() const
Test if octree is able to dynamically change its depth.
Definition: octree_base.h:774
BreadthFirstIterator breadth_begin(uindex_t max_depth_arg=0u)
Definition: octree_base.h:226
const ConstDepthFirstIterator depth_end() const
Definition: octree_base.h:216
ConstBreadthFirstIterator breadth_begin(uindex_t max_depth_arg=0u) const
Definition: octree_base.h:233
OctreeBreadthFirstIterator< OctreeT > BreadthFirstIterator
Definition: octree_base.h:222
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.
Definition: octree_base.h:654
bool existLeaf(const OctreeKey &key_arg) const
Check for existence of a leaf node in the octree.
Definition: octree_base.h:510
OctreeBase()
Empty constructor.
Definition: octree_base.hpp:48
OctreeNode * getBranchChildPtr(const BranchNode &branch_arg, unsigned char child_idx_arg) const
Retrieve a child node pointer for child node at child_idx.
Definition: octree_base.h:554
const DepthFirstIterator depth_end()
Definition: octree_base.h:210
void deleteBranchChild(BranchNode &branch_arg, unsigned char child_idx_arg)
Delete child node and all its subchilds from octree.
Definition: octree_base.h:596
const ConstBreadthFirstIterator breadth_end() const
Definition: octree_base.h:246
OctreeLeafNode< LeafContainerT > LeafNode
Definition: octree_base.h:67
virtual void deserializeTreeCallback(LeafContainerT &, const OctreeKey &)
Callback executed for every leaf node during deserialization.
Definition: octree_base.h:762
ConstFixedDepthIterator fixed_depth_begin(uindex_t fixed_depth_arg=0u) const
Definition: octree_base.h:262
Abstract octree branch class
Definition: octree_nodes.h:180
bool hasChild(unsigned char child_idx_arg) const
Check if branch is pointing to a particular child node.
Definition: octree_nodes.h:262
OctreeNode * getChildPtr(unsigned char child_idx_arg) const
Get pointer to child.
Definition: octree_nodes.h:241
Abstract octree iterator class
Octree key class
Definition: octree_key.h:54
Octree leaf node iterator class.
Abstract octree leaf class
Definition: octree_nodes.h:81
const ContainerT * getContainerPtr() const
Get const pointer to container.
Definition: octree_nodes.h:154
Abstract octree node class
Definition: octree_nodes.h:59
virtual node_type_t getNodeType() const =0
Pure virtual method for retrieving 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.