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

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

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

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

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

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

轴对齐包围盒算法的研究

本文围绕如何提高虚拟环境中物体运动的真实性和实时性,对虚拟环境中的物体进行了预处理,并从相交测试复杂度、紧密性角度对几种常见的包围盒进行了比较,在分析轴对齐包围盒（AABB）树生成基础上,从存储空间的角度对AABB包围盒树的节点进行了存储优化和AABB包围盒树结构的优化,改进后显著提高了碰撞检测的速度,增强了系统的实时性.     

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

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

基于B+树存储的AABB包围盒碰撞检测算法

对于碰撞检测算法,使用传统的AABB包围盒来构建包围盒层次树时,其包围盒层次树的层数、叶子结点的个数和各结点的存储字节数是影响碰撞检测效率的主要因素.为了减少结点存储容量对碰撞检测效率的影响,提高碰撞检测的效率,文中采取B+树的存储结构来存储包围盒等信息.在包围盒相交测试之前,使得各结点存储索引有序,不需要再对各结点进行额外的排序,减少了内存开销,并且避免了不必要的包围盒测试.此外B+树的非叶子结点不存储具体的数据信息,从而减少了整棵树的存储空间.实验表明,在检测环境和检测对象相同的条件下,使用B+树存储的AABB包围盒碰撞检测算法的检测时间明显比传统的AABB算法短.     

融合DNN与AABB—圆形包围盒自碰撞检测

目的 为了解决自碰撞检测剔除率低和检测速度慢的问题,提出一种AABB（aixe align bounding box）—圆形包围盒树结构和具有二分类功能的深度神经网络（deep neural network,DNN）加速包围盒相交检测的方法。方法 对变形体构建AABB—圆形包围盒树,即对内部节点构建AABB包围盒,对叶子节点构建圆形包围盒。根据AABB—圆形包围盒生成包围盒测试树（bounding volume test tree,BVTT）,采用深度神经网络优化BVTT的包围盒相交测试和法向锥测试,输出碰撞三角形对。结果 在确定最优隐含层数和每层最优节点数保证深度神经网络达到最佳准确率的情况下,实验结果表明,在没有自碰撞的情况下,本文方法与AABB-OBB方法、经典包围盒方法耗时相同,但在自碰撞足够多的模拟场景中,融合深度神经网络的AABB-圆形包围盒方法比AABB-OBB（oriented bounding box）方法和经典的包围盒方法速度更快,整体耗时缩短了21%~37%。同时,对5种方法的更新率、检测效率和图元相交测试时间进行实验对比,发现本文方法比AABB-OBB方法和经典的方法具有更好的贴合性和更快的相交测试速度。结论 本文方法相对于AABB-OBB方法、经典包围盒方法的测试速度更快,不仅提高了自碰撞检测高层剔除率,同时降低了模拟整体耗时,更适用于实时变形体自碰撞检测领域。     

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

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

作物可视化中的碰撞检测及响应研究

将碰撞检测与响应技术引入作物可视化生长模拟,针对以NURBS曲面表示的作物叶片,提出了一种基于曲面分割技术及混合层次包围盒实现作物叶片间碰撞检测的方法.首先采用节点插入技术分割叶片曲面,然后为分割后的叶片曲面建立轴向包围盒(AABB)与固定方向凸包(FDH)的混合层次包围盒树:根节点采用AABB包围盒,以快速排除不可能相交的叶片;其它层节点采用FDH包围盒,以保证精确地判定距离较近的叶片间碰撞状态.在此基础上,根据作物叶片形态变化规律,提出了较合理、有效的冲突响应机制.实例分析表明,所建立的算法可有效地应用于作物叶片碰撞的模拟实现.     

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

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

作物可视化中的碰撞检测及响应研究

将碰撞检测与响应技术引入作物可视化生长模拟,针对以NUR13S曲面表示的作物叶片,提出了一种基于曲 面分割技术及混合层次包围盒实现作物叶片间碰撞检测的方法。首先采用节点插入技术分割叶片曲面,然后为分割 后的叶片曲面建立轴向包围盒(AAI313)与固定方向凸包(FDH)的混合层次包围盒树:根节点采用AA1313包围盒,以快 速排除不可能相交的叶片;其它层节点采用FDH包围盒,以保证精确地判定距离较近的叶片间碰撞状态。在此基础 上,根据作物叶片形态变化规律,提出了较合理、有效的冲突响应机制。实例分析表明,所建立的算法可有效地应用于 作物叶片碰撞的模拟实现。     

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

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

一种简单的平滑公平轮转调度算法

根据通用处理器共享的公平排队思想,针对数据包或信元交换,提出了一种将数据流的预订速率作为时隙分配的权值来构建动态调度树的公平轮转调度算法。其主要思路是:当有新数据流到达时,将各数据流按其权值均匀分布到完全二叉树的叶子节点上,在每个时隙开始时轮转调度算法负责从叶子节点中依次取出数据流号,发送该数据流的信元,调度复杂度为O(1)。与其他经典的公平调度算法引比,所提出的公平轮转调度算法实现简单。理论分析和仿真结果都表明,这种简单的平滑公平轮转调度算法(SSFRR)具有良好的公平性,对源端为漏桶控制的数据流能够提供端到端的有界时延,且能够提供基于数据流的QoS保证。     

一种改进的基于抽象语法树的软件源代码比对算法

在软件同源性检测方法中,基于抽象语法树的比对方法能够有效地检测出基于代码全文拷贝、修改变量名、调整代码顺序等的抄袭手段,被广泛用于抄袭检测工具中。但基于抽象语法树的比对方法对于修改变量类型和添加无意义变量的抄袭手段束手无策。针对这种情况,提出了一种基于抽象语法树的改进思想,该思想通过剪去语法树中影响判断的叶子节点的手段来还原检测原文抄袭,能够达到有效检测修改变量类型和添加无意义变量等抄袭的目的。     

数据包过滤规则的快速匹配算法和冲突检测

通过分析数据包过滤技术中的性能瓶颈,提出了过滤规则的快速匹配算法BSLT．该算法采用Trie数据结构存储规则表,并只在叶节点存储相应规则,节省了存储空间,其空间复杂度为O(NW),查找的时间复杂度为O(W);在匹配时采用二分法进行查找,提高了匹配速度,匹配的时间复杂度为O(N)．实验证明BSLT的吞吐率在100条规则内比顺序匹配算法提高了近20％,而且规则越多．BSLT的优势越明显．此外,分析了数据包过滤技术的另一个问题——规则冲突,给出了冲突的理论证明和查找算法．实验证明该算法能准确地检测出冲突规则．     

B+树索引机制的研究及优化

B+树索引是大型数据库系统中较为常用的一种索引技术。当数据庞杂时,B+树索引在查找效率和空间利用率方面还存在不足。针对该问题提出一种改进的B+树结构,首先通过调整叶子结点与非叶子结点的数量关系,以降低树的深度;然后优化原插入算法,在分裂结点前进行平衡处理(BP),以提高树的空间利用率。经试验,改进后的B+树与传统B+树相比,在查找效率和空间利用率上分别提高了10%和6%,证明对B+树的改进具有可行性。     

基于四叉树结构的数字地表模型快速生成算法设计

为了研究数字地表模型的快速生成方法，在总结传统Delaunay三角化算法的基础上，给出了一个基于四叉树结构的数字地表模型快速生成算法的详细设计，该算法的基本思想是首先利用四叉树结构来对离散点进行分割，然后对四叉树叶节点进行Delaunay三角化，再两两合并四叉树节点三角网的凸壳，以快速生成地表表格网模型，该算法是以四叉树为基本单位为实现限定边和限定多边形的快速嵌入，最后给出了算法在不同情况下的测试结果，并对测试结果进行了具体分析，给出了算法的时间效率分析和空间复杂性分析，实测数据结果表明，该算法有着较好的性能，而且也非常稳定，通过实测结果分析和算法的时间效率分析，可以得到算法的时间效率近似为O(nlog(n）），通过算法的空间复杂性分析可以看出，算法可以自动适应不同的点空间分布情况，而且采用四叉树结构也非常有利于限定边和限定多边形的嵌入。