OcTree base class, to be used with with any kind of OcTreeDataNode. More...
#include <OcTreeBaseImpl.h>
Data Structures | |
| class | iterator_base |
| Base class for OcTree iterators. More... | |
| class | leaf_bbx_iterator |
| Bounding-box leaf iterator. More... | |
| class | leaf_iterator |
| Iterator to iterate over all leafs of the tree. More... | |
| class | tree_iterator |
| Iterator over the complete tree (inner nodes and leafs). More... | |
Public Types | |
| typedef leaf_iterator | iterator |
| typedef NODE | NodeType |
| Make the templated NODE type available from the outside. | |
Public Member Functions | |
| OcTreeKey | adjustKeyAtDepth (const OcTreeKey &key, unsigned int depth) const |
| Adjusts a 3D key from the lowest level to correspond to a higher depth (by shifting the key values) | |
| key_type | adjustKeyAtDepth (key_type key, unsigned int depth) const |
| Adjusts a single key value from the lowest level to correspond to a higher depth (by shifting the key value) | |
| iterator | begin (unsigned char maxDepth=0) const |
| leaf_iterator | begin_leafs (unsigned char maxDepth=0) const |
| leaf_bbx_iterator | begin_leafs_bbx (const OcTreeKey &min, const OcTreeKey &max, unsigned char maxDepth=0) const |
| leaf_bbx_iterator | begin_leafs_bbx (const point3d &min, const point3d &max, unsigned char maxDepth=0) const |
| tree_iterator | begin_tree (unsigned char maxDepth=0) const |
| size_t | calcNumNodes () const |
| Traverses the tree to calculate the total number of nodes. | |
| void | clear () |
| Deletes the complete tree structure. | |
| void | clearKeyRays () |
| Clear KeyRay vector to minimize unneeded memory. | |
| bool | computeRay (const point3d &origin, const point3d &end, std::vector< point3d > &ray) |
| Traces a ray from origin to end (excluding), returning the coordinates of all nodes traversed by the beam. | |
| bool | computeRayKeys (const point3d &origin, const point3d &end, KeyRay &ray) const |
| Traces a ray from origin to end (excluding), returning an OcTreeKey of all nodes traversed by the beam. | |
| OcTreeKey | coordToKey (const point3d &coord) const |
| Converts from a 3D coordinate into a 3D addressing key. | |
| OcTreeKey | coordToKey (const point3d &coord, unsigned depth) const |
| Converts from a 3D coordinate into a 3D addressing key at a given depth. | |
| key_type | coordToKey (double coordinate) const |
| Converts from a single coordinate into a discrete key. | |
| key_type | coordToKey (double coordinate, unsigned depth) const |
| Converts from a single coordinate into a discrete key at a given depth. | |
| OcTreeKey | coordToKey (double x, double y, double z) const |
| Converts from a 3D coordinate into a 3D addressing key. | |
| OcTreeKey | coordToKey (double x, double y, double z, unsigned depth) const |
| Converts from a 3D coordinate into a 3D addressing key at a given depth. | |
| bool | coordToKeyChecked (const point3d &coord, OcTreeKey &key) const |
| Converts a 3D coordinate into a 3D OcTreeKey, with boundary checking. | |
| bool | coordToKeyChecked (const point3d &coord, unsigned depth, OcTreeKey &key) const |
| Converts a 3D coordinate into a 3D OcTreeKey at a certain depth, with boundary checking. | |
| bool | coordToKeyChecked (double coordinate, key_type &key) const |
| Converts a single coordinate into a discrete addressing key, with boundary checking. | |
| bool | coordToKeyChecked (double coordinate, unsigned depth, key_type &key) const |
| Converts a single coordinate into a discrete addressing key, with boundary checking. | |
| bool | coordToKeyChecked (double x, double y, double z, OcTreeKey &key) const |
| Converts a 3D coordinate into a 3D OcTreeKey, with boundary checking. | |
| bool | coordToKeyChecked (double x, double y, double z, unsigned depth, OcTreeKey &key) const |
| Converts a 3D coordinate into a 3D OcTreeKey at a certain depth, with boundary checking. | |
| NODE * | createNodeChild (NODE *node, unsigned int childIdx) |
| Creates (allocates) the i-th child of the node. | |
| bool | deleteNode (const OcTreeKey &key, unsigned int depth=0) |
| Delete a node (if exists) given an addressing key. | |
| bool | deleteNode (const point3d &value, unsigned int depth=0) |
| Delete a node (if exists) given a 3d point. | |
| bool | deleteNode (double x, double y, double z, unsigned int depth=0) |
| Delete a node (if exists) given a 3d point. | |
| void | deleteNodeChild (NODE *node, unsigned int childIdx) |
| Deletes the i-th child of the node. | |
| const iterator | end () const |
| const leaf_iterator | end_leafs () const |
| const leaf_bbx_iterator | end_leafs_bbx () const |
| const tree_iterator | end_tree () const |
| virtual void | expand () |
| Expands all pruned nodes (reverse of prune()) | |
| virtual void | expandNode (NODE *node) |
| Expands a node (reverse of pruning): All children are created and their occupancy probability is set to the node's value. | |
| virtual void | getMetricMax (double &x, double &y, double &z) |
| maximum value of the bounding box of all known space in x, y, z | |
| void | getMetricMax (double &x, double &y, double &z) const |
| maximum value of the bounding box of all known space in x, y, z | |
| virtual void | getMetricMin (double &x, double &y, double &z) |
| minimum value of the bounding box of all known space in x, y, z | |
| void | getMetricMin (double &x, double &y, double &z) const |
| minimum value of the bounding box of all known space in x, y, z | |
| virtual void | getMetricSize (double &x, double &y, double &z) |
| Size of OcTree (all known space) in meters for x, y and z dimension. | |
| virtual void | getMetricSize (double &x, double &y, double &z) const |
| Size of OcTree (all known space) in meters for x, y and z dimension. | |
| const NODE * | getNodeChild (const NODE *node, unsigned int childIdx) const |
| NODE * | getNodeChild (NODE *node, unsigned int childIdx) const |
| double | getNodeSize (unsigned depth) const |
| size_t | getNumLeafNodes () const |
| Traverses the tree to calculate the total number of leaf nodes. | |
| double | getResolution () const |
| NODE * | getRoot () const |
| unsigned int | getTreeDepth () const |
| std::string | getTreeType () const |
| void | getUnknownLeafCenters (point3d_list &node_centers, point3d pmin, point3d pmax, unsigned int depth=0) const |
| return centers of leafs that do NOT exist (but could) in a given bounding box | |
| virtual bool | isNodeCollapsible (const NODE *node) const |
| A node is collapsible if all children exist, don't have children of their own and have the same occupancy value. | |
| point3d | keyToCoord (const OcTreeKey &key) const |
| converts from an addressing key at the lowest tree level into a coordinate corresponding to the key's center | |
| point3d | keyToCoord (const OcTreeKey &key, unsigned depth) const |
| converts from an addressing key at a given depth into a coordinate corresponding to the key's center | |
| double | keyToCoord (key_type key) const |
| converts from a discrete key at the lowest tree level into a coordinate corresponding to the key's center | |
| double | keyToCoord (key_type key, unsigned depth) const |
| converts from a discrete key at a given depth into a coordinate corresponding to the key's center | |
| unsigned long long | memoryFullGrid () const |
| virtual size_t | memoryUsage () const |
| virtual size_t | memoryUsageNode () const |
| bool | nodeChildExists (const NODE *node, unsigned int childIdx) const |
| Safe test if node has a child at index childIdx. | |
| bool | nodeHasChildren (const NODE *node) const |
| Safe test if node has any children. | |
| OcTreeBaseImpl (const OcTreeBaseImpl< NODE, INTERFACE > &rhs) | |
| Deep copy constructor. | |
| OcTreeBaseImpl (double resolution) | |
| bool | operator== (const OcTreeBaseImpl< NODE, INTERFACE > &rhs) const |
| Comparison between two octrees, all meta data, all nodes, and the structure must be identical. | |
| virtual void | prune () |
| Lossless compression of the octree: A node will replace all of its eight children if they have identical values. | |
| virtual bool | pruneNode (NODE *node) |
| Prunes a node when it is collapsible. | |
| std::istream & | readData (std::istream &s) |
| Read all nodes from the input stream (without file header), for this the tree needs to be already created. | |
| NODE * | search (const OcTreeKey &key, unsigned int depth=0) const |
| Search a node at specified depth given an addressing key (depth=0: search full tree depth) You need to check if the returned node is NULL, since it can be in unknown space. | |
| NODE * | search (const point3d &value, unsigned int depth=0) const |
| Search node at specified depth given a 3d point (depth=0: search full tree depth) You need to check if the returned node is NULL, since it can be in unknown space. | |
| NODE * | search (double x, double y, double z, unsigned int depth=0) const |
| Search node at specified depth given a 3d point (depth=0: search full tree depth). | |
| void | setResolution (double r) |
| Change the resolution of the octree, scaling all voxels. This will not preserve the (metric) scale! | |
| virtual size_t | size () const |
| void | swapContent (OcTreeBaseImpl< NODE, INTERFACE > &rhs) |
| Swap contents of two octrees, i.e., only the underlying pointer / tree structure. | |
| double | volume () |
| std::ostream & | writeData (std::ostream &s) const |
| Write complete state of tree to stream (without file header) unmodified. Pruning the tree first produces smaller files (lossless compression) | |
| virtual | ~OcTreeBaseImpl () |
Protected Member Functions | |
| void | allocNodeChildren (NODE *node) |
| void | calcMinMax () |
| recalculates min and max in x, y, z. Does nothing when tree size didn't change. | |
| void | calcNumNodesRecurs (NODE *node, size_t &num_nodes) const |
| void | deleteNodeRecurs (NODE *node) |
| Recursively delete a node and all children. Deallocates memory but does NOT set the node ptr to NULL nor updates tree size. | |
| bool | deleteNodeRecurs (NODE *node, unsigned int depth, unsigned int max_depth, const OcTreeKey &key) |
| recursive call of deleteNode() | |
| void | expandRecurs (NODE *node, unsigned int depth, unsigned int max_depth) |
| recursive call of expand() | |
| size_t | getNumLeafNodesRecurs (const NODE *parent) const |
| void | init () |
| initialize non-trivial members, helper for constructors | |
| OcTreeBaseImpl (double resolution, unsigned int tree_depth, unsigned int tree_max_val) | |
| Constructor to enable derived classes to change tree constants. This usually requires a re-implementation of some core tree-traversal functions as well! | |
| void | pruneRecurs (NODE *node, unsigned int depth, unsigned int max_depth, unsigned int &num_pruned) |
| recursive call of prune() | |
| std::istream & | readNodesRecurs (NODE *, std::istream &s) |
| recursive call of readData() | |
| std::ostream & | writeNodesRecurs (const NODE *, std::ostream &s) const |
| recursive call of writeData() | |
Protected Attributes | |
| std::vector< KeyRay > | keyrays |
| data structure for ray casting, array for multithreading | |
| const leaf_bbx_iterator | leaf_iterator_bbx_end |
| const leaf_iterator | leaf_iterator_end |
| double | max_value [3] |
| max in x, y, z | |
| double | min_value [3] |
| min in x, y, z contains the size of a voxel at level i (0: root node). tree_depth+1 levels (incl. 0) | |
| double | resolution |
| in meters | |
| double | resolution_factor |
| = 1. / resolution | |
| NODE * | root |
| Pointer to the root NODE, NULL for empty tree. | |
| bool | size_changed |
| std::vector< double > | sizeLookupTable |
| point3d | tree_center |
| const unsigned int | tree_depth |
| Maximum tree depth is fixed to 16 currently. | |
| const tree_iterator | tree_iterator_end |
| const unsigned int | tree_max_val |
| size_t | tree_size |
| number of nodes in tree flag to denote whether the octree extent changed (for lazy min/max eval) | |
Detailed Description
class octomap::OcTreeBaseImpl< NODE, INTERFACE >
OcTree base class, to be used with with any kind of OcTreeDataNode.
This tree implementation currently has a maximum depth of 16 nodes. For this reason, coordinates values have to be, e.g., below +/- 327.68 meters (2^15) at a maximum resolution of 0.01m.
This limitation enables the use of an efficient key generation method which uses the binary representation of the data point coordinates.
- Note
- You should probably not use this class directly, but OcTreeBase or OccupancyOcTreeBase instead
- Template Parameters
-
NODE Node class to be used in tree (usually derived from OcTreeDataNode) INTERFACE Interface to be derived from, should be either AbstractOcTree or AbstractOccupancyOcTree
Member Typedef Documentation
◆ iterator
| typedef leaf_iterator octomap::OcTreeBaseImpl< NODE, INTERFACE >::iterator |
◆ NodeType
| typedef NODE octomap::OcTreeBaseImpl< NODE, INTERFACE >::NodeType |
Make the templated NODE type available from the outside.
Constructor & Destructor Documentation
◆ OcTreeBaseImpl() [1/3]
| octomap::OcTreeBaseImpl< NODE, I >::OcTreeBaseImpl | ( | double | resolution | ) |
References init(), resolution, root, tree_depth, tree_max_val, and tree_size.
Referenced by octomap::OcTreeBaseImpl< NODE, INTERFACE >::iterator_base::iterator_base(), memoryUsage(), OcTreeBaseImpl(), octomap::OcTreeBaseImpl< NODE, INTERFACE >::iterator_base::operator=(), operator==(), and swapContent().
◆ ~OcTreeBaseImpl()
|
virtual |
References clear().
◆ OcTreeBaseImpl() [2/3]
| octomap::OcTreeBaseImpl< NODE, INTERFACE >::OcTreeBaseImpl | ( | const OcTreeBaseImpl< NODE, INTERFACE > & | rhs | ) |
Deep copy constructor.
References OcTreeBaseImpl().
◆ OcTreeBaseImpl() [3/3]
|
protected |
Constructor to enable derived classes to change tree constants. This usually requires a re-implementation of some core tree-traversal functions as well!
References init(), resolution, root, tree_depth, tree_max_val, and tree_size.
Member Function Documentation
◆ adjustKeyAtDepth() [1/2]
|
inline |
Adjusts a 3D key from the lowest level to correspond to a higher depth (by shifting the key values)
- Parameters
-
key Input key, at the lowest tree level depth Target depth level for the new key
- Returns
- Key for the new depth level
References tree_depth.
Referenced by coordToKeyChecked(), and search().
◆ adjustKeyAtDepth() [2/2]
| key_type octomap::OcTreeBaseImpl< NODE, I >::adjustKeyAtDepth | ( | key_type | key, |
| unsigned int | depth ) const |
Adjusts a single key value from the lowest level to correspond to a higher depth (by shifting the key value)
- Parameters
-
key Input key, at the lowest tree level depth Target depth level for the new key
- Returns
- Key for the new depth level
References tree_depth, and tree_max_val.
◆ allocNodeChildren()
|
protected |
Referenced by createNodeChild().
◆ begin()
|
inline |
- Returns
- beginning of the tree as leaf iterator
Referenced by calcMinMax(), computeRay(), getMetricMax(), and getMetricMin().
◆ begin_leafs()
|
inline |
- Returns
- beginning of the tree as leaf iterator
◆ begin_leafs_bbx() [1/2]
|
inline |
- Returns
- beginning of the tree as leaf iterator in a bounding box
◆ begin_leafs_bbx() [2/2]
|
inline |
- Returns
- beginning of the tree as leaf iterator in a bounding box
◆ begin_tree()
|
inline |
- Returns
- beginning of the tree as iterator to all nodes (incl. inner)
◆ calcMinMax()
|
protected |
recalculates min and max in x, y, z. Does nothing when tree size didn't change.
References begin(), end(), octomap::OcTreeBaseImpl< NODE, INTERFACE >::iterator_base::getSize(), octomap::OcTreeBaseImpl< NODE, INTERFACE >::iterator_base::getX(), octomap::OcTreeBaseImpl< NODE, INTERFACE >::iterator_base::getY(), octomap::OcTreeBaseImpl< NODE, INTERFACE >::iterator_base::getZ(), max_value, min_value, root, size(), and size_changed.
Referenced by getMetricMax(), and getMetricMin().
◆ calcNumNodes()
| size_t octomap::OcTreeBaseImpl< NODE, I >::calcNumNodes | ( | ) | const |
Traverses the tree to calculate the total number of nodes.
References calcNumNodesRecurs(), and root.
Referenced by main(), octomap::OccupancyOcTreeBase< NODE >::readBinaryData(), and readData().
◆ calcNumNodesRecurs()
|
protected |
References calcNumNodesRecurs(), getNodeChild(), nodeChildExists(), and nodeHasChildren().
Referenced by calcNumNodes(), and calcNumNodesRecurs().
◆ clear()
| void octomap::OcTreeBaseImpl< NODE, I >::clear | ( | ) |
◆ clearKeyRays()
|
inline |
Clear KeyRay vector to minimize unneeded memory.
This is only useful for the StaticMemberInitializer classes, don't call it for an octree that is actually used.
References keyrays.
Referenced by octomap::ColorOcTree::StaticMemberInitializer::StaticMemberInitializer(), and octomap::CountingOcTree::StaticMemberInitializer::StaticMemberInitializer().
◆ computeRay()
| bool octomap::OcTreeBaseImpl< NODE, I >::computeRay | ( | const point3d & | origin, |
| const point3d & | end, | ||
| std::vector< point3d > & | ray ) |
Traces a ray from origin to end (excluding), returning the coordinates of all nodes traversed by the beam.
You still need to check if a node at that coordinate exists (e.g. with search()).
- Note
- : use the faster computeRayKeys method if possible.
- Parameters
-
origin start coordinate of ray end end coordinate of ray ray KeyRay structure that holds the keys of all nodes traversed by the ray, excluding "end"
- Returns
- Success of operation. Returning false usually means that one of the coordinates is out of the OcTree's range
References begin(), computeRayKeys(), end(), keyrays, and keyToCoord().
◆ computeRayKeys()
| bool octomap::OcTreeBaseImpl< NODE, I >::computeRayKeys | ( | const point3d & | origin, |
| const point3d & | end, | ||
| KeyRay & | ray ) const |
Traces a ray from origin to end (excluding), returning an OcTreeKey of all nodes traversed by the beam.
You still need to check if a node at that coordinate exists (e.g. with search()).
- Parameters
-
origin start coordinate of ray end end coordinate of ray ray KeyRay structure that holds the keys of all nodes traversed by the ray, excluding "end"
- Returns
- Success of operation. Returning false usually means that one of the coordinates is out of the OcTree's range
References octomap::KeyRay::addKey(), coordToKeyChecked(), end(), keyToCoord(), octomath::Vector3::norm(), OCTOMAP_WARNING_STR, octomap::KeyRay::reset(), resolution, octomap::KeyRay::size(), and octomap::KeyRay::sizeMax().
Referenced by computeRay().
◆ coordToKey() [1/6]
|
inline |
Converts from a 3D coordinate into a 3D addressing key.
References coordToKey().
◆ coordToKey() [2/6]
|
inline |
Converts from a 3D coordinate into a 3D addressing key at a given depth.
References coordToKey(), and tree_depth.
◆ coordToKey() [3/6]
|
inline |
Converts from a single coordinate into a discrete key.
References resolution_factor, and tree_max_val.
Referenced by coordToKey(), coordToKey(), coordToKey(), coordToKey(), and getUnknownLeafCenters().
◆ coordToKey() [4/6]
|
inline |
Converts from a single coordinate into a discrete key at a given depth.
References resolution_factor, tree_depth, and tree_max_val.
◆ coordToKey() [5/6]
|
inline |
Converts from a 3D coordinate into a 3D addressing key.
References coordToKey().
◆ coordToKey() [6/6]
|
inline |
Converts from a 3D coordinate into a 3D addressing key at a given depth.
References coordToKey(), and tree_depth.
◆ coordToKeyChecked() [1/6]
| bool octomap::OcTreeBaseImpl< NODE, I >::coordToKeyChecked | ( | const point3d & | coord, |
| OcTreeKey & | key ) const |
Converts a 3D coordinate into a 3D OcTreeKey, with boundary checking.
- Parameters
-
coord 3d coordinate of a point key values that will be computed, an array of fixed size 3.
- Returns
- true if point is within the octree (valid), false otherwise
References coordToKeyChecked().
Referenced by octomap::OccupancyOcTreeBase< NODE >::castRay(), computeRayKeys(), coordToKeyChecked(), coordToKeyChecked(), coordToKeyChecked(), coordToKeyChecked(), deleteNode(), deleteNode(), octomap::OccupancyOcTreeBase< NODE >::getNormals(), search(), and search().
◆ coordToKeyChecked() [2/6]
| bool octomap::OcTreeBaseImpl< NODE, I >::coordToKeyChecked | ( | const point3d & | coord, |
| unsigned | depth, | ||
| OcTreeKey & | key ) const |
Converts a 3D coordinate into a 3D OcTreeKey at a certain depth, with boundary checking.
- Parameters
-
coord 3d coordinate of a point depth level of the key from the top key values that will be computed, an array of fixed size 3.
- Returns
- true if point is within the octree (valid), false otherwise
References coordToKeyChecked().
◆ coordToKeyChecked() [3/6]
| bool octomap::OcTreeBaseImpl< NODE, I >::coordToKeyChecked | ( | double | coordinate, |
| key_type & | key ) const |
Converts a single coordinate into a discrete addressing key, with boundary checking.
- Parameters
-
coordinate 3d coordinate of a point key discrete 16 bit adressing key, result
- Returns
- true if coordinate is within the octree bounds (valid), false otherwise
References resolution_factor, and tree_max_val.
◆ coordToKeyChecked() [4/6]
| bool octomap::OcTreeBaseImpl< NODE, I >::coordToKeyChecked | ( | double | coordinate, |
| unsigned | depth, | ||
| key_type & | key ) const |
Converts a single coordinate into a discrete addressing key, with boundary checking.
- Parameters
-
coordinate 3d coordinate of a point depth level of the key from the top key discrete 16 bit adressing key, result
- Returns
- true if coordinate is within the octree bounds (valid), false otherwise
References adjustKeyAtDepth(), resolution_factor, and tree_max_val.
◆ coordToKeyChecked() [5/6]
| bool octomap::OcTreeBaseImpl< NODE, I >::coordToKeyChecked | ( | double | x, |
| double | y, | ||
| double | z, | ||
| OcTreeKey & | key ) const |
Converts a 3D coordinate into a 3D OcTreeKey, with boundary checking.
- Parameters
-
x y z key values that will be computed, an array of fixed size 3.
- Returns
- true if point is within the octree (valid), false otherwise
References coordToKeyChecked().
◆ coordToKeyChecked() [6/6]
| bool octomap::OcTreeBaseImpl< NODE, I >::coordToKeyChecked | ( | double | x, |
| double | y, | ||
| double | z, | ||
| unsigned | depth, | ||
| OcTreeKey & | key ) const |
Converts a 3D coordinate into a 3D OcTreeKey at a certain depth, with boundary checking.
- Parameters
-
x y z depth level of the key from the top key values that will be computed, an array of fixed size 3.
- Returns
- true if point is within the octree (valid), false otherwise
References coordToKeyChecked().
◆ createNodeChild()
| NODE * octomap::OcTreeBaseImpl< NODE, I >::createNodeChild | ( | NODE * | node, |
| unsigned int | childIdx ) |
Creates (allocates) the i-th child of the node.
- Returns
- ptr to newly create NODE
References allocNodeChildren(), size_changed, and tree_size.
Referenced by readNodesRecurs().
◆ deleteNode() [1/3]
| bool octomap::OcTreeBaseImpl< NODE, I >::deleteNode | ( | const OcTreeKey & | key, |
| unsigned int | depth = 0 ) |
Delete a node (if exists) given an addressing key.
Will always delete at the lowest level unless depth !=0, and expand pruned inner nodes as needed. Pruned nodes at level "depth" will directly be deleted as a whole.
References root.
◆ deleteNode() [2/3]
| bool octomap::OcTreeBaseImpl< NODE, I >::deleteNode | ( | const point3d & | value, |
| unsigned int | depth = 0 ) |
Delete a node (if exists) given a 3d point.
Will always delete at the lowest level unless depth !=0, and expand pruned inner nodes as needed. Pruned nodes at level "depth" will directly be deleted as a whole.
References coordToKeyChecked(), and OCTOMAP_ERROR_STR.
◆ deleteNode() [3/3]
| bool octomap::OcTreeBaseImpl< NODE, I >::deleteNode | ( | double | x, |
| double | y, | ||
| double | z, | ||
| unsigned int | depth = 0 ) |
Delete a node (if exists) given a 3d point.
Will always delete at the lowest level unless depth !=0, and expand pruned inner nodes as needed. Pruned nodes at level "depth" will directly be deleted as a whole.
References coordToKeyChecked(), deleteNode(), and OCTOMAP_ERROR_STR.
Referenced by deleteNode().
◆ deleteNodeChild()
| void octomap::OcTreeBaseImpl< NODE, I >::deleteNodeChild | ( | NODE * | node, |
| unsigned int | childIdx ) |
Deletes the i-th child of the node.
References size_changed, and tree_size.
Referenced by deleteNodeRecurs(), and main().
◆ deleteNodeRecurs() [1/2]
|
protected |
Recursively delete a node and all children. Deallocates memory but does NOT set the node ptr to NULL nor updates tree size.
References deleteNodeRecurs().
Referenced by deleteNodeRecurs(), and deleteNodeRecurs().
◆ deleteNodeRecurs() [2/2]
|
protected |
recursive call of deleteNode()
References octomap::computeChildIdx(), deleteNodeChild(), deleteNodeRecurs(), expandNode(), getNodeChild(), nodeChildExists(), nodeHasChildren(), root, and tree_depth.
◆ end()
|
inline |
- Returns
- end of the tree as leaf iterator
References leaf_iterator_end.
Referenced by calcMinMax(), computeRay(), computeRayKeys(), getMetricMax(), getMetricMin(), octomap::OcTreeBaseImpl< NODE, INTERFACE >::leaf_iterator::operator++(), and octomap::OcTreeBaseImpl< NODE, INTERFACE >::leaf_iterator::operator++().
◆ end_leafs()
|
inline |
- Returns
- end of the tree as leaf iterator
References leaf_iterator_end.
◆ end_leafs_bbx()
|
inline |
- Returns
- end of the tree as leaf iterator in a bounding box
References leaf_iterator_bbx_end.
◆ end_tree()
|
inline |
- Returns
- end of the tree as iterator to all nodes (incl. inner)
References tree_iterator_end.
◆ expand()
|
virtual |
Expands all pruned nodes (reverse of prune())
- Note
- This is an expensive operation, especially when the tree is nearly empty!
References expandRecurs(), root, and tree_depth.
Referenced by main().
◆ expandNode()
|
virtual |
Expands a node (reverse of pruning): All children are created and their occupancy probability is set to the node's value.
You need to verify that this is indeed a pruned node (i.e. not a leaf at the lowest level)
References nodeHasChildren().
Referenced by deleteNodeRecurs(), expandRecurs(), and main().
◆ expandRecurs()
|
protected |
recursive call of expand()
References expandNode(), expandRecurs(), getNodeChild(), nodeChildExists(), and nodeHasChildren().
Referenced by expand(), and expandRecurs().
◆ getMetricMax() [1/2]
|
virtual |
maximum value of the bounding box of all known space in x, y, z
References calcMinMax(), and max_value.
Referenced by getMetricSize(), and getMetricSize().
◆ getMetricMax() [2/2]
| void octomap::OcTreeBaseImpl< NODE, I >::getMetricMax | ( | double & | x, |
| double & | y, | ||
| double & | z ) const |
maximum value of the bounding box of all known space in x, y, z
References begin(), end(), octomap::OcTreeBaseImpl< NODE, INTERFACE >::iterator_base::getSize(), octomap::OcTreeBaseImpl< NODE, INTERFACE >::iterator_base::getX(), octomap::OcTreeBaseImpl< NODE, INTERFACE >::iterator_base::getY(), octomap::OcTreeBaseImpl< NODE, INTERFACE >::iterator_base::getZ(), max_value, root, and size_changed.
◆ getMetricMin() [1/2]
|
virtual |
minimum value of the bounding box of all known space in x, y, z
References calcMinMax(), and min_value.
Referenced by getMetricSize(), and getMetricSize().
◆ getMetricMin() [2/2]
| void octomap::OcTreeBaseImpl< NODE, I >::getMetricMin | ( | double & | x, |
| double & | y, | ||
| double & | z ) const |
minimum value of the bounding box of all known space in x, y, z
References begin(), end(), octomap::OcTreeBaseImpl< NODE, INTERFACE >::iterator_base::getSize(), octomap::OcTreeBaseImpl< NODE, INTERFACE >::iterator_base::getX(), octomap::OcTreeBaseImpl< NODE, INTERFACE >::iterator_base::getY(), octomap::OcTreeBaseImpl< NODE, INTERFACE >::iterator_base::getZ(), min_value, root, and size_changed.
◆ getMetricSize() [1/2]
|
virtual |
Size of OcTree (all known space) in meters for x, y and z dimension.
References getMetricMax(), and getMetricMin().
Referenced by memoryFullGrid(), and volume().
◆ getMetricSize() [2/2]
|
virtual |
Size of OcTree (all known space) in meters for x, y and z dimension.
References getMetricMax(), and getMetricMin().
◆ getNodeChild() [1/2]
| const NODE * octomap::OcTreeBaseImpl< NODE, I >::getNodeChild | ( | const NODE * | node, |
| unsigned int | childIdx ) const |
- Returns
- const ptr to child number childIdx of node
◆ getNodeChild() [2/2]
| NODE * octomap::OcTreeBaseImpl< NODE, I >::getNodeChild | ( | NODE * | node, |
| unsigned int | childIdx ) const |
- Returns
- ptr to child number childIdx of node
Referenced by calcNumNodesRecurs(), deleteNodeRecurs(), expandRecurs(), getNumLeafNodesRecurs(), isNodeCollapsible(), pruneRecurs(), search(), and writeNodesRecurs().
◆ getNodeSize()
|
inline |
References sizeLookupTable, and tree_depth.
Referenced by keyToCoord().
◆ getNumLeafNodes()
| size_t octomap::OcTreeBaseImpl< NODE, I >::getNumLeafNodes | ( | ) | const |
Traverses the tree to calculate the total number of leaf nodes.
References getNumLeafNodesRecurs(), and root.
Referenced by memoryUsage().
◆ getNumLeafNodesRecurs()
|
protected |
References getNodeChild(), getNumLeafNodesRecurs(), nodeChildExists(), and nodeHasChildren().
Referenced by getNumLeafNodes(), and getNumLeafNodesRecurs().
◆ getResolution()
|
inline |
References resolution.
Referenced by main().
◆ getRoot()
|
inline |
◆ getTreeDepth()
|
inline |
References tree_depth.
Referenced by main().
◆ getTreeType()
|
inline |
Reimplemented in octomap::OcTreeStamped.
◆ getUnknownLeafCenters()
| void octomap::OcTreeBaseImpl< NODE, I >::getUnknownLeafCenters | ( | point3d_list & | node_centers, |
| point3d | pmin, | ||
| point3d | pmax, | ||
| unsigned int | depth = 0 ) const |
return centers of leafs that do NOT exist (but could) in a given bounding box
References coordToKey(), keyToCoord(), resolution, search(), tree_depth, octomath::Vector3::x(), octomath::Vector3::y(), and octomath::Vector3::z().
◆ init()
|
protected |
initialize non-trivial members, helper for constructors
References max_value, min_value, resolution, setResolution(), and size_changed.
Referenced by OcTreeBaseImpl(), and OcTreeBaseImpl().
◆ isNodeCollapsible()
|
virtual |
A node is collapsible if all children exist, don't have children of their own and have the same occupancy value.
References getNodeChild(), nodeChildExists(), and nodeHasChildren().
◆ keyToCoord() [1/4]
|
inline |
converts from an addressing key at the lowest tree level into a coordinate corresponding to the key's center
References keyToCoord().
◆ keyToCoord() [2/4]
|
inline |
converts from an addressing key at a given depth into a coordinate corresponding to the key's center
References keyToCoord().
◆ keyToCoord() [3/4]
|
inline |
converts from a discrete key at the lowest tree level into a coordinate corresponding to the key's center
References resolution, and tree_max_val.
◆ keyToCoord() [4/4]
| double octomap::OcTreeBaseImpl< NODE, I >::keyToCoord | ( | key_type | key, |
| unsigned | depth ) const |
converts from a discrete key at a given depth into a coordinate corresponding to the key's center
References getNodeSize(), keyToCoord(), and tree_depth.
Referenced by computeRay(), computeRayKeys(), getUnknownLeafCenters(), keyToCoord(), keyToCoord(), and keyToCoord().
◆ memoryFullGrid()
| unsigned long long octomap::OcTreeBaseImpl< NODE, I >::memoryFullGrid | ( | ) | const |
- Returns
- Memory usage of a full grid of the same size as the OcTree in bytes (for comparison)
- Note
- this can be larger than the adressable memory - size_t may not be enough to hold it!
References getMetricSize(), resolution, and root.
◆ memoryUsage()
|
virtual |
- Returns
- Memory usage of the complete octree in bytes (may vary between architectures)
References getNumLeafNodes(), memoryUsageNode(), OcTreeBaseImpl(), and tree_size.
◆ memoryUsageNode()
|
inlinevirtual |
- Returns
- Memory usage of a single octree node
Referenced by memoryUsage().
◆ nodeChildExists()
| bool octomap::OcTreeBaseImpl< NODE, I >::nodeChildExists | ( | const NODE * | node, |
| unsigned int | childIdx ) const |
Safe test if node has a child at index childIdx.
First tests if there are any children. Replaces node->childExists(...)
- Returns
- true if the child at childIdx exists
Referenced by calcNumNodesRecurs(), deleteNodeRecurs(), expandRecurs(), getNumLeafNodesRecurs(), isNodeCollapsible(), main(), pruneRecurs(), search(), and writeNodesRecurs().
◆ nodeHasChildren()
| bool octomap::OcTreeBaseImpl< NODE, I >::nodeHasChildren | ( | const NODE * | node | ) | const |
Safe test if node has any children.
Replaces node->hasChildren(...)
- Returns
- true if node has at least one child
Referenced by calcNumNodesRecurs(), deleteNodeRecurs(), expandNode(), expandRecurs(), getNumLeafNodesRecurs(), isNodeCollapsible(), main(), and search().
◆ operator==()
| bool octomap::OcTreeBaseImpl< NODE, I >::operator== | ( | const OcTreeBaseImpl< NODE, INTERFACE > & | rhs | ) | const |
Comparison between two octrees, all meta data, all nodes, and the structure must be identical.
References OcTreeBaseImpl(), tree_depth, and tree_max_val.
◆ prune()
|
virtual |
◆ pruneNode()
|
virtual |
Prunes a node when it is collapsible.
- Returns
- true if pruning was successful
Referenced by pruneRecurs().
◆ pruneRecurs()
|
protected |
recursive call of prune()
References getNodeChild(), nodeChildExists(), pruneNode(), and pruneRecurs().
Referenced by pruneRecurs().
◆ readData()
| std::istream & octomap::OcTreeBaseImpl< NODE, I >::readData | ( | std::istream & | s | ) |
Read all nodes from the input stream (without file header), for this the tree needs to be already created.
For general file IO, you should probably use AbstractOcTree::read() instead.
References calcNumNodes(), OCTOMAP_ERROR_STR, OCTOMAP_WARNING_STR, readNodesRecurs(), root, size_changed, and tree_size.
◆ readNodesRecurs()
|
protected |
recursive call of readData()
References createNodeChild(), and readNodesRecurs().
Referenced by readData(), and readNodesRecurs().
◆ search() [1/3]
| NODE * octomap::OcTreeBaseImpl< NODE, I >::search | ( | const OcTreeKey & | key, |
| unsigned int | depth = 0 ) const |
Search a node at specified depth given an addressing key (depth=0: search full tree depth) You need to check if the returned node is NULL, since it can be in unknown space.
- Returns
- pointer to node if found, NULL otherwise
References adjustKeyAtDepth(), octomap::computeChildIdx(), getNodeChild(), nodeChildExists(), nodeHasChildren(), root, and tree_depth.
◆ search() [2/3]
| NODE * octomap::OcTreeBaseImpl< NODE, I >::search | ( | const point3d & | value, |
| unsigned int | depth = 0 ) const |
Search node at specified depth given a 3d point (depth=0: search full tree depth) You need to check if the returned node is NULL, since it can be in unknown space.
- Returns
- pointer to node if found, NULL otherwise
References coordToKeyChecked(), OCTOMAP_ERROR_STR, and search().
◆ search() [3/3]
| NODE * octomap::OcTreeBaseImpl< NODE, I >::search | ( | double | x, |
| double | y, | ||
| double | z, | ||
| unsigned int | depth = 0 ) const |
Search node at specified depth given a 3d point (depth=0: search full tree depth).
You need to check if the returned node is NULL, since it can be in unknown space.
- Returns
- pointer to node if found, NULL otherwise
References coordToKeyChecked().
Referenced by getUnknownLeafCenters(), main(), main(), and search().
◆ setResolution()
| void octomap::OcTreeBaseImpl< NODE, I >::setResolution | ( | double | r | ) |
Change the resolution of the octree, scaling all voxels. This will not preserve the (metric) scale!
References resolution, resolution_factor, tree_center, and tree_max_val.
Referenced by init().
◆ size()
|
inlinevirtual |
- Returns
- The number of nodes in the tree
Referenced by calcMinMax(), main(), and main().
◆ swapContent()
| void octomap::OcTreeBaseImpl< NODE, I >::swapContent | ( | OcTreeBaseImpl< NODE, INTERFACE > & | rhs | ) |
Swap contents of two octrees, i.e., only the underlying pointer / tree structure.
You have to ensure yourself that the metadata (resolution etc) matches. No memory is cleared in this function
References OcTreeBaseImpl(), root, and tree_size.
◆ volume()
| double octomap::OcTreeBaseImpl< NODE, I >::volume | ( | ) |
References getMetricSize().
◆ writeData()
| std::ostream & octomap::OcTreeBaseImpl< NODE, I >::writeData | ( | std::ostream & | s | ) | const |
Write complete state of tree to stream (without file header) unmodified. Pruning the tree first produces smaller files (lossless compression)
References root, and writeNodesRecurs().
◆ writeNodesRecurs()
|
protected |
recursive call of writeData()
References getNodeChild(), nodeChildExists(), and writeNodesRecurs().
Referenced by writeData(), and writeNodesRecurs().
Field Documentation
◆ keyrays
|
protected |
data structure for ray casting, array for multithreading
Referenced by clearKeyRays(), and computeRay().
◆ leaf_iterator_bbx_end
|
protected |
Referenced by end_leafs_bbx().
◆ leaf_iterator_end
|
protected |
Referenced by end(), and end_leafs().
◆ max_value
|
protected |
max in x, y, z
Referenced by calcMinMax(), getMetricMax(), getMetricMax(), and init().
◆ min_value
|
protected |
min in x, y, z contains the size of a voxel at level i (0: root node). tree_depth+1 levels (incl. 0)
Referenced by calcMinMax(), getMetricMin(), getMetricMin(), and init().
◆ resolution
|
protected |
in meters
Referenced by computeRayKeys(), getResolution(), getUnknownLeafCenters(), init(), keyToCoord(), memoryFullGrid(), OcTreeBaseImpl(), OcTreeBaseImpl(), and setResolution().
◆ resolution_factor
|
protected |
= 1. / resolution
Referenced by coordToKey(), coordToKey(), coordToKeyChecked(), coordToKeyChecked(), and setResolution().
◆ root
|
protected |
Pointer to the root NODE, NULL for empty tree.
Referenced by calcMinMax(), calcNumNodes(), clear(), deleteNode(), deleteNodeRecurs(), expand(), getMetricMax(), getMetricMin(), getNumLeafNodes(), getRoot(), memoryFullGrid(), OcTreeBaseImpl(), OcTreeBaseImpl(), prune(), readData(), search(), swapContent(), and writeData().
◆ size_changed
|
protected |
Referenced by calcMinMax(), createNodeChild(), deleteNodeChild(), getMetricMax(), getMetricMin(), init(), and readData().
◆ sizeLookupTable
|
protected |
Referenced by getNodeSize().
◆ tree_center
|
protected |
Referenced by setResolution().
◆ tree_depth
|
protected |
Maximum tree depth is fixed to 16 currently.
Referenced by adjustKeyAtDepth(), adjustKeyAtDepth(), coordToKey(), coordToKey(), coordToKey(), deleteNodeRecurs(), expand(), getNodeSize(), getTreeDepth(), getUnknownLeafCenters(), keyToCoord(), OcTreeBaseImpl(), OcTreeBaseImpl(), octomap::OcTreeBaseImpl< NODE, INTERFACE >::leaf_bbx_iterator::operator++(), operator==(), and search().
◆ tree_iterator_end
|
protected |
Referenced by end_tree().
◆ tree_max_val
|
protected |
◆ tree_size
|
protected |
number of nodes in tree flag to denote whether the octree extent changed (for lazy min/max eval)
Referenced by createNodeChild(), deleteNodeChild(), octomap::OcTreeBaseImpl< NODE, INTERFACE >::tree_iterator::isLeaf(), memoryUsage(), OcTreeBaseImpl(), OcTreeBaseImpl(), readData(), and swapContent().
The documentation for this class was generated from the following files:
- include/octomap/OcTreeBaseImpl.h
- include/octomap/OcTreeBaseImpl.hxx
