|
|
| KDTree (const std::vector< PointType > &points, uint pointsPerCell=16, uint maxDepth=64, bool balanced=false) |
| |
template<MeshConcept MeshType>
requires (std::is_same_v< typename MeshType::VertexType::CoordType, PointType>) |
| | KDTree (const MeshType &m, uint pointsPerCell=16, uint maxDepth=64, bool balanced=false) |
| | Builds the KDTree starting from the given mesh.
|
| |
| uint | nearestNeighborIndex (const PointType &queryPoint, Scalar &dist=dummyScalar) const |
| | Searchs the closest point.
|
| |
|
PointType | nearestNeighbor (const PointType &queryPoint, Scalar &dist=dummyScalar) const |
| |
| std::vector< uint > | kNearestNeighborsIndices (const PointType &queryPoint, uint k, std::vector< Scalar > &distances=dummyScalars) const |
| | Performs the k nearest neighbour query.
|
| |
|
std::vector< PointType > | kNearestNeighbors (const PointType &queryPoint, uint k, std::vector< Scalar > &distances=dummyScalars) const |
| |
| std::vector< uint > | neighborsIndicesInDistance (const PointType &queryPoint, Scalar dist, std::vector< Scalar > &distances=dummyScalars) const |
| | Performs the distance query.
|
| |
|
std::vector< PointType > | neighborsInDistance (const PointType &queryPoint, Scalar dist, std::vector< Scalar > &distances=dummyScalars) const |
| |
|
|
using | Scalar = PointType::ScalarType |
| |
|
| uint | createTree (uint nodeId, uint start, uint end, uint level, bool balanced) |
| | Rrecursively builds the kdtree.
|
| |
|
uint | split (uint start, uint end, uint dim, Scalar splitValue) |
| | Split the subarray between start and end in two part, one with the elements less than splitValue, the other with the elements greater or equal than splitValue. The elements are compared using the "dim" coordinate [0 = x, 1 = y, 2 = z].
|
| |
|
|
std::vector< PointType > | mPoints |
| |
|
std::vector< uint > | mIndices |
| |
|
std::vector< Node > | mNodes |
| |
|
uint | mPointsPerCell = 16 |
| |
|
uint | mMaxDepth = 64 |
| |
|
uint | mDepth = 0 |
| |
|
|
static Scalar | dummyScalar |
| |
|
static std::vector< Scalar > | dummyScalars |
| |
◆ KDTree()
template<PointConcept PointType>
template<MeshConcept MeshType>
requires (std::is_same_v<
typename MeshType::VertexType::CoordType, PointType>)
Builds the KDTree starting from the given mesh.
Requirements:
- Parameters
-
| m | |
| pointsPerCell | |
| maxDepth | |
| balanced | |
◆ createTree()
template<PointConcept PointType>
| uint vcl::KDTree< PointType >::createTree |
( |
uint |
nodeId, |
|
|
uint |
start, |
|
|
uint |
end, |
|
|
uint |
level, |
|
|
bool |
balanced |
|
) |
| |
|
inlineprivate |
Rrecursively builds the kdtree.
The heuristic is the following:
- if the number of points in the node is lower than targetCellsize then make a leaf
- else compute the AABB of the points of the node and split it at the middle of the largest AABB dimension.
This strategy might look not optimal because it does not explicitly prune empty space, unlike more advanced SAH-like techniques used for RT. On the other hand it leads to a shorter tree, faster to traverse and our experience shown that in the special case of kNN queries, this strategy is indeed more efficient (and much faster to build). Moreover, for volume data (e.g., fluid simulation) pruning the empty space is useless.
Actually, storing at each node the exact AABB (we therefore have a binary BVH) allows to prune only about 10% of the leaves, but the overhead of this pruning (ball/ABBB intersection) is more expensive than the gain it provides and the memory consumption is x4 higher!
◆ kNearestNeighborsIndices()
template<PointConcept PointType>
| std::vector< uint > vcl::KDTree< PointType >::kNearestNeighborsIndices |
( |
const PointType & |
queryPoint, |
|
|
uint |
k, |
|
|
std::vector< Scalar > & |
distances = dummyScalars |
|
) |
| const |
|
inline |
Performs the k nearest neighbour query.
This algorithm uses the simple distance to the split plane to prune nodes. 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 result of the query, the k-nearest neighbors, are stored into a vector, and they are sorted on order of neighbohood.
◆ nearestNeighborIndex()
template<PointConcept PointType>
| uint vcl::KDTree< PointType >::nearestNeighborIndex |
( |
const PointType & |
queryPoint, |
|
|
Scalar & |
dist = dummyScalar |
|
) |
| const |
|
inline |
Searchs the closest point.
The result of the query, the closest point to the query point, is the index of the point and and the distance from the query point.
◆ neighborsIndicesInDistance()
template<PointConcept PointType>
| std::vector< uint > vcl::KDTree< PointType >::neighborsIndicesInDistance |
( |
const PointType & |
queryPoint, |
|
|
Scalar |
dist, |
|
|
std::vector< Scalar > & |
distances = dummyScalars |
|
) |
| const |
|
inline |
Performs the distance query.
The result of the query, all the points within the distance dist form the query point, is the vector of the indeces and the vector of the distances from the query point.
The documentation for this class was generated from the following file:
- vclib/core/include/vclib/space/complex/kd_tree.h
1.9.8