Adaptive Collision Culling for Large-Scale Simulations by a Parallel Sweep and Prune Algorithm

Capannini, Gabriele; Larsson, Thomas

Adaptive Collision Culling for Large-Scale Simulations by a Parallel Sweep and Prune Algorithm

Files

001-010.pdf (4.75 MB)

Date

2016

Authors

Capannini, Gabriele
Larsson, Thomas

Publisher

The Eurographics Association

Abstract

We propose a parallel Sweep and Prune algorithm that solves the dynamic box intersection problem in three dimensions. It scales up to very large datasets, which makes it suitable for broad phase collision detection in complex moving body simulations. Our algorithm gracefully handles high-density scenarios, including challenging clustering behavior, by using a dual-axis sweeping approach and a cache-friendly succinct data structure. The algorithm is realized by three parallel stages for sorting, candidate generation, and object pairing. By the use of temporal coherence, our sorting stage runs with close to optimal load balancing. Furthermore, our approach is characterized by a work-division strategy that relies on adaptive partitioning, which leads to almost ideal scalability. Experimental results show high performance for up to millions of objects on modern multi-core CPUs.

        @inproceedings{10.2312:pgv.20161177
,
booktitle = {Eurographics Symposium on Parallel Graphics and Visualization
},
editor = {Enrico Gobbetti and Wes Bethel
},
title = {{Adaptive Collision Culling for Large-Scale Simulations by a Parallel Sweep and Prune Algorithm
}},
author = {Capannini, Gabriele and 
Larsson, Thomas
},
year = {2016
},
publisher = {The Eurographics Association
},
ISSN = {1727-348X
},
ISBN = {978-3-03868-006-2
},
DOI = {10.2312/pgv.20161177
}
}