Subspace gradient domain mesh deformation

ABSTRACT

In this paper we present a general framework for performing constrained mesh deformation tasks with gradient domain techniques. We present a gradient domain technique that works well with a wide variety of linear and nonlinear constraints. The constraints we introduce include the nonlinear volume constraint for volume preservation, the nonlinear skeleton constraint for maintaining the rigidity of limb segments of articulated figures, and the projection constraint for easy manipulation of the mesh without having to frequently switch between multiple viewpoints. To handle nonlinear constraints, we cast mesh deformation as a nonlinear energy minimization problem and solve the problem using an iterative algorithm. The main challenges in solving this nonlinear problem are the slow convergence and numerical instability of the iterative solver. To address these issues, we develop a subspace technique that builds a coarse control mesh around the original mesh and projects the deformation energy and constraints onto the control mesh vertices using the mean value interpolation. The energy minimization is then carried out in the subspace formed by the control mesh vertices. Running in this subspace, our energy minimization solver is both fast and stable and it provides interactive responses. We demonstrate our deformation constraints and subspace deformation technique with a variety of constrained deformation examples.

REFERENCES

• 1: Alexa, M. 2003. Differential coordinates for local mesh morphing and deformation. The Visual Computer 19, 2, 105--114.
• 2: Au, O. K.-C., Tai, C.-L., Liu, L., and Fu, H. 2005. Mesh editing with curvature flow laplacian operator. Tech. rep., Computer Science Technical Report, HKUST-CS05-10.
• 3: Jernej Barbič , Doug L. James, Real-Time subspace integration for St. Venant-Kirchhoff deformable models, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 4: Botsch, M., and Kobbelt, L. 2003. Multiresolution surface representation based on displacement volumes. Computer Graphics Forum 22, 3, 483--492.
• 5: Sabine Coquillart, Extended free-form deformation: a sculpturing tool for 3D geometric modeling, Proceedings of the 17th annual conference on Computer graphics and interactive techniques, p.187-196, September 1990, Dallas, TX, USA
• 6: Mathieu Desbrun , Mark Meyer , Peter Schröder , Alan H. Barr, Implicit fairing of irregular meshes using diffusion and curvature flow, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.317-324, July 1999 [doi>10.1145/311535.311576]
• 7: Michael S. Floater , Géza Kós , Martin Reimers, Mean value coordinates in 3D, Computer Aided Geometric Design, v.22 n.7, p.623-631, October 2005 [doi>10.1016/j.cagd.2005.06.004]
• 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: Gentaro Hirota , Renee Maheshwari , Ming C. Lin, Fast volume-preserving free form deformation using multi-level optimization, Proceedings of the fifth ACM symposium on Solid modeling and applications, p.234-245, June 08-11, 1999, Ann Arbor, Michigan, United States [doi>10.1145/304012.304036]
• 10: William M. Hsu , John F. Hughes , Henry Kaufman, Direct manipulation of free-form deformations, Proceedings of the 19th annual conference on Computer graphics and interactive techniques, p.177-184, July 1992
• 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: Igor E. Kaporin , Owe Axelsson, On a class of nonlinear equation solvers based on the residual norm reduction over a sequence of affine subspaces, SIAM Journal on Scientific Computing, v.16 n.1, p.228-249, Jan. 1995 [doi>10.1137/0916015]
• 13: Ladislav Kavan , Jiří Žára, Spherical blend skinning: a real-time deformation of articulated models, Proceedings of the 2005 symposium on Interactive 3D graphics and games, April 03-06, 2005, Washington, District of Columbia [doi>10.1145/1053427.1053429]
• 14: 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]
• 15: Paul G. Kry , Doug L. James , Dinesh K. Pai, EigenSkin: real time large deformation character skinning in hardware, Proceedings of the 2002 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 21-22, 2002, San Antonio, Texas [doi>10.1145/545261.545286]
• 16: Lander, J. 1998. Skin them bones: Game programming for the web generation. In Game Developer Magazine.
• 17: 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]
• 18: Differential Coordinates for Interactive Mesh Editing, Proceedings of the Shape Modeling International 2004 (SMI'04), p.181-190, June 07-09, 2004 [doi>10.1109/SMI.2004.30]
• 19: 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
• 20: Ron MacCracken , Kenneth I. Joy, Free-form deformations with lattices of arbitrary topology, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.181-188, August 1996 [doi>10.1145/237170.237247]
• 21: Madsen, K., Nielsen, H., and Tingleff, O. 2004. Optimization with constraints. Tech. rep., Informatics and Mathematical Modelling, Technical University of Denmark.
• 22: Tim Milliron , Robert J. Jensen , Ronen Barzel , Adam Finkelstein, A framework for geometric warps and deformations, ACM Transactions on Graphics (TOG), v.21 n.1, p.20-51, January 2002 [doi>10.1145/504789.504791]
• 23: 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
• 24: Ari Rappoport , Alla Sheffer , Michel Bercovier, Volume-Preserving Free-Form Solids, IEEE Transactions on Visualization and Computer Graphics, v.2 n.1, p.19-27, March 1996 [doi>10.1109/2945.489383]
• 25: Pedro V. Sander , Xianfeng Gu , Steven J. Gortler , Hugues Hoppe , John Snyder, Silhouette clipping, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.327-334, July 2000 [doi>10.1145/344779.344935]
• 26: Thomas W. Sederberg , Scott R. Parry, Free-form deformation of solid geometric models, Proceedings of the 13th annual conference on Computer graphics and interactive techniques, p.151-160, August 1986
• 27: Alla Sheffer , Vladislav Kraevoy, Pyramid Coordinates for Morphing and Deformation, Proceedings of the 3D Data Processing, Visualization, and Transmission, 2nd International Symposium on (3DPVT'04), p.68-75, September 06-09, 2004 [doi>10.1109/3DPVT.2004.99]
• 28: Shewchuk, J. R. 2002. What is a good linear element? interpolation, conditioning, and quality measures. In 11th International Meshing Roundtable, 115--126.
• 29: Karan Singh , Eugene Fiume, Wires: a geometric deformation technique, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.405-414, July 1998 [doi>10.1145/280814.280946]
• 30: 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]
• 31: Steihaug, T. 1995. An inexact gauss-newton approach to mildly nonlinear problems. Tech. rep., Dept. of Mathematics, University of Linkoping.
• 32: Robert W. Sumner , Matthias Zwicker , Craig Gotsman , Jovan Popović, Mesh-based inverse kinematics, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 33: Jane Wilhelms , Allen Van Gelder, Anatomically based modeling, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.173-180, August 1997 [doi>10.1145/258734.258833]
• 34: 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
• 35: 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
• 36: 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.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Nonlinear programming; Constrained optimization; Gradient methods

General Terms:
Algorithms, Design, Theory

Keywords:
nonlinear constraints, projection constraint, skeletal control, volume preservation