{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,8]],"date-time":"2026-02-08T07:45:09Z","timestamp":1770536709916,"version":"3.49.0"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2005,7]]},"abstract":"<jats:p>We present a novel method for computing cache-oblivious layouts of large meshes that improve the performance of interactive visualization and geometric processing algorithms. Given that the mesh is accessed in a reasonably coherent manner, we assume no particular data access patterns or cache parameters of the memory hierarchy involved in the computation. Furthermore, our formulation extends directly to computing layouts of multi-resolution and bounding volume hierarchies of large meshes.We develop a simple and practical cache-oblivious metric for estimating cache misses. Computing a coherent mesh layout is reduced to a combinatorial optimization problem. We designed and implemented an out-of-core multilevel minimization algorithm and tested its performance on unstructured meshes composed of tens to hundreds of millions of triangles. Our layouts can significantly reduce the number of cache misses. We have observed 2--20 times speedups in view-dependent rendering, collision detection, and isocontour extraction without any modification of the algorithms or runtime applications.<\/jats:p>","DOI":"10.1145\/1073204.1073278","type":"journal-article","created":{"date-parts":[[2005,11,7]],"date-time":"2005-11-07T16:00:45Z","timestamp":1131379245000},"page":"886-893","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":55,"title":["Cache-oblivious mesh layouts"],"prefix":"10.1145","volume":"24","author":[{"given":"Sung-Eui","family":"Yoon","sequence":"first","affiliation":[{"name":"University of North Carolina at Chapel Hill"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter","family":"Lindstrom","sequence":"additional","affiliation":[{"name":"Lawrence Livermore National Laboratory"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Valerio","family":"Pascucci","sequence":"additional","affiliation":[{"name":"Lawrence Livermore National Laboratory"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dinesh","family":"Manocha","sequence":"additional","affiliation":[{"name":"University of North Carolina at Chapel Hill"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2005,7]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"crossref","unstructured":"Arge L. Brodal G. and Fagerberg R. 2004. Cache oblivious data structures. Handbook on Data Structures and Applications. Arge L. Brodal G. and Fagerberg R. 2004. Cache oblivious data structures. Handbook on Data Structures and Applications.","DOI":"10.1201\/9781420035179.ch34"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2004.14"},{"key":"e_1_2_2_3_1","doi-asserted-by":"crossref","unstructured":"Bogomjakov A. and Gotsman C. 2002. Universal rendering sequences for transparent vertex caching of progressive meshes. In Computer Graphics Forum 137--148. Bogomjakov A. and Gotsman C. 2002. Universal rendering sequences for transparent vertex caching of progressive meshes. In Computer Graphics Forum 137--148.","DOI":"10.1111\/1467-8659.00573"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2003.1260746"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/207110.207162"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/1081407.1081409"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/218380.218391"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/568522.568523"},{"key":"e_1_2_2_9_1","volume-title":"Proc. CEIG, 217--232","author":"Franquesa-Niubo M.","unstructured":"Franquesa-Niubo , M. , and Brunet , P . 2003. Collision prediction using mktrees . Proc. CEIG, 217--232 . Franquesa-Niubo, M., and Brunet, P. 2003. Collision prediction using mktrees. Proc. CEIG, 217--232."},{"key":"e_1_2_2_10_1","volume-title":"Symposium on Foundations of Computer Science, 285--297","author":"Frigo M.","unstructured":"Frigo , M. , Leiserson , C. , Prokop , H. , and Ramachandran , S . 1999. Cache-oblivious algorithms . Symposium on Foundations of Computer Science, 285--297 . Frigo, M., Leiserson, C., Prokop, H., and Ramachandran, S. 1999. Cache-oblivious algorithms. Symposium on Foundations of Computer Science, 285--297."},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90059-1"},{"key":"e_1_2_2_12_1","doi-asserted-by":"crossref","unstructured":"Gopi M. and Eppstein D. 2004. Single-strip triangulation of manifolds with arbitrary topology. In EUROGRAPHICS 371--379. Gopi M. and Eppstein D. 2004. Single-strip triangulation of manifolds with arbitrary topology. In EUROGRAPHICS 371--379.","DOI":"10.1111\/j.1467-8659.2004.00768.x"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/237170.237244"},{"key":"e_1_2_2_14_1","volume-title":"Concurrency: Practice and Experience, 85--109.","author":"Heber G.","year":"2000","unstructured":"Heber , G. , Biswas , R. , and Gao , G . 2000 . Self-avoiding walks over adaptive unstructured grids. In Concurrency: Practice and Experience, 85--109. Heber, G., Biswas, R., and Gao, G. 2000. Self-avoiding walks over adaptive unstructured grids. In Concurrency: Practice and Experience, 85--109."},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/311535.311565"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/882262.882366"},{"key":"e_1_2_2_17_1","volume-title":"Tech. Rep. UCRL-CONF-201992, LLNL.","author":"Isenburg M.","year":"2004","unstructured":"Isenburg , M. , and Lindstrom , P . 2004 . Streaming meshes. Tech. Rep. UCRL-CONF-201992, LLNL. Isenburg, M., and Lindstrom, P. 2004. Streaming meshes. Tech. Rep. UCRL-CONF-201992, LLNL."},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/261619.261620"},{"key":"e_1_2_2_19_1","doi-asserted-by":"crossref","unstructured":"Karni Z. Bogomjakov A. and Gotsman C. 2002. Efficient compression and rendering of multi-resolution meshes. In IEEE Visualization 347--354. Karni Z. Bogomjakov A. and Gotsman C. 2002. Efficient compression and rendering of multi-resolution meshes. In IEEE Visualization 347--354.","DOI":"10.1109\/VISUAL.2002.1183794"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1997.1404"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/504794.504796"},{"key":"e_1_2_2_22_1","doi-asserted-by":"crossref","unstructured":"Lin M. and Manocha D. 2003. Collision and proximity queries. In Handbook of Discrete and Computational Geometry. Lin M. and Manocha D. 2003. Collision and proximity queries. In Handbook of Discrete and Computational Geometry.","DOI":"10.1201\/9781420035315.ch35"},{"key":"e_1_2_2_23_1","doi-asserted-by":"crossref","unstructured":"Lindstrom P. and Pascucci V. 2001. Visualization of large terrains made easy. IEEE Visualization 363--370. Lindstrom P. and Pascucci V. 2001. Visualization of large terrains made easy. IEEE Visualization 363--370.","DOI":"10.1109\/VISUAL.2001.964533"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/S00361445003820"},{"key":"e_1_2_2_25_1","doi-asserted-by":"crossref","unstructured":"Pascucci V. and Frank R. J. 2001. Global static indexing for real-time exploration of very large regular grids. Super Computing 225--241. Pascucci V. and Frank R. J. 2001. Global static indexing for real-time exploration of very large regular grids. Super Computing 225--241.","DOI":"10.1145\/582034.582036"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/344779.344940"},{"key":"e_1_2_2_27_1","doi-asserted-by":"crossref","unstructured":"Sagan H. 1994. Space-Filling Curves. Springer-Verlag. Sagan H. 1994. Space-Filling Curves. Springer-Verlag.","DOI":"10.1007\/978-1-4612-0871-6"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/602220.602225"},{"key":"e_1_2_2_29_1","unstructured":"Silva C. Chiang Y.-J. Correa W. El-Sana J. and Lindstrom P. 2002. Out-of-core algorithms for scientific visualization and computer graphics. Visualization'02 Course Notes. Silva C. Chiang Y.-J. Correa W. El-Sana J. and Lindstrom P. 2002. Out-of-core algorithms for scientific visualization and computer graphics. Visualization'02 Course Notes."},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/262839.269238"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/127719.122727"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/384192.384193"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1111\/1467-8659.00352"},{"key":"e_1_2_2_34_1","doi-asserted-by":"crossref","unstructured":"Yoon S.-E. and Manocha D. 2005. Cache-Oblivious Layouts of Bounding Volume Hierarchies. Tech. rep. University of North Carolina-Chapel Hill. Yoon S.-E. and Manocha D. 2005. Cache-Oblivious Layouts of Bounding Volume Hierarchies. Tech. rep. University of North Carolina-Chapel Hill.","DOI":"10.1145\/1186822.1073278"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1057432.1057450"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/VISUAL.2004.86"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1073204.1073278","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,5]],"date-time":"2025-01-05T10:33:20Z","timestamp":1736073200000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1073204.1073278"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,7]]},"references-count":36,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2005,7]]}},"alternative-id":["10.1145\/1073204.1073278"],"URL":"https:\/\/doi.org\/10.1145\/1073204.1073278","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,7]]},"assertion":[{"value":"2005-07-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}