39 #ifndef PCL_OCTREE_TREE_BASE_H
40 #define PCL_OCTREE_TREE_BASE_H
45 #include "octree_nodes.h"
46 #include "octree_container.h"
47 #include "octree_key.h"
48 #include "octree_iterator.h"
61 template<
typename LeafContainerT = int,
62 typename BranchContainerT = OctreeContainerEmpty >
168 createLeaf (
unsigned int idx_x_arg,
unsigned int idx_y_arg,
unsigned int idx_z_arg);
178 findLeaf (
unsigned int idx_x_arg,
unsigned int idx_y_arg,
unsigned int idx_z_arg);
187 existLeaf (
unsigned int idx_x_arg,
unsigned int idx_y_arg,
unsigned int idx_z_arg)
const ;
195 removeLeaf (
unsigned int idx_x_arg,
unsigned int idx_y_arg,
unsigned int idx_z_arg);
231 serializeTree (std::vector<char>& binary_tree_out_arg, std::vector<LeafContainerT*>& leaf_container_vector_arg);
237 serializeLeafs (std::vector<LeafContainerT*>& leaf_container_vector_arg);
250 deserializeTree (std::vector<char>& binary_tree_input_arg, std::vector<LeafContainerT*>& leaf_container_vector_arg);
283 LeafContainerT* result = 0;
326 unsigned char child_idx_arg)
const
329 return (branch_arg.
getChildPtr(child_idx_arg) != 0);
339 unsigned char child_idx_arg)
const
350 unsigned char child_idx_arg,
353 branch_arg[child_idx_arg] = new_child_arg;
368 for (i = 0; i < 8; i++) {
370 node_bits |=
static_cast<char> ((!!child) << i);
383 if (branch_arg.
hasChild(child_idx_arg))
385 OctreeNode* branch_child = branch_arg[child_idx_arg];
392 deleteBranch (*static_cast<BranchNode*> (branch_child));
409 branch_arg[child_idx_arg] = 0;
422 for (i = 0; i < 8; i++)
432 unsigned char child_idx_arg)
435 branch_arg[child_idx_arg] =
static_cast<OctreeNode*
> (new_branch_child);
437 return new_branch_child;
449 branch_arg[child_idx_arg] =
static_cast<OctreeNode*
> (new_leaf_child);
451 return new_leaf_child;
468 unsigned int depth_mask_arg,
482 unsigned int depth_mask_arg,
484 LeafContainerT*& result_arg)
const;
494 unsigned int depth_mask_arg,
506 std::vector<char>* binary_tree_out_arg,
507 typename std::vector<LeafContainerT*>* leaf_container_vector_arg)
const;
520 typename std::vector<char>::const_iterator& binary_tree_input_it_arg,
521 typename std::vector<char>::const_iterator& binary_tree_input_it_end_arg,
522 typename std::vector<LeafContainerT*>::const_iterator* leaf_container_vector_it_arg,
523 typename std::vector<LeafContainerT*>::const_iterator* leaf_container_vector_it_end_arg);
557 return log( n_arg ) / log( 2.0 );
OctreeBase()
Empty constructor.
const OctreeBreadthFirstIterator< OctreeT > ConstBreadthFirstIterator
OctreeKey max_key_
key range
Iterator begin(unsigned int max_depth_arg=0)
BranchNode * createBranchChild(BranchNode &branch_arg, unsigned char child_idx_arg)
Create and add a new branch child to a branch class.
void removeLeaf(const OctreeKey &key_arg)
Remove leaf node from octree.
OctreeBase(const OctreeBase &source)
Copy constructor.
BreadthFirstIterator breadth_begin(unsigned int max_depth_arg=0)
LeafContainerT * createLeaf(const OctreeKey &key_arg)
Create a leaf node.
const ContainerT * getContainerPtr() const
Get const pointer to container.
LeafContainerT * findLeaf(const OctreeKey &key_arg) const
Find leaf node.
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).
unsigned int depth_mask_
Depth mask based on octree depth.
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).
Abstract octree leaf class
bool deleteLeafRecursive(const OctreeKey &key_arg, unsigned int depth_mask_arg, BranchNode *branch_arg)
Recursively search and delete leaf node.
OctreeNode * getBranchChildPtr(const BranchNode &branch_arg, unsigned char child_idx_arg) const
Retrieve a child node pointer for child node at child_idx.
const OctreeDepthFirstIterator< OctreeT > ConstDepthFirstIterator
std::size_t branch_count_
Amount of branch nodes.
OctreeNode * getRootNode() const
Retrieve root node.
Abstract octree branch class
virtual void serializeTreeCallback(LeafContainerT &, const OctreeKey &) const
Callback executed for every leaf node during serialization.
void deserializeTree(std::vector< char > &binary_tree_input_arg)
Deserialize a binary octree description vector and create a corresponding octree structure.
void setBranchChildPtr(BranchNode &branch_arg, unsigned char child_idx_arg, OctreeNode *new_child_arg)
Assign new child node to branch.
OctreeDepthFirstIterator< OctreeT > DepthFirstIterator
const BreadthFirstIterator breadth_end()
BranchNode * root_node_
Pointer to root branch node of octree.
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.
virtual void deserializeTreeCallback(LeafContainerT &, const OctreeKey &)
Callback executed for every leaf node during deserialization.
bool hasChild(unsigned char child_idx_arg) const
Check if branch is pointing to a particular child node.
LeafNode * createLeafChild(BranchNode &branch_arg, unsigned char child_idx_arg)
Create and add a new leaf child to a branch class.
virtual node_type_t getNodeType() const =0
Pure virtual method for receiving the type of octree node (branch or leaf)
OctreeNode * getChildPtr(unsigned char child_idx_arg) const
Get pointer to child.
bool octreeCanResize()
Test if octree is able to dynamically change its depth.
DepthFirstIterator depth_begin(unsigned int max_depth_arg=0)
Abstract octree node class
const DepthFirstIterator depth_end()
OctreeBase & operator=(const OctreeBase &source)
Copy operator.
bool branchHasChild(const BranchNode &branch_arg, unsigned char child_idx_arg) const
Check if branch is pointing to a particular child node.
OctreeLeafNodeIterator< OctreeT > LeafNodeIterator
bool dynamic_depth_enabled_
Enable dynamic_depth.
void setTreeDepth(unsigned int max_depth_arg)
Set the maximum depth of the octree.
std::size_t leaf_count_
Amount of leaf nodes.
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).
const OctreeLeafNodeIterator< OctreeT > ConstLeafNodeIterator
void serializeLeafs(std::vector< LeafContainerT * > &leaf_container_vector_arg)
Outputs a vector of all LeafContainerT elements that are stored within the octree leaf nodes...
const OctreeDepthFirstIterator< OctreeT > ConstIterator
BranchContainerT BranchContainer
std::size_t getBranchCount() const
Return the amount of existing branch nodes in the octree.
LeafContainerT LeafContainer
double Log2(double n_arg)
Helper function to calculate the binary logarithm.
Abstract octree iterator class
void deleteBranch(BranchNode &branch_arg)
Delete branch and all its subchilds from octree.
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.
unsigned int octree_depth_
Octree depth.
const LeafNodeIterator leaf_end()
OctreeBase< LeafContainerT, BranchContainerT > OctreeT
virtual ~OctreeBase()
Empty deconstructor.
void setMaxVoxelIndex(unsigned int max_voxel_index_arg)
Set the maximum amount of voxels per dimension.
void deleteTree()
Delete the octree structure and its leaf nodes.
std::size_t getLeafCount() const
Return the amount of existing leafs in the octree.
Octree leaf node iterator class.
unsigned int getTreeDepth() const
Get the maximum depth of the octree.
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).
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...
OctreeLeafNode< LeafContainerT > LeafNode
OctreeBreadthFirstIterator< OctreeT > BreadthFirstIterator
OctreeDepthFirstIterator< OctreeT > Iterator
void deleteBranchChild(BranchNode &branch_arg, unsigned char child_idx_arg)
Delete child node and all its subchilds from octree.
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.
OctreeBranchNode< BranchContainerT > BranchNode
bool existLeaf(const OctreeKey &key_arg) const
Check for existance of a leaf node in the octree.
char getBranchBitPattern(const BranchNode &branch_arg) const
Generate bit pattern reflecting the existence of child node pointers.
LeafNodeIterator leaf_begin(unsigned int max_depth_arg=0)