mdh.sePublikationer
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Adaptive Collision Culling for Massive Simulations by a Parallel and Context-Aware Sweep and Prune Algorithm
Mälardalens högskola, Akademin för innovation, design och teknik, Inbyggda system.
Mälardalens högskola, Akademin för innovation, design och teknik, Inbyggda system.ORCID-id: 0000-0002-1550-0994
2018 (Engelska)Ingår i: IEEE Transactions on Visualization and Computer Graphics, ISSN 1077-2626, E-ISSN 1941-0506, Vol. 4, nr 7, s. 2064-2077Artikel i tidskrift (Refereegranskat) 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.

Ort, förlag, år, upplaga, sidor
2018. Vol. 4, nr 7, s. 2064-2077
Nyckelord [en]
Collision detection, Simulation, Parallel algorithms, Multicore processing, Multithreading, Tree data structures, Sorting
Nationell ämneskategori
Datorsystem
Identifikatorer
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
Projekt
RALF3 - Software for Embedded High Performance ArchitecturesTillgänglig från: 2018-04-10 Skapad: 2018-04-10 Senast uppdaterad: 2018-06-14Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

Förlagets fulltextScopus

Personposter BETA

Larsson, Thomas B

Sök vidare i DiVA

Av författaren/redaktören
Capannini, GabrieleLarsson, Thomas B
Av organisationen
Inbyggda system
I samma tidskrift
IEEE Transactions on Visualization and Computer Graphics
Datorsystem

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetricpoäng

doi
urn-nbn
Totalt: 37 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf