{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,20]],"date-time":"2026-03-20T18:03:44Z","timestamp":1774029824380,"version":"3.50.1"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"6","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2025,12,1]]},"abstract":"<jats:p>\n                    Prior research has demonstrated the efficacy of balanced trees as spatially adaptive grids for large-scale simulations. However, state-of-the-art methods for balanced tree construction are restricted by the iterative nature of the ripple effect, thus failing to fully leverage the massive parallelism offered by modern GPU architectures. We propose to reframe the construction of balanced trees as a process to merge\n                    <jats:italic toggle=\"yes\">N<\/jats:italic>\n                    -balanced Minimum Spanning Trees (\n                    <jats:italic toggle=\"yes\">N<\/jats:italic>\n                    -balanced MSTs) generated from a collection of seed points. To ensure optimal performance, we propose a stack-free parallel strategy for constructing all internal nodes of a specified\n                    <jats:italic toggle=\"yes\">N<\/jats:italic>\n                    -balanced MST. This approach leverages two 32-bit integer registers as buffers rather than relying on an integer array as a stack during construction, which helps maintain balanced workloads across different GPU threads. We then propose a dynamic update algorithm utilizing refinement counters for all internal nodes to enable parallel insertion and deletion operations of\n                    <jats:italic toggle=\"yes\">N<\/jats:italic>\n                    -balanced MSTs. This design achieves significant efficiency improvements compared to full reconstruction from scratch, thereby facilitating fluid simulations in handling dynamic moving boundaries. Our approach is fully compatible with GPU implementation and demonstrates up to an order-of-magnitude speedup compared to the state-of-the-art method [Wang et al. 2024]. The source code for the paper is publicly available at https:\/\/github.com\/peridyno\/peridyno.\n                  <\/jats:p>","DOI":"10.1145\/3763349","type":"journal-article","created":{"date-parts":[[2025,12,4]],"date-time":"2025-12-04T17:15:39Z","timestamp":1764868539000},"page":"1-15","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["A Stack-Free Parallel h-Adaptation Algorithm for Dynamically Balanced Trees on GPUs"],"prefix":"10.1145","volume":"44","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3113-7926","authenticated-orcid":false,"given":"Lixin","family":"Ren","sequence":"first","affiliation":[{"name":"Institute of Software, Chinese Academy of Sciences, Beijing, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8870-2482","authenticated-orcid":false,"given":"Xiaowei","family":"He","sequence":"additional","affiliation":[{"name":"Institute of Software, Chinese Academy of Sciences, Beijing, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7416-5110","authenticated-orcid":false,"given":"Shusen","family":"Liu","sequence":"additional","affiliation":[{"name":"Institute of Software, Chinese Academy of Sciences, Beijing, China"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-4578-9701","authenticated-orcid":false,"given":"Yuzhong","family":"Guo","sequence":"additional","affiliation":[{"name":"Institute of Software Chinese Academy of Sciences, Beijing, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2174-1428","authenticated-orcid":false,"given":"Enhua","family":"Wu","sequence":"additional","affiliation":[{"name":"Key Laboratory of System Software (Chinese Academy of Sciences) and SKLCS, Institute of Software, Chinese Academy of Sciences, Beijing, China"},{"name":"FST, University of Macau, Macao SAR, China"}]}],"member":"320","published-online":{"date-parts":[[2025,12,4]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3072959.3073625"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1342250.1357022"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3386569.3392460"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcp.2016.11.035"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/100791634"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11390-022-0331-x"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3550454.3555523"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2014.2307873"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3306346.3322939"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcp.2015.03.024"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcp.2018.04.039"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2012.47"},{"key":"e_1_2_2_13_1","unstructured":"Daniel Juenger Nico Iskos Yunsong Wang Jake Hemstad Christian Hundt and Nikolay Sakharnykh. 2023. Maximizing Performance with Massively Parallel Hash Maps on GPUs. https:\/\/developer.nvidia.com\/blog\/maximizing-performance-with-massively-parallel-hash-maps-on-gpus\/#entry-content-comments"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/2383795.2383801"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00371-014-1018-2"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.13558"},{"key":"e_1_2_2_17_1","volume-title":"Proceedings of the ACM SIGGRAPH\/Eurographics Symposium on Computer Animation","author":"Koschier Dan","year":"2016","unstructured":"Dan Koschier, Crispin Deul, and Jan Bender. 2016. Hierarchical hp-adaptive signed distance fields. In Proceedings of the ACM SIGGRAPH\/Eurographics Symposium on Computer Animation (Zurich, Switzerland) (SCA '16). Eurographics Association, Goslar, DEU, 189\u2013198."},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2009.01377.x"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2015.2476788"},{"key":"e_1_2_2_20_1","volume-title":"Exact and adaptive signed distance fields computation for rigid and deformablemodels on gpus","author":"Liu Fuchang","year":"2013","unstructured":"Fuchang Liu and Young J Kim. 2013. Exact and adaptive signed distance fields computation for rigid and deformablemodels on gpus. IEEE transactions on visualization and computer graphics 20, 5 (2013), 714\u2013725."},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.compfluid.2005.01.006"},{"key":"e_1_2_2_22_1","doi-asserted-by":"crossref","unstructured":"Frank Losasso Fr\u00e9d\u00e9ric Gibou and Ron Fedkiw. 2004. Simulating water and smoke with an octree data structure. In Acm siggraph 2004 papers. 457\u2013462.","DOI":"10.1145\/1186562.1015745"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2601097.2601152"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1201\/9781420035179"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cag.2017.05.024"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.002"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0021-9991(03)00298-5"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1882261.1866201"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2661229.2661269"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcp.2019.07.011"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/070681727"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cpc.2018.06.018"},{"key":"e_1_2_2_33_1","volume-title":"O'Hallaron","author":"Tu Tiankai","year":"2004","unstructured":"Tiankai Tu and David R. O'Hallaron. 2004. Balance Refinement of Massive Linear Octree Datasets. https:\/\/api.semanticscholar.org\/CorpusID:978691"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcp.2024.112823"},{"key":"e_1_2_2_35_1","volume-title":"Data-parallel octrees for surface reconstruction","author":"Zhou Kun","year":"2010","unstructured":"Kun Zhou, Minmin Gong, Xin Huang, and Baining Guo. 2010. Data-parallel octrees for surface reconstruction. IEEE transactions on visualization and computer graphics 17, 5 (2010), 669\u2013681."},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1409060.1409079"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3763349","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,20]],"date-time":"2026-03-20T17:02:13Z","timestamp":1774026133000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3763349"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12,1]]},"references-count":36,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2025,12,1]]}},"alternative-id":["10.1145\/3763349"],"URL":"https:\/\/doi.org\/10.1145\/3763349","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,12,1]]},"assertion":[{"value":"2025-05-23","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-08-09","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-12-04","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}