Fast Collision Detection Algorithms with Applications to Particle Flow
No Thumbnail Available
Date
1998
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Blackwell Publishers Ltd and the Eurographics Association
Abstract
In this paper, we present efficient algorithms for collision detection of arbitrarily shaped rigid moving objects in a variety of interactive as well as non-interactive environments. The algorithms primarily consist of two stages. The first stage involves finding candidate objects for possible collisions. The second stage involves detecting exact (within a prespecified tolerance) collision between these candidates. The primary data structure used in the algorithms is an octree. In the first stage, we build an octree for the enclosure containing the objects, which is used to detect possible collisions. Assuming spatial/temporal coherence i.e., that the particles move slowly or that the time sampling is fast enough, the average time complexity of this stage can be shown to be O(n) (excluding the time complexity for a one time octree construction), where n is the number of particles. In the second stage, we build a surface-octree for each object. If the objects are convex and assuming coherence, the expected time complexity to detect precise (within a prespecified tolerance) collision for each pair is a constant (excluding the time complexity for a one time surface-octree construction). Therefore, the overall expected time complexity for convex object collision detection is linear with respect to n. For the concave objects, complexity analysis is nontrivial to perform and instead we provide a very practical (almost linear time) algorithm. We apply our algorithms to particle flow simulations by simulating flow density conditions often arising in granular flows.
Description
@article{10.1111:1467-8659.00233,
journal = {Computer Graphics Forum},
title = {{Fast Collision Detection Algorithms with Applications to Particle Flow}},
author = {Vemuri, B. C. and Cao, Y. and Chen, L.},
year = {1998},
publisher = {Blackwell Publishers Ltd and the Eurographics Association},
ISSN = {1467-8659},
DOI = {10.1111/1467-8659.00233}
}