● 摘要
碰撞检测问题在虚拟装配、机器人运动规划、计算机辅助设计等领域中已有很长的研究历史。近年来随着虚拟现实、分布交互仿真等技术的兴起，碰撞检测问题也开始成为研究的热点。精确的碰撞检测对提高虚拟环境的真实性、增强虚拟环境的沉浸感有着至关重要的作用。由于计算机硬件以及三维扫描等数据获取技术和CAD建模技术的迅速发展，在各种虚拟现实应用中所处理的虚拟场景的规模越来越大，模型的数据量已远远超过普通计算机内存的容量。因此实时性要求较高的虚拟现实应用对碰撞检测技术提出了更高的要求。本文以国家十一五863课题“支持移动终端的多人协同虚拟环境及开发工具研究”为背景，针对基于外存模型的碰撞检测中存在的问题，对外存模型的组织和实时碰撞检测算法进行了研究。虚拟场景由大量的几何图元构成，这些图元的分布无固定规律，因此不能体现场景的空间分布情况。通常使用空间数据结构对场景进行组织是加速虚拟环境中各种算法(可见性裁剪、碰撞检测等)的有效方法。而对于模型数据量超过内存容量的外存场景模型，模型数据无法同时读入内存，需要实时按需进行调度。本文给出一种外存索引八叉树结构，利用八叉树结构将静态场景划分为可管理的子块，并在叶节点建立其所对应的外存文件的索引，使在实时阶段能够以叶节点为单位进行按需的调度。基于外存模型的碰撞检测与内存模型下的碰撞检测相比最大的不同是模型数据无法同时读入内存进行处理，而只能在实时阶段以某种方式按需地调入内存，因此需要实时访问，而低速的磁盘I/O操作对算法效率有较大的影响。本文给出了一个外存模型下实时碰撞检测的算法框架，利用数据缓存对内外存数据调度进行管理，使外存模型下的碰撞检测能够在有限的内存大小下进行，并给出一种基于八叉树邻居的碰撞预测算法，根据八叉树结构的特点和碰撞检测的时空连续性预测预取可能发生碰撞的节点的数据。实验结果表明本文所采用的碰撞预测方法能够在不重复进行相交测试计算下保持较高的预测准确率，并且碰撞预测和多线程数据预取能够有效地减少低速磁盘操作对算法效率的影响。场景的绘制效率对虚拟现实应用的实时性也非常重要。由于复杂场景中包含大量的多属性对象，绘制中频繁的属性切换会导致绘制效率的明显降低，本文针对这一问题给出一种基于状态转换优化策略的多属性对象绘制方法，通过定义绘制状态对场景中对象的属性进行管理，并将绘制状态的转换关系表示为带权有向图，进而利用最优化算法找到绘制状态转换的优化序列。实验结果表明对于具有多属性对象的复杂场景，本方法能够有效的降低状态转换的开销，提高场景的绘制效率。