虚拟现实中碰撞检测问题已经成为计算几何、计算机动画、仿真机器人、CAD/CAM、3D游戏开发、物理仿真等领域中的一个热点问题,而日趋复杂的虚拟环境的真实感和实时性对碰撞检测提出了更高的要求。针对以上实时性的需求本文做了以下研究:1、提出一种高质量的BVH结构的几何划分方法。实现高效完全并行化的加速结构的构造过程,在x86 CPU架构下实现8位的单位向量计算及向量扩展计算,采用分组图元方法,实现线性时间复杂性完成的聚类算法。2、提出了一个高性能层次包围盒的划分方法。快速并行实现以最长包围盒平面投影顺序分配图元过程,对图元提出了快速并行分段折半排序算法,使用位置跟踪的遍历方法加速光线跟踪及提高帧速率,给出了与三种经典算法SAH-BVH等的比较过程。内存占用及平均相交测试过程,并与SAH-BVH算法做了比较。3、提出一种基于交叉与排斥算子的SIMD并行碰撞检测算法提出了一种基于交叉排斥算子的并行碰撞检测算法CROCDA。引入了交叉与排斥算子,将搜索空间限定在非均匀的局部极小区域,减少了蚁群的搜索时间。在多蚁群求解过程中,采用并行任务的细粒度分解,将子任务使用负载均衡策略分配到多核处理器的各个处理核心上并行执行,主要优点从以下几个方面表述:(1)利用SIMD-Dop包围盒的结构优点,构造任务树,子任务在多线程下执行,使程序的并行化处理更加高效;(2)引入交叉排斥算子的概念。采用堆栈技术,标记遍历节点,减少了相交检测次数,提高了碰撞检测的速度,实时虚拟场景变换的实时性;(3)程序在计算机集群中并行处理,子任务并行执行,缩短碰撞检测时间;(4)采用交叉排斥算子优化蚁群,使算法不易陷入局部极值,并在SIMD下快速执行。4、提出一个重组流水线使用GPU提高光线跟踪性能的碰撞检测方法。在详细检测阶段采用光线跟踪算法来有效地处理不同性质的对象,通过详细检测阶段的分段划分,将整个流水线保持密集输入,提高GPU的使用效率。实验结果表明,所提出的方法平均加速了1.27倍。5、提出了一种利用空间和时间相关性迭代光线跟踪的碰撞检测算法。本章提出的迭代光线跟踪算法可以加速任何现有的光线跟踪算法,从最后一个受影响的三角形开始迭代直到找到当前的三角形,而不是每一步都重新计算光线,并引入了预测光线以避免不必要的穿透。提出了一种利用光线跟踪技术完成布料和布料之间碰撞检测方法。是一种基于对象空间的算法,在CUDA和NVIDIA OptiX光线跟踪引擎中实现。从移动的布料顶点投射几条光线,发现与场景中其他对象的位置关系,利用GPU高性能并行计算性能,加速碰撞检测求解过程。6、提出了一种在GPU上实现变形模型光线跟踪及碰撞检测与响应的新算法。对于运动模型,沿着变形模型的每个顶点的运动方向投射光线,通过光线跟踪判断是否存在碰撞,如果发现碰撞,则找到碰撞点;如果没有发现碰撞,则使用法向量投射另一条光线,采用反演处理方法修正离散模拟带来的误差。与基于图像空间的碰撞检测相比,具有很高的效率,可以应用于变形模型的动态仿真。