“Subspace gradient domain mesh deformation” by Huang, Shi, Liu, Zhou, Wei, et al. …

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.

1. Alexa, M. 2003. Differential coordinates for local mesh morphing and deformation. The Visual Computer 19, 2, 105–114.Google ScholarCross Ref
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.Google Scholar
3. Barbic, J., and James, D. 2005. Real-time subspace integration for st. venant-kirchhoff deformable models. ACM Trans. Graph. 24, 3, 982–990. Google ScholarDigital Library
4. Botsch, M., and Kobbelt, L. 2003. Multiresolution surface representation based on displacement volumes. Computer Graphics Forum 22, 3, 483–492.Google ScholarCross Ref
5. Coquillart, S. 1990. Extended free-form deformation: a sculpturing tool for 3d geometric modeling. In SIGGRAPH 90, 187–196. Google ScholarDigital Library
6. Desbrun, M., Meyer, M., Schroder, P., and Barr, A. H. 1999. Implicit fairing of irregular meshes using diffusion and curvature flow. In SIGGRAPH 99, 317–324. Google ScholarDigital Library
7. Floater, M. S., Kos, G., and Reimers, M. 2005. Mean value coordinates in 3d. CAGD 22, 623–631. Google ScholarDigital Library
8. Guskov, I., Sweldens, W., and Schroder, P. 1999. Multiresolution signal processing for meshes. In SIGGRAPH 99, 325–334. Google ScholarDigital Library
9. Hirota, G., Maheshwari, R., and Lin, M. C. 1999. Fast volume-preserving free form deformation using multi-level optimization. In Proceedings of the fifth ACM symposium on Solid modeling and applications, 234–245. Google ScholarDigital Library
10. Hsu, W. M., Hughes, J. F., and Kaufman, H. 1992. Direct manipulation of free-form deformations. In SIGGRAPH 92, 177–184. Google ScholarDigital Library
11. 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
12. Kaporin, I., and Axelsson, O. 1994. On a class of nonlinear equation solvers based on the residual norm reduction over a sequence of affine subspaces. SIAM J. Scientific Computing 16, 1, 228–249. Google ScholarDigital Library
13. Kavan, L., and Zara, J. 2005. Spherical blend skinning: a real-time deformation of articulated models. In Proceedings of the symposium on Interactive 3D graphics and games, 9–16. Google ScholarDigital Library
14. Kobbelt, L., Campagna, S., Vorsatz, J., and Seidel, H.-P. 1998. Interactive multi-resolution modeling on arbitrary meshes. In SIGGRAPH 98, 105–114. Google ScholarDigital Library
15. Kry, P. G., James, D. L., and Pai, D. K. 2002. Eigenskin: real time large deformation character skinning in hardware. In Proceedings of the symposium on Computer animation, 153–159. Google ScholarDigital Library
16. Lander, J. 1998. Skin them bones: Game programming for the web generation. In Game Developer Magazine.Google Scholar
17. Lewis, J. P., Cordner, M., and Fong, N. 2000. Pose space deformation: a unified approach to shape interpolation and skeleton-driven deformation. In SIGGRAPH 2000, 165–172. Google ScholarDigital Library
18. Lipman, Y., Sorkine, O., Cohen-Or, D., Levin, D., Rössl, C., and Seidel, H.-P. 2004. Differential coordinates for interactive mesh editing. In Proceedings of Shape Modeling International, 181–190. Google ScholarDigital Library
19. 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
20. MacCracken, R., and Joy, K. I. 1996. Free-form deformations with lattices of arbitrary topology. In SIGGRAPH 96, 181–188. Google ScholarDigital Library
21. Madsen, K., Nielsen, H., and Tingleff, O. 2004. Optimization with constraints. Tech. rep., Informatics and Mathematical Modelling, Technical University of Denmark.Google Scholar
22. Milliron, T., Jensen, R. J., Barzel, R., and Finkelstein, A. 2002. A framework for geometric warps and deformations. ACM Trans. Graph. 21, 1, 20–51. Google ScholarDigital Library
23. Nealen, A., Sorkine, O., Alexa, M., and Cohen-Or, D. 2005. A sketch-based interface for detail-preserving mesh editing. ACM Trans. Graph. 24, 3, 1142–1147. Google ScholarDigital Library
24. Rappaport, A., Sheffer, A., and Bercovier, M. 1996. Volume-preserving free-form solids. IEEE Transactions on Visualization and Computer Graphics 2, 1 (Mar.), 19–27. Google ScholarDigital Library
25. Sander, P. V., Gu, X., Gortler, S. J., Hoppe, H., and Snyder, J. 2000. Silhouette clipping. In SIGGRAPH 2000, 327–334. Google ScholarDigital Library
26. Sederberg, T. W., and Parry, S. R. 1986. Free-form deformation of solid geometric models. In SIGGRAPH 86, 151–160. Google ScholarDigital Library
27. Sheffer, A., and Kraevoy, V. 2004. Pyramid coordinates for morphing and deformation. In Proceedings of 3DPVT ’04, 68–75. Google ScholarCross Ref
28. Shewchuk, J. R. 2002. What is a good linear element? interpolation, conditioning, and quality measures. In 11th International Meshing Roundtable, 115–126.Google Scholar
29. Singh, K., and Fiume, E. 1998. Wires: a geometric deformation technique. In SIGGRAPH 98, 405–414. Google ScholarDigital Library
30. Sorkine, O., Cohen-Or, D., Lipman, Y., Alexa, M., Rössl, C., and Seidel, H.-P. 2004. Laplacian surface editing. In Proceedings of the symposium on Geometry processing, 175–184. Google ScholarDigital Library
31. Steihaug, T. 1995. An inexact gauss-newton approach to mildly nonlinear problems. Tech. rep., Dept. of Mathematics, University of Linkoping.Google Scholar
32. Sumner, R. W., Zwicker, M., Gotsman, C., and Popovic, J. 2005. Mesh-based inverse kinematics. ACM Trans. Graph. 24, 3, 488–495. Google ScholarDigital Library
33. Wilhelms, J., and Gelder, A. V. 1997. Anatomically based modeling. In SIGGRAPH 97, 173–180. Google ScholarDigital Library
34. Yu, Y., Zhou, K., Xu, D., Shi, X., Bao, H., Guo, B., and Shum, H.-Y. 2004. Mesh editing with poisson-based gradient field manipulation. ACM Trans. Graph. 23, 3, 644–651. Google ScholarDigital Library
35. Zhou, K., Huang, J., Snyder, J., Liu, X., Bao, H., Guo, B., and Shum, H.-Y. 2005. Large mesh deformation using the volumetric graph laplacian. ACM Trans. Graph. 24, 3, 496–503. Google ScholarDigital Library
36. Zorin, D., Schroder, P., and Sweldens, W. 1997. Interactive multiresolution mesh editing. In SIGGRAPH 97, 259–268. Google ScholarDigital Library