Neighboring-based Linear System for Dynamic Meshes

Abstract

A linear system is a fundamental building block for several mesh-based computer graphics applications such as simulation, shape deformation, virtual surgery, and fluid/smoke animation, among others. Nevertheless, such a system is most of the times seen as a black box and algorithms do not deal with its optimization. Depending on the number of unknowns, the linear system is often considered as an obstacle for real time application and as a building block for offline computations. We present in this paper, a neighboring-based methodology for representing a linear system. This new representation enables a compact storage of the set of equation, flexibility for ordering the unknowns and a rapid iterative solution, by means of an optimized matrix-vector multiplication. In addition, this representation facilitates the modification of part of the linear system without affecting its unchanged part and avoiding the complete rebuild of the system. This specially benefits applications dealing with dynamic meshes, where the geometry, the topology or both are constantly changed. We present the capabilities of our methodology in models with different sizes and for different operations, highlighting the dynamic characteristic of the mesh. We believe that several applications in computer graphics could benefit from our methodology, in order to improve their convergence and their performance, reducing the number of iterations and the computation time.