碰撞检测经典解决方案

碰撞检测在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 collision detection）。离散点的碰撞检测是指定某一时刻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到多边形的最短距离，如果该距离如图这里以一个三角形为例子，左图中该三角形的所有点到线段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是要描的级数(等下会解释到),我们先可以先看下里面的逐句解释

function doFigure(pmc, num) {

// 为pmc建立一个数组,数组的大小是num*2;

pmc.point = new Array(num*2); // 从pmc的长和宽中取大的,然后除以2 var mx = Math.max(pmc._width, pmc._height)/2;

// 把360℃num等分 var inc = 360/num; // 定义两个变量等下用

var n = 0; var i = 0;

// while循环的次数为 iwhile (i<(num*2)) {

// 从下面n+=inc知道 xs和ys 就是每一个等分上x和y的所指的方向

var xs = Math.cos((n*Math.PI)/180); var ys = Math.sin((n*Math.PI)/180);

// 以pmc的(x,y)点为定点,半径为mx的一个圆的轨迹

var x = pmc._x+(mx*xs); var y = pmc._y+(mx*ys);

// 如果x,y没有接触到pmc上,不断循环

while (!pmc.hitTest(x, y, true)) {

// x,y分别减 x -= xs; y -= ys;

// 如果都小于0,就break跳出循环

if (x<0 && y<0) {

break;

} }

// 把此时的x和y,分别计入point数组中

pmc.point[i] = x-pmc._x; pmc.point[i+1] = y-pmc._y;

n += inc; i += 2; } }

他这么做到底什么意思呢?

其实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.

其实这只是一个大概的数据,并不是百分百的描边,不过这样已经够用了^^\"

onClipEvent (load) {

numb = 100;

_root.doFigure(_name, numb);

}

onClipEvent (enterFrame) {

_root.hit = false;

i = 0;

while (i < (numb * 2)) { x = points[i] + _x; y = points[i + 1] + _y; if (_root.mc2.hitTest(x, y, true)) {

_root.hit = true;

break; } i = i + 2;

} }

onClipEvent (mouseDown) {

if (this.hitTest(_root._xmouse, _root._ymouse, true)) {

this.startDrag();

} }

onClipEvent (mouseUp) {

this.stopDrag();

}

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

转】MSDN中关于OnDrawItem的说明

afx_msg void OnDrawItem( int nIDCtl, LPDRAWITEMSTRUCT lpDrawItemStruct ); 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) 0); }

// 球体－平面的碰撞 Sphere-Plane Collision bool IsCollidingSphereToPlane() { // 提前跳过测试：检查小球是否可以在没有碰撞的情况下移动， // 如果可以，则返回false；

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

re

{

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)

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中目前只有行走动画，没有起跳，下落等动画。。）

算法是程序设计的精髓，程序设计的实质就是构造解决问题的算法，将其解释为计算机语言。

算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说，就是计算机解题的过程。在这个过程中，无论是形成解题思路还是编写程序，都是在实施某种算法。前者是推理实现的算法，后者是操作实现的算法。

一个算法应该具有以下五个重要的特征：

有穷性： 一个算法必须保证执行有限步之后结束； 确切性： 算法的每一步骤必须有确切的定义；

输入：一个算法有0个或多个输入，以刻画运算对象的初始情况；

输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的； 可行性： 算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。

动态规划-航线设置

问题描述:美丽的莱茵河畔,每边都分布着N个城市,两边的城市都是唯一对应的友好城市,现需要在友好城市开通航线以加强往来.但因为莱茵河常年大雾,如果开设的航线发生交叉现象就有可能出现碰船的现象.现在要求近可能多地开通航线并且使航线不能相交!

假如你是一个才华横溢的设计师,该如何设置友好城市间的航线使的航线数又最大又不相交呢?

分析:此问题可以演化成求最大不下降序列来完成.源程序如下:

program dongtai; {动态规划之友好城市航线设置问题} var

d:array[1..1000,1..4] of integer; i,j,k,n,L,p:integer;

procedure print(L:integer); {打印结果} begin

writeLn('最多可设置的航线数是 : ',k); repeat

writeLn(d[L,1]:4,d[L,2]:4); {输出可以设置航线的友好城市代码} L:=d[L,4] untiL L=0 end; begin

writeLn('输入友好城市对数: '); readLn(n);

writeLn('输入友好城市对（友好城市放在同一行:'); {输入} for i:=1 to n do

readLn(d[i,1],d[i,2]); {D[I，1]表示起点，D[I，2]表示终点} for i:=1 to n do begin

d[i,3]:=1; {D[I，3]表示可以设置的航线条数}

d[i,4]:=0 {D[I，4]表示后继，即下一条航线从哪里开始设置，为0表示不能设置下一条航线} end;

for i:=n-1 downto 1 do {从倒数第二个城市开始规划} begin

L:=0; p:=0; {L表示本城市后面可以设置的航线数，P表示下条航线从哪个城市开始}

for j:=i+1 to n do {找出本城市后面可以设置的最大航线数和小条航线到底从哪个城市开始设置} if (d[i,2] L) then

{如果本城市I的终点小于后面城市的终点（即不相交）} {并且此城市后面可以设置的航线数大于L} begin

L:=d[j,3]; {那么L等于城市J的可以设置航线数} p:=j {P等于可以设置下条航线的城市代码} end;

if L>0 then {如果本城市后面总共可以设置的航线数>0则} begin

d[i,3]:=L+1; {本城市可以设置的航线数在下个城市可以设置航线数的基础上加1} d[i,4]:=p {D[I，4]等于本城市后续城市的代码} end end;

k:=d[1,3]; {K为可以设置最大航线数，假设初值为第一个城市可以设置的航线数} L:=1; {L为城市代码，初值为第一个城市}

for i:=2 to n do {找出可以设置航线的最大值，赋值给K，同时L记下哪个可以设置最大航线数的城市代码} if d[i,3]>k then begin k:=d[i,3]; L:=i end;

for i:=1 to n do {打印结果，因为有可能有多种方案，所以只要哪个城市可以设置的航线数等于最大值K就打印结果}

if d[i,3]=k then print(i) end.

归并排序算法

合并排序（MERGE SORT）是又一类不同的排序方法，合并的含义就是将两个或两个以上的有序数据序列合并成一个新的有序数据序列，因此它又叫归并算法。它的基本思想就是假设数组A有N个元素，那么可以看成数组A是又N个有序的子序列组成，每个子序列的长度为1，然后再两两合并，得到了一个 N/2 个长度为2或1的有序子序列，再两两合并，如此重复，值得得到一个长度为N的有序数据序列为止，这种排序方法称为2—路合并排序。

例如数组A有7个数据，分别是： 49 38 65 97 76 13 27，那么采用归并排序算法的操作过程如图7所示：

初始值 [49] [38] [65] [97] [76] [13] [27]

看成由长度为1的7个子序列组成

第一次合并之后 [38 49] [65 97] [13 76] [27]

看成由长度为1或2的4个子序列组成

第二次合并之后 [38 49 65 97] [13 27 76]

看成由长度为4或3的2个子序列组成

第三次合并之后 [13 27 38 49 65 76 97]

图6 归并排序算法过程图

合并算法的核心操作就是将一维数组中前后相邻的两个两个有序序列合并成一个有序序列。合并算法也可以采用递归算法来实现，形式上较为简单,但实用性很差。

合并算法的合并次数是一个非常重要的量,根据计算当数组中有3到4个元素时,合并次数

是2次,当有5到8个元素时,合并次数是3次,当有9到16个元素时,合并次数是4次，按照这一 X

规律,当有N个子序列时可以推断出合并的次数是X(2 >=N,符合此条件的最小那个X)。 源程序：

program hebing; const n=10; var

a:array[1..n] of integer; i:integer;

procedure init; var i:integer; begin

for i:=1 to n do read(a[i]);

readln; end;

procedure merge(low,mid,high:integer); var

h,i,j,k:integer; b:array[1..n] of integer; begin

h:=low; i:=low; j:=mid+1; while (h<=mid) and (j<=high) do begin

if (a[h]<=a[j]) then begin

b[i]:=a[h]; h:=h+1; end else begin

b[i]:=a[j]; j:=j+1; end; i:=i+1; end; if h>mid then for k:=j to high do begin

b[i]:=a[k]; i:=i+1; end else

for k:=h to mid do begin

b[i]:=a[k]; i:=i+1; end;

for k:=low to high do a[k]:=b[k]; end;

procedure mergesort(low,high:integer); var mid:integer; begin if low begin

mid:=(low+high) div 2; mergesort(low,mid); mergesort(mid+1,high); merge(low,mid,high); end; end; 枚举法

有4个学生，上地理课时提出我国四大谈水湖的排列次序如下：

甲：洞庭湖最大，洪泽湖最小，鄱阳湖第三；

乙：洪泽湖最大，洞庭湖最小，鄱阳湖第二，太湖第三；

丙：洪泽湖最小，洞庭湖第三；

丁：鄱阳湖最大，太湖最小，洪泽湖第二，洞庭湖第三；

对于各湖泊应处的位置，每个人只说对了一个。根据以上描述和条件，编写程序，让计算机判断一下各湖泊应该处于第几位。

解题思路：设置洞庭湖、洪泽湖、鄱阳湖、太湖分别用字母A、B、C、D代表，最大到最小依次用数字4——1表示。应用枚举法可以解决此问题，不过稍微复杂罗嗦点。

源程序如下：

program hupo; var

a,b,c,d:integer; begin

for b:=1 to 4 do for a:=1 to 4 do

if ((b=1) and (a<>2)) or ((a=2) and (b<>1)) then if a<>b then for c:=1 to 4 do if (a<>c) and (b<>c) then

if (a+b+c<>7) and (a+b<>5) and (a+c<>6) and (b+c<>3) then for d:=1 to 4 do if c<>d then

if (b+a<>5) and (b+c<>7) and (b+d<>6) then if (a+c<>4) and (a+d<>3) and (c+d<>5) then if (c+d<>5) and (c+b<>7) and (c+a<>6) then if (d+b<>4) and (d+a<>3) and (b+a<>5) then writeln('a=',a,' b=',b,' c=',c,' d=',d)

end.

改进程序：

program ygzj; var

a,b,c,d:integer; begin for a:=1 to 4 do for b:=1 to 4 do for c:=1 to 4 do begin d:=10-a-b-c;

if ord(a=1)+ord(b=4)+ord(c=3)=1 then

if ord(b=1)+ord(a=4)+ord(c=2)+ord(d=3)=1 then if ord(b=4)+ord(a=3)=1 then

if ord(c=1)+ord(d=4)+ord(b=2)+ord(a=3)=1 then if a*b*c*d=24 then

writeln('洞庭湖第':3,a:3,'洪泽湖第':3,b:3,'波阳湖第':3,c:3,'太湖第':3,d:3); end; writeln end.

数字全排列问题：

任意给出从1到N的N个连续的自然数，求出这N个自然数的各种全排列。如N=3时，共有以下6种排列方式：

123，132，213，231，312，321。

注意：数字不能重复，N由键盘输入（N<=9）。

解题思路：

应用回溯法，每个数的取法都有N个方向（1——N），当取够N个数时，输出一个排列，然后退后一步，取前一个数的下一个方向（即前一个数+1），并且要保证所有数字不能重复。当前数字的所有方向都取完时，继续退一步，一直重复到第一个数为止。

程序代码：

program quanpailie; {数字全排列问题} var

a:array[1..9] of integer; k,x,n:integer;

function panduan(j,h:integer):boolean; {判断当前数字是否能赋值给当前数组元素} var m:integer; begin panduan:=true; for m:=1 to h-1 do

if a[m]=j then panduan:=false {如果当前数字与前面的数组元素相同则不能赋值} end;

procedure try(h:integer); var i,j,m:integer; begin for j:=1 to n do if panduan(j,h) then

begin

a[h]:=j; {能够赋值，且长度k加一} k:=k+1;

if k=n then {如果长度达到N则表示一种组合已经完成，输出结果} begin

for m:=1 to n do write(a[m]); write('':4);

x:=x+1; {每输出一种排列方式加一}

if x mod 5=0 then writeln; {每行输出5种排列方案} end else

try(h+1); {对下一个数组元素进行赋值} k:=k-1 {回溯的时候一定要把长度减一} end end; begin

writeln('输入 N:'); readln(n);

k:=0; {k表示长度，长度初始值为0} x:=0; {x表示总的排列方式} try(1); {对第一个数组元素赋值} writeln('共有 ', x ,' 种排列方案') end.

Dijkstra最短路径（一点到各顶点最短路径）

{本程序解决6个顶点之间的最短路径问题,各顶点间关系的数据文件在sj.txt中}

{如果顶点I到顶点J不能直达就设置距离为30000} program dijkstra; type

jihe=set of 0..5; var

a:array[0..5,0..5] of integer; dist:array[0..5] of integer; i,j,k,m,n:integer; fv:text; s:jihe; begin s:=[0];

assign(fv,'sj.txt'); reset(fv);

for i:=0 to 5 do {从文件中读数据,其中a[i,j]代表从顶点i到顶点j的直达距离,如果不通用30000代替} begin

for j:=0 to 5 do read(fv,a[i,j]); readln(fv) end;

for i:=1 to 5 do {设置DIST数组的初始值,即为顶点0到各顶点的直达距离(算法的第一步)} dist[i]:=a[0,i]; for i:=1 to 5 do begin m:=0;

dist[m]:=30000; {设置DIST[M]的目的是为下面的一步做准备,即在DIST数组中一个最小的值}

for j:=1 to 5 do {算法的第二步,找最小的DIST值} if (not (j in s)) and (dist[m]>dist[j]) then m:=j ; {用M来记录到底是哪个顶点} s:=s+[m]; {把顶点加入S中}

for k:=1 to 5 do {算法的第三步,修改后面的DIST值} if (not (k in s)) and (dist[k]>dist[m]+a[m,k]) then

dist[k]:=dist[m]+a[m,k] end;

writeln('原各顶点间的路径关系是：（30000代表不通）'); for i:=0 to 5 do begin

for j:=0 to 5 do write(a[i,j]:6); writeln end;

writeln; writeln;

八皇后问题

{问题描述：在国际象棋8X8的棋盘里摆放8个皇后，使每个皇后都能生存而不互相冲突，即同一行、同一列同对角线（包括主对角线和辅对角线）都只能有一个皇后}

program eightqueen; {本程序可以搜索出所有的解} var

a,b:array[1..8] of integer; c:array[-7..7] of integer; d:array[2..16] of integer;

i,k:integer; {K变量用来存放答案的个数} fv:text;

procedure print; var

i:integer; begin for i:=1 to 8 do

writeln(fv,'第',i:2, '行放在第', a[i]:2,'列'); {结果输出到文件里} k:=k+1; {每输出一个答案计数加1} writeln(fv) end;

procedure try(i:integer); var j:integer; begin for j:=1 to 8 do

if (b[j]=0) and (c[i-j]=0) and (d[i+j]=0) then begin a[i]:=j;

b[j]:=1; {宣布占领列、主副对角线} c[i-j]:=1; d[i+j]:=1;

if i<8 then try(i+1) else print; b[j]:=0; {释放占领列、主副对角线} c[i-j]:=0; d[i+j]:=0 end end; begin

for i:=1 to 8 do a[i]:=0; for i:=-7 to 7 do c[i]:=0; for i:=2 to 16 do d[i]:=0;

k:=0;

assign(fv,'jieguo.txt'); {指定文件与文件变量相联系} rewrite(fv); {以写的方式打开文件} try(1);

close(fv); {一定要记得关闭文件，不然数据有可能丢失} writeln('共有 ',k:3,' 种摆法') end.

快速排序算法

program kuaisu(input,output); const n=10; var

s:array[1..10] of integer; k,l,m:integer;

procedure qsort(lx,rx:integer); var I,j,t:integer; Begin I:lx;j:rx;t:s[I]; Repeat

While (s[j]>t) and (j>I) do Begin k:=k+1; j:=j-1 end; if I begin

s[I]:=s[j];I:=I+1;l:=l+1; while (s[I] begin k:=k+1; I:=I+1 End; If I begin

S[j]:=s[I];j:=j-1;l:=l+1; End; End; Until I=j;

S[I]:=t;I:=I+1;j:=j-1;l:=l+1; If lx If I

End;{过程qsort结束} Begin

Writeln('input 10 integer num:'); For m:=1 to n do read(s[m]); K:=0;l:=0; Qsort(l,n);

Writeln('排序后结果是：')； For m:=1 to n do write(s[m]:4) End.

地图四色问题

{问题描述：任何一张地图只要用四种颜色进行填涂，就可以保证相邻省份不同色}

program tt; const num=20;

var a:array [1..num,1..num] of 0..1;

s:array [1..num] of 0..4; {用1-4分别代表RBWY四种颜色;0代表末填进任何颜色} k1,k2,n:integer;

function pd(i,j:integer):boolean;{判断可行性：第I个省填上第J种颜色} var k:integer; begin

for k:=1 to i-1 do {一直从第一个省开始进行比较一直到I省减一的那个省，目的是对已经着色的省份来进行比较，因为>I的省还没 有着色，比较没有意义，着色的顺序是先第一、二、三……I个省} if (a[i,k]=1) and (j=s[k]) then {省I和省J相邻且将填进的颜色和已有的颜色相同} begin

pd:=false; {即不能进行着色} exit; {退出当前函数} end;

pd:=true; {可以进行着色} end;

procedure print;{打印结果} var k:integer; begin

for k:=1 to n do{将数字转为RBWY串} case s[k] of 1:write('R':4); 2:write('B':4); 3:write('W':4); 4:write('Y':4); end; writeln; end;

procedure try(i:integer); var j:integer; begin for j:=1 to 4 do if pd(i,j) then begin s[i]:=j; if i=n then print

else try(i+1); {对下一个省进行着色}

s[i]:=0; {不能进行着色，将当前状态设置0，即不进行着色} end; end; BEGIN

write('please input city number: '); readln(n); writeln('please input the relation of the cities:'); for k1:=1 to n do begin

for k2:=1 to n do read(a[k1,k2]); {A[K1，K2]=1表示省K1、K2相邻，为0就不相邻} readln; end;

for k1:=1 to n do s[k1]:=0; {把所有的颜色设置为0，即还没有进行着色} try(1); END. 穿越迷宫

{本程序假设迷宫是一个4 X 4的矩阵，入口在A[1，1]，出口在A[4，4]}

{矩阵数据放在文件shuju3.txt 中} program mikong; var

a,b,c:array[1..4,1..4] of integer; {数组A用来存放迷宫路径，约定元素值为0表示通，1表示不通} {数组B用来存放方向增量}

{数组C用来记录结果，当第I步移到某一元素时，该元素就等于I} i,j,k,m,n:integer; fv:text;

q:boolean; {用来标记迷宫是否有出路}

procedure print; var m,n:integer; begin

q:=true; {如果打印步骤，表示肯定有出路} writeln; writeln;

writeln('穿越迷宫的步骤是：'); for m:=1 to 4 do begin

for n:=1 to 4 do write(c[m,n]:4); writeln; end end;

procedure try(x,y,i:integer); var u,v,k:integer; begin

for k:=1 to 4 do {可以有4个方向选择} begin

u:=x+b[k,1]; {当前坐标加上方向增量} v:=y+b[k,2];

if (u>=1) and (u<=4) and (v>=1) and (v<=4) then {判断是否越界}

if (a[u,v]=0) and (c[u,v]=0) then {判断是否为0，为0就表示通，为1就表示不通} begin

if (x=2) and (y=3) then writeln('aaaaaaaaaaaa');

c[u,v]:=i; {数组 C打上记号，表示此元素是第I步到达} if (u<>4) or (v<>4) then {判断是否到出口} try(u,v,i+1) {没有就继续走} else print;

c[u,v]:=0 {下一路所有方向都不通，清除本次所做的标记} end end end; begin

assign(fv,'shuju3.txt'); reset(fv); for i:=1 to 4 do begin for j:=1 to 4 do read(fv,a[i,j]); readln(fv) end;

b[1,1]:=-1; b[1,2]:=0; b[2,1]:=0; b[2,2]:=1;

b[3,1]:=1; b[3,2]:=0; b[4,1]:=0; b[4,2]:=-1; close(fv);

for i:=1 to 4 do {首先标记数组C所有元素全部为0} for j:=1 to 4 do c[i,j]:=0; c[1,1]:=1;

for i:=1 to 4 do {显示迷宫具体线路，0表示通，1表示不通} begin for j:=1 to 4 do write(a[i,j]:4); writeln end;

q:=false; {假设迷宫没有出路} try(1,1,2);

if q=false then writeln( '此迷宫没有出路') end.

项目管理就是指把各种系统、方法和人员结合在一起，在规定的时间、预算和质量目标范围内完成项目的各项工作，有效的项目管理是指 在规定用来实现具体目标和指标的时间内，对组织机构资源进行计划、引导和控制工作。

项目管理包括范围、成本、质量、资源、沟通、风险、采购、集成等一系列管理。但是日常的实践中争论的焦点往往是采用什么方法来管理，我的项目管理符合某某体系标准，我采用了什么先进的工具……，一个问题被忽视了，那就是人的问题。

项目管理的核心是人：

人是进行项目管理中最大的变数。不同的人有着不同的背景知识和特长，不同的处事和思考方法，不同的价值观，甚至采用不同的语言进行沟通。与此同时，人也恰恰是最善于处理项目中永恒的变更的动态因素。

不妨看看过猴山的故事。

古时候有个人，过猴山的时候睡着了，山上的猴子趁着他熟睡的时候拿走了他带着贩卖的草帽，当那人醒来的时候发现草帽没了，于是心生一计，将自己戴着的草帽扔在地上，猴子跟人学，于是也把拿走的草帽都扔在地上，结果那人追回了所有的草帽。后来，当他老了的时候他把这个经验传授给了自己的孙子。有一天，他的孙子也过猴山，睡着了，山上的猴子拿走了他的草帽，于是他按照爷爷传授的经验如法炮制，结果，猴子没有跟着学，反而跳下树，把他扔在地上的草帽也拿走了。就在他纳闷的时候，一只猴子说话了，“不要以为只有你有爷爷”。

看到这里也许你会觉得好笑，但是，这个小故事却揭示了这样一个真理，世上万物都不是一成不变的。因此，总是恪守老经验、老方法是无法处理这些变化着的问题的。对于我们的软件团队所遵从的体系、方法是相对不变的；我们使用的工具也是没有生命的；唯有人是灵活的，可以因地制宜的依据实际情况作出调整的，可以灵活的使用工具的，可以灵活的选用或裁剪方法的。只是上面的笑话里面为了幽默效果，人跟猴子易位了。因此，一个好的项目经理不仅仅要懂得项目管理的那些相关领域知识，还要善于用人！

我们来看看品三国里面曹操是怎么用人的。曹操作为一个好“领导”，他的用人有着四大特点：

1、知人善任

知道那些人是人才；知道这些人是那方面的人才；知道该把这样的人才放在什么位置上；

2、为才是用，不拘小节

用人用的是他的优点和长处，不可以总是盯着人家的小毛病不放，当然，对于原则性的问题还是需要恪守底线的，不能够姑息。

3、用人不疑，海纳百川

一旦确定在某个位置上用什么人就完全的信任他，不然容易滋生上下猜忌，形成内耗，用三国里面的话讲就是“上下相疑之秋也”。

4、令行禁止，赏罚分明

处罚要严厉，奖励要到位，莫与部下争风头，虚怀若谷，若不听而失败，一定要检讨，奖励不可走过场。（当然由于国内企业的项目经理财权有限，奖励的兑现估计有难度）

做到上面这些，可以使得人心一统，成员一心协力，在应对变化的各种情况的时候也可以最大限度的发挥每个成员的主观能动性，不会出现那种项目问题被成员隐瞒、拖延、延误的问题。一旦项目组达成统一，相应的，在沟通、协作等等方面的额外开销也就大大减少。

最后，让我们看看对曹操用人的总结，时刻来检讨自己，不要忽视了人的作用。

“真心诚意，以情感人；推心置腹，以诚待人；开诚布公，以理服人；言行一致，以信取人； 令行禁止，依法治人；设身处地，以宽容人；扬人责己，以功归人；行赏，以奖励人。”

[编辑本段]

§DEMO的概述§

DEMO是demonstration的缩写，在电脑上的DEMO简单的说就是展示电脑图形与音乐的程式，所以游戏开始的动画展示也是DEMO的一种。在电脑公司，可以看到电脑上展示介绍电脑软硬件的程式，这些属于商业性质的DEMO；这些DEMO是凭借图形与音乐来吸引顾客，达到宣传的目的。

但如果只是一般DEMO那就没有什么好看的了。这里主要介绍的DEMO并非指的商业性的DEMO，而是在国际比赛，有个参赛团体专门为DEMO比赛而制作的DEMO。这些DEMO主要目的是：带给欣赏者趣味并且发挥电脑在绘图与音乐上的亲历。也就是说DEMO结合令人看到目瞪口呆的CG与音乐，再加上DEMO制作者的编程技巧与功力，展现出许多高难度的表演。有人说DEMO就是：“亲爱的，我把PC变成SGI了。”得奖的DEMO在设计时一般进行程序最优化，充分发挥PC的硬件潜力，产生惊人的效果，包括：多变的音乐，即时运算产生的RENER图形，FRACTRL，透明，PLASMA，3D VECTOR SPACE，VIRTUAL REALITY，MORPH等。 [编辑本段]

§DEMO的特性§

为了达到这些效果，这些DEMO通常有下面四个特性：

⑴ 使用汇编语言，要产生一个简单的DEMO，用高级语言可以很轻松的写出来，但因为一些速度很不理想。运用汇编语言最优化，可以充分发挥与控制软硬件的威力。

⑵ 多声道的音乐。

⑶ 突破传统的绘图能力：在PC上标准VGA在320×200的解析度只能显示256色，很少有记忆页，造成很多。而DEMO往往使用特殊的模式，通常称做X MODE，在这些模式下能达到320×200 256色多记忆页。

⑷ 即时运算：在这些DEMO里大多有3D向量空间，虚拟真实的部分，或是有许多的电脑上色效果，还有变形等。由于即时运算的关系，尽管一个DEMO不大，也可以播10-20分钟。 [编辑本段]

§DEMO的创造者§

DEMO就象编一个游戏，任何DEMO都需要有程序设计，美术人员与编曲人员。常常以DEMO团队的方式来编制DEMO。 一个DEMO团体通常包括：

⑴ 领队 ORGANIZER：统筹策划带领团队

⑵ 编程人员 CODER：设计DEMO程序,他们是Demo的核心人物，优秀的coder可以写出强大而又精巧的demo引擎，一个优秀的coder+优秀的优化编译器+UPX加壳就足够能把任意的实时图形演算程序控制在kb内了。

⑶ 作曲家 MUSICIAN：tracker/sound/music,制作音乐，不是简单的产生mp3文件那么简单，由于kb无法存储一个波形文件，此时的sound track都是通过程序实时波形演算合成而来。基本上一个成熟的团队都会写一个自己的FM发音引擎，这和8位红白机的音乐一样，好的音效师，可以利用波形合成在简单的FC游戏中产生与mp3一样的音效，而完全不懂FM合成的音效师则可能只能让团队的FM引擎发出“嘀嘀”的正弦波形

⑷ 美工 GRAPHICS ARTS：主要负责demo的构思和图片素材的建立，他在设计画面的同时，也要考虑色彩的位深、贴图的尺寸、画面的特效以便于更好的能够提升cpu和显卡的处理效率。

⑸ 其他人员：负责BBS和协助等 （和游戏开发团队很象，不是吗？）