 |
Image Component Library (ICL)
|
|
Image Component Library (ICL)
|
Generic Octree Implementation. More...
#include <Octree.h>
Classes | |
| struct | AABB |
| internally used axis-aligned bounding box More... | |
| struct | Allocator |
| Inernally used block allocator. More... | |
| struct | Node |
| Internally used node structure. More... | |
Public Member Functions | |
| Octree (const Scalar &minX, const Scalar &minY, const Scalar &minZ, const Scalar &width, const Scalar &height, const Scalar &depth) | |
| creates a QuadTree for the given 2D rectangle | |
| Octree (const Scalar &min, const Scalar &len) | |
| creates a QuadTree for the given 2D rectangle | |
| ~Octree () | |
| destructor | |
| const AABB & | getRootAABB () const |
| returs the Octree's top-level bounding box | |
| Pt | nn_approx (const Pt &p) const throw (utils::ICLException) |
| returns an approximated nearst neighbour | |
| Pt | nn (const Pt &pIn) const throw (utils::ICLException) |
| finds the nearest neighbor to the given node | |
| template<class OtherVectorType > | |
| void | insert (const OtherVectorType &pIn) |
| inserts a node into the QuadTree | |
| std::vector< Pt > | query (const Scalar &minX, const Scalar &minY, const Scalar &minZ, const Scalar &width, const Scalar &height, const Scalar &depth) const |
| returns all contained points within the given rectangle | |
| std::vector< Pt > | queryAll () const |
| returns all contained points | |
| void | clear () |
| removes all contained points and nodes | |
| int | size () const |
| number of elments inserted | |
Protected Member Functions | |
| const Pt & | nn_approx_internal (const Pt &p, double &currMinDist, const Pt *&currNN) const throw (utils::ICLException) |
| internal utility method that is used to find an approximated nearest neighbour | |
Static Protected Member Functions | |
| static Pt | scale_up (const Pt &p) |
| static Pt | scale_down (const Pt &p) |
| static Pt | scale_down_1 (const Pt &p) |
Protected Attributes | |
| Node * | root |
| root node pointer | |
| Allocator | alloc |
| memory allocator for all children except for the root node | |
| int | num |
| internal counter for the number of contained points | |
Generic Octree Implementation.
The Octree implementation is a simple 3D-generalization of the QuadTree class template.
Even though, we do not have any reliable results, it might be possible, that the octree is much faster then the pcl-octree!
| icl::math::Octree< Scalar, CAPACITY, SF, Pt, ALLOC_CHUNK_SIZE >::Octree | ( | const Scalar & | minX, |
| const Scalar & | minY, | ||
| const Scalar & | minZ, | ||
| const Scalar & | width, | ||
| const Scalar & | height, | ||
| const Scalar & | depth | ||
| ) | [inline] |
creates a QuadTree for the given 2D rectangle
| icl::math::Octree< Scalar, CAPACITY, SF, Pt, ALLOC_CHUNK_SIZE >::Octree | ( | const Scalar & | min, |
| const Scalar & | len | ||
| ) | [inline] |
creates a QuadTree for the given 2D rectangle
| icl::math::Octree< Scalar, CAPACITY, SF, Pt, ALLOC_CHUNK_SIZE >::~Octree | ( | ) | [inline] |
destructor
Deletes the root node only, all other nodes are deleted by the allocator
| void icl::math::Octree< Scalar, CAPACITY, SF, Pt, ALLOC_CHUNK_SIZE >::clear | ( | ) | [inline] |
removes all contained points and nodes
The allocator will free all memory except for the first CHUNK
| const AABB& icl::math::Octree< Scalar, CAPACITY, SF, Pt, ALLOC_CHUNK_SIZE >::getRootAABB | ( | ) | const [inline] |
returs the Octree's top-level bounding box
| void icl::math::Octree< Scalar, CAPACITY, SF, Pt, ALLOC_CHUNK_SIZE >::insert | ( | const OtherVectorType & | pIn | ) | [inline] |
inserts a node into the QuadTree
This method is also implemented in an iterative fashion for performance issues. 'insert' automatically uses the internal allocator if new nodes are needed.
| Pt icl::math::Octree< Scalar, CAPACITY, SF, Pt, ALLOC_CHUNK_SIZE >::nn | ( | const Pt & | pIn | ) | const throw (utils::ICLException) [inline] |
finds the nearest neighbor to the given node
The implementation of this method explicitly avoids recursion by using a run-time stack. This leads to a 4x speed factor in comparison to the recursive implementaiton of this function.
As an extra accelleration, the method initializes it's frist nearest neighbor guess using the nn_approx method, which gives an approximate speed up of factor two to four.
As a 2nd accelleration heuristic, all CAPACITY nodes' distances are are first calculated and compared in a squared version, which can be computed without an expensive square-root operation. However, once the closest point within a single node is found, its real euclidian minimum distance is computed and stored for further bounding box checks.
If no neighbour could be found, an exception is thown. This should actually only happen when nn is called on an empty QuadTree
| Pt icl::math::Octree< Scalar, CAPACITY, SF, Pt, ALLOC_CHUNK_SIZE >::nn_approx | ( | const Pt & | p | ) | const throw (utils::ICLException) [inline] |
returns an approximated nearst neighbour
While the real nearst neighbour must not neccessarily be in the cell that would theoretically contain p, The approximated one is always assumed to be in that bottom layer cell. If, by chance, the optimal leaf node does not contain any points (because it was just created as empty leaf), the leaf's parent node, which must actually contain CAPACITY points, is used instead. The approximate nearest neighbour search can easily be 5 times as fast as the real nearest neighbor search. The result quality depends on the number of contained points, and on the QuadTree's template parameters
| const Pt& icl::math::Octree< Scalar, CAPACITY, SF, Pt, ALLOC_CHUNK_SIZE >::nn_approx_internal | ( | const Pt & | p, |
| double & | currMinDist, | ||
| const Pt *& | currNN | ||
| ) | const throw (utils::ICLException) [inline, protected] |
internal utility method that is used to find an approximated nearest neighbour
| std::vector<Pt> icl::math::Octree< Scalar, CAPACITY, SF, Pt, ALLOC_CHUNK_SIZE >::query | ( | const Scalar & | minX, |
| const Scalar & | minY, | ||
| const Scalar & | minZ, | ||
| const Scalar & | width, | ||
| const Scalar & | height, | ||
| const Scalar & | depth | ||
| ) | const [inline] |
returns all contained points within the given rectangle
| std::vector<Pt> icl::math::Octree< Scalar, CAPACITY, SF, Pt, ALLOC_CHUNK_SIZE >::queryAll | ( | ) | const [inline] |
returns all contained points
| static Pt icl::math::Octree< Scalar, CAPACITY, SF, Pt, ALLOC_CHUNK_SIZE >::scale_down | ( | const Pt & | p | ) | [inline, static, protected] |
| static Pt icl::math::Octree< Scalar, CAPACITY, SF, Pt, ALLOC_CHUNK_SIZE >::scale_down_1 | ( | const Pt & | p | ) | [inline, static, protected] |
| static Pt icl::math::Octree< Scalar, CAPACITY, SF, Pt, ALLOC_CHUNK_SIZE >::scale_up | ( | const Pt & | p | ) | [inline, static, protected] |
| int icl::math::Octree< Scalar, CAPACITY, SF, Pt, ALLOC_CHUNK_SIZE >::size | ( | ) | const [inline] |
number of elments inserted
Allocator icl::math::Octree< Scalar, CAPACITY, SF, Pt, ALLOC_CHUNK_SIZE >::alloc [protected] |
memory allocator for all children except for the root node
int icl::math::Octree< Scalar, CAPACITY, SF, Pt, ALLOC_CHUNK_SIZE >::num [protected] |
internal counter for the number of contained points
Node* icl::math::Octree< Scalar, CAPACITY, SF, Pt, ALLOC_CHUNK_SIZE >::root [protected] |
root node pointer
1.7.6.1
