基于包围盒的碰撞检测算法（精选6篇）
篇1：基于包围盒的碰撞检测算法
基于包围盒的碰撞检测算法
详细分析比较了基于包围盒的碰撞检测算法中的轴向包围盒法、方向包围盒法、离散方向多面体法的检测原理和检测效率,并改进了轴向包围盒碰撞检测算法,提出利用简化包围盒边缘节点实现碰撞检测的`新设想,其可行性已被初步试验证实.不仅显著提高了碰撞检测的速度,而且可以便捷地得到更为详细的碰撞检测信息,满足了进一步进行碰撞响应处理的需要,使飞行模拟机的视景系统能够实时、准确地检测出虚拟物体间的碰撞.
作 者：王立文 刘璧瑶 韩俊伟 WANG Li-wen LIU Bi-yao HAN Jun-wei 作者单位：中国民航大学,航空地面特种设备研究基地,天津,300300刊 名：中国民航大学学报 ISTIC英文刊名：JOURNAL OF CIVIL AVIATION UNIVERSITY OF CHINA年，卷(期)：25(4)分类号：V244.1关键词：碰撞检测 包围盒 飞行模拟机 算法
篇2：基于包围盒的碰撞检测算法
在三维模型广泛应用于三维游戏、虚拟现实和计算机动画等领域的趋势下，三维物体间的碰撞检测技术也随之成为这些领域的核心技术。碰撞检测的目的是检测虚拟空间中，两个或多个对象之间是否发生了碰撞，即接触或穿透。随着计算机建模技术的发展，虚拟场景中的物体数量越来越大，三维模型也越来越复杂，人们对于虚拟场景的沉浸感和逼真度的要求也与日倶增，这对碰撞检测系统的实时性提出了更大的挑战，因此，实时高效的碰撞检测算法成为当今研究的热点。
目前，从空间域方面进行划分，可以将碰撞检测算法分为两大类:基于物体空间的碰撞检测算法和基于图像空间的碰撞检测算法[1]。
基于图像空间的碰撞检测算法首先将三维模型投影到预设的二维平面，然后根据二维空间的图像采样和相应的深度信息来判断三维模型是否相交[2]。该类算法的发展是比较缓慢的，文献[3]首先采用图形硬件来辅助碰撞检测。文献[4]对用模板缓存检测每帧变化的方法进行改进，提出了一种新的改进算法。文献[5]将浑度缓存和模板缓存的功能结合在一起，加快了图象空间碰撞检测算法的计算速度。以上算法有效地利用图形硬件GPU[6]的绘图加速功能加速了碰撞检测过程，但由于算法的检测结果不够精确，并且对计算机硬件的依赖性过大，因此，基于图像空间的碰撞检测算法还不够成熟。
基于物体空间的碰撞检测算法是通过计算几何体间是否发生交集来判断物体是否相交。根据所选空间结构的不同可将其分两类:空间剖分法和层次包围盒树法。空间剖分法是将大的虚拟场景按照某种空间剖分技术划分成若干小的单元，每个物体对应一个或多个单元，只有处于同一单元的物体才可能发生碰撞，大大减少了碰撞检测的次数。常用的空间剖分技术是均匀网格、二叉树、八义树等。近几年来，研究者在对空间剖分的研究过程中取得了不少成果，文献[7]在形状分割中运用了模糊数据聚类，并有效避免了对模型的过度分割。文献[8]采用Lloyd方法对模型进行网格划分，以少量的椭球拟合3D模型的表面，取得了良好的效果。文献[9]根据三维模型的体积误差对模型进行自适应划分，并基于e-tightness对包围模型的椭球进行优化，由于该方法计算复杂，大大降低了检测效率。文献[10]为了将过度分割模型得到的相似块进行分类，将子空间聚类方法应用于共同分割中，但该方法在一些情况下容易出现错误。相比空间剖分法，层次包围盒法更广泛地被研究者采用，文献[11]提出了基于流式AABB包围盒的碰撞检测算法，该算法可在GPU上并行地执行多个流计算，大大提高了更新可变形体的速度;但该算法对数据流的预处理和映射较为复杂。文献[12]提出基于包围球和OBB包围盒的层次结构，显著提高了碰撞检测的效率;但该算法的更新比较复杂，不适用于变形体之间的碰撞。文献[13]中，Otaduy等人对层次包围盒进行有选择地重构，Zachmann等人提出了线性时间内的更新方法，两者均不同程度地提高了包围盒的更新效率。文献[14]在GPU上采用数据和线程并行来加速包围盒层次结构的构建、遍历和更新过程;但在小模型的碰撞检测中，该方法中的并行将受到局限。尽管以上算法的性能均得到了不同程度的提高，但仍然存在某些局限性。
针对单纯的空间剖分法或层次包围盒树法难以满足碰撞检测的实时性这一问题，本文提出了将两者结合的混合碰撞检测算法。该算法的主要创新点如下:
(1)采用八叉树作为层次划分树，在达到理想的叶节点的前提下，八叉树相比文献[15]中采用的二叉树有效减小了划分深度，加快了空间剖分的速度。
(2)运用同时向下遍历的方法并结合时空相关性理论加速了层次包围盒树的遍历过程。
(3)利用三角形与两面相交线的位置关系和元素分配法有效提高了三角形相交测试的效率。
1 算法描述
本文算法大体分为两大阶段:预检测阶段和精确相交测试阶段。预检测阶段进行空间剖分并为遴选出的潜在碰撞基元集合构建包围盒层次树。在精确检测阶段，遍历包围盒层次树并进行包围盒间的相交测试，若包围盒不相交，则判定对象不相交，否则，对可能相交的对象进行精确的基元相交测试。算法流程如图1所示。
2 算法实现
2.1 空间剖分
在混合碰撞检测算法中，空间剖分是作为前期的子过程存在的，因此，应尽量减小该阶段的时间开销。选取高效的空间剖分技术和适当的分解深度可以降低划分树的深度，加速层次划分树的构建和遍历。
2.1.1 空间分解技术与分解深度的确定
在空间剖分阶段需要建立层次划分树，因此选用的剖分技术是二叉树或多叉树。研究表明，树的度数越大，划分深度越小，反之，树的度数越小则划分深度越大。此外，确定分解深度时，在最大限度地减小划分树的深度的同时，还要尽量减小叶节点的体积使其包含尽可能少的基元数目。
综合考虑以上因素，可以通过选择度数稍大的划分树，在达到理想体积的叶节点的同时，降低划分树的深度。目前，国内外研究人员广泛使用二叉树并证实其具有较好的性价比，但事实证明，该技术会导致层次划分树的深度过大，从而增大构建和遍历层次划分树的时间开销。针对以上问题，本文算法采用度数稍大的八叉树作为空间剖分技术。
2.1.2 多叉树节点的分割
构建八叉树的过程中，选用合理的节点分割方法可以使同一个基元与多个单元格同时相交的概率大大降低。本文算法中的节点分割方法是在朴素八叉树节点分割方法的基础上进行改进得来的。在朴素八叉树节点分割方法中，假设物体运动的空间域是AABB型的，三边的长度分别是x0,y0,z0，那么划分节点时每次可以以如下的方式将空间节点划分成8个部分:依次在x0/2,y0/2,z0/2处将空间域进行三次剖分，得到8个三条边长分别为x0/2,y0/2,z0/2的长方体子空间。如此持续划分，直到每个子域包含特定的三角形面片数目为止。该方法虽然简捷，但也存在如下的不足:
1)当x0,y0,z0相差较大时，每次划分后得到的子部分的形状过于狭长，而不是类似立方体的形状，导致效率降低。
2)当x0,y0,z0相差很大时，划分到最后阶段，最短的棱将无法被继续剖分，最终只能划分出4个不同的子空间域。
针对以上不足，本文算法在对每个父节点空间结构进行划分前，先进行一次判定，根据判定结果决定如何对空间结构进行剖分，仍然假设待剖分区域是长方体，长宽高分别为x,y,z，那么判定规则的伪代码如下:
按x/2,y/2,z/2划分成8叉树
构建完成八叉树后，将对象的全部基元分配到八叉树的节点上，检测各节点的基元来源，把基元来自于两个或两个以上对象的节点称为潜在碰撞单元格PCVs(Potentially Colliding Volumes)[16]，并将这些PCV导入包围盒层次树阶段进行进一步检测。
2.2 包围盒的选取
由于碰撞检测过程中需要实时地构建和遍历包围盒二叉树，因此，选取相交测试高效的包围盒，减少测试的时间开销对提高算法的效率至关重要。本文将评价包围盒碰撞检测算法性能的函数[17]中的代价改为时间耗费，计算公式如下:
其中:T是碰撞检测耗费的总时间;NV是相交测试中参与测试的包围盒对的数目;CV是单对包围盒相交测试耗费的时间;NP是参与基元测试的基本几何元素的对数;CP是基元测试中，单对基本几何元素相交测试耗费的时间;NU是物体运动后需要更新的节点数;CU是更新单个节点耗费的时间[18]。根据式(1)的指标，应该选取紧密性良好且计算简捷的包围盒，综合考虑以上因素，AABB是最优选择。
2.3 包围盒二叉树的遍历
本文采用从上向下的方法构建包围盒二叉树，并采用同时向下遍历的方法和时空相关性思想，来加快对层次树的遍历速度，从而达到提高算法效率的目的。
2.3.1 同时向下遍历的规则
传统的遍历规则使测试的步骤繁琐，工作量大，本文采用同时向下遍历的方法，大大减小了工作量，加速了遍历过程。同时向下遍历的规则简言之即若两节点发生碰撞而且两节点不是叶子节点时，同时比较它们的子节点，即同时比较(A-left,B-left)、(A-left,B-right)、(A-right,B-left)、(A-right,B-right)。若两节点不发生碰撞，则终止遍历;若两节点发生碰撞且它们都是叶子节点，则进行精确的基本几何元素间的相交测试。
2.3.2 时空相关性对遍历过程的优化
时空相关性简言之即由于物体运动的连续性，使得活动对象在相邻两个时间采样点的位置变化很小，而且在前后两个时刻的相交状态相关联，因此可以根据两物体在上一时刻的相交状态来推断当前时刻的相交状态。
依据上述理论，可以在某一时刻选取层次树的各条树枝上第一个因不发生碰撞而导致遍历终止的节点作为标记点，并使用二叉堆来储存管理以上标记节点。遍历时，观察两个物体的位置关系，若两物体逐渐远离，则从根节点开始采用同时向下遍历的方法对包围盒二叉树进行遍历;若两物体逐渐靠近，则从标记节点开始采用同时向下遍历的方法对节点进行遍历。以一棵层次包围盒树为例，如图2所示，黑色节点即为标记节点，即在t时刻该树与另一棵树进行相交测试时，因未发生碰撞而导致遍历停止的节点。
在下一时刻t+1，如图3所示，可以从t时刻标记的黑色节点开始遍历，截止至t+1时刻物体仍未发生碰撞，黑色节点为更新的标记节点。
如图3所示，如果t+1时刻从根节点开始遍历则需要访问的节点是E0,E1,E2,E3,E4,E7,E8,E9,E10，一共9个节点，而如果从t时刻标记的节点E2,E3,E9,E10，开始遍历则只需要访问E2,E3,E7,E8,E9,E10，一共6个节点，可见，从标记节点开始遍历在一定程度上提高了遍历效率。
2.4 AABB与AABB的相交测试
由于AABB包围盒的各边均平行于坐标轴，因此，可以利用投影法来判断两个AABB包围盒的相交情况。分别将两个AABB包围盒投影在坐标轴上，仅当两包围盒在3个坐标轴上的投影均相交时，才可判定两个AABB包围盒相交，否则，判定两个AABB包围盒不相交。
2.5 基元相交测试
2.5.1 两异面三角形的相交测试
由于每个三角形必存在于一个平面，若两个异面三角形相交，其所在的平面也必相交于一线，因此可以根据两个异面三角形与其所在的两面交线的关系来判断两个三角形的位置关系。当两个异面三角形与两面交线的位置关系如以下三种情况时，可判定两三角形相交:
(1)三线合一。两三角形分别与两面交线交于一条线段，且两线段至少有一个交点，如图4(a)所示。
(2)点线合一。一个三角形与两面交线交于一条线段，另一个三角形与两面交线交于一点，而且交点在线段上，如图4(b)所示。
(3)两点合一。两个三角形分别与两面交线交于一点，并且两点重合。
在具体地判断某个三角形与另一个三角形所在平面的位置关系时，可以根据该三角形的三个顶点到该平面的有符号距离的符号来判断，具体方法如下:
假设两个三角形P0(V0,0,V0,1,V0,2)和P1(V1,0,V1,1,V1,2)，其中V0,i(i=0,1,2)和V0,j(j=0,1,2)分别表示三角形P0和P1的顶点序列，三角形P0和P1分别位于平面π0和π1内，两平面法向量分别为N0和N1，其中法向量表示如下:
πk的平面方程为:
式中，V为πk上的点。引入一个新节点V0,3=V0,0将P1顶点V1,i(i=0,1,2)依次代入式(3)，计算顶点V0,i到平面π1的有符号距离:
对此距离讨论得:
(1)若式(4)中的d0,i符号均相同，说明三角形P0与平面π1不相交，所以P0和P1不相交;
(2)若式(4)中的d0,i等于0，说明三角形P0和P1共面，此时执行同一平面内的二维相交测试;
(3)若式(4)中的d0,i的符号不全相同，则三角形P0与平面π1相交于一条直线L，同理，若P1与平面π2也相交，则也必交于于直线L，此时，观察两三角形与直线L相交得到的两条线段的位置关系，若两线段至少有一个交点则判定两三角形必相交。
2.5.2 多个三角形的相交测试
对多个三角形进行相交测试时，常遇到多个三角形共有相同元素的情况，此时巧妙地避免对相同元素的重复测试可以提高相交测试的效率。本文采用元素分配法将多个三角形共有的相同元素进行分配。元素分配法的主要思想是，任一个元素必须被分配且仅被分配给一个与之相关的三角形。这样就保证了在所有与该元素有关的元素对的检测中，该元素仅作为所属三角形的元素参与元素对的检测，有效避免了对同一元素的重复测试。
另外，在元素对的碰撞检测中，不可避免地会对实际并未发生碰撞的元素对进行碰撞检测，无形之中使碰撞检测的效率降低。本文依据碰撞检测的时空相关性，选出当前时刻实际并未发生碰撞但对其进行了碰撞检测的元素对，并且重新分配这些元素对中的元素。下面是元素分配的一个例子，如图5所示。
如图5(a)所示，某时刻，假设Y2和Y3的包围盒相交，边EF被分配给了Y2，边GH被分配给了Y3，那么，需要对(EF,GH)进行相交测试，但是由图知，边EF与边GH并不相交，此时对元素对EF与GH的检测是无用的。下一时刻，如图5(b)中所示，假设Y2和Y3的包围盒仍然相交并且边EF与边GH也仍不相交，那么根据碰撞检测的时空相关性和图5(a)中的检测结果，将EF分配给Y1，将GH分配给Y4，这样就避免了对元素对EF和GH进行无用检测。
3 实验结果与分析
实验在内存1GB,CPU Intel Celeron M1.86Hz，显卡NVIDIA Geforce FX 6600，采用VC++6.0编程语言的PC机上实现。Rapid算法是经典的基于OBB包围盒的碰撞检测算法，实验对比在同一虚拟碰撞场景中，在三角形重叠数目相同的前提下进行，将本文提出的基于空间剖分和包围盒的混合碰撞检测算法与Rapid算法进行对比分析。实验选用两个几何结构相对复杂的茶壶模型(8 455个顶点)进行碰撞检测，如图6显示了实验中某一时刻几何对象发生碰撞的情况。通过对两种算法在10次碰撞检测中的碰撞检测时间的对比，得到了表1中的实验结果，从表1中可以看出，随着三角形重叠对数的增加，本文算法相对于Rapid算法的碰撞检测效率提升倍数逐渐增大。图7显示了两种算法在每次碰撞检测中的平均碰撞检测时间，由图可知，本文算法在不同的碰撞检测复杂程度下消耗的时间波动不大，在三角形重叠对数最大的情况下，本文算法耗时仅为18.4毫秒;在相同条件下，随着发生碰撞的三角形对数的增加，Rapid算法与本文算法的检测耗时的差值越来越大，这证明了在复杂碰撞场景中，本文算法比Rapid算法具有更高的检测效率。
4 结语
本文提出了一种新的基于空间剖分和包围盒的混合碰撞检测算法，该算法选用构建快速的八叉树作为层次划分树，有效地缩短了子过程空间剖分的时间开支;利用同时向下遍历的方法，结合时空相关性的思想，加速了对层次包围盒树的遍历;根据三角形与两面交线的位置关系并运用元素分配法来对三角形相交测试进行优化，显著提高了基元相交测试的效率。实验结果表明，与传统的Rapid算法进行比较分析，该算法明显减小了平均碰撞检测时间，有效提高了碰撞检测的实时性和真实性。由于算法在层次包围盒阶段使用的是AABB，在以后的研究中，试图采用紧密性更好的K-Dop包围盒或OBB包围盒，并利用文献[13]中的更新方法及时地对包围盒层次树进行更新，使算法在达到更高的精确度的同时，也适用于变形体的碰撞检测。
摘要：针对碰撞检测的实时性和逼真度较差的缺陷,提出一种新的混合碰撞检测算法。该算法在空间剖分阶段采用八叉树技术有效降低了层次划分树的深度,提高了层次划分树的构建速度,快速剔除了不可能相交的基元对。在精确检测阶段,采用同时向下遍历的方法并结合时空相关性对层次包围盒树的遍历过程进行优化,利用三角形与两面交线的位置关系快速判定两异面三角形的位置关系,并采用元素分配法避免了对公共元素的重复测试和无用的元素对测试,使基元相交测试的效率显著提高。实验结果证明,与经典的Rapid算法相比,该算法有效地减少了碰撞检测的时间开销,提高了碰撞检测的实时性和真实感。
篇3：游戏引擎中碰撞检测算法研究
关键词：游戏引擎；碰撞检测；包围盒
中图分类号：TP391.41 文献标识码：A 文章编号：1674-7712 （2014） 04-0000-01
近年来虚拟现实技术和分布式交互仿真技术的应用越来越广泛，计算机模拟现实世界真实性的需求越来越高，这种真实性的关键在于如何自然合理的模拟现实世界中各物体间的相互关系即相互碰撞问题。为了保证计算机模拟环境的真实性，虚拟环境中的对象进行各种运动时必须实时检测物体间是否发生了碰撞，而且虚拟环境中的其它对象要能够做出及时地响应，避免现实生活中不可能出现的如物体间的穿透等现象的发生。在游戏引擎软件中的大规模复杂动态场景中，对象的几何复杂度直接导致了对象间碰撞检测计算量大、较为耗时，使得碰撞检测问题更加复杂，通过对碰撞检测算法的研究及优化，可以提高碰撞检测算法的性能、提高碰撞检测的效率。
一、 游戏引擎
游戏开发的核心技术是游戏引擎，游戏引擎是指通过整理和封装通用技术细节来形成面向游戏应用的接口函数，游戏开发人员只需调用游戏引擎框架中相关的函数而不用关心底层技术是如何实现的。完整的游戏引擎是由许多游戏功能组件共同来组成的，它具有分明的层次结构，一般包括物理数学支持层、图形渲染内核、系统层、游戏介质层以及开发工具层。其中最关键的部分是图形渲染内核，包括配置子系统、图形子系统、声音子系统、输入子系统和时效子系统，它们互相配合共同完成游戏中的各种效果。现在市面上有很多商业引擎，基本上都采用了底层算法思想以及最新的图形图像学技术，表现出非常好的开发性和延展性，又各有各的特点，对于特定网络游戏的开发具有重要的意义。
二、碰撞检测
碰撞检测是构建游戏引擎最主要的环节之一，也是衡量一款游戏是否达到预期效果的标准。碰撞检测问题在计算机图形学、智能机器人等领域都有着悠久的研究历史，它是基于“两个不可穿透的物体不能同时共享相同的空间区域”这个现实生活中广泛存在的事实设定的。
（一）碰撞检测概念
碰撞检测就是对物体在运动过程中可能出现的碰撞进行检查，避免碰撞的发生，或进行碰撞的响应处理。碰撞检测的基本任务就是确定两个物体之间是否发生了接触或穿透，即两个多面体的求交测试问题。碰撞检测是构造虚拟环境的核心部分，游戏中如果不进行碰撞检测，人物就可以在场景中任意游走，就会出现穿墙过树等与现实世界不符的行为规则，所以说合理精确的碰撞检测在游戏中是必不可少的。最简单的碰撞检测就是对两个输入模型中所有几何元素进行两两相交测试，随着输入模型的复杂度越来越高，相交测试数目成几何级数增长，大大影响游戏运行的效率，因此，如何提高算法的速度以保证游戏中的实时交互性是碰撞检测的核心。
（二）碰撞检测分类
碰撞检测方法可以分为两类：空间分解法和层次包围盒法。空间分解法是将整个虚拟空间划分成体积相等的若干小单元格，并且只对同一单元格或相邻单元格的几何元素进行相交测试。层次包围盒法是用体积较大而几何特性相对简单的包围盒来近似描述复杂的几何元素，先对包围盒进行相交测试，在此基础上只需对包围盒重叠部分进行进一步的相交测试。两种方法都使用了层次结构模型，都是为了尽可能地减少相交测试的几何元素数目。空间分解法适用于稀疏环境中几何对象分布比较均匀的碰撞检测，而层次包围盒法适用于复杂环境中几何对象的碰撞检测，它的应用更为广泛，本文主要研究的就是基于层次包围盒的碰撞检测算法。
三、基于层次包围盒的碰撞检测算法
（一）层次包围盒法原理
层次包围盒法的基本思想是用体积较大而几何特性相对简单的包围盒来近似地描述复杂的几何对象，通过构造树形层次结构可以将包围盒越来越逼近对象的几何模型，最终可以获得与实际对象有着几乎完全一致的几何特性的包围盒，由于包围盒的相交测试比直接对几何对象进行相交测试要简单的多，因此，在对几何对象进行碰撞检测时，首先对包围盒进行相交测试，这样能够快速排除许多不相交的几何对象，如果相交再对包围盒重叠部分进行进一步的相交测试，提高了算法的执行效率。
（二）常见的包围盒
通过使用简单几何模型包围复杂对象进行碰撞检测大大提高了碰撞检测的效率，但并不是所有几何模型都可以充当包围体的，它必须是具有构造简单、占用内存空间小、有良好的紧密性、相交测试计算量小且能够快速更新等优势。常见的包围盒有以下几种：（1）轴向包围盒：包含该对象且各边与坐标轴平行的最小正六面体。它的简单性好，紧密性差，当对象旋转后需要重新进行计算。（2）方向包围盒：包含该对象且方向任意的最小正六面体。紧密性较好，实时性较高，当对象旋转后只需对包围盒进行同样的旋转。（3）离散方向多面体包围盒：包含该对象且有k个固定方向的凸多面体结构。紧密性较好，但需要合理选取平行平面对的个数和方向。（4）球包围盒：包含该对象的最小球体。简单性好，紧密性差，当对象旋转后包围球不需要作任何改变，当对象变形后需要重新计算。
层次包围盒法是目前应用最广泛的碰撞检测算法，各种包围盒算法有各自的优劣，针对不同的应用场合选择不同的方法，以达到简单、紧密、实时的要求。
（三）层次包围盒树
虽然采用包围盒代替基本几何对象进行相交测试的方法提高了碰撞检测性能，但还需进行两两包围盒的相交测试，如果将包围盒整合到树形结构中，应用层次包围盒技术，两两包围盒之间相交测试的时间复杂度可以由平方级降为对数级。在树形结构中，根节点代表对象本身，所有叶子结点组成对象的基本几何元素。可以采用自顶向下或者自底向上的构造方法来构造层次包围盒树。
四、结束语
随着虚拟环境的复杂性越来越高，对于碰撞检测算法的实时性和精确性还要不断进行深入研究，通过不断改进优化算法并应用于游戏引擎中，可以有效地解决大型复杂虚拟环境下的碰撞检测问题。
参考文献：
[1]黄杨飞.大场景3D游戏引擎技术研究与实现[D].浙江师范大学，2011
篇4：基于包围盒碰撞检测算法研究
1 碰撞检测基本原理
1.1 相关定义
碰撞检测就是检测虚拟场景中不同对象之间是否发生了碰撞。从几何上讲,碰撞检测表现为两个多面体的求交测试问题;按对象所处的空间可分为二维平面碰撞检测和三维空间碰撞检测。平面碰撞检测相对简单一些,已经有较为成熟的检测算法,而三维碰撞检测要复杂的多。在VR系统中,主要是如何解决碰撞在检测的实时性和精确性的矛盾。不同的应用场合,对实时性和精确性的要求不尽相同。按照是否考虑时间参数,碰撞检测又分为连续碰撞检测和离散碰撞检测。
1.2 碰撞检测的常用算法
碰撞检测算法总体上可以分为空间分解法和层次包围盒法两大类。空间分解法是将虚拟空间分解为体积相等的小单元格,只对占据同一单元格或相邻单元格的几何对象进行相交测试。层次包围盒法师利用体积略大而形状简单的包围盒把复杂的几何对象包裹起来,在进行碰撞检测时首先进行包围盒之间的相交测试。显然,包围盒法对于判断两个几何对象不相交十分有效。包围盒相交,并不意味着两个几何对象一定相交,所以包围盒的选择应满足简单性和紧密性的要求。空间分解法由于存储量大及灵活性不好,应用不如层次包围盒法广泛。层次包围盒法根据包围盒的不同又分为轴向包围盒(Axis-Aligned Bounding Boxes:AABB)检测算法、方向包围盒(Oriented Bounding Box:OBB)检测算法、离散方向多面体(Discrete Orientation Polytopes:k-DOPs)检测算法、时空包围盒(Space-Time Bounding Boxes:STBB)检测算法等。这些算法在不同的场合得到广泛的应用。
2 基于包围盒碰撞检测算法的改进
2.1 OBB包围盒检测算法
一个给定对象的方向包围盒OBB被定义为包含该对象且相对于坐标轴方向任意的最小长方体。假定一个OBB的中心为c,三个相互正交的方向为v1,v2和v3,三方向上边长为r1,r2和r3。则OBB的区域为:R={c+ar1v1+br2v2+cr3v3,-1≤a,b,c≤1}。
OBB的计算关键是寻找最佳方向,方法主要是利用顶点坐标的一阶和二阶统计特性,首先计算顶点分布的均值u,将它作为包围盒的中心,然后计算协方差矩阵C。基本几何元素为三角形,第i个三角形的顶点用pi,qi和ri表示,则均值μ和协方差矩阵C计算如下:
其中,n为三角形的数目,,它们均为R3中的一个向量,Cjk为3×3协方差矩阵C中的元素。
协方差矩阵C的三个特征向量是正交的,正规化后可作为一个基底,它确定了OBB的方向,分别计算各个元素的顶点在该基底的三个轴向上的最大值和最小值,以确定该OBB的大小。
OBB间的相交测试基于分离轴理论。若两个OBB在1条轴线上(不一定是坐标轴)的投影不重叠,则这条分离轴称为分离轴。若1对OBB间存在1条分离轴线,则可以判定这两个OBB不相交。对任意两个不相交的凸多面体,其分离轴或者与任一多面的某一面平行,或者同时垂直于每个多面体的某一条边。因此,对1对OBB,只需测试15条可能是分离轴的轴,只要找到一条这样的分离轴,就可以判定这两个OBB是不相交的,如果这15条轴都不能将这两个OBB分离,则它们是相交的。两个OBB的相交测试最多需要15次比较运算,60次加法运算,81次乘法运算和24次绝对值运算。
2.2 对象运动后包围和的更新
对于刚体运动来说,运动分为平移和旋转两类。运动对象中虚拟环境中的运动具有很大的随意性。我们无法得到关于运动的方程,但是可以从输入设备得到当前时刻对象相对与原始状态的位置参数和方向参数。沿x轴、y轴、z轴的平移参数,对应于一个平移向量t=(x,y,z)T;沿x轴、y轴、z轴的旋转参数θ、φ、ω的变换矩阵:
所以可以用一个变换f:x→Rx+t描述对象从原始状态到当前状态的变换,也可以分解为一个平移变换ft:x→x+t和一个旋转变换fR:x→Rx。
平移运动时,可以对其包围盒做同样的平移转换,即可得到新位置处的包围盒。当对象发生旋转时,其新位置处不能通过简单的旋转得到,不同包围盒类型可以采用不同的更新方法。但是一个对象的OBB完全是由它自身的集合属性决定的,不受任何外界因素的影响。因此,当活动对象运动后,如果对其OBB进行同样的运动,则得到的仍然是包围它的最小的OBB包围盒。因此基于OBB的碰撞检测算法用于活动刚体对象时的处理时非常简单。只需要对OBB的基底乘以一旋转举证,并加一平移向量即可,OBB在各个基底方向上的大小则保持不变。
3 结论
层次包围盒算法可以快速有效的进行碰撞检测。包围盒类型的选择直接关系到算法的执行效率,我们希望在保证一定精确性的前提下,大幅提升算法的执行速度。实验表明,采用了排序技术和缓存技术,能够得到满意的算法执行速度。
参考文献
[1]张茂军.虚拟现实系统[M].北京:科学出版社,2001:2-80.
[2]马登武,孙隆和,终明安.虚拟场景中的碰撞检测算法[J].火力与指挥控制,2004,8(4):46.
篇5：基于包围盒的碰撞检测算法
关键词：AABB-OBB包围盒,碰撞检测,玉米叶片
0 引言
随着信息技术与农业科学的不断融合,数字植物研究得到了前所未有的发展。在碰撞检测方法中,层次包围盒树法[1,2]应用最为广泛。它是以简单图元类型包裹测试对象,构建层次结构并实施盒体测试的方法。常见的图元类型有球体盒、轴对齐包围盒(AABB)[3]、非轴向对齐包围盒(OBB)[4]和离散有向多面体(k-DOPs)[5]。此类方法计算简单适用性较强,通过盒体重叠测试,可以快速剔除不相交测试对象,有效提高碰撞查询效率。李长锋等也曾基于四面体网格提出了在虚拟场景中的碰撞检测方法[6]。鉴于植株器官以叶片居多,发生叶片穿透的现象极为常见,故本研究选取具有代表性的玉米叶片为研究对象,探索叶片之间的碰撞检测。基于AABB盒相交测试简单和OBB盒紧密性好的优点,本文提出一种适用于玉米叶片特点的AABB-OBB包围盒策略。多次模拟实验表明,该方法能快速检测玉米叶片的穿透,对相似特征叶片均可适用。
1 数据获取与预处理
本研究中所用玉米叶片数据均由数字化仪扫描得到。数字化仪使用方便快捷,能够准确获取叶片空间信息,大大缩短了三维重建时间。通过数字化仪采集来的数据还只是散乱的点云数据,需要经过曲面参数化才能更为逼真地表现叶片形态。笔者采用非均匀有理样条曲线(NURBS)来实现曲面参数化,即
undefined (1)
式中 Vi,j—控制顶点;
Wi,j—权因子;
Bi,k(u)—沿u向的k次B样条基函数;
Bj,k(w)—沿w向的l次B样条基函数。
参数化过程中剔除了大量冗余顶点,主要保留体现几何特征的顶点,包括叶脉和叶边缘等特征点,最终构成参数化网格。为了简化整株模型,在参数化网格上提取特征点网格,特征点主要为叶脉曲率变化较大处横向分布的系列顶点,包括叶尖和叶边缘等,如图1所示。单叶特征点网格包含119～150个特征点,195～240个三角面片,每个面片均保证了与原始网格有较好的拟合性。
长期的观察实验表明,玉米叶片主要特征点上的交叉碰撞对叶片几何空间变化起着关键作用。基于此,笔者以玉米叶片特征点网格为研究对象,结合在生长过程中常见的交叉情况,探索快速的碰撞检测方法。
2 AABB-OBB包围盒
轴对齐包围盒(AABB)是应用最为广泛的包围盒类型之一,其最大的特点是能够实现快速的相交测试,即只需沿3个坐标轴判定是否相交,如图2(a)所示。此外,AABB盒数据存储量小,只需要记录2个最大最小值坐标。因此,本研究对玉米叶片网格首先构建AABB盒,并实施重叠测试。若发生重叠,则对AABB盒空间均匀分割1次八叉树,再执行重叠测试。通过AABB盒的快速测试,可以高效剔除掉不相交对象。考虑玉米叶片长且宽的特点,单纯AABB盒包裹紧密度不够。故在AABB盒检测后,若仍然存在可能相交情况,则对该子空间网格应用OBB盒做深入检测。OBB盒构造采用协方差矩阵计算得到。设节点叶片网格所含三角形数为n,采用如下两式可计算得到紧凑OBB盒。则有
undefined (2)
undefined (3)
其中,式(2)计算OBB中心坐标,pi,qi,ri为第i个三角各个顶点的第u个分量,所得u即为该分量中值。式(3)计算OBB盒的三个轴向量,Cj,k为第(j,k)个元素的方差。生成的OBB盒中最长轴往往倾向于中心叶脉首尾连成的直线。与AABB盒相比,OBB盒紧凑度高,同时测试代价也较高。OBB盒测试一般采用分离轴测试法,设两盒中心距为d,在分离轴上投影长度分别为r1和r2,若r1与r2的和值s小于中心距d意味着处于分离状态,此时可判定该OBB盒测试对未相交。最坏的情况是经过15次测试s均大于d,此时可认定测试对相交,如图2(b)所示。为了提高测试效率,本研究以其中一OBB盒为局部坐标系,将另一OBB盒转移到该局部坐标系下进行测试。考虑到叶片常见交叉情况,对分离轴测试顺序上进行了优化。设两测试对象分别为A与B,并以A为局部坐标系中心。首先,测试以盒A与盒B的最长轴为分离轴进行测试,紧跟着其他轴向分离轴。然后测试盒B各个轴向量与盒A最长轴叉积生成的分离轴,最后测试其他分离轴。对于重叠测试相交的对象,需要进一步剔除冗余的测试空间。本文中采用了最长轴中值分割法来自上而下的构造OBB二叉树,如图3所示。
由于沿叶脉延伸方向往往倾向于最长轴,故分割点大多集中在叶脉曲线。对于越界的三角面片,通过计算质心坐标,将其归并到最近的OBB中。综合考虑叶片模型的数据量以及OBB-OBB盒测试消耗,设定树的深度不超过3。在真实场景中,叶前端的交叉状况最常见。受此启发,二叉树节点根据所属叶片部位获得一个相应的遍历优先权值k。其中,偏向于叶尖部位的节点系数设为1,远离叶尖的节点系数设为0.8。假定树深度增加1,所在节点k值减少0.1。如此,构成了以根节点初始k值为1的优先遍历树。在遍历搜索中,优先测试k值高的节点,如图2(c)所示。
3 图元测试
当包围盒重叠测试剔除了大部分分离对象后,需要在基本图元之间执行精细测试,以确定相交状态。由于大多数模型都采用三角网格构建,故针对此类的图元测试实际为三角面片之间的相交测试。一般两个三角面片需要进行6次顶点—面测试和9次边—边测试,即最多15次测试即可确定相交状态。许多学者对三角测试以及三角网格进行了大量工作,undefined与Held分别提出了针对三角对的区域相交算法[7,8],二者均高效廉价。Devillers在前人基础上得出更为快捷的相交算法[9]。本研究采用了Devillers算法来实现三角测试。该算法首先计算三角形a和b的平面方程,分别测试其一三角形各顶点与另一三角平面的侧向关系。若两三角顶点都均未在另一平面一侧,则两三角形平面必相交于一条直线L,需要进一步计算L相交区域。此时,通过限定位于另一三角形平面一侧的顶点为当前三角形的首顶点,依次交换其余顶点从而获得三角形的“规范格式”。最终L上的区间相交计算可变成相应顶点上两个标量三重积测试[10]。该算法尽管逻辑较为复杂,但在实际执行时快捷方便。
针对交叉部分可能出现在分割轴以及横跨两节点的情况,笔者开辟一个块数据存储分割轴附近的三角片索引信息。在盒体重叠测试后,若对象A中某节点与对象B中某一层相邻两节点交叉,则测试对象B中涉及的少量分割三角面片与A中该节点的相交关系。该过程通过最多13条分离轴测试实现,包括:①三角形上的一条面法线;②OBB盒节点的3条方向向量;③二者边—边组合叉积形成的9条分离轴。
为了减少测试消耗,实际只执行前面主要的4条分离轴测试。由于叶片相交部位常呈带状区域,若不相交,则仍然按常规的遍历过程,执行三角对测试。若该测试结果呈相交状态,则图元测试将简化为以B中该分割轴为中心的少量三角面片与A节点三角面片的相交测试,且无须遍历对象B中两节点内所有三角面片。
玉米叶尖部位是主要的扭曲的部位,在几何网格上多表现为自碰撞。尽管玉米叶片边缘起伏较大,但自碰撞几乎不发生。因而,本研究在测试过程中重点对叶尖网格执行自碰撞检测。根据叶片三角面片总数,设定10%～15%的查询容量,仍采用Delliers算法对所含三角面片做自碰撞检测。
4 实验与结果
笔者采用Visual C++开发平台实现了本文所述方法。实验所用配置为:Inter Pentium 4,2.5GHz CPU,2GB内存,以及NVidia GeForce 9500GT显卡。在该机器上,笔者模拟了相似于真实场景的玉米叶片模型碰撞场景,如图4(a)和(d)所示。通过AABB盒测试后,对可能相交对象构建OBB盒,如图4(b)和(e)所示。经过OBB树遍历,确定相交区域,并对该区域内的特征点网格进行三角测试,最终获得相交状态。图4(c)和(f)所示不同灰度区域即为交叉三角面片。
多次实验结果表明,改良后的分离轴测试平均次数为5.8次,而未优化的平均测试次数为6.4次。在OBB树重叠测试中,叶尖节点测试结果约占全部遍历结果的68%。通过优先对叶尖节点的测试,有效提升了整体检测命中率。应用本优先权值的方法在遍历过程中取得了一定的效率提高。此外,相比未做任何优化的图元测试,采用跨节点的图元处理方法在该交叉情况下节省了约30%的图元测试时间。实验结果统计:本方法检测准确率达到99.6 %,平均2叶片检测耗时8.9ms。
5 总结与展望
综上所述,本文提出了一种AABB-OBB混合包围盒检测方法,在玉米叶片上实现了准确快速检测。依据玉米叶片常见交叉情况,对重叠测试和图元测试进行了一定优化,取得了较好效果,可在相似特征叶片类型上适用。
值得注意的是,整个检测耗时主要集中在OBB盒的盒体计算,今后将尽量采用AABB盒实现检测过程。下一步,计划在群体植株尺度上探索基于特征点网格的快速碰撞检测方法。
参考文献
[1]P Jiménez,F Thomas,C Torras.3D collision detection:a sur-vey[J].Computers&Graphics,2001,25(2):69-285.
[2]马登武,叶文,李瑛.基于包围盒的碰撞检测算法综述[J].系统仿真学报,2006,18(4):1 058-1 061,1 064.
[3]Gino van den Bergen.Efficient collision detection of complexdeformable models using AABB trees[J].Journal of GraphicsTools,1997,2(4):1-14.
[4]Stefan Gottschalk,Ming C Lin,Dinesh Manocha.Obb-tree:A hierarchical structure for rapid interference detection[C]//In SIGGRAPH,1996:171-180.
[5]James T Klosowski,Martin Held,Joseph S B Mitchell,et al.Efficient collision detection using bounding volume hierar-chies of k-DOPs[J].IEEE Transactions on Visualizationand ComputerGraphics,1998,4(1):21-36.
[6]李长锋,郭新宇,赵春江,等.基于空间散列法的虚拟植物碰撞检测算法[J].计算机应用与软件,2009,26(4):242-245.
[7]Tomas M.o.ller.A Fast Triangle-Triangle Intersection Test[J].Journal of Graphics Tools,1997(2):25-30.
[8]Held Martin.ERIT:a collection of efficient and reliable in-tersection tests[J].Journal of Graphics Tools,1997,2(4):25-44.
[9]Devillers Olivier,Philippe Guigue.Faster Triangle-TriangleIntersection Tests[C]//Technical Report 4488,INRIA,2002.
篇6：基于包围盒的碰撞检测算法
碰撞检测问题在计算机图形学领域中有很长的研究历史,近年来,随着虚拟现实中的场景模型越来越多样化,场景规模也不断扩大,如何有效地提高碰撞检测的效率再一次成为研究的热点[1]。碰撞检测系统的输入模型是构成几何对象的基本几何元素(通常是三角形) 的集合,其任务是确定在某一时刻两个模型是否发生干涉,即它们的交集是否不为空。目前的几何模型多为四面体网格模型,最原始最简单的碰撞检测算法就是对两个输入模型中的所有基本几何元素进行两两相交测试,当模型的复杂度增高时,这种O(n2) 次的相交测试显然是无法容忍的。因此减少基本几何元素两两相交测试的数目,提高算法速度,以保证虚拟环境的实时交互性是碰撞检测问题的核心。本文采用八叉树结构将场景中的各节点按空间位置进行有效的组织归类,通过树结构的遍历方式对场景中的各节点实施碰撞检测,从而达到减少检测次数的目的。而在检测过程中采用OBB作为几何节点的包围盒能够更精准地反映轮廓,增加碰撞检测的精度[2,3]。
1 相关工作:八叉树的划分[4]
本方法的设计是建立在八叉树生成算法的基础上的,生成算法已经对场景进行了空间八叉树的划分,并做了很好的封装,可以很好地处理XML格式的模型文件。场景通过引擎处理后,生成如下的八叉树数据结构:
其中index是树节点的序号(采用深度遍历排序);depth描述的是八叉树节点的深度信息。box主要描述该空间八叉树节点的包围盒信息;father记录的是该节点的父节点;children记录以本节点为父节点的8个子节点,叶子节点无子节点;mesh是叶子节点特有的成员变量,记录该叶子节点所包围立体空间中的所有模型节点。
2 碰撞检测[5]
本文提到的碰撞检测方法,主要是先通过八叉树的空间节点与运动节点进行相交检测,确定需要做进一步检测的八叉树叶子节点,取出叶子节点中包含的所有几何节点,利用几何节点的OBB包围盒与运动节点做进一步检测,从而确定所有的碰撞节点。
2.1 包围盒的定义与构建
在整个碰撞检测过程中我们一共定义了两种形式的包围盒:AABB和OBB。
AABB(Axis Aligned Bounding Box)是一个正立方体结构,它的三条轴向量分别平行于世界坐标的坐标轴,所以仅用两个点的坐标就能完整地描述一个AABB包围盒,本文中AABB用来描述八叉树的一个空间节点的包围盒特性,其数据结构如下:
max代表了包围盒前右上顶点的世界坐标,min代表了包围盒后左下顶点的世界坐标。AABB包围盒的构建很简单,只要遍历所有的顶点,分别取出最大和最小的x值,y值,z值(共六个值),max点就由最大的三个值组成,min点由最小的三个值组成。
有向包围盒OBB(Oriented Bounding Box)本质上是一个最贴近物体的长方体,只不过该长方体可以根据物体的一阶矩任意旋转。OBB是用来描述几何节点的包围盒信息,两个OBB包围盒之间的相交检测是整个碰撞检测系统的最后一个环节,它将具体确认相应的两个几何节点是否相交,在本方法中OBB包围盒是通过三个向量和这三个方向上分别的长度来定义的数据结构如下:
如图1所示,mCenter 代表OBB的中心坐标,mAxes代表三个向量,mExtent代表了三个向量上的长度(正负方向都有)。OBB的包围盒构建相对于AABB要复杂很多。OBB的计算关键是寻找最佳方向,并确定在该方向上包围对象的包围盒的最小尺寸。为此,计算OBB的方法主要是利用顶点坐标的一阶和二阶统计特性,首先计算顶点分布的均值μ,将它作为包围盒的中心,然后计算协方差矩阵C。算式如下:
公式(1)累计所有的定点的坐标向量,计算平均向量μ,其中n是所有三角面的数量,p,q,r分别是三角面的三个顶点。
公式(2)利用平均向量计算协方差矩阵C。其中
2.2 八叉树空间节点的碰撞检测
八叉树是将3D数据集划分到不同的包围体层次的一种典型有效的数据结构。由根节点开始每个节点下最多可以有8个子节点,每个子节点还可以拥有8个子节点,就这样一层一层地划分下去,直到满足划分条件为止,最后那些不包含子节点的节点我们称为叶子节点,这类节点记录了所包含空间的所有几何节点。
在做节点碰撞检测时,第一次由根节点开始层层向下寻找包含整个运动节点的最小八叉树节点(通过判断OBB包围盒的所有八个顶点是否包含于八叉树节点AABB包围盒内实现),找到后记录该节点,如没找到则记录根节点,该节点作为下一次判断时的起始节点。然后遍历该节点下的所有子节点,如完全与运动节点不相交,则该节点下的所有叶子节点中所包含的全部几何节点都不与运动节点产生碰撞,如相交,则需要进行细化检测,检测所包含的几何节点与运动节点的相交情况。以后的判断就从记录的节点开始,如果由于移动等原因导致该节点已不能包含整个运动节点时,则向上查询最小的一个包含该节点的八叉树空间节点,否则再次向下查询,确认新的起始节点,整个程序流程如图2所示。
该过程中主要完成OBB与AABB的包围盒碰撞检测,具体方法为先将OBB的三个方向轴上的线段在世界坐标的x轴上取投影,然后将这三个投影合并成一条线段(该线段为三条投影线段长度的和),然后利用该线段与AABB的X轴线段进行比较,检查有无相交,在Y轴和Z轴上完成同样的工作,如果其中任意一次相交检测的结果为否则判定两个包围盒不相交,反之则相交。求投影线段的具体公式如下(公式(3)和公式(4)表示X轴投影,其他类似):
其中Xmax和Xmin组成了X轴上的投影线段;a1、a2、a3 分别代表三个方向向量上的长度;
2.3 具有OBB包围盒的节点的相交检测
两个OBB包围盒之间的相交检测是整个碰撞检测系统的最后一个步骤,它将与运动节点相交的叶子节点所包含的所有几何节点一一取出,然后分别与运动节点进行相交检测,最后确认碰撞检测的具体结果。两个OBB之间的相交检测和AABB与OBB之间的相交检测基本原理相同,但是稍微复杂一点。我们要将做检测的两个OBB分别在X轴,Y轴,Z轴上取投影,然后两两之间相互检测是否相交,如果三个方向是全部相交,则我们判定这两个OBB相交。
3 实验结果
根据本文中提到的方法,在VC.net 的编译环境下使用Direct3D渲染某大规模场景,屏幕分辨率设定为1280×1024。按照上述方法实现碰撞检测。在一个简单漏斗型地形中无序密集放置不同数量的几何模型,分别对采用非八叉树和八叉树模式进行碰撞检测,实验结果如表1所示。
不难发现几何节点越多的场景渲染效率提高的越为明显,这是因为对于较多数量几何节点而言,线性方式的比较所占用的时间远大于本文中采用的八叉树方式,数量越多八叉树方式的优势越为明显。当然不能否认这些效率的提高有一部分需要归功于采用八叉树方式后,视域剔除效率的提高,但是通过上表不难发现对于大规模场景而言(第三行数据),完全符合实时渲染的要求。
摘要：碰撞检测技术是大规模复杂场景渲染的关键技术之一,它可以有效地提高虚拟环境的真实感和沉浸感。碰撞检测的研究目标是如何在很高的实时交互要求下完成大量复杂物体的相交检测。提出一种将场景图中的OBB包围盒以八叉树的形式划分,并利用八叉树的层次结构实现有效碰撞检测的方法,该方法从宏观到微观的搜索方式可以快速确定需要进行相交检测的对象列表,有效地避免所有几何节点与运动节点的相交检测,提高了碰撞检测的效率,并且采用OBB包围盒来描述几何模型,有效地提高碰撞检测的精度。
关键词：八叉树,碰撞检测,有向包围盒
参考文献
[1]Pi Xuexian,Yang Xudong,Li Sikun,Song Junqiang.High-performancenavigation and rendering of very-large scale landscape and seascape.Computer Aided Design and Computer Graphics,2005.Ninth Interna-tional Conference,2005,6.
[2]Bradshaw G,O Sullivan C.Adaptive medial-axis approximation forsphere-tree construction.ACMTransactions on Graphics,2004:1-26.
[3]Raffin R,Gesquire G,Remy E,Thon S.VirSculpt:a virtual sculptingenvironment.GraphiCon′04 Proceedings,2004:184-187.
[4] Soares L,Merrier C,Raffin B,Rochi J.-L.Parallel Adaptive Octree Carving for Real-time 3D Modeling.Virtual Reality Conference, 2007. VR′07. IEEE,2007:273-274.
【基于包围盒的碰撞检测算法】相关文章：
幸福包围范文05-17
幸福被温暖包围范文06-18
半包围结构写字教案(六年)05-03
“半包围结构——上盖下出”写字教学设计04-23
农村包围城市——浅议步步高公司的品牌营销09-27
伤感的句子：就算痛到心碎也要走出包围06-01
基于遗传算法的优化设计论文04-28
基于大数据算法的论文题目05-04
基于数字混沌的图像加密算法09-11