2025/02/28 by Vani Nagarajan, Rohan Gangaraju, Kirshanthan Sundararajah +2 · 1 voice · 1 citation
Computer Science · Engineering · #Computer Graphics and Visualization Techniques #Advanced Vision and Imaging #3D Shape Modeling and Analysis
paper · pdf · doi:10.1145/3710848.3710885
openalex publication_date 2025/02/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
The n-body problem involves calculating the effect of bodies on each other. n-body simulations are ubiquitous in the fields of physics and astronomy and notoriously computationally expensive. The naïve algorithm for n-body simulations has the prohibiting O(n2) time complexity. Reducing the time complexity to O(n · lg(n)), the tree-based Barnes-Hut algorithm approximates the effect of bodies beyond a certain threshold distance. Other than algorithmic improvements, extensive research has gone into accelerating n-body simulations on GPUs and multi-core systems. However, Barnes-Hut is a tree-traversal algorithm, which makes it a poor target for acceleration using traditional GPU shader cores. In contrast, recent work shows that, for tree-based computations, GPU ray-tracing (RT) cores dominate shader cores. In this work, we reformulate the Barnes-Hut algorithm as a ray-tracing problem and implement it with NVIDIA OptiX. Our evaluation shows that the resulting system, RT-BarnesHut, outperforms current state-of-the-art GPU-based implementations.