A fast multigrid algorithm for mesh deformation

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.

REFERENCES

• 1: Burak Aksoylu , Andrei Khodakovsky , Peter Schröder, Multilevel Solvers for Unstructured Surface Meshes, SIAM Journal on Scientific Computing, v.26 n.4, p.1146-1165, 2005 [doi>10.1137/S1064827503430138]
• 2: Marc Alexa , Daniel Cohen-Or , David Levin, As-rigid-as-possible shape interpolation, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.157-164, July 2000 [doi>10.1145/344779.344859]
• 3: Alexa, M. 2003. Differential coordinates for local mesh morphing and deformation. The Visual Computer 19, 2, 105--114.
• 4: Jeff Bolz , Ian Farmer , Eitan Grinspun , Peter Schröoder, Sparse matrix solvers on the GPU: conjugate gradients and multigrid, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 5: Botsch, M., and Kobbelt, L. 2005. Real-time shape editing using radial basis functions. Computer Graphics Forum (Eurographics 2005) 24, 3, 611--621.
• 6: Botsch, M., Bommes, D., and Kobbelt, L. 2005. Efficient linear system solvers for mesh processing. In Proc. of IMA conference on Mathematics of Surfaces, 62--83.
• 7: U. Clarenz , M. Griebel , M. Rumpf , M. A. Schweitzer , A. Telea, Feature sensitive multiscale editing on surfaces, The Visual Computer: International Journal of Computer Graphics, v.20 n.5, p.329-343, July 2004 [doi>10.1007/s00371-004-0245-3]
• 8: Davis, T. A. 2005. Umfpack version 4.4 user guide. Tech. Rep. TR-04-003, University of Florida.
• 9: Davis, T. A. 2006. User guide for cholmod. Tech. rep., University of Florida.
• 10: James W. Demmel , Stanley C. Eisenstat , John R. Gilbert , Xiaoye S. Li , Joseph W. H. Liu, A Supernodal Approach to Sparse Partial Pivoting, SIAM Journal on Matrix Analysis and Applications, v.20 n.3, p.720-755, July 1999 [doi>10.1137/S0895479895291765]
• 11: Nolan Goodnight , Cliff Woolley , Gregory Lewin , David Luebke , Greg Humphreys, A multigrid solver for boundary value problems using programmable graphics hardware, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, July 26-27, 2003, San Diego, California
• 12: Gould, N. I. M., Hu, Y., and Scott, J. A. 2005. A numerical evaluation of sparse direct solvers for the solution of large sparse, symmetric linear systems of equations. Tech. Rep. RAL-TR-2005-005, RAL Technical Reports.
• 13: Grady, L., and Tasdizen, T. 2005. A geometric multigrid approach to solving the 2d inhomogeneous Laplace equation with internal Dirichlet boundary conditions. In International Conference on Image Processing.
• 14: Igor Guskov , Wim Sweldens , Peter Schröder, Multiresolution signal processing for meshes, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.325-334, July 1999 [doi>10.1145/311535.311577]
• 15: Heroux, M. A., and Willenbring, J. M. 2003. Trilinos users guide. Tech. Rep. SAND2003-2952, Sandia National Laboratories.
• 16: Ron Kimmel , Irad Yavneh, An Algebraic Multigrid Approach for Image Analysis, SIAM Journal on Scientific Computing, v.24 n.4, p.1218-1231, 2002 [doi>10.1137/S1064827501389229]
• 17: Leif Kobbelt , Swen Campagna , Jens Vorsatz , Hans-Peter Seidel, Interactive multi-resolution modeling on arbitrary meshes, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.105-114, July 1998 [doi>10.1145/280814.280831]
• 18: Yaron Lipman , Olga Sorkine , David Levin , Daniel Cohen-Or, Linear rotation-invariant coordinates for meshes, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 19: Xinlai Ni , Michael Garland , John C. Hart, Fair morse functions for extracting the topological structure of a surface mesh, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 20: Nicolas Ray , Bruno Levy, Hierarchical Least Squares Conformal Map, Proceedings of the 11th Pacific Conference on Computer Graphics and Applications, p.263, October 08-10, 2003
• 21: Thomas W. Sederberg , Scott R. Parry, Free-form deformation of solid geometric models, Proceedings of the 13th annual conference on Computer graphics and interactive techniques, p.151-160, August 1986
• 22: O. Sorkine , D. Cohen-Or , Y. Lipman , M. Alexa , C. Rössl , H.-P. Seidel, Laplacian surface editing, Proceedings of the 2004 Eurographics/ACM SIGGRAPH symposium on Geometry processing, July 08-10, 2004, Nice, France [doi>10.1145/1057432.1057456]
• 23: Robert W. Sumner , Jovan Popović, Deformation transfer for triangle meshes, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 24: Robert W. Sumner , Matthias Zwicker , Craig Gotsman , Jovan Popović, Mesh-based inverse kinematics, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 25: Toledo, S., Rotkin, V., and Chen, D. 2003. Taucs:a library of sparse linear solvers. version 2.2. Tech. rep., Tel-Aviv University.
• 26: Ulrich Trottenberg , Anton Schuller, Multigrid, Academic Press, Inc., Orlando, FL, 2000
• 27: Wesseling, P. 2004. An Introduction to Multigrid Methods. R. T. Edwards, Inc.
• 28: Yizhou Yu , Kun Zhou , Dong Xu , Xiaohan Shi , Hujun Bao , Baining Guo , Heung-Yeung Shum, Mesh editing with poisson-based gradient field manipulation, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 29: Zayer, R., Rössl, C., Karni, Z., and Seidel, H.-P. 2005. Harmonic guidance for surface deformation. Computer Graphics Forum (Eurographics 2005) 24, 3.
• 30: Kun Zhou , Jin Huang , John Snyder , Xinguo Liu , Hujun Bao , Baining Guo , Heung-Yeung Shum, Large mesh deformation using the volumetric graph Laplacian, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 31: Denis Zorin , Peter Schröder , Wim Sweldens, Interactive multiresolution mesh editing, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.259-268, August 1997 [doi>10.1145/258734.258863]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Boundary representations

Keywords:
Laplacian, constraints, graph hierarchy, mesh editing, prolongation/restriction operators