Interactively Cutting and Constraining Vertices in Meshes Using Augmented Matrices

Yu-Hong Yeung, Jessica Crouch, Alex Pothen

We present a finite element solution method that is well-suited for interactive simulations of cutting meshes in the regime of linear elastic models. Our approach features fast updates to the solution of the stiffness system of equations to account for real-time changes in mesh connectivity and boundary conditions. Updates are accomplished by augmenting the stiffness matrix to keep it consistent with the changes to the underlying model, without re-factoring the matrix at each step of cutting. The initial stiffness matrix and its Cholesky factors are used to implicitly form and solve a Schur complement system using an iterative solver. As changes accumulate over many simulation time steps, the augmented solution method slows down due to the size of the augmented matrix. However, by periodically re-factoring the stiffness matrix in a concurrent background process, fresh Cholesky factors that incorporate recent model changes can replace the initial factors. This controls the size of the augmented matrices and provides a way to maintain a fast solution rate as the number of changes to a model grows. We exploit sparsity in the stiffness matrix, the right-hand-side vectors and the solution vectors to compute the solutions fast, and show that the time complexity of the update steps is bounded linearly by the size of the Cholesky factor of the initial matrix. Our complexity analysis and experimental results demonstrate that this approach scales well with problem size. Results for cutting and deformation of 3D linear elastic models are reported for meshes representing the brain, eye, and model problems with element counts up to 167, 000; these show the potential of this method for real-time interactivity. An application to limbal incisions for surgical correction of astigmatism, where linear elastic models and small deformations are sufficient, is included.

Interactively Cutting and Constraining Vertices in Meshes Using Augmented Matrices

(Comments are closed)