The simulation of deformable solids is a traditional topic in mechanics. Recently, deformable solids simulation has been widely used in computer animation, game development and virtual surgery to generate realistic deformations. Numerous methods have been developed to accelerate the simulation of realistic materials with complicated geometries, dynamic effects, as well as under user interface control and interaction with rigid bodies and fluids. Recently, there has been an increasing interest in the application of multigrid methods to practical problems, targeting interactive simulation with very high resolutions and with the help of parallel computer implementations.

This thesis presents a multigrid framework for the simulation of high resolution elastic deformable models. The framework incorporates several state-of-the-art techniques from multigrid theory, while adapting them to the specific requirements of graphics, animation and engineering applications, such as the ability to handle elaborate geometry and complex boundary conditions. The efficiency of the solver is practically independent of material parameters, even for near-incompressible materials. The solver also supports the simulation of co-rotational linear elasticity and dynamic systems. With optimization, the algorithm achieves simulation rates as high as 6 frames per second on an 8-core SMP for test models with 256K vertices, and 1.6 frames per second on a 16-core SMP for a 2M vertex object.

To achieve higher-order accuracy solutions, we also present a cut cell method for enforcing Dirichlet and Neumann boundary conditions with nearly incompressible linear elastic materials in irregular domains. Virtual nodes on cut uniform grid cells are used to provide geometric exibility in the domain boundary shape without sacrificing accuracy. We use a mixed formulation utilizing a MACtype staggered grid with piecewise bilinear displacements centered at cell faces and piecewise constant pressures at cell centers. These discretization choices provide the necessary stability in the incompressible limit and the necessary accuracy in cut cells. Numerical experiments suggest second order accuracy in L1. A geometric multigrid method is developed for solving the discrete equations for displacements and pressures that achieves nearly optimal convergence rates independent of grid resolution.

Finally, we propose a soft constraint model for controllable deformable solids simulation and collision problems, and develop an efficient multigrid solver for the constraint system.