【作者】 周之平；

【导师】 吴介一；

【作者基本信息】 东南大学 ， 控制理论与控制工程， 2006， 博士

【摘要】 干涉检测技术是计算机图形学中的一个关键技术,在虚拟装配、虚拟手术、飞行导航、机器人路径规划和计算机游戏动画等领域中有着非常广泛的应用。这些应用领域通常要求系统能预计可能发生的干涉,并根据距离信息及时地对路径进行调整和变更,以避免可能发生的干涉。因此,对于这些应用领域来说,快速地判定对象的位置关系并提供一个准确的距离信息(分离距离、穿透深度和距离实现向量)成为图形学算法设计工作的首要任务。它不仅仅局限于某个特定问题,涉及到计算机科学、动力学、机械工程和数学等多个学科,对它展开研究具有重要的实践意义和理论价值。但是迄今为止这个课题仍然存在许多问题没有解决,特别是对计算精度要求很高的应用环境。本论文研究的目的是将扫描线技术、包围体层次树、分支限界策略、启发式搜索算法和非线性规划理论等应用到本课题的研究中,寻求本课题一些关键问题的快速和有效的解决方法。本论文主要针对平面多边形、凸多面体和空间曲面这三种模型的干涉检测和距离求解问题进行了研究,并且获得了一些有意义的成果。本论文的主要创新性工作如下:1.提出了求解平面凸多边形最小平移距离的QuasiQuickHull算法—QQH算法。QQH算法在QuickHull算法基础上,利用面积计算对形态和进行隐式构造,解决了平面凸多边形的最小平移距离问题。算法先通过执行两次GJK(Gilbert-Johnson-Kerrthi)算法获得TCSO(translational C-space obstacle )对象M上的两互异顶点;再根据(三角形)面积计算获得与M内接的初始多边形P;然后确定P上距离原点最近的边,并通过面积计算搜索M上与最近边对应的对拓顶点;然后利用新搜索到的对拓顶点更新P的边界,迭代测试,直至找到M边界上距离原点最近的边或顶点为止。该方法给出了基于面积值判断的快速终止条件,避免了异常情形的特殊处理,并能通过区域测试快速判定两多边形是否发生干涉。2.提出了判定平面简单多边形位置关系的扫描线算法。算法在包围体层次树干涉检测算法基础上,利用扫描线技术判定单调链的位置关系,解决了一般多边形之间的位置关系判定问题。该方法先对多边形进行单调链分解;然后对单调链构造包围盒层次树,并利用包围体层次树的干涉检测技术确定包围盒发生干涉的单调链对;再根据扫描线技术判定链对的位置关系;最后,根据链对的测试结果来精确判定多边形的位置关系。该方法能有效地区别边界接触和内部相交两种情形,并且提高了射线求交法判定多边形包含关系的稳定性。3.提出了一种计算平面简单多边形分离距离的单调链配对算法。该算法在包围体层次树距离算法基础上,通过对单调链进行选择性配对来确定可能包含最近点对的子边界,解决了一般多边形之间的分离距离问题。该算法先根据多边形包围盒的位置关系初步确定对可能包含最近点的关联边界,并对多边形距离上界值进行初始化;然后,对关联边界进行单调性分解,并对单调性相同的链构造包围体层次树;再利用包围体层次树距离算法对单调性互异的链对进行选择性匹配,并根据最近获得的链对的几何信息来动态更新距离上界值;最后,利用层次树距离算法迭代计算单调链的距离,从而获得多边形的最近距离。该方法采用基于距离阈值的筛选策略对单调性互异的链对进行选择性匹配,减少了包围盒距离计算和边对距离计算的次数,从而大大提高了算法的效率。4.提出了一种求解平面简单多边形穿透深度的平移向量算法。该算法在旋转标尺算法和边界凸分解技术基础上,通过搜索使得多边形刚好发生接触的最短平移向量来确定穿透深度的实现向量,解决了一般多边形之间的穿透深度问题。该算法首先对一般多边形构造凸包并计算凸包的穿透深度;然后,对多边形更多还原

【Abstract】 Interference detection is an important technology of computer graphics, which is extensively used in the fields such as virtual assembly, virtual surgery, flight navigation, path planning of robots and animation. For above applications of computer graphics, both information of distance and detection of intersection are required to adjust the route/trajectory timely and avoid the possible interference. So, it is vital that determine the position between objects and provide distance information (separation, penetration depth and the witness vector) efficiently and accurately to fit the need of such applications. The research work, which is not limited to a special problem, involves many subjects such as computer science, dynamics, machine engineering and mathematics. Because of the great value in theory and practice, various new theories and algorithms have emerged in endlessly. However, so far many difficulties remain unresolved, especially in some applications that require an accurate measure. The objective of this research is to present new approaches for improving the performance of distance algorithm by use of some existing technologies such as sweeping line, bounding volume hiberarchy, branch limit strategy, heuristic searching and nonlinear programming theory. The research of the dissertation consists of the interference detection and distance computation for some typical models such as planar polygon, convex polyhedron and smooth surface, and some efficient algorithms are presented in the paper.The principal research work and novelties are listed as follows:1.A quasi QuickHull algorithm (QQH algorithm) computing the distance between planar convex polygons is presented in the dissertation. QQH algorithm, which is based on the QuickHull algorithm, solves the problem of minimum translational distance (MTD) between planar convex polygons by constructing the translational C-space obstacle (TCSO) M of both objects implicitly with computing directed area. Firstly, two different vertices are obtained by calling GJK (Gilbert-Johnson-Kerrthi) algorithm two times; secondly, the initial inner polygon P is calculated via (triangle) area computation; thirdly, the nearest edge on P distance to origin is determined and then the opposite vertex on M corresponds to the nearest edge is searched using area computation; finally, the boundary of P is updated by adding the new opposite vertex and carries out the above procedure repeatedly until the nearest edge or vertex on the border of M is found.QQH algorithm provides a fast terminate condition based on judging the area and avoids the special process for the exception, as well as determines whether interference occurs or not by region test.2.A sweep line method to determine the position between two planar simple polygons is purposed in this paper. Based on intersection detection algorithm of bounding volume hierarchy tree (BVT), the method resolves the problem of relation determining for planar simple polygons by testing the position between monotone chains with sweep line technology. Firstly, the border of polygon is decomposed into a collection of monotone chains; secondly, the BVH of monotone chains are constructed respectively and the monotone chain-pairs whose bounding volume overlap are obtained using interference detection technology based on BVT; thirdly, the relation of a monotone chain-pair is decided through sweep line approach; finally, the accurate relation between polygons are achieved by the further test accord to the results from chain-pair test. The new method can distinguish just boundary touching from inner intersection, and the stability of ray shooting for checking whether one object contain the other is enhanced.3.A new approach based on coupling monotone chains pairwse for computing the separation between planar simple polygons is put forward in the article. On the basis of BVT distance algorithm, the approach settles the separation problem between two separable simple polygons by coupling the monotone chains selectively to determine the possible sub-boundary where the nearest point lies with. Firstly, both the interested boundary更多还原