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

论文摘要

干涉检测技术是计算机图形学中的一个关键技术,在虚拟装配、虚拟手术、飞行导航、机器人路径规划和计算机游戏动画等领域中有着非常广泛的应用。这些应用领域通常要求系统能预计可能发生的干涉,并根据距离信息及时地对路径进行调整和变更,以避免可能发生的干涉。因此,对于这些应用领域来说,快速地判定对象的位置关系并提供一个准确的距离信息（分离距离、穿透深度和距离实现向量）成为图形学算法设计工作的首要任务。它不仅仅局限于某个特定问题,涉及到计算机科学、动力学、机械工程和数学等多个学科,对它展开研究具有重要的实践意义和理论价值。但是迄今为止这个课题仍然存在许多问题没有解决,特别是对计算精度要求很高的应用环境。本论文研究的目的是将扫描线技术、包围体层次树、分支限界策略、启发式搜索算法和非线性规划理论等应用到本课题的研究中,寻求本课题一些关键问题的快速和有效的解决方法。本论文主要针对平面多边形、凸多面体和空间曲面这三种模型的干涉检测和距离求解问题进行了研究,并且获得了一些有意义的成果。本论文的主要创新性工作如下: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
• 第一章 绪论
• 1.1 课题的研究背景
• 1.2 国内外研究现状和干涉检测技术研究的主要问题
• 1.2.1 动态系统干涉检测的一般处理方法
• 1.2.2 主要干涉检测算法介绍
• 1.3 论文的研究思路与研究内容
• 1.3.1 论文的研究思路
• 1.3.2 研究目标和研究内容
• 1.4 论文的结构安排
• 1.5 参考文献
• 第二章 求解凸多边形最小平移距离的拟 QuickHull 算法
• 2.1 引言
• 2.2 QuickHull 算法介绍
• 2.3 求解凸多边形最小平移距离问题的拟QuickHull 算法
• 2.3.1 数学预备知识
• 2.3.2 算法的基本运行流程
• 2.3.3 关键技术实现
• 2.3.4 算法的实现步骤
• 2.3.5 算法的几何解释
• 2.3.6 算法的完整性证明
• 2.3.7 改进策略
• 2.4 算法性能分析
• 2.4.1 复杂度分析
• 2.4.2 试验验证
• 2.5 小结
• 2.6 参考文献
• 第三章 基于扫描线技术的平面简单多边形干涉判定算法
• 3.1 引言
• 3.2 数学预备知识
• 3.3 基于扫描线技术的平面简单多边形干涉判定算法
• 3.3.1 多边形干涉判定的基本流程
• 3.3.2 简单多边形的单调链分解
• 3.3.3 包围体层次树技术
• 3.3.4 判定单调链位置关系的扫描线算法
• 3.3.5 点与多边形的包含关系判定
• 3.3.6 简单多边形干涉判定算法
• 3.3.7 算法完整性证明
• 3.4 算法复杂度分析与性能比较
• 3.4.1 算法复杂度分析
• 3.4.2 试验验证
• 3.5 小结
• 3.6 参考文献
• 第四章 求解平面简单多边形分离距离的单调链配对算法
• 4.1 引言
• 4.2 数学预备知识
• 4.3 多边形距离的单调链配对算法
• 4.3.1 距离算法的基本流程
• 4.3.2 关键技术的实现细节
• 4.3.3 多边形距离算法的实现步骤
• 4.4 算法性能分析
• 4.4.1 算法复杂度分析
• 4.4.2 试验验证
• 4.5 小结
• 4.6 参考文献
• 第五章 求解平面简单多边形穿透深度的平移向量算法
• 5.1 引言
• 5.2 简单多边形穿透深度问题描述
• 5.3 求解简单多边形穿透深度的平移向量算法
• 5.3.1 平移向量算法的提出
• 5.3.2 相关数学知识
• 5.3.3 算法的基本流程
• 5.3.4 算法的实现细节
• 5.4 算法复杂度分析和试验验证
• 5.4.1 算法复杂度分析
• 5.4.2 试验验证
• 5.5 小结
• 5.6 参考文献
• 第六章 基于非线性规划理论的凸多面体最小平移距离算法
• 6.1 引言
• 6.2 凸多面体最小平移距离问题描述
• 6.2.1 最小平移距离定义
• 6.2.2 用一对广义分离平面确定凸多面体最小平移距离
• 6.3 基于非线性规划理论的凸多面体最小平移距离算法
• 6.3.1 NLP 等价模型的提出
• 6.3.2 NLP 模型等价性证明
• 6.3.3 NLP 等价模型的求解
• 6.3.4 判定凸多面体位置关系
• 6.3.5 NLPBA 算法描述
• 6.4 算法性能分析
• 6.4.1 模型选择
• 6.4.2 性能比较
• 6.5 小结
• 6.6 参考文献
• 第七章 求解曲面距离问题的退火遗传算法
• 7.1 引言
• 7.2 数学预备知识
• 7.2.1 Bezier 曲面和NUBRS 曲面
• 7.2.2 遗传算法的原理
• 7.2.3 模拟退火算法的原理
• 7.3 求解曲面距离问题的退火遗传算法
• 7.3.1 模型参数化处理
• 7.3.2 编码与译码
• 7.3.3 适应值函数
• 7.3.4 遗传操作
• 7.3.5 退火遗传算法的提出
• 7.3.6 算法描述
• 7.3.7 改进策略
• 7.4 试验结果与算法性能比较
• 7.4.1 仿真实例选择
• 7.4.2 参数设定
• 7.4.3 试验验证
• 7.5 小结
• 7.6 参考文献
• 第八章 总结与展望
• 8.1 论文研究工作总结
• 8.2 有待进一步解决的问题
• 致谢
• 作者在攻读博士学位期间发表的学术论文