Research And Implementation Of Real-time Continuous Collision Detection Algorithms For Blast-fragment Warhead Virtual Experiments

Collision Detection (CD) is one of the important research fields in Computer Graphics, fast and reliable Collision Detection is required by a lot of applications, including physically based animation, virtual environment, virtual characters and geometric modeling. With respect to the handling the motion of objects, they can be categorized into two types, Discrete Collision Detection (DCD) and Continuous Collision Detection (CCD). DCD algorithms are called at fixed time intervals to deal with the motion of objects. When objects are moving at a high speed or objects are thin, it may miss collisions or have interpenetrations. Meanwhile, CCD algorithms take the object's continuous motion into account and prevent the problems of DCD. However, CCD algorithms are much slower than DCD algorithms. How to accelerate the CCD has drawn much attention in recently.Based on a fast adaptive bisection approach, we present a real-time CCD algorithm for the Blast-fragment Warhead Virtual Experiments. Using a constant-velocity translation and rotation as arbitrary in-between motions, our algorithm meets the simulation needs more reasonable and accurate. Bounding sphere's continuous overlap test is firstly used to eliminate the fragments which have no collision with the destination and then the Oriented Bounding Box (OBB) continuous overlap test is applied to fast figure out the mesh which maybe has collision. The separating axis theorem is simplified to accelerate the OBB tree's continuous overlap. We also use points instead of triangles as the primitives to describe the fragments. So the Triangle-Triangle continuous intersection test is translated to Point-Triangle continuous intersection test, the method of elementary CCD to simplified and accelerated with small errors.Parallel computation is used in order to speed up the algorithm. First, we use a programming library named MPI to implement the distributed computation. Each fragment with the destination's CCD computation task in an interval should be distributed to the PC in the LAN and then the result is gathered for analysis and rendering. Second, GPU is used to accelerate the single task. We improved the serial CCD algorithms to the parallel algorithms for the GPU could be used to achieve a better performance.