“Embedded deformation for shape manipulation” by Sumner, Schmid and Pauly

We present an algorithm that generates natural and intuitive deformations via direct manipulation for a wide range of shape representations and editing scenarios. Our method builds a space deformation represented by a collection of affine transformations organized in a graph structure. One transformation is associated with each graph node and applies a deformation to the nearby space. Positional constraints are specified on the points of an embedded object. As the user manipulates the constraints, a nonlinear minimization problem is solved to find optimal values for the affine transformations. Feature preservation is encoded directly in the objective function by measuring the deviation of each transformation from a true rotation. This algorithm addresses the problem of “embedded deformation” since it deforms space through direct manipulation of objects embedded within it, while preserving the embedded objects’ features. We demonstrate our method by editing meshes, polygon soups, mesh animations, and animated particle systems.

1. Allen, B., Curless, B., and Popović, Z. 2003. The space of human body shapes: Reconstruction and parameterization from range scans. ACM Trans. Graph. 22, 3. Google ScholarDigital Library
2. Barr, A. H. 1984. Global and local deformations of solid primitives. In Proc. of SIGGRAPH. Google ScholarDigital Library
3. Botsch, M., and Kobbelt, L. 2004. An intuitive framework for real-time freeform modeling. ACM Trans. Graph. 23, 3. Google ScholarDigital Library
4. Botsch, M., and Kobbelt, L. 2005. Real-time shape editing using radial basis functions. Computer Graphics Forum 24, 3.Google ScholarCross Ref
5. Botsch, M., and Sorkine, O. 2007. On linear variational surface deformation methods. To appear in IEEE Transaction on Visualization on Computer Graphics. Google ScholarDigital Library
6. Botsch, M., Pauly, M., Gross, M., and Kobbelt, L. 2006. Primo: Coupled prisms for intuitive surface modeling. In Fourth Eurographics Symposium on Geometry Processing. Google ScholarDigital Library
7. Botsch, M., Sumner, R. W., Pauly, M., and Gross, M. 2006. Deformation transfer for detail-preserving surface editing. In Vision, Modeling & Visualization 2006.Google Scholar
8. Coquillart, S. 1990. Extended free-form deformation: A sculpturing tool for 3D geometric modeling. In Proc. of SIGGRAPH. Google ScholarDigital Library
9. Gill, P. E., Murray, W., and Wright, M. H. 1989. Practical Optimization. Academic Press, London.Google Scholar
10. Grassia, F. S. 1998. Practical parameterization of rotations using the exponential map. J. Graph. Tools 3, 3. Google ScholarDigital Library
11. Hsu, W. M., Hughes, J. F., and Kaufman, H. 1992. Direct manipulation of free-form deformations. In Proc. of SIGGRAPH. Google ScholarDigital Library
12. 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. Google ScholarDigital Library
13. Kircher, S., and Garland, M. 2006. Editing arbitrarily deforming surface animations. ACM Trans. Graph. 25, 3. Google ScholarDigital Library
14. Kobbelt, L., Campagna, S., Vorsatz, J., and Seidel, H.-P. 1998. Interactive multi-resolution modeling on arbitrary meshes. In Proc. of SIGGRAPH. Google ScholarDigital Library
15. MacCracken, R., and Joy, K. I. 1996. Free-form deformations with lattices of arbitrary topology. In Proc. of SIGGRAPH. Google ScholarDigital Library
16. Madsen, K., Nielsen, H., and Tingleff, O. 2004. Methods for non-linear least squares problems. Tech. rep., Informatics and Mathematical Modelling, Technical University of Denmark.Google Scholar
17. Mohr, A., and Gleicher, M. 2003. Building efficient, accurate character skins from examples. ACM Trans. Graph. 22, 3. Google ScholarDigital Library
18. Pauly, M., Mitra, N. J., Giesen, J., Gross, M., and Guibas, L. J. 2005. Example-based 3d scan completion. In Third Eurographics Symposium on Geometry Processing. Google ScholarDigital Library
19. Sederberg, T. W., and Parry, S. R. 1988. Free-form deformation of solid geometric models. In Proc. of SIGGRAPH. Google ScholarDigital Library
20. Sheffer, A., and Kraevoy, V. 2004. Pyramid coordinates for morphing and deformation. In Proc. of the 2nd Symposium on 3D Processing, Visualization and Transmission. Google ScholarCross Ref
21. Shi, L., Yu, Y., Bell, N., and Feng, W.-W. 2006. A fast multigrid algorithm for mesh deformation. ACM Trans. Graph. 25, 3. Google ScholarDigital Library
22. Singh, K., and Fiume, E. L. 1998. Wires: A geometric deformation technique. In Proc. of SIGGRAPH. Google ScholarDigital Library
23. Singh, K., and Kokkevis, E. 2000. Skinning characters using surface oriented free-form deformations. In Graphics Interface.Google Scholar
24. Sorkine, O. 2005. Laplacian mesh processing. In State of the Art Reports, Eurographics.Google Scholar
25. Sumner, R. W., and Popović, J. 2004. Deformation transfer for triangle meshes. ACM Trans. Graph. 23, 3. Google ScholarDigital Library
26. Toledo, S., 2003. TAUCS: A library of sparse linear solvers, version 2.2. http://www.tau.ac.il/~stoledo/taucs.Google Scholar
27. Weber, J. 2000. Run-time skin deformation. In Proceedings of the 2000 Game Developers Conference.Google Scholar
28. 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. Google ScholarDigital Library