Design of an interactive nonlinear finite element-based deformable object simulator

Realistic behavior of deformable objects is essential for many applications such as simulation for surgical training. Existing techniques of deformable modeling for real time simulation have either used approximate methods that are not physically accurate or linear methods that do not produce reasonable global behavior. The proposed nonlinear finite element method (FEM) on hyper-elastic material is developed, which produces a linear computation cost to system size ratio enabling real time computation. Adaptive meshing is necessary to provide sufficient detail where necessary while minimizing unnecessary computation. I propose a scheme for mesh adaptation based on the dynamic progressive mesh (DPM) algorithm.; Novel explicit time integration schemes utilizing multiple levels of detail are proposed based on multigrid (MG) method. These original approaches construct a non-nested mesh hierarchy which makes the methods easier to set up. They possess the desirable characteristic in a surgical simulation environment that simulation stability under arbitrary user manipulation is greatly improved. MG algorithms can also improve the convergence rate.; Interactive simulation of nonlinear deformable objects requires high computational power in order to achieve the level of detail and realism required by typical applications. I developed a high performance interactive simulation system that runs on a cluster system exploiting a fast, parallelized nonlinear multigrid FEM engine. I also discuss the methodology I used to parallelize the multigrid time integrator and analyze the speedup.