mdh.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Adaptive Collision Culling for Massive Simulations by a Parallel and Context-Aware Sweep and Prune Algorithm
Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.ORCID iD: 0000-0002-1550-0994
2018 (English)In: IEEE Transactions on Visualization and Computer Graphics, ISSN 1077-2626, E-ISSN 1941-0506, Vol. 4, no 7, p. 2064-2077Article in journal (Refereed) Published
Abstract [en]

We present an improved 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 double-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. In addition, for scenarios that involves intense clustering along several axes simultaneously, we propose an enhancement that increases the context-awareness of the algorithm. By exploiting information gathered along three orthogonal axes, an efficient choice of what range query to perform can be made per object during run-time. Experimental results show high performance for up to millions of objects on modern multi-core CPUs.

Place, publisher, year, edition, pages
2018. Vol. 4, no 7, p. 2064-2077
Keywords [en]
Collision detection, Simulation, Parallel algorithms, Multicore processing, Multithreading, Tree data structures, Sorting
National Category
Computer Systems
Identifiers
URN: urn:nbn:se:mdh:diva-38938DOI: 10.1109/TVCG.2017.2709313ISI: 000433321900001Scopus ID: 2-s2.0-85047737311OAI: oai:DiVA.org:mdh-38938DiVA, id: diva2:1196684
Projects
RALF3 - Software for Embedded High Performance ArchitecturesAvailable from: 2018-04-10 Created: 2018-04-10 Last updated: 2018-06-14Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records BETA

Larsson, Thomas B

Search in DiVA

By author/editor
Capannini, GabrieleLarsson, Thomas B
By organisation
Embedded Systems
In the same journal
IEEE Transactions on Visualization and Computer Graphics
Computer Systems

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 9 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf