A Hierarchical Grid Based Framework for Fast Collision Detection

Loading...
Thumbnail Image
Date
2011
Journal Title
Journal ISSN
Volume Title
Publisher
The Eurographics Association and Blackwell Publishing Ltd.
Abstract
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.
Description

        
@article{
10.1111:j.1467-8659.2011.02019.x
, journal = {Computer Graphics Forum}, title = {{
A Hierarchical Grid Based Framework for Fast Collision Detection
}}, author = {
Fan, Wenshan
and
Wang, Bin
and
Paul, Jean-Claude
and
Sun, Jiaguang
}, year = {
2011
}, publisher = {
The Eurographics Association and Blackwell Publishing Ltd.
}, ISSN = {
1467-8659
}, DOI = {
10.1111/j.1467-8659.2011.02019.x
} }
Citation