Radix Trees

Detailed Description

This module defines functions to generate binary Radix Trees on top of sorted integer sequences

Classes
struct	cugar::cuda::Radixtree_context

Functions
template<typename Tree_writer , typename Integer >
void	cugar::cuda::generate_radix_tree (const uint32 n_codes, const Integer *codes, const uint32 bits, const uint32 max_leaf_size, const bool keep_singletons, const bool middle_splits, Tree_writer &tree)
template<typename Tree_writer , typename Integer >
void	cugar::cuda::generate_radix_tree (Radixtree_context &context, const uint32 n_codes, const Integer *codes, const uint32 bits, const uint32 max_leaf_size, const bool keep_singletons, const bool middle_splits, Tree_writer &tree)
template<typename Tree_writer , typename Integer >
void	cugar::generate_radix_tree (const uint32 n_codes, const Integer *codes, const uint32 bits, const uint32 max_leaf_size, const bool keep_singletons, const bool middle_splits, Tree_writer &tree)

Function Documentation

generate_radix_tree() [1/3]

template<typename Tree_writer , typename Integer >

void cugar::generate_radix_tree	(	const uint32	n_codes,
		const Integer *	codes,
		const uint32	bits,
		const uint32	max_leaf_size,
		const bool	keep_singletons,
		const bool	middle_splits,
		Tree_writer &	tree
	)

Generate a binary radix tree from a set of sorted integers, splitting the set top-down at each occurrence of a bit set to 1. In practice, if the integers are seen as Morton codes, this algorithm generates a middle-split k-d tree.

Parameters

n_codes	number of entries in the input set of codes
codes	input set of codes
bits	number of bits per code
max_leaf_size	maximum target number of entries per leaf
keep_singletons	mark whether to keep or suppress singleton nodes in the output tree
middle_splits	mark whether to allow pure middle splits once a group of integers are all equal. NOTE that if this flag is set to false, the maximum leaf size cannot be guaranteed
tree	output tree

Generate a binary radix tree from a set of sorted integers, splitting the set top-down at each occurrence of a bit set to 1. In practice, if the integers are seen as Morton codes, this algorithm generates a middle-split k-d tree.

Parameters

context	the generation context
n_codes	number of entries in the input set of codes
codes	input set of codes
bits	number of bits per code
max_leaf_size	maximum target number of entries per leaf
keep_singletons	mark whether to keep or suppress singleton nodes in the output tree
tree	output tree

The Tree_writer template parameter has to provide the following interface:

struct Tree_writer
{
   void reserve_nodes(const uint32 n);  // reserve space for n nodes
   void reserve_leaves(const uint32 n); // reserve space for n leaves

   context_type get_context();          // get a context to write nodes/leaves

   struct context_type
   {
       void write_node(
          const uint32 node,          // node to write
          const uint32 parent,        // node parent
          const bool   left_child,    // specify whether the node has a left child
          const bool   right_child,   // specify whether the node has a right child
          const uint32 offset,        // child offset
          const uint32 skip_node,     // skip node
          const uint32 level,         // split level
          const uint32 begin,         // node range begin
          const uint32 end,           // node range end
          const uint32 split_index);  // split index

       void write_leaf(
          const uint32 leaf_index,    // leaf to write
          const uint32 node_index,    // node containing this leaf
          const uint32 begin,         // leaf range begin
          const uint32 end);          // leaf range end
   };
};

The following code snippet shows how to use this builder:

#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;

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,
    tree_writer );

generate_radix_tree() [2/3]

template<typename Tree_writer , typename Integer >

void cugar::cuda::generate_radix_tree	(	const uint32	n_codes,
		const Integer *	codes,
		const uint32	bits,
		const uint32	max_leaf_size,
		const bool	keep_singletons,
		const bool	middle_splits,
		Tree_writer &	tree
	)

Generate a binary radix tree from a set of sorted integers, splitting the set top-down at each occurrence of a bit set to 1. In practice, if the integers are seen as Morton codes, this algorithm generates a middle-split k-d tree.

Parameters

context	the generation context
n_codes	number of entries in the input set of codes
codes	input set of codes
bits	number of bits per code
max_leaf_size	maximum target number of entries per leaf
keep_singletons	mark whether to keep or suppress singleton nodes in the output tree
tree	output tree

The Tree_writer template parameter has to provide the following interface:

struct Tree_writer
{
   void reserve_nodes(const uint32 n);  // reserve space for n nodes
   void reserve_leaves(const uint32 n); // reserve space for n leaves

   context_type get_context();          // get a context to write nodes/leaves

   struct context_type
   {
       void write_node(
          const uint32 node,          // node to write
          const uint32 parent,        // node parent
          const bool   left_child,    // specify whether the node has a left child
          const bool   right_child,   // specify whether the node has a right child
          const uint32 offset,        // child offset
          const uint32 skip_node,     // skip node
          const uint32 level,         // split level
          const uint32 begin,         // node range begin
          const uint32 end,           // node range end
          const uint32 split_index);  // split index

       void write_leaf(
          const uint32 leaf_index,    // leaf to write
          const uint32 node_index,    // node containing this leaf
          const uint32 begin,         // leaf range begin
          const uint32 end);          // leaf range end
   };
};

The following code snippet shows how to use this builder:

#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;

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,
    tree_writer );

generate_radix_tree() [3/3]

template<typename Tree_writer , typename Integer >

void cugar::cuda::generate_radix_tree	(	Radixtree_context &	context,
		const uint32	n_codes,
		const Integer *	codes,
		const uint32	bits,
		const uint32	max_leaf_size,
		const bool	keep_singletons,
		const bool	middle_splits,
		Tree_writer &	tree
	)

Generate a binary tree from a set of sorted integers, splitting the set top-down at each occurrence of a bit set to 1. In practice, if the integers are seen as Morton codes, this algorithm generates a middle-split k-d tree.

Parameters

context	the generation context
n_codes	number of entries in the input set of codes
codes	input set of codes
bits	number of bits per code
max_leaf_size	maximum target number of entries per leaf
keep_singletons	mark whether to keep or suppress singleton nodes in the output tree
middle_splits	mark whether to allow pure middle splits once a group of integers are all equal. NOTE that if this flag is set to false, the maximum leaf size cannot be guaranteed
tree	output tree