39 #ifndef PCL_OCTREE_TREE_BASE_H
40 #define PCL_OCTREE_TREE_BASE_H
44 #include <pcl/octree/octree_nodes.h>
45 #include <pcl/octree/octree_container.h>
46 #include <pcl/octree/octree_key.h>
47 #include <pcl/octree/octree_iterator.h>
60 template<
typename LeafContainerT = int,
61 typename BranchContainerT = OctreeContainerEmpty >
115 Iterator
begin (
unsigned int max_depth_arg = 0u)
117 return Iterator (
this, max_depth_arg? max_depth_arg : this->octree_depth_);
132 PCL_DEPRECATED (
"Please use leaf_depth_begin () instead.")
133 LeafNodeIterator
leaf_begin (
unsigned int max_depth_arg = 0u)
135 return LeafNodeIterator (
this, max_depth_arg? max_depth_arg : this->octree_depth_);
138 PCL_DEPRECATED (
"Please use leaf_depth_end () instead.")
223 leaf_count_ (source.leaf_count_),
224 branch_count_ (source.branch_count_),
225 root_node_ (new (BranchNode) (*(source.root_node_))),
226 depth_mask_ (source.depth_mask_),
227 octree_depth_ (source.octree_depth_),
228 dynamic_depth_enabled_(source.dynamic_depth_enabled_),
229 max_key_ (source.max_key_)
275 createLeaf (
unsigned int idx_x_arg,
unsigned int idx_y_arg,
unsigned int idx_z_arg);
285 findLeaf (
unsigned int idx_x_arg,
unsigned int idx_y_arg,
unsigned int idx_z_arg);
294 existLeaf (
unsigned int idx_x_arg,
unsigned int idx_y_arg,
unsigned int idx_z_arg)
const ;
302 removeLeaf (
unsigned int idx_x_arg,
unsigned int idx_y_arg,
unsigned int idx_z_arg);
338 serializeTree (std::vector<char>& binary_tree_out_arg, std::vector<LeafContainerT*>& leaf_container_vector_arg);
344 serializeLeafs (std::vector<LeafContainerT*>& leaf_container_vector_arg);
357 deserializeTree (std::vector<char>& binary_tree_input_arg, std::vector<LeafContainerT*>& leaf_container_vector_arg);
374 BranchNode* leaf_node_parent;
390 LeafContainerT* result = 0;
411 if (key_arg <= max_key_)
433 unsigned char child_idx_arg)
const
436 return (branch_arg.
getChildPtr(child_idx_arg) != 0);
446 unsigned char child_idx_arg)
const
457 unsigned char child_idx_arg,
460 branch_arg[child_idx_arg] = new_child_arg;
475 for (i = 0; i < 8; i++) {
477 node_bits |=
static_cast<char> ((!!child) << i);
490 if (branch_arg.
hasChild(child_idx_arg))
492 OctreeNode* branch_child = branch_arg[child_idx_arg];
499 deleteBranch (*static_cast<BranchNode*> (branch_child));
516 branch_arg[child_idx_arg] = 0;
529 for (i = 0; i < 8; i++)
539 unsigned char child_idx_arg)
541 BranchNode* new_branch_child =
new BranchNode();
542 branch_arg[child_idx_arg] =
static_cast<OctreeNode*
> (new_branch_child);
544 return new_branch_child;
555 LeafNode* new_leaf_child =
new LeafNode();
556 branch_arg[child_idx_arg] =
static_cast<OctreeNode*
> (new_leaf_child);
558 return new_leaf_child;
575 unsigned int depth_mask_arg,
576 BranchNode* branch_arg,
577 LeafNode*& return_leaf_arg,
578 BranchNode*& parent_of_leaf_arg);
589 unsigned int depth_mask_arg,
590 BranchNode* branch_arg,
591 LeafContainerT*& result_arg)
const;
601 unsigned int depth_mask_arg,
602 BranchNode* branch_arg);
613 std::vector<char>* binary_tree_out_arg,
614 typename std::vector<LeafContainerT*>* leaf_container_vector_arg)
const;
627 typename std::vector<char>::const_iterator& binary_tree_input_it_arg,
628 typename std::vector<char>::const_iterator& binary_tree_input_it_end_arg,
629 typename std::vector<LeafContainerT*>::const_iterator* leaf_container_vector_it_arg,
630 typename std::vector<LeafContainerT*>::const_iterator* leaf_container_vector_it_end_arg);
664 return log( n_arg ) / log( 2.0 );
679 #ifdef PCL_NO_PRECOMPILE
680 #include <pcl/octree/impl/octree_base.hpp>
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(unsigned int idx_x_arg, unsigned int idx_y_arg, unsigned int idx_z_arg)
Create new leaf node at (idx_x_arg, idx_y_arg, idx_z_arg).
const DepthFirstIterator depth_end()
OctreeBreadthFirstIterator< OctreeT > BreadthFirstIterator
void deleteTree()
Delete the octree structure and its leaf nodes.
bool branchHasChild(const BranchNode &branch_arg, unsigned char child_idx_arg) const
Check if branch is pointing to a particular child node.
void setMaxVoxelIndex(unsigned int max_voxel_index_arg)
Set the maximum amount of voxels per dimension.
OctreeLeafNodeBreadthFirstIterator< OctreeT > LeafNodeBreadthFirstIterator
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()
virtual void serializeTreeCallback(LeafContainerT &, const OctreeKey &) const
Callback executed for every leaf node during serialization.
bool deleteLeafRecursive(const OctreeKey &key_arg, unsigned int depth_mask_arg, BranchNode *branch_arg)
Recursively search and delete leaf node.
LeafContainerT * findLeaf(const OctreeKey &key_arg) const
Find leaf node.
This file defines compatibility wrappers for low level I/O functions.
virtual node_type_t getNodeType() const =0
Pure virtual method for receiving the type of octree node (branch or leaf)
const LeafNodeBreadthFirstIterator leaf_breadth_end()
const OctreeFixedDepthIterator< OctreeT > ConstFixedDepthIterator
virtual ~OctreeBase()
Empty deconstructor.
const OctreeLeafNodeDepthFirstIterator< OctreeT > ConstLeafNodeIterator
OctreeNode * getChildPtr(unsigned char child_idx_arg) const
Get pointer to child.
bool existLeaf(unsigned int idx_x_arg, unsigned int idx_y_arg, unsigned int idx_z_arg) const
idx_x_arg for the existence of leaf node at (idx_x_arg, idx_y_arg, idx_z_arg).
const LeafNodeDepthFirstIterator leaf_depth_end()
void deleteBranch(BranchNode &branch_arg)
Delete branch and all its subchilds from octree.
BranchContainerT BranchContainer
OctreeBase & operator=(const OctreeBase &source)
Copy operator.
void setTreeDepth(unsigned int max_depth_arg)
Set the maximum depth of the octree.
Iterator begin(unsigned int max_depth_arg=0u)
OctreeBase()
Empty constructor.
OctreeBase(const OctreeBase &source)
Copy constructor.
OctreeNode * getBranchChildPtr(const BranchNode &branch_arg, unsigned char child_idx_arg) const
Retrieve a child node pointer for child node at child_idx.
LeafNode * createLeafChild(BranchNode &branch_arg, unsigned char child_idx_arg)
Create and add a new leaf child to a branch class.
unsigned int octree_depth_
Octree depth.
BreadthFirstIterator breadth_begin(unsigned int max_depth_arg=0u)
const OctreeBreadthFirstIterator< OctreeT > ConstBreadthFirstIterator
unsigned int createLeafRecursive(const OctreeKey &key_arg, unsigned int depth_mask_arg, BranchNode *branch_arg, LeafNode *&return_leaf_arg, BranchNode *&parent_of_leaf_arg)
Create a leaf node at octree key.
void serializeTree(std::vector< char > &binary_tree_out_arg)
Serialize octree into a binary output vector describing its branch node structure.
void removeLeaf(unsigned int idx_x_arg, unsigned int idx_y_arg, unsigned int idx_z_arg)
Remove leaf node at (idx_x_arg, idx_y_arg, idx_z_arg).
bool hasChild(unsigned char child_idx_arg) const
Check if branch is pointing to a particular child node.
OctreeBase< LeafContainerT, BranchContainerT > OctreeT
BranchNode * createBranchChild(BranchNode &branch_arg, unsigned char child_idx_arg)
Create and add a new branch child to a branch class.
std::size_t getLeafCount() const
Return the amount of existing leafs in the octree.
OctreeKey max_key_
key range
bool octreeCanResize()
Test if octree is able to dynamically change its depth.
OctreeBranchNode< BranchContainerT > BranchNode
BranchNode * root_node_
Pointer to root branch node of octree.
void serializeLeafs(std::vector< LeafContainerT * > &leaf_container_vector_arg)
Outputs a vector of all LeafContainerT elements that are stored within the octree leaf nodes...
OctreeDepthFirstIterator< OctreeT > DepthFirstIterator
OctreeLeafNodeDepthFirstIterator< OctreeT > LeafNodeDepthFirstIterator
const ContainerT * getContainerPtr() const
Get const pointer to container.
LeafContainerT * findLeaf(unsigned int idx_x_arg, unsigned int idx_y_arg, unsigned int idx_z_arg)
Find leaf node at (idx_x_arg, idx_y_arg, idx_z_arg).
Octree leaf node iterator class.
char getBranchBitPattern(const BranchNode &branch_arg) const
Generate bit pattern reflecting the existence of child node pointers.
void removeLeaf(const OctreeKey &key_arg)
Remove leaf node from octree.
virtual void deserializeTreeCallback(LeafContainerT &, const OctreeKey &)
Callback executed for every leaf node during deserialization.
bool dynamic_depth_enabled_
Enable dynamic_depth.
LeafContainerT LeafContainer
LeafNodeDepthFirstIterator leaf_depth_begin(unsigned int max_depth_arg=0u)
LeafContainerT * createLeaf(const OctreeKey &key_arg)
Create a leaf node.
void findLeafRecursive(const OctreeKey &key_arg, unsigned int depth_mask_arg, BranchNode *branch_arg, LeafContainerT *&result_arg) const
Recursively search for a given leaf node and return a pointer.
Abstract octree leaf class
unsigned int getTreeDepth() const
Get the maximum depth of the octree.
OctreeLeafNodeDepthFirstIterator< OctreeT > LeafNodeIterator
void deserializeTreeRecursive(BranchNode *branch_arg, unsigned int 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.
OctreeLeafNode< LeafContainerT > LeafNode
std::size_t getBranchCount() const
Return the amount of existing branch nodes in the octree.
const LeafNodeIterator leaf_end()
bool existLeaf(const OctreeKey &key_arg) const
Check for existence of a leaf node in the octree.
DepthFirstIterator depth_begin(unsigned int max_depth_arg=0u)
OctreeFixedDepthIterator< OctreeT > FixedDepthIterator
void setBranchChildPtr(BranchNode &branch_arg, unsigned char child_idx_arg, OctreeNode *new_child_arg)
Assign new child node to branch.
Abstract octree iterator class
FixedDepthIterator fixed_depth_begin(unsigned int fixed_depth_arg=0u)
LeafNodeIterator leaf_begin(unsigned int max_depth_arg=0u)
OctreeNode * getRootNode() const
Retrieve root node.
const OctreeLeafNodeBreadthFirstIterator< OctreeT > ConstLeafNodeBreadthFirstIterator
const OctreeDepthFirstIterator< OctreeT > ConstIterator
const OctreeDepthFirstIterator< OctreeT > ConstDepthFirstIterator
Abstract octree branch class
LeafNodeBreadthFirstIterator leaf_breadth_begin(unsigned int max_depth_arg=0u)
std::size_t leaf_count_
Amount of leaf nodes.
const BreadthFirstIterator breadth_end()
const OctreeLeafNodeDepthFirstIterator< OctreeT > ConstLeafNodeDepthFirstIterator
Abstract octree node class
unsigned int depth_mask_
Depth mask based on octree depth.
double Log2(double n_arg)
Helper function to calculate the binary logarithm.
OctreeDepthFirstIterator< OctreeT > Iterator
std::size_t branch_count_
Amount of branch nodes.
Octree leaf node iterator class.
void deleteBranchChild(BranchNode &branch_arg, unsigned char child_idx_arg)
Delete child node and all its subchilds from octree.