{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,18]],"date-time":"2026-08-18T01:43:40Z","timestamp":1787017420729,"version":"3.56.0"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2022,11,30]],"date-time":"2022-11-30T00:00:00Z","timestamp":1669766400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["SFB1120"],"award-info":[{"award-number":["SFB1120"]}],"id":[{"id":"10.13039\/501100001659","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":[[2022,12]]},"abstract":"<jats:p>We present a new octree-based neighborhood search method for SPH simulation. A speedup of up to 1.9x is observed in comparison to state-of-the-art methods which rely on uniform grids. While our method focuses on maximizing performance in fixed-radius SPH simulations, we show that it can also be used in scenarios where the particle support radius is not constant thanks to the adaptive nature of the octree acceleration structure.<\/jats:p>\n                  <jats:p>Neighborhood search methods typically consist of an acceleration structure that prunes the space of possible particle neighbor pairs, followed by direct distance comparisons between the remaining particle pairs. Previous works have focused on minimizing the number of comparisons. However, in an effort to minimize the actual computation time, we find that distance comparisons exhibit very high throughput on modern CPUs. By permitting more comparisons than strictly necessary, the time spent on preparing and searching the acceleration structure can be reduced, yielding a net positive speedup. The choice of an octree acceleration structure, instead of the uniform grid typically used in fixed-radius methods, ensures balanced computational tasks. This benefits both parallelism and provides consistently high computational intensity for the distance comparisons. We present a detailed account of high-level considerations that, together with low-level decisions, enable high throughput for performance-critical parts of the algorithm.<\/jats:p>\n                  <jats:p>Finally, we demonstrate the high performance of our algorithm on a number of large-scale fixed-radius SPH benchmarks and show in experiments with a support radius ratio up to 3 that our method is also effective in multi-resolution SPH simulations.<\/jats:p>","DOI":"10.1145\/3550454.3555523","type":"journal-article","created":{"date-parts":[[2022,11,30]],"date-time":"2022-11-30T16:19:07Z","timestamp":1669825147000},"page":"1-13","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":19,"title":["Fast Octree Neighborhood Search for SPH Simulations"],"prefix":"10.1145","volume":"41","author":[{"given":"Jos\u00e9 Antonio","family":"Fern\u00e1ndez-Fern\u00e1ndez","sequence":"first","affiliation":[{"name":"RWTH Aachen University, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lukas","family":"Westhofen","sequence":"additional","affiliation":[{"name":"RWTH Aachen University, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Fabian","family":"L\u00f6schner","sequence":"additional","affiliation":[{"name":"RWTH Aachen University, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Stefan Rhys","family":"Jeske","sequence":"additional","affiliation":[{"name":"RWTH Aachen University, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andreas","family":"Longva","sequence":"additional","affiliation":[{"name":"RWTH Aachen University, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jan","family":"Bender","sequence":"additional","affiliation":[{"name":"RWTH Aachen University, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,11,30]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1276377.1276437"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.13890"},{"key":"e_1_2_2_3_1","unstructured":"Jan Bender et al. 2022. SPlisHSPlasH Library. https:\/\/github.com\/InteractiveComputerGraphics\/SPlisHSPlasH."},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2016.2578335"},{"key":"e_1_2_2_5_1","volume-title":"Turbulent micropolar SPH fluids with foam","author":"Bender Jan","year":"2018","unstructured":"Jan Bender, Dan Koschier, Tassilo Kugelstadt, and Marcel Weiler. 2018. Turbulent micropolar SPH fluids with foam. IEEE transactions on visualization and computer graphics 25, 6 (2018), 2284--2295."},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2020.3004245"},{"key":"e_1_2_2_7_1","unstructured":"Mathieu Desbrun and Marie-Paule Cani. 1999. Space-time adaptive simulation of highly deformable substances. Ph. D. Dissertation. INRIA."},{"key":"e_1_2_2_8_1","first-page":"12","article-title":"Neighbour lists in smoothed particle hydrodynamics","volume":"67","author":"Dom\u00ednguez J. M.","year":"2010","unstructured":"J. M. Dom\u00ednguez, A. J. C. Crespo, M. G\u00f3mez-Gesteira, and J. C. Marongiu. 2010. Neighbour lists in smoothed particle hydrodynamics. International Journal for Numerical Methods in Fluids 67, 12 (nov 2010), 2026--2042.","journal-title":"International Journal for Numerical Methods in Fluids"},{"key":"e_1_2_2_9_1","volume-title":"Smoothed particle hydrodynamics: theory and application to non-spherical stars. Monthly notices of the royal astronomical society 181, 3","author":"Gingold Robert A","year":"1977","unstructured":"Robert A Gingold and Joseph J Monaghan. 1977. Smoothed particle hydrodynamics: theory and application to non-spherical stars. Monthly notices of the royal astronomical society 181, 3 (1977), 375--389."},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3386569.3392431"},{"key":"e_1_2_2_11_1","volume-title":"Particle simulation using CUDA. NVIDIA whitepaper 6","author":"Green Simon","year":"2010","unstructured":"Simon Green. 2010. Particle simulation using CUDA. NVIDIA whitepaper 6 (2010), 121--128."},{"key":"e_1_2_2_12_1","volume-title":"Computer Graphics and Visual Computing (CGVC)","author":"Gross Julian","unstructured":"Julian Gross, Marcel K\u00f6ster, and Antonio Kr\u00fcger. 2019. Fast and Efficient Nearest Neighbor Search for Particle Simulations. In Computer Graphics and Visual Computing (CGVC). The Eurographics Association."},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1321261.1321271"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1086\/191344"},{"key":"e_1_2_2_16_1","volume-title":"A parallel SPH implementation on multi-core CPUs. Comput. Graph. Forum 30 (03","author":"Ihmsen Markus","year":"2011","unstructured":"Markus Ihmsen, Nadir Akinci, Markus Becker, and Matthias Teschner. 2011. A parallel SPH implementation on multi-core CPUs. Comput. Graph. Forum 30 (03 2011), 99--112."},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2013.105"},{"key":"e_1_2_2_18_1","unstructured":"Markus Ihmsen Jens Orthmann Barbara Solenthaler Andreas Kolb and Matthias Teschner. 2014b. SPH Fluids in Computer Graphics."},{"key":"e_1_2_2_19_1","volume-title":"A Survey on SPH Methods in Computer Graphics. Computer Graphics Forum 41, 2","author":"Koschier Dan","year":"2022","unstructured":"Dan Koschier, Jan Bender, Barbara Solenthaler, and Matthias Teschner. 2022. A Survey on SPH Methods in Computer Graphics. Computer Graphics Forum 41, 2 (2022)."},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3480142"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1146\/annurev.aa.30.090192.002551"},{"key":"e_1_2_2_22_1","unstructured":"Guy M Morton. 1966. A computer oriented geodetic data base and a new technique in file sequencing. (1966)."},{"key":"e_1_2_2_23_1","first-page":"6","article-title":"An Implicit SPH Formulation for Incompressible Linearly Elastic Solids","volume":"37","author":"Peer Andreas","year":"2017","unstructured":"Andreas Peer, Christoph Gissler, Stefan Band, and Matthias Teschner. 2017. An Implicit SPH Formulation for Incompressible Linearly Elastic Solids. Computer Graphics Forum 37, 6 (dec 2017), 135--148.","journal-title":"Computer Graphics Forum"},{"key":"e_1_2_2_24_1","volume-title":"Advances in Visual Computing","author":"Pelfrey Brandon","unstructured":"Brandon Pelfrey and Donald House. 2010. Adaptive Neighbor Pairing for Smoothed Particle Hydrodynamics. In Advances in Visual Computing. Springer Berlin Heidelberg, 192--201."},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2010324.1964976"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.12578"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3203188"},{"key":"e_1_2_2_28_1","first-page":"1","article-title":"Computer \"Experiments\" on Classical Fluids","volume":"159","author":"Verlet Loup","year":"1967","unstructured":"Loup Verlet. 1967. Computer \"Experiments\" on Classical Fluids. I. Thermodynamical Properties of Lennard-Jones Molecules. Physical Review 159, 1 (jul 1967), 98--103.","journal-title":"I. Thermodynamical Properties of Lennard-Jones Molecules. Physical Review"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1002\/fld.1761"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.13349"},{"key":"e_1_2_2_31_1","volume-title":"Draper","author":"Willis James S.","year":"2018","unstructured":"James S. Willis, Matthieu Schaller, Pedro Gonnet, Richard G. Bower, and Peter W. Draper. 2018. An Efficient SIMD Implementation of Pseudo-Verlet Lists for Neighbour Interactions in Particle-Based Codes. Advances in Parallel Computing 32 (2018)."},{"key":"e_1_2_2_32_1","unstructured":"Rene Winchenbach Hendrik Hochstetter and Andreas Kolb. 2016. Constrained Neighbor Lists for SPH-based Fluid Simulations."},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3072959.3073713"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.14090"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3363555"},{"key":"e_1_2_2_36_1","volume-title":"A GPU-accelerated smoothed particle hydrodynamics (SPH) model for the shallow water equations. Environmental Modelling & Software 75 (jan","author":"Xia Xilin","year":"2016","unstructured":"Xilin Xia and Qiuhua Liang. 2016. A GPU-accelerated smoothed particle hydrodynamics (SPH) model for the shallow water equations. Environmental Modelling & Software 75 (jan 2016), 28--43."}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3550454.3555523","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3550454.3555523","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T13:51:44Z","timestamp":1750168304000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3550454.3555523"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,11,30]]},"references-count":35,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["10.1145\/3550454.3555523"],"URL":"https:\/\/doi.org\/10.1145\/3550454.3555523","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,11,30]]},"assertion":[{"value":"2022-11-30","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}