刘亚峰

摘要：本文着重描述了核电站虚拟建造系统中相机漫游时碰撞检测、碰撞响应处理的技术实现。根据相机的初始位置、行进方向、行进步长构造射线方程，先与物体边界体进行粗的碰撞检测，有碰撞再进行与物体的各个面进行细的碰撞检测，以及碰撞发生后的响应处理。碰撞检测时，构造检测面的平面方程，根据空间几何学直线与平面的相交测试知识，与构成的射线方程进行求交，以及应用仿射射坐标系分解的方法判断交点是否在三角形内，来检测是否有碰撞发生。

关键词：碰撞检测、响应处理、帧、轴对齐包围盒、射线（直线）方程、平面方程、法向量、相交测试

中图分类号：O313.4 文献标识码：A 文章编号：

Abstract: this paper describes the nuclear power station built system of virtual camera when roaming collision detection, collision response processing technical implementation. According to the camera's initial position, moving direction, and do the progress long tectonic rays equation, first and object boundary body rough collision detection, a collision with each object again face thin collision detection, and after a collision occurs the response of the processing. Collision detection, the tectonic detection plane equation, according to dimensional geometry lines and planes intersect test of knowledge, and the composing of the ray intersection equation, and application of affine shoot coordinate system decomposition of intersection method in triangle whether judge inside, to test whether there is a collision.

Keywords: collision detection, response processing, frame, shaftalignment the bounding box, ray (linear) equation, plane equation, law vector, the intersection of the test

1、引言：

核電站虚拟建造系统，是对核电站实际建造施工过程的计算机模拟和预演,以实现施工中的事前控制和动态管理。它涉及到虚拟现实技术、仿真技术、优化技术、建模技术和核电建造信息管理技术。而在系统的具体实施中，核心问题是场景管理、碰撞检测、碰撞响应处理的实现及其优化，而实现过程预演、问题发现、场景漫游等的关键就是碰撞。在本文中，笔者主要论述了在《核电站虚拟建造系统》中碰撞检测、响应处理的技术实现。

2、系统架构

本系统采用的是典型的多层C/S架构。选择的图形库是OpenGL，以动态链接库（DLL）形式调用；开发工具为Visual C++ 6.0，基于MFC应用框架；数据库选用Oracle 9i，数据库接口为ADO。

3、设计思路

所有模型、基本场景用3D MAX进行建模，生成3DS格式文件；工程信息、管理信息、场景信息、模型信息、系统维护信息等放入数据库；建立客户端程序，完成场景生成、模型场景装入、显示、交互、漫游及图片、视频、报表等的生成、输出。

4、关键技术

系统实施中，需要处理的技术问题包括数据库访问、报表生成；3DS文件的装入、生成；场景动态生成、管理；用户交互；图片、视频生成、输出；动画生成、演示；场景实时漫游；碰撞检测、碰撞响应处理；性能优化等。在这里，只讨论其中碰撞检测、碰撞响应及其优化的技术实现。

5、碰撞检测

决定两个物体何时发生交互作用的过程称为碰撞检测，有两种典型的碰撞检测算法，其一：检测发生在一个运动物体与周围环境中静止的几何体之间的碰撞；其二：检测发生在两个都可能运动的物体之间的碰撞。

在该系统中，实现场景实时漫游时，应用到第一种类型的碰撞检测；在预演施工过程时，会存在多个物体同时运动，它将会应用到第二种类型的碰撞检测。

第二种类型的碰撞，由于两个运动的物体可以看成一个物体相对于另一个物体的相对运动，因此运动物体间的碰撞检测问题可以简化为一个运动物体和一个固定物体之间的碰撞检测问题。所以，本文就只讨论第一种类型的碰撞检测，也称环境碰撞。

为了减少碰撞检测的计算，通常用边界体近似地表示具有复杂几何形状的物体，如点、球体或者长方体。在该系统中，就将模拟漫游的相机抽象为一个点。

运动物体无论以何速度、加速度、沿何轨迹进行运动，由于两帧之间的间隔都非常短，可以将两帧时间间隔之间视作直线运动，因此，环境碰撞检测问题简化为边界体沿线段的延伸与环境中某一部分的求交问题。当运动物体的边界体抽象为一个点时，即简化成了射线的求交问题。

环境中的物体，表面也都是由许多多边形所构成，在本项目中，所有的多边形都为三角形，即每个物体都是由许多三角形面所构成，判断射线与构成物体的所有三角形面的求交，上述的射线求交问题就转化为直线与面的相交测试。这样的测试是精细的碰撞检测，有时为了提高性能，会先做粗的碰撞检测，即构造环境中每个物体的边界体（球体、长方体等），判断射线与物体边界体的求交计算，以大大减少计算量。在该项目中，以物体的轴对齐包围盒（AABB）来构造长方体，做为物体的边界体。

直线与平面的相交测试：

在3D空间几何中，空间中的一条直线可以表示为：

P(t) = P + tV（1）

即包含点P并沿V方向延伸的直线，Q为直线上的任意点。

空间中的一个平面可以用平面上的一个点P0和该平面的法向量N来确定，用平面方程表示为：

Ax + By + Cz + D =0 （2）

其中A、B、C是平面的法向量N的x、y和z分量，D为-N .P0（两个向量的点积或内积）

平面到任意点Q的带符号距离d，就可以表示为：

d = N . Q + D （3）

如果d = 0，则点Q就在平面上；如果d大于0，则点Q位于平面法向量N所指的一侧；如果d小于0，则点Q位于平面法向量N所指的相反一侧。

如果将Q用直线上的任意点P(t)来表示，即将（1）式代入（3）式

N．P(t) + D = 0

用Q + tV替代P(t)，得：

N．Q + (N . V)t + D = 0

解关于t的方程，可得

-N . Q + D

t =

N . V

把t的值代回（1）式中，就可以求得直线与平面的交点。如果N . V为0，直线与平面平行，在这种情况下，如果N . Q + D= 0，直线在该平面上，否则，直线和平面没有交点。

直线与三角形面的相交：

直线与三角形所在平面相交，并不代表直线就与该三角形面相交，因此检测直线与平面相交还不够，必须进一步判断直线与平面的交点是否在三角形内部。判断交点是否在三角形内，使用仿射坐标分解的方法来计算。

与我们熟悉的笛卡尔正交坐标系相比，仿射坐标系的两个坐标轴是不平行的，只要是两个不平行的轴就可以构成一个仿射坐标系，显然笛卡尔坐标系是仿射坐标系的一个特例。

我们把三角形的一个顶点作为仿射坐标的原点，而从这个点发出的两条边作为仿射坐标两个坐标轴的单位向量，那么平面内的任何一个点在这个仿射坐标系的坐标数值就可以区分出来这个点和三角形之间的关系。假设这个点的坐标数值为u、v，则如果满足等式 u+v<=1，就表示这个点在三角形内。

它的算法实现如下：

设三角形的三个顶点（都为三维坐标）为：P1、P2，P3，与三角形同平面的交点为：P0

构造两个边向量U、V：

U = P2 – P1 V = P3 – P1

P0在此坐标系对应的点为

PP = P0 – P1

可写为：PP = x * U + y * V

求出x、y值后，就可判断交点P0是否在三角形内。由于U、V都是三维分量，需要求两个未知数，只要找三维分量中绝对值最小的两个分量求解就可以了。

射线与三角形相交的实现如下：

第一步：构造三角形所在平面

以三角形的第一个顶点P1为平面上的一个点，

顶点P1与另个两个顶点P2、P3的差向量U、V表示为：

U = P2 – P1V = P3 – P1

法向量N = U x V（向量U与向量V的叉积）

对向量N进行规格化处理

P为平面上的任意点，则平面方程可表示为：

N . P – N . P1 = 0

第二步：构造射线方程（见后）

第三步：计算射线与平面的交点

第四步：判断交点是否在三角形内

直线与长方体（轴对齐包围盒）的相交测试：

第一步：构造物体的轴对齐包围盒

通过计算物体的所有顶点（三个轴分别用X、Y、Z表示）在三个分量上的极小、极大值，表示为Xmin、Ymin、Zmin、Xmax、Ymax、Zmax，物体的轴对齐包围盒如下图所示

第二步：构造六个面的平面方程

根据上图可得包围盒的8个顶点的值：

(Xmin,Ymin,Zmax)(Xmax,Ymin,Zmax)

(Xmax,Ymin,Zmin)(Xmin,Ymin,Zmin)

(Xmin,Ymax,Zmax) (Xmax,Ymax,Zmax)

(Xmax,Ymax,Zmin) (Xmin,Ymax,Zmin)

再者，由于是轴对齐包围盒，它的各个平面法向量都是与坐标轴平行的，而法向量一般都是要进行单位规格化，6个面的法向量都可以分别表示为：

(1,0,0)、(-1,0,0)、(0,1,0)、(0,-1,0)、(0,0,1)、(0,0,-1)。

将顶点及平面法向量值代入上公式（2）中，即可得到包围盒的六个面的平面方程：

x – Xmax = 0x + Xmin = 0

y – Ymax = 0y + Ymin = 0

z – Zmax = 0z + Zmin = 0

第三步：直线（射线）与轴对齐包围盒相交测试

 从六个面中，丢弃法向量朝向背面的面，会丢弃三个面；

 从剩下的三个面中，进行射线与平面的相交测试，计算相交点Q距离值t;

 选择最大距离值t所对应的相交点Q；

 判断Q点是否在包围盒内（比较简单，只要判断它的各分量与包围盒的极值分量进行比较）；

碰撞检测实现：

第一步：构造射线（或直线）方程

相机初始点为P0，前进方向为V，则直线方程表示为：

P(t) = P0 + tV

第二步：进行射线与物体的轴对齐包围盒（AABB）相交测试

第三步：如果与AABB相交，进行下一步；否则，跳至第六步

第四步：进行射线与物体的各个面相交测试

第五步：如果相交，有碰撞发生，记录，跳至第二步，继续进行与其它物体的AABB相交测试；如果不相交，则进行下一步

第六步：无碰撞发生，跳至第二步，继续进行与其它物体的AABB相交测试

6、碰撞响应处理

当检测到有碰撞发生后，就要进行碰撞响应处理。一种处理方法就是停止行进，以阻止穿过物体或进入物体内部；另一种处理方法是，按设定规则向相邻方向行进，行进步长按预先设定数值。

在本系统中，响应处理如下：

第一步：与物体轴对齐包围盒相交，则进行与物体的所有三角形面进行相交测试；

第二步：如果不相交，则认为没有碰撞发生；相交，有碰撞发生，计算与所有面相交距离最小的值d；

第三步：如果d小于等于系统设定相机至物体间最小距离W，在按顺时针方向，向相邻方向行进，并进行碰撞检测判断；如果d大于系统设定相机至物体间最小距离W，在前进至最近面距离为W处。

为了避免卡住的问题，进行处理时，要先判断相机点是否落在物体的轴对齐包围盒内或者物体内部，遇到此情况出现时，强行跳出物体的轴对齐包围盒。

7、性能优化

当场景变得比较复杂，模型较多时，碰撞检测、响应处理对系统性能就尤为关键。必须采取优化算法，来提高碰撞检测、响应处理的效率。

在该系統中，采用了粗、细碰撞检测相结合的方法，即上面论述的先用物体的轴对齐包围盒来进行粗碰撞检测，如果发生碰撞，再进行与物体的三角形所有面相交测试的精细碰撞检测。因为轴对齐包围盒只有六个面，而物体的三角形面要多得多，所以在工作中效率上有很大提高。

此外，可以采用空间分割技术，它涉及到场景管理，常用八叉树或BSP树来表示场景空间，在该项目中，使用了八叉树结构。

由于在用八叉树和BSP树表示的空间中，区域是被平面分割开的，通常可以无须将运动物体与场景中大部分区域中实际几何模型进行碰撞检查，就可以知道它不与这些区域发生碰撞。

结束语：

应用效果满意，满足系统功能需要。在一台配置为PIII 1.2G 128M 64M独立显存的PC机上，动态生成一个1167个对象，共106721个顶点，53180个面的场景，运行比较流畅，也没有发卡问题。但在模拟上楼梯、电梯运行等，还需要做进一处的技术处理。

参考文献：

1、《OpenGL超级宝典》 Richard S.Wright,Jr.Michael Sweet 著人民邮电出版社

2、《OpenGL Red Book》

3、《OpenGL Blue Book》

4、《实时计算机图形学》Tomas Akenine-Moller著 北京大学出版社

5、《3D游戏与计算机图形学中的数学方法》 Eric Lengyel著清华大学出版社

6、《Core Techniques and Algorithms in Game Programming》 Daniel Sanchez-Crespo Dalmau 著 New Rider Publishing 出版

7、《BSP-TREES AND POLYGON REMOVAL IN REAL TIME 3D RENDERING》 Samuel Ranta-Eskola 著Uppsala University 出版

注：文章内所有公式及图表请用PDF形式查看。