John Canny and Yan Zhuang
UC Berkeley

“Real-Time Simulation of Global Deformation”

Surgical simulation for haptics is a great challenge. Tissue deformations are large, material properties are time-dependent and non-linear, and tissue geometry changes due to cutting. In this work, we focus on fixed-geometry models. We were able to  demonstrate real-time performance with non-linear strain and thousands of elements. We explored two techniques to accelerate mass matrix inversion (the bottleneck): nested dissection and diagonalization. Nested dissection is more expensive but models dynamics exactly. Diagonalization lumps mass to nodes and is similar dynamically to spring-mass models. We used diagonalization in our real-time simulations. We extended the model  above in two ways: (i) addition of an impulse response to contacts on the surface of the model. Our impulse response step is constant-time, so simulations run in real time even with many impacts. (ii) use of a "graded mesh" for the model interior. The stress in an elastic material is low-passed filtered by the material itself. It turns out that elements can be graded with size that increases with distance from the boundary, without losing accuracy in the computed strains. Such a graded mesh is one  order of magnitude smaller than a dense mesh (O(n^2) vs. O(n^3)). To put it another way, a graded mesh has the same asymptotic number of elements as a surface mesh, and yet accurately models the internal state of the material, even with non-linear strain.