Automatic dynamics simplification in Fast Multipole Method: application to large flocking systems

摘要

This paper introduces a novel framework with the ability to adjust simulation's accuracy level dynamically for simplifying the dynamics computation of large particle systems to improve simulation speed. Our new approach follows the overall structure of the well-known Fast Multipole Method (FMM) coming from computational physics. The main difference is that another level of simplification has been introduced by combining the concept of motion levels of detail from computer graphics with the FMM. This enables us to have more control on the FMM execution time and thus to trade accuracy for efficiency whenever possible. At each simulation cycle, the motion levels of detail are updated and the appropriate ones are chosen adap-tively to reduce computational costs. The proposed framework has been tested on the simulation of a large dynamical flocking system. 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 more realistic situations such as crowd simulation.