Coherent spherical range-search for dynamic points on GPUs. (May 2017)

• Record Type: Journal Article
• Authors: Xing, Lianping; Wang, Charlie C.L.; Hui, Kin-Chuen
• Is Part Of: Computer aided design. Volume 86(2017)
• Page Start: 12
• Page End: 25
• Publication Date: 2017-05
• Subjects: Range-search -- Coherence -- Dynamic points -- Parallel algorithm -- GPU; Computer-aided design -- Periodicals; Engineering design -- Data processing -- Periodicals; Computer graphics -- Periodicals; Conception technique -- Informatique -- Périodiques; Infographie -- Périodiques; Computer graphics; Engineering design -- Data processing; Periodicals; Electronic journals; 620.00420285
• DOI: 10.1016/j.cad.2017.01.002
• Languages: English
• ISSNs: 0010-4485

Abstract

Abstract: 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. Highlights: We present an approach to accelerate spherical range-search (SRS) for dynamic points that employs the computational power of many-core GPUs. 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-set geometry processing, distance-field generation and particle-based simulation. We observe an increase in speed of up to 4 times compared with state-of-the- art approaches running on GPUs.