[弱弱的问] 现在3D游戏中的碰撞检测是通过什么实现的?
[问题点数：30分，结帖人xiao7cn]
[弱弱的问] 现在3D游戏中的碰撞检测是通过什么实现的?
[问题点数：30分，结帖人xiao7cn]
不显示删除回复
显示所有回复
显示星级回复
显示得分回复
只显示楼主
2005年7月 专题开发/技术/项目大版内专家分月排行榜第二2005年5月 专题开发/技术/项目大版内专家分月排行榜第二2004年9月 专题开发/技术/项目大版内专家分月排行榜第二2004年3月 专题开发/技术/项目大版内专家分月排行榜第二2004年1月 专题开发/技术/项目大版内专家分月排行榜第二2002年12月 专题开发/技术/项目大版内专家分月排行榜第二
2005年3月 专题开发/技术/项目大版内专家分月排行榜第三2004年12月 专题开发/技术/项目大版内专家分月排行榜第三2004年8月 专题开发/技术/项目大版内专家分月排行榜第三2004年7月 专题开发/技术/项目大版内专家分月排行榜第三2003年12月 专题开发/技术/项目大版内专家分月排行榜第三2003年9月 专题开发/技术/项目大版内专家分月排行榜第三2003年8月 专题开发/技术/项目大版内专家分月排行榜第三2003年7月 专题开发/技术/项目大版内专家分月排行榜第三
匿名用户不能发表回复！|后使用快捷导航没有帐号？
　论坛入口：
　　|　　　|　　　　|　　　|　
我要游戏程序
查看: 6951|回复: 4
球体与三角形的连续碰撞检测实现方法
原文http://www.cnblogs.com/Perit/articles/1759781.html 作者: Perit
DX为我们提供了射线与三角形碰撞检测函数
BOOL D3DXIntersectTri(
&&CONST D3DXVECTOR3 *p0,
&&CONST D3DXVECTOR3 *p1,
&&CONST D3DXVECTOR3 *p2,
&&CONST D3DXVECTOR3 *pRayPos,
&&CONST D3DXVECTOR3 *pRayDir,
&&FLOAT *pU,
&&FLOAT *pV,
&&FLOAT *pDist
& & 但是如果我们用一个半径一定的球体按一定方向发射, 如何求出球将会什么时侯碰到三形形的什么位置, 碰撞点的法向如何, 球将会向何方继续运动, 或者结果球不会与三形形相撞. 作为连续碰撞检测来讲, 球体与三角形的连续碰撞检测是一个最基本的最核心的算法. 而连续碰撞检测算法也较我们常用的静态相交测试要费事的多. 在两篇外文文档中管这种检测叫&sweep test&.而介绍这种碰撞检测的资料十分少. 网上仅能找到的有价值的是下面两篇资料.
1) Generic Collision Detection for Games Using Ellipsoids
Paul Nettle
June 13, 2000
(Revised October 5, 2000)
2)Improved Collision detection and Response
Kasper Fauerby
kasper@peroxide.dk
http://www.peroxide.dk
25th July 2003
& & 第一篇文档是最老的一篇文档, 我当时按其内容实现了其算法, 但是我在测试算法时总是能感觉球体在和三角形边缘碰撞时计算不正确, 因此做了很多检测, 最后确定是第一篇文档的算法本身出了问题, 从网上相关信息搜索来看仅能看到GameDev论坛上有人提出相似的凝问(http://www.gamedev.net/community/forums/topic.asp?key=featart&uid=1026&forum_id=35&Topic_Title=General+Collision+Detection+for+Games+Using+Ellipsoids), 其它信息没了. 经过不断搜索相关资料终于发现了上面的第二篇文档, 上面也说明是第一篇文档的增强形算法,解决了上篇文档中的三角形边缘和球体的碰撞检测错误. 至此经过我按第二篇文档的方法测试, 证明其算法正确. 这儿简单说明下算法原理, 具体可以阅读上面两篇文档.&&
为了和ＤＸ的射线和三角形相交的函数配套,我们仿照它的函数原型写出我们的函数原型
BOOL SphereIntersectTri(const Vec3D &v0,
& && && && && && && && &const Vec3D &v1,
& && && && && && && && &const Vec3D &v2,
& && && && && && && && &const Vec3D &start,
& && && && && && && && &const Vec3D &end,
& && && && && && && && &const float radius,
& && && && && && && && &float &dist,
& && && && && && && && &Vec3D &pos,
& && && && && && && && &Vec3D &normal)
最基本的相交算法, 球体和平面的相交算法. 见下图:
(图片取自上面的文档)
我们利用这个算法可以求出如果球体和三形形平面向撞，并且相撞点在三形形内部的话，其碰撞点就是我们最终要求的点。
求点是否在三角形内部有好几种方法。
一是检测所有点是否在三角形各条边同一侧
BOOL SameSide(const Vec3D &pos1, const Vec3D &pos2, const Vec3D &a, const Vec3D &b)
& & Vec3D ab = b -
& & Vec3D d1 = pos1 -
& & Vec3D d2 = pos2 -
& & Vec3D cross1;
& & Vector3Cross(ab, d1, cross1);
& & Vec3D cross2;
& & Vector3Cross(ab, d2, cross2);
& & float fdot = Vector3Dot(cross1, cross2);
& & if(fdot &= 0)
& && &&&return TRUE;
& && &&&return FALSE;
// 判断是否点位于各条边的同一侧
BOOL pointInTriangle(const Vec3D &pos, const Vec3D &posA, const Vec3D &posB, const Vec3D &posC)
& & if( SameSide(pos, posA, posB, posC) &&
& && &&&SameSide(pos, posB, posA, posC) &&
& && &&&SameSide(pos, posC, posA, posB) )
& && &&&return TRUE;
& & return FALSE;
二是利用面积测试点是事位于三角形内部
float triangleArea(const Vec3D &pos1, const Vec3D &pos2, const Vec3D &pos3)
& & Vec3D d1 = pos2 - pos1;
& & Vec3D d2 = pos3 - pos1;
& & Vector3Cross(d1, d2, cross);
& & float result = 0.5f * cross.length();
// 利用面积测试点是事位于三角形内部
BOOL pointInTriangle2(const Vec3D &pos, const Vec3D &posA, const Vec3D &posB, const Vec3D &posC)
& & double triArea = triangleArea(posA, posB, posC);
& & double area = triangleArea(pos, posA, posB);
& & area += triangleArea(pos, posA, posC);
& & area += triangleArea(pos, posB, posC);
& & double epsilon = 0.0001;
& & if (fabs(triArea - area) & epsilon)
& && &&&return TRUE;
& & return FALSE;
如果碰撞点不在三角形内部，我们就要检查碰撞点会不会在三角形的三个顶点和三条边上，并且取出最早的一个碰撞点做我们的返回值.
球体和点的碰撞检测和球体和线段的碰撞撞检测我们都采用解一元二次方程的方法来解决．
一元二次方程我们用如下函数来计算
bool getLowestRoot(float a, float b, float c, float maxR, float &root)
& & // Check if a solution exists
& & float determinant = b*b - 4.0f*a*c;
& & // If determinant is negative it means no solutions.
& & if (determinant & 0.0f)
& & if(a == 0.0f)
& & // calculate the two roots: (if determinant == 0 then&&x1==x2 let us disregard that slight optimization)
& & float sqrtD = sqrt(determinant);
& & float r1 = (-b - sqrtD) / (2*a);
& & float r2 = (-b + sqrtD) / (2*a);
& & // Sort so x1 &= x2
& & if (r1 & r2)
& && &&&float temp = r2;
& && &&&r2 = r1;
& && &&&r1 =
& & // Get lowest root:
& & if (r1 & 0 && r1 & maxR)
& && &&&root = r1;
& & // It is possible that we want x2 - this can happen if x1 & 0
& & if (r2 & 0 && r2 & maxR)
& && &&&root = r2;
& & // No (valid) solutions
下面是球体和点的碰撞检测函数
A = velocity * velocity
B = 2 * (velocity * (basePoint - p))
C =&&(p&&- basePoint).length()^2 - 1
BOOL sphereIntersectPoint(const Vec3D &p,
& && && && && && && && &&&const Vec3D &start,
& && && && && && && && &&&const Vec3D &end,
& && && && && && && && &&&float radius,& && && && && && && && && &
& && && && && && && && &&&float &t,
& && && && && && && && &&&Vec3D &collisionPoint)
& & // some commonly used terms:
& & Vec3D velocity = end -
& & Vec3D base =
& & float velocitySquaredLength = velocity.lengthSquared();
& & float a, b, // Params for equation
& & float newT;
& & bool foundCollison =
& & // For each vertex or edge a quadratic equation have to
& & // be solved. We parameterize this equation as
& & // a*t^2 + b*t + c = 0 and below we calculate the
& & // parameters a,b and c for each test.
& & // Check against points:
& & a = velocitySquaredL
& & b = 2.0f * (Vector3Dot(velocity, (base-p)));
& & c = (p-base).lengthSquared() - radius *
& & if (getLowestRoot(a, b, c, t, newT))
& && &&&t = newT;
& && &&&foundCollison =
& && &&&collisionPoint =
& & return foundC
下面是球体和线段的碰撞检测函数
// Check agains edges: p1 -& p2:
BOOL sphereIntersectEdge(const Vec3D &p1,
& && && && && && && && & const Vec3D &p2,
& && && && && && && && & const Vec3D &start,
& && && && && && && && & const Vec3D &end,
& && && && && && && && & float radius,& && && && && && && && &&&
& && && && && && && && & float &t,
& && && && && && && && & Vec3D &collisionPoint)
& & bool foundCollison =
& & Vec3D velocity = end -
& & float velocitySquaredLength = velocity.lengthSquared();
& & Vec3D edge = p2 - p1;
& & Vec3D baseToVertex = p1 -
& & float edgeSquaredLength = edge.lengthSquared();
& & float edgeDotVelocity = Vector3Dot(edge, velocity);
& & float edgeDotBaseToVertex = Vector3Dot(edge, baseToVertex);
& & float a, b,
& & float newT;
& & // Calculate parameters for equation
& & a = edgeSquaredLength * -velocitySquaredLength + edgeDotVelocity * edgeDotV& &
& & b = edgeSquaredLength * (2 * Vector3Dot(velocity, baseToVertex)) - 2.0f * edgeDotVelocity * edgeDotBaseToV
& & c = edgeSquaredLength * (radius * radius - baseToVertex.lengthSquared()) + (edgeDotBaseToVertex * edgeDotBaseToVertex);
& & // Does the swept sphere collide against infinite edge?
& & if (getLowestRoot(a,b,c, t, newT))
& && &&&// Check if intersection is within line segment:
& && &&&float f = ( edgeDotVelocity * newT - edgeDotBaseToVertex ) / edgeSquaredL
& && &&&if (f &= 0.0 && f &= 1.0)
& && && && &// intersection took place within segment.
& && && && &t = newT;
& && && && &foundCollison =
& && && && &collisionPoint = p1 + f*
& & return foundC
最后给出综合各种检测的结果
BOOL SphereIntersectTri(const Vec3D &v0,
& && && && && && && && &const Vec3D &v1,
& && && && && && && && &const Vec3D &v2,
& && && && && && && && &const Vec3D &start,
& && && && && && && && &const Vec3D &end,
& && && && && && && && &const float radius,
& && && && && && && && &float &dist,
& && && && && && && && &Vec3D &pos,
& && && && && && && && &Vec3D &normal)
& & Vec3D sphereIntersectionP
& & Vec3D planeIntersectionP
& & Vec3D polygonIntersectionP
& & BOOL embedInPlane = FALSE;
& & Vec3D velocity = end -
& & Vec3D dir = velocity.normalize();
& & Plane triPlane(v0, v1, v2);
& & Vec3D n = triPlane.
& & float dStart = triPlane.getDistance(start);
& & // 北向三角形运动
& & float vn = velocity *
& & if(vn & 0.0f)
& && &&&return FALSE;
& & // 运动方向和三角形平行
& & if( fabs(vn) & std::numeric_limits&float&::epsilon() )
& && &&&if(fabs(dStart) &= radius)
& && && && &return FALSE;
& & // 剔除背向的三角形
& & if(dStart & 0)
& && &&&return FALSE;
& & if(dStart &= radius)
& && &&&embedInPlane = TRUE;
& && &&&// Is the plane embedded
& && &&&// Calculate the plane intersection point
& && &&&planeIntersectionPoint = start - dStart *
& && &&&//
& && &&&// 运动起点和终点是否在三角形同一侧，如果是则不与此三角形相交
& && &&&//
& && &&&float dEnd = triPlane.getDistance(end);
& && &&&if( dEnd & radius)
& && && && &return FALSE;
& && &&&// Calculate the sphere intersection point
& && &&&sphereIntersectionPoint = start - radius *
& && &&&// Calculate the plane intersection point
& && &&&Ray r(sphereIntersectionPoint, dir);
& && &&&float planedist = r.intersectPlane(&triPlane);
& && &&&// Are we traveling away from this polygon?
& && &&&if (planedist & 0.0f)
& && && && &return FALSE;
& && &&&// Calculate the plane intersection point
& && &&&planeIntersectionPoint = sphereIntersectionPoint + planedist *
& & // 检查三角形面碰撞点是否在三角形内部
& & BOOL bIntersectionPointInTriangle = pointInTriangle(planeIntersectionPoint, v0, v1, v2);
& & if(bIntersectionPointInTriangle)
& && &&&if(!embedInPlane)
& && && && &dist = (planeIntersectionPoint - sphereIntersectionPoint).length();
& && && && &pos = start + dist *
& && && && &normal = (pos - planeIntersectionPoint).normalize();
& && && && &return TRUE;
& && &&&else
& && && && &dist = 0;
& && && && &pos =
& && && && &normal =& && && && &
& && && && &return TRUE;
& && &&&float t = 999999;
& && &&&BOOL bIntersect = FALSE;
& && &&&// 检测三个顶点是否和球体相交
& && &&&bIntersect |= sphereIntersectPoint(v0, start, end, radius, t, polygonIntersectionPoint);
& && &&&bIntersect |= sphereIntersectPoint(v1, start, end, radius, t, polygonIntersectionPoint);
& && &&&bIntersect |= sphereIntersectPoint(v2, start, end, radius, t, polygonIntersectionPoint);
& && &&&// 三条边是否和球体相交
& && &&&bIntersect |= sphereIntersectEdge(v0, v1, start, end, radius, t, polygonIntersectionPoint);
& && &&&bIntersect |= sphereIntersectEdge(v1, v2, start, end, radius, t, polygonIntersectionPoint);
& && &&&bIntersect |= sphereIntersectEdge(v2, v0, start, end, radius, t, polygonIntersectionPoint);
& && &&&if(bIntersect)
& && && && &dist = t * ( (end - start).length() );& &
& && && && &pos = start + dist *
& && && && &normal = (pos - polygonIntersectionPoint&&).normalize();
& && && && &return TRUE;
& & return FALSE;
好了，总算完成了，看到了么，静态检测一个非常简单的测试算法，改成连续碰撞检测会有多麻烦，这就是为什么大多数物理引擎都采用静态碰撞检则的原因，当然这种检测不
不用过于担心其效率，因为大多数计算在发现球体根本不和三形形平面相撞时已经不再进行下面的复杂计算了，这个算法是逐级深入检测，也即是在最坏的情况下，从平面检测
一直到检测完所有顶点和线段 ．而这种情况并不常见．所以不用过于担心这个函数的调用开销．
　　　至于还有什么不明白的可以搜索上面的文档，慢慢研究.
Re:球体与三角形的连续碰撞检测实现方法
连续性碰撞检测的确挺麻烦的。我觉得给三角形生成一个包围球，先做俩球的运动碰撞检测，之后再做精确检测，这样也行。
Re: 球体与三角形的连续碰撞检测实现方法
Re:连续性碰撞检测的确挺麻烦的。我觉得给三角形生成一个包围球，先做俩球的运动碰撞检测，之后再做精确检测，这样也行。
可行, 应该还有不少可以优化的方法.
提示: 作者被禁止或删除 内容自动屏蔽
Re:球体与三角形的连续碰撞检测实现方法
Re : niexuchina 我们的凸多边形是以顶点列表的形式表示的。扩大多边形的目的...
通过将待检测多边形按圆半径扩展目的就是将圆的检测转化为线段与多边形的检测，这种方法用的比较多，读过你的文章，我觉的你的方法正确。开始时我也是想通过扩展多边形的办法来做，但是发现在3D中球体与多边形相交的情况要复杂，当时我是拿球比照房间的墙角各处，不断分析各种相交的情况，发现这种方法在处理3D中的碰撞要考虑的情况复杂，后来从我上面写的文章里找到的新的将球体碰撞测试转化为射线碰撞测试的方法感觉非常好，其算法就是先找到待检测碰撞的两个物体的碰撞点(如果存在这样的碰撞点的话), 然后将球体的碰撞点作为起始点，原来的运动方向作为新的运动方向，这样会形成
一个用作碰撞测试的射线。。。单片机、电路板
连接器、接插件
其他元器件
碰撞检测技术在视景仿真中的解决方案
碰撞检测技术在视景仿真中的解决方案
视景仿真（VisualSimulation）是一种基于可计算信息的沉浸式交互环境，具体地说，就是采用以计算机技术为核心的现代高科技生成逼真的视、听、触觉一体化的特定范围的虚拟环境，用户借助必要的设备以自然的方式与虚拟环境中的对象进行交互作用、相互影响，从而产生"沉浸"于等同真实环境的感受和体验。其作为计算机技术中最为前沿的应用领域之一，它已经广泛应用于虚拟现实、模拟驾驶、场景再现、城市规划及其它应
视景仿真（VisualSimulation）是一种基于可计算信息的沉浸式交互环境，具体地说，就是采用以计算机技术为核心的现代高科技生成逼真的视、听、触觉一体化的特定范围的虚拟环境，用户借助必要的设备以自然的方式与虚拟环境中的对象进行交互作用、相互影响，从而产生"沉浸"于等同真实环境的感受和体验。其作为计算机技术中最为前沿的应用领域之一，它已经广泛应用于虚拟现实、模拟驾驶、场景再现、城市规划及其它应用领域。在众多的视景仿真应用中，碰撞检测及其相关问题是最基本也是最重要的组成部分。实时、精确的碰撞检测技术对于提高虚拟环境的真实性，增强虚拟环境的沉浸感起着至关重要的作用。本文通过改进的轴向包围盒碰撞检测算法，对业界广泛使用的视景仿真开发平台VEGA的碰撞检测部分进行了改进。改进后的系统不仅显着提高了碰撞检测的速度，并且可以便捷地得到更为详细的碰撞检测信息，满足了进一步进行碰撞响应处理的需要。1 VEGA软件及其碰撞功能简介Vega是MultiGen-Paradigm公司最主要的工业软件环境，用于实时视觉模拟、虚拟现实和普通视觉应用。Vega将先进的模拟功能和易用工具相结合，对于复杂的应用，能够提供便捷的创建、编辑和驱动工具。Vega能显着地提高工作效率，同时大幅度减少源代码开发时间。Paradigm还提供和Vega紧密结合的特殊应用模块，这些模块使Vega很容易满足特殊模拟要求，例如航海、红外线、雷达、高级照明系统、动画人物、大面积地形数据库管理、CAD数据输入和DIS分布应用等等。Vega对于程序员和非程序员都是称心如意的。其中VOLUME方法用于用户指定的体与目标场景的碰撞检测；Z、HAT、ZPR、TRIPOD方法用于高程查询（功能略有不同）；XYZHPR方法用于非平面地球坐标系交点及姿态计算；LOS方法用于射线交点和距离查询；BUMP方法可以用于物体间的碰撞检测计算。BUMP定义了一个由六条线段组成的Segment类型内部体，沿物体体坐标系的X、Y、Z三个坐标轴正负六个方向延伸，长度受参数Width、Length、Height控制。如果其中的线段与其他物体相交，则BUMP方法将碰撞结果保存于result[24]的浮点数组中，按照固定格式，从中仅可以提取三个轴向的碰撞点坐标和物体相应轴向长度的碰撞信息。而且BUMP方法非常消耗系统资源，以两个由3 072个三角形组成的物体相交测试为例，BUMP方法的平均检测时间多达6ms.在大多数需要进一步进行碰撞响应处理的仿真应用中，要求得到一些基本的碰撞部位的几何信息（点、面等），进而对这些碰撞部位进行处理或保存试验结果进行分析，如物体变形、确定破片散布等。而BUMP方法以及VEGA提供的其他检测方式都不能满足这些要求。2 碰撞检测系统设计几何模型间的碰撞检测算法大致可分为空间分解法和层次包围盒两类。层次包围盒的方法应用较为广泛，适用于复杂环境的物体间碰撞检测。其基本思想是通过体积略大而几何特征简单的包围盒来近似表示复杂的几何对象，从而减少基本几何元素（通常是三角形）两两相交的测试数目，提高碰撞检测的效率。基于层次包围盒的碰撞检测算法的性能可以使用公式（1）进行评估：目前常用的包围盒类型有包围球（SPHERE）、轴对齐包围盒（AABB）、方向包围盒（OBB）和离散有向多面体（K-DOP）。包围球由于紧密性差，基本很少使用。OBB和K-DOP（最佳为K=18）具有较好的拟合效果，相交测试速度快，但需要较多的存储空间，构造和更新包围体都比较慢。轴对齐包围盒（AABB）虽然对几何体的拟合效果和相交测试速度不如OBB和K-DOP,但其在构造、所需存储空间、AABB间的相交测试和包围体的更新速度方面都比其他算法效率高，因此也是使用最为广泛的碰撞算法，尤其适用于多物体运动的大规模环境。特别是对于需要动态创建包围树的情况，构建时间成为重要因素。2.1算法描述轴向包围盒定义：包含给定几何体且边平行于坐标轴的最小正六面体。轴向包围盒的构造：采用递归的方式分别计算几何体中各元素顶点x,y,z的最大值和最小值，即可构造出该几何体的层次包围体。轴向包围盒的相交测试：两个AABB相交当且仅当它们在三个坐标轴上的投影分别重叠。根据AABB定义的六个最大值和最小值在三个轴向的投影，其两个子树节点最多仅需六次比较运算。伪代码如下：AABB_intersect（A,B）for each i∈{X,Y,Z}if（aimin&bimax or bimin&aimax）轴向包围盒的旋转和更新：根据AABB定义的六个最大值和最小值进行组合，对得到的八个顶点进行相应旋转后，选出最大值和最小值即可。而AABB节点的更新也远比其他算法简单，当几何体对象发生变形后，对变形叶节点部分自底向上重新选择最大值和最小值，仅需六次比较运算即可完成一个节点的更新。2.2 算法改进（1）AABB树由2×N-1个节点组成，其中N是几何体中基本图元（通常是三角形）的数目。完全AABB树有N个叶节点和N-1个内部节点，每一个叶节点包含一个指向基本图元的指针和包围基本图元的包围体。在进行碰撞检测时，遇到测试两个叶节点的情况，需要首先进行包围体间（BV/BV）的相交测试。如果包围体相交测试成立，则可进行基本图元的相交测试，确定精确位置。改进算法的基本思想是舍弃AABB树的叶节点，即无需进行包围体间的相交测试，直接进行基本图元间的测试。因为如果基本图元相交，则包围体间的相交测试就可以省略；如果基本图元不相交，则改进所付出的代价就是测试包围体比测试基本图元节省的时间。由于AABB树没有叶节点，由更精确的基本图元（三角形）与包围体间的相交测试取代较粗糙的包围体间的测试，使得总体上进行相交测试的次数减少。碰撞检测查询伪代码如下：程序中三角形和AABB的重叠检测采用Akenine-Moler的算法。该算法基于分离轴定理，对13条轴线进行测试，即AABB的三条法线。三角形的法线n,aij=ei×fj,i,j∈{0,1,2},其中ei为AABB的三条法线，fj为三角形边向量。三角形与三角形的相交测试使用经典ERIT算法，这两种算法在参考文献[1]中有详细描述。完整的AABB树有2×N-1个节点，现在省略了N个叶节点，仅需N-1个节点，节省了大量的存储空间。在许多视景仿真应用中，一个场景可能存在许多复杂物体，从而占用大量系统内存，导致系统性能下降。与OBB和K-dop算法相比，改进的AABB算法节省了近70%的存储空间，显着改善了系统效率。（2）虚拟环境中可能包含成百上千个运动物体。如果场景中包含N个运动物体和M个固定物体，则穷举的处理方法需要执行的碰撞测试次数为：。显然，其中包含了大量无效测试。随着N和M数量的增加，计算的开销会越来越大。为了尽可能减少进行碰撞检测的物体对数量，本文采用扫描-修剪算法进行筛选处理。扫描-修剪算法利用虚拟环境中的时间相关性，即两幅连续画面之间物体的位置与方向变化较小，通过动态分离轴测试方法，计算可能发生碰撞的物体对，减少进行碰撞检测的次数。其基本原理是：如果两个物体重叠，则它们在三个主轴方向上的所有一维时间间隔必定也相互重叠。假设Si、Ei分别表示在某主轴（X,Y,Z）上的一定时间间隔，Ii表示物体i在此时间间隔[Si,Ei]内投影到主轴上的运动区间。将[Si,Ei]存入一个排序列表中，然后对此列表进行扫描，当遇到起始点Si时，将其相应的时间间隔放入一个活动列表；当遇到结束点Ei时，将相应的时间间隔从活动列表中清除。如果在活动列表中存在多个时间间隔事件，则它们一定重叠。如图1所示：当S2进入活动列表后，S3进入，当遇到E2结束点时，S3仍然在活动列表中，因此可以确定，此刻物体运动区间I2、I3在该主轴上发生重叠。考虑到随后进行的碰撞检测调用中包围盒测试也使用投影方式确定是否重叠，因此在算法程序实现上只需要在X、Y轴上进行排序和投影。在精确碰撞检测的包围盒测试中则先对Z轴投影，这样可以省略在一个主轴方向上的投影和排序，提高算法的效率。3 VEGA程序中轴向包围盒（AABB）的建立构造AABB树，必须获得几何模型的点、面信息。VEGA开发环境下是以OpenFlight文件加载模型的。因此，可以根据已经公开的Flt文件格式，通过直接读取Flt文件获得几何模型信息，进而构建包围树。但是这种方式速度较慢，只能在程序初始化时加载所有需要精确碰撞检测的模型，这极大地影响了程序的灵活性。本文提供一种方式，可以在程序中根据需要动态获取模型几何信息。由于封装的原因，VEGA没有直接提供访问基本几何元素（三角形）的功能，但是VEGA是在SGI Performer基础上发展起来的，可以通过嵌入Performer函数调用，获取所需信息。如果处理时间允许，也可以对模型进行修改。（1）通过调用vgGetObjPfNode（VgObj?鄢obj）获得物体的Pfnode句柄。（2）遍历Pfnode子树，利用pfIsOfType（pfnode,pfGetGeodeClassType（ ））得到pfGeode节点。（3）在Performer中，模型的点、面存储于pfGeoSet节点。调用pfGetGSet（ ）函数可以得到pfGeoSet句柄。（4）调用函数pfGetGSetAttrLists（ ）获得模型的点信息列表。通过pfGetGSetPrimType（ ）确定列表信息的存储顺序。可以使用pfGSetAttr（ ）修改几何模型。基本代码如下：由于这种方式是在程序中动态读取场景中模型信息，所以读取时间将直接影响显示的帧频。一般情况下，正常显示所需的刷新频率在25帧/秒以上，VEGA平台下开发的程序帧频因场景及物体复杂度的不同而变化。以一个由7万多个三角形、132个物体组成的场景为例，稳定的帧频在19.0ms至20.3ms之间。经过多组试验比对，这种在程序中动态读取场景模型信息的方式，通常情况下不会超过2ms.如表1数据所示，比较复杂的模型（模型3和模型4）的读取时间都小于2ms,且独立部件越多，时间越长。如果模型过于复杂，可以考虑在程序初始化时加载。当然，CREATOR不提倡通过增加模型复杂度的方式达到提高逼真度的效果。正确的建模方式应该是对纹理技术、LOD以及BILLBORD技术合理搭配地运用，使模型尽量具有真实感，进而达到在视景驱动时减少内存使用、提高渲染速度的目的。4 实验结果及分析实验运行环境为：CPU主频--AMD2400+,内存--1GB DDR,显卡--128MB,VEGA版本为3.7.首先对VEGA的Bump算法进行测试，为了屏蔽地形及场景等其他因素对实验结果的影响，场景中只放置三个运动物体（三角形数：3 072），结果如表2.由实验数据分析可知：Bump方法没有进行优化处理，所以无论是否发生碰撞，所需的检测时间几乎相同，因而非常耗费系统资源。对于相同场景，采用轴向包围盒方法对两个运动物体进行检测，结果如图2.其峰值检测时间仅为0.4ms,平均检测时间为0.063ms.对于多物体的情况，采用扫描-修剪算法对运动物体进行排序后再进行检测，所需时间也有显着减少。通过上述数据对比可以证明，在VEGA下使用改进AABB算法处理物体间碰撞处理可以极大地缩短检测时间，系统性能也获得了显着提高。碰撞检测是视景仿真软件最重要的组成部分。本文就VEGA软件中关于物体间碰撞检测算法进行改进，将其应用于车辆碰撞仿真试验、某武器系统杀伤效果评估等项目，均取得了良好的效果。必须说明，由于仿真场景的高度复杂性和仿真要求的不同，处理场景中物体间碰撞的方式也不尽相同，许多情况下需要多种方法结合使用。因此，灵活地选取不同碰撞算法组合，才能取得较好的仿真效果。同时，本文提供了一种在VEGA环境下调用Performer访问、修改场景中物体三维模型的方法，对于希望在VEGA下进行底层操作的开发者具有一定的借鉴意义。参考文献:[1].VEGAdatasheethttp://www.dzsc.com/datasheet/VEGA_1117503.html.[2].N-1datasheethttp://www.dzsc.com/datasheet/N-1_1997158.html.[3].Fltdatasheethttp://www.dzsc.com/datasheet/Flt_329018.html.
型号/产品名
阳光在线私网|阳光在线黑网
阳光在线私网|阳光在线黑网
阳光在线私网|阳光在线黑网
阳光在线私网|阳光在线黑网