Paper published in a book (Scientific congresses, symposiums and conference proceedings)
Comparing Broad-Phase Interaction Detection Algorithms for Multiphysics DEM Applications
Rousset, Alban; Mainassara Chekaraou, Abdoul Wahid; Liao, Yu-Chung et al.
2018In AIP Conference Proceedings of 15th International Conference of Numerical Analysis and Applied Mathematics (ICNAAM)
Peer reviewed
 

Files


Full Text
Abstract_Broadphase_XDEM.pdf
Publisher postprint (291.36 kB)
Request a copy

All documents in ORBilu are protected by a user license.

Send to



Details



Keywords :
broadphase; HPC; CD
Abstract :
[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, naively 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 operate 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.
Research center :
LuXDEM - University of Luxembourg: Luxembourg XDEM Research Centre
Disciplines :
Computer science
Author, co-author :
Rousset, Alban ;  University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Engineering Research Unit
Mainassara Chekaraou, Abdoul Wahid ;  University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Engineering Research Unit
Liao, Yu-Chung ;  University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Engineering Research Unit
Besseron, Xavier  ;  University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Engineering Research Unit
Varrette, Sébastien ;  University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC)
Peters, Bernhard ;  University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Engineering Research Unit
External co-authors :
no
Language :
English
Title :
Comparing Broad-Phase Interaction Detection Algorithms for Multiphysics DEM Applications
Publication date :
10 July 2018
Event name :
15th International Conference of Numerical Analysis and Applied Mathematics (ICNAAM 2017)
Event place :
Thessaloniki, Greece
Event date :
from 25-09-2017 to 30-09-2017
Audience :
International
Main work title :
AIP Conference Proceedings of 15th International Conference of Numerical Analysis and Applied Mathematics (ICNAAM)
Publisher :
American Institute of Physics, New York, United States - New York
Peer reviewed :
Peer reviewed
Focus Area :
Computational Sciences
Name of the research project :
Luxdem.LSDEM
Available on ORBilu :
since 14 September 2017

Statistics


Number of views
306 (67 by Unilu)
Number of downloads
23 (17 by Unilu)

OpenCitations
 
5

Bibliography


Similar publications



Contact ORBilu