K-d Trees Module

This module implements data-structures and functions to store, build and manipulate K-d trees.

• Kd_node
• cugar::cuda::Kd_builder

as well as a submodule for K-NN lookups: k-Nearest Neighbors.

As an example, consider the following code to create a K-d tree on a set of points, in parallel, on the device:

#include <cugar/kd/cuda/kd_builder.h>
#include <cugar/kd/cuda/kd_context.h>

cugar::vector<device_tag,Vector3f> kd_points;
... // code to fill the input vector of points

cugar::vector<device_tag,Kd_node>  kd_nodes;
cugar::vector<device_tag,uint2>    kd_leaves;
cugar::vector<device_tag,uint32>   kd_index;
cugar::vector<device_tag,uint2>    kd_ranges;

cugar::cuda::Kd_builder<uint64> builder( kd_index );
cugar::cuda::Kd_context kd_tree( &kd_nodes, &kd_leaves, &kd_ranges );
builder.build(
    kd_tree,                                    // output tree
    kd_index,                                   // output index
    Bbox3f( Vector3f(0.0f), Vector3f(1.0f) ),   // suppose all bboxes are in [0,1]^3
    kd_points.begin(),                          // begin iterator
    kd_points.end(),                            // end iterator
    4 );                                        // target 4 objects per leaf

The following k-NN example shows how to perform k-NN lookups on such a tree:

#include <cugar/kd/cuda/kd_knn.h>

cugar::vector<device_tag,Vector4f> query_points;
... // code to build the k-d tree and query points here...
    // NOTE: even though we're doing 3-dimensional queries,
    // we can use Vector4f arrays for better coalescing

cugar::vector<device_tag,cuda::Kd_knn<3>::Result> results( query_points.size() );

cugar::cuda::Kd_knn<3> knn;
knn.run(
    query_points.begin(),
    query_points.end(),
    raw_pointer(kd_nodes),
    raw_pointer(kd_ranges),
    raw_pointer(kd_leaves),
    raw_pointer(kd_points),
    raw_pointer(results) );