【作者】 水泳；

【导师】 郑津津；

【作者基本信息】 中国科学技术大学 ， 精密仪器及机械， 2013， 博士

【摘要】 虚拟环境中的碰撞检测问题是触觉渲染、物理仿真、机器人的路径规划、计算机游戏以及CAD/CAM等领域中的经典问题。实现实时的、高精确度的连续碰撞检测对增强虚拟场景的沉浸感以及真实性起着非常重要的作用。由于大部分虚拟现实系统都需要进行实时的人机交互,只有连续碰撞检测的速度达到一定的帧数时,才可以流畅的进行人机交互。虚拟环境中所有图元之间的碰撞都需要准确的检测结果,否则在视觉上会产生明显的不真实感。因而,如何提高连续碰撞检测算法的速度与准确度一直都是研究的重点内容。本论文在对各种碰撞检测算法进行全面了解的基础上,针对可变形物体之间的连续碰撞检测算法中存在的问题,进行了研究。本论文的主要研究内容包括以下几个方面：本论文分析了在设计以及实现可变形物体之间的连续碰撞检测算法过程中需要考虑的几个因素。首先,对于物体模型的表示方式,选择了本论文所提出的算法所适用的三角形网格模型。其次,把整个连续碰撞检测过程分为两步执行,即初步检测阶段和详细检测阶段。其中,初步检测阶段主要是把可能发生碰撞的物体分在同一个子集中,然后在详细检测阶段对这些子集分别执行进一步的测试。在详细检测阶段中对于图元之间的碰撞测试,使用点面图元对检测算法和边边图元对检测算法。最后,对于可能出现的健壮性问题进行了分析,并采取了一些措施来避免产生这些问题。详细的介绍了本论文所使用的k-DOPs包围盒以及层次包围树结构。层次包围树结构可以用于加速连续碰撞检测的初步检测阶段以及详细检查阶段。对于初步测试阶段,可以使用虚拟场景中所有物体的层次包围树来进行碰撞检测,从而剔除不可能发生碰撞的物体对；对于详细测试阶段,使用由组成物体的图元构建的层次包围树来进行碰撞检测,从而剔除那些不可能发生碰撞的图元。还详细介绍了本论文所使用的层次包围树的构建方法、执行相交测试时所使用的遍历方法以及当物体发生变形时所使用的层次包围树的更新方法。详细的说明了本论文所提出的一种用于自碰撞检测的算法。该算法分别对自碰撞检测的曲率测试和轮廓投影线测试这两个测试条件进行了改进。对于可变形物体,根据它的几何图元之间的邻接信息使用自底向上的方法构建物体的层次包围树。在构建层次包围树的过程中,计算每一个节点内的子三角形网格区域的最小法向量锥。将最小法向量锥思想应用到轮廓投影线的自碰撞测试中,避免了轮廓投影线中各条线段之间的两两测试。同时,还根据子三角形网格区域之间的邻接信息减少自碰撞检测过程中大量不必要的检测。最后实验结果说明,该算法能较好的提高自碰撞检测的速度。详细的阐述了本论文所提出的一种用于连续碰撞检测算法中的基于子空间的剔除算法。在连续碰撞检测过程中两个非常接近但是实际上没有发生碰撞的图元往往会产生误报。针对这种问题,首先使用基于一维子空间的剔除算法,然后对剩余的图元对使用基于二维子空间的剔除算法。若是三维空间中的两个图元在一维子空间或者二维子空间内没有发生碰撞,那么它们在三维空间中也不会发生碰撞。最后实验结果表明,该剔除算法能够显著的减少连续碰撞检测中的误报数量,从而避免了大量的三次方程的求解运算,提高了连续碰撞检测的速度。更多还原

【Abstract】 Collision detection in the virtual environment is a classic topic in research area of haptic rendering, physical simulation, robot path planning, computer games and CAD/CAM. The real-time and high accuracy continuous collision detection plays a very important role in enhancing the immersion and improving the authenticity of the virtual environment. Since most of the virtual reality systems require real-time human-computer interaction. Only when the speed of continuous collision detection is fast enough, the systems can achieve the goal of the real-time interaction. All collisions between the primitives in the virtual environment need the accurate results, otherwise there is not realistic. Therefore, how to improve the speed and accuracy of the continuous collision detection algorithm has always been the focus of the research.After a comprehensive understanding for a variety of collision detection algorithm, the paper studies the continuous collision detection algorithm between the deformable objects. In this paper, the main research contents are described as follows:This paper analyzes several factors those need to be considered in the process of the design and implementation of the continuous collision detection algorithm between the deformable objects. First of all, for the representation of the object model, the algorithms proposed in this paper apply the triangular mesh model. Secondly, the whole continuous collision detection process is divided into two phases, those are the broad-phase and the narrow-phase. In the broad-phase the algorithms put the objects those may be colliding in a group, and then in the narrow-phase the algorithms perform pair-wise tests within these groups. In the narrow-phase the algorithms use vertex-face and edge-edge elementary tests between the primitives. Finally, the robustness problems that may occur are analyzed, and then some measures are taken to avoid these problems.This paper gives a detailed description of the k-DOPs bounding box and the bounding volume hierarchies. Bounding volume hierarchies can be used to accelerate the broad-phase and the narrow-phase of the continuous collision detection. In the broad-phase, the hierarchy of all the objects in the virtual environment can be used for collision detection, thereby it can excludes those objects that are not colliding; In the narrow-phase, the hierarchy of all the primitives of the object can be used for collision detection, thereby it can excludes those primitives that are not colliding. This paper also describes the construction methods of the bounding volume hierarchies, the traversal methods of the intersection test and the update methods of the bounding volume hierarchies of the deforming objects.This paper gives a detailed description of a self-collision detection algorithm. The algorithm improves the curvature test and contour test of the self-collision detection. The bounding volume hierarchy of the deformable objects is built by the bottom-up method based on the adjacency information between its geometric primitives. In the process of building the bounding volume hierarchy, the minimum normal cone of the sub-triangle mesh area of each node is calculated. Apply the minimum normal cone to the contour test to avoid the pair-wise test of the contour projection lines. Moreover, according to the adjacency information between sub-triangular mesh area, the algorithm can reduce a large number of unnecessary collision detection during the self-collision detection process. Finally, the experimental results demonstrate that the algorithm can improve the speed of self-collision detection.This paper gives a detailed description of a subspace culling algorithm for continuous collision detection. When two primitives are very close and in fact there is no collision between them, they may produce a false positive in the process of continuous collision detection. In order to solve this problem, at first we use a culling algorithm based on the one-dimensional subspace, and then use the culling algorithm based on the two-dimensional subspace for the remaining primitive-pair. If two primitives in the three-dimensional space are not colliding in the one-dimensional subspace or two-dimensional subspace, then they don’t collide each other in the three-dimensional space. The experimental results show that the culling algorithm can significantly reduce the number of false positives in the continuous collision detection, thus the algorithm can avoid solving a large number of the cubic equations to improve the speed of continuous collision detection.更多还原