We present an efficient method for the physical simulation of soft tissue deformation for animated characters using octrees. Previous work on efficient elasticity simulation relies on the regular structure of a uniform grid discretization. However, representing the complicated boundaries of animated characters requires a high resolution grid, which consumes large amounts of memory and is computationally expensive. By refining an octree around the surface of the character, our memory usage and simulation times grow only quadratically with the inverse of the cell size, compared to cubic growth for a uniform grid. We realize memory savings of 18x and a speedup of 1.7x over a uniform grid with the same boundary resolution on one production example. Moreover, we show that we are able to simulate complex geometry that is infeasible with a uniform grid due to memory usage that would exceed our method by 50x or more. To achieve this we derive a matrix-free geometric multigrid method for the solution of linear systems resulting from an octree discretization of the equations of corotational linear elasticity. We also demonstrate the high parallel scalability of our optimized shared-memory CPU implementation in a fully-featured production-level system.

Andy Milne, Mark A. McLaughlin, Haixiang Liu, Alexey Stomakhin, Rasmus Tamstorf

Disney Tech Report 2017