Class LBVHIndex

Class Documentation

class LBVHIndex

A class that uses a GPU based approach to find nearest neighbors in a data set and calculate surface normals on the neighborhoods by using a LBVH as acceleration structure for the kNN search.

Public Functions

LBVHIndex()

Default constructor m_num_objects = 0; m_num_nodes = 0; m_leaf_size = 1; m_sort_queries = true; m_compact = true; m_flip_x = 1000000.0; m_flip_y = 1000000.0; m_flip_z = 1000000.0;.

LBVHIndex(int leaf_size, bool sort_queries, bool compact, float flip_x = 1000000.0f, float flip_y = 1000000.0f, float flip_z = 1000000.0f)

Constructor of the LBVH.

Parameters:

  • leaf_size – Max number of points covered by a leaf node

  • sort_queries – True, if queries should be sorted by their morton codes

  • compact – True, if the tree should be compacted after the optimization step

  • flip_x – x coordinate that the normals will be flipped to

  • flip_y – y coordinate that the normals will be flipped to

  • flip_z – z coordinate that the normals will be flipped to

~LBVHIndex()

Destructor of the LBVH.

void build(float *points, size_t num_points)

This function builds the LBVH on the given points.

Parameters:

  • points – The points of the dataset

  • num_points – The number of points in the dataset

void kSearch(float *query_points, size_t num_queries, int K, unsigned int *n_neighbors_out, unsigned int *indices_out, float *distances_out) const

This function performs a kNN search on the LBVH with the given queries.

Parameters:

  • query_points – The query points.

  • num_queries – Number of query points

  • K – The number of neighbours that should be searched.

  • n_neighbors_out – Stores the number of found neighbors for each query

  • indices_out – Stores the indices of all found neighbors

  • distances_out – Stores the distances of all found neighbors

void kSearch_dev_ptr(float *d_query_points, size_t num_queries, int K, unsigned int *d_n_neighbors_out, unsigned int *d_indices_out, float *d_distances_out) const

This function performs a kNN search on the LBVH with the given queries, but expects device pointers.

Parameters:

  • d_query_points – The query points as device pointer

  • num_queries – Number of query points

  • K – The number of neighbours that should be searched.

  • d_n_neighbors_out – Stores the number of found neighbors for each query as device pointer

  • d_indices_out – Stores the indices of all found neighbors as device pointer

  • d_distances_out – Stores the distances of all found neighbors as device pointer

void radiusSearch(float *query_points, size_t num_queries, int K, float r, unsigned int *n_neighbors_out, unsigned int *indices_out, float *distances_out) const

This function performs a radius search on the LBVH with the given queries.

Parameters:

  • query_points – The query points.

  • num_queries – Number of query points

  • K – The number of neighbours that should be searched.

  • r – The radius

  • n_neighbors_out – Stores the number of found neighbors for each query

  • indices_out – Stores the indices of all found neighbors

  • distances_out – Stores the distances of all found neighbors

void radiusSearch_dev_ptr(float *d_query_points, size_t num_queries, int K, float r, unsigned int *d_n_neighbors_out, unsigned int *d_indices_out, float *d_distances_out) const

This function performs a radius search on the LBVH with the given queries, but expects device pointers.

Parameters:

  • d_query_points – The query points.

  • num_queries – Number of query points

  • K – The number of neighbours that should be searched.

  • r – The radius

  • d_n_neighbors_out – Stores the number of found neighbors for each query as device pointer

  • d_indices_out – Stores the indices of all found neighbors as device pointers

  • d_distances_out – Stores the distances of all found neighbors as device pointers

void process_queries(float *queries_raw, size_t num_queries, int K, float r, unsigned int *n_neighbors_out, unsigned int *indices_out, float *distances_out) const

This function processes the queries by calling the query_knn_kernel.

Parameters:

  • queries_raw – The query points.

  • num_queries – Number of query points

  • K – The number of neighbours that should be searched.

  • r – The radius

  • n_neighbors_out – Stores the number of found neighbors for each query

  • indices_out – Stores the indices of all found neighbors

  • distances_out – Stores the distances of all found neighbors

void process_queries_dev_ptr(float *d_query_points, size_t num_queries, int K, float r, unsigned int *d_n_neighbors_out, unsigned int *d_indices_out, float *d_distances_out) const

This function processes the queries by calling the query_knn_kernel, but expects device pointer.

Parameters:

  • d_query_points – The query points.

  • num_queries – Number of query points

  • K – The number of neighbours that should be searched.

  • r – The radius

  • d_n_neighbors_out – Stores the number of found neighbors for each query as device pointer

  • d_indices_out – Stores the indices of all found neighbors as device pointers

  • d_distances_out –

    Stores the distances of all found neighbors

    as device pointers

void calculate_normals(float *normals, size_t num_normals, float *queries, size_t num_queries, int K, const unsigned int *n_neighbors_in, const unsigned int *indices_in) const

This function calculates the normals of each query with the given nearest neighborhoods by calling the calculate_normals_kernel.

Parameters:

  • normals – Stores the calculated normals

  • num_normals – Number of normals that are calculated

  • queries – The queries for which the normal is calculated

  • num_queries – Number of queries

  • K – The number of neighbours that should be searched.

  • n_neighbors_in – Number of found neighbors for each query

  • indices_in – Indices of the found neighbors

void knn_normals(int K, float *normals, size_t num_normals)

This function performs a kNN search on each point in the dataset and calculates the normals on the neighborhoods in a single kernel launch (knn_normals_kernel)

Parameters:

  • K – The number of neighbours that should be searched.

  • normals – Stores the calculated normals

  • num_normals – Number of normals to be calculated

void getExtent(AABB *extent, float *points, size_t num_points) const

This function gets the extent of the dataset (max and min values of each dimension)

Parameters:

  • extent – Stores the extent of the dataset

  • points – The points of the dataset

  • num_points – Number of points in the dataset

void getPtxFromCuString(std::string &ptx, const char *sample_name, const char *cu_source, int K) const

This function creates a PTX from a given CUDA file.

Parameters:

  • ptx – String that stores the PTX

  • sample_name – Name of the CUDA kernel

  • cu_source – The CUDA file as char*

  • K – The number of neighbours that should be searched.

Public Members

unsigned int m_num_objects
unsigned int m_num_nodes
unsigned int m_leaf_size
bool m_sort_queries
bool m_compact
unsigned int *m_root_node
float m_flip_x
float m_flip_y
float m_flip_z
float *m_d_points
unsigned int *m_d_sorted_indices
BVHNode *m_d_nodes
AABB *m_d_extent