Radix Trees Module

This module provides functions to build radix trees on top of sorted integer sequences. In practice, if the integers are seen as Morton codes of spatial points, the algorithms generate a middle-split k-d tree.

The following code snippet shows an example of how to use such builders:

#include <cugar/bintree/cuda/bintree_gen.h>
#include <cugar/bintree/cuda/bintree_context.h>
#include <cugar/bits/morton.h>

typedef Bintree_node<leaf_index_tag> node_type;

const uint32 n_points = 1000000;
cugar::vector<device_tag,Vecto3f> points( n_points );
... // generate a bunch of points here

// compute their Morton codes
cugar::vector<device_tag,uint32> codes( n_points );
thrust::transform(
    points.begin(),
    points.begin() + n_points,
    codes.begin(),
    morton_functor<uint32,3>() );

// sort them
thrust::sort( codes.begin(), codes.end() );

// allocate storage for a binary tree...
cugar::vector<device_tag,node_type> nodes;
cugar::vector<device_tag,uint2>     leaves;

// build a tree writer
Bintree_writer<node_type, device_tag> tree_writer( nodes, leaves );

// ...and generate it!
cuda::generate_radix_tree(
    n_points,
    thrust::raw_pointer_cast( &codes.front() ),
    30u,
    16u,
    false,
    true,
    tree_writer );