碰撞检测经典解决方案

        碰撞检测在3D游戏中至关重要，好的碰撞检测要求人物在场景中可以平滑移动，遇到一定高度内的台阶可以自动上去，而过高的台阶则把人挡住，遇到斜率较小的斜坡可以上去，斜率过大则把人挡住，在各种前进方向被挡住的情况下都要尽可能地让人物沿合理的方向滑动而不是被迫停下。在满足这些要求的同时还要做到足够精确和稳定，防止人物在特殊情况下穿墙而掉出场景。

       碰撞检测做得好了是应该的，不易被人注意到，因为这符合我们日常生活中的常识。做得差了却很容易让人发现，人物经常被卡住不能前进或者人物穿越了障碍。所以大部分人都觉得写碰撞检测代码是件吃力不讨好的事情，算法复杂、容易出bug、不容易出彩。下面还是回到正题，看看我们该如何解决这个难题。

       早期3D游戏的碰撞检测多数基于格子或者BSP树，基于格子的系统实现简单但精度不够，不属于严格意义的3D碰撞检测。基于BSP树的碰撞检测一度十分流行，算法基本已经成熟定型，但它的固有缺点却使它不太适合现在的游戏。BSP树需要很长的预处理时间不适合加载时计算，BSP划分经常会产生原多边形数三到四倍的多边形，考虑到不用保存法线、颜色、uv等信息也要增加将近一倍的资源容量，在一个大的游戏中将模型资源的容量从200M增加到400M相信是大部分人都不愿接受的。目前对于任意复杂三角形集合（mesh）的碰撞检测多数基于BVTree（bounding volume tree）,具体可以是aabb tree，obb tree或者K-dop tree，这也是当今各种物理引擎和碰撞检测引擎流行的做法。

       上面是碰撞检测按数据结构不同的分类，按检测方式又可以分为离散点的碰撞检测和连续碰撞检测（CCD continuous collisiondetection）。离散点的碰撞检测是指定某一时刻T的两个静态碰撞体，看它们之间是否交迭，如果没有交迭则返回它们最近点的距离，如果交迭则返回交迭深度，交迭方向等。连续碰撞检测则是分别指定在T1、T2两个时刻两个碰撞体的位置，看它们在由T1运动到T2时刻的过程中是否发生碰撞，如果碰撞则返回第一碰撞点的位置和法线。连续碰撞检测是最为自然的碰撞检测，可以大大方便碰撞响应逻辑的编写，可以很容易避免物体发生交迭或者穿越。离散点的碰撞检测则没有那么友好，当检测到碰撞时两个物体已经发生了交迭，如果其中有三角形网格对象那么已经有许多三角形发生了交迭，如何将两个交迭的对象分开并按合理的方式运动是一个挑战。虽然连续碰撞检测是最自然的方式，但它的实现非常复杂，运算开销也很大，所以目前大部分成熟的物理引擎和碰撞检测引擎还是采用了基于离散点的碰撞检测，为了避免物体交迭过深或者彼此穿越，它们都要采用比较小的模拟步长。

       由于碰撞检测引擎的复杂性和对效率的高要求，我们应该尽量使用目前成熟的完整引擎，而不是自己去开发。经过评估，我决定采用Opcode碰撞检测引擎来做游戏中人物和场景的碰撞检测。Opcode的主要功能是用aabb tree管理复杂三角形集合来和射线、球体，立方体，另一个三角形集合等进行离散点上的碰撞检测，如果检测到交迭则返回所有发生交迭的三角形。Opcode的特点是高度的内存使用优化和极好的效率，ODE物理引擎底层就采用它来做复杂三角形mesh的碰撞检测，Opcode的作者也是NovodeX（PhysX前身）物理引擎的核心开发人员，据说NovodeX采用了Opcode的一个更优化版本。由此可见Opcode的成熟与效率。

       确定了要使用的引擎，下面要讨论的算法就和具体引擎无关了，适合于任何离散点的碰撞检测引擎。我们用AABB包围盒来代表场景中的人物，看看如何实现文章开头所提出的效果。

        首先解释一下检测地面的方式，沿人物包围盒的四条竖边向下投四条射线，射线的终点略低于人物的脚底（也就是说射线的长度是有限的），如果与场景发生碰撞并且碰撞平面的斜率小于某一值则取得碰撞点的高度，否则视为这条射线没有检测到地面。将所有射线检测到的地面高度最大值作为最后的地面高度，如果四条射线都没有检测到地面则认为人物悬空。

 vD = 当前帧人物位移

p0 = 人物包围盒中心当前位置

bOnGroundP1; // 人物是否站在地面

bOnGroundP3; // 人物是否站在地面

bOnGround; // 人物是否站在地面

p1 = p0 + vD

在p1位置检测地面

if( 检测到地面 )

{

     将包围盒下放到地面得到位置p2

    bOnGroundP1 = true;

}

else

{

     p2 = p1;

    bOnGroundP1 = false;

}

测试p2点的包围盒是否与场景交迭

if( 交迭 )

{

     取得所有交迭三角形的法线，将它们相加后取平均值，得到法线normal

     将法线与向上的向量叉乘得到切线方向tangent

     // 计算人物沿切线滑动后的位置，注意这里用p0做计算。

     // 如果要使滑动更平滑可以把p0向法线方向推出一些

     // p3 =p0 + normal * 0.1f + vD.Dot(tangent);

     p3 = p0 +vD.Dot(tangent); 

     在p3位置检测地面

     if( 检测到地面 )

     {

        将包围盒下放到地面得到位置p4

         bOnGroundP3 = true;

     }

     Else

     {

        p4 = p3;

         bOnGroundP3 = false;

     }

     测试p4点的包围盒是否与场景交迭

     if( 交迭 )

     {

        测试p1点的包围盒是否与场景交迭

        if( 交迭 )

        {

             // 无法得到合理的移动位置，人物位置保持不变

             // 等待下一帧玩家调整前进方向再做测试

             将p0作为人物的新位置

             bOnGround = true;

             return;

        }

        else

        {

             将p1作为人物的新位置

             bOnGround = bOnGroundP1;

             return;

        }

     }

     Else

     {

        将p4作为人物的新位置

        bOnGround = bOnGroundP3;

         return;

     }

}

else

{

     将p2作为人物的新位置

    bOnGround = bOnGroundP1;

     return;

}

上面的算法基本达到了文章开头所提到的效果，在某些复杂情况下人物移动还有些不流畅，但没有发现人物有穿越障碍物的现象。在大部分情况下人物的新坐标都会由p2点返回，最坏情况是人物被卡住返回p0点。在P4 3.0G的机器上可以支持120个人物在最坏情况下保持30帧的游戏帧数。

在使用广义碰撞阶段迅速排除了大量物体以后，将会使用精确到多边形级别的精确碰撞，比如两个凸包之间的碰撞，凸包和面片之间的碰撞，以及2次曲面和多边形面片的碰撞，在游戏中常用的两次曲面有，椭圆体，圆柱体，胶囊，球体等等。对于两个凸包之间的碰撞算法目前比较流行的是SAT，分离轴测试算法可以静态和动态的计算出两个凸包之间的碰撞时间法向量等等。但是对于面数较多的凸包以及2次曲面却不大适合，此时一般使用GJK算法但是GJK算法本身强壮性的实现问题一直是一个较难的问题。在我的一项使用BSP进行碰撞检测的实验中，人物以胶囊来模拟，房屋内部通过非SOLID 的LEAFY BSP来构造，在使用BSP剔除了大量面片以后，遇到这样一个问题：如何在最后筛选下的三角形面片进行碰撞测试，以确定碰撞发生的时间，法向量等。

本文提出一种简单，易懂，准确的方法用来确定一个以速度v前进的胶囊和一个凸多边形第一次发生碰撞的时间。

首先一个胶囊是所有到某根线段的距离等于某个值r的点的集合：

如图：虚线表示该线段这里以ab表示，r代表所有点到该线段的长度：

首先观察静态情况下的碰撞情况。当一个多边形面片和胶囊碰撞的时候，实际上是该多边形面片中存在一些点，这些点到线段ab的距离小于了r，这是因为在胶囊外部的点到线段ab的距离均大于r（胶囊是所有到某根线段的距离等于某个输r的点的集合）。所以在两个物体都静止的情况下相交测试实际上是测试线段ab到多边形的最短距离，如果该距离<R那么存在碰撞，否则不存在碰撞：

如图这里以一个三角形为例子，左图中该三角形的所有点到线段ab的距离均大于r所以和该胶囊不相交，而右图中三角形的黑色区域中的点到线段ab的距离小于r所以该三角形和胶囊相交。

所以实际上只要计算一条线段到某个多边形的距离，然后和r作比较就可以知道是否发生碰撞。而一条线段和一个多边形的距离计算，需要分以下几个步骤（以三角形为例）

A将线段ab的2个端点投影到三角形所在平面，并检查投影点是否落在三角形内部，如果是的话将该投影距离作为一个候选值

B分别计算线段ab和三角形的三条边的最短距离点对，并检查该点对中的点是否落在线段中（ab线段和三角形的边线段中）如果是的话将该点对的距离作为一个候选值。

C分别计算线段ab的两个端点到三角形每条边的投影（实际上是计算最近点对），并检查该投影是否落在边的线段中如果是的话作为一个候选值保存。

D分别计算三角形的3个顶点到线段ab上的投影，并检查该投影是否落在线段ab中。如果是的话作为一个候选值保存。

E 分别计算三角形的3个顶点到线段ab的两个顶点，把距离作为候选值保存。

这样一来碰撞检测就归结为，点和线段，线段和线段，以及点和面的最短点对的计算了，

最后将上述的候选值进行比较，结果最小的那个就是三角形中到线段ab的距离。

上述方法非常容易推广到动态的情况也就是：当胶囊以速度v运动时第一次和三角形发生碰撞的时间。问题归结为在哪个时间T线段ab到三角形的距离等于半径r，而这又归结为上述A,B,C,D,E 5个子问题。如果能够分别求出这5个子问题的时间，t1,t2,t3,t4,t5那么取这5个时间中的最小值就是胶囊和三角形发生碰撞的确切时间了。

下面以两条直线，一条静止，另外一条以速度v移动作为例子，来说明求得时间的过程。问题等同于:

给定一条静止，另外一条以速度v移动的直线，求出在哪个时间T这两条直线的距离等于半径r。

对于两条直线，假设直线的方程分别为：

L1:P1+r1*t;

L2:P2+r2*t;

现在架设直线L2以速度v={vx,vy,vz}移动；

根据两条直线的距离公式

d=|P1P2 .（r1Xr2）| /|（r1Xr2）|

其中P1P2是向量代表 P2-P1，X代表叉积，.代表点积

由于r1,r2是常量不会随着直线的移动而改变，这里令（r1Xr2）=r={x*,y*,z*}

P1={x1,y1,z1}不变，P2={x2+vx*t, y2+vy*t, z2+vz*t}其中t代表时间是个变量

带入公式d=|P1P2 .（r1Xr2）| /|（r1Xr2）|可得

d(t)=x*(x2-x1)+y*(y2-y1)+z*(z2-z1)+(x*vx+y*vy+z*vz)t

令(x*vx+y*vy+z*vz)=a; x*(x2-x1)+y*(y2-y1)+z*(z2-z1)=b;

那么d(t) = at+b —————————–(1)

公式1就是两条直线之间的距离随着时间t变化的函数，这是一个带符号的距离，两边平方可得 d^2(t)= (at+b)^2

这是一个两次方程，假设胶囊半径为r 那么只要求解方程(at+b)^2=r^2这个方程就可以求出子问题B的时间了，同时注意计算出时间t之后还需要计算出该时间两条直线的线最近点对是否都处在两条对应的线段上，如果是的话才是一个合理的时间否则就抛弃该时间。

通过同样的推导可以分别求出其他子问题的时间取这些时间，取这些时间的最小值就是碰撞第一次发生的时间，当然在求解2次方程过程中要考虑到delta<或者=0的情况这些情况都有自己的物理意义，以上面两条线段距离为例d^2(t)= (at+b)^2中如果a=0

那么方程恒等于b^2，考察a=0的物理意义，a=0也就是(x*vx+y*vy+z*vz)=0；其中x*,y*,z*是这两条直线所组成的面的法向量

这表面移动速度平行于这两条直线所组成的面。显然距离是恒定不变的。

结论：

以上方法很容易推广到凸多边形，以及求出碰撞的法向量（根据最短时间是由上述A,BCDE中那种情况所引起的）。

在一般网游的室内环境检测中，使用胶囊模拟人物已经足够了，结合BSP的漂亮剪枝能力，可以做出比较满意和快速的碰撞检测，人物和其他物件的碰撞可以采用凸包比较或者GJK方法等。

周末一天没事写个游戏,好简单的,里面的亮点是碰撞检测代码,是我在国外论坛上看到的一个算法,算是很强的了.下面我贴出来,然后讲一下大致思路,关于游戏的代码就不贴了,一大串的看了也心烦 ^^”
点击浏览该文件
这个函数就是碰撞检测的关键,我给它启名叫 “描边“
首先里面两个参数,第一个pmc就是要描边的mc,第二个num是要描的级数(等下会解释到),我们先可以先看下里面的逐句解释

他这么做到底什么意思呢?
其实point里面就是记录了,一个图形的边缘的坐标.他是怎么做到的?
我们抛开所有从最里面的while循环讲起吧.
while的条件是,当(x,y)点没有接触到pmc的时候,就不断循环,循环的内容是 x-=xs,y-=ys;
如果我们前面什么也没看,应该可以想象,一开始(x,y)点一定在pmc的右边,然后不断的减一个数值xs,ys,直到减到x,y碰到pmc为止,这样,x,y就是pmc上的一点坐标了.
但是我们目前还不知道x和y是怎么定义的,还有就是xs和ys怎么来的
往上看

var xs = Math.cos((n*Math.PI)/180);
var ys = Math.sin((n*Math.PI)/180);
var x = pmc._x+(mx*xs);
var y = pmc._y+(mx*ys);

数学好的,一看就看出来了,这是圆的极坐标公式,就是以pmc的(x,y)为定点,mx为半径的圆的轨迹.
看到这里,应该可以猜到,一定是让一些点以圆的方式出现在mc的周围,然后每个点往mc靠拢,知道每个点都靠到mc上面.
这样我们只要解决这个圆的大小问题了,也就是mx的大小,实际上,你把mx定义成一个很大的数也没问题,但是这样做,会浪费很多,对于写程序的来说,不必要的浪费是不行的^^
那么看上面的

var mx = Math.max(pmc._width, pmc._height)/2;

这里就定下了 mx的大小,也就是从mc的长和宽中找一个较大的出来,这样可以保证画出来的圆把整个mc都抱在了里面,大家看到除以2了吧,所以一定能想到 mc 的注册点一定是在中心哦(这也是关键之一^^)
接着,和定义半径大小一样,我们做个360度每一度检测一下,也是可以的,但是这样做会很费资源,而且也没有必要那么精细.
所以才会有一个描边级数num,这个级数就是规定了,分num个等次来描,来记录num个点的坐标.然后就是运用了
随便画个形状,在这个mc中写下面的代码,场景上再建立一个mc,命名为mc2
你可以看到,你的描边级数越高,每次检测的就越多,所以尽量减少就可以了,像我游戏里面只定义了10.
其实这只是一个大概的数据,并不是百分百的描边,不过这样已经够用了^^”

数学不好,解释的不太清楚,大家不懂的再发贴问,我尽量解释,当然也请高手帮忙完善^^!

转】MSDN中关于OnDrawItem的说明

afx_msgvoidOnDrawItem(intnIDCtl,LPDRAWITEMSTRUCTlpDrawItemStruct);

Parameters

nIDCtl

     存储发送WM_DRAWITEM消息的控件ID，如果是菜单发送的，nIDCtl的值为0。

lpDrawItemStruct

     一个指向DRAWITEMSTRUCT结构体的指针，该结构体保存有关要被绘制的项目与绘制所需要的类型等星系。

Remarks

当自绘按钮(owner-draw button)，下拉列表框(combo box)，列表框(list box)视觉属性，或者菜单发生变化时，框架为他们的owner调用该函数。

DRAWITEMSTRUCT结构的itemAction成员定义了要进行的绘制操作行为。该值确定了所需的绘制动作。

在处理完此消息之前，应用程序应当确保由DRAWITEMSTRUCT结构的成员hDC标识的设备上下文还原到默认状态。

如果上面结构的成员hwndItem指向CButton，CMenu，CListBox或者CComboBox对象，那么就调用相应类的DrawItem虚函数。重载相应类的DrawItem成员函数来绘制各个项。

其他的一些说明：

OnPaint()这个函数是在已经有形的控件上进行画图的     
  OnPaint()  
  {  
      在这里只是画原控件没有的图形  
  }  
   
  OnDrawItem()这个函数是自已去绘画一个控件，根据你想要的形状，图案.它是建立一个控件的外表而用到的

可以这样理解，OnDrawItem是画窗口中的子控件的，因为它的入口参数LPDRAWITEMSTRUCT带入不同子控件的相关参数，而且，你得把字控件设置成“自画”类型，才会调用到OnDrawItem，顺便说一下自画，不是所有设置成自画类型的控件都会调用父窗口的OnDrawItem，例如ListBox的自画，你就必须重载CListBox的DrawItem方法和MeasureItem方法才可以，但象菜单，按钮等的自画则会调用OnDrawItem。OnPaint和OnDrawItem不在一个范畴内，他是WM_PAINT的响应函数，凡是基于CWnd的类都有OnPaint事件发生，就是说凡是窗口都有WM_PAINT事件发生。（不知道我理解的对不对）

2009产品创新数字化峰会征文：基于CAD的碰撞检测技术及其在虚拟装配拆卸系统中的应用

1 引言

    几何形体间的碰撞检测在虚拟装配和拆卸过程中几乎无处不在，碰撞检测的精度决定了虚拟装配和拆卸的精度，对于目前的商用VR开发平台而言，普遍采用多边形（通常是三角形）描述场景中的任意几何形体，并通过纹理映射、光照模型来模型物体在真实世界的视觉效果。而多边形模型首先是面模型，面模型不包括物体的内部信息，无法计算由面所组成的体之间的空间干涉情况，只能计算面面之间的相交情况；其次多边形模型只是对形体几何的逼近形式，对形体的逼近程度决定了三角形面片数量的多少，逼近程度越高，三角形网格数量越多，渲染和碰撞检测的时间开销越大；对形体的描述形式决定了基于多边形网格的碰撞检测算法难以实现物体间的精确碰撞检测。

    精确的碰撞检测首先要保证模型是精确的，其次要保证碰撞检测算法要基于精确模型之间的空间相交求解。在目前一些大型的商用CAD软件中，如UG、Pro/E等，不仅采用初等解析曲面和样条曲面定义几何物体的外形轮廓曲面，而且采用的是体模型，能够准确定义几何物体的内外部空间，同时其提供的静态干涉检查功能和算法是成熟的，分析时间是高效的，本文通过把商用CAD系统提供的干涉检查功能无缝集成到定制开发的虚拟装配和拆卸系统中，一方面能够实现形体间的精确碰撞检测，同时能够快速地绘制场景以实现交互，并进一步通过采用诸如包围盒等方式构造合适的精确碰撞检测加速策略，快速排除大量不会发生碰撞的物体对，降低复杂场景中进行精确碰撞检测的开销，提高虚拟装配/拆卸系统的实时性。

2 总体技术方案

    目前商用的VR开发平台均不提供基于CAD几何模型的精确碰撞检测功能，而只提供基于多边形相交测试的碰撞检测功能，不仅碰撞检测精度难以提高，而且由于难以判别包容干涉、接触干涉、硬干涉三种之间的区别，对于虚拟装配和拆卸过程中广泛存在的对齐、贴合、相切等情况难以得到正确的碰撞检测结果，从而影响系统对这类情况做出正确的反应。

    通过深入的研究和程序开发，本文在VR环境中实现了基于CAD几何模型的快速精确碰撞检测功能，图1是系统结构框图。

    从图中可以看出，CAD模型是联系前台的场景展示和后台的碰撞检测计算的纽带，一方面，基于CAD的精确碰撞检测平台在后台对CAD模型进行空间干涉计算，另一方面，前台根据CAD模型动态生成场景图并进行绘制以用于用户交互，从而将仿真的三维显示和仿真计算分离。当场景中的几何对象发生运动时，通过在二者之间建立的通讯技术同步更新运动的几何对象在场景中的几何方位并保持一致。几何对象运动过程中的干涉计算采用离散时间步的方法进行计算，即：几何对象运动时，在场景中以一定的时间间隔步进，同时把该物体运动后的空间方位通过通讯传递给后台用于计算的CAD碰撞检测平台，在后台同步更新运动部件的空间方位后，与其它部件在该时刻进行静态的碰撞干涉计算，然后得到并分析计算结果，并把计算结果通过通讯计算传递到前台VR环境控制端，如果部件间没有发生干涉，则继续进行下一个步进动作，否则在场景中发出干涉信号并做出相应的反应。这样只要步进的距离或角度足够合理，可以获得几何对象运动过程中可能发生的任何干涉情况。

图1系统结构框图

3 关键技术

    3.1基于CAD的精确碰撞检测算法及其程序实现

    CAD交互界面下的干涉检查功能无法实现批量自动化处理，显然无法集成到定制开发的VR系统中去，为此，必须找到脱离CAD交互运行界面的程序自动化计算方法。通常而言，高端商用CAD系统提供有二次开发包，在其开发包上进行二次开发有望实现干涉检测的程序自动化处理。

    UG NX是高端CAD系统，其提供的二次开发工具NX/Open功能强大，在NX/Open的基础上能够开发实现任意几何对象之间的精确碰撞检测的自动计算。

    使用NX/Open的进行干涉检查分析的步骤如下：

    1)创建一个间隙分析数据集，分配空间并设置相关属性

    2)设置间隙分析模式，允许采用实体模型或多边形网格模型进行干涉检查。

    3)设置间隙分析规则，设置需要排除的干涉检查对。

    4)设置间隙分析中用于分析的几何对象。

    5)进行间隙分析，对上面的设置进行干涉分析。

    6)对计算结果进行分析。从计算结果中找到发生硬干涉的物体对以及干涉区域。

    使用NX/Open进行干涉检查的计算结果的干涉类型分为如下4类：

    1)不干涉：几何对象间没有发生干涉；

    2)包容干涉：一个几何对象在另一个几何对象内部；

    3)硬干涉：两个几何物体在三维空间存在空间位置重叠并且存在相交的空间曲面；

    4)接触干涉：两个几何物体在三维空间存在点或空间曲面接触，但不存在公共的实体空间；

    通过对干涉计算结果进行分析，可以得到任意两个几何对象间的准确的空间干涉情况。

    3.2基于CAD的VR场景图动态生成技术

    商用VR开发平台不能识别并绘制CAD模型，商用的VR开发平台通常只支持多边形网格模型，而CAD模型是由参数曲面组成的三维实体模型，为了在VR开发平台下渲染CAD模型，必须根据CAD模型的层次结构动态生成VR场景图对象。

    根据CAD模型动态创建VR场景图的关键在于把CAD参数曲面转换为某张逼近程度的多边形网格模型，并按照规定的层次和结构组合成一颗场景树。

    对于一个UG装配文件，采用如下方式组织VR场景图（VR开发平台采用Vega Prime）：

    1)在Vega Prime场景图根节点上创建一个vpObject组节点，UG装配文件根节点对应于该组节点。

    2)对于UG装配中的每一个部件，在Vega Prime场景图中创建一个vpTransform节点，并把该节点作为第一步创建的vpObject节点的子节点。根据该部件在装配中的空间方位矩阵定义一个vpTransform节点中的方位矩阵，如果该部件是零件模型，则创建一个vsGeometry节点，并把该节点作为vpTransform的子节点；如果该部件仍然是一个装配模型，则再创建一个vpTransform节点，并把该节点作为上一级vpTransform的子节点，把该vpTransform节点作为父节点递归调用步骤2；

    通过如上步骤，建立了与CAD模型层次结构类似的Vega Prime场景图结构。

    CAD几何模型到多边形网格模型的转换需要借助于具体的参数曲面离散和多边形网格剖分算法，对于不同类型的的参数曲面，曲面离散和多边形网格剖分算法复杂程度不同，文献[1]对此有详细的描述。

3.3 可视化前端与后台计算端的几何对象空间方位同步机制

    由于用于用户交互的可视化前端绘制的是由参数曲面离散生成的多边形网格，而后台碰撞检测计算采用的是最初的CAD模型，为了保证碰撞检测结果的正确性，必须保证这两个环境中的部件在任意时刻的空间相对方位保持一致。基于CAD的VR场景图动态生成技术保证了在初始时刻二者在空间方位上的一致性，同步机制需要保证在任意时刻运动部件在二者当中具有同样的运动特性。采用如下步骤保证二者中的几何对象空间方位的一致性：

    1)在Vega Prime场景图节点对象和CAD中的几何对象之间建立一一映射关系，只有建立了一一映射关系，才有可能当用户在交互界面中选择并移动或旋转了某个几何对象时，系统才能指导该几何对象对应于CAD中的哪一个几何对象，并进行相应的平移或旋转。

    2)定义一个结构，该结构用于描述平移或旋转的类型及所有参数以及碰撞检测结果，变换的类型及参数用于在CAD计算端进行同样的变换操作，碰撞检测结果用于指示可视化前端进行相应的响应。该结构定义如下：

    Struct CommunicationData{
    Tag_t motionprt;  //当前运动的几何对象
    Unsigned int motiontype;  //0代表平移，1、2、3分别绕xyz轴旋转
    Double translate[3];  //代表进行平移的坐标值
    Double angle;  //代表旋转的角度值
    BOOL bIsCollision;  //代表是否发生空间干涉 }
   
    3)当可视化前端选中某个几何对象并进行相应的运动后，填充CommunicationData中的数据并传递到CAD计算端，CAD计算端根据旋转或平移的大小重新计算运动部件在CAD场景中的方位矩阵，最后采用UF_ASSEM_reposition_part_occurrence或者UF_ASSEM_reposition_instance函数把运动部件放置在新的位置。

    4)CAD端计算运动部件在新的方位处与其它部件之间的空间干涉情况，如果干涉计算结果为硬干涉，则发生空间干涉，填充CommunicationData结构中的bIsCollision域并通知可视化前端，可视化前端获取该值并做出相应的反应。

   3.4 碰撞检测加速策略

    层次包围盒方法的基本思想是用体积略大而几何特性简单的包围盒来近似描述复杂的几何对象，进而通过构造树状层次结构来逼近对象的几何模型，直到几乎完全获得对象的几何特性，从而只需对包围盒重叠的部分进行进一步的相交测试。层次包围盒最重要的特点是能够应用于任意形状的几何对象的物体的碰撞检测，因此也是目前应用最广泛的一种碰撞检测方法。

    层次包围盒树根据包围盒类型的不同又可分为包围球、AABB、OBB、k-Dop等等，对应于每一类的包围盒都有一个代表性的碰撞检测算法，包围盒的示意图如图6所示：

    表1是对几种基本包围盒的碰撞检测算法的性能比较，沿坐标轴的包围盒AABB（axis-aligned bounding boxes）是使用的最久也是最广的包围盒类型，一个给定对象的AABB被定义为包含该对象且各边平行于坐标轴的最小的六面体。其计算十分简单，只需分别计算组成对象的基本几何元素集合中各个元素的顶点的X、Y、Z坐标的最大值和最小值即可；两个AABB相交当且仅当它们在三个坐标轴上的投影区间均重叠，AABB间的相交测试最多只需要6次比较运算。AABB也是众多VR开发平台广泛支持的包围盒类型，为此，本文采用AABB作为选定的包围盒类型。

    本文采用AABB层次包围盒加基于CAD模型的精确碰撞检测算法实现碰撞检测，其中层次包围盒算法用于快速排除场景中没有发生干涉的物体对，对于采用层次包围盒算法计算后仍然干涉的物体对，用采用基于CAD模型的精确碰撞检测算法进行准确的碰撞检测，这样一方面保证了碰撞检测结果的正确性，另一方面能够大大降低碰撞检测的时间开销。

表1基本包围盒碰撞检测算法比较

4 应用实例及结论

    图3是在Vega Prime中开发的原型系统的程序运行界面，在该原型系统中，通过选择运动部件并设置运动路径（平移和旋转），程序通过计算运动部件运动过程中与其它部件的空间干涉情况来判断该运动过程是否存在干涉，空间干涉的结果根据在运动过程中运动部件和非运动部件的UG CAD模型的空间干涉情况得出。

图3原型系统运行界面

图4用于碰撞检测测试的模型

    图4是用于虚拟安装测试的模型，需要把红色部件插入到另一个部件的中心圆孔中（圆孔直径与红色物体外径相同），实际上，在插入圆孔的过程中，它们之间只存在接触干涉,而不存在空间硬干涉，对此，基于CAD模型的精确碰撞检测算法可以正确识别，而基于多边形相交测试的碰撞检测算法只能把这类情况作为发生干涉进行处理。

    表2显示了在p4 3.4GCPU，4G内存和Nvidia Quadro Fx1400显卡微机上进行测试时（红色物体逐步插入圆孔中心，采样100帧的平均值）不同碰撞检测算法和时间开销比较表。

表2几种碰撞检测算法计算的平均时间开销

    从试验结果可以看出，基于CAD模型的精确碰撞检测算法可以区分接触干涉和硬干涉以及包容干涉之间的区别，同时可以在很快的时间开销下完成几何物体间的精确碰撞检测，采用层次包围盒可以进一步降低碰撞检测的时间开销，而采用基于多边形一一相交测试的碰撞检测算法的时间开销随着用于碰撞检测的多边形数目的增加而急剧增加。

    实践证明，本文提出的技术方案切实可行，不仅解决了商用VR开发系统中碰撞检测精度难以提高的技术问题，而且用于精确碰撞检测的时间开销能够满足工程实际需要。

[参考文献]

[1] 赵瑛峰，NX Openflight数据交换输出接口开发技术研究[J]，产品数字化实践论文集，电子工业出版社，2008.5

// 球体－球体的碰撞 Sphere-Sphere Collision 

bool IsCollidingSphereToSphere()

{

      // 两个小球的相对速度

      relative_vel = Sphere2_Vel - Sphere1_Vel;

      r = Sphere1_Radius + Sphere2_Radius;

      relative_position = Sphere2_Center – Sphere1_Center;

      // 检查两个小球是否已经碰撞

      if ((Sqr_relative_position - (r*r)) <= 0)

            return true; 

      // 提前跳过测试：如果两个小球朝向远离对方的方向移动，则返回false

      float rel_distance = sqrt(Sqr_relative_pos) - (r); 

      //这里我们需要检测两次update之间是否存在碰撞

      if (rel_distance < (sqrt(Sqr_relative_vel)*update_interval))

      {

            time_fract = rel_distance/sqrt(Sqr_relative_vel);

            time_remain = update_interval – time_fract;

            if ((Sqr_relative_pos - (r*r)) <= 0)          {     return true;              }      }      return ((relative_movement * relative_movement - ((Sqr_relative_pos - r*r) -              Sqr_relative_vel)) >

            0);

} 

// 球体－平面的碰撞 Sphere-Plane Collision

bool IsCollidingSphereToPlane()

{

      // 提前跳过测试：检查小球是否可以在没有碰撞的情况下移动，

      // 如果可以，则返回false；

      // 如果不可以则检测球体与平面之间的距离是否为

      for (int i=0; i<6; i++)

      {

            // 小球的速度与平面法向量的点积

            // 如果点积为，则速度矢量平行与平面，因此不可能碰撞

            float unit_normal_vel_dot = normal . velocity;

            if (unit_normal_vel_dot < 0.0f)

            {

                  // 计算平面公式

                  float D1 = normal * point_on_plane;

                  float normal_pos_dot = normal . center_S;

                  // 计算球心到平面的距离

                  float distance = (D1-normal_pos_dot)/unit_normal_vel_dot;

                  // 这里处理球体已经接触到盒子的情况

                  if (distance <= radius1)                {                   collide = true;                      // 存储这个面的法向量              }                    break;             }            else         {                  float Projected = velocity * update_interval;                 // 这里处理球体在update_interval时间移动距离x，               // 但是x小于球与平面的距离的情况                 if (Projected > distance)

                  {

                        collide = true;

                        time_fract = (distance–radius)/velocity;

                        time_remain = update_interval - time_fract;

                  }

                  break;

            }

      }

      return collide;

物移动控制是单机和网游中比较重要的部分，但前单机游戏使用动力学以及IK动画等已经达到了非常逼真的地步，在大型网络游戏中这样的物理模拟同步是很实现的，因此在目前多数网游中仍旧是采取使用一个包围体（盒子或者胶囊）来模拟人物。一个好的移动系统是很重要的，平滑的贴墙滑动以及下滑，跳跃等会带给玩家顺畅的手感否则则会有种奇怪的感觉，本文具体介绍了一下碰撞反应，包括贴墙滑动等的具体实现细节。包括一个demo实例 。
目前物理引擎里面大多自带独立于刚体的人物角色控制，但是物理引擎需要特定的物理模型命名以及比较大的物理模拟开销度。如果需要定制自己的特别功能或者需要简化计算（同时模拟多个延迟或者玩家的反应）。就必须自己完成人物碰撞反应控制的代码。
要完成人物发生碰撞以后的行为控制，需要碰撞检测系统提供以下的碰撞信息，对于每一个碰撞：
1． 碰撞发生的时间
2． 碰撞的法向量
3． 碰撞点
对于基本的人物碰撞控制反应来说，以上3点是必须的，有时还需要提供和包围体发生碰撞的具体三角形信息。

对于场景上的物体首先使用胶囊所在的包围盒AABB或者OBB和场景中的碰撞体包围盒作层次碰撞裁减，至于具体怎么组织可以任意，比如可以采用AABB或者OBB树，也可以采用简单的球树。但碰撞进行到树的叶子节点后开始检测人物的AABB盒和该AABB盒所包围的OBJECT的碰撞情况。如果发现这2个AABB（OBB）盒将会发生碰撞，那么开始使用人物的胶囊体和景物所带的三角面片进行精确到polygon soup级别的比较。这时候仍旧可以优化，比如说我还做了一步把一个Object中的三角形面片打成BSP树的形式存储起来，这样可以大大减少胶囊和三角形碰撞检测的次数，因为这种动态检测是十分耗时的。有关胶囊和三角形面片的比较可以参考：http://dev.gameres.com/Program/Abstract/Arithmetic/capsule.mht中的方法。 对于BSP的划分以及AABB碰撞检测就不用多说了~到处都可以找到文章。
对于地形而言，也是采用同样的方法，只不过对于地形而言三角形信息不用额外存储，只需要使用和渲染相同的三角形（对于景物来说一般不会使用渲染用的三角形而会使用更加简化数量更少的简化网格碰撞模型）。这里可以有很多优化的技巧，因为地形本身是规则的cell一个地形是由若干个patch(一般是16X16)组成的，而每个patch是由若干cell(一般是16X16)组成的。对于patch来说一般已经组织到了一颗QUADTREE中了因为视棱锥裁减也需要这种结构，因此碰撞检测中的AABB-AABB阶段使用这颗已经存在的QUADTREE就可以快速的完成层次碰撞检测了。但发现某个patch中的AABB和人物的AABB发生碰撞后需要检测每一个CELL所在的AABB和人物AABB盒的碰撞，这里可以使用点小技巧比如说首先将AABB盒投影到CELL所在的XY平面上，找出被投影覆盖的那些CELL然后再检测这些CELL的AABB盒是否和人物的发生碰撞。一但确定了某个CELL和人物发生碰撞那么就可以将该CELL中的三角形取出（一般为2个）依次和人物所在的胶囊进行三角形-胶囊的碰撞检测。
这样当碰撞检测系统完成任务以后我们将会获得一个碰撞信息的数组：
class CollideInFo{
public:
GFVECTOR_3D m_worldcdnorm;//碰撞法向量
GFPOINT_3D m_worldpoint;//碰撞点
float m_cdtime;//碰撞时间
};

CollideInFo collidearray[]；
然后使用这个数组就可以进行碰撞后的处理了包括，沿墙滑动下滑等等。在具体说明整个人物移动控制算法之前，首先说下动态碰撞检测和静态碰撞检测的区别，动态碰撞检测是指物体A以速度V前进了T时间，在这期间第一次和物体B发生碰撞的时间。这样的碰撞检测必须返回第一次2个物体发生碰撞的时间。而静态检测是指2个不动的物体是否互相相交对于这种检测是不需要返回时间的。动态检测算法比静态的复杂而且也耗用更多的时间。一个完善的碰撞系统需要解决以上2种碰撞检测，如果你不想自己写检测代码，目前比较流行的有OPCODE，SOLID库等检测库 。你可以直接使用他们提供的功能，这里我采用的是自己写检测代码的方法，目前只用到三角形-胶囊，AABB-AABB，OBB-OBB的碰撞检测。 [Page]
完成了包围体（用的是胶囊）和三角形的碰撞，胶囊和BSP，地形的碰撞检测之后，拥有了碰撞的信息 1。碰撞时间。2。碰撞法向量。3。碰撞点。接着就可以处理人物在碰撞后的反应了。
首先人物的一次移动分2个阶段，第一个是初始阶段，使用静态碰撞检测获得该阶段的速度（具体做法在后面说）。第2阶段使用该速度去做动态碰撞检测得到碰撞信息，根据这些碰撞信息去处理碰撞后的反应。
先来看第一阶段，过程对于一个胶囊我们需要获取他周围的临近面片的信息，以决定这个胶囊目前所处平面的倾斜度，是否贴着不可通过的墙等等。我采用的方法是将胶囊体略为膨胀一些，然后调用静态碰撞检测的代码获取和该膨胀后的胶囊体相交的三角形面片碰撞信息如图：
棕色的是原始的胶囊体，红色的表示将胶囊半径略为增加以后的胶囊体，蓝色的2个地形是将胶囊膨胀以后所发生相交的2个三角形，而如果不采用膨胀的话该胶囊是不和任何三角形相交的，具体膨胀数值可以设为胶囊下落的最小高度，比如你设定胶囊离底部物体超过0.6单位属于腾空状态的话你就将膨胀数值设为0.6。在这个例子中我们将会检测到2个碰撞（蓝色部分）这2个碰撞法向量正好是这2个三角面的法向量（在很多情况下也可能不是这个看你的碰撞代码中法向量是如何计算的了）。其中底部的那个是可行走平面，另外一个是不可行走平面，有了这2个碰撞平面就很简单了，如果用户输入的速度和那个不可行走的平面相反（也就是撞向那个不可行走平面），那么那个不可行走平面是有效的，这样他和底部那个可行走的平面所组成的交线就是人物的初始速度，如果用户输入的速度和那个不可行走的平面法向量相同，那么这个不可行走平面没有作用人物最终的速度就是把用户速度投影到该可行走平面上的速度。
0顶一下

具体计算是否能够水平移动以及移动速度的算法：当给出M个不可行走平面和N个可行走平面时：
1首先将速度在N个可行走平面上分解，检查这些分解的速度是否有效（如何判断速度有效下面会说道）
2如果在1的时候存在一个有效的速度直接返回该速度
3没有有效速度，这时检查NXM个平面的交线，将速度在上面分解同时检查是否存在有效速度
4如果存在有效速度返回该速度
5否则检查MXM条交线的，将速度在上面分解同时检查是否存在有效速度
6如果存在有效速度返回该速度
7否则返回0速度
那么如何判定速度是否有效呢，首先我们知道了所有碰撞的信息，给定一个速度，如果该速度和所有碰撞的法向量的夹角都是小于90度那么这就是个有效速度，（说明该分解后速度不会引起和这些碰撞面的在一次碰撞，因为该速度是将物体拉下远离该平面的方向的）。如果只要有一个夹角大于90度那么该速度就是非有效速度，同时在移动时还要判断该速度的倾斜角是否大于最大下滑倾斜角。注意 5是很重要的因为2个不可行走的平面所形成的交线仍旧可能是可以行走的，甚至是水平的。
以上的部分是检查是否能够水平移动的，如果不能水平移动那么该物体会下滑，1如果没有检测到碰撞平面说明物体处于腾空状态，这时候给物体加上重力加速度，产生一个往下的速度和原来的水平速度结合起来（如果存在）。
如图棕色是原始状态胶囊经过上一帧移动后到达蓝色的位置这时通过上诉算法可以检测到胶囊腾空，这时他的速度为水平速度（红色）+下滑速度（绿色）。
2如果检测到碰撞平面但是平面以及它们的交线都是不可行走的（倾斜角大于可行走角度）那么依次将当前速度在碰撞平面分解，以及检测每一条可能下滑的交线。得出速度后检测是否是有效速度具体过程和前面检查水平速度时的方法一样，只是将速度投影到平面上的方法不一样具体方法可以根据程序需要，我这里采用首先去掉原始速度在碰撞平面法线的分量，然后将速度分解为2个速度一个是贴着平面水平移动的速度另外一个是贴着平面下滑的速度。注意如果上一帧更新后物体处于下滑状态那么当前速度就因该是该下滑速度，否则则是用户输入的速度。
如果用户输入的速度是跳跃也就是带Z分量的速度那么，计算初始速度这一步需要略过直接输入给下一阶段用户起跳的速度。

阶段2计算初始速度引起的碰撞

对于多数情况来说，计算完初始速度就不会再发生碰撞了，一旦发生，那么我们依旧传入碰撞面的那些法向量，碰撞点的信息，同样采用前面计算初始速度时所采用的方法，计算出碰撞后的调整速度。 [Page]

整个处理过程基本上就是这样的，其中可能还会出现一些小问题比如说误差控制等。总结一条就是人物行走要么研着平面分解速度要么沿着2个平面的交线行走或者下滑。这个是Demo示例画面（由于没有人帮我做动画。。所以demo中目前只有行走动画，没有起跳，下落等动画。。）