A fast multigrid algorithm for mesh deformation
- 1 July 2006
- journal article
- conference paper
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Graphics
- Vol. 25 (3), 1108-1117
- https://doi.org/10.1145/1141911.1142001
Abstract
In this paper, we present a multigrid technique for efficiently deforming large surface and volume meshes. We show that a previous least-squares formulation for distortion minimization reduces to a Laplacian system on a general graph structure for which we derive an analytic expression. We then describe an efficient multigrid algorithm for solving the relevant equations. Here we develop novel prolongation and restriction operators used in the multigrid cycles. Combined with a simple but effective graph coarsening strategy, our algorithm can outperform other multigrid solvers and the factorization stage of direct solvers in both time and memory costs for large meshes. It is demonstrated that our solver can trade off accuracy for speed to achieve greater interactivity, which is attractive for manipulating large meshes. Our multigrid solver is particularly well suited for a mesh editing environment which does not permit extensive precomputation. Experimental evidence of these advantages is provided on a number of meshes with a wide range of size. With our mesh deformation solver, we also successfully demonstrate that visually appealing mesh animations can be generated from both motion capture data and a single base mesh even when they are inconsistent. Copyright © 2006 by the Association for Computing Machinery, Inc.link_to_subscribed_fulltexKeywords
This publication has 22 references indexed in Scilit:
- Real‐Time Shape Editing using Radial Basis FunctionsComputer Graphics Forum, 2005
- Harmonic Guidance for Surface DeformationComputer Graphics Forum, 2005
- Large mesh deformation using the volumetric graph LaplacianACM Transactions on Graphics, 2005
- Mesh-based inverse kinematicsACM Transactions on Graphics, 2005
- Linear rotation-invariant coordinates for meshesACM Transactions on Graphics, 2005
- Mesh editing with poisson-based gradient field manipulationACM Transactions on Graphics, 2004
- Deformation transfer for triangle meshesACM Transactions on Graphics, 2004
- Fair morse functions for extracting the topological structure of a surface meshACM Transactions on Graphics, 2004
- Sparse matrix solvers on the GPUACM Transactions on Graphics, 2003
- Free-form deformation of solid geometric modelsACM SIGGRAPH Computer Graphics, 1986