{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,20]],"date-time":"2025-11-20T18:16:28Z","timestamp":1763662588979,"version":"3.41.0"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2006,7,1]],"date-time":"2006-07-01T00:00:00Z","timestamp":1151712000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2006,7]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1145\/1141911.1142001","type":"journal-article","created":{"date-parts":[[2006,7,25]],"date-time":"2006-07-25T14:14:26Z","timestamp":1153836866000},"page":"1108-1117","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":80,"title":["A fast multigrid algorithm for mesh deformation"],"prefix":"10.1145","volume":"25","author":[{"given":"Lin","family":"Shi","sequence":"first","affiliation":[{"name":"University of Illinois at Urbana-Champaign"}]},{"given":"Yizhou","family":"Yu","sequence":"additional","affiliation":[{"name":"University of Illinois at Urbana-Champaign"}]},{"given":"Nathan","family":"Bell","sequence":"additional","affiliation":[{"name":"University of Illinois at Urbana-Champaign"}]},{"given":"Wei-Wen","family":"Feng","sequence":"additional","affiliation":[{"name":"University of Illinois at Urbana-Champaign"}]}],"member":"320","published-online":{"date-parts":[[2006,7]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827503430138"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/344779.344859"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00371-002-0180-0"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/882262.882364"},{"key":"e_1_2_2_5_1","doi-asserted-by":"crossref","unstructured":"Botsch M. and Kobbelt L. 2005. Real-time shape editing using radial basis functions. Computer Graphics Forum (Eurographics 2005) 24 3 611--621.  Botsch M. and Kobbelt L. 2005. Real-time shape editing using radial basis functions. Computer Graphics Forum (Eurographics 2005) 24 3 611--621.","DOI":"10.1111\/j.1467-8659.2005.00886.x"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/11537908_5"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00371-004-0245-3"},{"volume-title":"User guide for cholmod. Tech. rep","author":"Davis T. A.","key":"e_1_2_2_9_1","unstructured":"Davis , T. A. 2006. User guide for cholmod. Tech. rep ., University of Florida . Davis, T. A. 2006. User guide for cholmod. Tech. rep., University of Florida."},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479895291765"},{"key":"e_1_2_2_11_1","unstructured":"Goodnight N. Woolley C. Lewin G. Luebke D. and Humphreys G. 2003. A multigrid solver for boundary value problems using programmable graphics hardware. In Graphics Hardware 102--111.   Goodnight N. Woolley C. Lewin G. Luebke D. and Humphreys G. 2003. A multigrid solver for boundary value problems using programmable graphics hardware. In Graphics Hardware 102--111."},{"key":"e_1_2_2_12_1","volume-title":"Tech. Rep. RAL-TR-2005-005, RAL Technical Reports.","author":"Gould N. I. M.","year":"2005","unstructured":"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. 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."},{"volume-title":"International Conference on Image Processing.","author":"Grady L.","key":"e_1_2_2_13_1","unstructured":"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. 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."},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/311535.311577"},{"volume-title":"Tech. Rep. SAND2003-2952","author":"Heroux M. A.","key":"e_1_2_2_15_1","unstructured":"Heroux , M. A. , and Willenbring , J. M . 2003. Trilinos users guide . Tech. Rep. SAND2003-2952 , Sandia National Laboratories. Heroux, M. A., and Willenbring, J. M. 2003. Trilinos users guide. Tech. Rep. SAND2003-2952, Sandia National Laboratories."},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827501389229"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/280814.280831"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073204.1073217"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1015706.1015769"},{"volume-title":"Proceedings of Pacific Graphics, 263--270","author":"Ray N.","key":"e_1_2_2_20_1","unstructured":"Ray , N. , and Levy , B . 2003. Hierarchical least squares conformal map . In Proceedings of Pacific Graphics, 263--270 . Ray, N., and Levy, B. 2003. Hierarchical least squares conformal map. In Proceedings of Pacific Graphics, 263--270."},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/15922.15903"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1057432.1057456"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1015706.1015736"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073204.1073218"},{"key":"e_1_2_2_25_1","unstructured":"Toledo S. Rotkin V. and Chen D. 2003. Taucs:a library of sparse linear solvers. version 2.2. Tech. rep. Tel-Aviv University.  Toledo S. Rotkin V. and Chen D. 2003. Taucs:a library of sparse linear solvers. version 2.2. Tech. rep. Tel-Aviv University."},{"key":"e_1_2_2_26_1","unstructured":"Trottenberg U. Oosterlee C. and Schuller A. 2000. Multigrid. Academic Press.   Trottenberg U. Oosterlee C. and Schuller A. 2000. Multigrid. Academic Press."},{"volume-title":"An Introduction to Multigrid Methods. R. T. Edwards","author":"Wesseling P.","key":"e_1_2_2_27_1","unstructured":"Wesseling , P. 2004. An Introduction to Multigrid Methods. R. T. Edwards , Inc . Wesseling, P. 2004. An Introduction to Multigrid Methods. R. T. Edwards, Inc."},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1015706.1015774"},{"key":"e_1_2_2_29_1","volume-title":"-P","author":"Zayer R.","year":"2005","unstructured":"Zayer , R. , R\u00f6ssl , C. , Karni , Z. , and Seidel , H . -P . 2005 . Harmonic guidance for surface deformation. Computer Graphics Forum (Eurographics 2005) 24, 3. Zayer, R., R\u00f6ssl, C., Karni, Z., and Seidel, H.-P. 2005. Harmonic guidance for surface deformation. Computer Graphics Forum (Eurographics 2005) 24, 3."},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073204.1073219"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/258734.258863"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1141911.1142001","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1141911.1142001","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T15:06:11Z","timestamp":1750259171000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1141911.1142001"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,7]]},"references-count":30,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2006,7]]}},"alternative-id":["10.1145\/1141911.1142001"],"URL":"https:\/\/doi.org\/10.1145\/1141911.1142001","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"type":"print","value":"0730-0301"},{"type":"electronic","value":"1557-7368"}],"subject":[],"published":{"date-parts":[[2006,7]]},"assertion":[{"value":"2006-07-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}