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