39 #ifndef PCL_OCTREE_2BUF_BASE_HPP 40 #define PCL_OCTREE_2BUF_BASE_HPP 47 template<
typename LeafContainerT,
typename BranchContainerT>
55 tree_dirty_flag_ (false),
57 dynamic_depth_enabled_(false)
62 template<
typename LeafContainerT,
typename BranchContainerT>
71 template<
typename LeafContainerT,
typename BranchContainerT>
void 74 unsigned int treeDepth;
76 assert (max_voxel_index_arg > 0);
80 static_cast<unsigned int> (std::ceil (
Log2 (max_voxel_index_arg))))),
81 static_cast<unsigned int> (0));
88 template<
typename LeafContainerT,
typename BranchContainerT>
void 91 assert (depth_arg > 0);
104 template<
typename LeafContainerT,
typename BranchContainerT> LeafContainerT*
108 OctreeKey key (idx_x_arg, idx_y_arg, idx_z_arg);
115 template<
typename LeafContainerT,
typename BranchContainerT> LeafContainerT*
119 OctreeKey key (idx_x_arg, idx_y_arg, idx_z_arg);
126 template<
typename LeafContainerT,
typename BranchContainerT>
bool 130 OctreeKey key (idx_x_arg, idx_y_arg, idx_z_arg);
137 template<
typename LeafContainerT,
typename BranchContainerT>
void 141 OctreeKey key (idx_x_arg, idx_y_arg, idx_z_arg);
148 template<
typename LeafContainerT,
typename BranchContainerT>
void 165 template<
typename LeafContainerT,
typename BranchContainerT>
void 182 unsigned char child_idx;
184 for (child_idx = 0; child_idx < 8; child_idx++)
191 template<
typename LeafContainerT,
typename BranchContainerT>
void 193 bool do_XOR_encoding_arg)
198 binary_tree_out_arg.clear ();
208 template<
typename LeafContainerT,
typename BranchContainerT>
void 210 std::vector<LeafContainerT*>& leaf_container_vector_arg,
211 bool do_XOR_encoding_arg)
216 binary_tree_out_arg.clear ();
217 leaf_container_vector_arg.clear ();
229 template<
typename LeafContainerT,
typename BranchContainerT>
void 235 leaf_container_vector_arg.clear ();
246 template<
typename LeafContainerT,
typename BranchContainerT>
void 248 bool do_XOR_decoding_arg)
256 std::vector<char>::const_iterator binary_tree_in_it = binary_tree_in_arg.begin ();
257 std::vector<char>::const_iterator binary_tree_in_it_end = binary_tree_in_arg.end ();
260 binary_tree_in_it, binary_tree_in_it_end, 0, 0,
false,
261 do_XOR_decoding_arg);
268 template<
typename LeafContainerT,
typename BranchContainerT>
void 270 std::vector<LeafContainerT*>& leaf_container_vector_arg,
271 bool do_XOR_decoding_arg)
276 typename std::vector<LeafContainerT*>::const_iterator leaf_container_vector_it = leaf_container_vector_arg.begin ();
279 typename std::vector<LeafContainerT*>::const_iterator leaf_container_vector_it_end = leaf_container_vector_arg.end ();
285 std::vector<char>::const_iterator binary_tree_in_it = binary_tree_in_arg.begin ();
286 std::vector<char>::const_iterator binary_tree_in_it_end = binary_tree_in_arg.end ();
292 binary_tree_in_it_end,
293 &leaf_container_vector_it,
294 &leaf_container_vector_it_end,
296 do_XOR_decoding_arg);
305 template<
typename LeafContainerT,
typename BranchContainerT>
void 311 leaf_container_vector_arg.clear ();
321 template<
typename LeafContainerT,
typename BranchContainerT>
324 unsigned int depth_mask_arg,
328 bool branch_reset_arg)
331 unsigned char child_idx;
334 if (branch_reset_arg)
337 for (child_idx = 0; child_idx < 8; child_idx++)
346 if (depth_mask_arg > 1)
364 child_branch =
static_cast<BranchNode*
> (child_node);
389 return createLeafRecursive (key_arg, depth_mask_arg / 2, child_branch, return_leaf_arg, parent_of_leaf_arg, doNodeReset);
406 child_leaf =
static_cast<LeafNode*
> (child_node);
423 return_leaf_arg = child_leaf;
424 parent_of_leaf_arg = branch_arg;
430 parent_of_leaf_arg = branch_arg;
434 return depth_mask_arg;
438 template<
typename LeafContainerT,
typename BranchContainerT>
void 440 unsigned int depth_mask_arg,
442 LeafContainerT*& result_arg)
const 445 unsigned char child_idx;
450 if (depth_mask_arg > 1)
473 template<
typename LeafContainerT,
typename BranchContainerT>
bool 475 unsigned int depth_mask_arg,
479 unsigned char child_idx;
486 if (depth_mask_arg > 1)
490 bool bBranchOccupied;
500 if (!bBranchOccupied)
517 for (child_idx = 0; child_idx < 8; child_idx++)
529 template<
typename LeafContainerT,
typename BranchContainerT>
void Octree2BufBase<
532 std::vector<char>* binary_tree_out_arg,
533 typename std::vector<LeafContainerT*>* leaf_container_vector_arg,
534 bool do_XOR_encoding_arg,
535 bool new_leafs_filter_arg)
538 unsigned char child_idx;
541 char branch_bit_pattern_curr_buffer;
542 char branch_bit_pattern_prev_buffer;
543 char node_XOR_bit_pattern;
550 node_XOR_bit_pattern = branch_bit_pattern_curr_buffer ^ branch_bit_pattern_prev_buffer;
552 if (binary_tree_out_arg)
554 if (do_XOR_encoding_arg)
557 binary_tree_out_arg->push_back (node_XOR_bit_pattern);
562 binary_tree_out_arg->push_back (branch_bit_pattern_curr_buffer);
567 for (child_idx = 0; child_idx < 8; child_idx++)
582 leaf_container_vector_arg, do_XOR_encoding_arg, new_leafs_filter_arg);
589 if (new_leafs_filter_arg)
593 if (leaf_container_vector_arg)
601 if (leaf_container_vector_arg)
628 template<
typename LeafContainerT,
typename BranchContainerT>
void 630 unsigned int depth_mask_arg,
OctreeKey& key_arg,
631 typename std::vector<char>::const_iterator& binaryTreeIT_arg,
632 typename std::vector<char>::const_iterator& binaryTreeIT_End_arg,
633 typename std::vector<LeafContainerT*>::const_iterator* dataVectorIterator_arg,
634 typename std::vector<LeafContainerT*>::const_iterator* dataVectorEndIterator_arg,
635 bool branch_reset_arg,
bool do_XOR_decoding_arg)
638 unsigned char child_idx;
642 char recoveredNodeBits;
645 if (branch_reset_arg)
648 for (child_idx = 0; child_idx < 8; child_idx++)
654 if (binaryTreeIT_arg!=binaryTreeIT_End_arg) {
656 nodeBits = *binaryTreeIT_arg++;
660 if (do_XOR_decoding_arg)
666 recoveredNodeBits = nodeBits;
670 for (child_idx = 0; child_idx < 8; child_idx++)
673 if (recoveredNodeBits & (1 << child_idx))
682 if (depth_mask_arg > 1)
697 child_branch =
static_cast<BranchNode*
> (child_node);
725 binaryTreeIT_arg, binaryTreeIT_End_arg,
726 dataVectorIterator_arg, dataVectorEndIterator_arg,
727 doNodeReset, do_XOR_decoding_arg);
741 child_leaf =
static_cast<LeafNode*
> (child_node);
757 if (dataVectorIterator_arg
758 && (*dataVectorIterator_arg != *dataVectorEndIterator_arg))
760 LeafContainerT& container = **child_leaf;
761 container = ***dataVectorIterator_arg;
762 ++*dataVectorIterator_arg;
789 template<
typename LeafContainerT,
typename BranchContainerT>
void 793 unsigned char child_idx;
796 char occupied_children_bit_pattern_prev_buffer;
797 char node_XOR_bit_pattern;
798 char unused_branches_bit_pattern;
807 unused_branches_bit_pattern = node_XOR_bit_pattern & occupied_children_bit_pattern_prev_buffer;
810 for (child_idx = 0; child_idx < 8; child_idx++)
833 if (unused_branches_bit_pattern & (1 << child_idx))
843 #define PCL_INSTANTIATE_Octree2BufBase(T) template class PCL_EXPORTS pcl::octree::Octree2BufBase<T>; double Log2(double n_arg)
Helper function to calculate the binary logarithm.
Octree2BufBase()
Empty constructor.
OctreeNode * getChildPtr(unsigned char buffer_arg, unsigned char index_arg) const
Get child pointer in current branch node.
void serializeLeafs(std::vector< LeafContainerT *> &leaf_container_vector_arg)
Outputs a vector of all DataT elements that are stored within the octree leaf nodes.
unsigned int createLeafRecursive(const OctreeKey &key_arg, unsigned int depth_mask_arg, BranchNode *branch_arg, LeafNode *&return_leaf_arg, BranchNode *&parent_of_leaf_arg, bool branch_reset_arg=false)
Create a leaf node at octree key.
void setTreeDepth(unsigned int depth_arg)
Set the maximum depth of the octree.
void treeCleanUpRecursive(BranchNode *branch_arg)
Recursively explore the octree and remove unused branch and leaf nodes.
static const unsigned char maxDepth
unsigned int octree_depth_
Octree depth.
char getBranchBitPattern(const BranchNode &branch_arg) const
Generate bit pattern reflecting the existence of child node pointers for current buffer.
virtual node_type_t getNodeType() const =0
Pure virtual method for receiving the type of octree node (branch or leaf)
LeafNode * createLeafChild(BranchNode &branch_arg, unsigned char child_idx_arg)
Fetch and add a new leaf child to a branch class.
OctreeKey max_key_
key range
void deleteBranch(BranchNode &branch_arg)
Delete branch and all its subchilds from octree (both buffers)
void serializeTreeRecursive(BranchNode *branch_arg, OctreeKey &key_arg, std::vector< char > *binary_tree_out_arg, typename std::vector< LeafContainerT *> *leaf_container_vector_arg, bool do_XOR_encoding_arg=false, bool new_leafs_filter_arg=false)
Recursively explore the octree and output binary octree description together with a vector of leaf no...
void deserializeTree(std::vector< char > &binary_tree_in_arg, bool do_XOR_decoding_arg=false)
Deserialize a binary octree description vector and create a corresponding octree structure.
void deserializeTreeRecursive(BranchNode *branch_arg, unsigned int depth_mask_arg, OctreeKey &key_arg, typename std::vector< char >::const_iterator &binary_tree_in_it_arg, typename std::vector< char >::const_iterator &binary_tree_in_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, bool branch_reset_arg=false, bool do_XOR_decoding_arg=false)
Rebuild an octree based on binary XOR octree description and DataT objects for leaf node initializati...
void deleteTree()
Delete the octree structure and its leaf nodes.
void popBranch()
pop child node from octree key
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.
void switchBuffers()
Switch buffers and reset current octree structure.
void serializeTree(std::vector< char > &binary_tree_out_arg, bool do_XOR_encoding_arg=false)
Serialize octree into a binary output vector describing its branch node structure.
virtual ~Octree2BufBase()
Empty deconstructor.
void deleteBranchChild(BranchNode &branch_arg, unsigned char buffer_selector_arg, unsigned char child_idx_arg)
Delete child node and all its subchilds from octree in specific buffer.
void setMaxVoxelIndex(unsigned int max_voxel_index_arg)
Set the maximum amount of voxels per dimension.
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).
virtual void deserializeTreeCallback(LeafContainerT &, const OctreeKey &)
Callback executed for every leaf node data during deserialization.
void serializeNewLeafs(std::vector< LeafContainerT *> &leaf_container_vector_arg)
Outputs a vector of all DataT elements from leaf nodes, that do not exist in the previous octree buff...
unsigned char getChildIdxWithDepthMask(unsigned int depthMask) const
get child node index using depthMask
std::size_t branch_count_
Amount of branch nodes.
bool existLeaf(unsigned int idx_x_arg, unsigned int idx_y_arg, unsigned int idx_z_arg) const
Check for the existence of leaf node at (idx_x_arg, idx_y_arg, idx_z_arg).
char getBranchXORBitPattern(const BranchNode &branch_arg) const
Generate XOR bit pattern reflecting differences between the two octree buffers.
Abstract octree leaf class
unsigned char buffer_selector_
Currently active octree buffer.
const ContainerT * getContainerPtr() const
Get const pointer to container.
virtual void serializeTreeCallback(LeafContainerT &, const OctreeKey &)
Callback executed for every leaf node data during serialization.
Octree double buffer class
BranchNode * createBranchChild(BranchNode &branch_arg, unsigned char child_idx_arg)
Fetch and add a new branch child to a branch class in current buffer.
BranchNode * root_node_
Pointer to root branch node of octree.
unsigned int depth_mask_
Depth mask based on octree depth.
void setChildPtr(unsigned char buffer_arg, unsigned char index_arg, OctreeNode *newNode_arg)
Set child pointer in current branch node.
void pushBranch(unsigned char childIndex)
push a child node to the octree key
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 node class
std::size_t leaf_count_
Amount of leaf nodes.
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 deleteLeafRecursive(const OctreeKey &key_arg, unsigned int depth_mask_arg, BranchNode *branch_arg)
Recursively search and delete leaf node.
bool hasChild(unsigned char buffer_arg, unsigned char index_arg) const
Check if branch is pointing to a particular child node.