“Large mesh deformation using the volumetric graph Laplacian” by Zhou, Huang, Snyder, Liu, Bao, et al. …

  • ©Kun Zhou, Jin Huang, John M. Snyder, Xinguo Liu, Hujun Bao, Baining Guo, and Heung-Yeung Shum




    Large mesh deformation using the volumetric graph Laplacian



    We present a novel technique for large deformations on 3D meshes using the volumetric graph Laplacian. We first construct a graph representing the volume inside the input mesh. The graph need not form a solid meshing of the input mesh’s interior; its edges simply connect nearby points in the volume. This graph’s Laplacian encodes volumetric details as the difference between each point in the graph and the average of its neighbors. Preserving these volumetric details during deformation imposes a volumetric constraint that prevents unnatural changes in volume. We also include in the graph points a short distance outside the mesh to avoid local self-intersections. Volumetric detail preservation is represented by a quadric energy function. Minimizing it preserves details in a least-squares sense, distributing error uniformly over the whole deformed mesh. It can also be combined with conventional constraints involving surface positions, details or smoothness, and efficiently minimized by solving a sparse linear system.We apply this technique in a 2D curve-based deformation system allowing novice users to create pleasing deformations with little effort. A novel application of this system is to apply nonrigid and exaggerated deformations of 2D cartoon characters to 3D meshes. We demonstrate our system’s potential with several examples.


    1. Alexa, M., Cohen-Or. D., and Levin, D. 2000. As-rigid-as-possible shape interpolation. In SIGGRAPH 2000 Conference Proceedings, 157–164. Google ScholarDigital Library
    2. Alexa, M. 2003. Differential coordinates for local mesh morphing and deformation. The Visual Computer 19, 2, 105–114.Google ScholarCross Ref
    3. Barr, A. 1984. Global and local deformations of solid primitives. SIGGRAPH 84 Conference Proceedings 18, 3, 21–30. Google ScholarDigital Library
    4. Bendels, G. H., and Klein, R. 2003. Mesh forging: editing of 3d meshes using implicitly defined occluders. In Symposium on Geometry Processing, ACM SIGGRAPH/Eurographics, 207–217. Google ScholarDigital Library
    5. Botsch, M., and Kobbelt, L. 2003. Multiresolution surface representation based on displacement volumes. Computer Graphics Forum 22, 3.Google ScholarCross Ref
    6. Botsch, M., and Kobbelt, L. 2004. An intuitive framework for real-time freeform-modeling. ACM Trans. on Graphics 23, 3, 630-634. Google ScholarDigital Library
    7. Bregler, C., Loeb, L., Chuang, E., and Deshpande, H. 2002. Turning to the masters: Motion capturing cartoons. In SIGGRAPH 2002 Conference Proceedings, 399-407. Google ScholarDigital Library
    8. Bridson, R., Teran, J., Molino, N., and Fedkiw, R. 2004. Adaptive physics based tetrahedral mesh generation using level sets. Engineering with Computers, to appear. Google ScholarDigital Library
    9. Chung, F. R. K. 1997. Spectral graph theory. CBMS 92, AMS.Google Scholar
    10. Coquillart, S. 1990. Extended free-form deformation: A sculpturing tool for 3d geometric modeling. SIGGRAPH 90 Conference Proceedings 24, 4, 187–196. Google ScholarDigital Library
    11. Cutler, B., Dorsey, J., and McMillan, L. 2004. Simplification and improvement of tetrahedral models for simulation. In Symposium on Geometry Processing, ACM SIGGRAPH/Eurographics, 95–104. Google ScholarDigital Library
    12. Desbrun, M., Meyer, M., Schröder, P., and Barr, A. 1999. Implicit fairing of irregular meshes using diffusion and curvature flow. In SIGGRAPH 99 Conference Proceedings, 317–324. Google ScholarDigital Library
    13. Favreau, L., Reveret, L., Depraz, C., and Cani, M.-P. 2004. Animal gaits from video. In Symposium on Computer Animation. ACM SIGGRAPH / Eurographics. Google ScholarDigital Library
    14. Finkelstein, A., and Salesin, D. H. 1994. Multiresolution curves. In SIGGRAPH 94 Conference Proceedings, 261–268. Google ScholarDigital Library
    15. Fujiwara, K. 1995. Eigenvalues of laplacians on a closed riemannian manifold and its nets. In Proceedings of AMS 123, 2585–2594.Google ScholarCross Ref
    16. Guskov, I., Sweldens, W., and Schröder, P. 1999. Multiresolution signal processing for meshes. In SIGGRAPH 99 Conference Proceedings, 325–334. Google ScholarDigital Library
    17. Hertzmann, A., Oliver, N., Curless, B., and Seitz, S. M. 2002. Curve analogies. In Proceedings of the 13th Eurographics Workshop on Rendering, 233–245. Google ScholarDigital Library
    18. Hirota, G., Maheshwari, R., and Lin, M. C. 1999. Fast volume preserving free form deformation using multi-level optimization. In Proceedings of Solid Modeling and Applications, 234–245. Google ScholarDigital Library
    19. Hsu, W., Hughes, J., and Kaufman, H. 1992. Direct manipulation of free-form deformations. In SIGGRAPH 92 Conference Proceedings, 177–184. Google ScholarDigital Library
    20. Igarashi, T., Matsuoka, S., and Tanaka, H. 1999. Teddy: A sketching interface for 3d freeform design. In SIGGRAPH 99 Conference Proceedings, 409–416. Google ScholarDigital Library
    21. Kho, Y., and Garland, M. 2005. Sketching mesh deformations. In Proceedings of the ACM Symposium on Interactive 3D Graphics. Google ScholarDigital Library
    22. Kobbelt, L., Campagna, S., Vorsatz, J., and Seidel, H.-P. 1998. Interactive multi-resolution modeling on arbitrary meshes. In SIGGRAPH 98 Conference Proceedings, 105–114. Google ScholarDigital Library
    23. Kobbelt, L., Bareuther, T., and Seidel, H.-P. 2000. Multiresolution shape deformations for meshes with dynamic vertex connectivity. Computer Graphics Forum 19, 3, 249–260.Google ScholarCross Ref
    24. 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, IEEE Computer Society Press, 181–190. Google ScholarDigital Library
    25. MacCracken, R., and Joy, K. 1996. Free-form deformations with lattices of arbitrary topology. In SIGGRAPH 96 Conference Proceedings, 181–188. Google ScholarDigital Library
    26. Meyer, M., Desbrun, M., Schröder, P., and Barr, A. 2002. Discrete differential-geometry operators for triangulated 2-manifolds. In Proc. VisMath.Google Scholar
    27. Milliron, T., Jensen, R., Barzel, R., and Finkelstein, A. 2002. A framework for geometric warps and deformations. ACM Trans. Graphics 21, 1, 20–51. Google ScholarDigital Library
    28. Owen, S. J. 1998. A survey fo unstructured mesh generation technology. In 7th International Mehsing Roundtable, 239–267.Google Scholar
    29. Rappoport, A., Sheffer, A., and Bercovier, M. 1995. Volume preserving free-form solid. In Proceedings of Solid modeling and applications, 361–372. Google ScholarDigital Library
    30. Sederberg, T., and Parry, S. 1986. Free-form deformation of solid geometric models. SIGGRAPH 86 Conference Proceedings 20, 4, 151–160. Google ScholarDigital Library
    31. Sheffer, A., and Kraevoy, V. 2004. Pyramid coordinates for morphing and deformation. In Proceedings of 3DPVT. Google ScholarDigital Library
    32. Shewchuk, J. R. 1998. Tetrahedral mesh generation by delaunay refinement. In Proceedings of the 14th Annual Symposium on Computational Geometry, 86–95. Google ScholarDigital Library
    33. Singh, K., and Fiume, E. 1998. Wires: A geometric deformation technique. In SIGGRAPH 98 Conference Proceedings, 405–414. Google ScholarDigital Library
    34. Sorkine, O., Lipman, Y., Cohen-Or, D., Alexa, M., Rössl, C., and Seidel, H.-P. 2004. Laplacian surface editing. In Symposium on Geometry Processing, ACM SIGGRAPH / Eurographics, 179–188. Google ScholarDigital Library
    35. Sumner, R. W., and Popović, J. 2004. Deformation transfer for triangle meshes. ACM Trans. on Graphics 23, 3, 399–405. Google ScholarDigital Library
    36. Taubin, G. 1995. A signal processing approach to fair surface design. In SIGGRAPH 95 Conference Proceedings, 351–358. Google ScholarDigital Library
    37. Welch, W., and Witkin, A. 1994. Free-form shape design using triangulated surfaces. In SIGGRAPH 94 Conference Proceedings, 247–256. Google ScholarDigital Library
    38. 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. on Graphics 23, 3, 644–651. Google ScholarDigital Library
    39. Zelinka, S., and Garland, M. 2004. Mesh modelling with curve analogies. In Proceedings of Pacific Graphics, 94–98. Google ScholarDigital Library
    40. Zorin, D., Schröder, P., and Sweldens, W. 1997. Interactive multiresolution mesh editing. In SIGGRAPH 97 Conference Proceedings, 259–268. Google ScholarDigital Library

ACM Digital Library Publication:

Overview Page: