{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,14]],"date-time":"2026-04-14T22:06:53Z","timestamp":1776204413618,"version":"3.50.1"},"reference-count":46,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2014,11,19]],"date-time":"2014-11-19T00:00:00Z","timestamp":1416355200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000145","name":"Division of Information and Intelligent Systems","doi-asserted-by":"publisher","award":["IIS-1253598, CNS-1218432, IIS-1407282, CCF-1423064"],"award-info":[{"award-number":["IIS-1253598, CNS-1218432, IIS-1407282, CCF-1423064"]}],"id":[{"id":"10.13039\/100000145","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000144","name":"Division of Computer and Network Systems","doi-asserted-by":"publisher","award":["IIS-1253598, CNS-1218432, IIS-1407282, CCF-1423064"],"award-info":[{"award-number":["IIS-1253598, CNS-1218432, IIS-1407282, CCF-1423064"]}],"id":[{"id":"10.13039\/100000144","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["IIS-1253598, CNS-1218432, IIS-1407282, CCF-1423064"],"award-info":[{"award-number":["IIS-1253598, CNS-1218432, IIS-1407282, CCF-1423064"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2014,11,19]]},"abstract":"<jats:p>\n            We introduce a new method for fluid simulation on high-resolution adaptive grids which rivals the throughput and parallelism potential of methods based on uniform grids. Our enabling contribution is\n            <jats:italic>SPGrid<\/jats:italic>\n            , a new data structure for compact storage and efficient stream processing of sparsely populated uniform Cartesian grids. SPGrid leverages the extensive hardware acceleration mechanisms inherent in the x86 Virtual Memory Management system to deliver sequential and stencil access bandwidth comparable to dense uniform grids. Second, we eschew tree-based adaptive data structures in favor of storing simulation variables in a pyramid of sparsely populated uniform grids, thus avoiding the cost of indirect memory access associated with pointer-based representations. We show how the costliest algorithmic kernels of fluid simulation can be implemented as a composition of two kernel types: (a) stencil operations on a single sparse uniform grid, and (b) structured data transfers between\n            <jats:italic>adjacent<\/jats:italic>\n            levels of resolution, even when modeling non-graded octrees. Finally, we demonstrate an adaptive multigrid-preconditioned Conjugate Gradient solver that achieves resolution-independent convergence rates while admitting a lightweight implementation with a modest memory footprint. Our method is complemented by a new interpolation scheme that reduces dissipative effects and simplifies dynamic grid adaptation. We demonstrate the efficacy of our method in end-to-end simulations of smoke flow.\n          <\/jats:p>","DOI":"10.1145\/2661229.2661269","type":"journal-article","created":{"date-parts":[[2014,11,18]],"date-time":"2014-11-18T14:21:03Z","timestamp":1416320463000},"page":"1-12","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":117,"title":["SPGrid"],"prefix":"10.1145","volume":"33","author":[{"given":"Rajsekhar","family":"Setaluri","sequence":"first","affiliation":[{"name":"University of Wisconsin - Madison"}]},{"given":"Mridul","family":"Aanjaneya","sequence":"additional","affiliation":[{"name":"University of Wisconsin - Madison"}]},{"given":"Sean","family":"Bauer","sequence":"additional","affiliation":[{"name":"University of Wisconsin - Madison"}]},{"given":"Eftychios","family":"Sifakis","sequence":"additional","affiliation":[{"name":"University of Wisconsin - Madison"}]}],"member":"320","published-online":{"date-parts":[[2014,11,19]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1275808.1276437"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/MCG.1984.276141"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2461912.2461982"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2009.01639.x"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1833349.1778784"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcp.2011.12.001"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1964921.1964977"},{"key":"e_1_2_2_8_1","volume-title":"SCA '07","author":"Chentanez N."},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2451236.2451243"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1730804.1730807"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1507149.1507152"},{"key":"e_1_2_2_12_1","volume-title":"-P","author":"Desbrun M.","year":"1996"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/74334.74351"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2485895.2485897"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/383259.383260"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073368.1073405"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2014.2307873"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/344779.344899"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2366145.2366167"},{"key":"e_1_2_2_20_1","volume-title":"SCA '10","author":"Goswami P."},{"key":"e_1_2_2_21_1","doi-asserted-by":"crossref","unstructured":"Harlow F. H. and Welch J. E. 1965. Numerical calculation of time-dependent viscous incompressible flow of fluid with free surface. Physics of Fluids (1958-1988) 8 12.  Harlow F. H. and Welch J. E. 1965. Numerical calculation of time-dependent viscous incompressible flow of fluid with free surface. Physics of Fluids (1958-1988) 8 12.","DOI":"10.1063\/1.1761178"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1122501.1122508"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1179352.1141959"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1179352.1141961"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1186562.1015745"},{"key":"e_1_2_2_26_1","first-page":"2006","article-title":"Spatially adaptive techniques for level set methods and incompressible flow","volume":"35","author":"Losasso F.","year":"2005","journal-title":"Computers and Fluids"},{"key":"e_1_2_2_27_1","volume-title":"SCA '10","author":"McAdams A."},{"key":"e_1_2_2_28_1","volume-title":"SCA '03","author":"M\u00fcller M."},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2037826.2037894"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487228.2487235"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1964921.1964978"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10915-005-9062-8"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1289603.1289607"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.compfluid.2013.04.027"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1187112.1187280"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1111\/1467-8659.00687"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1186822.1073282"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1599470.1599502"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1964921.1964976"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/311535.311548"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcph.1998.6106"},{"key":"e_1_2_2_42_1","volume-title":"SCA '08 Posters.","author":"Tan J."},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1141911.1141929"},{"key":"e_1_2_2_44_1","unstructured":"Trottenberg U. Oosterlee C. W. and Schuller A. 2001. Multigrid. Academic Press.   Trottenberg U. Oosterlee C. W. and Schuller A. 2001. Multigrid . Academic Press."},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1186822.1073298"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2461912.2461999"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2661229.2661269","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2661229.2661269","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:13:05Z","timestamp":1750227185000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2661229.2661269"}},"subtitle":["a sparse paged grid structure applied to adaptive smoke simulation"],"short-title":[],"issued":{"date-parts":[[2014,11,19]]},"references-count":46,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2014,11,19]]}},"alternative-id":["10.1145\/2661229.2661269"],"URL":"https:\/\/doi.org\/10.1145\/2661229.2661269","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,11,19]]},"assertion":[{"value":"2014-11-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}