Coherent spherical range-search for dynamic points on GPUs

Lianping Xing, Charlie Wang*, Kin-Chuen Hui

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

1 Citation (Scopus)


We present an approach to accelerate spherical range-search (SRS) for dynamic points that employs the computational power of many-core GPUs. Unlike finding k approximate nearest neighbours (ANNs), exact SRS is needed in geometry processing and physical simulation to avoid missing small features. The spatial coherence of query points and the temporal coherence of dynamic points are exploited in our approach to achieve very efficient range-search on AABB-trees. We test our coherent SRS in several applications including point-point-set geometry processing, distance-field generation and particle-based simulation, which are best scenarios to present the spatial and the temporal coherence of spherical queries on dynamic points. On a PC with NVIDIA GTX 660 Ti GPUs, our approach can take 1M queries on 1M dynamic points at a rate of 1600 queries/ms, where 49 neighbours are found on average within the range of 1/100 of the bounding-box's diagonal length. We observe an increase of up to 4x compared with conventional voxel-based GPU searching approaches in the benchmark of particle-based fluid simulation. Moreover, the speedup can be scaled up to 150x when being applied to highly non-uniform distribution of particles in the simulation.

Original languageEnglish
Pages (from-to)12-25
Number of pages14
JournalComputer-Aided Design
Publication statusPublished - 16 Jan 2017


  • Coherence
  • Dynamic points
  • GPU
  • Parallel algorithm
  • Range-search


Dive into the research topics of 'Coherent spherical range-search for dynamic points on GPUs'. Together they form a unique fingerprint.

Cite this