{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,20]],"date-time":"2026-07-20T11:23:02Z","timestamp":1784546582941,"version":"3.55.0"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2006,1,1]],"date-time":"2006-01-01T00:00:00Z","timestamp":1136073600000},"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,1]]},"abstract":"<jats:p>This article introduces the Hierarchical Run-Length Encoded (H-RLE) Level Set data structure. This novel data structure combines the best features of the DT-Grid (of Nielsen and Museth [2004]) and the RLE Sparse Level Set (of Houston et al. [2004]) to provide both optimal efficiency and extreme versatility. In brief, the H-RLE level set employs an RLE in a dimensionally recursive fashion. The RLE scheme allows the compact storage of sequential nonnarrowband regions while the dimensionally recursive encoding along each axis efficiently compacts nonnarrowband planes and volumes. Consequently, this new structure can store and process level sets with effective voxel resolutions exceeding 5000 \u00d7 3000 \u00d7 3000 (45 billion voxels) on commodity PCs with only 1 GB of memory. This article, besides introducing the H-RLE level set data structure and its efficient core algorithms, also describes numerous applications that have benefited from our use of this structure: our unified implicit object representation, efficient and robust mesh to level set conversion, rapid ray tracing, level set metamorphosis, collision detection, and fully sparse fluid simulation (including RLE vector and matrix representations.) Our comparisons of the popular octree level set and Peng level set structures to the H-RLE level set indicate that the latter is superior in both narrowband sequential access speed and overall memory usage.<\/jats:p>","DOI":"10.1145\/1122501.1122508","type":"journal-article","created":{"date-parts":[[2006,5,8]],"date-time":"2006-05-08T16:09:20Z","timestamp":1147104560000},"page":"151-175","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":79,"title":["Hierarchical RLE level set"],"prefix":"10.1145","volume":"25","author":[{"given":"Ben","family":"Houston","sequence":"first","affiliation":[{"name":"Exocortex Technologies, Frantic Films, Ottawa, Ont., Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael B.","family":"Nielsen","sequence":"additional","affiliation":[{"name":"University of \u00c5rhus, Norrk\u00f6ping, Sweden"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christopher","family":"Batty","sequence":"additional","affiliation":[{"name":"University of British Columbia, Frantic Films, Vancouver, BC, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ola","family":"Nilsson","sequence":"additional","affiliation":[{"name":"Link\u00f6ping Institute of Technology, Norrk\u00f6ping, Sweden"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ken","family":"Museth","sequence":"additional","affiliation":[{"name":"Link\u00f6ping Institute of Technology and University of \u00c5rhus, Norrk\u00f6ping, Sweden"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2006,1]]},"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","volume-title":"Proceedings of the SIGGRAPH 2005 on Sketches & Applications. ACM Press","author":"Batty C.","year":"1871"},{"key":"e_1_2_1_3_1","volume-title":"Level Sets and PDE Methods for Computer Graphics. ACM SIGGRAPH '04 COURSE &num;27","author":"Breen D."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/2945.928169"},{"key":"e_1_2_1_5_1","unstructured":"Bridson R. 2003. Computational aspects of dynamic surfaces. dissertation. Stanford University Stanford CA.   Bridson R. 2003. Computational aspects of dynamic surfaces. dissertation. Stanford University Stanford CA."},{"key":"e_1_2_1_6_1","volume-title":"SCA '03: Proceedings of the 2003 ACM SIGGRAPH\/Eurographics Symposium on Computer animation. Eurographics Association, Aire-la-Ville","author":"Bridson R."},{"key":"e_1_2_1_7_1","unstructured":"Carlson M. 2004. Rigid melting and flowing fluid. Ph.D. dissertation Georgia Institute of Technology Atlanta GA.   Carlson M. 2004. Rigid melting and flowing fluid. Ph.D. dissertation Georgia Institute of Technology Atlanta GA."},{"key":"e_1_2_1_8_1","volume-title":"Annual Conference Series. 303--312","author":"Curless B."},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the XVII Brazilian Symposium on Computer Graphics and Image Processing (SIBGRAPI'04)","author":"de Araujo B. R."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.compstruc.2004.04.024"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/566654.566645"},{"key":"e_1_2_1_12_1","volume-title":"SIGGRAPH '01: Proceedings of the 28th Annual Conference on Computer Graphics and Interactive Techniques. ACM Press","author":"Foster N."},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of SIGGRAPH 2000. Computer Graphics Proceedings, Annual Conference Series. ACM Press","author":"Frisken S. F."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1015706.1015746"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/882262.882358"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the SIGGRAPH 2003 on Sketches & Applications. ACM Press","author":"Houston B."},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the SIGGRAPH 2005 on Sketches & Applications. ACM Press","author":"Houston B.","year":"1871"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the SIGGRAPH 2004 on Sketches & Applications. ACM Press","author":"Houston B.","year":"1862"},{"key":"e_1_2_1_19_1","volume-title":"SCA '04: Proceedings of the 2004 ACM SIGGRAPH\/Eurographics Symposium on Computer Animation","author":"Irving G."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1015706.1015815"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/0733033"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcph.1994.1187"},{"key":"e_1_2_1_23_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. In Press.  Losasso F. Fedkiw R. and Osher S. 2005. Spatially adaptive techniques for level set methods and incompressible flow. Comput. Fluids. In Press.","DOI":"10.21236\/ADA479010"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1015706.1015745"},{"key":"e_1_2_1_25_1","unstructured":"Mauch S. 2000. A fast algorithm for computing the closest point and distance transform. Go online to http:\/\/www.acm.caltech.edu\/seanm\/software\/cpt\/cpt.pdf.  Mauch S. 2000. A fast algorithm for computing the closest point and distance transform. Go online to http:\/\/www.acm.caltech.edu\/seanm\/software\/cpt\/cpt.pdf."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/566654.566585"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10915-005-9062-8"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/0021-9991(88)90002-2"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/0728049"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcph.1999.6345"},{"key":"e_1_2_1_31_1","volume-title":"SCA '04: Proceedings of the 2004 ACM SIGGRAPH\/Eurographics Symposium on Computer Animation. ACM Press","author":"Rasmussen N."},{"key":"e_1_2_1_32_1","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1073\/pnas.93.4.1591","article-title":"A fast marching level set method for monotonically advancing fronts","volume":"93","author":"Sethian J. A.","year":"1996","journal-title":"Proceedings of the National Academy of Sciences of the USA"},{"key":"e_1_2_1_33_1","volume-title":"SCA '04: Proceedings of the 2004 ACM SIGGRAPH\/Eurographics Symposium on Computer Animation. ACM Press","author":"Shah M."},{"key":"e_1_2_1_34_1","unstructured":"Shewchuk J. R. 1994. An introduction to the conjugate gradient method without the agonizing pain. Go online to http:\/\/www.cs.cmu.edu\/quake-papers\/painless-conjugate-gradient.pdf.  Shewchuk J. R. 1994. An introduction to the conjugate gradient method without the agonizing pain. Go online to http:\/\/www.cs.cmu.edu\/quake-papers\/painless-conjugate-gradient.pdf."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/0021-9991(88)90177-5"},{"key":"e_1_2_1_36_1","volume-title":"Proceedings of SIGGRAPH 99. Computer Graphics Proceedings, Annual Conference Series. 121--128","author":"Stam J.","year":"1999"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcph.1999.6205"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008036829907"},{"key":"e_1_2_1_39_1","volume-title":"Proceedings of the SIGGRAPH 2004 on Sketches & Applications. ACM Press","author":"Wiebe M.","year":"1862"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2002.1044520"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1122501.1122508","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1122501.1122508","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T16:08:37Z","timestamp":1750262917000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1122501.1122508"}},"subtitle":["A compact and versatile deformable surface representation"],"short-title":[],"issued":{"date-parts":[[2006,1]]},"references-count":40,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2006,1]]}},"alternative-id":["10.1145\/1122501.1122508"],"URL":"https:\/\/doi.org\/10.1145\/1122501.1122508","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,1]]},"assertion":[{"value":"2006-01-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}