Mesh puppetry: cascading optimization of mesh deformation with inverse kinematics

ABSTRACT

We present mesh puppetry, a variational framework for detail-preserving mesh manipulation through a set of high-level, intuitive, and interactive design tools. Our approach builds upon traditional rigging by optimizing skeleton position and vertex weights in an integrated manner. New poses and animations are created by specifying a few desired constraints on vertex positions, balance of the character, length and rigidity preservation, joint limits, and/or self-collision avoidance. Our algorithm then adjusts the skeleton and solves for the deformed mesh simultaneously through a novel cascading optimization procedure, allowing realtime manipulation of meshes with 50K+ vertices for fast design of pleasing and realistic poses. We demonstrate the potential of our framework through an interactive deformation platform and various applications such as deformation transfer and motion retargeting.

REFERENCES

• 1: Norman I. Badler , Kamran H. Manoocherhri , Grahm Walters, Articulated figure positioning by multiple constraints, IEEE Computer Graphics and Applications, v.7 n.6, p.28-38, June 1987 [doi>10.1109/MCG.1987.276894]
• 2: Paolo Baerlocher , Ronan Boulic, An inverse kinematics architecture enforcing an arbitrary number of strict priority levels, The Visual Computer: International Journal of Computer Graphics, v.20 n.6, p.402-417, August 2004 [doi>10.1007/s00371-004-0244-4]
• 3: Mario Botsch , Mark Pauly , Markus Gross , Leif Kobbelt, PriMo: coupled prisms for intuitive surface modeling, Proceedings of the fourth Eurographics symposium on Geometry processing, June 26-28, 2006, Cagliari, Sardinia, Italy
• 4: Ronan Boulic , Ramon Mas-Sanso , Daniel Thalmann, Complex Character Positioning Based on a Compatible Flow Model of Multiple Supports, IEEE Transactions on Visualization and Computer Graphics, v.3 n.3, p.245-261, July 1997 [doi>10.1109/2945.620491]
• 5: Chen, Q., and Guan, S.-U. 2004. Incremental multiple objective genetic algorithms. IEEE Trans. on Systems, Man, and Cybernetics 34, 3 (June), 1325--1334.
• 6: ColDet. 2002. Free 3d collision detection library (gnu lgpl). http://sourceforge.net/projects/coldet.
• 7: Kevin G. Der , Robert W. Sumner , Jovan Popović, Inverse kinematics for reduced deformable models, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
• 8: Igor Guskov , Wim Sweldens , Peter Schröder, Multiresolution signal processing for meshes, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.325-334, July 1999 [doi>10.1145/311535.311577]
• 9: Jin Huang , Xiaohan Shi , Xinguo Liu , Kun Zhou , Li-Yi Wei , Shang-Hua Teng , Hujun Bao , Baining Guo , Heung-Yeung Shum, Subspace gradient domain mesh deformation, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
• 10: Doug L. James , Christopher D. Twigg, Skinning mesh animations, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 11: Tao Ju , Scott Schaefer , Joe Warren, Mean value coordinates for closed triangular meshes, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 12: Leif Kobbelt , Swen Campagna , Jens Vorsatz , Hans-Peter Seidel, Interactive multi-resolution modeling on arbitrary meshes, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.105-114, July 1998 [doi>10.1145/280814.280831]
• 13: Benoît Le Callennec , Ronan Boulic, Interactive motion deformation with prioritized constraints, Graphical Models, v.68 n.2, p.175-193, March 2006 [doi>10.1016/j.gmod.2005.03.001]
• 14: J. P. Lewis , Matt Cordner , Nickson Fong, Pose space deformation: a unified approach to shape interpolation and skeleton-driven deformation, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.165-172, July 2000 [doi>10.1145/344779.344862]
• 15: Yaron Lipman , Olga Sorkine , David Levin , Daniel Cohen-Or, Linear rotation-invariant coordinates for meshes, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 16: Yaron Lipman , Daniel Cohen-Or , Ran Gal , David Levin, Volume and shape preservation via moving frame manipulation, ACM Transactions on Graphics (TOG), v.26 n.1, p.5-es, January 2007 [doi>10.1145/1189762.1189767]
• 17: Lloyd, S. P. 1982. Least squares quantization in pcm. IEEE Transactions on Information Theory 28, 2, 129 -- 137.
• 18: N. Magnenat-Thalmann , R. Laperrière , D. Thalmann, Joint-dependent local deformations for hand animation and object grasping, Proceedings on Graphics interface '88, p.26-33, December 1989, Edmonton, Alberta, Canada
• 19: Alex Mohr , Luke Tokheim , Michael Gleicher, Direct manipulation of interactive character skins, Proceedings of the 2003 symposium on Interactive 3D graphics, April 27-30, 2003, Monterey, California [doi>10.1145/641480.641488]
• 20: Andrew Nealen , Olga Sorkine , Marc Alexa , Daniel Cohen-Or, A sketch-based interface for detail-preserving mesh editing, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 21: Lin Shi , Yizhou Yu , Nathan Bell , Wei-Wen Feng, A fast multigrid algorithm for mesh deformation, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
• 22: O. Sorkine , D. Cohen-Or , Y. Lipman , M. Alexa , C. Rössl , H.-P. Seidel, Laplacian surface editing, Proceedings of the 2004 Eurographics/ACM SIGGRAPH symposium on Geometry processing, July 08-10, 2004, Nice, France [doi>10.1145/1057432.1057456]
• 23: Robert W. Sumner , Jovan Popović, Deformation transfer for triangle meshes, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 24: Robert W. Sumner , Matthias Zwicker , Craig Gotsman , Jovan Popović, Mesh-based inverse kinematics, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 25: Marek Teichmann , Seth Teller, Assisted articulation of closed polygonal models, ACM SIGGRAPH 98 Conference abstracts and applications, p.254, July 19-24, 1998, Orlando, Florida, United States [doi>10.1145/280953.282217]
• 26: Wolfram von Funck , Holger Theisel , Hans-Peter Seidel, Vector field based shape deformations, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
• 27: Yamane, K., and Nakamura, Y. 2003. Natural motion animation through constraining and deconstraining at will. In IEEE Transactions on Visualization and Computer Graphics, no. 3.
• 28: Yizhou Yu , Kun Zhou , Dong Xu , Xiaohan Shi , Hujun Bao , Baining Guo , Heung-Yeung Shum, Mesh editing with poisson-based gradient field manipulation, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 29: Zayer, R., Rössl, C., Karni, Z., and Seidel, H.-P. 2005. Harmonic guidance for surface deformation. In Eurographics 2005, 601--609.
• 30: Jianmin Zhao , Norman I. Badler, Inverse kinematics positioning using nonlinear programming for highly articulated figures, ACM Transactions on Graphics (TOG), v.13 n.4, p.313-336, Oct. 1994 [doi>10.1145/195826.195827]
• 31: Kun Zhou , Jin Huang , John Snyder , Xinguo Liu , Hujun Bao , Baining Guo , Heung-Yeung Shum, Large mesh deformation using the volumetric graph Laplacian, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 32: Denis Zorin , Peter Schröder , Wim Sweldens, Interactive multiresolution mesh editing, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.259-268, August 1997 [doi>10.1145/258734.258863]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.7 Three-Dimensional Graphics and Realism

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations; Computations on discrete structures

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling

General Terms:
Algorithms, Design

Keywords:
geometry processing, inverse kinematics, mesh deformation, nonlinear optimization