基于粒子群优化技术的限时碰撞检测算法

论文摘要

目前，实时交互系统对碰撞检测算法提出了更高的实时性要求。本文探索和研究了虚拟环境中广泛使用的碰撞检测算法，尝试把几何模型的碰撞检测问题转化为优化搜索问题，把粒子群优化搜索技术引入碰撞检测领域，并结合碰撞检测领域现有的层次包围盒技术和网格简化技术，组成新颖的限时干涉检测算法框架，即用户可以方便地控制分配给碰撞检测算法的时间，尝试去克服这一技术瓶颈。本文在“触觉交互系统”中进行算法性能测试，获三得了良好的性能效果。本文的主要工作为：第一章概述了碰撞检测问题，把目前的碰撞检测算法分为八大类，主要介绍了与本文算法相关的层次包围盒技术和基于随机方法的碰撞检测技术，并详述了作为BASIC-PSO碰撞检测算法基础的粒子群优化搜索技术。第二章提出了基于粒子群优化技术的快速碰撞检测算法（BASIC-PSO），该算法利用最基本的粒子群优化搜索技术，以三角形的AABB包围盒作为基本的操作对象。本章还测试了粒子的最大钳制速度、初始惯性权值、种群规模以及模型之间的接触状态等参数对BASIC-PSO算法的影响规律。另外也提出了一种比较新颖的基于分区编码的三角形窗口线裁剪算法，应用在空间三角形的静态求交中。第三章提出一个高效的算法框架AABB-PSO。该算法框架的主要思想是首先用AABB层次包围盒技术把粒子搜索空间缩小，然后使用BASIC-PSO算法进行搜索，这样则发挥了层次包围盒技术和BASIC-PSO算法各自的优势，互补对方的缺陷。也测试了粒子搜索空间大小对算法性能的影响规律。第四章提出了另一个快速的算法框架SURS-PSO。该算法框架则首先利用Garland网格简化技术在预处理阶段把复杂场景进行误差允许范围内的简化，缩小粒子的搜索空间，然后使用BASIC-PSO进行快速搜索。这充分利用了网格简化技术能够把大规模复杂场景在一定误差范围内进行大幅度化简，且可以在碰撞检测算法动态运行之前完成，不占用算法动态干涉时间这一优势。第五章实现了两种加速技术。一种是结合本文算法的特点而开发的基于“三角形几何拓扑信息”的加速技术；另一种就是目前被广泛使用的基于几何模型时空相关性原理的加速技术。第六章介绍了算法测试平台“触觉交互系统”的构成和主要模块，详述了干涉检测算法的数据结构和技术细节，并通过在该平台上运行一些实例对两个算法框架的性能进行了验证。另外还开发了一个高效的NFF文件修补算法和一个数据接口，用于和网格简化系统QSlim2.0进行数据交换。第七章归纳了本文的主要研究工作，并对后续些可能研究方向进行了分析和展望。

论文目录

• 摘要
• Abstract
• 目录
• 第1章 绪论
• 1.1 问题背景
• 1.2 问题描述
• 1.3 相关工作
• 1.3.1 层次包围盒技术
• 1.3.2 基于随机方法的碰撞检测技术
• 1.3.3 粒子群优化算法
• 1.4 主要贡献
• 第2章 BASIC-PSO:基于基本粒子群的随机限时碰撞检测算法
• 2.1 引言
• 2.2 BASIC-PSO搜索空间的构建
• 2.2.1 基本粒子——三角形的AABB包围盒
• 2.2.2 粒子位置与速度
• 2.2.3 评价函数
• 2.2.4 速度和位置更新方法
• 2.2.5 终止条件
• 2.3 BASIC-PSO的干涉检测方法
• 2.3.1 PSO搜索策略
• 2.3.2 三角形的精确检测流程
• 2.3.3 基于分区编码的三角形窗口线裁剪算法
• 2.4 BASIC-PSO算法的性能测试
• 2.4.1 实验方案设计
• max对搜索成功率ratio_s的影响'>2.4.2 钳制速度V_max对搜索成功率ratio_s的影响
• max对成功率ratio_s及时间的影响'>2.4.3 惯性权值w_max对成功率ratio_s及时间的影响
• Agents对成功率ratio_s的影响'>2.4.4 种群规模N_Agents对成功率ratio_s的影响
• 2.4.5 接触状态对搜索成功率及时间的影响
• 2.5 BASIC-PSO算法分析
• 2.5.1 BASIC-PSO算法的时间分析
• 2.5.2 BASIC-PSO算法的缺陷
• 2.6 本章小结
• 第3章 AABB-PSO:基于层次包围盒和粒子群的限时碰撞检测算法框架
• 3.1 AABB-PSO算法框架思想的来源
• 3.2 AABB-PSO干涉检测算法框架
• 3.2.1 树结构的选择
• 3.2.2 二叉树的构建过程
• 3.2.3 干涉检测过程
• 3.3 搜索空间大小对搜索成功率及时间的影响
• 3.3.1 球-球模型
• 3.3.2 活塞-活塞销模型
• 3.4 二叉树的最佳深度值讨论
• 3.5 本章小结
• 第4章 SURS-PSO:基于网格简化和粒子群的限时碰撞检测算法框架
• 4.1 SURS-PSO算法框架思想的来源
• 4.2 Garland的网格简化技术
• 4.2.1 算法思想
• 4.2.2 构造可选点集的两个原则
• 4.3 SURS-PSO干涉检测算法框架
• 4.3.1 干涉检测过程
• 4.3.2 活塞的网格简化过程
• 4.3.3 算法性能测试
• 4.4 网格简化误差和粒子总体性能的博弈
• 4.5 本章小结
• 第5章 限时碰撞检测加速技术
• 5.1 基于三角形拓扑关系的加速策略
• 5.1.1 随机碰撞检测算法的干涉率
• 5.1.2 基于三角形拓扑信息建立网状搜索空间
• 5.1.3 网状搜索空间中的粒子搜索策略
• 5.2 基于时空相关性加速策略
• 5.3 算法测试
• 5.3.1 球-球模型
• 5.3.2 活塞-活塞销模型
• 5.4 本章小结
• 第6章 碰撞检测算法测试平台的实现及其应用
• 6.1 测试平台的简介
• 6.1.1 系统的开发工具
• 6.1.2 系统的主要模块和功能
• 6.2 算法思想的程序实现
• 6.2.1 输入模型
• 6.2.2 NFF文件的缺陷
• 6.2.3 NFF文件修补算法
• 6.2.4 算法流程
• 6.2.5 主要类和数据结构设计
• 6.3 运行实例
• 6.3.1 在汽车发动机仿真中的应用
• 6.3.2 在车桥仿真中的应用
• 6.3.3 在研磨机仿真中的应用
• 第7章 总结与展望
• 7.1 全文总结
• 7.2 工作展望
• 参考文献
• 附录 发表的学术论文和参加的科研项目
• 致谢