Super4PCS Library  V1.1.2(719f5c0)
Classes | Public Types | Public Member Functions | Static Public Member Functions | List of all members
GlobalRegistration::KdTree< _Scalar, _Index > Class Template Reference
+ Inheritance diagram for GlobalRegistration::KdTree< _Scalar, _Index >:
+ Collaboration diagram for GlobalRegistration::KdTree< _Scalar, _Index >:

Classes

struct  KdNode
 
struct  QueryNode
 element of the stack More...
 
struct  RangeQuery
 

Public Types

typedef _Scalar Scalar
 
typedef _Index Index
 
typedef Eigen::Matrix< Scalar, 3, 1 > VectorType
 
typedef AABB3D< Scalar > AxisAlignedBoxType
 
typedef std::vector< KdNode > NodeList
 
typedef std::vector< VectorType > PointList
 
typedef std::vector< Index > IndexList
 

Public Member Functions

const NodeList & _getNodes (void)
 
const PointList & _getPoints (void)
 
const PointList & _getIndices (void)
 
 KdTree (const PointList &points, unsigned int nofPointsPerCell=KD_POINT_PER_CELL, unsigned int maxDepth=KD_MAX_DEPTH)
 Create the Kd-Tree using memory copy. More...
 
 KdTree (unsigned int size=0, unsigned int nofPointsPerCell=KD_POINT_PER_CELL, unsigned int maxDepth=KD_MAX_DEPTH)
 Create a void KdTree. More...
 
template<class VectorDerived >
void add (const VectorDerived &p)
 Add a new vertex in the KdTree. More...
 
void add (Scalar *position)
 
void finalize ()
 Finalize the creation of the KdTree. More...
 
const AxisAlignedBoxType & aabb () const
 
 ~KdTree ()
 
template<int stackSize, typename Container = std::vector<VectorType>>
void doQueryDist (RangeQuery< stackSize > &query, Container &result) const
 Performs distance query and return vector coordinates. More...
 
template<int stackSize, typename IndexContainer = std::vector<Index>>
void doQueryDistIndices (RangeQuery< stackSize > &query, IndexContainer &result) const
 Performs distance query and return indices. More...
 
template<int stackSize, typename Functor >
void doQueryDistProcessIndices (RangeQuery< stackSize > &query, Functor f) const
 Performs distance query and return indices. More...
 
template<int stackSize>
Index doQueryRestrictedClosestIndex (RangeQuery< stackSize > &query, int currentId=-1) const
 Finds the closest element index within the range [0:sqrt(sqdist)]. More...
 

Static Public Member Functions

static constexpr Index invalidIndex ()
 

Detailed Description

template<typename _Scalar, typename _Index = int>
class GlobalRegistration::KdTree< _Scalar, _Index >

Generation

You can create the KdTree in two way :

  • Simple pass construction : easy to use, but use a full vertices memory copy :
    basic::TArray < KdTree<float>::VectorType > data(60);
    int i = 0;
    for ( ; i != 30; i++ ) {
    data << vec3 (rand() % 10 + 1,
    rand() % 10 + 1,
    rand() % 10 + 1); // vertex to add
    }
    data << vec3(0.5,0.5,0.5); // we must find this vertex
    i++;
    for ( ; i != 60; i++ ) {
    data << vec3 (rand() % 10 + 1,
    rand() % 10 + 1,
    rand() % 10 + 1); // vertex to add
    }
    KdTree<float> t ( data ); // Memory copy
    • Per-vertex pass construction : more code, but avoid copy :
      KdTree<float> t ( 60 );
      int i = 0;
      for ( ; i != 30; i++ ) {
      vec3 v( rand() % 10 + 1,
      rand() % 10 + 1,
      rand() % 10 + 1); // vertex to add
      t.set( i ,v );
      }
      t.set(i, vec3(0.5,0.5,0.5)); // we must find this vertex
      i++;
      for ( ; i != 60; i++ ) {
      vec3 v( rand() % 10 + 1,
      rand() % 10 + 1,
      rand() % 10 + 1); // vertex to add
      t.set( i ,v );
      }
      t.finalize(); // the real creation of the KdTree
      This version is very usefull if data are computed on the fly.

Closest-Point query

It is important to note that in the case of multiple neighbors request, the result isn't sorted (see HeapMaxPriorityQueue for more explanations). So if you want to get the closest point, you must perform a single request.

You must specify the size of the request using setMaxNofNeighbors.

t.setMaxNofNeighbors(1);
vec3 result = t.getNeighbor( 0 ).p;
unsigned int resultId = t.getNeighborId( 0 );
cout << resultId << endl;
cout << result(0) << " " << result(1) << " " << result(2) << endl;
cout << t.getNeighborSquaredDistance( 0 ) << endl;

Member Typedef Documentation

◆ AxisAlignedBoxType

template<typename _Scalar, typename _Index = int>
typedef AABB3D<Scalar> GlobalRegistration::KdTree< _Scalar, _Index >::AxisAlignedBoxType

◆ Index

template<typename _Scalar, typename _Index = int>
typedef _Index GlobalRegistration::KdTree< _Scalar, _Index >::Index

◆ IndexList

template<typename _Scalar, typename _Index = int>
typedef std::vector<Index> GlobalRegistration::KdTree< _Scalar, _Index >::IndexList

◆ NodeList

template<typename _Scalar, typename _Index = int>
typedef std::vector<KdNode> GlobalRegistration::KdTree< _Scalar, _Index >::NodeList

◆ PointList

template<typename _Scalar, typename _Index = int>
typedef std::vector<VectorType> GlobalRegistration::KdTree< _Scalar, _Index >::PointList

◆ Scalar

template<typename _Scalar, typename _Index = int>
typedef _Scalar GlobalRegistration::KdTree< _Scalar, _Index >::Scalar

◆ VectorType

template<typename _Scalar, typename _Index = int>
typedef Eigen::Matrix<Scalar,3,1> GlobalRegistration::KdTree< _Scalar, _Index >::VectorType

Constructor & Destructor Documentation

◆ KdTree() [1/2]

template<typename Scalar , typename Index >
GlobalRegistration::KdTree< Scalar, Index >::KdTree ( const PointList &  points,
unsigned int  nofPointsPerCell = KD_POINT_PER_CELL,
unsigned int  maxDepth = KD_MAX_DEPTH 
)

Create the Kd-Tree using memory copy.

See also
KdTree(unsigned int size, unsigned int nofPointsPerCell, unsigned int maxDepth)

◆ KdTree() [2/2]

template<typename Scalar , typename Index >
GlobalRegistration::KdTree< Scalar, Index >::KdTree ( unsigned int  size = 0,
unsigned int  nofPointsPerCell = KD_POINT_PER_CELL,
unsigned int  maxDepth = KD_MAX_DEPTH 
)

Create a void KdTree.

Second way to create the KdTree, in two time.

You must call finalize() before requesting for closest points.

See also
finalize()

◆ ~KdTree()

template<typename Scalar , typename Index >
GlobalRegistration::KdTree< Scalar, Index >::~KdTree ( )

Member Function Documentation

◆ _getIndices()

template<typename _Scalar, typename _Index = int>
const PointList& GlobalRegistration::KdTree< _Scalar, _Index >::_getIndices ( void  )
inline

◆ _getNodes()

template<typename _Scalar, typename _Index = int>
const NodeList& GlobalRegistration::KdTree< _Scalar, _Index >::_getNodes ( void  )
inline

◆ _getPoints()

template<typename _Scalar, typename _Index = int>
const PointList& GlobalRegistration::KdTree< _Scalar, _Index >::_getPoints ( void  )
inline

◆ aabb()

template<typename _Scalar, typename _Index = int>
const AxisAlignedBoxType& GlobalRegistration::KdTree< _Scalar, _Index >::aabb ( ) const
inline

◆ add() [1/2]

template<typename _Scalar, typename _Index = int>
template<class VectorDerived >
void GlobalRegistration::KdTree< _Scalar, _Index >::add ( const VectorDerived &  p)
inline

Add a new vertex in the KdTree.

◆ add() [2/2]

template<typename _Scalar, typename _Index = int>
void GlobalRegistration::KdTree< _Scalar, _Index >::add ( Scalar *  position)
inline

◆ doQueryDist()

template<typename _Scalar, typename _Index = int>
template<int stackSize, typename Container = std::vector<VectorType>>
void GlobalRegistration::KdTree< _Scalar, _Index >::doQueryDist ( RangeQuery< stackSize > &  query,
Container &  result 
) const
inline

Performs distance query and return vector coordinates.

◆ doQueryDistIndices()

template<typename _Scalar, typename _Index = int>
template<int stackSize, typename IndexContainer = std::vector<Index>>
void GlobalRegistration::KdTree< _Scalar, _Index >::doQueryDistIndices ( RangeQuery< stackSize > &  query,
IndexContainer &  result 
) const
inline

Performs distance query and return indices.

◆ doQueryDistProcessIndices()

template<typename _Scalar, typename _Index = int>
template<int stackSize, typename Functor >
void GlobalRegistration::KdTree< _Scalar, _Index >::doQueryDistProcessIndices ( RangeQuery< stackSize > &  query,
Functor  f 
) const
inline

Performs distance query and return indices.

◆ doQueryRestrictedClosestIndex()

template<typename Scalar , typename Index >
template<int stackSize>
Index GlobalRegistration::KdTree< Scalar, Index >::doQueryRestrictedClosestIndex ( RangeQuery< stackSize > &  query,
int  currentId = -1 
) const
inline

Finds the closest element index within the range [0:sqrt(sqdist)].

This algorithm uses the simple distance to the split plane to prune nodes.

Parameters
currentIdIndex of the querypoint if it belongs to the tree

A more elaborated approach consists to track the closest corner of the cell relatively to the current query point. This strategy allows to save about 5% of the leaves. However, in practice the slight overhead due to this tracking reduces the overall performance.

This algorithm also use a simple stack while a priority queue using the squared distances to the cells as a priority values allows to save about 10% of the leaves. But, again, priority queue insertions and deletions are quite involved, and therefore a simple stack is by far much faster.

The optionnal parameter currentId is used when the query point is stored in the tree, and must thus be avoided during the query

◆ finalize()

template<typename Scalar , typename Index >
void GlobalRegistration::KdTree< Scalar, Index >::finalize ( )
inline

Finalize the creation of the KdTree.

◆ invalidIndex()

template<typename _Scalar, typename _Index = int>
static constexpr Index GlobalRegistration::KdTree< _Scalar, _Index >::invalidIndex ( )
inlinestatic