Efficient BVH-based Collision Detection Scheme with Ordering and Restructuring

by Xinlei Wang1, Min Tang1, 3, Dinesh Manocha2, and Ruofeng Tong1

1 - Zhejiang University, China

2 - University of North Carolina at Chapel Hill, USA

3 - Alibaba-Zhejiang University Joint Institute of Frontier Technologies, China


We present a fast and robust BVH-based collision detection scheme on GPU. By efficiently ordering and restructuring BVHs and BVTT fronts, our approach addresses the problem of inefficient caching on GPU and performance drop due to model deformations. Our techniques are based on the use of histogram sort and an auxiliary structure BVTT front log, through which we analyze the dynamic status of BVTT front and BVH quality. Our approach efficiently handles inter- and intra-object collisions and performs especially well in simulations where there is considerable spatio-temporal coherence. The benchmark results demonstrate that our approach is significantly faster than the previous BVH-based method, and also outperforms other state-of-the-art spatial subdivision schemes in terms of speed.



Xinlei Wang, Min Tang, Dinesh Manocha, Ruofeng Tong, Efficient BVH-based Collision Detection Scheme with Ordering and Restructuring, Computer Graphics Forum, 37(2): 227-237, (Proceedings of Eurographics), 2018.

      author = {Wang, Xinlei and Tang, Min and Manocha, Dinesh and Tong, Ruofeng},
      title = {Efficient {BVH}-based Collision Detection Scheme with Ordering and Restructuring},
      journal = {Computer Graphics Forum (Proceedings of Eurographics 2018)},
      volume = {37},
      number = {2},
      pages = {227--237},
      year = {2018},

Source Code


Related Links

I-Cloth: Incremental Collision Handling for GPU-Based Interactive Cloth Simulation

I-Cloth: API for fast and reliable cloth simulation with CUDA

PSCC: Parallel Self-Collision Culling with Spatial Hashing on GPUs

Accurate Self-Collision Detection Using Enhanced Dual-Cone Method

CAMA: Contact-Aware Matrix Assembly with Unified Collision Handling for GPU-based Cloth Simulation

A GPU-based Streaming Algorithm for High-Resolution Cloth Simulation

UNC dynamic model benchmark repository

Collision-Streams: Fast GPU-based Collision Detection for Deformable Models

Fast Continuous Collision Detection using Deforming Non-Penetration Filters

Interactive Continuous Collision Detection between Deformable Models using Connectivity-Based Culling

MCCD: Multi-Core Collision Detection between Deformable Models using Front-Based Decomposition

Fast Collision Detection for Deformable Models using Representative-Triangles

DeformCD: Collision Detection between Deforming Objects

Self-CCD: Continuous Collision Detection for Deforming Objects

Interactive Collision Detection between Deformable Models using Chromatic Decomposition

Fast Proximity Computation Among Deformable Models using Discrete Voronoi Diagrams

CULLIDE: Interactive Collision Detection between Complex Models using Graphics Hardware

RCULLIDE: Fast and Reliable Collision Culling using Graphics Processors

Quick-CULLIDE: Efficient Inter- and Intra-Object Collision Culling using Graphics Hardware

Collision Detection



All benchmarks are from the UNC Dynamic Scene Benchmarks collection. The project is supported in part by the National Key Research and Development Program (2017YFB1002700), NSFC (61572423, 61572424, 61732015), the Science and Technology Project of Zhejiang Province (2018C01080), and Zhejiang Provincial NSFC (LZ16F020003).