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