EFFICIENT AND ACCURATE COLLISION DETECTION FOR GRANULAR FLOW SIMULATION

In this paper, we present efficient algorithms for contact detection a nd accurate contact mechanics in granular flow simulations. The contac t detection algorithms that we present are applicable to arbitrarily s haped rigid particles in a variety of environments including interacti ve as well as non-interactive. We present a very accurate force displa cement model for characterizing the behavior of particles in contact. These algorithms are applied to granular flow simulations, in particul ar, soybean flow through an inclined chute. There are two phases of th is research, namely, the development of contact detection algorithms a nd the development of accurate contact mechanics based force-displacem ent models. In the first phase, the algorithms consist of two stages. The first stage involves finding candidate particles for possible cont acts. The second stage involves detecting precise contact between thes e candidates. In our application, the soybeans, which are approximatel y ellipsoidal in shape, are well approximated by a cluster of overlapp ing spheres. Detecting precise contact between spherical shapes is qui te simple and hence, in this paper, we will focus only on the first st age of the first phase. The primary data structure used in the first s tage is an octree. We build an octree for the enclosure/chute (contain ing the n particles) and use it in the algorithm for detecting possibl e contacts. The average time complexity of this stage of the first pha se is O(n) and the worst case is O(n log n). in phase two, we develop a very accurate force-displacement model for dealing with the contact mechanics of soybean Bow through an inclined chute. This model is a re asonably close approximation to the widely accepted Mindlin force-disp lacement model for elastic frictional contacts. Our force-displacement model accounts for normal and tangential direction contact forces act ing between particles and/or particles and the chute walls. We also pr esent examples of soybean flow simulations with fast contact detection and accurate contact mechanics. (C) 1998 Academic Press.