UE3场景管理与碰撞

UE3场景管理与碰撞

场景管理是怎样搭建的，场景管理的作用之一是可以用来做的碰撞检测的，而本篇文章要给大家将的就是 UE3里的场景管理和碰撞，一起来看看吧。

场景管理简要概述：

3D场景管理，简单来讲指的是对3D场景内所有具有位置和大小信息的物体进行的管理，以下是一个简单的游戏引擎场景数据流，场景数据作为数据源，每帧输入到碰撞、物理系统及游戏逻辑等各子系统中处理，子系统更新场景内的物体状态（位置、光照、新增、消亡等），然后场景数据进入渲染系统处理，最终显示在屏幕上。

场景管理的作用大致有这么几个方面：按一定层次及坐标系统储存场景物体、可见性剔除、碰撞检测。

一，场景物体层次结构：

场景管理的第一个作用很明显：场景中的物体需要有一定的数据结构来储存。

首先，我们假设一个场景内有3个物体：人、屋子、地板，首先定义一个简单的物体数据结构：Actor（含有简单的位置和可渲染网格，为简单起见，不考虑旋转）:

class Actor

{

Public:

Vector3D location;  

Mesh* mesh; // 可渲染的网格模型

Int id;

}

将这3个物体模型加载到Actor内并赋予一定的位置，然后，我们暂且用一个全局的简单数组来保存这些Actor：

vector g_Actors;

每帧通过遍历数组将场景物体传递给子系统进行处理，这里也暂且不讨论数组的效率问题。

进一步看，如果某个物体并非由简单的一个模型组成，比如它是一个全身上下都挂满装备的铠甲武士。一般来说，美术并不会把装备和武士身体做成一个模型，那样的话他可有得忙活了（每换一个装备都得制作一整套模型！），而是将武士各部位的模型单独提供给我们，所以，我们会有1个身体模型和m种装备模型，假如按照前述的方式，把它们作为m + 1个物体加入数组中进行管理，那么每次武士的位置或者旋转改变，它各部位的装备位置和旋转也要跟着变化，那么就得单独计算m + 1个物体的位置和旋转，更糟糕的是，这m种装备的模型旋转和位移是相对武士模型来计算的，所以不得不先通过它们各自的世界位置计算出它们之间的相对位置和旋转，然后再计算出各个装备模型的位置和旋转。所以，得对物体的数据结构进行升级，添加一个新类Component，它代表一个可视组件，每个Actor下有一个Component的列表：

class Component

{

Public:

Mesh* mesh;

Vector3D translation; // 相对位置

Actor *owner; // 组件拥有者

Bound bound; // 包围盒大小，后续会再讨论包围盒的类型

}

class Actor

{

Public:

Vector3D location;

vector components;

}

这样，武士作为一个Actor在场景中有一个世界位置location，武士的身体模型及其m个装备模型则以Component的形式挂载在Actor上，Component的translation记录了相对Actor的位置（为了简单起见没有记录旋转等其他信息），这样武士运动的时候，只需要改变一个location，挂载在其身上的所有模型都不需要改变位置。要得到某个模型渲染的位置，只需要将Actor的location加上Component的translation即可，这有点类似于骨骼系统。

当然更进一步，如果武士是骑在一匹马上，而这匹马又是站在一艘轮船上，要满足这样的需求，那么我们还需要升级一下Actor的数据结构：

class Actor

{

Public:

Vector3D location;

vector components;

vector childObjects;

}

这个时候，轮船作为一个Actor，它的location是世界位置，马同样作为一个Actor被加到轮船的childObjects内，它的location是相对轮船的位置，同理，武士被加到马的childObjects内，这样，比如要得到武士手上一把刀的渲染位置，需要经历如下的计算：

Component(刀).translation +

Actor(武士).location +

Actor(马).location +

Actor(轮船).location;

二，场景物体的组织：

讨论完场景物体，该升级一下组织场景物体的数据结构了，我们暂且把这个数据结构称之为“仓库”。前面我们的仓库就是一个简单的数组，为了方便各个子系统对场景物体的存取处理，我们再定义一个场景管理类World，World提供一个GetActorByID或者GetActorByName的方法以便查找到场景中的某个对象：

class World

{

Public:

Actor* GetActorByID(int id);

Actor* GetActorByName(string strName);

Private:

vector actors;

}

World通过遍历数组来查找所需要的对象，每帧也通过遍历数组将场景物体传递给子系统进行处理，对于只有几个物体的小场景来说，这种方式，并无什么不妥。

让我们进一步，如果把仓库的数据结构改成一张map，以场景物体的ID或者对象名作为Key：

class World

{

Public:

...

Private:

map actors;

...

}

这样World查找一个Actor的时间相比数组方式就大大缩小了，但是同样地World每帧还是要通过遍历Map的方式将所有对象传递给子系统进行处理，对于一个场景较为简单的游戏，比如相机固定，场景之间元素不需要考虑碰撞，这样的数据组织方式足以满足，据说某劲舞类的游戏就是这样管理场景的。

考虑到如果是像魔兽世界这样级别地图的游戏，即使考虑了动态加载地图区块的因素，每帧只把当前区块内所有场景物体传递给下一子系统进行处理，也是非常低效的。所以我们需要升级一下仓库的数据结构。

在升级数据结构之前，我们回顾下之前所说的场景管理的后面两个用途：可见性剔除、碰撞检测。可见性剔除和渲染系统相关，不可见的物体要在渲染系统处理之前全部剔除掉，而碰撞检测和碰撞系统相关，但是碰撞系统处理的物体可有可能是看不到的，比如一个FPS相机视角的游戏，玩家在后退过程中，如果有一堵墙在身后，虽然玩家看不到墙，但是这堵墙还是必须对他有碰撞阻挡。

1，可见性剔除及细分网格

首先来说说可见性剔除（也叫视锥体裁剪），假设10000米*10000米的区域内10000个物体，如果不进行可见性剔除，把这10000个物体全部交给渲染系统，那么渲染系统的确够忙活。一般来说可见区域只是场景中很小的一部分，因此剔除视野外的物体格外重要，所以我们首先通过物体的位置和包围盒计算出完全不在视锥体内的物体，将它们剔除，然后更细一步，将部分在视锥体内的物体进行裁剪，再处理背面消除、遮挡处理，LOD处理等（这里不详细讨论物体级别以下的裁剪），再交给渲染系统处理（如图所示，红色为完全剔除的物体，蓝色为部分在视锥体内的物体，绿色为完全在视锥体内的物体）：

即使是经过了可见性剔除，算法还是得遍历10000个物体是否和视锥体相交，

这个过程仍旧是非常缓慢的。我们尝试把数据组织的方式改进一下吧，把10000*10000的区域划分成n*n个子区域，每个子区域内的物体记录在子区域内，这样我们首先遍历子区域，让子区域同视锥体相交检测，如果子区域完全不在视锥体内，那么将不检测该子区域内的所有物体，这种方法叫做细分网格。决定子区域的大小是个难题，如果细分为1*1，那么相比最初没有任何改进，如果细分区域数量太多，那么遍历次数依旧很多。不管怎么说，细分网格这种方法，如果细分层数适当，效率还是有很大的提升的。

2，细分网格的扩展

按照细分网格的思想，完全可以对子网格进一步进行细分，所以bsp树、四叉树、八叉树等空间划分算法被引入了裁剪，它们解决了均匀网格划分粒度大小的问题，这种多级层次划分，既能保证让大量物体迅速被剔除，又能保证裁剪精度。

UE3中，场景管理是结合八叉树和BSP树进行的，我们更新下World的数据结构：

class World

{

Public:

...

Private:

Octree *octree;

BspTree *bsp;

...

}

我们将之前简单的一个map替换成了一棵八叉树和BSP树。

这里需要说明的是UE3中，使用unreal编辑器画刷添加的所有几何体（缩写CSG——构造实体几何体）在场景构建（build)后，都会添加到bsp树中进行管理，

这边只简要介绍下BSP树构建的一个简单过程，如下图所示：

具体算法就不描述了，大致就是选取分割面及归类多边形到子树上的递归过程，直到所有多边形都处理完。再简要说明一下BSP的使用场合及优点和缺点：BSP （BinarySpace Partition）二叉空间分割，它是基于场景中的多边形构建的一棵二叉分割树。使用这种方法可以使我们在运行时使用一个预先计算好的树来得到多边形从后向前的列表，它的复杂度为 。UE3中，BSP树用于关卡中用画刷构建的室内场景尤其是那种室内联通的各种区域，它的优点是算法复杂度低，能够快速剔除复杂关卡内的隐藏面以及用于关卡内画刷多边形的碰撞检测，缺点是BSP树是预先生成的，构建它的物体在关卡内都应该是静态的，而实时构建BSP是低效的，所以对于动态物体它不适用。在关卡加载时，World会加载已经构建好的Bsp序列化数据到BspTree中。

对于大量室外场景及动态物体的处理，UE3提供了另外一个种数据结构：八叉树，顾名思义，就是它的每个非叶子节点的子节点个数都是八个，这在三维空间里，对应于3D坐标系中的八个象限，它是细分网格思想的一种扩展，从平面扩展到立体，如图所示（三级八叉树结构）：

初始的八叉树只有一个根节点，它和一个包围体积一一对应，UE3中这个包围体积是一个恒定变量：RootNodeBounds，它是以(0, 0, 0)点为中心，HALF_WORLD_MAX为扩展范围的一个包围盒，HALF_WORLD_MAX=262144.0f（虚幻单位，1米=50.0虚幻单位），HALF_WORLD_MAX为上图立方体的一半边长，(0,0,0)点对应立方体的中心位置，也就是说，根节点bound宽度差不多是10公里（2*262144/50.0 米）。

现在再让我们来考虑一个问题，我们应该把场景中哪种对象挂载到八叉树中去管理呢？如果直接挂载一个Actor是否合适呢？由于八叉树在添加对象时，需要知道该对象的具体大小也就是包围盒的大小，才能知道往哪个节点去添加。而上述Actor的数据结构经过改造之后，实际上，它的大小取决于挂载在它身上的所有Component，Actor本身只是一个逻辑概念，除了位置外并没有实际大小的概念，所以，如果直接挂载Actor到八叉树上，逻辑上容易混乱，算法上也不好实现。再来看看Component，每个Component（在UE3中准确来说可渲染的组件都是PrimitiveComponent）都有自己的bound，且每个Component对应一个渲染单位，无论从碰撞检测的需求还是可视化剔除的需求来看，Component无疑是最适合用来挂载到八叉树进行管理的。

八叉树和四叉树的算法类似，只不过增加了一个纬度，这里讨论下在UE3中的大概构建流程：

关卡加载时，引擎会将编辑器在关卡中预先设置好的所有Actor中的Component逐个添加到World->octree中。初始的时候，根节点就是一个叶子节点，它没有任何子节点，Component首先挂载物体到根节点上，等到根节点上的Component数量到了上限（UE3中节点挂载上限是一个常数：MAX_PRIMITIVES_PER_NODE=10)，这时，给根节点生成8个空的子节点，再根据八叉树的特性，判断要添加的Component的bounds是属于8个象限中的哪个，再将该Component挂载到对应节点。这里有个问题，当根节点挂载的Component数量到达上限之后，而新加的Component的bounds不完全位于根节点的任何一个子节点（我们暂且称这种Component叫做跨节点Component），这个时候，我们该怎么挂载这个跨节点Component呢？为了应对这种情况，UE3给该Component提供了一个叫做bWasSNFiltered的变量，该变量为TRUE时，只允许Component添加到一个节点上，这时该Component将不受节点挂载上限数量MAX_PRIMITIVES_PER_NODE的限制，仍旧往根节点挂载，如果bWasSNFiltered为FALSE，那么将同时在根节点的任何一个只有部分包含该Component的叶子节点上挂载该Component。那么，什么时候跨节点Component应该只挂载到一个节点，什么时候跨节点Compoent应该挂载到多个节点上呢？由于挂载到单个节点效率较高但精度会有所降低，挂载多个节点效率比较低但精度会比较高，对于那些关卡中永恒不变或者基本不变的静态物体，例如：关卡中事先拖拉好的房子、树木、岩石等，它们一般都是在关卡初始的时候加载的，且游戏过程基本不怎么变化，这种静态类的Component一般都是挂载到多个节点上的，而像玩家角色身上的Component，基本每帧都会变化，每帧都需要更新其在八叉树的位置，所以动态类的Component一般都是挂载在单节点上的，这样效率较高，且动态类型的Component一般都维持在一个较小的Bound内，所以它跨节点的情况比较少，精度影响并不大。UE3中，当Component初次附加到Actor或者位置、旋转、大小等改变，都会间接调用到一个AddPrimitive函数，这个函数会添加或者更新Component在八叉树上的挂载位置。

3，碰撞检测：

在有了场景物体的数据结构以及组织方式后,我们就能比较方便讨论碰撞检测了。

先说明一下UE3中两个术语的意思：

ZeroExtent,：零粗细，一般指碰撞检测的线或者点没有粗细（体积为0）

NonZeroExtent：非零粗细，一般指碰撞检测的线或者点有粗细（即有实际体积）

UE3中，碰撞检测分为PointCheck（点检测）和LineCheck（线检测）。而PointCheck又分为ZeroExtent PointCheck和NonZeroExtentPointCheck，LineCheck分为ZeroExtentLineCheck和NonZeroExtent LineCheck。非零粗细检测的效率比零粗细检测低，所以可以用零粗细模拟的碰撞检测应该尽量用零粗细方式。

举两个比较常见的LineCheck的例子：

在一个玩家Actor移动的时候要检测移动方向上是否有阻挡物，那么就要用到NonZeroExtent LineCheck，检测的粗细度和Actor的碰撞盒大小有关。

如果是检测一颗很小的子弹是否击中物体，那么就应该用ZeroExtent LineCheck，因为子弹较小，用0体积来模拟并无不妥。

PointCheck一般用于判断某块区域内有哪些物体，或者某两个物体是否重叠等。

LineCheck和PointCheck区别在于LineCheck用于判断某条线是否与某体积相交，而PointCheck用于判断某点是否与某体积相交。

UE3中的包围体：

类似于细分区域的方法，在对一个物体进行细节碰撞检测前，先对其简单的包围体进行检测，能够线过滤掉大部分不能通过测试的物体，从而大大提高检测效率。

AABB/坐标轴对齐包围盒（FBox）：（如下图包围鹿的蓝色立方体）

OBB/定向包围盒（NxBox）：（如下图的大炮的各部分都是一个OBB）

包围球（FSphere）：（如下图包围鹿的黄色球体）

包围柱（FCylinder)：

K-DOP（离散定向多面体）：

关于这些包围体的几何知识和具体碰撞测试算法，超出本文范围，不深入探讨。

由于继承自PrimitiveComponent（图元组件）的子类有许多种，各种子类都可能适用不同的包围体，一般来说普通的射线检测使用的是AABB或者包围球。包围柱是只能绕着纵向轴旋转物体，而不能绕着其它轴线旋转，或者只能进行平移，它经常作为直立人物的包围体使用。而OBB用于物理刚体，K-DOP一般用于静态物体。

总结下UE3中进行碰撞检测的处理层次：

1，根据BSP树、八叉树的细分结构以及测试体积和测试位置，找出将要进行测试的细分区域。

2，对将要测试的细分区域内的所有拥有碰撞标记的物体使用其包围体进行碰撞检测，剔除那些没有通过测试的物体。

3，对通过测试的物体进行精确到三角形面片的细节碰撞检测（UE3中，PrimitiveComponent是所有可以进行渲染和碰撞检测的组件的基类，它的子类会根据自身的需要重写PointCheck和LineCheck函数来决定如何精确地检测碰撞，然后再返回碰撞检测结果）

由于碰撞检测是引擎的核心模块，每帧都会有大量调用，所以，和骨骼计算类似，必须对碰撞检测的核心代码进行优化。UE3通过SIMD指令（Single InstructionMultiple Data，单指令多数据流）来提高计算速度，为了方便调试和理解算法，UE3针对每个碰撞检测的算法都会提供两个版本的算法，一个是普通指令的一个是SIMD的，通过USE_SIMD_XXX来开启是否使用SIMD版本。

二，UE3中的一些碰撞标记及UC脚本碰撞事件

1，碰撞标记

UE3中的碰撞标记存在于Actor和PrimitiveComponent中，

PrimitiveComponent内的标记有：

BlockZeroExtent：是否屏蔽零粗细检测。在做ZeroExtent LineCheck或者ZeroExtent PointCheck检测时，是否检测该PrimitiveComponent。

BlockNonZeroExtent：是否屏蔽非零粗细检测。在做NonZeroExtent LineCheck或者NonZeroExtent PointCheck检测时，是否检测该PrimitiveComponent。

CollideActors：是否要做进行碰撞检测。

BlockActors：是否要作阻挡。

Actor内的标记有：

bCollideActors：是否要做进行碰撞检测。这个标记决定Actor内的所有PrimitiveComponent是否要做碰撞检测，如果为FALSE，即使PrimitiveComponent的CollideActors为TRUE也不会做碰撞检测。

bBlockActors：是否要作阻挡。这个标记决定Actor内的所有PrimitiveComponent是否要作阻挡，如果为FALSE，即使PrimitiveComponent的BlockActors为TRUE也不会作阻挡。

bCollideComplex(碰撞复杂度)：是否在 Actor 移动过程中，忽略这个 Actor 上的简化碰撞外壳 ，并碰撞每个多边形。简化碰撞外壳在虚幻编辑器中或3D内容创建包中生成。碰撞每个多边形对非零粗细跟踪来说十分有用，这样子弹就能精确碰撞。碰撞每个多边形不推荐在actor移动中应用，这样对性能要求太高。

BlockRigidBody(屏蔽刚体)： 使用PhysX的Actor是否应该同这个Actor进行对碰。

bNoEncroachCheck(不进行侵占检查) - 当移动该actor时关闭encroachment                                 checking(侵占检查)的一种优化处理。启用该项将会加速游戏                            的运行，但是 Actor 将不能触碰触发器、推动玩家，进入或                               走出体积。

bPathColliding(路径碰撞) - 该Actor是否能在路径构建中屏蔽路径。 这个标志很有用，如果想让角色寻路时能够考虑动态的Actor阻挡，它默认是FALSE，开启会有一定效率损耗。

CollisionComponent(碰撞组件)：用于该actor运动的针对组件的引用 如果actor正在使用PHYS_Walking(物理行走)，那么和该组件边界框相对齐的坐标轴会同该关卡碰撞。如果该Actor正在使用PHYS_RigidBody(物理刚体)，那么这个组件的模型或是物理物体正在被使用。

CollisionType(碰撞类型) ：这是为方便关卡设计师设定关卡物体碰撞类型的一种简便方法。这个标志的设置，会同时影响上述的bColliderActors、bBlockActors、BlockRigidbody、BlockZeroExtent、BlocNonZeroExtent等变量，从而符合碰撞种类的描述，碰撞枚举如下：

o   COLLIDE_CustomDefault(碰撞_自定义默认) - 程序员设置碰撞。选中该项时在默认属性中把碰撞恢复到默认设置。

o   COLLIDE_NoCollision(碰撞_无碰撞) - 不碰撞任何物体。

o   COLLIDE_BlockAll(碰撞_屏蔽所有) - 屏蔽所有。

o   COLLIDE_BlockWeapons(碰撞_屏蔽武器) - 只屏蔽通常使用在武器上的零粗细踪迹。

o   COLLIDE_TouchAll(碰撞_触碰所有) - 触碰所有，但不屏蔽。

o   COLLIDE_BlockWeapons(碰撞_屏蔽武器) - 只屏蔽通常使用在武器上的零粗细轨迹。

o   COLLIDE_BlockAllButWeapons - 除了通常使用在武器上的零粗细轨迹踪迹，其他的都屏蔽。.

o   COLLIDE_BlockAllButWeapons - 除了通常使用在武器上的零粗细踪迹，其他的都触碰。这个不屏蔽。

o   COLLIDE_BlockWeapons(碰撞_屏蔽可脱卸武器) - 只屏蔽通常使用在武器上的零粗细轨迹。同样启用标记允许玩家更换该actor。

2，碰撞事件

Touch(触碰) ：当两个Actor相互触碰时调用touch(触碰)。调用的前提是两个Actor有检测碰撞（bCollideActors为TRUE），且有一个Actor为非阻挡状态（bBlockActors为FALSE），例如角色触碰到一个触发器或者可进入体积。Touch事件会同时在两个Actor中调用。

Untouch(未触碰) ：当两个Touch的Actor相互离开时，会调用Untouch事件，调用前提同Touch，同样，Untouch事件会同事在两个Actor中调用。

Bump（撞击）：当两个Actor撞击时调用。它同Touch的区别是，撞击时两个Actor并未彼此进入对方的空间，而是相互阻挡着。所以它的调用前提是两个Actor都有检测碰撞（bCollideActors为TRUE），且两个Actor都是阻挡状态（bBlockActors为TRUE）。

EncroachingOn（正在侵占）：（AcrtorA.EncroachingOn(ActorB)）当Actor A正在侵占另外一个Actor B时调用。前提是Actor A是一个“Encroacher”（侵占者），当bCollideActors为TRUE且Actor处在物理刚体状态或者Actor的bCollideAsEncroacher标记为TRUE时，该Actor是一个侵占者。Actor B是一个被侵占者，当它的bPushedByEncroachers为TRUE时，该Actor是被侵占者。如果EncroachingOn返回FALSE,当被侵占者被侵占时，会根据被侵占的距离而移动相应距离,否则，不会移动。当A的bNoEncroachCheck开启时，此事件不会被调用。

EncroachedBy（被侵占)：同EncroachingOn对应，当一个Actor被另一个Actor侵占时，会调用这个事件。