skip to main content
article

Large mesh deformation using the volumetric graph Laplacian

Published: 01 July 2005 Publication History

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.

Cited By

View all
  • (2025)2D/3D Image morphing technology from traditional to modern: A surveyInformation Fusion10.1016/j.inffus.2024.102913117(102913)Online publication date: May-2025
  • (2024)High-performance nonlinear least square optimization via domain specific languageFifteenth International Conference on Graphics and Image Processing (ICGIP 2023)10.1117/12.3021593(96)Online publication date: 25-Mar-2024
  • (2024)3D Object Reconstruction with Deep LearningIntelligent Information Processing XII10.1007/978-3-031-57919-6_12(161-175)Online publication date: 6-Apr-2024
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Graphics
ACM Transactions on Graphics  Volume 24, Issue 3
July 2005
826 pages
ISSN:0730-0301
EISSN:1557-7368
DOI:10.1145/1073204
Issue’s Table of Contents
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 2005
Published in TOG Volume 24, Issue 3

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. deformation retargeting
  2. differential domain methods
  3. local transform propagation
  4. volumetric details

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)26
  • Downloads (Last 6 weeks)4
Reflects downloads up to 07 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2025)2D/3D Image morphing technology from traditional to modern: A surveyInformation Fusion10.1016/j.inffus.2024.102913117(102913)Online publication date: May-2025
  • (2024)High-performance nonlinear least square optimization via domain specific languageFifteenth International Conference on Graphics and Image Processing (ICGIP 2023)10.1117/12.3021593(96)Online publication date: 25-Mar-2024
  • (2024)3D Object Reconstruction with Deep LearningIntelligent Information Processing XII10.1007/978-3-031-57919-6_12(161-175)Online publication date: 6-Apr-2024
  • (2023)Slippage-Preserving Reshaping of Human-Made 3D ContentACM Transactions on Graphics10.1145/361839142:6(1-18)Online publication date: 5-Dec-2023
  • (2023)Surface deformation technology of large-scale complex components based on LaplaceAdvanced Optical Manufacturing Technologies and Applications 2022; and 2nd International Forum of Young Scientists on Advanced Optical Manufacturing (AOMTA and YSAOM 2022)10.1117/12.2655822(69)Online publication date: 9-Jan-2023
  • (2023)Optimizing Mesh Simplification: A Newton-Based Approach to Quadratic Error Metrics2023 16th International Congress on Image and Signal Processing, BioMedical Engineering and Informatics (CISP-BMEI)10.1109/CISP-BMEI60920.2023.10373281(1-7)Online publication date: 28-Oct-2023
  • (2023)Modeling of human muscle and its deformationComputer Methods in Biomechanics and Biomedical Engineering10.1080/10255842.2023.218616027:3(365-377)Online publication date: 7-Mar-2023
  • (2023)Assessing geometrical uncertainties in geological interface models using Markov chain Monte Carlo sampling via abstract graphTectonophysics10.1016/j.tecto.2023.230032864(230032)Online publication date: Oct-2023
  • (2022)Reduced representation of deformation fields for effective non-rigid shape matchingProceedings of the 36th International Conference on Neural Information Processing Systems10.5555/3600270.3601026(10405-10420)Online publication date: 28-Nov-2022
  • (2022)Real-Time Ray-Traced Soft Shadows of Environmental Lighting by Conical Ray CullingProceedings of the ACM on Computer Graphics and Interactive Techniques10.1145/35226175:1(1-15)Online publication date: 4-May-2022
  • Show More Cited By

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media