Variational harmonic maps for space deformation

ABSTRACT

A space deformation is a mapping from a source region to a target region within Euclidean space, which best satisfies some userspecified constraints. It can be used to deform shapes embedded in the ambient space and represented in various forms -- polygon meshes, point clouds or volumetric data. For a space deformation method to be useful, it should possess some natural properties: e.g. detail preservation, smoothness and intuitive control. A harmonic map from a domain ω ⊂ R^d to R^d is a mapping whose d components are harmonic functions. Harmonic mappings are smooth and regular, and if their components are coupled in some special way, the mapping can be detail-preserving, making it a natural choice for space deformation applications. The challenge is to find a harmonic mapping of the domain, which will satisfy constraints specified by the user, yet also be detail-preserving, and intuitive to control. We generate harmonic mappings as a linear combination of a set of harmonic basis functions, which have a closed-form expression when the source region boundary is piecewise linear. This is done by defining an energy functional of the mapping, and minimizing it within the linear span of these basis functions. The resulting mapping is harmonic, and a natural "As-Rigid-As-Possible" deformation of the source region. Unlike other space deformation methods, our approach does not require an explicit discretization of the domain. It is shown to be much more efficient, yet generate comparable deformations to state-of-the-art methods. We describe an optimization algorithm to minimize the deformation energy, which is robust, provably convergent, and easy to implement.

REFERENCES

• 1: Oscar Kin-Chung Au , Chiew-Lan Tai , Hung-Kuo Chu , Daniel Cohen-Or , Tong-Yee Lee, Skeleton extraction by mesh contraction, ACM Transactions on Graphics (TOG), v.27 n.3, August 2008
• 2: Botsch, M., Pauly, M., Wicke, M., and Gross, M. 2007. Adaptive space deformations based on rigid cells. Computer Graphics Forum 26, 3, 339--347.
• 3: S. Dong , S. Kircher , M. Garland, Harmonic functions for quadrilateral remeshing of arbitrary manifolds, Computer Aided Geometric Design, v.22 n.5, p.392-423, July 2005 [doi>10.1016/j.cagd.2005.04.004]
• 4: 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]
• 5: Floater, M. S. and Hormann, K. 2005. Surface parameterization: A tutorial and survey. Advances in Multiresolution for Geometric Modeling 157--186.
• 6: 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
• 7: Pushkar Joshi , Mark Meyer , Tony DeRose , Brian Green , Tom Sanocki, Harmonic coordinates for character articulation, ACM Transactions on Graphics (TOG), v.26 n.3, July 2007
• 8: Tao Ju , Scott Schaefer , Joe Warren, Mean value coordinates for closed triangular meshes, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 9: Kythe, K., P. 1995. An Introduction to Boundary Element Methods. CRC Press.
• 10: 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]
• 11: Yaron Lipman , Johannes Kopf , Daniel Cohen-Or , David Levin, GPU-assisted positive mean value coordinates for mesh deformations, Proceedings of the fifth Eurographics symposium on Geometry processing, July 04-06, 2007, Barcelona, Spain
• 12: Yaron Lipman , David Levin , Daniel Cohen-Or, Green Coordinates, ACM Transactions on Graphics (TOG), v.27 n.3, August 2008
• 13: 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
• 14: Liu, L., Zhang, L., Xu, Y., Gotsman, C., and Gortler, S. J. A local/global approach to mesh parameterization. 2008. Computer Graphics Forum 27, 5, 1495--1504.
• 15: Martin, S., Kaufmann, P., Botsch, M., Wicke, M., and Gross, M. Polyhedral finite elements using harmonic basis functions. 2008. Computer Graphics Forum 27, 5, 1521--1529.
• 16: Olga Sorkine , Marc Alexa, As-rigid-as-possible surface modeling, Proceedings of the fifth Eurographics symposium on Geometry processing, July 04-06, 2007, Barcelona, Spain
• 17: Least-Squares Meshes, Proceedings of the Shape Modeling International 2004, p.191-199, June 07-09, 2004 [doi>10.1109/SMI.2004.38]
• 18: 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]
• 19: Robert W. Sumner , Johannes Schmid , Mark Pauly, Embedded deformation for shape manipulation, ACM Transactions on Graphics (TOG), v.26 n.3, July 2007
• 20: Urago, M. 2000. Analytical integrals of fundamental solution of three-dimensional Laplace equation and their gradients. In Trans. of the Japan Soc. of Mech. Eng. 66, 642, 254--261.
• 21: Weber, O., Sorkine, O., Lipman, Y., and Gotsman, C. 2007. Context-aware skeletal shape deformation. Computer Graphics Forum 26, 3, 265--274.
• 22: Weber, O., Ben-Chen, M., and Gotsman, C. 2009. Complex barycentric coordinates with applications to planar shape deformation. Computer Graphics Forum 28, 2, 587--597.

INDEX TERMS

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

Keywords:
harmonic maps, shape editing, space deformation