Time-Critical Collision Detection Based On Particle Swarm Optimization

To satisfy the time-critical requirement of collision detection for the real time interactive systems, this dissertation first makes a summary of the currently used collision detection algorithms, and tries to consider the collision detection problem as a optimization search problem. Then the particle swarm optimization (PSO) is introduced to collision detection area. In this dissertation, it also proposes two novel framework which combines the exist techniques of hierarchy bounding volume and surface simplification with the PSO. We have tested the frameworks in our "Haptic Interactive System ". The new frameworks performance well for most models in virtual scene. The PSO may open a new door for interference detection methods in collision detection area.The main jobs of this dissertation are as following:Chapter one firstly describes the essential of collision detection problem, according which most the collision detection algorithms were classified into seven categories. Then a survey on hierarchy bounding volume, surface simplification and the particle swarm optimization is presented, which is the basis of the new frameworks.Chapter two presents a new rapid collision detection algorithm based on PSO, i.e. BASIC-PSO, which consider the AABB bounding volume of a triangle as a particle. In this chapter, the impact law of parameters "suppressed velocity","inertia weight","initial population size","contact status of model" are also tested. By the way, there also a new clipping algorithm of line against triangle window to solve the interference area between two space triangles is put forward.Chapter three proposes a new framework AABB-PSO for rapid collision detection. In this framework, first, the search space is reduced by using the technique AABB bounding volume; then obtains the interference triangles via BASIC-PSO. This framework develops the advantages of each technique of AABB BV and BASIC-PSO. We also test how the size of search space affects the algorithm.Chapter four designs another novel framework SURS-PSO for more efficient collision detection, with a litter geometrical error. In this framework, first, the search space is reduced by surface simplification during the pre-process and then the interference triangles are gained by BASIC-PSO. This framework takes the surface simplification's advantage of decreasing the triangles dramatically with litter geometry error.Chapter five implements two accelerated techniques. One is a special and new technique based on the neighborhoods of each triangle. The other is universal used in collision detection area based on the spatial and time coherence.Chapter six makes a brief description of the "Haptic Interactive System ", and introduces the main data structure & techniques of the former algorithms, and also gives some implement examples of the algorithms. We also develop an efficient algorithm for data exchange between Haptic Interactive System and QSlime2.0.Chapter seven makes a summary of my main contribution in the dissertation, and gives some advice for the further research about my new method.