Bulk-synchronous parallel simultaneous BVH traversal for collision detection on GPUs

Abstract

© 2018 Association for Computing Machinery. Simultaneous BVH traversal, as a dynamic task of pair-wise proximity tests, poses several challenges in terms of parallelization using GPUs. It isahighly dynamic and data-dependent problem which can induce control-flow divergence and inefficient data-access patterns. We present a simple solution using the bulk-synchronous parallel model to ensure a uniform mode of execution, and balanced workloads across GPU threads. The method is easy to implement, fast and operates entirely on the GPU by relying on a topology-centred work expansion scheme to ensure large concurrent workloads. We demonstrate speedups of upto 7.1× over the widely used "streams" model for GPU based parallel collision detection.