“Linear subspace design for real-time shape deformation”

  • ©Yu Wang, Alec Jacobson, Jernej Barbic, and Ladislav Kavan




    Linear subspace design for real-time shape deformation

Session/Category Title: Simsquishal Geometry




    We propose a method to design linear deformation subspaces, unifying linear blend skinning and generalized barycentric coordinates. Deformation subspaces cut down the time complexity of variational shape deformation methods and physics-based animation (reduced-order physics). Our subspaces feature many desirable properties: interpolation, smoothness, shape-awareness, locality, and both constant and linear precision. We achieve these by minimizing a quadratic deformation energy, built via a discrete Laplacian inducing linear precision on the domain boundary. Our main advantage is speed: subspace bases are solutions to a sparse linear system, computed interactively even for generously tessellated domains. Users may seamlessly switch between applying transformations at handles and editing the subspace by adding, removing or relocating control handles. The combination of fast computation and good properties means that designing the right subspace is now just as creative as manipulating handles. This paradigm shift in handle-based deformation opens new opportunities to explore the space of shape deformations.


    1. Baran, I., and Popović, J. 2007. Automatic rigging and animation of 3D characters. ACM Trans. Graph. 26, 3, 72:1–72:8. Google ScholarDigital Library
    2. Barbič, J., and James, D. L. 2005. Real-time subspace integration for St. Venant-Kirchhoff deformable models. ACM Trans. on Graph. 24, 3 (Aug.), 982–990. Google ScholarDigital Library
    3. Ben-Chen, M., Weber, O., and Gotsman, C. 2009. Variational harmonic maps for space deformation. ACM Trans. Graph. 28, 3, 34:1–34:11. Google ScholarDigital Library
    4. Bobach, T., Hering-Bertram, M., and Umlauf, G. 2006. Comparison of voronoi based scattered data interpolation schemes. In Proceedings of International Conference on Visualization, Imaging and Image Processing, 342–349.Google Scholar
    5. Bookstein, F. L. 1989. Principal warps: Thin-plate splines and the decomposition of deformations. IEEE Transactions on pattern analysis and machine intelligence 11, 6, 567–585. Google ScholarDigital Library
    6. Botsch, M., and Kobbelt, L. 2004. An intuitive framework for real-time freeform modeling. ACM Trans. Graph. 23, 3. Google ScholarDigital Library
    7. Botsch, M., and Kobbelt, L. 2005. Real-time shape editing using radial basis functions. Comput. Graph. Forum 24.Google Scholar
    8. Botsch, M., and Sorkine, O. 2008. On linear variational surface deformation methods. IEEE Transactions on Visualization and Computer Graphics 14, 1, 213–230. Google ScholarDigital Library
    9. Botsch, M., Pauly, M., Gross, M., and Kobbelt, L. 2006. PriMo: Coupled prisms for intuitive surface modeling. In Proc. SGP, 11–20. Google ScholarDigital Library
    10. Botsch, M., Pauly, M., Wicke, M., and Gross, M. 2007. Adaptive space deformations based on rigid cells. Comput. Graph. Forum 26, 3, 339–347.Google ScholarCross Ref
    11. Chao, I., Pinkall, U., Sanan, P., and Schröder, P. 2010. A simple geometric model for elastic deformations. ACM Trans. Graph. 29, 4 (July), 38:1–38:6. Google ScholarDigital Library
    12. Davis, T. A. 2006. Cholmod: a sparse supernodal Cholesky factorization and modification package, version 3.0. University of Florida.Google Scholar
    13. Desbrun, M., Meyer, M., and Alliez, P. 2002. Intrinsic parameterizations of surface meshes. Comput. Graph. Forum 21, 3, 209–218.Google ScholarCross Ref
    14. Faure, F., Gilles, B., Bousquet, G., and Pai, D. K. 2011. Sparse meshless models of complex deformable solids. ACM Trans. Graph. 30. Google ScholarDigital Library
    15. Finch, M., Snyder, J., and Hoppe, H. 2011. Freeform vector graphics with controlled thin-plate splines. ACM Trans. Graph. 30, 6, 166:1–166:10. Google ScholarDigital Library
    16. Fisher, M., Schröder, P., Desbrun, M., and Hoppe, H. 2007. Design of tangent vector fields. ACM Trans. Graph. 26, 3. Google ScholarDigital Library
    17. Gilles, B., Bousquet, G., Faure, F., and Pai, D. 2011. Frame-based elastic models. ACM Trans. Graph. 30, 2. Google ScholarDigital Library
    18. Harmon, D., and Zorin, D. 2013. Subspace integration with local deformations. ACM Trans. Graph. 32, 4. Google ScholarDigital Library
    19. Hauser, K. K., Shen, C., and O’Brien, J. F. 2003. Interactive deformation using modal analysis with constraints. In Proc. of Graphics Interface, 247–256.Google Scholar
    20. Hildebrandt, K., Schulz, C., Tycowicz, C. V., and Polthier, K. 2011. Interactive surface modeling using modal analysis. ACM Trans. Graph. 30, 5, 119:1–119:11. Google ScholarDigital Library
    21. Hormann, K., and Sukumar, N. 2008. Maximum entropy coordinates for arbitrary polytopes. Comput. Graph. Forum 27, 5. Google ScholarDigital Library
    22. 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
    23. Igarashi, T., Moscovich, T., and Hughes, J. F. 2005. As-rigid-as-possible shape manipulation. ACM Trans. Graph. 24, 3. Google ScholarDigital Library
    24. Jacobson, A., Tosun, E., Sorkine, O., and Zorin, D. 2010. Mixed finite elements for variational surface modeling. In Proc. SGP, 1565–1574.Google Scholar
    25. Jacobson, A., Baran, I., Popović, J., and Sorkine, O. 2011. Bounded biharmonic weights for real-time deformation. ACM Trans. Graph. 30, 4, 78:1–78:8. Google ScholarDigital Library
    26. Jacobson, A., Baran, I., Kavan, L., Popović, J., and Sorkine, O. 2012. Fast automatic skinning transformations. ACM Trans. Graph. 31, 4. Google ScholarDigital Library
    27. Jacobson, A., Weinkauf, T., and Sorkine, O. 2012. Smooth shape-aware functions with controlled extrema. In Proc. SGP. Google ScholarDigital Library
    28. Jacobson, A., Kavan, L.,, and Sorkine-Hornung, O. 2013. Robust inside-outside segmentation using generalized winding numbers. ACM Trans. Graph. 32, 4, 33:1–33:12. Google ScholarDigital Library
    29. Jacobson, A., Deng, Z., Kavan, L., and Lewis, J. 2014. Skinning: Real-time shape deformation. In ACM SIGGRAPH 2014 Courses. Google ScholarDigital Library
    30. Jacobson, A. 2013. Algorithms and Interfaces for Real-Time Deformation of 2D and 3D Shapes. PhD thesis, ETH Zurich.Google Scholar
    31. James, D. L., and Pai, D. K. 2002. DyRT: Dynamic Response Textures for Real Time Deformation Simulation With Graphics Hardware. ACM Trans. Graph. 21, 3. Google ScholarDigital Library
    32. 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
    33. Ju, T., Schaefer, S., and Warren, J. 2005. Mean value coordinates for closed triangular meshes. ACM Trans. Graph. 24, 3. Google ScholarDigital Library
    34. Kavan, L., Sloan, P., and O’Sullivan, C. 2010. Fast and efficient skinning of animated meshes. Comput. Graph. Forum 29, 2, 327–336.Google ScholarCross Ref
    35. Kavan, L., Gerszewski, D., Bargteil, A., and Sloan, P.-P. 2011. Physics-inspired upsampling for cloth simulation in games. ACM Trans. Graph. 30, 4, 93:1–93:9. Google ScholarDigital Library
    36. Krysl, P., Lall, S., and Marsden, J. E. 2001. Dimensional model reduction in non-linear finite element dynamics of solids and structures. Int. J. for Numerical Methods in Engineering 51.Google Scholar
    37. Langer, T., and Seidel, H.-P. 2008. Higher order barycentric coordinates. Comput. Graph. Forum 27, 2, 459–466.Google ScholarCross Ref
    38. Li, X.-Y., and Hu, S.-M. 2013. Poisson coordinates.Google Scholar
    39. Lipman, Y., Kopf, J., Cohen-Or, D., and Levin, D. 2007. GPU-assisted positive mean value coordinates for mesh deformations. In Proc. SGP, 117–124. Google ScholarDigital Library
    40. Lipman, Y., Rustamov, R., and Funkhouser, T. 2010. Biharmonic distance. ACM Trans. Graph. 29, 3. Google ScholarDigital Library
    41. Liu, L., Zhang, L., Xu, Y., Gotsman, C., and Gortler, S. J. 2008. A local/global approach to mesh parameterization. Comput. Graph. Forum 27, 5. Google ScholarDigital Library
    42. Magnenat-Thalmann, N., Laperrière, R., and Thalmann, D. 1988. Joint-dependent local deformations for hand animation and object grasping. In Graphics Interface, 26–33. Google ScholarDigital Library
    43. Martin, S., Thomaszewski, B., Grinspun, E., and Gross, M. 2011. Example-based elastic materials. ACM Trans. Graph. 30, 4 (July), 72:1–72:8. Google ScholarDigital Library
    44. Merry, B., Marais, P., and Gain, J. 2006. Animation space: A truly linear framework for character animation. ACM Trans. Graph. 25, 4, 1400–1423. Google ScholarDigital Library
    45. Müller, M., Heidelberger, B., Teschner, M., and Gross, M. 2005. Meshless deformations based on shape matching. ACM Trans. Graph. 24 (July), 471–478. Google ScholarDigital Library
    46. Neumann, T., Varanasi, K., Wenger, S., Wacker, M., Magnor, M., and Theobalt, C. 2013. Sparse localized deformation components. ACM Trans. Graph. 32, 6. Google ScholarDigital Library
    47. Nieto, J. R., and Susin, A. 2013. Cage based deformations: a survey. In Deformation Models. Springer, 75–99.Google Scholar
    48. Ozolinš, V., Lai, R., Caflisch, R., and Osher, S. 2013. Compressed plane waves-compactly supported multiresolution basis for the laplace operator. Proc. of NAS.Google Scholar
    49. Sacht, L., Jacobson, A., Panozzo, D., Schüller, C., and Sorkine-Hornung, O. 2013. Consistent volumetric discretizations inside self-intersecting surfaces. vol. 32, 147–156. Google ScholarDigital Library
    50. Sederberg, T. W., and Parry, S. R. 1986. Free-form deformation of solid geometric models. In Proc. SIGGRAPH, 151–160. Google ScholarDigital Library
    51. Sin, F. S., Schroeder, D., and Barbič, J. 2013. Vega: Non-linear fem deformable object simulator. In Computer Graphics Forum, vol. 32, Wiley Online Library, 36–48.Google Scholar
    52. Sorkine, O., and Alexa, M. 2007. As-rigid-as-possible surface modeling. In Proc. SGP, 109–116. Google ScholarDigital Library
    53. Sorkine, O., and Cohen-Or, D. 2004. Least-squares meshes. In Proc. SMI, 191–199. Google ScholarDigital Library
    54. Sorkine, O., Lipman, Y., Cohen-Or, D., Alexa, M., Rössl, C., and Seidel, H.-P. 2004. Laplacian surface editing. In Proc. SGP, 179–188. Google ScholarDigital Library
    55. Vallet, B., and Lévy, B. 2008. Spectral geometry processing with manifold harmonics. In Computer Graphics Forum, vol. 27, Wiley Online Library, 251–260.Google Scholar
    56. Wang, X. C., and Phillips, C. 2002. Multi-weight enveloping: least-squares approximation techniques for skin animation. In Proc. SCA, 129–138. Google ScholarDigital Library
    57. Wardetzky, M., Mathur, S., Kälberer, F., and Grinspun, E. 2007. Discrete Laplace operators: no free lunch. In Proc. SGP, 33–37. Google ScholarDigital Library
    58. Weber, O., Ben-Chen, M., Gotsman, C., and Hormann, K. 2011. A complex view of barycentric mappings. Comput. Graph. Forum 30, 5.Google ScholarCross Ref
    59. Xu, H., and Barbič, J. 2014. Signed distance fields for polygon soup meshes. Graphics Interface 2014. Google ScholarDigital Library
    60. Xu, K., Zhang, H., Cohen-Or, D., and Xiong, Y. 2009. Dynamic harmonic fields for surface processing. Computers & Graphics 33, 3, 391–398. Google ScholarDigital Library
    61. Zhang, J., Deng, B., Liu, Z., Patanè, G., Bouaziz, S., Hormann, K., and Liu, L. 2014. Local barycentric coordinates. ACM Trans. Graph. 33. Google ScholarDigital Library

ACM Digital Library Publication:

Overview Page: