Boids群集动画中Mesh碰撞检测的研究与实现

摘要：Boids是一种用于模拟动物群体行为的算法，碰撞检测问题是Boids群集动画中的关键问题，通过对Boids群集动画的分析和研究，采用Mesh碰撞检测方法，解决人工鸟群对不规则3D物体碰撞检测问题。最后采用C++与DirectX技术，模拟实现了人工鸟群遇到障碍物房子时的碰撞检测。

Abstract: Boids is a algorithm of simulating animal flock behavior，collision detection is the key problem in Boids flock animation，through analysis and study of flock animation，Mesh collision detection method is adopted to solve collision detection problem of artificial birds and irregular 3D objects．Finally using C++ and DirectX technology to simulate and implement collision detection when the artificial birds collided obstacle house．

关键词：Boids；碰撞检测；Mesh

Key words: Boids；collision detection；Mesh

中图分类号：TP37 文献标识码：A文章编号：1006-4311（2010）36-0213-02

0引言

Boids是一种用于模拟动物群体行为的算法，也是人工生命、自组织、多主体系统等概念的典型代表。动画中的人工鸟（Boid）具有最基本的飞行能力和几种简单的行为，它们可以进行群落运动。群体在遇到障碍物的时候，群落就会分成两部分，越过障碍物以后，又重新聚集在一起。Boids群集动画在当今的电子游戏开发，电影特效制作中被广泛使用。几乎所有的3D特效设计都离不开碰撞检测，包括各物体之间的碰撞检测和物体与场景之间的碰撞检侧[1]。碰撞检测已成为计算机动画、计算几何、CAD系统、虚拟环境仿真等领域研究的重要课题[2]。碰撞检测问题是Boids群集动画中的关键问题，所以在Boids群集动画中，研究如何对不规则3D物体进行碰撞检测是非常有意义，而且具有极高的应用价值。

1Boids群集动画的研究与分析

Craig Reynolds博士制作了一个比较经典的生命模拟Boids群集动画。动画中的人工鸟有最基本的飞行能力和几种简单的行为，它们可以进行群落运动[3]。如果群落遇到障碍物，群落就会分成两部分，越过障碍以后，又重新聚集在一起，如图1所示。

在Boids视频中，可以看到鸟群绕过圆柱继续飞行的场景。在该视频中，使用的碰撞检测原理是判断鸟的位置是否在圆柱所在的二维圆形内，如果在圆柱所在的二维圆形内，就认为是发生碰撞。通过对Boids群集动画的研究与分析后发现，使用这种碰撞检测原理，优点是比较简单、计算速度快，缺点是无法对不规则3D物体进行碰撞检测。

通过对Craig Reynolds博士提出的Boids规则和原理进行分析后，为了实现人工鸟群对不规则3D物体进行碰撞检测，需要在Craig Reynolds博士提出的Boids规则上进行改进，并通过对多种碰撞检测方法，如空间剖分法、包围盒法和距离跟踪法进行研究比较后，决定采用Mesh碰撞检测原理，来解决Boids群集动画中的碰撞检测问题。

2Mesh碰撞检测的分析与设计

Mesh碰撞检测是网格和网格之间的碰撞检测，从中提出基于物体三角形碰撞检测的算法。如果它们的三角形相互碰撞，那么Mesh之间一定存在碰撞[4]。所以，在使用Mesh碰撞检测方法时，先确定一个Mesh中的三角形的三条边，若这三边存在一条和另外一个Mesh的三角形相交，那么就判定发生碰撞。

在设计Boids群集动画过程中，直接从人工鸟所在位置发射射线，来检测是否和障碍物网格中的某一个三角形发生碰撞。在程序设计时，使用D3DXIntersect（）函数，具体编码如下：

HRESULT D3DXIntersect（

LPD3DXBASEMESH pMesh，

CONST D3DXVECTOR3 * pRayPos，

CONST D3DXVECTOR3 * pRayDir，

BOOL * pHit，

DWORD * pFaceIndex，

FLOAT * pU，

FLOAT * pV，

FLOAT * pDist，

LPD3DXBUFFER * ppAllHits，

DWORD * pCountOfHits

）；

由此可见，在设计时，通过CONST D3DXVECTOR3 * pRayPos与CONST D3DXVECTOR3 * pRayDir两条代码来确定人工鸟的位置和运动方向，就可以确定一条射线，通过发射这条射线，来检测它和障碍物的关系，如果（*pHit）为真并且（*pDist）距离小于人工鸟的视野，那么，人工鸟沿当前方向运动就会发生碰撞。如图2所示，人工鸟正前方的红色线为其发射的碰撞检测射线，其视野大小为红色线段的长度。显然可以看到，人工鸟到障碍物房子边缘的距离小于鸟的视野，因此认定将会发生碰撞。

3Mesh碰撞检测的实现

为了验证Mesh碰撞检测方法在Boids群集动画中的效果，下面以房子作为障碍物为例，模拟实现Boids群集动画中鸟群遇到障碍物房子时的碰撞检测。

D3DXIntersect（）函数中的射线是基于物体自身坐标系的，因此当房子进行缩放、旋转、平移的操作后，射线要做房子的逆变换。如果要判断人工鸟是否将与障碍物房子相撞，首先应求出房子的世界矩阵的逆矩阵至于房子的逆变换矩阵，可以用D3DXMatrixInverse（）函数求障碍物房子的逆矩阵，代码如下：

D3DXMatrixInverse（&obstacle.InverseWorldMatrix，NULL，

&（s * rmx * rmy * rmz * t））；

其中（s * rmx * rmy * rmz * t）是障碍物房子的世界矩阵，结果输出到obstacle.InverseWorldMatrix中，然后对射线进行逆变换，代码如下：

D3DXVECTOR3 Position，Direction；

//pos（x，y，z，1） * InverseWorldMatrix点的逆变换（需要平移）

D3DXVec3TransformCoord（&Position，&pos，&obs.InverseWorldMatrix）；

//dir（x，y，z，0） * InverseWorldMatrix方向的逆变换（不需要平移）

D3DXVec3TransformNormal（&Direction，&dir，&obs.InverseWorldMatrix）；

其中，Position与Direction定义了射线的起点和方向，然后用D3DXIntersect（）函数对变换后的射线进行碰撞检测。实现后3D动画效果图如图3所示。

4结语

Mesh碰撞检测既可以完成对复杂场景的碰撞检测，也能够反馈特定模型之间的碰撞信息，从而使虚拟环境的真实感和拟真度得到很大提高[5]。本文通过研究和分析Boids群集动画，提出了人工鸟群对不规则3D物体进行碰撞检测的问题，采用Mesh碰撞检测方法进行了设计和实现，解决了人工鸟群遇到障碍物房子后的碰撞检测问题，具有一定的实际意义和应用价值。

参考文献：

[1]于晓霞．碰撞检测技术在游戏中的应用与实现[D]．山西：太原理工大学，2007：9-26．

[2]王志强，洪嘉．碰撞检测问题研究综述[J]．软件学报，1999，10（5）：545-550．

[3]Craig Reynolds.Boids[M/OL]．/cwr/boids/．

[4]吴国良，马登武．三维视觉运动建模中碰撞检测算法研究[J]．火力与指挥控制，2002，27（3）：29-31．

[5]冯善达，刘怡昕．虚拟场景中碰撞检测实用算法研究[J]．计算机仿真，2004，21（6）：100-111．