A Hierarchical Grid Based Framework for Fast Collision Detection

dc.contributor.authorFan, Wenshanen_US
dc.contributor.authorWang, Binen_US
dc.contributor.authorPaul, Jean-Claudeen_US
dc.contributor.authorSun, Jiaguangen_US
dc.contributor.editorMario Botsch and Scott Schaeferen_US
dc.date.accessioned2015-02-27T15:03:09Z
dc.date.available2015-02-27T15:03:09Z
dc.date.issued2011en_US
dc.description.abstractWe 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.en_US
dc.description.seriesinformationComputer Graphics Forumen_US
dc.identifier.doi10.1111/j.1467-8659.2011.02019.xen_US
dc.identifier.issn1467-8659en_US
dc.identifier.urihttps://doi.org/10.1111/j.1467-8659.2011.02019.xen_US
dc.publisherThe Eurographics Association and Blackwell Publishing Ltd.en_US
dc.subjectI.3.5 [Computer Graphics]en_US
dc.subjectComputational Geometry and Object Modelingen_US
dc.subjectGeometric algorithmsen_US
dc.subjectlanguagesen_US
dc.subjectand systemsen_US
dc.titleA Hierarchical Grid Based Framework for Fast Collision Detectionen_US
Files