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

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

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

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

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

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

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

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

结合轴对齐包围盒和空间划分的碰撞检测算法

目的 碰撞检测是虚拟现实,特别是虚拟装配中的关键技术。针对基于包围盒的碰撞检测算法的准确性和检测效率不足的问题,提出一种结合AABB轴对齐包围盒和空间划分的碰撞检测算法。方法 本文算法采用分步检测的方法,利用AABB算法来确定两包围盒的相交区域后,结合模型移动方向和运动趋势进行空间划分,利用碰撞检测的时空相关性,对时空相关的部分进行相交测试,通过将包围盒还原成三角面以及点的方式来保证检测的准确性。结果 本文算法与AABB层次包围盒二叉树算法、k-Dops包围盒算法以及BPS空间分割树算法进行对比实验分析。在碰撞的几何精度上,本文算法在大部分情况下与AABB算法和k-Dops算法的距离差超过阈值0.02,证明本文算法在碰撞几何精度上有明显的提高。在碰撞检测时耗上,随着碰撞检测难度的不断增加,本文算法在平移自由度下比AABB算法和BSP算法、在旋转自由度下比AABB算法和k-Dops算法的检测时间均降低了50%以上。在三角面数对算法碰撞检测时耗的影响上,当运动模型的三角面数较多时,本文算法表现出更高的稳定性。结论 结合AABB包围盒和空间划分方法的碰撞检测算法,在减少碰撞检测所需时间的同时提高了碰撞检测的准确性,可以满足虚拟装配技术中对碰撞检测算法准确性的要求,同时也能满足使用者实时性的交互习惯。     

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

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

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

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

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

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

基于AABB树的聚变堆形变部件碰撞检测算法

针对工程设计中形变部件的限元模型的碰撞检测问题,提出了一种基于AABB树的快速碰撞检测算法.对于需要分析的有限元,对几何表面进行三角化,随后建立AABB包围盒,并采用优化的AABB树算法进行空间划分;利用AABB树与包围盒排除不相交图形,采用Devillers算法测试三角形相交,并利用并行方式加快计算.实验结果表明,本算法有效提高了碰撞检测的效率,适用于复杂有限元模型的碰撞检测.     

基于AABB包围盒的碰撞检测算法的研究

利用虚拟空间中对象运动的特性和AABB包围盒的构造特性,改进了基于AABB层次包围盒的碰撞检测算法。传统的该类算法分为两个检测过程,在初步检测过程中,基于运动对象碰撞行为的局部性,改进了原来的排序方法,采用希尔排序。为了提高检测效率,在相交测试之前将检测对象细分,划分测试区域,避免了不必要的相交测试;在对可能相交的对象进行精确检测过程中,基于AABB包围盒的构造特性,对可能碰撞对象的层次包围盒树进行压缩存储,通过减少算法的存储空间来提高算法的检测速度。对算法的两个检测过程同时进行改进,实验表明在检测对象较多的情况下减少了算法所需的执行时间。     

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

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

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

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

基于包围盒和空间分割的混合碰撞检测算法

针对碰撞检测算法实时性较差的缺陷,提出基于层次包围盒和空间分割的混合碰撞检测算法。该算法采用构造对象的AABB包围盒,快速排除不可能相交的对象进行空间分割,实现虚拟环境对象的碰撞检测。实验结果表明,与经典的Rapid算法对比,该算法能够节省检测时间,提高碰撞检测的效率。     

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

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

改进的基于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的自碰撞检查算法,而且模拟效果的准确性也得以保证,是一种高效的碰撞检测方法。