“Variational harmonic maps for space deformation” by Ben-Chen, Weber and Gotsman

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 ω ⊂ Rd to Rd 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.

1. Au, O. K.-C., Tai, C.-L., Chu, H.-K., Cohen-Or, D., and Lee, T.-Y. 2008. Skeleton extraction by mesh contraction. ACM Trans. Graph. 27, 3, 1–10. Google ScholarDigital Library
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.Google ScholarCross Ref
3. Dong, S., Kircher, S., and Garland, M. 2005. Harmonic functions for quadrilateral remeshing of arbitrary manifolds. Computer Aided Geometric Design 22, 5, 392–423. Google ScholarDigital Library
4. Floater, M. S., Kós, G., and Reimers, M. 2005. Mean value coordinates in 3D. Computer Aided Geometric Design 22, 7, 623–631. Google ScholarDigital Library
5. Floater, M. S. and Hormann, K. 2005. Surface parameterization: A tutorial and survey. Advances in Multiresolution for Geometric Modeling 157–186.Google Scholar
6. Huang, J., Shi, X., Liu, X., Zhou, K., Wei, L.-Y., Teng, S.-H., Bao, H., Guo, B., and Shum, H.-Y. 2006. Subspace gradient domain mesh deformation. ACM Trans. Graph. 25, 3, 1126–1134. Google ScholarDigital Library
7. Joshi, P., Meyer, M., DeRose, T., Green, B., and Sanocki, T. 2007. Harmonic coordinates for character articulation. ACM Trans. Graph. 26, 3, 71. Google ScholarDigital Library
8. Ju, T., Schaefer, S., and Warren, J. 2005. Mean value coordinates for closed triangular meshes. ACM Trans. Graph. 24, 3, 561–566. Google ScholarDigital Library
9. Kythe, K., P. 1995. An Introduction to Boundary Element Methods. CRC Press.Google Scholar
10. Lipman, Y., Cohen-Or, D., Gal, R., and Levin, D. 2007. Volume and shape preservation via moving frame manipulation. ACM Trans. Graph. 26, 1, 5. Google ScholarDigital Library
11. Lipman, Y., Kopf, J., Cohen-Or, D., and Levin, D. 2007. GPU assisted positive mean value coordinates for mesh deformations. In Proc. Symposium on Geometry Processing, 117–123. Google ScholarDigital Library
12. Lipman, Y., Levin, D., and Cohen-Or, D. 2008. Green coordinates. ACM Trans. Graph. 27, 3, 1–10. Google ScholarDigital Library
13. Lipman, Y., Sorkine, O., Levin, D., and Cohen-Or, D. 2005. Linear rotation-invariant coordinates for meshes. ACM Trans. Graph. 24, 3, 479–487. Google ScholarDigital Library
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. Google ScholarDigital Library
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. Google ScholarDigital Library
16. Sorkine, O. and Alexa, M. 2007. As-rigid-as-possible surface modeling. In Proc. Symposium on Geometry Processing, 109–116. Google ScholarDigital Library
17. Sorkine, O., and Cohen-Or, D. 2004. Least-squares meshes. In Proc. of Shape Modeling International, 191–199. Google ScholarDigital Library
18. Sorkine, O., Cohen-Or, D., Lipman, Y., Alexa, M., Rössl, C., and Seidel, H. 2004. Laplacian surface editing. In Proc. Symposium on Geometry Processing, 175–184. Google ScholarDigital Library
19. Sumner, R. W., Schmid, J., and Pauly, M. 2007. Embedded deformation for shape manipulation. ACM Trans. Graph. 26, 3, 80. Google ScholarDigital Library
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.Google ScholarCross Ref
21. Weber, O., Sorkine, O., Lipman, Y., and Gotsman, C. 2007. Context-aware skeletal shape deformation. Computer Graphics Forum 26, 3, 265–274.Google ScholarCross Ref
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.Google ScholarCross Ref