Reference : Comparing Broad-Phase Interaction Detection Algorithms for Multiphysics DEM Applications
Scientific congresses, symposiums and conference proceedings : Unpublished conference
Engineering, computing & technology : Computer science
Computational Sciences
http://hdl.handle.net/10993/32261
Comparing Broad-Phase Interaction Detection Algorithms for Multiphysics DEM Applications
English
Rousset, Alban mailto [University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Engineering Research Unit >]
Mainassara Chekaraou, Abdoul Wahid mailto [University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Engineering Research Unit >]
Liao, Yu-Chung mailto [University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Engineering Research Unit >]
Besseron, Xavier mailto [University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Engineering Research Unit >]
Varrette, Sébastien mailto [University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC) >]
Peters, Bernhard mailto [University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Engineering Research Unit >]
Sep-2017
Yes
Yes
International
V International Conference on Particle-Based Methods (PARTICLES 2017
from 26-09-2017 to 28-09-2017
Hannover
Germany
[en] broadphase ; HPC ; CD
[en] Collision detection is an ongoing source of research and optimization in many fields including video-games and
numerical simulations [6, 7, 8]. The goal of collision detection is to report a geometric contact when it is about to
occur or has actually occurred. Unfortunately, detailed and exact collision detection for large amounts of objects
represent an immense amount of computations, naivly n 2 operation with n being the number of objects [9]. To avoid
and reduce these expensive computations, the collision detection is decomposed in two phases as it shown on Figure 1:
the Broad-Phase and the Narrow-Phase.
In this paper, we focus on Broad-Phase algorithm in a large dynamic three-dimensional environment. We studied
two kinds of Broad-Phase algorithms: spatial partitioning and spatial sorting. Spatial partitioning techniques op-
erate by dividing space into a number of regions that can be quickly tested against each object. Two types of spatial
partitioning will be considered: grids and trees. The grid-based algorithms consist of a spatial partitioning processing
by dividing space into regions and testing if objects overlap the same region of space. And this reduces the number
of pairwise to test. The tree-based algorithms use a tree structure where each node spans a particular space area. This
reduces the pairwise checking cost because only tree leaves are checked. The spatial sorting based algorithm consists
of a sorted spatial ordering of objects. Axis-Aligned Bounding Boxes (AABBs) are projected onto x, y and z axes and
put into sorted lists. By sorting projection onto axes, two objects collide if and only if they collide on the three axes.
This axis sorting reduces the number of pairwise to tested by reducing the number of tests to perform to only pairs
which collide on at least one axis.
For this study, ten different Broad-Phase collision detection algorithms or framework have been considered. The
Bullet [6], CGAL [10, 11] frameworks have been used. Concerning the implemented algorithms most of them come
from papers or given implementation
University of Luxembourg: Luxembourg XDEM Research Centre - LuXDEM
Researchers ; Professionals
http://hdl.handle.net/10993/32261

File(s) associated to this reference

Fulltext file(s):

FileCommentaryVersionSizeAccess
Limited access
Abstract_Broadphase_XDEM.pdfPublisher postprint284.53 kBRequest a copy

Bookmark and Share SFX Query

All documents in ORBilu are protected by a user license.