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

比较基于包围盒的碰撞检测算法中的包围球法、轴向包围盒法、方向包围盒法、离散方向多面体法、固定方向凸包(FDH),分析结果表明:包围盒的简单性和其包裹对象的紧密性是一对矛盾,如何更好的兼顾简单性和紧密性成为关键.     

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

碰撞检测问题在机器人运动规划、计算机图形学等领域中有很长的研究历史,近年来随着虚拟现实、分布交互仿真等技术的兴起,碰撞检测问题开始成为研究的热点.目前存在许多碰撞检测算法,它们各有优劣.该文主要介绍了基于包围盒的各种碰撞检测算法,并对这几种包围盒算法进行比较,最后基于时空相关性的分析,提出改进的方法来提升算法的效率.     

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

基于包围盒的碰撞检测算法是一类重要的碰撞检测算法。文章比较了几种常用的包围盒碰撞检测算法;给出了OBB包围盒的计算算法及其改进和修正算法;包围盒树的建立算法;包围盒的重叠测试和基于包围盒的碰撞检测算法;最后以OBB验证了该类算法的有效性,正确性和鲁棒性。     

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

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

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

提出了一种基于k-dops包围盒与包围球相结合的碰撞检测算法。预处理阶段为几何对象构造包围盒二叉树,其中节点的内层构造k-dops包围盒,节点的外层构造包围球。碰撞检测阶段,首先利用包围球快速排除不可能发生相交的物体,然后利用k-dops包围盒进一步精确地判断物体对是否发生相交。通过与QuickCD算法的性能进行比较,证明了这种混合包围盒能够有效地提高复杂结构几何体之间碰撞检测的效率。     

包围盒碰撞检测算法应用研究

碰撞检测是视景仿真应用中的关键技术,研究了基于OBBTree的包围盒层次碰撞检测算法,并在视景仿真系统中得到实现。该算法首先创建能够紧密包围物体的OBB（Oriented Bounding Box）包围盒,并自上而下地创建OBB树,然后采用“分割轴”（separating axis）方法快速检测两个OBB包围盒是否相交。使用该算法进行碰撞检测的“虚拟仓库设备布放系统”在实时性和逼真性方面都取得了很好的效果。     

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

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

碰撞检测中的固定方向凸包包围盒的研究

碰撞检测在计算机图形学、CAD、仿真、虚拟现实等领域都有重要的研究意义.包围盒层次是解决碰撞检测问题固有的时间复杂性的一个有效途径.论述了用固定方向凸包(fixeddirectionshulls,简称FDH)作为包围盒进行碰撞检测的方法,证明了固定方向凸包适用于复杂环境中的精确碰撞检测,包括软体对象环境中的碰撞检测,并通过实验数据与其他包围盒进行了性能分析与比较.     

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

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

碰撞检测中的层次包围盒方法

碰撞检测在机器人运动规划、虚拟环境、分布交互仿真中都起着重要作用 ,层次包围盒方法可以有效地解决碰撞检测固有的计算复杂性 ,包围盒类型的选择是层次包围盒方法的关键。本文介绍了基于层次包围盒的碰撞检测算法 ,并着重对现有的各种包围盒类型进行了分析比较     

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

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

基于笔划包围盒的脱机手写体汉字分割算法

汉字分割是脱机手写体汉字识别预处理的重要部分，改进了基于笔画包围盒的汉字分割算法。根据方向行程长度提取出汉字的笔画，对所得笔画建立包围盒。使用4种基本合并操作得到汉字的粗略的分割。最后使用动态规划的方法实现汉字的精细分割。实验结果表明，该算法较好地解决了汉字分割中的笔画粘连和重叠问题。     

基于圆柱体轴向包围盒检测的巷道相交建模

针对岩土工程中三维巷道相交建模复杂、运算时间长的问题,根据巷道的几何特性,提出了一种圆柱体-轴向包围盒的双层包围盒检测方法。该方法能够快速查找出可能相交的三角形单元,结合三维实体布尔运算实现了一种不规则三角形网(TIN)巷道曲面相交的快速构建方法。详细讲述了圆柱体-轴向包围盒(AABB)双层包围盒碰撞检测的基本原理以及实体相交布尔运算中的关键技术,对生成的实体网格提出优化方案。通过工程实例验证,在巷道曲面相交建模中,相比于层次有向包围盒(OBB)算法,圆柱体-AABB双层包围盒在包围盒生成方面效率提高近50%,具有建模简单、检测时间短、顶层检测准确度高等特点。     

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

为提高复杂环境下多物体碰撞检测的效率,提出了一种基于均匀网格分割与椭球包围盒的并行碰撞检测算法。该算法首先用均匀网格分割法来确定相邻物体,然后用紧密性较好的椭球包围盒层次树依次把它们包围,并利用基于线程池的多任务并行处理技术实现了并行化。为降低椭球相交测试的复杂度,先预测了椭球间的相交情况,再将三维椭球降维成二维椭圆,从而整体提高了算法的效率。通过实验数据表明,相对于其他算法,该算法具有较好的性能。     

基于混合包围盒与三角形相交的碰撞检测优化算法

碰撞检测的速度与准确性是众多计算机应用程序的关键难题之一。为了提高检测速度同时兼顾准确性,将检测分为两个阶段：预处理检测阶段首先均匀剖分待测空间以确定相邻对象,然后对相邻的对象构造AABB-OBB混合层次包围盒,改进包围盒的构造方式,同时改善任务结构加速遍历过程;详细检测阶段在M?ller算法基础上加以改进,构造新的计算坐标系,对空间几何三角形进行投影降维,在二维平面上解决空间问题,从而减少算法总的计算量。实验结果表明,在保证碰撞检测准确性的前提下其检测速度大幅提高。     

Oriented bounding box and octree based global interference detection in 5-axis machining of free-form surfaces

Global interference detection is a critical problem in 5-axis NC machining of free-form surfaces. Based on the hierarchical oriented bounding box (OBB) which is used in virtual reality to detect spatial collisions between 3D objects, a new global interference detection method is developed in this paper. In this method, in order to simplify the computation process of updating tool positions and orientations in 5-axis machining, the cutter and cutter holder are modeled by a hierarchical OBB structure, whereas the workpiece surfaces are approximated by an octree. Interference detection is conducted between the tool OBBs and the gray octants of the surface octree with the separating axis theorem. With the hierarchical structure of octree, if interference is found in one octant, its sub-octants are further processed to locate the exact colliding leaf nodes and the discretized surface points contained in these leaf nodes are tested with a conventional vector calculation method for exact interference detection; if no interference is detected, all the sub-octants are then considered as interference free and are not processed further. Meanwhile, with the hierarchical structure of the tool OBBs, should interference occur between octants and the OBBs in the first level of the hierarchical structure, the sub-OBBs in the second level would be further tested. Otherwise it could be determined with certainty that there is no interference between the tool and the octant.     

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