【作者】 赵伟；

【导师】 李文辉；

【作者基本信息】 吉林大学 ， 计算机系统结构， 2009， 博士

【摘要】 为了解决虚拟环境的真实感问题,必须对虚拟环境进行实时的碰撞检测。本文围绕实时碰撞检测问题,就如何提高复杂场景下碰撞检测的效率进行了深入研究。着重探讨了如何利用并行技术来有效提高碰撞检测算法的效率。主要研究成果包括以下八个方面:1.提出了一种基于分治和流水线技术的并行碰撞检测算法。采用并行算法中的流水线技术,通过划分进程来遍历任务树从而加速碰撞检测过程。同时在进程中也应用了多线程技术,因而能快速的检测到碰撞。2.提出了一种基于混合包围体的OpenMP并行化碰撞检测算法。利用OpenMP并行模型来并行遍历混合包围体层次,进一步加速碰撞检测过程。提出了一种基于着色算法的并行碰撞检测算法,在并行机上采用多线程技术执行相同类别的任务树的遍历过程,在遍历过程中检测是否有碰撞发生。3.提出了一种基于时空相关性的MPI并行碰撞检测算法。在空间分割和时空相关性基础上采用基于MPI的并行处理技术。并通过MPI并行处理方式将各子任务分配到各子进程执行。4.提出了一种基于粒子群算法的并行碰撞检测算法。将OpenMP、MPI并行模型来并行化基于粒子群面向可变形物体的随机碰撞检测算法,提出了一种基于遗传算法的并行碰撞检测算法。采用一种快速的基于模拟退火遗传算法的碰撞检测技术,完成整个检测过程,然后将并行技术用于遗产算法,进一步加速碰撞检测的速度。5.提出了一种改进的基于球体混合重建的并行碰撞检测算法。对球体混合表面提出一个子线性时间复杂性的重建过程,利用四元组构造变换范围,扩展了从线性到球形混合的构造变换方法,采用循环划分的方法完成由球体混合到线性混合的分解过程。然后采用OpenMP技术并行化上述算法,可以快速完成虚拟环境下复杂的碰撞检测问题。更多还原

【Abstract】 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.更多还原