KDTree Manual

Table of Contents

About

A k-d tree organizes a given set of points in three-dimensional space. It is used to search quickly for the point nearest to a given point.

KDTree

A maxon::KDTree is simply created with:

The tree is filled with:

The nearest point for a given point in space can be found with:

// This example creates and fills a k-d tree. The tree is then
// used to search the nearest points for the given sample points.
// create k-d tree for single-threaded use
tree.Init(1) iferr_return;
// insert points
for (maxon::Int i = 0; i < pointCnt; ++i)
{
tree.Insert(points[i], i) iferr_return;
}
// balance tree
tree.Balance();
// search for nearest points next to the sample points
nearestPoints.EnsureCapacity(samplePointCnt) iferr_return;
for (const maxon::Vector& samplePoint : samplePoints)
{
// find nearest point
const maxon::Int nearestIndex = tree.FindNearest(0, samplePoint, nullptr);
nearestPoints.Append(nearestIndex) iferr_return;
}

Further Reading

maxon::KDTree::Init
Result< void > Init(Int maxThreads)
maxon::KDTree
class to find closest points in space for a given point cloud
Definition: kdtree.h:98
iferr_return
#define iferr_return
Definition: resultbase.h:1434
maxon::BaseArray
Definition: basearray.h:366
maxon::KDTree::Balance
void Balance()
balance the kd-tree. This needs to be done once after all nodes have been inserted calling 'Insert'
maxon::BaseArray::Append
MAXON_ATTRIBUTE_FORCE_INLINE ResultRef< T > Append()
Definition: basearray.h:569
maxon::Vec3< Float, 1 >
maxon::Int
Int64 Int
signed 32/64 bit int, size depends on the platform
Definition: apibase.h:184
maxon::KDTree::Insert
Result< void > Insert(const Vector &point, Int idValue)
maxon::BaseArray::EnsureCapacity
ResultMem EnsureCapacity(Int requestedCapacity, COLLECTION_RESIZE_FLAGS resizeFlags=COLLECTION_RESIZE_FLAGS::ON_GROW_RESERVE_CAPACITY)
Definition: basearray.h:1188
maxon::KDTree::FindNearest
Int FindNearest(Int threadIndex, const Vector &point, KDTreeNearest *nearest)