Research On Fast Collision Detection Algorithm Based On Parallelism

As a classic and critical problem in the areas of computer graphics, virtual reality, computer games, animation, computer-aided design, robotics and virtual manufacturing and other fields, collision detection has been more concerned about over the years. At present, most of the geometric models in virtual reality are composed of thousands of basic geometric elements. With the increase of the geometric complexity of virtual environment, the calculating complexity of collision detection greatly increased, and the interaction of complex scenes consumes a large amount of computer resources, so collision detection often becomes a bottleneck in virtual environment. So how to design an efficient collision detection algorithm to meet the real-time accuracy and universality has become a serious problem currently.With the rapid development of parallel computer, parallel technology has brought unprecedented opportunities and challenges for the researchers. There are so many parallel technologies have been used in collision detection algorithm, such as partition, pipelining, divide and conquer, symmetry breaking, MPI, OpenMP. But those technologies applied in collision detection are at the beginning.Concerning the requirements of real-time and accurate collision detection in interactive system, we had an in-depth study of parallel technology and proposed several parallel collision detection algorithms. Then we use two parallel technologies MPI and OpenMP to parallel the collision detection algorithm based on particle swarm and the collision detection algorithm based on spherical blend reconstruction, at the same time, we compare several existed parallel algorithms from two aspects of the time efficiency and resource consumption. Our paper includes the following contents:1) Parallel collision detection algorithm based on pipelining and divide-and-conquer: A parallel collision detection algorithm based on pipelining and divide-and-conquer is presented. The characteristic in this algorithm is as follows: at first, it builds Balance-BoxTrees for every objects in environment using divide-and-conquer technologies which are mostly primary technologies in parallel algorithm, then form traversing of a WorkTrees by traversing two BoxTrees and in this process it shares alike this task by each computer, also applies pipelining technologies which is also important in parallel algorithm and traversing the WorkTrees by dividing tenors. Because of the application of dividing tenors, our algorithm can apply multi-threads in tenors so that it can run on both single processor computer and multi-processor computer. So we can see the result about experiment data from Table 1 and Table 2 which can indicate the meaning about our research. As we use so many parallel technologies, this algorithm speeds up collision detection by a long way.2) Parallel collision detection algorithm based on mixed BVH and OpenMP: First we incorporate the merits of both AABB bounding box and bounding spheres to construct a hybrid bounding representation of arbitrary non-convex polyhedra (S-AABB) for attaining speed, and then use OpenMP parallel programming model to traversal the built hybrid bounding volume hierarchy, so further accelerate the collision detection algorithm. At the same time, our algorithm can run on both single processor computer and multi-processor computer.3) The comparison of the multiple parallel collision detection: We have shown that our two parallel algorithms are superior by comparing the four parallel collision detection algorithms such as MPI,Pipelining,OpenMP,SymmetryBreaking in terms of time efficiency, resource consumption and stability. Here MPI is the parallel collision detection algorithm based on MPI, Pipelining is the parallel collision detection algorithm based on pipelining, OpenMP is our first parallel collision detection algorithm based on OpenMP, SymmetryBreaking is our second parallel collision detection algorithm based on symmetry breaking.4) A new parallel collision detection algorithm based on mixed BVH and symmetry breaking: At first, we incorporate the merits of both AABB bounding box and bounding spheres to construct a hybrid bounding representation of arbitrary non-convex polyhedra (S-AABB) for attaining speed, especially the S-AABB is balanced using divide-and-conquer technologies which are mostly primary technologies in parallel algorithm. Then we apply Symmetry Breaking—k-Colouring technology which is also important in parallel algorithm in order to reduce diffrernt categories, and assign them to different processors; Also multi-thread is used in multi-processor computer. At last, experiments results have shown that our algorithm is advantageous over other current typical collision detection such as I-COLLIDE regarding efficiency and accuracy, so can meets the real-time and accurate requirements in complex interactive virtual environment.5) Parallel Collision Detection Algorithm Based on Temporal-spatial Coherence and MPI: We present an advanced algorithm which based on temporal-spatial coherence and spatial subdivision algorithm and adapt a parallel method based on MPI. At first, it subdivides the space into a series of voxels, compute the size and build the list of objects in the voxels by the state of the objects. It confirms the traversing orders of tree by using temporal-spatial coherence and dispatches every sub-task into sub-tenor by the parallel method based on MPI.This algorithm reduces the times of collision detection and the traversing depth of the bounding box'tree. The results of experiment prove that this method speeds up collision detection and guarantees its real-time performance.6) Parallel collision detection based on particle swarm optimization algorithm: It combines stochastic collision detection and particle swarm optimization (PSO) Algorithm. Firstly, the algorithmsamples primitive pairs within the models to construct a discrete binary search space for PSO, by which user can balance performance and detection quality. In order to handle the deformation of models in the object space, a particle update process was added in the beginning of every time step, which handles the dynamic environments problem in search space caused by deformation. The algorithm is also very general that makes no assumption about the input model, which can be without topology information or even be"polygon soups". It doesn't need to store additional data structures either, so the memory cost is relative low. At last, we use two techniques MPI and OpenMP to parallel the above algorithm, so further improve the efficiency of the collision detection.7) Parallel collision detection based on spherical blend reconstruction: We present a novel collision detection algorithm based on spherical blend skinning. A procedure is presented for refitting of bounding spheres for spherical blend skinning with sublinear time complexity, to construct rotation bound by a quaternion. This refitting operation is an extension of the refitting for linear blending. To complete decomposes from spherical blending to linear by rotational component. Although it is of course a little more difficult than in the linear case, the resulting algorithm is almost as easy to implement and the computation complexity of the presented algorithm is almost the same as that of the linear version.8) Computing distance of two objects in space is a important aspect. Improving computing speed of distance of two convex polyhedrons can speed up collision detection. With convex Bounding volume hierarchies (BVHs) express convex polyhedron, conversing distance problem of two convex polyhedrons to non-linear programming problem. Using simulation anneal genetic algorithms solve it. Using receive criterion of simulation anneal intersect and vary. Algorithms Optimize time complexity. Finally in order to speed up the collision detection, we use parallel parallel to parallelize genetic algorithm.Result show that simulation anneal genetic algorithms especially the genetic algorithms parallel have better efficiency and more faster computing speed.