Fast and Robust Inversion-Free Shape Manipulation

Tiantian Liu
University of Pennsylvania
Ming Gao
University of Wisconsin-Madison
Lifeng Zhu
Southeast University
Eftychios Sifakis
University of Wisconsin-Madison

Ladislav Kavan
University of Utah

A band of surface vertices on a tetrahedralized bunny is constricted to a tight noose. Even with severe distortion, the resulting mesh is inversion-free, i.e., all tetrahedral elements have positive volume.


We present a shape manipulation technique capable of producing deformations of 2D and 3D meshes, guaranteeing that no elements will be inverted. We achieve this by augmenting the quadratic ex-rotated elastic energy with additional convex terms that penalize the presence of inverted elements. Using a schedule of increasing penalty coefficients, we efficiently and robustly converge to an inversion free state by solving a sequence of unconstrained convex minimization problems. This process can be interpreted as a special purpose Semi-Definite Programming (SDP) solver. We demonstrate that our method outperforms solvers used in previous work, including commercial-grade SDP software (MOSEK). As an additional benefit, our method also converges to the solution via a more intuitive path, which can be used for quick preview. We demonstrate the efficacy of our scheme in a number of 2D and 3D shapes undergoing moderate to drastic deformation.


Tiantian Liu, Ming Gao, Lifeng Zhu, Eftychios Sifakis, Ladislav Kavan. Fast and Robust Inversion-Free Shape Manipulation. Computer Graphics Forum 35(2) [Proceedings of Eurographics], 2016.  

Links and Downloads



Supplemental document



Our special thanks belong to Nathan Marshak for initial investigation of this problem within the scope of his Masters thesis. We thank the anonymous reviewers for many useful comments and Alec Jacobson, Shahar Kovalsky, Yaron Lipman, Daniele Panozzo, and Steven Wright for fruitful discussions.We also thank Harmony Li for narrating the accompanying video. This research was supported by NSF CAREER Award IIS-1350330 and NSF Grants IIS- 1253598, IIS-1407282. Lifeng Zhu has been partially supported by the National Science Foundation of China (NSFC) under Grant No. 61502096 and the Natural Science Foundation of Jiangsu Province under Grant No. BK20150634.