ACloudViewer  3.9.4
A Modern Library for 3D Data Processing
Public Member Functions | Protected Types | Protected Member Functions | Protected Attributes | List of all members
flann::CudaKdTreeBuilder Class Reference

#include <kdtree_cuda_builder.h>

Public Member Functions

 CudaKdTreeBuilder (const thrust::device_vector< float4 > &points, int max_leaf_size)
 
 ~CudaKdTreeBuilder ()
 
void buildTree ()
 

Protected Types

enum  AllocationInfo { NodeCount =0 , NodesAllocated =1 , OutOfSpace =2 }
 

Protected Member Functions

void update_leftright_and_aabb (const thrust::device_vector< float > &x, const thrust::device_vector< float > &y, const thrust::device_vector< float > &z, const thrust::device_vector< int > &ix, const thrust::device_vector< int > &iy, const thrust::device_vector< int > &iz, const thrust::device_vector< int > &owners, thrust::device_vector< cuda::kd_tree_builder_detail::SplitInfo > &splits, thrust::device_vector< float4 > &aabbMin, thrust::device_vector< float4 > &aabbMax)
 takes the partitioned nodes, and sets the left-/right info of leaf nodes, as well as the AABBs More...
 
void separate_left_and_right_children (thrust::device_vector< int > &key_in, thrust::device_vector< int > &val_in, thrust::device_vector< int > &key_out, thrust::device_vector< int > &val_out, thrust::device_vector< int > &left_right_marks, bool scatter_val_out=true)
 
void resize_node_vectors (size_t new_size)
 

Protected Attributes

const thrust::device_vector< float4 > * points_
 
thrust::device_vector< int > * child1_
 
thrust::device_vector< int > * parent_
 parent node of each node More...
 
thrust::device_vector< cuda::kd_tree_builder_detail::SplitInfo > * splits_
 split info (dim/value or left/right pointers) More...
 
thrust::device_vector< float4 > * aabb_min_
 min aabb value of each node More...
 
thrust::device_vector< float4 > * aabb_max_
 max aabb value of each node More...
 
thrust::device_vector< int > allocation_info_
 
int max_leaf_size_
 
thrust::device_vector< float > * points_x_
 
thrust::device_vector< float > * points_y_
 
thrust::device_vector< float > * points_z_
 
thrust::device_vector< int > * index_x_
 
thrust::device_vector< int > * index_y_
 
thrust::device_vector< int > * index_z_
 
thrust::device_vector< int > * owners_x_
 
thrust::device_vector< int > * owners_y_
 
thrust::device_vector< int > * owners_z_
 
thrust::device_vector< int > * leftright_x_
 
thrust::device_vector< int > * leftright_y_
 
thrust::device_vector< int > * leftright_z_
 
thrust::device_vector< int > * tmp_index_
 
thrust::device_vector< int > * tmp_owners_
 
thrust::device_vector< int > * tmp_misc_
 
bool delete_node_info_
 

Detailed Description

Definition at line 401 of file kdtree_cuda_builder.h.

Member Enumeration Documentation

◆ AllocationInfo

enum flann::CudaKdTreeBuilder::AllocationInfo
protected
Enumerator
NodeCount 
NodesAllocated 
OutOfSpace 

Definition at line 701 of file kdtree_cuda_builder.h.

Constructor & Destructor Documentation

◆ CudaKdTreeBuilder()

flann::CudaKdTreeBuilder::CudaKdTreeBuilder ( const thrust::device_vector< float4 > &  points,
int  max_leaf_size 
)
inline

Definition at line 404 of file kdtree_cuda_builder.h.

References aabb_max_, aabb_min_, allocation_info_, child1_, delete_node_info_, index_x_, index_y_, index_z_, flann::cuda::kd_tree_builder_detail::SplitInfo::left, leftright_x_, leftright_y_, leftright_z_, max_leaf_size_, NodeCount, NodesAllocated, OutOfSpace, owners_x_, owners_y_, owners_z_, parent_, points, points_, points_x_, points_y_, points_z_, flann::cuda::kd_tree_builder_detail::SplitInfo::right, splits_, tmp_index_, tmp_misc_, and tmp_owners_.

◆ ~CudaKdTreeBuilder()

flann::CudaKdTreeBuilder::~CudaKdTreeBuilder ( )
inline

Definition at line 449 of file kdtree_cuda_builder.h.

References aabb_max_, aabb_min_, child1_, delete_node_info_, index_x_, index_y_, index_z_, leftright_x_, leftright_y_, leftright_z_, owners_x_, owners_y_, owners_z_, parent_, points_x_, points_y_, points_z_, splits_, tmp_index_, tmp_misc_, and tmp_owners_.

Member Function Documentation

◆ buildTree()

void flann::CudaKdTreeBuilder::buildTree ( )
inline

build the tree general idea:

  • build sorted lists of the points in x y and z order (to be able to compute tight AABBs in O(1) )
  • while( nodes to split exist )
    • split non-child nodes along longest axis if the number of points is > max_points_per_node
    • for each point: determine whether it is in a node that was split. If yes, mark it as belonging to the left or right child node of its current parent node
    • reorder the points so that the points of a single node are continuous in the node array
    • update the left/right pointers and AABBs of all nodes

Definition at line 484 of file kdtree_cuda_builder.h.

References aabb_max_, aabb_min_, allocation_info_, flann::cuda::kd_tree_builder_detail::SplitNodes::child1_, child1_, copy, QtCompat::endl(), index_x_, index_y_, index_z_, leftright_x_, leftright_y_, leftright_z_, make_float4(), max_leaf_size_, flann::cuda::kd_tree_builder_detail::SplitNodes::maxPointsPerNode, flann::cuda::kd_tree_builder_detail::SplitNodes::node_count, NodeCount, flann::cuda::kd_tree_builder_detail::SplitNodes::nodes_allocated, NodesAllocated, flann::cuda::kd_tree_builder_detail::SplitNodes::out_of_space, OutOfSpace, owners_x_, owners_y_, owners_z_, flann::cuda::kd_tree_builder_detail::SplitNodes::parent_, parent_, points_, points_x_, points_y_, points_z_, resize_node_vectors(), separate_left_and_right_children(), flann::cuda::kd_tree_builder_detail::SplitNodes::splits, splits_, std::swap(), tmp_index_, tmp_owners_, and update_leftright_and_aabb().

◆ resize_node_vectors()

void flann::CudaKdTreeBuilder::resize_node_vectors ( size_t  new_size)
inlineprotected

allocates additional space in all the node-related vectors. new_size elements will be added to all vectors.

Definition at line 670 of file kdtree_cuda_builder.h.

References aabb_max_, aabb_min_, child1_, flann::cuda::kd_tree_builder_detail::SplitInfo::left, parent_, flann::cuda::kd_tree_builder_detail::SplitInfo::right, and splits_.

Referenced by buildTree().

◆ separate_left_and_right_children()

void flann::CudaKdTreeBuilder::separate_left_and_right_children ( thrust::device_vector< int > &  key_in,
thrust::device_vector< int > &  val_in,
thrust::device_vector< int > &  key_out,
thrust::device_vector< int > &  val_out,
thrust::device_vector< int > &  left_right_marks,
bool  scatter_val_out = true 
)
inlineprotected

Separates the left and right children of each node into continuous parts of the array. More specifically, it seperates children with even and odd node indices because nodes are always allocated in pairs -> child1==child2+1 -> child1 even and child2 odd, or vice-versa. Since the split operation is stable, this results in continuous partitions for all the single nodes. (basically the split primitive according to sengupta et al) about twice as fast as thrust::partition

Definition at line 649 of file kdtree_cuda_builder.h.

References flann::cuda::kd_tree_builder_detail::set_addr3::f_, flann::cuda::kd_tree_builder_detail::set_addr3::npoints_, tmp_misc_, and flann::cuda::kd_tree_builder_detail::set_addr3::val_.

Referenced by buildTree().

◆ update_leftright_and_aabb()

void flann::CudaKdTreeBuilder::update_leftright_and_aabb ( const thrust::device_vector< float > &  x,
const thrust::device_vector< float > &  y,
const thrust::device_vector< float > &  z,
const thrust::device_vector< int > &  ix,
const thrust::device_vector< int > &  iy,
const thrust::device_vector< int > &  iz,
const thrust::device_vector< int > &  owners,
thrust::device_vector< cuda::kd_tree_builder_detail::SplitInfo > &  splits,
thrust::device_vector< float4 > &  aabbMin,
thrust::device_vector< float4 > &  aabbMax 
)
inlineprotected

takes the partitioned nodes, and sets the left-/right info of leaf nodes, as well as the AABBs

Definition at line 610 of file kdtree_cuda_builder.h.

References flann::cuda::kd_tree_builder_detail::SetLeftAndRightAndAABB::aabbMax, flann::cuda::kd_tree_builder_detail::SetLeftAndRightAndAABB::aabbMin, flann::cuda::kd_tree_builder_detail::SetLeftAndRightAndAABB::counts, flann::cuda::kd_tree_builder_detail::SetLeftAndRightAndAABB::ix, flann::cuda::kd_tree_builder_detail::SetLeftAndRightAndAABB::iy, flann::cuda::kd_tree_builder_detail::SetLeftAndRightAndAABB::iz, flann::cuda::kd_tree_builder_detail::SetLeftAndRightAndAABB::labels, flann::cuda::kd_tree_builder_detail::SetLeftAndRightAndAABB::maxPoints, flann::cuda::kd_tree_builder_detail::SetLeftAndRightAndAABB::nElements, flann::cuda::kd_tree_builder_detail::SetLeftAndRightAndAABB::nodes, tmp_index_, tmp_owners_, flann::cuda::kd_tree_builder_detail::SetLeftAndRightAndAABB::x, flann::cuda::kd_tree_builder_detail::SetLeftAndRightAndAABB::y, and flann::cuda::kd_tree_builder_detail::SetLeftAndRightAndAABB::z.

Referenced by buildTree().

Member Data Documentation

◆ aabb_max_

thrust::device_vector<float4>* flann::CudaKdTreeBuilder::aabb_max_
protected

max aabb value of each node

Definition at line 699 of file kdtree_cuda_builder.h.

Referenced by buildTree(), CudaKdTreeBuilder(), resize_node_vectors(), and ~CudaKdTreeBuilder().

◆ aabb_min_

thrust::device_vector<float4>* flann::CudaKdTreeBuilder::aabb_min_
protected

min aabb value of each node

Definition at line 697 of file kdtree_cuda_builder.h.

Referenced by buildTree(), CudaKdTreeBuilder(), resize_node_vectors(), and ~CudaKdTreeBuilder().

◆ allocation_info_

thrust::device_vector<int> flann::CudaKdTreeBuilder::allocation_info_
protected

Definition at line 711 of file kdtree_cuda_builder.h.

Referenced by buildTree(), and CudaKdTreeBuilder().

◆ child1_

thrust::device_vector<int>* flann::CudaKdTreeBuilder::child1_
protected

left child of each node. (right child==left child + 1, due to the alloc mechanism) child1_[node]==-1 if node is a leaf node

Definition at line 691 of file kdtree_cuda_builder.h.

Referenced by buildTree(), CudaKdTreeBuilder(), resize_node_vectors(), and ~CudaKdTreeBuilder().

◆ delete_node_info_

bool flann::CudaKdTreeBuilder::delete_node_info_
protected

Definition at line 724 of file kdtree_cuda_builder.h.

Referenced by CudaKdTreeBuilder(), and ~CudaKdTreeBuilder().

◆ index_x_

thrust::device_vector<int>* flann::CudaKdTreeBuilder::index_x_
protected

Definition at line 718 of file kdtree_cuda_builder.h.

Referenced by buildTree(), CudaKdTreeBuilder(), and ~CudaKdTreeBuilder().

◆ index_y_

thrust::device_vector<int> * flann::CudaKdTreeBuilder::index_y_
protected

Definition at line 718 of file kdtree_cuda_builder.h.

Referenced by buildTree(), CudaKdTreeBuilder(), and ~CudaKdTreeBuilder().

◆ index_z_

thrust::device_vector<int> * flann::CudaKdTreeBuilder::index_z_
protected

Definition at line 718 of file kdtree_cuda_builder.h.

Referenced by buildTree(), CudaKdTreeBuilder(), and ~CudaKdTreeBuilder().

◆ leftright_x_

thrust::device_vector<int>* flann::CudaKdTreeBuilder::leftright_x_
protected

Definition at line 722 of file kdtree_cuda_builder.h.

Referenced by buildTree(), CudaKdTreeBuilder(), and ~CudaKdTreeBuilder().

◆ leftright_y_

thrust::device_vector<int> * flann::CudaKdTreeBuilder::leftright_y_
protected

Definition at line 722 of file kdtree_cuda_builder.h.

Referenced by buildTree(), CudaKdTreeBuilder(), and ~CudaKdTreeBuilder().

◆ leftright_z_

thrust::device_vector<int> * flann::CudaKdTreeBuilder::leftright_z_
protected

Definition at line 722 of file kdtree_cuda_builder.h.

Referenced by buildTree(), CudaKdTreeBuilder(), and ~CudaKdTreeBuilder().

◆ max_leaf_size_

int flann::CudaKdTreeBuilder::max_leaf_size_
protected

Definition at line 713 of file kdtree_cuda_builder.h.

Referenced by buildTree(), and CudaKdTreeBuilder().

◆ owners_x_

thrust::device_vector<int>* flann::CudaKdTreeBuilder::owners_x_
protected

Definition at line 720 of file kdtree_cuda_builder.h.

Referenced by buildTree(), CudaKdTreeBuilder(), and ~CudaKdTreeBuilder().

◆ owners_y_

thrust::device_vector<int> * flann::CudaKdTreeBuilder::owners_y_
protected

Definition at line 720 of file kdtree_cuda_builder.h.

Referenced by buildTree(), CudaKdTreeBuilder(), and ~CudaKdTreeBuilder().

◆ owners_z_

thrust::device_vector<int> * flann::CudaKdTreeBuilder::owners_z_
protected

Definition at line 720 of file kdtree_cuda_builder.h.

Referenced by buildTree(), CudaKdTreeBuilder(), and ~CudaKdTreeBuilder().

◆ parent_

thrust::device_vector<int>* flann::CudaKdTreeBuilder::parent_
protected

parent node of each node

Definition at line 693 of file kdtree_cuda_builder.h.

Referenced by buildTree(), CudaKdTreeBuilder(), resize_node_vectors(), and ~CudaKdTreeBuilder().

◆ points_

const thrust::device_vector<float4>* flann::CudaKdTreeBuilder::points_
protected

Definition at line 685 of file kdtree_cuda_builder.h.

Referenced by buildTree(), and CudaKdTreeBuilder().

◆ points_x_

thrust::device_vector<float>* flann::CudaKdTreeBuilder::points_x_
protected

Definition at line 716 of file kdtree_cuda_builder.h.

Referenced by buildTree(), CudaKdTreeBuilder(), and ~CudaKdTreeBuilder().

◆ points_y_

thrust::device_vector<float> * flann::CudaKdTreeBuilder::points_y_
protected

Definition at line 716 of file kdtree_cuda_builder.h.

Referenced by buildTree(), CudaKdTreeBuilder(), and ~CudaKdTreeBuilder().

◆ points_z_

thrust::device_vector<float> * flann::CudaKdTreeBuilder::points_z_
protected

Definition at line 716 of file kdtree_cuda_builder.h.

Referenced by buildTree(), CudaKdTreeBuilder(), and ~CudaKdTreeBuilder().

◆ splits_

thrust::device_vector<cuda::kd_tree_builder_detail::SplitInfo>* flann::CudaKdTreeBuilder::splits_
protected

split info (dim/value or left/right pointers)

Definition at line 695 of file kdtree_cuda_builder.h.

Referenced by buildTree(), CudaKdTreeBuilder(), resize_node_vectors(), and ~CudaKdTreeBuilder().

◆ tmp_index_

thrust::device_vector<int>* flann::CudaKdTreeBuilder::tmp_index_
protected

Definition at line 723 of file kdtree_cuda_builder.h.

Referenced by buildTree(), CudaKdTreeBuilder(), update_leftright_and_aabb(), and ~CudaKdTreeBuilder().

◆ tmp_misc_

thrust::device_vector<int> * flann::CudaKdTreeBuilder::tmp_misc_
protected

Definition at line 723 of file kdtree_cuda_builder.h.

Referenced by CudaKdTreeBuilder(), separate_left_and_right_children(), and ~CudaKdTreeBuilder().

◆ tmp_owners_

thrust::device_vector<int> * flann::CudaKdTreeBuilder::tmp_owners_
protected

Definition at line 723 of file kdtree_cuda_builder.h.

Referenced by buildTree(), CudaKdTreeBuilder(), update_leftright_and_aabb(), and ~CudaKdTreeBuilder().

The documentation for this class was generated from the following file: