{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,30]],"date-time":"2025-08-30T16:52:26Z","timestamp":1756572746450,"version":"3.41.0"},"reference-count":20,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2020,8,26]],"date-time":"2020-08-26T00:00:00Z","timestamp":1598400000000},"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":["Proc. ACM Comput. Graph. Interact. Tech."],"published-print":{"date-parts":[[2020,8,26]]},"abstract":"<jats:p>We introduce the concurrent binary tree (CBT), a novel concurrent representation to build and update arbitrary binary trees in parallel. Fundamentally, our representation consists of a binary heap, i.e., a 1D array, that explicitly stores the sum-reduction tree of a bitfield. In this bitfield, each one-valued bit represents a leaf node of the binary tree encoded by the CBT, which we locate algorithmically using a binary-search over the sum-reduction. We show that this construction allows to dispatch down to one thread per leaf node and that, in turn, these threads can safely split and\/or remove nodes concurrently via simple bitwise operations over the bitfield. The practical benefit of CBTs lies in their ability to accelerate binary-tree-based algorithms with parallel processors. To support this claim, we leverage our representation to accelerate a longest-edge-bisection-based algorithm that computes and renders adaptive geometry for large-scale terrains entirely on the GPU. For this specific algorithm, the CBT accelerates processing speed linearly with the number of processors.<\/jats:p>","DOI":"10.1145\/3406186","type":"journal-article","created":{"date-parts":[[2021,3,23]],"date-time":"2021-03-23T17:45:26Z","timestamp":1616521526000},"page":"1-20","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Concurrent Binary Trees (with application to longest edge bisection)"],"prefix":"10.1145","volume":"3","author":[{"given":"Jonathan","family":"Dupuy","sequence":"first","affiliation":[{"name":"Unity Technologies"}]}],"member":"320","published-online":{"date-parts":[[2020,8,26]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2461912.2461982"},{"key":"e_1_2_2_2_1","volume-title":"Computer Graphics and Visual Computing (CGVC)","author":"Apetrei Ciprian","year":"2014","unstructured":"Ciprian Apetrei . 2014. Fast and Simple Agglomerative LBVH Construction . In Computer Graphics and Visual Computing (CGVC) , Rita Borgo and Wen Tang (Eds.). The Eurographics Association . https:\/\/doi.org\/10.2312\/cgvc. 2014 1206 10.2312\/cgvc.20141206 Ciprian Apetrei. 2014. Fast and Simple Agglomerative LBVH Construction. In Computer Graphics and Visual Computing (CGVC), Rita Borgo and Wen Tang (Eds.). The Eurographics Association. https:\/\/doi.org\/10.2312\/cgvc.20141206"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195907002495"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2008.01245.x"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/VISUAL.1997.663860"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0006-x"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2018323.2018333"},{"key":"e_1_2_2_8_1","unstructured":"Mark Harris et al. 2007. Optimizing parallel reduction in CUDA. Nvidia developer technology 2 4 (2007) 70.  Mark Harris et al. 2007. Optimizing parallel reduction in CUDA. Nvidia developer technology 2 4 (2007) 70."},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1006\/jsco.1994.1029"},{"key":"e_1_2_2_10_1","first-page":"033","volume-title":"Eurographics\/ACM SIGGRAPH Symposium on High Performance Graphics, Carsten Dachsbacher, Jacob Munkberg, and Jacopo Pantaleoni (Eds.). The Eurographics Association. https:\/\/doi.org\/10","author":"Karras Tero","year":"2012","unstructured":"Tero Karras . 2012 . Maximizing Parallelism in the Construction of BVHs, Octrees, and k-d Trees . In Eurographics\/ACM SIGGRAPH Symposium on High Performance Graphics, Carsten Dachsbacher, Jacob Munkberg, and Jacopo Pantaleoni (Eds.). The Eurographics Association. https:\/\/doi.org\/10 .2312\/EGGH\/HPG12\/ 033 - 037 10.2312\/EGGH Tero Karras. 2012. Maximizing Parallelism in the Construction of BVHs, Octrees, and k-d Trees. In Eurographics\/ACM SIGGRAPH Symposium on High Performance Graphics, Carsten Dachsbacher, Jacob Munkberg, and Jacopo Pantaleoni (Eds.). The Eurographics Association. https:\/\/doi.org\/10.2312\/EGGH\/HPG12\/033-037"},{"key":"e_1_2_2_11_1","unstructured":"Brano Kemen. 2009. Procedural terrain algorithm visualization. https:\/\/outerra.blogspot.com\/2009\/02\/procedural-terrain-algorithm.html  Brano Kemen. 2009. Procedural terrain algorithm visualization. https:\/\/outerra.blogspot.com\/2009\/02\/procedural-terrain-algorithm.html"},{"key":"e_1_2_2_12_1","volume-title":"Turner","author":"Lindstrom Peter","year":"1996","unstructured":"Peter Lindstrom , David Koller , William Ribarsky , Larry F. Hodges , Nick Faust , and Gregory A . Turner . 1996 . Real-Time, Continuous Level of Detail Rendering of Height Fields (SIGGRAPH '96). Association for Computing Machinery , New York, NY, USA, 109--118. https:\/\/doi.org\/10.1145\/237170.237217 10.1145\/237170.237217 Peter Lindstrom, David Koller, William Ribarsky, Larry F. Hodges, Nick Faust, and Gregory A. Turner. 1996. Real-Time, Continuous Level of Detail Rendering of Height Fields (SIGGRAPH '96). Association for Computing Machinery, New York, NY, USA, 109--118. https:\/\/doi.org\/10.1145\/237170.237217"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2002.1021577"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/0916014"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1002\/nme.1620200412"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/646014.677336"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8396(01)00039-5"},{"key":"#cr-split#-e_1_2_2_19_1.1","unstructured":"K. Weiss and L. De Floriani. 2011. Simplex and Diamond Hierarchies: Models and Applications. 2127--2155 pages. https:\/\/doi.org\/10.1111\/j. 1467-8659.2011.01853.x arXiv:https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1111\/j.1467-8659.2011.01853.x 10.1111\/j"},{"key":"#cr-split#-e_1_2_2_19_1.2","unstructured":"K. Weiss and L. De Floriani. 2011. Simplex and Diamond Hierarchies: Models and Applications. 2127--2155 pages. https:\/\/doi.org\/10.1111\/j. 1467-8659.2011.01853.x arXiv:https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1111\/j.1467-8659.2011.01853.x"},{"volume-title":"Eurographics Symposium on Parallel Graphics and Visualization","author":"Yalcin M. Adil","key":"e_1_2_2_20_1","unstructured":"M. Adil Yalcin , Kenneth Weiss , and Leila De Floriani . 2011. GPU Algorithms for Diamond-based Multiresolution Terrain Processing . In Eurographics Symposium on Parallel Graphics and Visualization , Torsten Kuhlen, Renato Pajarola, and Kun Zhou (Eds.). The Eurographics Association . https:\/\/doi.org\/10.2312\/EGPGV\/EGPGV11\/121-130 10.2312\/EGPGV M. Adil Yalcin, Kenneth Weiss, and Leila De Floriani. 2011. GPU Algorithms for Diamond-based Multiresolution Terrain Processing. In Eurographics Symposium on Parallel Graphics and Visualization, Torsten Kuhlen, Renato Pajarola, and Kun Zhou (Eds.). The Eurographics Association. https:\/\/doi.org\/10.2312\/EGPGV\/EGPGV11\/121-130"}],"container-title":["Proceedings of the ACM on Computer Graphics and Interactive Techniques"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406186","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406186","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:31:52Z","timestamp":1750195912000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406186"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8,26]]},"references-count":20,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,8,26]]}},"alternative-id":["10.1145\/3406186"],"URL":"https:\/\/doi.org\/10.1145\/3406186","relation":{},"ISSN":["2577-6193"],"issn-type":[{"type":"electronic","value":"2577-6193"}],"subject":[],"published":{"date-parts":[[2020,8,26]]},"assertion":[{"value":"2020-08-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}