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

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

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

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

基于时空相关性的快速碰撞检测算法

针对如何提高碰撞检测算法实时性的问题,提出一种空间分解与层次包围盒相结合的碰撞检测算法,并利用物体运动的时空相关性来加速物体之间的碰撞检测速度。首先用空间分割的方法确定相邻物体,然后用基于时空相关性的层次包围盒方法检测物体之间的碰撞情况,在包围盒碰撞检测时采用加入预判的OBB相交测试方法,减少了包围盒的相交测试计算。实验结果表明,该算法能够实现多个物体同时发生碰撞的检测,并且提高碰撞检测的实时性。     

基于混合包围盒的碰撞检测算法优化

为提高复杂场景中碰撞检测的效率,提出一种传统混合包围盒碰撞检测算法的优化算法。从数据结构上对混合包围盒树进行改进,引入时空相关性概念,将包围盒树分为上下2层结构,上层采用包围球,下层采用轴向包围盒,构造混合层次包围盒树,实现物体的快速碰撞检测,利用碰撞检测的时空相关性,简化树的搜索过程。实验结果表明,与传统的混合包围盒碰撞检测算法相比,该算法具有较好的碰撞检测性能。     

基于Sphere-OBB的改进碰撞检测算法及其应用

静态或动态环境中两个或者多个几何模型之间的碰撞检测是计算机图形学基础问题之一,基于层次包围盒的碰撞检测算法是一种比较有效的碰撞检测算法。提出了OBB包围盒与球包围盒相结合的高效碰撞检测算法,该算法既具有OBB的包围紧密性,又具有球包围盒的测试简便性。用高效的球包围盒排除大量距离远的不相交物体,剩下距离近的物体用分离轴测试,其中一些分离轴效率更高应该优先被测试。将该算法用于虚拟针灸训练系统,实验结果表明算法减少了查询时间并增强了实时性。     

基于形状分类的包围盒碰撞检测优化算法

由于现有的包围盒不能足够紧密地包围所有待检测的物体,剔除不相交物体的效果差导致了碰撞检测效率低。针对这个问题,提出一种基于形状分类的包围盒碰撞检测优化算法。算法根据每个物体的偏球率将它们进行分类,形状接近球体的,采用球包围盒;形状与球体偏离大的,采用OBB包围盒,这能够更加逼近真实的物体。同时,加入时空相关性和区域划分策略来优化遍历过程。实验结果表明,该算法缩短了相交测试的时间,提高了碰撞检测的效率。     

基于八叉树精确划分型值点的碰撞检测算法

针对虚拟现实中碰撞检测的快速计算问题,提出一种新的粗略碰撞检测与精确碰撞检测相结合的检测算法。首先利用AABB包围盒法排除不可能相交的物体,然后对可能发生碰撞的包围盒采用八叉树算法进行空间分割,在包围盒内找到由型值点形成的三角形面片,利用三角形面片的碰撞检测算法精确地判断物体是否碰撞。通过与OBB包围盒算法的碰撞检测数据对比,验证了该方法的有效性。     

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

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

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

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

基于包围盒与空间分解的碰撞检测算法

本文提出了一种基于包围盒方法与空间分解方法相结合的碰撞检测算法,用于解决变形体的碰撞检测问题。该算法首先用包围盒来快速判断物体之间是否相交,如果相交则进一步用空间分解法来定位相交的区域,在此阶段用哈希表的数据结构来保存物体的几何信息。与其他碰撞检测算法相比较,本算法不仅能够较大地节省空间,而且时间复杂度也比较低。除此之外,本算法不仅能够找出发生碰撞的基本几何元素对,而且还能够精确地找出碰撞点。     

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

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

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

目的 针对当前在虚拟环境中布料柔体碰撞检测效率慢和准确性低的问题,提出一种根节点双层包围盒树结构和融合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的自碰撞检查算法,而且模拟效果的准确性也得以保证,是一种高效的碰撞检测方法。     

虚拟手术中的快速碰撞检测算法

为了解决当前虚拟手术仿真中使用单一包围盒进行碰撞检测实时性不能满足要求的问题,提出了一种针对虚拟手术的基于层次包围体的快速碰撞检测方法。该方法主要应用了层次包围盒(BVH)的思想,同时根据不同对象的拓扑结构特征,采用不同的包围盒技术来表示。首先,用层次包围盒来表示手术工具,用层次包围球表示手术对象;然后,利用包围球和方向包围盒的相交测试快速排除不相交部分;最后,对于可能发生碰撞的部分再使用更为精确的三角面片相交测试来确定碰撞信息。实验结果表明,在相同的虚拟手术场景下,提出的这种方法较使用单一的层次包围盒具有更快的速度。     

一种快速的双重层次包围盒碰撞检测算法

传统的包含方向包围盒(OBB)的混合包围盒结构大多只是利用了OBB的紧密性特点,没有对OBB之间的相交测试进行改进,而OBB相交测试却占了这类算法的大部分运行时间。基于此,提出一种基于AABB-OBB双重包围盒的碰撞检测算法,外层的AABB可以快速排除分离距离较大的模型对,而当AABB相交时,与传统需要检测15条潜在分离轴的方法不同,内层的OBB之间的相交测试只需检测特定的5条分离轴。最后在算法的基本图元相交测试阶段,利用OBB之间相交测试所计算的中间值代替三角形的坐标值,省去不同模型中的三角形坐标变换,这一步骤进一步提升了整个算法的效率。     

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

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

导弹飞行视景仿真中的碰撞检测算法

针对导弹飞行视景仿真中碰撞检测实时性与精确性的不足,提出了一种优化的混合包围盒碰撞检测算法.该算法在包围盒树的上层使用Sphere,下层使用OBB;将该算法在导弹飞行视景仿真系统中实现后,分别与相交矢量碰撞检测算法、OBB包围盒算法进行对比试验和分析.结果表明,这种混合包围盒算法能够有效地提高导弹飞行视景仿真中碰撞检测的实时性与精确性.