{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,20]],"date-time":"2026-03-20T15:57:05Z","timestamp":1774022225748,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":49,"publisher":"ACM","funder":[{"name":"NSERC","award":["RGPIN-2023-05120"],"award-info":[{"award-number":["RGPIN-2023-05120"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,8,10]]},"DOI":"10.1145\/3721238.3730725","type":"proceedings-article","created":{"date-parts":[[2025,7,23]],"date-time":"2025-07-23T08:40:47Z","timestamp":1753260047000},"page":"1-10","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Stochastic Barnes-Hut Approximation for Fast Summation on the GPU"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6119-7500","authenticated-orcid":false,"given":"Abhishek","family":"Madan","sequence":"first","affiliation":[{"name":"University of Toronto, Toronto, Canada"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2130-3735","authenticated-orcid":false,"given":"Nicholas","family":"Sharp","sequence":"additional","affiliation":[{"name":"NVIDIA, Seattle, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2189-881X","authenticated-orcid":false,"given":"Francis","family":"Williams","sequence":"additional","affiliation":[{"name":"NVIDIA, New York, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9926-780X","authenticated-orcid":false,"given":"Ken","family":"Museth","sequence":"additional","affiliation":[{"name":"NVIDIA, Los Angeles, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7079-1934","authenticated-orcid":false,"given":"David I.W.","family":"Levin","sequence":"additional","affiliation":[{"name":"University of Toronto, Toronto, Canada and NVIDIA, Toronto, Canada"}]}],"member":"320","published-online":{"date-parts":[[2025,7,27]]},"reference":[{"key":"e_1_3_3_3_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/VISUAL.2001.964489"},{"key":"e_1_3_3_3_3_1","doi-asserted-by":"crossref","unstructured":"Gavin Barill Neil\u00a0G Dickson Ryan Schmidt David\u00a0IW Levin and Alec Jacobson. 2018. Fast winding numbers for soups and clouds. ACM Transactions on Graphics (TOG) 37 4 (2018) 1\u201312.","DOI":"10.1145\/3197517.3201337"},{"key":"e_1_3_3_3_4_1","doi-asserted-by":"crossref","unstructured":"Josh Barnes and Piet Hut. 1986. A hierarchical O (N log N) force-calculation algorithm. nature 324 6096 (1986) 446\u2013449.","DOI":"10.1038\/324446a0"},{"key":"e_1_3_3_3_5_1","doi-asserted-by":"crossref","unstructured":"Joshua\u00a0E Barnes. 1990. A modified tree code: Don\u2019t laugh; it runs. J. Comput. Phys. 87 1 (1990) 161\u2013170.","DOI":"10.1016\/0021-9991(90)90232-P"},{"key":"e_1_3_3_3_6_1","doi-asserted-by":"crossref","unstructured":"Jeroen B\u00e9dorf Evghenii Gaburov and Simon\u00a0Portegies Zwart. 2012. A sparse octree gravitational N-body code that runs entirely on the GPU processor. J. Comput. Phys. 231 7 (2012) 2825\u20132839.","DOI":"10.1016\/j.jcp.2011.12.024"},{"key":"e_1_3_3_3_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-12-384988-5.00006-1"},{"key":"e_1_3_3_3_8_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.12256"},{"key":"e_1_3_3_3_9_1","doi-asserted-by":"crossref","unstructured":"Leslie Greengard and Vladimir Rokhlin. 1987. A fast algorithm for particle simulations. Journal of computational physics 73 2 (1987) 325\u2013348.","DOI":"10.1016\/0021-9991(87)90140-9"},{"key":"e_1_3_3_3_10_1","unstructured":"Ga\u00ebl Guennebaud Beno\u00eet Jacob et\u00a0al. 2010. Eigen v3. http:\/\/eigen.tuxfamily.org."},{"key":"e_1_3_3_3_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2461217.2461219"},{"key":"e_1_3_3_3_12_1","doi-asserted-by":"crossref","unstructured":"Lars Hernquist. 1990. Vectorization of tree traversals. J. Comput. Phys. 87 1 (1990) 137\u2013147.","DOI":"10.1016\/0021-9991(90)90230-X"},{"key":"e_1_3_3_3_13_1","doi-asserted-by":"crossref","unstructured":"Alec Jacobson Ladislav Kavan and Olga Sorkine. 2013. Robust Inside-Outside Segmentation using Generalized Winding Numbers. ACM Trans. Graph. 32 4 (2013).","DOI":"10.1145\/2461912.2461916"},{"key":"e_1_3_3_3_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/15922.15902"},{"key":"e_1_3_3_3_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/258734.258769"},{"key":"e_1_3_3_3_16_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2009.01377.x"},{"key":"e_1_3_3_3_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3641519.3657395"},{"key":"e_1_3_3_3_18_1","doi-asserted-by":"crossref","unstructured":"Abhishek Madan and David\u00a0I.W. Levin. 2022. Fast Evaluation of Smooth Distance Constraints on Co-Dimensional Geometry. ACM Trans. Graph. 41 4 (2022).","DOI":"10.1145\/3528223.3530093"},{"key":"e_1_3_3_3_19_1","doi-asserted-by":"crossref","unstructured":"Junichiro Makino. 1990. Vectorization of a treecode. J. Comput. Phys. 87 1 (1990) 148\u2013160.","DOI":"10.1016\/0021-9991(90)90231-O"},{"key":"e_1_3_3_3_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/3384667"},{"key":"e_1_3_3_3_21_1","doi-asserted-by":"crossref","unstructured":"Don McLeish. 2011. A general method for debiasing a Monte Carlo estimator. Monte Carlo Methods and Applications 17 4 (2011) 301\u2013315. https:\/\/doi.org\/doi:10.1515\/mcma.2011.013","DOI":"10.1515\/mcma.2011.013"},{"key":"e_1_3_3_3_22_1","doi-asserted-by":"crossref","unstructured":"Nicholas Metropolis and Stanislaw Ulam. 1949. The monte carlo method. Journal of the American statistical association 44 247 (1949) 335\u2013341.","DOI":"10.1080\/01621459.1949.10483310"},{"key":"e_1_3_3_3_23_1","doi-asserted-by":"crossref","unstructured":"Zackary Misso Benedikt Bitterli Iliyan Georgiev and Wojciech Jarosz. 2022. Unbiased and consistent rendering using biased estimators. ACM Transactions on Graphics (TOG) 41 4 (2022) 1\u201313.","DOI":"10.1145\/3528223.3530160"},{"key":"e_1_3_3_3_24_1","doi-asserted-by":"crossref","unstructured":"Thomas M\u00fcller Fabrice Rousselle Alexander Keller and Jan Nov\u00e1k. 2020. Neural control variates. ACM Transactions on Graphics (TOG) 39 6 (2020) 1\u201319.","DOI":"10.1145\/3414685.3417804"},{"key":"e_1_3_3_3_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3450623.3464653"},{"key":"e_1_3_3_3_26_1","doi-asserted-by":"crossref","unstructured":"Ashish Myles Nico Pietroni and Denis Zorin. 2014. Robust Field-aligned Global Parametrization. ACM Trans. on Graphics - Siggraph 2014 33 4 (2014) Article No. 135. http:\/\/vcg.isti.cnr.it\/Publications\/2014\/MPZ14","DOI":"10.1145\/2601097.2601154"},{"key":"e_1_3_3_3_27_1","unstructured":"Lars Nyland Mark Harris and Jan Prins. 2007. Fast n-body simulation with cuda. GPU gems 3 (2007) 62\u201366."},{"key":"e_1_3_3_3_28_1","volume-title":"Monte Carlo theory, methods and examples","author":"Owen Art\u00a0B.","year":"2013","unstructured":"Art\u00a0B. Owen. 2013. Monte Carlo theory, methods and examples. https:\/\/artowen.su.domains\/mc\/."},{"key":"e_1_3_3_3_29_1","doi-asserted-by":"crossref","unstructured":"Steven\u00a0G Parker James Bigler Andreas Dietrich Heiko Friedrich Jared Hoberock David Luebke David McAllister Morgan McGuire Keith Morley Austin Robison et\u00a0al. 2010. Optix: a general purpose ray tracing engine. Acm transactions on graphics (tog) 29 4 (2010) 1\u201313.","DOI":"10.1145\/1778765.1778803"},{"key":"e_1_3_3_3_30_1","volume-title":"Physically based rendering: From theory to implementation","author":"Pharr Matt","year":"2023","unstructured":"Matt Pharr, Wenzel Jakob, and Greg Humphreys. 2023. Physically based rendering: From theory to implementation. MIT Press."},{"key":"e_1_3_3_3_31_1","doi-asserted-by":"crossref","unstructured":"Ante Qu and Doug\u00a0L James. 2021. Fast linking numbers for topology verification of loopy structures. ACM Trans. Graph. 40 4 (2021) 106\u20131.","DOI":"10.1145\/3450626.3459778"},{"key":"e_1_3_3_3_32_1","doi-asserted-by":"crossref","unstructured":"Alexander Rath Pascal Grittmann Sebastian Herholz Philippe Weier and Philipp Slusallek. 2022. EARS: Efficiency-Aware Russian Roulette and Splitting. ACM Transactions on Graphics (Proceedings of SIGGRAPH 2022) 41 4 Article 81 (jul 2022) 14\u00a0pages. https:\/\/doi.org\/10.1145\/3528223.3530168","DOI":"10.1145\/3528223.3530168"},{"key":"e_1_3_3_3_33_1","doi-asserted-by":"crossref","unstructured":"Chang-han Rhee and Peter\u00a0W Glynn. 2015. Unbiased estimation with square root convergence for SDE models. Operations Research 63 5 (2015) 1026\u20131043.","DOI":"10.1287\/opre.2015.1404"},{"key":"e_1_3_3_3_34_1","doi-asserted-by":"crossref","unstructured":"Damien Rioux-Lavoie Ryusuke Sugimoto T\u00fcmay \u00d6zdemir Naoharu\u00a0H Shimada Christopher Batty Derek Nowrouzezahrai and Toshiya Hachisuka. 2022. A monte carlo method for fluid simulation. ACM Transactions on Graphics (TOG) 41 6 (2022) 1\u201316.","DOI":"10.1145\/3550454.3555450"},{"key":"e_1_3_3_3_35_1","doi-asserted-by":"crossref","unstructured":"Rohan Sawhney and Keenan Crane. 2020. Monte Carlo geometry processing: A grid-free approach to PDE-based methods on volumetric domains. ACM Transactions on Graphics 39 4 (2020).","DOI":"10.1145\/3386569.3392374"},{"key":"e_1_3_3_3_36_1","doi-asserted-by":"crossref","unstructured":"Peter Shirley Changyaw Wang and Kurt Zimmerman. 1996. Monte carlo techniques for direct lighting calculations. ACM Transactions on Graphics (TOG) 15 1 (1996) 1\u201336.","DOI":"10.1145\/226150.226151"},{"key":"e_1_3_3_3_37_1","doi-asserted-by":"crossref","unstructured":"Ryusuke Sugimoto Terry Chen Yiti Jiang Christopher Batty and Toshiya Hachisuka. 2023. A practical walk-on-boundary method for boundary value problems. ACM Transactions on Graphics (TOG) 42 4 (2023) 1\u201316.","DOI":"10.1145\/3592109"},{"key":"e_1_3_3_3_38_1","unstructured":"L\u00e1szl\u00f3 Szirmay-Kalos Gy\u00f6rgy Antal and Mateu Sbert. 2005. Go with the Winners Strategy in Path Tracing. J. WSCG 13 2 (2005) 49\u201356. http:\/\/wscg.zcu.cz\/wscg2005\/Papers_2005\/Journal\/!WSCG2005_Journal_Final.pdf"},{"key":"e_1_3_3_3_39_1","first-page":"15","volume-title":"Proceedings of the Conference on High-Performance Graphics","author":"Vaidyanathan Karthik","year":"2019","unstructured":"Karthik Vaidyanathan, Sven Woop, and Carsten Benthin. 2019. Wide BVH traversal with a short stack. In Proceedings of the Conference on High-Performance Graphics. 15\u201319."},{"key":"e_1_3_3_3_40_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.13533"},{"key":"e_1_3_3_3_41_1","doi-asserted-by":"crossref","unstructured":"Ji\u0159\u00ed Vorba and Jaroslav K\u0159iv\u00e1nek. 2016. Adjoint-driven Russian Roulette and Splitting in Light Transport Simulation. ACM Trans. Graph. 35 4 Article 42 (July 2016) 11\u00a0pages. https:\/\/doi.org\/10.1145\/2897824.2925912","DOI":"10.1145\/2897824.2925912"},{"key":"e_1_3_3_3_42_1","doi-asserted-by":"publisher","DOI":"10.1111\/1467-8659.00508"},{"key":"e_1_3_3_3_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1186822.1073318"},{"key":"e_1_3_3_3_44_1","doi-asserted-by":"crossref","unstructured":"Yu-Chen Wang Yu-Ting Wu Tzu-Mao Li and Yung-Yu Chuang. 2021. Learning to cluster for rendering with many lights. ACM Transactions on Graphics (TOG) 40 6 (2021) 1\u201310.","DOI":"10.1145\/3478513.3480561"},{"key":"e_1_3_3_3_45_1","doi-asserted-by":"crossref","unstructured":"Francis Williams Jiahui Huang Jonathan Swartz Gergely Klar Vijay Thakkar Matthew Cong Xuanchi Ren Ruilong Li Clement Fuji-Tsang Sanja Fidler Eftychios Sifakis and Ken Museth. 2024. fVDB: A Deep-Learning Framework for Sparse Large-Scale and High-Performance Spatial Intelligence. ACM Transactions on Graphics (SIGGRAPH) 43 4 Article 133 (July 2024) 15\u00a0pages. https:\/\/doi.org\/10.1145\/3658226","DOI":"10.1145\/3658226"},{"key":"e_1_3_3_3_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3587423.3595511"},{"key":"e_1_3_3_3_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3105762.3105773"},{"key":"e_1_3_3_3_48_1","doi-asserted-by":"crossref","unstructured":"Chris Yu Caleb Brakensiek Henrik Schumacher and Keenan Crane. 2021a. Repulsive Surfaces. ACM Trans. Graph. 40 6 (2021).","DOI":"10.1145\/3478513.3480521"},{"key":"e_1_3_3_3_49_1","doi-asserted-by":"crossref","unstructured":"Chris Yu Henrik Schumacher and Keenan Crane. 2021b. Repulsive curves. ACM Transactions on Graphics (TOG) 40 2 (2021) 1\u201321.","DOI":"10.1145\/3439429"},{"key":"e_1_3_3_3_50_1","first-page":"27","volume-title":"Proceedings of the Conference on High-Performance Graphics","author":"Yuksel Cem","year":"2019","unstructured":"Cem Yuksel. 2019. Stochastic lightcuts. In Proceedings of the Conference on High-Performance Graphics. 27\u201332."}],"event":{"name":"SIGGRAPH Conference Papers '25: Special Interest Group on Computer Graphics and Interactive Techniques Conference Conference Papers","location":"Vancouver BC Canada","acronym":"SIGGRAPH Conference Papers '25","sponsor":["SIGGRAPH ACM Special Interest Group on Computer Graphics and Interactive Techniques"]},"container-title":["Proceedings of the Special Interest Group on Computer Graphics and Interactive Techniques Conference Conference Papers"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3721238.3730725","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,20]],"date-time":"2026-03-20T14:57:13Z","timestamp":1774018633000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3721238.3730725"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,27]]},"references-count":49,"alternative-id":["10.1145\/3721238.3730725","10.1145\/3721238"],"URL":"https:\/\/doi.org\/10.1145\/3721238.3730725","relation":{},"subject":[],"published":{"date-parts":[[2025,7,27]]},"assertion":[{"value":"2025-07-27","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}