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

dc.contributor.authorCapannini, Gabrieleen_US
dc.contributor.authorLarsson, Thomasen_US
dc.contributor.editorEnrico Gobbetti and Wes Bethelen_US
dc.date.accessioned2016-06-09T09:43:10Z
dc.date.available2016-06-09T09:43:10Z
dc.date.issued2016en_US
dc.description.abstractWe 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.en_US
dc.description.sectionheadersGeometryen_US
dc.description.seriesinformationEurographics Symposium on Parallel Graphics and Visualizationen_US
dc.identifier.doi10.2312/pgv.20161177en_US
dc.identifier.isbn978-3-03868-006-2en_US
dc.identifier.issn1727-348Xen_US
dc.identifier.pages1-10en_US
dc.identifier.urihttps://doi.org/10.2312/pgv.20161177en_US
dc.identifier.urihttps://diglib.eg.org:443/handle/10
dc.publisherThe Eurographics Associationen_US
dc.subjectF.2.2 [Analysis Of Algorithms And Problem Complexity]en_US
dc.subjectNonnumerical Algorithms and Problemsen_US
dc.subjectGeometrical problems and computationsen_US
dc.subjecten_US
dc.subjectI.3.6 [Computer Graphics]en_US
dc.subjectMethodology and Techniquesen_US
dc.subjectGraphics data structuresen_US
dc.titleAdaptive Collision Culling for Large-Scale Simulations by a Parallel Sweep and Prune Algorithmen_US
Files
Original bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
001-010.pdf
Size:
4.75 MB
Format:
Adobe Portable Document Format