CSRS: A Library for Coherent Spherical Range-Search on GPUs

Lianping Xing, Charlie C.L. Wang and Kin-Chuen Hui

what is CSRS? copyright source code example 1 example 2 example 3

What is CSRS?
CSRS is a library written in C++, which supports algorithms for exact spherical range-search in arbitrarily dimensions.

Range-search with a radius r for a query q on a set of data points P is an operation to find all the neighbors p the distances from which to q are not larger than r. As the range of search is a d-dimensional sphere, this is called spherical range-search (SRS).

Different from finding k approximate nearest neighbors (ANNs), exact SRS is needed in geometry processing and physical simulation to avoid missing small features. With the help of a balanced AABB-tree, the spatial coherence of query points and the temporal coherence of dynamic points are exploited to achieve very efficient range-search and hierarchical update.

The library also comes with test programs for measuring the quality of performance of CSRS on any particular data sets. Our library provides the implementation of method presented in the following paper.

[1] Lianping Xing, Charlie C.L. Wang, and Kin-Chuen Hui, "Coherent spherical range-search for dynamic points on GPUs", Computer-Aided Design, 2017.
All rights about the program are reserved by Lianping Xing, Charlie C.L. Wang and Kin-Chuen Hui at the Department of Mechanical and Automation Engineering, The Chinese University of Hong Kong. In no event shall the author be liable to any party for direct, indirect, special, incidental, or consequential damage arising out of the use of this program.
This program is developed based on nVIDIA CUDA GPUs with compute capability larger than 2.0.

The current version of CSRS can be downloaded here.
  • CSRS Version 0.5: CSRS_0.5.zip (Date: July 10, 2015)

  • Notes:
  • For different dimension executions, "#define CSRS_PNT_DIM" (the current setting is for dimension 3) at the top of the header file - "SRStree.h" should be changed accordingly.

  • Example of General Search

    Example of Searching by Data Points (This is about 30% faster than the general search.)

    Example of Searching Nearest Neighbors (This is much faster than the general spherical range search.)