Scalable and rapid nearest neighbor particle search using adaptive disk sector

Area of Science:

• Computational Physics
• Scientific Computing
• Particle-Based Simulations

Background:

• Nearest Neighbor Particle (NNP) calculations are crucial for particle-based simulations.
• Existing methods often struggle with efficiency in dynamic, movable particle systems.
• Traditional approaches like tree structures require continuous updates, hindering performance.

Purpose of the Study:

• To propose an efficient framework for accelerating NNP calculations in movable particle systems.
• To leverage dynamic changes in disk sectors for faster neighbor identification.
• To provide a simple, efficient alternative to complex data structures for NNP.

Main Methods:

• A novel framework utilizes adaptive disk sectors to define the NNP region.
• The inspection range (disk sector) is automatically updated based on particle movement (position and velocity).
• NNP calculations are accelerated by using particles within dynamically adjusted disk sectors via closed-form expressions.

Main Results:

• The proposed method achieves 2x to 20x speedup compared to Hash tables and K-d trees.
• Demonstrated efficiency in diverse simulation scenes and various applications.
• Scalability confirmed across scenarios including particle-based fluids, collision handling, and turbulent flow.

Conclusions:

• The proposed framework offers a simple yet effective method for accelerating NNP calculations.
• It significantly outperforms traditional methods, especially for dynamic and movable particle systems.
• The approach is highly scalable and applicable to a wide range of scientific simulations.