Medial Elastics:Efficient and Collision-ready Deformation via Medial Axis Transform
Authors
Lei Lan, Ran Luo, Marco Fratarcangeli, Weiwei Xu, Huamin Wang, Xiaohu Guo, Junfeng Yao, Yin Yang
Abstract
We propose a framework for the real-time simulation of nonlinear deformable objects. The primary feature of our system is the seamless integration of deformable simulation and collision culling, which are often independently handled in existing animation systems. The bridge connecting them is the medial axis transform or MAT, a high-fidelity shape approximation of complex 3D shapes. From the physics simulation perspective, MAT leads to an expressive and compact reduced nonlinear model. We employ a semi-reduced projective dynamics formulation, which well captures highfrequency local deformations of high-resolution models while retaining a low computation cost. Our key observation is that the most compelling (nonlinear) deformable effects are actually enabled by the local constraints projection, which should not be aggressively reduced. The global stage solves a linear system and is less GPU-friendly, to which the model reduction applies with marginal compromise of the visual plausibility. We propose a novel subspace collision-ready matrix assembly strategy so that the reduced global matrix is collision-invariant and can be pre-factorized. From the collision detection/culling perspective, MAT is more geometrically versatile using linear- or bilinear-interpolated spheres (i.e. the so called medial primitive) to approximate the boundary of the input model. For instance, only 87 medial primitives are able to encapsulate the dinosaur model as tightly as one uses 53, 294 AABBs or 37, 282 bounding spheres. The intersection test between two medial primitives is formulated as a quadratically constrained quadratic program problem. We give an algorithm to solve this problem exactly, which yields the deepest penetration between a pair of intersecting medial primitives. When coupled with spatial hashing, collision (including self-collision) can be efficiently identified on GPU within few milliseconds even for massive simulations. We have tested our system on a variety of geometrically complex and high-resolution deformable objects, and our system can produce convincing animations with all the collisions/self-collisions well handled in real time.
