碰撞检测中的KDOPS算法论文

碰撞检测中的KDOPS算法论文（精选7篇）

篇1：碰撞检测中的KDOPS算法论文

假定已分别为一静态环境对象E和一活动对象F建立了包围盒树状层次模型(简称为包围盒树)。在包围盒树中，每个结点上的包围盒都对应于组成该对象的基本几何元素集合的一个子集，根结点为整个对象的包围盒。碰撞检测算法的核心就是通过有效的遍历这两棵树，以确定在当前位置下，活动对象的某些部分是否与环境对象的某些部分发生碰撞。这是一个双重遍历的过程。算法首先用活动对象包围盒树的根结点遍历环境对象包围盒树，如果能到达叶结点，再用该叶结点遍历活动对象的包围盒树。如果能到达活动对象的叶结点，则进一步进行基本几何元素的相交测试[7] 。其基本思想是利用几何特性简单的包围盒代替复杂的几何对象进行相交测试，如果两个结点上的包围盒不相交，则它们所包围的对象的基本几何元素的子集必定不相交，从而不需要对子集中的元素做进一步的相交测试。

下面我们简单给出基于包围盒树的碰撞检测算法[8]。它主要由一个递归调用函数 Traverse(vE，vF)组成，vF为活动对象包围盒树中的当前结点，vE为环境对象包围盒树中的当前结点。算法的原始输入为活动对象包围盒树的根结点F和环境对象包围盒树的根结点E。

和 分别为结点vE和vF所对应的基本几何元素的子集， 和 分别为它们的包围盒。

算法1：Traverse(vE，vF)

1) If then

2) If vE是叶结点 then

3) If vF是叶结点 then

4) For 中的每一个基本元素

5) For 中的每一个基本元素

6) If then

7) Return 碰撞

8) End If

9) End For

10) End For

11) Else

12) For vF中的每一个结点vF

13) Traverse(vE，vF)

14) End For

15) End If

16) Else

17) For vE中的每一个结点ve

18) Traverse(ve，vF)

19) End for

20) End If

21) End If

算法的开销主要在于包围盒 b(SE)和 b(SF)间的相交测试，如果它们不相交，则可以结束本次调用。否则，如果 vE不是叶结点，则我们在环境对象树中继续向下一层，为 vE的每个孩子 ve递归调用Traverse(vE，vF)。如果 vE是叶结点，则我们检查 vF是否为叶结点，如果是，则我们在 vE的每个基本几何元素和 vF的每个基本几何元素间进行基本几何元素间的相交测试(如，三角形与三角形间的相交测试、三角形与四面体间的相交测试等);否则，我们在活动对象树中继续向下一层，为 vF的每个孩子vf 递归调用Traverse( vf， vE)。

在这里，我们之所以先用活动对象的根结点遍历环境对象树，主要是因为通常情况下环境对象比活动对象更大更复杂一些(例如手术刀无论是大小还是复杂度都小于人体组织)，这样做可以快速地定位活动对象在环境中的位置，较早地排除与活动对象不相交的部分;如果先用环境对象的根结点遍历活动对象树，往往会增加包围盒相交测试的次数。考虑下面这种极端情况，当活动对象完全置身于一个很大的环境对象中时，则当环境对象的根结点遍历活动对象树时，不会有任何包围盒不相交的机会。

下面对上述算法的改进，对17，18，19进行修改

17) If vF是叶结点 then

18) ForvE 的每一个子结点ve

19) Traverse( ve，vF)

20) End for

21) else

22) For 的每一个子结点 ve

23) For 的每一个子结点 vf

24) Traverse( ve，vf)

25) End for

26) End for

27) End if

这种算法的优点是在遍历过程中环境对象树和活动对象树能同时到达叶结点，降低了纵向搜索的深度，但同时也加大的横向搜索的幅度。对于环境对象与活动对象大小接近且碰撞密集的情况，其性能有明显的提高。

6 结论

基于K_DOPS包围盒层次结构的碰撞检测方法，其关键是K_DOPS的计算及BV_ TREE的构造，还有就是对环境对象包围盒树和活动对象包围盒树的遍历过程中，对传统的碰撞检测算法进行了改进，使环境对象树和活动对象树能同时到达叶结点，降低了纵向搜索的深度，明显地提高了搜索效率。

参考文献

[1] J.Canny. Collision Detection for Moving Polyhedra. IEEE Trans. Pattern Anal. Mach. Intel. 1986，8(2)： 200-209

[2] A .Smith，Y.Kitamura，H.Takemura，F.Kishino. A Simple Efficient Method for Accurate Collision Detection Among Deformable Polyhedral Objects in Arbitrary Motion. Proceedings of the IEEE Virtual Reality Annual International Symposium，pp.136-145，1995.2

[3] MyszKowski K，et al。Fast collision detection between computer solids using rasterizing graphics hardware [J]The Visual Computer，1995 1l(9);497-511

[4]Hubbard，P. M. Approximating polyhedral with spheres for time critical collision detection. ACM Transactions on Graphics，，15(3)：179210

[5]Van Den Bergen，Efficient collision detection of complex deformable models using AABB trees. Journal of Graphics Tools .，2 (4)：1-14

[6]James T.Klosowiski. Efficient Collision Detection Using Bounding Volume Hierarchies of k-Dops，IEEE Transactions on Visualization and Computer Graphics，Vol. 4，No. 1，

[7]王志强，洪嘉振，杨辉.碰撞检测问题研究综述.软件学报，，10 (5)： 545-551

[8]魏迎梅，吴泉源，石教英..碰撞检测中的固定方向凸壳包围盒的研究.软件学报，

篇2：碰撞检测中的KDOPS算法论文

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

详细分析比较了基于包围盒的碰撞检测算法中的轴向包围盒法、方向包围盒法、离散方向多面体法的检测原理和检测效率,并改进了轴向包围盒碰撞检测算法,提出利用简化包围盒边缘节点实现碰撞检测的`新设想,其可行性已被初步试验证实.不仅显著提高了碰撞检测的速度,而且可以便捷地得到更为详细的碰撞检测信息,满足了进一步进行碰撞响应处理的需要,使飞行模拟机的视景系统能够实时、准确地检测出虚拟物体间的碰撞.

作 者：王立文 刘璧瑶 韩俊伟 WANG Li-wen LIU Bi-yao HAN Jun-wei 作者单位：中国民航大学,航空地面特种设备研究基地,天津,300300刊 名：中国民航大学学报 ISTIC英文刊名：JOURNAL OF CIVIL AVIATION UNIVERSITY OF CHINA年，卷(期)：25(4)分类号：V244.1关键词：碰撞检测 包围盒 飞行模拟机 算法

篇3：碰撞检测中的KDOPS算法论文

智能算法在碰撞检测领域中的应用,即是利用智能优化算法判断两物体碰撞的最优路径和方式,其中主要应用的算法有遗传算法,粒子群算法和蚁群算法等。对于算法在碰撞领域中的应用,首先要了解该智能优化算法能解决什么问题,以及如何进行优化,本文在理论研究基础上,结合碰撞检测的实际特点,对传统的蚁群算法进行改进与设计,最后通过对手术中手术器械与人体的碰撞反映的仿真,验证了基于信息素扩散模型的蚁群算法在碰撞检测中能提高碰撞的效率和精确度,即能以较短的时间内寻找到器械与人体的最优接触方式,有效地降低了手术中的失误。

1 蚁群算法简介

人工蚁群算法[2]是受到人们对自然界中真实的蚁群集体行为研究成果的启发而提出的一种基于蚁群的模拟进化算法,属于随机搜索算法,由意大利学者M.Dorigo等人于1991年首先提出。仿生学家经过大量细致观察研究发现,蚂蚁个体之间是通过一种称之为外激素(pheromone)的物质进行信息传递,从而能相互协作,完成复杂的任务。蚁群之所以表现出复杂有序的行为,个体之间的信息交流与相互协作起着重要的作用。蚂蚁在运动过程中,能够在它所经过的路径上留下该种物质,而且蚂蚁在运动过程中能够感知这种物质的存在及其强度,并以此指导自己的运动方向,蚂蚁倾向于朝着该物质强度高的方向移动。因此,由大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象:某一路径上走过的蚂蚁越多,则后来者选择该路径的概率就越大。蚂蚁个体之间就是通过这种信息的交流达到搜索食物的目的。蚁群算法正是模拟了这样的优化机制,即通过个体之间的信息交流与相互协作最终找到最优解。

基本蚁群算法(Ant System,As)是Dorigo等人提出最早的,也是最基本的蚁群算法[3]。该算法可描述如下:设m是蚁群中蚂蚁的数量,dij(i,j=1,2,……,n)表示城市i和城市j之间的距离,Iij(t)表示t时刻在城市i与城市j路径上信息素的浓度。初始时刻,各条路径上信息素的浓度相等,Iij(0)=c(c为常数)。蚂蚁通过概率策略选择下一个要访问的城市,令pkij(t)表示在t时刻蚂蚁k从城市i转移到城市j的概率,则

其中:ηij(t)表示路径(i,j)的能见度,通常取值为1 dij;α称为信息素启发式因子,表示信息素在选择概率上的作用,α=0;β称为期望启发式因子,表示路径长度在选择概率上的作用,β=0;禁忌表tabuk(k=1,3,…,m)用来记录蚂蚁k所经过的城市;allowedk表示蚂蚁k下一步允许访问的城市集合[4]。

经过n个时刻,蚂蚁完成一次周游,各路径上信息量要根据下式作调整:

蚁群算法具有很多的优点,能并行化计算,能与其他智能算法结合,能有较强的鲁棒性等。但蚁群算法本身仍然存在有一些缺点,最主要的缺点就是该算法需要很长的搜索时间,如果规模增大,算法的时间复杂度也就增大。因此文献[5]采取了限定信息量允许值的上下限;文献[6]采取了有条件地接受信息素,而不是任何一个蚂蚁的信息素都接受,并更改路径上的信息量。这些优化算法在一定程度上减少了蚁群算法的缺点,故本文将基于信息素扩散模型的蚁群算法应用在碰撞检测中,提高碰撞的效率和精确度,下文对基于该模型的碰撞检测进行分析。

2 基于信息素扩散模型的蚁群算法在碰撞检测中的应用

两个碰撞的模型是两个特征集合,在解空间里就是两个模型的坐标点,那么判断两物体是否发生碰撞就相当于是判断两个物体间是否至少有一对特征对间的距离是否达到碰撞的条件,即三维空间至少存在一对特征对的两个点,两点间有一条最优的路径。

文献[7]中的基于信息素扩散模型的蚁群算法,在一定程度上加快了收敛速度,但效率却比较低,而且模型比较复杂,没有进行信息素的局部更新,只是进行全局更新。本文提出一种信息素扩散优化模型并很好得进行全局和局部的更新。

设蚂蚁在原点o处,信息素将会以原点为中心进行扩散,即在扩散的范围内都会接受到信息,信息素的浓度设定为Io,本文提出的扩散算法主要采用高斯模型,则圆内的任意距离圆心为d接收到的信息浓度Id为:

式(1)中w为扩散系数。

蚂蚁在爬行中都会向邻近路径扩散信息素,同时更新路径上的信息素。有两个相距dab距离的两个点a和b,令蚂蚁k在点c的信息素浓度为Io,蚂蚁一旦爬行经过,则蚂蚁会以点c为中心向周围扩散信息素,则信息素扩散都会对(a,b)产生影响,设变化量分别为ΔIkab,设c点到路径(a,b)的平均距离为d-,则结合式(3)推得:

这样,采用这种新的信息素扩散方法更新局部信息,更加快速,灵活。同时本文采用设定最优解的上限,选取一次循环中的ε个最优解,如有m个蚂蚁,则ε=0.1 m,这样避免局部收敛,解决了停滞现象。

蚁群优化流程图:

3 实验结果与分析

实验环境设定了一个简单的动态场景,两个由10000个三角面片组成已经碰撞的手臂模型,如图2所示。采用C++语言对算法进行编程,对手术中器械与人体碰撞反映进行仿真验算,验证了该算法不仅能寻找到最优的碰撞路径,同时与基本的蚁群算法相比,缩短了检测时间,有效的提高了碰撞的效率性和准确性。

由上图可知,通过蚁群算法寻找到最优的碰撞方式,使肱骨和桡骨有效的接合,而不至于错位或对接不上,从而有效的修复骨折,验证了该算法在碰撞检测中的可行性。另外,试验采取三组特征对,计算碰撞检测时间,如表1所示。

由表1可知,随着采样特征值的增多,要搜索的空间越大,搜索的时间也就越长,但采用本文算法能减小检测时间,提高碰撞的效率。

4 结束语

本文提出了一种基于优化的蚁群算法,改进了信息素的扩散模型,提高了计算效率,提升了收敛速度。最后将其应用在碰撞检测,通过仿真验证该算法在碰撞检测中的可行性,与传统蚁群算法相比较,该算法能减小检测时间,提高碰撞效率。本文仅仅仿真了简单的两物的碰撞检测,之后的研究方向是多模块的碰撞,将能应用在粉碎性骨折的修复当中。

参考文献

[1]ERICSON CHRISTER.Real-time collision detection[M].Morgan Kaufmann Publishers Inc,2005.

[2]段海滨.蚁群算法原理及其应用[M].北京:科学出版社,2005.

[3]ClolmiM.Dorig,V.maniezzo Distributed optimization by ant colonies[C].proeeedings of the 1st European Conference on AitificialLife,1991:134-142.

[4]吴斌,史忠植.一种基于蚁群算法的TSP问题分段求解算法[J].计算机学报,2001,24(12):1328-1333.

[5]Stutzl T,Hoos H H.The MAX-MIN ant system and local search for the for the traveling salesman problem[C].In Proc IEEE In ternational conference on Evolutionary Computation(ICEC’97),Indianapolis,USA,1997:309-314.

[6]陈峻,秦玲,陈宏建,等.具有感觉和知觉特征的蚁群算法[J].系统仿真学报,2003,15(10):1418-1425.

篇4：游戏引擎中碰撞检测算法研究

关键词：游戏引擎；碰撞检测；包围盒

中图分类号：TP391.41 文献标识码：A 文章编号：1674-7712 （2014） 04-0000-01

近年来虚拟现实技术和分布式交互仿真技术的应用越来越广泛，计算机模拟现实世界真实性的需求越来越高，这种真实性的关键在于如何自然合理的模拟现实世界中各物体间的相互关系即相互碰撞问题。为了保证计算机模拟环境的真实性，虚拟环境中的对象进行各种运动时必须实时检测物体间是否发生了碰撞，而且虚拟环境中的其它对象要能够做出及时地响应，避免现实生活中不可能出现的如物体间的穿透等现象的发生。在游戏引擎软件中的大规模复杂动态场景中，对象的几何复杂度直接导致了对象间碰撞检测计算量大、较为耗时，使得碰撞检测问题更加复杂，通过对碰撞检测算法的研究及优化，可以提高碰撞检测算法的性能、提高碰撞检测的效率。

一、 游戏引擎

游戏开发的核心技术是游戏引擎，游戏引擎是指通过整理和封装通用技术细节来形成面向游戏应用的接口函数，游戏开发人员只需调用游戏引擎框架中相关的函数而不用关心底层技术是如何实现的。完整的游戏引擎是由许多游戏功能组件共同来组成的，它具有分明的层次结构，一般包括物理数学支持层、图形渲染内核、系统层、游戏介质层以及开发工具层。其中最关键的部分是图形渲染内核，包括配置子系统、图形子系统、声音子系统、输入子系统和时效子系统，它们互相配合共同完成游戏中的各种效果。现在市面上有很多商业引擎，基本上都采用了底层算法思想以及最新的图形图像学技术，表现出非常好的开发性和延展性，又各有各的特点，对于特定网络游戏的开发具有重要的意义。

二、碰撞检测

碰撞检测是构建游戏引擎最主要的环节之一，也是衡量一款游戏是否达到预期效果的标准。碰撞检测问题在计算机图形学、智能机器人等领域都有着悠久的研究历史，它是基于“两个不可穿透的物体不能同时共享相同的空间区域”这个现实生活中广泛存在的事实设定的。

（一）碰撞检测概念

碰撞检测就是对物体在运动过程中可能出现的碰撞进行检查，避免碰撞的发生，或进行碰撞的响应处理。碰撞检测的基本任务就是确定两个物体之间是否发生了接触或穿透，即两个多面体的求交测试问题。碰撞检测是构造虚拟环境的核心部分，游戏中如果不进行碰撞检测，人物就可以在场景中任意游走，就会出现穿墙过树等与现实世界不符的行为规则，所以说合理精确的碰撞检测在游戏中是必不可少的。最简单的碰撞检测就是对两个输入模型中所有几何元素进行两两相交测试，随着输入模型的复杂度越来越高，相交测试数目成几何级数增长，大大影响游戏运行的效率，因此，如何提高算法的速度以保证游戏中的实时交互性是碰撞检测的核心。

（二）碰撞检测分类

碰撞检测方法可以分为两类：空间分解法和层次包围盒法。空间分解法是将整个虚拟空间划分成体积相等的若干小单元格，并且只对同一单元格或相邻单元格的几何元素进行相交测试。层次包围盒法是用体积较大而几何特性相对简单的包围盒来近似描述复杂的几何元素，先对包围盒进行相交测试，在此基础上只需对包围盒重叠部分进行进一步的相交测试。两种方法都使用了层次结构模型，都是为了尽可能地减少相交测试的几何元素数目。空间分解法适用于稀疏环境中几何对象分布比较均匀的碰撞检测，而层次包围盒法适用于复杂环境中几何对象的碰撞检测，它的应用更为广泛，本文主要研究的就是基于层次包围盒的碰撞检测算法。

三、基于层次包围盒的碰撞检测算法

（一）层次包围盒法原理

层次包围盒法的基本思想是用体积较大而几何特性相对简单的包围盒来近似地描述复杂的几何对象，通过构造树形层次结构可以将包围盒越来越逼近对象的几何模型，最终可以获得与实际对象有着几乎完全一致的几何特性的包围盒，由于包围盒的相交测试比直接对几何对象进行相交测试要简单的多，因此，在对几何对象进行碰撞检测时，首先对包围盒进行相交测试，这样能够快速排除许多不相交的几何对象，如果相交再对包围盒重叠部分进行进一步的相交测试，提高了算法的执行效率。

（二）常见的包围盒

通过使用简单几何模型包围复杂对象进行碰撞检测大大提高了碰撞检测的效率，但并不是所有几何模型都可以充当包围体的，它必须是具有构造简单、占用内存空间小、有良好的紧密性、相交测试计算量小且能够快速更新等优势。常见的包围盒有以下几种：（1）轴向包围盒：包含该对象且各边与坐标轴平行的最小正六面体。它的简单性好，紧密性差，当对象旋转后需要重新进行计算。（2）方向包围盒：包含该对象且方向任意的最小正六面体。紧密性较好，实时性较高，当对象旋转后只需对包围盒进行同样的旋转。（3）离散方向多面体包围盒：包含该对象且有k个固定方向的凸多面体结构。紧密性较好，但需要合理选取平行平面对的个数和方向。（4）球包围盒：包含该对象的最小球体。简单性好，紧密性差，当对象旋转后包围球不需要作任何改变，当对象变形后需要重新计算。

层次包围盒法是目前应用最广泛的碰撞检测算法，各种包围盒算法有各自的优劣，针对不同的应用场合选择不同的方法，以达到简单、紧密、实时的要求。

（三）层次包围盒树

虽然采用包围盒代替基本几何对象进行相交测试的方法提高了碰撞检测性能，但还需进行两两包围盒的相交测试，如果将包围盒整合到树形结构中，应用层次包围盒技术，两两包围盒之间相交测试的时间复杂度可以由平方级降为对数级。在树形结构中，根节点代表对象本身，所有叶子结点组成对象的基本几何元素。可以采用自顶向下或者自底向上的构造方法来构造层次包围盒树。

四、结束语

随着虚拟环境的复杂性越来越高，对于碰撞检测算法的实时性和精确性还要不断进行深入研究，通过不断改进优化算法并应用于游戏引擎中，可以有效地解决大型复杂虚拟环境下的碰撞检测问题。

参考文献：

[1]黄杨飞.大场景3D游戏引擎技术研究与实现[D].浙江师范大学，2011

篇5：基于包围盒碰撞检测算法研究

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.

篇6：自定义的AABB碰撞检测算法

碰撞检测是视景仿真系统研究[1,2,3]中的关键技术之一。碰撞检测与碰撞响应算法的好坏，直接影响视景仿真的效果。Vega是一种用于实时仿真及虚拟现实应用的高性能软件环境和工具[4,5]。它主要包括两个部分：一个是被称为LynX的图形用户界面的工具箱;另一个则是基于C语言的Vega函数调用库。作为软件环境和工具，Vega提供了碰撞检测机制，可满足实时碰撞检测的需求，但其提供的已封装好的相交矢量类检测方法，却没有完全避免“穿墙而过”、“传土而入”、“上房”等现象的发生[6,7,8]，或者存在碰撞检测不精确的现象，如“擦墙而过”等。

为了提高视景仿真系统的逼真度，提高碰撞检测的精度或效率，许多学者在碰撞检测领域中做出了相当多的工作，提出了一系列算法[9,10,11,12,13,14,15]。其中，比较典型的是基于包围盒的碰撞检测算法[8]，以及对其的改进算法[10,13]。通过对相关的文献分析得出：(1)大部分包围盒算法比较复杂，应用实践起来比较困难，实用性差;(2)很多算法与Vega自身的碰撞检测机制不统一，兼容性差，不利于快速研发基于Vega的视景仿真漫游系统。

综上所述，为解决Vega中现有碰撞检测算法存在不逼真现象的失真问题，提出一种基于AABB的自定义的碰撞检测算法，利用Vega中的Segment方法，构造运动体的AABB盒，算法简单，实用性高。通过对AABB盒的各条边进行碰撞结果检测，使得碰撞做出更精确的响应，与Vega自身的碰撞检测机制相一致，达到了快速研发基于Vega的视景仿真系统的目的。

2 基于运动体的AABB构造算法

2.1 对象的AABB盒

AABB即沿坐标轴包围盒，是指包含一个给定对象的且各边平行于坐标轴的最小六面体。一般来说，给定一个左下顶点和一个右上顶点，即可构造一个AABB包围盒。那么AABB的技术只需计算给定对象的各个元素顶点的坐标的最小值和最大值即可。如果最小值分别为minx、miny、minz，最大值分别为maxx、maxy、maxz，则构造该AABB的左下顶点坐标为(minx, miny, minz)，右上顶点坐标为(maxx, maxy, maxz)。

两个对象的发生碰撞当且仅当它们在3个坐标轴上的投影区间均重叠。对于拥有AABB的对象，它与其他对象或场景的碰撞检测可转换为该对象的12条边与另外一个对象或场景的碰撞检测，只要任一条边发生了碰撞，则该对象就与另外一个对象或场景发生了碰撞。所以，复杂运动体在场景中漫游时的碰撞检测问题可以转化为其AABB包围盒的边与其他对象或场景的碰撞检测问题，正好弥补目前Vega产品只支持Segment图元的不足。

2.2 Vega的碰撞检测

Vega软件提供了八种相交矢量方法，完成一些简单的碰撞检测和相交测试，也就是Vega基本模块中的Isector好Volume。在Isector模块中，除了Volume体方法外，其余的七种方法都属于线段类型的方法，由不同方法设计的线段配合相交矢量来检测碰撞情况。碰撞检测的结果保存在一个内部缓冲区中，以一个数组的形式存储。在进行碰撞响应处理时，可通过Vega的函数vgGetIsectResult () 函数来获得这些数据。虽然，Volume方法在Lynx里面提供了Box、Sphere等方法参数，但是目前的Vega产品没有很好地支持这些高级的方法。当然，基于Volume方法，可对Vega中的碰撞检测算法改进，通过建立Segment类型的体(Volume)，然后把这个体放置在适当的位置上，实现该体的交叉方法，就可以进行更精确的碰撞检测了。

2.3 自定义的AABB碰撞检测与响应

在基于Vega的视景仿真系统中，如果要实现对运动体的碰撞检测，必须设定碰撞检测目标和交叉体。根据前面分析，为了使得碰撞检测更加精确，可对Vega中的Volume方法进行改进。因此，提出一种自定义的运动体AABB构造方法。步骤如下：

(1)确定运动体的体Box的值。即确定该体的左下顶点和右上顶点坐标。

(2)在Vega中设置好运动体的坐标位置。当然，如果这个体需要和角色关联，可把这个位置绑定在Player上。

(3)根据(1)和(2)确定运动体的AABB的8个顶点坐标。

(4)根据八个顶点关系，确定AABB的12条边的每条边的其中一个顶点的位置、沿坐标轴的方向、长度。这一步是为了自定义一个Segment类型的碰撞检测相交矢量。

(5)根据每条边的情况，自定义一个Volume体，类型Segment，绑定一个新的Isector。每条边就是一个线段，包括一个顶点、长度和方向。这是Vega API中自定义相交矢量类的要求的参数。

(6)为每条边对应的体的Isector设置Render On，则可以看到运动体外构造的AABB包围盒。

(7)如果12条边都已经构造完成，则算法结束。

注意：每条边对应的Isector目标掩码和目标对象对应的掩码一致。

碰撞响应是检测到碰撞后的处理过程。碰撞响应可在程序的主循环中进行，对于AABB包围盒的每条边，计算相交矢量，交叉计算，获取相交结果，根据运动体碰撞的物理意义进行碰撞结果处理，把处理后的结果反应到运动体的位置变化即可。碰撞响应的算法步骤如下：

(1)在运动体的AABB包围盒上，任取一条边对应的Isector。

(2)放置相交矢量。

(3)对该Segment类型的体与目标交叉计算，并保存结果。

(4)如果所有的边都已经计算完成，转(5);否则转(1)。

(5)计算12条边的交叉结果，判定是否相交，如果相交，则根据不同的边碰撞情况，分类处理，得到一个新的运动体的位置;否则运动体的位置不变。

(6)重置运动体的位置，算法结束。

3 实验

3.1 实验环境

Vega是一种用于实时仿真应用的高性能软件环境和工具。它包括图形用户界面Lynx、Vega模块以及C语言API库。实验是在Vega3.7版本[4]上进行的，另外还包括三维建模工具Creator、软件集成开发环境VC++等。整个实验环境配置参数如表1所示。

3.2 实验方法

整个实验以实现一个场景漫游系统为目的，实验方法主要步骤如下：

(1)使用Vega的图形界面Lynx设置好参数，导入两个对象town和tank，并配置相关的观察者、运动模型、环境等。

(2)利用VC++6.0开发环境编写程序代码，实现自定义的AABB碰撞检测算法。在构造AABB的时候，可通过Creator打开tank对象的flt文件，获得其Box边界，设置准备构造的AABB的各条边的值。在程序中实现每条边的相交Isector类。主要程序代码如下：

(3) 碰撞结果计算, 实现碰撞响应算法。对每条边的碰撞结果进行收集, 然后统一处理。计算每条边的碰撞结果的主要程序代码如下:

3.3 实验结果

整个工程编译之后，运行结果如图1所示，坦克上的红色的六面体就是自定义的AABB盒。该系统原型采用鼠标控制坦盒的发生碰撞的边就会变成绿色，碰撞响应的处理之后，坦克回到碰撞前的状态，如图2所示。

通过驾驶坦克在小镇场景中漫游，仔细观察测试发现，没有“穿墙而过”、“传土而入”等失真现象，而且，坦克只要与墙体擦边，立刻被检测到发生碰撞，提高了碰撞检测的精确性和逼真性。

4 结语

篇7：碰撞检测中的KDOPS算法论文

关键词：碰撞检测,虚拟维修,算法,包围盒,空间分割

0引言

虚拟维修是虚拟现实技术在机械领域的应用。随着计算机技术的发展,用户对仿真的真实性(即:实时性、精确度)提出了更高要求。碰撞检测技术作为构建系统的关键技术之一,精确的碰撞检测可以有效地提高仿真效果。目前,碰撞检测的算法研究取得了一批有意义的成果,但针对虚拟维修系统的算法研究不多,通常借鉴或修改其它的算法加以应用,达不到系统设计之初的效果,严重制约了虚拟维修技术的发展。基于此,对虚拟维修的碰撞检测算法进行系统的整理显得尤为必要。本文通过阅读大量相关文献,在准确把握虚拟维修的特点和理解各种算法的基础上,对各种算法做了全面分析,择出了几种适合于虚拟维修的算法,为今后虚拟维修系统算法的研究提供了方向。

1算法分类

由于应用领域、研究方向、研究目的的不同,研究人员有针对性的设计了很多种碰撞检测算法,能够有效地实现各类碰撞问题的检测,为其他新算法的研究奠定了理论基础和参考依据。目前,根据不同的分类标准其结果也不同,按照场景中物体的运动状态划分,可分为静态检测算法和动态检测算法,对于动态检测算法如从时间轴考虑大体可分为连续与离散算法。

虚拟维修系统中涉及大量动画仿真,而在众多动态算法中能够满足实时性要求的是算法大部分属于离散型检测算法。离散型算法又大致可分为基于图形和基于图像的算法两类,取得的研究成果也较多,如图1所示。两者的区别在于前者利用物体三维几何特征进行分析计算;后者利用二维投影及深度信息进行求交计算。基于图形的层次包围盒和空间分割的算法研究较为成熟,应用比较广,也是本文的主要论述内容。基于图像的算法的优势在于可通过GPU来平衡CPU的负担[1,10],虽然国内外学者对基于图像的检测算法也做得大量的工作,但其巨大的潜力仍未得到开发。

就虚拟维修而言,由于系统设计的使用目的不同,大体可以划分为两类。一类是面向产品的设计、生产,从产品的全生命周期考虑,在虚拟拆卸、装配过程中发现产品设计上的维修缺陷,以改进设计方案,为产品设计提供参考;另一类是面向装备维修保障训练,这类系统主要用以培训技术人员。由于使用目的的不同,二者对碰撞检测算法的要求差异较大,前者要求碰撞检测的结果精度高,后者则更强调系统的实时性。

2算法的分析

从本质上说,离散碰撞检测算法在每一时间离散点上可以通过类似于静态干涉检测算法的方法来实现,通过时间步长dt来确定计算的频率,运算效率得到显著提高。但也存在着一些问题,在物体运动速度过快的场景中,在某时间段T到T+dt中两物体很可能发生碰撞,因此而发生漏检和穿刺现象,如图2所示。通过采用自适应步长技术,在一定程度上减少离散碰撞检测算法的不足。连续碰撞检测算法不仅涉及到三维空间问题,还要考虑第四维时间t。该类算法能较好地解决离散碰撞检测算法存在的刺穿和漏检等问题,但计算速度较慢,无法满足大规模场景中多物体的碰撞检测。

2.1层次包围盒法

目前,包围盒技术理论成熟,应用较广,通过采用体积略大,但几何特性相对简单几何体包围几何对象。在碰撞交测过程用包围盒替代复杂几何对象,交测的实时性大幅提高。采用层次结构树来逼近几何对象可以提高碰撞检测的精度。经典的包围盒有轴向包围盒(axis aligned bounding box, AABB)、包围球(sphere)、方向包围盒(oriented bounding box,OBB)、 离散方向多面体(discrete orientation polytope,K-Dops)等[2,3,4,5,6,7,8],此外还有很多包围盒及混合包围盒。针对虚拟场景,每种包围盒法有着自己的优势与不足。下面通过的代价函数来分析不同包围盒的优劣[9]:

Ttotal=Nb×Cb+Np×Cp+Nu×Cu+Nv×Cv+Cd (1)

其中:Ttotal为一对几何体相交测试的总代价;Nb为参与相交测试的包围盒对数;Cb为一对包围盒相交测试的代价;Np为参与相交测试的几何元素对数;Cp为一对几何元素相交测试的代价;Nu为包围对象移动后需要更新节点的包围盒个数;Cu为更新一个移动后的包围盒所需代价;Nv为包围盒旋转后需要更新的包围盒个数;Cv为更新一个包围盒旋转后需要的代价;Cd为对象发生变形后更新节点的包围盒所需代价。

从式(1)可以得到某种包围盒相交测试的代价,包围盒移动、旋转后包围和更新需要的代价,以及物体发生变形后更新节点需要的代价。然而要评判包围盒性能的优劣、或是作为选择包围盒的依据远远不够。一般情况下,还要从包围盒的构造难度,占用存储空间,包围盒的紧密程度,算法的实时性与精确性需求。假定“1”为最优值,其优劣比较结果,如表1所示。

由表1可以看出每一种包围盒都存在着优势和不足,在算法的选择上,一是要分析场景中物体的几何特征、运动状态、数量大小,有无变形体;二是要考虑算法实时性与精确性之间的平衡等诸多因素。

2.2空间分割法

空间分割法[11,12,13]是将整个虚拟空间划分成等体积的规则单元格,以此将场景中的物体分割成更小的群组,并只对占据了同一单元格或相邻单元格的几何对象进行相交测试。一般来说,空间分割法在每次碰撞检测时都需要确定每个模型占有的空间单元。如果场景中不可动的模型很多,可以预先划分好空间单元格并确定每个模型占有的空间单元。当有模型运动时,只需要重新计算运动模型所占有的空间就可以了。

空间分割法适合于物体分布较为均匀的场景,在采用均匀网格分割时空间分割与对象无关,使得它特别适合变形体对象。变形体对象会在运动中发生形变,包围盒法需要重新构建或者更新围体树,重新构建整个数据结构的时间耗费巨大;而均匀空间分割的关键问题是确定适当的单元格尺寸。适当选择单元格尺寸,可使算法的计算能保持一定的准确度又不致代价太大。

与包围盒法相比,空间分割法在计算效率上具有一定优势,但当场景中的物体密集,分布不均时,单元格需要进一步分割,单元格之间的交测和存储都需要较大空间,计算效率急剧下降。由于存储量的敏感,使它不如包围盒应用广泛。

3层次结构树

无论包围盒法还是空间分割法都需要采用层次树的方法来提高交测速度和精度。包围合法比较典型的有二叉树、八叉树等。空间分割法通常采用均匀网格划分、四叉树、八叉树、BSP树、kd树[14,15,16],如图3所示。一般来说,BSP树、八叉树或kd一树都是对象相关的。层次树通常要结合算法、场景的复杂程度、几何体在场景中的分布、几何体的运动状态等因素来选择,合理的层次结构树能使算法达到最高效率。

在构建层次结构树时,希望算法能够快速的遍历整棵树,同时又希望层次树能尽可能的分解,以提高算法精度。然而目前的硬件水平和算法仍不能解决实时性和精确性之间的矛盾,不得不在二者之间进行平衡。因此在构造层次树时要考虑构造什么样的树,怎样构造树,以及设定合理的阈值。

度数δ决定了一棵树的高度,δ指树的是节点所拥有的最大孩子数。对于一个含n个叶节点的δ-叉树,树的高度h=logδn+1,其内部节点数为(n-1)/(δ-1)。可见树的度δ越大高度越低、内部节点数越少。在树的构造过程中人们总希望树的高度尽可能的小,这样可以很快的完成从根结点到叶节点的遍历。矛盾的是高度小的树在每个节点花费的时间会加长,因此树的度和高度之间需要需求一个平衡点。

树的常见构造方法有三种,分别是自上而下、自下而上、插入法,如图4所示。自上而下的方法应用较广,算法上易于实现。但一般情况得不到最优树。自下而上的方法是先输入叶节点,直至树的根结点,与自上而下的方法恰好相反。该方法易于生成最优树,但算法不易实现。插入法是不断的出入节点进行构造,但要选择插入位置以降低生成树的代价。这里以二分法为例来对比三种方法的不同:

层次结构树在分解几何对象时,如果阈值设置的过大则影响交测精度,反之又会影响实时性,因此合适的阈值直接影响算法的效果。八叉树既可以用于空间非均匀网格剖分算法,也可以用于包围盒算法,尤其适应于AABB型包围盒。下面以八叉树在空间分割法中的应用为例进行说明,该层次树是将场景中的空间立方体按三个方向中剖面分割成八个子立方体网格,组织成一棵八叉树。若某一子立方体网格中所含几何元素面片数大于给定的阈值,则为该子立方体作进一步的剖分。否则不分解。以此循环递归,再通过预先设定阈值,控制分解的终止,如图5所示。

4发展趋势

虚拟维修训练系统对碰撞检测的需求有特殊的地方,要求碰撞真实、直观反应现实,它不仅需要精确检测到碰撞的位置,还要求碰撞后合理的响应。

1) 碰撞响应的真实度,仿真系统的逼真程度取决于虚拟场景的构造和期间物体运动的合理性。不同材料、不同速度的物体发生碰撞能否作出合乎逻辑的响应,如篮球与篮球、篮球与铁球的相互撞击不同。

2) 实时性与精确性,长期以来二者之间的矛盾成为每一种算法不得不考虑的因素,相信一段长时间内,如何提高实时性与精确性仍然是碰撞检测算法研究的关键点之一。

3) 变形体的研究,在碰撞检测过程变形体几何外形的改变,导致包围体的重构,碰撞检测消耗过大,影响算法实时性。在虚拟维修训练系统的场景中存在大量变形体,如弹簧、橡胶管路等。