Scalable and rapid nearest neighbor particle search using adaptive disk sector

Abstract

In this paper, we propose a framework for efficiently accelerating Nearest Neighbor Particle (NNP) calculations in a movable particle-based system by leveraging the dynamic changes in disk sectors. The NNP region based on particles and disk sectors is determined by the following three conditions: 1) The position of the disk resides within the range of neighbor particles. 2) The position of a neighbor particle exists within a disk sector. 3) A neighbor particle exists between the two vectors that form the disk sector. When all of these conditions are satisfied, we assume that there is a particle within the disk sector. In this paper, we automatically update the inspection range of NNP, which is the disk sector, based on the movement of particles. To calculate the dynamic changes in the disk sector, we control the direction, length, and angle of the disk based on the positions and velocities of particles. Ultimately, we accelerate the computation of NNP by utilizing the particles located within the calculated disk sector. The proposed acceleration method can be implemented simply, as it operates on the particles within the disk sector using closed-form expressions, without the explicit data structures like trees. Especially in the case of movable particles, unlike the conventional adaptive tree approach that requires continuous data structure updates, the proposed method can be efficiently utilized in applications requiring NNP. This is because it rapidly calculates collision areas using closed-form expressions that are adjusted according to the particles’ motion. Our method yielded results that were 2 to 20 times faster compared to Hash tables or K-d trees in experiments conducted across diverse scenes. Furthermore, its scalability was demonstrated through its application in various scenarios (particle-based fluids, splash and foam, isoline tracking, turbulent flow, collision handling).