The Research Of High Performance Algorithms In Physically Based Fluid Animation

In this paper, the algorithms for ?uid animation are studied broadly and the performance bottlenecks are analyzed. Especially, several important high performance algorithms are investigated deeply. Actually, it conststs of the following topics, i.e., the high-performance generation of 3D ?uid data ?eld,the high-performance algorithms of solving Navier-Stokes equations, the highperformance algorithms for the simulation of granular materials with discrete element method and the design of a high-performance software platform for?uid animation.The generation of the 3D data ?eld not noly the data preparation for ?uid animation, but also go throughout the whole simulation process possibly. For this purpose, the generation of ?uid data ?eld, especially the signed distance?eld, is studied ?rst. A double layer method for constructing signed distance?eld(SDF) from triangle mesh is proposed. In this method, two layers of particles are constructed around the triangle mesh to approximate it. Then the unsigned distance ?elds of these two layers of particles are computed.Finally the desired SDF is computed by a simple formula. This approach has a simple form and avoids complex geometric con?gurations. Moreover, it can be parallelized trivally. The numerical results show that the double layer method has a high parallel e?ciency, with a speedup ratio of 10–40 or so.To solve the Navier-Stokes equations in a high performance way, a broad new parallel preconditioner for the conjugate gradient method for solving the pressure Poisson equation is proposed. In the design of the new preconditioner,the linear system turn into consideration back to the grid with the elements of the sparse matrix represented by intuitive grid templates. The inverse of the preconditioner is designed straightforward by combing the methods of theoretical analysis, data analysis and numerical experiments to determine the best parameters. In the research process, it was found that the condition number of the matrix can be reduced greatly by reconstructing the sparsity of the matrix.Based on it, the algorithm is further generilized. The numerical results show that actually the new preconditioned conjugate method has a better convergence rate and parallel e?ciency, the iterations are reduced to about a half of those for classical CG method. The generilized algorithm can reduce the iterations to about 1/3 of that of classical CG’s. Furthermore, the parallelized speedup ratio is about 5–10.The high performance discrete element method for the simulation of granular materials is also studied. In the computer graphics community, the grains are usually modeled by combined spheres. However, to our knowledge, the study of GPGPU algorithms for this special case are not found in the literature yet. The main di?culty of the parallelism is that the variable-length data structures are not supported by the GPGPU architectures directly. To overcome such di?culties, a new high performance data structure which is suitable for GPGPU platform is proposed. Then a new parallel algorithm is proposed based on this data structure. The numerical results show that the new parallel algorithm has a speedup ratio of 10.Finally, a software architecture for high performance ?uid animation is established, and then realized as a software platform PBAT. The architecture is designed according to the principle of seperating changing and loosely coupling of function modules. Actually, the intferface and simulation modules are seperated with a high degree. Di?erent simulation modules are designed to be loosely coupling e?ectively. Non-volatile functions are highly componentized.As the simulation parameters are designed as an independent module, the impact of parameters change to the whole system is localized. Actually, the PBAT architecture takes the develop-time properties and run-time properties,versatility and performance into consideration. Up to now, many mathematical tools and simulation modules have been implemented. The software platform has excellent reusability, scalability and maintainability due to the appropriate architecture. Moreover, the PBAT software has good heterogeneity and portability. More importantly, it has higher performance since many algorithms are implemented by OpenCL API.