Stochastic Barnes-Hut Approximation for Fast Summation on the GPU
arXiv:2506.02219 · doi:10.1145/3721238.3730725
Abstract
We present a novel stochastic version of the Barnes-Hut approximation. Regarding the level-of-detail (LOD) family of approximations as control variates, we construct an unbiased estimator of the kernel sum being approximated. Through several examples in graphics applications such as winding number computation and smooth distance evaluation, we demonstrate that our method is well-suited for GPU computation, capable of outperforming a GPU-optimized implementation of the deterministic Barnes-Hut approximation by achieving equal median error in up to 9.4x less time.
11 pages, 9 figures. To appear in ACM SIGGRAPH 2025
References in corpus (6)
- A sparse octree gravitational N-body code that runs entirely on the GPU processor
- A Practical Walk-on-Boundary Method for Boundary Value Problems
- fVDB: A Deep-Learning Framework for Sparse, Large-Scale, and High-Performance Spatial Intelligence
- Fast Linking Numbers for Topology Verification of Loopy Structures
- Neural Control Variates with Automatic Integration
- Fast Evaluation of Smooth Distance Constraints on Co-Dimensional Geometry