{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:39:07Z","timestamp":1750307947013,"version":"3.41.0"},"reference-count":97,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2007,10,1]],"date-time":"2007-10-01T00:00:00Z","timestamp":1191196800000},"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":[[2007,10]]},"abstract":"<jats:p>This article presents a generic framework for the representation and deformation of level set surfaces at extreme resolutions. The framework is composed of two modules that each utilize optimized and application specific algorithms: 1) A fast<jats:italic>out-of-core<\/jats:italic>data management scheme that allows for resolutions of the deforming geometry limited only by the available disk space as opposed to memory, and 2) compact and fast<jats:italic>compression<\/jats:italic>strategies that reduce both offline storage requirements and online memory footprints during simulation. Out-of-core and compression techniques have been applied to a wide range of computer graphics problems in recent years, but this article is the first to apply it in the context of level set and fluid<jats:italic>simulations<\/jats:italic>. Our framework is generic and flexible in the sense that the two modules can transparently be integrated, separately or in any combination, into existing level set and fluid simulation software based on recently proposed narrow band data structures like the DT-Grid of Nielsen and Museth [2006] and the H-RLE of Houston et al [2006]. The framework can be applied to narrow band signed distances, fluid velocities, scalar fields, particle properties as well as standard graphics attributes like colors, texture coordinates, normals, displacements etc. In fact, our framework is applicable to a large body of computer graphics problems that involve sequential or random access to very large co-dimension one (level set) and zero (e.g. fluid) data sets. We demonstrate this with several applications, including fluid simulations interacting with large boundaries (\u2248 1500<jats:sup>3<\/jats:sup>), surface deformations (\u2248 2048<jats:sup>3<\/jats:sup>), the solution of partial differential equations on large surfaces (\u2248 4096<jats:sup>3<\/jats:sup>) and mesh-to-level set scan conversions of resolutions up to \u2248 35000<jats:sup>3<\/jats:sup>(7 billion voxels in the narrow band). Our out-of-core framework is shown to be several times faster than current state-of-the-art level set data structures relying on OS paging. In particular we show sustained throughput (grid points\/sec) for gigabyte sized level sets as high as 65% of state-of-the-art throughput for in-core simulations. We also demonstrate that our compression techniques out-perform state-of-the-art compression algorithms for narrow bands.<\/jats:p>","DOI":"10.1145\/1289603.1289607","type":"journal-article","created":{"date-parts":[[2007,11,15]],"date-time":"2007-11-15T14:26:02Z","timestamp":1195136762000},"page":"16","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":14,"title":["Out-of-core and compressed level set methods"],"prefix":"10.1145","volume":"26","author":[{"given":"Michael B.","family":"Nielsen","sequence":"first","affiliation":[{"name":"University of \u00c5rhus"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ola","family":"Nilsson","sequence":"additional","affiliation":[{"name":"University of Link\u00f6ping"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andreas","family":"S\u00f6derstr\u00f6m","sequence":"additional","affiliation":[{"name":"University of Link\u00f6ping"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ken","family":"Museth","sequence":"additional","affiliation":[{"name":"University of Link\u00f6ping and University of \u00c5rhus"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2007,10]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcph.1995.1098"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1048935.1050202"},{"volume-title":"Proceedings of the 3rd USENIX Symposium on File and Storage Technologies.","author":"Bansal S.","key":"e_1_2_1_3_1"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1122501.1122503"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/2945.928169"},{"key":"e_1_2_1_8_1","unstructured":"Chiang Y.-J. and Silva C. T. 1997. I\/o optimal isosurface extraction (extended abstract). IEEE Visualiz. 293--300. Chiang Y.-J. and Silva C. T. 1997. I\/o optimal isosurface extraction (extended abstract). IEEE Visualiz. 293--300."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/339331.339424"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2003.1260746"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/868963"},{"volume-title":"Proceedings of the 8th Conference on Visualization (VIS'97)","author":"Cox M.","key":"e_1_2_1_12_1"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/311535.311576"},{"key":"e_1_2_1_14_1","unstructured":"Dongarra J. Lumsdaine A. Niu X. Pozo R. and Remington K. 1994. A sparse matrix library in C&plus;&plus; for high performance architectures. 214--218. http:\/\/citeseer.1st.psu.edu\/dongarra94sparse.html. Dongarra J. Lumsdaine A. Niu X. Pozo R. and Remington K. 1994. A sparse matrix library in C&plus;&plus; for high performance architectures. 214--218. http:\/\/citeseer.1st.psu.edu\/dongarra94sparse.html."},{"volume-title":"Proceedings of Graphics Interface.","author":"Eckstein I.","key":"e_1_2_1_15_1"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcph.2002.7166"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/566570.566645"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/383259.383261"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1179849.1179874"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/258612.258681"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073204.1073277"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.6028\/jres.049.044"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcp.2005.04.013"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1122501.1122508"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1186223.1186394"},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","unstructured":"Hy Trac U.-L. P. 2006. Out-of-core hydrodynamic simulations for cosmological applications. New Astronomy. Hy Trac U.-L. P. 2006. Out-of-core hydrodynamic simulations for cosmological applications. New Astronomy.","DOI":"10.1016\/j.newast.2005.08.003"},{"key":"e_1_2_1_27_1","first-page":"343","article-title":"Out-of-core compression and decompression of large n-dimensional scalar fields","volume":"22","author":"Ibarria L.","year":"2003","journal-title":"Comput. Graph. For."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1141911.1141959"},{"volume-title":"Graphics Conference Proceedings. 284--293","year":"2004","author":"Isenburg M.","key":"e_1_2_1_29_1"},{"key":"e_1_2_1_30_1","doi-asserted-by":"crossref","unstructured":"Isenburg M. and Alliez P. 2002. Compressing hexahedral volume meshes. Isenburg M. and Alliez P. 2002. Compressing hexahedral volume meshes.","DOI":"10.1016\/S1524-0703(03)00044-4"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/882262.882366"},{"key":"e_1_2_1_32_1","doi-asserted-by":"crossref","unstructured":"Isenburg M. Lindstrom P. and Snoeyink J. 2004. Lossless compression of floating-point geometry. CAD'3D. Isenburg M. Lindstrom P. and Snoeyink J. 2004. Lossless compression of floating-point geometry. CAD'3D.","DOI":"10.1080\/16864360.2004.10738292"},{"volume-title":"Symposium on Geometry Processing. 111--118","author":"Isenburg M.","key":"e_1_2_1_33_1"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/511334.511340"},{"volume-title":"Proceedings of the 20th International Conference on Very Large Data Bases (VLDB'94)","author":"Johnson T.","key":"e_1_2_1_35_1"},{"volume-title":"Proceedings of International Conference on Computer Graphics Visulization and Computer Vision. (WSCG) 199--204","year":"2004","author":"Jones M. W.","key":"e_1_2_1_36_1"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/566570.566586"},{"volume-title":"Proceedings of Eurographics.","author":"K\u00e4lberer F.","key":"e_1_2_1_38_1"},{"volume-title":"Proceedings of the Symposium on Operating Systems Design and Implementation (OSDI). 119--134","author":"Kim J. M.","key":"e_1_2_1_39_1"},{"key":"e_1_2_1_40_1","unstructured":"Kincaid D. and Cheney W. 1991. Numerical analysis: mathematics of scientific computing. Brooks\/Cole Publishing Co. Pacific Grove CA USA. Kincaid D. and Cheney W. 1991. Numerical analysis: mathematics of scientific computing. Brooks\/Cole Publishing Co. Pacific Grove CA USA."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/383259.383265"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30474-6_42"},{"volume-title":"Proceedings of International Conference on 3D Data Processing Visualization and Transmission (3DPVT). 470--479","author":"Laney D. E.","key":"e_1_2_1_43_1"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/301453.301487"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/882262.882294"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/VISUAL.2003.1250357"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1137\/0733033"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/344779.344849"},{"key":"e_1_2_1_49_1","doi-asserted-by":"crossref","unstructured":"Li M. and Vitanyi P. 1997. An Introduction to Kolmogorov Complexity and Its Applications 2nd Ed. Springer-Verlag. Li M. and Vitanyi P. 1997. An Introduction to Kolmogorov Complexity and Its Applications 2nd Ed. Springer-Verlag.","DOI":"10.1007\/978-1-4757-2606-0"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcph.1994.1187"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2004.14"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/37401.37422"},{"key":"e_1_2_1_53_1","doi-asserted-by":"crossref","unstructured":"Losasso F. Fedkiw R. and Osher S. 2005. Spatially adaptive techniques for level set methods and incompressible flow. Comput. Fluids. To appear. Losasso F. Fedkiw R. and Osher S. 2005. Spatially adaptive techniques for level set methods and incompressible flow. Comput. Fluids. To appear.","DOI":"10.21236\/ADA479010"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/1015706.1015745"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1109\/3DPVT.2004.49"},{"volume-title":"Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'00)","author":"Matias Y.","key":"e_1_2_1_56_1"},{"volume-title":"Proceedings of the 2nd USENIX Conference on File and Storage Technologies (FAST'03)","author":"Megiddo N.","key":"e_1_2_1_58_1"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcp.2004.04.019"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/290159.290162"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/566654.566585"},{"key":"e_1_2_1_63_1","doi-asserted-by":"crossref","first-page":"821","DOI":"10.1111\/j.1467-8659.2005.00904.x","article-title":"Algorithms for interactive editing of level set models","volume":"24","author":"Museth K.","year":"2005","journal-title":"Comput. Grap. For."},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/566570.566643"},{"key":"e_1_2_1_65_1","first-page":"3","article-title":"Rapid high quality compression of volume data for visualization","volume":"20","author":"Nguyen K. G.","year":"2001","journal-title":"Comput. Graph. For."},{"key":"e_1_2_1_66_1","first-page":"001","article-title":"Dynamic Tubular Grid: An efficient data structure and algorithms for high resolution level sets","volume":"9","author":"Nielsen M. B.","year":"2004","journal-title":"Link\u00f6ping Electronic Articles in Computer and Information Science"},{"volume-title":"Proceedings of SIGRAD'04","author":"Nielsen M. B.","key":"e_1_2_1_67_1"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10915-005-9062-8"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1145\/170035.170081"},{"key":"e_1_2_1_70_1","doi-asserted-by":"crossref","unstructured":"Osher S. and Fedkiw R. 2002. Level Set Methods and Dynamic Implicit Surfaces. Springer-Verlag Berlin Germany. Osher S. and Fedkiw R. 2002. Level Set Methods and Dynamic Implicit Surfaces. Springer-Verlag Berlin Germany.","DOI":"10.1007\/b98879"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1016\/0021-9991(88)90002-2"},{"key":"e_1_2_1_72_1","doi-asserted-by":"crossref","unstructured":"Pajarola R. 2005. Stream-processing points. in IEEE Visualiz. 31. Pajarola R. 2005. Stream-processing points. in IEEE Visualiz. 31.","DOI":"10.1109\/VIS.2005.93"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1145\/582034.582036"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1145\/224056.224064"},{"key":"e_1_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcph.1999.6345"},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1145\/98457.98523"},{"volume-title":"Proceedings of Conference on Parallel Processing for Scientific Computing (PPSC).","author":"Salmon J. K.","key":"e_1_2_1_77_1"},{"volume-title":"Data Compression: The Complete Reference. With contributions by Giovanni Motta and David Bryant","year":"2007","author":"Salomon D.","key":"e_1_2_1_78_1"},{"volume-title":"Proceedings of USENIX Conference on File and Storage Technologies (FAST).","author":"Schlosser S. W.","key":"e_1_2_1_79_1"},{"key":"e_1_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.5555\/243179.243183"},{"edition":"2","volume-title":"Level Set Methods and Fast Marching Methods","author":"Sethian J. A.","key":"e_1_2_1_81_1"},{"key":"e_1_2_1_82_1","unstructured":"Silva C. Chiang Y. El-Sana J. and Lindstrom P. 2002. Out-of-core algorithms for scientific visualization and computer graphics. Silva C. Chiang Y. El-Sana J. and Lindstrom P. 2002. Out-of-core algorithms for scientific visualization and computer graphics."},{"key":"e_1_2_1_83_1","doi-asserted-by":"publisher","DOI":"10.1145\/301453.301486"},{"key":"e_1_2_1_84_1","doi-asserted-by":"publisher","DOI":"10.1145\/311535.311548"},{"key":"e_1_2_1_85_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcph.1999.6205"},{"key":"e_1_2_1_86_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcph.1998.6106"},{"key":"e_1_2_1_87_1","first-page":"391","article-title":"Realistic animation of fluid with splashes and foam","volume":"22","author":"Takahashi T.","year":"2003","journal-title":"Comput. Graph. For."},{"volume-title":"Modern Operating Systems","author":"Tanenbaum A. S.","key":"e_1_2_1_88_1"},{"key":"e_1_2_1_89_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0021-9991(03)00192-X"},{"volume-title":"Blic: Bi-level isosurface compression","year":"2002","author":"Taubin G.","key":"e_1_2_1_90_1"},{"volume-title":"External Memory Algorithms","author":"Toledo S.","key":"e_1_2_1_92_1"},{"volume-title":"Proceedings of Conference (Graphics Interface). 26--34","author":"Touma C.","key":"e_1_2_1_93_1"},{"key":"e_1_2_1_94_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.newast.2005.08.003"},{"key":"e_1_2_1_95_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00366-004-0283-5"},{"key":"e_1_2_1_96_1","doi-asserted-by":"publisher","DOI":"10.1145\/384192.384193"},{"key":"e_1_2_1_97_1","doi-asserted-by":"crossref","unstructured":"Vitter J. S. and Shriver E. A. M. 1994. Algorithms for parallel memory i: Two-level memories. Algorithmica 12 2\/3 110--147. Vitter J. S. and Shriver E. A. M. 1994. Algorithms for parallel memory i: Two-level memories. Algorithmica 12 2\/3 110--147.","DOI":"10.1007\/BF01185207"},{"key":"e_1_2_1_98_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008036829907"},{"key":"e_1_2_1_99_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1025336916176"},{"key":"e_1_2_1_100_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00371-006-0003-9"},{"volume-title":"Proceedings of the IEEE Workshop on Variational and Level Set Methods (VLSM'01)","author":"Zhao H.-K.","key":"e_1_2_1_101_1"},{"key":"e_1_2_1_102_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2004.13"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1289603.1289607","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1289603.1289607","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T14:52:31Z","timestamp":1750258351000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1289603.1289607"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,10]]},"references-count":97,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2007,10]]}},"alternative-id":["10.1145\/1289603.1289607"],"URL":"https:\/\/doi.org\/10.1145\/1289603.1289607","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"type":"print","value":"0730-0301"},{"type":"electronic","value":"1557-7368"}],"subject":[],"published":{"date-parts":[[2007,10]]},"assertion":[{"value":"2007-10-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}