{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,27]],"date-time":"2026-09-27T15:37:42Z","timestamp":1790523462165,"version":"4.1.0"},"reference-count":77,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2015,11,2]],"date-time":"2015-11-02T00:00:00Z","timestamp":1446422400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["DMS-1304211"],"award-info":[{"award-number":["DMS-1304211"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2015,11,4]]},"abstract":"<jats:p>\n                    Many tasks in geometry processing and physical simulation benefit from multiresolution hierarchies. One important characteristic across a variety of applications is that coarser layers strictly\n                    <jats:italic>encage<\/jats:italic>\n                    finer layers, nesting one another. Existing techniques such as surface mesh decimation, voxelization, or contouring distance level sets do not provide sufficient control over the\n                    <jats:italic>quality<\/jats:italic>\n                    of the output surfaces while maintaining strict nesting. We propose a solution that enables use of application-specific decimation and quality metrics. The method constructs each next-coarsest level of the hierarchy, using a sequence of decimation, flow, and contact-aware optimization steps. From coarse to fine, each layer then fully encages the next while retaining a snug fit. The method is applicable to a wide variety of shapes of complex geometry and topology. We demonstrate the effectiveness of our nested cages not only for multigrid solvers, but also for conservative collision detection, domain discretization for elastic simulation, and cage-based geometric modeling.\n                  <\/jats:p>","DOI":"10.1145\/2816795.2818093","type":"journal-article","created":{"date-parts":[[2015,10,27]],"date-time":"2015-10-27T08:36:39Z","timestamp":1445934999000},"page":"1-14","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":63,"title":["Nested cages"],"prefix":"10.1145","volume":"34","author":[{"given":"Leonardo","family":"Sacht","sequence":"first","affiliation":[{"name":"Universidade Federal de Santa Catarina"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Etienne","family":"Vouga","sequence":"additional","affiliation":[{"name":"University of Texas at Austin"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alec","family":"Jacobson","sequence":"additional","affiliation":[{"name":"Columbia University"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2015,11,2]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/331532.331559"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2366145.2366170"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827503430138"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00371-010-0416-3"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1360612.1360643"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2005.49"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/882262.882357"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1599470.1599479"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1531326.1531340"},{"key":"e_1_2_2_10_1","volume-title":"OpenSG Symposium.","author":"Botsch M.","unstructured":"Botsch , M. , Steinberg , S. , Bischoff , S. , and Kobbelt , L . 2002. OpenMesh -- a generic and efficient polygon mesh data structure . In OpenSG Symposium. Botsch, M., Steinberg, S., Bischoff, S., and Kobbelt, L. 2002. OpenMesh -- a generic and efficient polygon mesh data structure. In OpenSG Symposium."},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/080737617"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2185520.2185592"},{"key":"e_1_2_2_13_1","unstructured":"Brune P. R. Knepley M. G. and Scott L. R. 2011. Unstructured geometric multigrid in two and three dimensions on complex and graded meshes. CoRR abs\/1104.0261.  Brune P. R. Knepley M. G. and Scott L. R. 2011. Unstructured geometric multigrid in two and three dimensions on complex and graded meshes. CoRR abs\/1104.0261."},{"key":"e_1_2_2_14_1","doi-asserted-by":"crossref","unstructured":"Campen M. and Kobbelt L. 2010. Polygonal Boundary Evaluation of Minkowski Sums and Swept Volumes. Comput. Graph. Forum 29 5 1613--1622.  Campen M. and Kobbelt L. 2010. Polygonal Boundary Evaluation of Minkowski Sums and Swept Volumes. Comput. Graph. Forum 29 5 1613--1622.","DOI":"10.1111\/j.1467-8659.2010.01770.x"},{"key":"e_1_2_2_15_1","unstructured":"Cgal Computational Geometry Algorithms Library. http:\/\/www.cgal.org.  Cgal Computational Geometry Algorithms Library. http:\/\/www.cgal.org."},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-0427(00)00411-8"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02207701"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002110050189"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827596310056"},{"key":"e_1_2_2_20_1","unstructured":"Chang W. Li H. Mitra N. J. Pauly M. and Wand M. 2010. Geometric registration for deformable shapes. In Eurographics 2010: Tutorial Notes.  Chang W. Li H. Mitra N. J. Pauly M. and Wand M. 2010. Geometric registration for deformable shapes. In Eurographics 2010: Tutorial Notes."},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1778765.1778775"},{"key":"e_1_2_2_22_1","volume-title":"Proc. SGP, 1475--1484","author":"Chuang M.","unstructured":"Chuang , M. , Luo , L. , Brown , B. J. , Rusinkiewicz , S. , and Kazhdan , M . 2009. Estimating the laplace-beltrami operator by restricting 3d functions . In Proc. SGP, 1475--1484 . Chuang, M., Luo, L., Brown, B. J., Rusinkiewicz, S., and Kazhdan, M. 2009. Estimating the laplace-beltrami operator by restricting 3d functions. In Proc. SGP, 1475--1484."},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2461912.2461986"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/383259.383262"},{"key":"e_1_2_2_25_1","unstructured":"Demmel J. 2004. Multigrid overview. http:\/\/www.cs.berkeley.edu\/~demmel.  Demmel J. 2004. Multigrid overview. http:\/\/www.cs.berkeley.edu\/~demmel."},{"key":"e_1_2_2_26_1","first-page":"3","article-title":"Automatic cage building with quadric error metrics","volume":"26","author":"Deng Z.-J.","year":"2011","unstructured":"Deng , Z.-J. , Luo , X.-N. , and Miao , X.-P. 2011 . Automatic cage building with quadric error metrics . Comp. Sci. & Tech. 26 , 3 . Deng, Z.-J., Luo, X.-N., and Miao, X.-P. 2011. Automatic cage building with quadric error metrics. Comp. Sci. & Tech. 26, 3.","journal-title":"Comp. Sci. & Tech."},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/311535.311576"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2010.268"},{"key":"e_1_2_2_30_1","unstructured":"Eppstein D. 2015. When is it possible to \"shrink\" a polyhedron? MathOverflow. http:\/\/mathoverflow.net\/q\/206750 (version: 2015-05-16).  Eppstein D. 2015. When is it possible to \"shrink\" a polyhedron? MathOverflow. http:\/\/mathoverflow.net\/q\/206750 (version: 2015-05-16)."},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/MCSE.2006.105"},{"key":"e_1_2_2_32_1","doi-asserted-by":"crossref","unstructured":"Feng Y. Peri\u0107 D. and Owen D. 1997. A non-nested galerkin multi-grid method for solving linear and nonlinear solid mechanics problems. Comp. methods in applied mech. & eng. 144 3.  Feng Y. Peri\u0107 D. and Owen D. 1997. A non-nested galerkin multi-grid method for solving linear and nonlinear solid mechanics problems. Comp. methods in applied mech. & eng. 144 3.","DOI":"10.1016\/S0045-7825(96)01183-8"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2014.2307873"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1002\/nme.1620381002"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/258734.258849"},{"key":"e_1_2_2_37_1","doi-asserted-by":"crossref","unstructured":"Gumhold S. Borodin P. and Klein R. 2003. Intersection free simplification. IJSM 155--176.  Gumhold S. Borodin P. and Klein R. 2003. Intersection free simplification. IJSM 155--176.","DOI":"10.1142\/S0218654303000097"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1531326.1531393"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2070781.2024171"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/237170.237216"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2461912.2461916"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1276377.1276466"},{"key":"e_1_2_2_43_1","volume-title":"Proc. SGP, 61--70","author":"Kazhdan M.","unstructured":"Kazhdan , M. , Bolitho , M. , and Hoppe , H . 2006. Poisson surface reconstruction . In Proc. SGP, 61--70 . Kazhdan, M., Bolitho, M., and Hoppe, H. 2006. Poisson surface reconstruction. In Proc. SGP, 61--70."},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2012.03179.x"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2461912.2461992"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2010324.1964932"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/1618452.1618483"},{"key":"e_1_2_2_48_1","unstructured":"Melax S. 1998. A simple fast and effective polygon reduction algorithm. Game Developer Magazine 44--49.  Melax S. 1998. A simple fast and effective polygon reduction algorithm. Game Developer Magazine 44--49."},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/2766907"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/1531326.1531358"},{"key":"e_1_2_2_51_1","volume-title":"Proc. SGP.","author":"Otaduy M. A.","unstructured":"Otaduy , M. A. , and Lin , M. C . 2003. CLODs: Dual hierarchies for multiresolution collision detection . In Proc. SGP. Otaduy, M. A., and Lin, M. C. 2003. CLODs: Dual hierarchies for multiresolution collision detection. In Proc. SGP."},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/882262.882305"},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/1015706.1015773"},{"key":"e_1_2_2_54_1","unstructured":"Peterhans C. 2012. Interactive Surface Reconstruction. Master's thesis ETH Zurich.  Peterhans C. 2012. Interactive Surface Reconstruction. Master's thesis ETH Zurich."},{"key":"e_1_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1111\/1467-8659.00653"},{"key":"e_1_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.12005"},{"key":"e_1_2_2_57_1","doi-asserted-by":"crossref","unstructured":"Ruge J. and St\u00fcben K. 1987. Algebraic multigrid. Multigrid methods 3.  Ruge J. and St\u00fcben K. 1987. Algebraic multigrid. Multigrid methods 3.","DOI":"10.1137\/1.9781611971057.ch4"},{"key":"e_1_2_2_58_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.12181"},{"key":"e_1_2_2_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/344779.344935"},{"key":"e_1_2_2_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/1015706.1015816"},{"key":"e_1_2_2_61_1","unstructured":"Si H. 2003. TetGen: A 3D delaunay tetrahedral mesh generator. http:\/\/tetgen.berlios.de.  Si H. 2003. TetGen: A 3D delaunay tetrahedral mesh generator. http:\/\/tetgen.berlios.de."},{"key":"e_1_2_2_62_1","volume-title":"Proc. SGP, 109--116","author":"Sorkine O.","unstructured":"Sorkine , O. , and Alexa , M . 2007. As-rigid-as-possible surface modeling . In Proc. SGP, 109--116 . Sorkine, O., and Alexa, M. 2007. As-rigid-as-possible surface modeling. In Proc. SGP, 109--116."},{"key":"e_1_2_2_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/1572614.1572619"},{"key":"e_1_2_2_64_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2012.03178.x"},{"key":"e_1_2_2_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/2461912.2461955"},{"key":"e_1_2_2_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/218380.218473"},{"key":"e_1_2_2_67_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2005.42"},{"key":"e_1_2_2_68_1","doi-asserted-by":"publisher","DOI":"10.1145\/1141911.1142007"},{"key":"e_1_2_2_69_1","unstructured":"Vouga E. Sacht L. and Jacobson A. 2015. Polyhedral nesting is NP-complete. Tech. rep. in supplementary materials.  Vouga E. Sacht L. and Jacobson A. 2015. Polyhedral nesting is NP-complete. Tech. rep. in supplementary materials."},{"key":"e_1_2_2_70_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2008.38"},{"key":"e_1_2_2_71_1","doi-asserted-by":"publisher","DOI":"10.1145\/2503177"},{"key":"e_1_2_2_72_1","doi-asserted-by":"publisher","DOI":"10.1145\/2601097.2601114"},{"key":"e_1_2_2_73_1","volume-title":"Proc. VMV.","author":"Wicker M.","unstructured":"Wicker , M. , Lanker , H. , and Gross , M . 2006. Untangling cloth with boundaries . In Proc. VMV. Wicker, M., Lanker, H., and Gross, M. 2006. Untangling cloth with boundaries. In Proc. VMV."},{"key":"e_1_2_2_74_1","volume-title":"Proc. SMA.","author":"Xian C.","unstructured":"Xian , C. , Lin , H. , and Gao , S . 2009. Automatic generation of coarse bounding cages from dense meshes . In Proc. SMA. Xian, C., Lin, H., and Gao, S. 2009. Automatic generation of coarse bounding cages from dense meshes. In Proc. SMA."},{"key":"e_1_2_2_75_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00371-011-0595-6"},{"key":"e_1_2_2_76_1","doi-asserted-by":"publisher","DOI":"10.1109\/CADGraphics.2013.36"},{"key":"e_1_2_2_77_1","doi-asserted-by":"publisher","DOI":"10.1002\/cav.1571"},{"key":"e_1_2_2_78_1","unstructured":"Xu H. and Barbi\u010d J. 2014. Signed distance fields for polygon soup meshes. Graphics Interface 2014.   Xu H. and Barbi\u010d J. 2014. Signed distance fields for polygon soup meshes. Graphics Interface 2014."},{"key":"e_1_2_2_79_1","doi-asserted-by":"publisher","DOI":"10.5555\/2421731.2421775"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2816795.2818093","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2816795.2818093","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:48:18Z","timestamp":1750211298000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2816795.2818093"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,11,2]]},"references-count":77,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2015,11,4]]}},"alternative-id":["10.1145\/2816795.2818093"],"URL":"https:\/\/doi.org\/10.1145\/2816795.2818093","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,11,2]]},"assertion":[{"value":"2015-11-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}