Premium
A Hierarchical Grid Based Framework for Fast Collision Detection
Author(s) -
Fan Wenshan,
Wang Bin,
Paul JeanClaude,
Sun Jiaguang
Publication year - 2011
Publication title -
computer graphics forum
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.578
H-Index - 120
eISSN - 1467-8659
pISSN - 0167-7055
DOI - 10.1111/j.1467-8659.2011.02019.x
Subject(s) - computer science , grid , collision detection , parallel computing , collision , simd , parallelism (grammar) , scheme (mathematics) , hierarchical database model , algorithm , computational science , data mining , geometry , mathematical analysis , mathematics , computer security
We present a novel hierarchical grid based method for fast collision detection (CD) for deformable models on GPU architecture. A two‐level grid is employed to accommodate the non‐uniform distribution of practical scene geometry. A bottom‐to‐top method is implemented to assign the triangles into the hierarchical grid without any iteration while a deferred scheme is introduced to efficiently update the data structure. To address the issue of load balancing, which greatly influences the performance in SIMD parallelism, a propagation scheme which utilizes a parallel scan and a segmented scan is presented, distributing workloads evenly across all concurrent threads. The proposed method supports both discrete collision detection (DCD) and continuous collision detection (CCD) with self‐collision. Some typical benchmarks are tested to verify the effectiveness of our method. The results highlight our speedups over prior algorithms on different commodity GPUs.