Large mesh deformation using the volumetric graph Laplacian

ABSTRACT

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.

References

1. Alexa, M., Cohen-Or. D., and Levin, D. 2000. As-rigid-as-possible shape interpolation. In SIGGRAPH 2000 Conference Proceedings, 157--164.
2. Alexa, M. 2003. Differential coordinates for local mesh morphing and deformation. The Visual Computer 19, 2, 105--114.
3. Barr, A. 1984. Global and local deformations of solid primitives. SIGGRAPH 84 Conference Proceedings 18, 3, 21--30.
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.
5. Botsch, M., and Kobbelt, L. 2003. Multiresolution surface representation based on displacement volumes. Computer Graphics Forum 22, 3.
6. Botsch, M., and Kobbelt, L. 2004. An intuitive framework for real-time freeform-modeling. ACM Trans. on Graphics 23, 3, 630-634.
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.
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.
9. Chung, F. R. K. 1997. Spectral graph theory. CBMS 92, AMS.
10. Coquillart, S. 1990. Extended free-form deformation: A sculpturing tool for 3d geometric modeling. SIGGRAPH 90 Conference Proceedings 24, 4, 187--196.
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.
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.
13. Favreau, L., Reveret, L., Depraz, C., and Cani, M.-P. 2004. Animal gaits from video. In Symposium on Computer Animation. ACM SIGGRAPH / Eurographics.
14. Finkelstein, A., and Salesin, D. H. 1994. Multiresolution curves. In SIGGRAPH 94 Conference Proceedings, 261--268.
15. Fujiwara, K. 1995. Eigenvalues of laplacians on a closed riemannian manifold and its nets. In Proceedings of AMS 123, 2585--2594.
16. Guskov, I., Sweldens, W., and Schröder, P. 1999. Multiresolution signal processing for meshes. In SIGGRAPH 99 Conference Proceedings, 325--334.
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.
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.
19. Hsu, W., Hughes, J., and Kaufman, H. 1992. Direct manipulation of free-form deformations. In SIGGRAPH 92 Conference Proceedings, 177--184.
20. Igarashi, T., Matsuoka, S., and Tanaka, H. 1999. Teddy: A sketching interface for 3d freeform design. In SIGGRAPH 99 Conference Proceedings, 409--416.
21. Kho, Y., and Garland, M. 2005. Sketching mesh deformations. In Proceedings of the ACM Symposium on Interactive 3D Graphics.
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.
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.
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.
25. MacCracken, R., and Joy, K. 1996. Free-form deformations with lattices of arbitrary topology. In SIGGRAPH 96 Conference Proceedings, 181--188.
26. Meyer, M., Desbrun, M., Schröder, P., and Barr, A. 2002. Discrete differential-geometry operators for triangulated 2-manifolds. In Proc. VisMath.
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.
28. Owen, S. J. 1998. A survey fo unstructured mesh generation technology. In 7th International Mehsing Roundtable, 239--267.
29. Rappoport, A., Sheffer, A., and Bercovier, M. 1995. Volume preserving free-form solid. In Proceedings of Solid modeling and applications, 361--372.
30. Sederberg, T., and Parry, S. 1986. Free-form deformation of solid geometric models. SIGGRAPH 86 Conference Proceedings 20, 4, 151--160.
31. Sheffer, A., and Kraevoy, V. 2004. Pyramid coordinates for morphing and deformation. In Proceedings of 3DPVT.
32. Shewchuk, J. R. 1998. Tetrahedral mesh generation by delaunay refinement. In Proceedings of the 14th Annual Symposium on Computational Geometry, 86--95.
33. Singh, K., and Fiume, E. 1998. Wires: A geometric deformation technique. In SIGGRAPH 98 Conference Proceedings, 405--414.
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.
35. Sumner, R. W., and Popović, J. 2004. Deformation transfer for triangle meshes. ACM Trans. on Graphics 23, 3, 399--405.
36. Taubin, G. 1995. A signal processing approach to fair surface design. In SIGGRAPH 95 Conference Proceedings, 351--358.
37. Welch, W., and Witkin, A. 1994. Free-form shape design using triangulated surfaces. In SIGGRAPH 94 Conference Proceedings, 247--256.
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.
39. Zelinka, S., and Garland, M. 2004. Mesh modelling with curve analogies. In Proceedings of Pacific Graphics, 94--98.
40. Zorin, D., Schröder, P., and Sweldens, W. 1997. Interactive multiresolution mesh editing. In SIGGRAPH 97 Conference Proceedings, 259--268.

Index Terms

• Computing methodologies

  • Artificial intelligence

    • Computer vision

      • Computer vision representations

        • Shape representations

  • Symbolic and algebraic manipulation

    • Symbolic and algebraic algorithms

      • Linear algebra algorithms

• Mathematics of computing

  • Discrete mathematics

    • Graph theory

      • Graph algorithms

  • Mathematical analysis

    • Numerical analysis

      • Computations on matrices