アンドリュー スミス,北村喜文
Towards the Realization of
Real-Time Collision Detection
Abstract:This technical report consists of 4 chapters which together describe my research activities during my stay at the Communication Systems Research Laboratory of the Advanced Telecommunications Research Institute from October of 1993 to December of 1994. The main focus of my research at ATR was on efficient algorithms for collision detection, and the flow of my research was as follows. Upon my arrival at ATR, work on efficient collision detection for polyhedral objects had been going on for about 6months. This original algorithm works by precomputing octrees for polyhedral objects, updating these objects' octrees at each time step and checking for interference of objects' updated octrees to localize possible collisions among the faces of the objects. This algorithm was shown to be quite efficient compared with the standard polyhedral collision detection method, where all combinations of different objects' faces must be tested for collision, but was still not effective for real-time collision detection in a virtual environment. Thus, my original project was to implement this algorithm on a parallel computer for real-time performance.
In starting work on parallelization of the original collision detection algorithm, I discovered various optimizations to the serial algorithm which made it roughly 5 times faster. These optimizations are described in the first chapter entitled "Optimization of Octree-based Collision Detection." Another problem with the original algorithm was that it had to move the octrees of objects at each time-step, which was quite time consuming. Thus, I investigated the problem of octree motion and discovered that not much research had been previously done on efficient algorithms for octree motion. Against this lack of research, I formulated various optimizations to the octree motion algorithm being used for collision detection, and these are described in the second chapter entitled "Efficient Algorithms for Octree Motion."
After implementing these optimizations to collision detection and octree motion, the collision detection was quite a bit more efficient but, unfortunately, still not entirely suitable for real-time applications. Thus, I formulated a new, more efficient collision detection algorithm. This algorithm was similar to the optimized collision detection algorithm (described in "Optimization of Octree Based Collision Detection" - the optimizations described in this chapter form the basis of the new algorithm) except that it eliminated the precomputation and update of octrees; instead, the algorithm used bounding boxes and octree-like spatial subdivision directly on the polyhedral faces to find the colliding faces. This
new algorithm was shown by experiments to be more efficient than the original collision detection algorithm, and was suitable for real-time applications. This new algorithm is described in the third chapter entitled "A Simple and Efficient Method for Accurate Collision Detection Among Deformable Polyhedral Objects in Arbitrary Motion." Finally, another version of this new algorithm, which does not miss collisions between time instants by testing for intersection of faces' swept space between time instants, was implemented. This version of the new algorithm was quite a bit slower (due to the necessity of computing interference between swept spaces) and did not have real-time performance; thus, parallelization of this algorithm was done and the last chapter, entitled "Parallelization of Collision Detection for Real-time Performance," describes the parallel algorithms and experimental results These four chapters together describe the research that I conducted while at ATR.