面向虚拟装配的干涉检测关键技术研究

《面向虚拟装配的干涉检测关键技术研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、摘要干涉检测技术是计算机图形学中的一个关键技术，在虚拟装配、虚拟手术、飞行导航、机器人路径规划和计算机游戏动画等领域中有着非常广泛的应用。这些应用领域通常要求系统能预计可能发生的干涉，并根据距离信息及时地对路径进行调整和变更，以避免可能发生的干涉。因此，对于这些应用领域来说，快速地判定对象的位置关系并提供一个准确的距离信息(分离距离、穿透深度和距离实现向量)成为图形学算法设计工作的首要任务。它不仅仅局限于某个特定问题，涉及到计算机科学、动力学、机械工程和数学等多个学科，对它展开研究具有重要的实践意义和理论价值。但是迄今为止这个课题仍然存在许多问题没有解决·特别是对计算精度要

2、求很高的应用环境。本论文研究的目的是将扫描线技术、包围体层次树、分支限界策略、启发式搜索算法和非线性规划理论等应用到本课题的研究中，寻求本课题一些关键问题的快速和有效的解决方法。本论文主要针对平面多边形、凸多面体和空间曲面这三种模型的干涉检测和距离求解问题进行了研究，并且获得了一些有意义的成果。本论文的主要创新性工作如下：1．提出了求解平面凸多边形最小平移距离的QuasiQuickHull算法—QQH算法。QQH算法在QuickHull算法基础上，利用面积计算对形态和进行隐式构造，解决了平面凸多边形的最小平移距离问题。算法先通过执行两次GJK(Gilbert-Johnson

3、-Kemhi)算法获得TCSO(translafionalC-spaceobstacle)对象膨上的两互异顶点；再根据(三角形)面积计算获得与肘内接的初始多边形只然后确定P上距离原点最近的边，并通过面积计算搜索J】If上与最近边对应的对拓顶点；然后利用新搜索到的对拓顶点更新P的边界，迭代测试，直至找到肘边界上距离原点最近的边或顶点为止。该方法给出了基于面积值判断的快速终止条件，避免了异常情形的特殊处理，并能通过区域测试快速判定两多边形是否发生干涉。2．提出了判定平面简单多边形位置关系的扫描线算法。算法在包围体层次树干涉检测算法基础上，利用扫描线技术判定单调链的位置关系，解决

4、了一般多边形之间的位置关系判定问题。该方法先对多边形进行单调链分解；然后对单调链构造包国鑫层次树，并利用包围体层次树的干涉检测技术确定包围盒发生干涉的单调链对；再根据扫描线技术判定链对的位置关系；最后，根据链对的测试结果来精确判定多边形的位置关系。该方法能有效地区别边界接触和内部相交两种情形，并且提高了射线求交法判定多边形包含关系的稳定性。3．提出了一种计算平面简单多边形分离距离的单调链配对算法。该算法在包围体层次树距离算法基础上，通过对单调链进行选择性配对来确定可能包含最近点对的子边界，解决了一般多边形之间的分离距离问题。该算法先根据多边形包围盒的位置关系初步确定对可能包

5、含最近点的关联边界，并对多边形距离上界值进行初始化；然后，对关联边界进行单调性分解，并对单调性相同的链构造包围体层次树；再利用包围体层次树距离算法对单调性互异的链对进行选择性匹配，并根据最近获得的链对的几何信息来动态更新距离上界值：最后，利用层次树距离算法迭代计算单调链的距离，从而获得多边形的最近距离。该方法采用基于距离阅值的筛选策略对单调性互异的链对进行选择性匹配，减少了包围盒距离计算和边对距离计算的次数，从而大大提高了算法的效率。4．提出了一种求解平面简单多边形穿透深度的平移向量算法。该算法在旋转标尺算法和边界凸分解技术基础上，通过搜索使得多边形刚好发生接触的最短平移向

6、量来确定穿透深度的实现向量，解决了一般多边形之间的穿透深度问题。该算法首先对一般多边形构造凸包并计算凸包的穿透深度；然后，对多边形边界进行凹、凸链分解，并用凸包穿透深度对链对进行筛选；再利用旋转标尺算法确定发生在链对之间的对拓特征对，并计算对拓特征对的距离实现向量，同时用凸包穿透深度对之进行筛选；最后，搜索距离实现向量中使得多边形刚好发生边界接触的最优平移向量，进而确定一般多边形之间的穿透深度的实现向量。该方法避免了形态和的显式构造，实现起来比较简单，并且仅需进行少量的迭代即可确定最优平移向量。s．提出了用非线性规划理论求解凸多面体最小平移距离的新方法。该方法在分离轴理论和

7、非线性规划的基础上，通过搜索与最小平移距离实现向量对应的一对最优广义分离平面，解决了凸多面体的最小平移距离问题。该方法首先提出了广义分离平面的概念，并用一对最优广义分离平面准确地确定多面体的最小平移距离；然后根据最优广义分离平面对满足的约束条件建立非线性等价模型，将最优广义分离平面对的搜索问题转化非线性规划问题；最后利用非线性优化工具软件对问题进行求解，从而获得最小平移距离及其实现向量。该方法能有效避免死循环和异常情形的特殊处理，并且采用梯度下降法的迭代规则，经过少量的迭代就可收敛。6．提出了计算曲面距离的统一方法