A Highly Efficient Computational Method for Particle Search and Positioning in 3D Cells: The Volume Comparison and Cartesian Cell Registration Approach

Abstract

This study introduces a notably simple and effective computational method for particle search and positioning in 3D cells by combining the newly proposed Volume Comparison (VC) method with the Cartesian Cell Registration (CCR) method. Our method achieves a remarkable speed-up ratio of 9,675 relative to the brute-force search in rarefied gas flow simulations using the DSMC method with 61,047 computational 3D cells. Furthermore, our results indicate that the proposed method is approximately 4.45 to 5.73 times faster than the conventional methods, due to the reduced number of cells that need to be searched. Moreover, it eliminates the time step restrictions inherent in the conventional methods by permitting particles to move beyond adjacent cells, thereby enabling larger time steps and reducing overall computational cost. Additionally, our method precisely performs particle search and positioning—determining whether a particle is located within three-dimensional convex or concave cells, regardless of type—and facilitates efficient computation of residence times by geometrically analyzing particle trajectories and their intersections with cell boundaries. These techniques effectively address challenges such as handling moving or deforming meshes without necessitating re-registration, employing the inverse deformation function to ensure robustness. By combining accuracy with computational efficiency, the VC and CCR methods prove highly effective for advanced simulations involving particle search and positioning in complex 3D environments, such as rarefied gases, solvents, diesel sprays in engines, molecules in nanoscale flows, the dynamics of granular materials, and the gas-phase equations of multiphase flows.