三维场景漫游中碰撞检测的研究与应用

在虚拟现实环境下,基于包围盒算法是一类重要碰撞检测算法,该文在比较了层次包围盒下的几种常用的包围盒技术,具体阐述了实时性好且较容易程序实现的轴一致包围盒(AABB)的定义、重叠测试和碰撞检测算法,并把该包围盒技术应用到虚拟现实系统的碰撞检测过程中,最终在VC++和OpenGL平台上实现了三维场景漫游过程中物体之间的精确碰撞检测。     

基于层次包围盒的混合碰撞检测算法

针对碰撞检测算法实时性较差的缺点,本文提出基于AABB包围盒与OBB包围盒相结合的混合碰撞检测算法,首先由对象投影来判断是否相交,检测出不可能相交对象;然后对可能相交的对象投影反向构建AABB包围盒,快速地测试对象;再用OBB包围盒进行精确地检测,以实现虚拟环境对象间高效的碰撞检测。本文还针对传统的基元相交测试效率不高的缺点进行了一定的改进。实验结果表明,与另外两种算法对比,该方法在相同环境前提下能够有效的提高碰撞检测的效率。     

融合神经网络的布料碰撞检测算法

目的 针对当前在虚拟环境中布料柔体碰撞检测效率慢和准确性低的问题,提出一种根节点双层包围盒树结构和融合OpenNN （open neural networks library）神经网络加速预测碰撞检测的算法。方法 首先改进了碰撞检测常用的包围盒技术,提出根节点双层包围盒算法,减少包围盒的构造时间。其次使用神经网络优化碰撞检测技术,利用神经网络可以处理大量数据的优势,每次可以检测大量基本图元是否发生碰撞,解决了碰撞检测计算复杂性高的问题。最后准确地找到碰撞粒子并做出碰撞响应。结果 在相同的复杂布料模型情况下,根节点双层包围盒算法在运行速度上比传统混合包围盒算法快,耗时缩减了5.51%~11.32%。基于OpenNN算法的总耗时比根节点双层包围盒缩减了11.70%,比融合DNN （deep neural network）的自碰撞检测算法减少了6.62%。随着碰撞检测难度的增大,当布料模型的精度增加84%时,传统物理碰撞检测方法用时增加96%,融合DNN的自碰撞检测算法用时增加90.11%,而本文基于神经网络的算法用时仅增加了68.37%,同时表现出更高的稳定性,满足使用者对实时性的要求。结论 对于模拟场景中简单模型的碰撞,本文提出的根节点双层包围盒算法比传统的包围盒方法耗时短。对于复杂模型,基于OpenNN神经网络的碰撞检测算法在效率上优于传统的包围盒算法和融合DNN的自碰撞检查算法,而且模拟效果的准确性也得以保证,是一种高效的碰撞检测方法。     

混合包围盒碰撞检测算法研究

为提高碰撞检测的实时性,提出一种混合包围盒碰撞检测算法。将物体的包围盒二叉树设计为2层结构,顶层使用AABB包围盒排除不相交的物体,下层利用k-DOPs包围盒检测物体之间的碰撞情况。采用任务树的方法对2棵混合包围盒二叉树进行同步遍历,实现物体之间的碰撞检测。与其他碰撞检测算法进行对比分析,实验结果表明,该算法能提高碰撞检测的实时性和精确性。     

基于层次包围盒的碰撞检测算法的存储优化

介绍了基于层次包围盒的碰撞检测算法的存储优化方法。该方法从存储空间的角度来改进基于AABB树的碰撞检测算法。根据AABB树的构造过程,减少内部节点的AABB包围盒的存储字节数;基于快速三角形相交测试算法,从叶节点结构里去掉包围盒信息,将叶节点从存储结构中删除。实验表明,利用AABB包围盒和叶节点的存储优化,既减少了算法的存储空间又加快了算法的执行时间。     

基于GPU加速的多物体碰撞检测方法

为了在虚拟环境中更加真实地模拟现实环境中物体的运动,需要在仿真系统中加入碰撞检测模块。现有的碰撞检测算法虽然能够快速检测两个物体是否相交,但在物体数量非常多的场景中,因需要对物体两两进行判断,所以仍无法达到较高的检测速度。利用GPU并行计算的特性,在GPU上增加一个预先剔除的过程,大幅度地快速排除不相交的物体,提高了检测的速度。     

复杂场景中基于拓扑空间网格的碰撞检测算法

为了提高复杂场景的碰撞检测效率,提出一种基于拓扑空间网格的碰撞检测算法. 由于场景中存在众多形状复杂、尺寸不一且运动状态不同的物体,首先采取场景预处理对空间进行均匀八叉树网格划分,建立物体方向包围盒层次树与空间网格拓扑结构,利用静态大尺寸物体分割策略提升定位精确性,然后在实时检测中利用拓扑空间网格及投影相交测试排除大量不相交物体对,利用层次包围盒算法对潜在碰撞对进行精确检测并计算出碰撞点. 实验结果表明,本算法有效地提高了实时检测的效率,适用于复杂虚拟场景中的碰撞检测.     

虚拟场景中基于空间域的碰撞检测算法研究

从空间域角度,详细分析了基于空间分割、基于层次包围盒和基于GPU的碰撞检测算法。对于基于空间分割的碰撞检测算法,详细介绍了八叉树和BSP算法;对于基于层次包围的碰撞检测,详细介绍了包围球、AABB、OBB和K-DOP算法;基于GPU的碰撞检测则分析了基于图像空间和基于GPU流计算的算法。最后,对各算法的优缺点进行了分析和比较。     

适用于复杂场景的碰撞检测算法研究

创建虚拟场景不仅要进行静态建模,更重要的是进行动态建模。而且物体之间的实时碰撞检测是关键。首先对常用检测算法的检测效率进行了分析和比较。然后重点针对复杂虚拟场景中吉有大量物体的特点,提出了混合包围盒碰撞检测算法。该算法利用帧与帧之间的时间和几何相关性,把对（cn^2＋m）个对象的动态跟踪转化为它们在三个坐标轴上的投影的排序问题,把时间复杂度由O（n^2）降低为O（n）。并引入树的深度的概念,根据不同的应用场合合理控制检测深度以加快检测速度。理论分析和仿真计算都表明,该算法能够满足多达几百个运动物体的实时交互碰撞检测。     

虚拟场景中碰撞检测实用算法研究

碰撞检测是虚拟系统中的一项关键技术,也是提高虚拟系统现实感的一个重要因素。许多算法对碰撞检测的精度进行了研究,但对一个大型的虚拟场景,碰撞检测的范围则是影响仿真速度的主要因素。该文在包围盒检测技术研究的基础上,根据大型虚拟场景的特点,提出了碰撞发生的局部性、主动性、相邻性的观点,由此给出了虚拟游览系统中碰撞检测的DS算法,通过在本单位虚拟战场仿真系统的应用及分析表明,该算法对提高虚拟系统的运算效率是非常有效的。     

Android手持设备游戏中的碰撞检测算法研究

针对Android手持终端中复杂游戏场景的碰撞检测需求,提出了一种基于包围球和AABB的实时碰撞检测算法。该算法针对不同的虚拟对象构建不同的包围盒,并将改进后的包围盒投影排序分组方法应用其中。将该算法与使用包围盒投影排序分组方法的包围球算法与AABB算法比较,实验表明,该算法在保持更高精度的前提下仍能满足复杂场景中实时碰撞检测的要求。     

基于空间剖分的碰撞检测算法研究

针对虚拟环境中物体碰撞检测效率不高的问题,提出了一种基于空间剖分的碰撞检测算法。利用物体空间分布特性以及运动物体碰撞行为的局部性,先用空域分割中定性-定量结合的方法快速确定可能碰撞的物体对,再用混合层次包围盒进行精确测试,明显地提高了碰撞检测速度。实验分析表明,该算法不仅可实现复杂场景下多个物体同时发生碰撞的检测,也能保证算法在物体高速运动时的有效性。     

一种快速的可变形物体的碰撞检测算法

为实现虚拟环境中可变形物体与刚体间实时的碰撞检测,提出了一种快速的基于混合包围盒层次结构的并行碰撞检测算法。算法充分利用包围盒在检测速度和精度上的不同侧重,对可变形物体建立Sphere和AABB混合包围盒层次树,对刚体建立Sphere和OBB混合包围盒层次树;每个物体的混合包围盒层次树又分成上层、中层和下层,每层使用不同的包围盒;在碰撞检测遍历时,上层使用Sphere和Sphere相交检测快速排除不相交物体,在中层使用Sphere和OBB的相交检测进一步排除物体相交的可能性,在下层使用AABB和OBB的相交检测较精确地确定物体是否相交;采用多线程技术,在多核设备上实现并行碰撞检测算法。实验结果表明,与经典的AABB算法相比较,该算法在效率方面具有明显优势,能够满足可变形物体与刚体的碰撞检测要求。     

基于AABB树的碰撞检测算法的内存优化

介绍了从存储空间角度来改进基于AABB树的碰撞检测算法的方法.根据有关三角形间快速相交测试算法和三角形与包围盒间的快速相交测试算法,略过包围盒间的相交测试,从叶节点结构里去掉包围盒信息,将叶节点从存储结构中删除.对一棵含有N个节点的 AABB 树而言,可以节约一半节点的内存空间.实验表明,利用 AABB 树叶节点的内存优化,减少了算法所需的内存空间且加快了算法的执行时间.     

包围盒碰撞检测算法的优化

围绕如何提高碰撞检测的速度,对虚拟环境中的物体进行了假设,提出了对碰撞检测进行预处理的方法,并结合各类包围盒的特点,提出了在碰撞检测中针对具有不同几何特征的物体选择不同类型包围盒的混合包围盒算法,分析了不同类型包围盒之间的求交算法,实现了层次包围盒碰撞检测算法的优化,提高了碰撞检测的速度,增强了系统的实时性。     

虚拟装配中快速碰撞检测算法的研究与实现

针对虚拟装配中碰撞检测的特殊要求，提出了一种基于包围盒与空间剖分法的两级碰撞检测算法HSDHBB。该算法首先用空间剖分法找出潜在的相交区域，然后用包围盒求得碰撞的三角面片对和精确的碰撞点。给出了层次包围盒树的构造方法和空间网格的剖分方法，在空间剖分中采用哈希表的数据结构加快检索速度。最后，在CATIA环境中实现了该算法，结果表明该算法能够满足虚拟装配系统的实时性和精确性的要求。     

一种新的基于混合层次包围盒的碰撞检测算法

为了实现物体间快速精确的碰撞检测,提出了一种新的基于混合层次包围盒的碰撞检测算法,充分利用了包围球计算简单和K-DOPs包围盒紧密性好的优点,来构建物体的混合层次包围盒结构。在包围盒树的上层采用Sphere包围盒,能快速排除不相交的物体,下层采用K-DOPs包围盒,进行更加精确的相交测试,提高了碰撞检测实时性。实验结果表明,该算法是有效可行的,具有较强的实时性及鲁棒性,性能优于传统碰撞检测算法。     

虚拟环境中优化的OBB碰撞检测算法研究

碰撞检测是计算机图形学的研究热点之一,基于包围盒的碰撞检测算法是一种比较有效的碰撞检测算法.OBB紧密性较好,能有效提高系统的检测效率,但是相交测试的代价太大,根据AABB易于构造、计算简单但紧密性差的特点,提出并实现了优化的OBB碰撞检测算法.实验结果证明:优化算法能够较大幅度地提高了碰撞检测的实时性能,取得较好的效果.     

基于图像空间的复杂模型碰撞检测算法

提出一种使用图形硬件用于复杂模型间的快速的碰撞检测算法.算法是基于CULLIDE的执行GPU可见性查询来减少物体模型间没有邻近特征的子集,描述了一个分类方案计算物体潜在碰撞集和碰撞自由子集,提高了裁减的性能.为了减少CPU的负载,利用GPU的可编程性,在GPU上进行精确的物体相交计算.