Using Motion Levels Of Detail in the Fast Multipole Method for Simulation of Large Particle Systems

摘要

This article introduces a novel approach to increase the performances of N-body simulations. In an N-body simulation, we wish to evaluate all pairwise interactions between N bodies or particles. The direct computation of all pairwise interactions requires O(N~2) time, which is clearly prohibitive for a very large N. Our approach combines the Fast Multipole Method (FMM) coming from computational physics with motion levels of detail from computer graphics. The main goal is to speed up the execution of the N-body simulations while controlling the precision of the associated approximation, a natural trade-off between accuracy and efficiency common in the field of simulation. At each simulation cycle, the motion levels of detail are generated automatically and the appropriate ones are chosen adaptively to reduce computational costs. The new approach follows the overall structure of the FMM. However, clusters are approximated using their Center of Mass (CoM) in force computations. A similarity measure is used to decide which clusters can be approximated without any significant loss in the accuracy of the simulation. The proposed approach is tested for Coulombic system, in which N charges induce potentials to each other. The preliminary results show a significant complexity reduction without any remarkable loss in the visual appearance of the simulation, indicating the potential use of the proposed model in the simulation of a wide range of N-Body systems.