第四章 碰撞模块（Collision Module）
4.1简介
碰撞模块包含形状（shape）以及操作它们的函数。此外，碰撞模块还包括dynamictree和broad-phase来加快大型系统的碰撞处理速度。
碰撞模块被设计为可独立于动态系统（dynamicsystem）工作，例如，你可以用dynamic tree来处理你游戏中除了物理计算之外的其他部分。
当然了，Box2D主要还是作为一款刚体物理引擎，所以单独使用碰撞模块可能会让人觉得受限制，因此，我不会花很多时间来针对碰撞模块写详细的文档或是去修饰API。
4.2形状
形状描绘了碰撞几何形状（collisiongeometry），除了在物理模拟中使用外也可以单独使用，你至少需要理解如何创建形状，以及如何将形状附加到刚体上。
Box2D形状的基类为b2Shape，基类提供了下面几类方法：
· 测试一个点是否和形状重叠（点在形状上）
· 对形状做射线投射（ray cast）
· 计算形状的AABB（axis aligned boundingbox，能够恰好包住形状并且各个边均与坐标轴（之一）平行的四边形）
· 计算形状的质量
此外，每个形状还有一个类型（type）和一个半径（radius）成员变量，即使是多边形类，也包含半径这个成员变量，我们下面会讨论到。
记住一个形状并不知道物体（body）的存在，它存在于动态系统之外，形状的大小和效率经过优化以简洁的形式存储起来。同样的，想要移动一个形状并不容易。你需要手动的设置形状的顶点位置来移动它。然而，当一个形状通过装置被附加到物体上，形状就牢牢地固定在物体上随物体一起移动了。简单概括如下：
· 当一个形状没有附加到物体上时，你可以看到它的顶点在世界坐标系中。
· 当一个形状附加到物体上以后，你可以看到它的顶点在本地坐标系中了。
圆形状（circle shape）
圆形状具有一个位置和半径。圆形状是实心的，你不能创建一个空心圆。
b2CircleShape circle;
circle.m_p.Set(2.0f, 3.0f);
circle.m_radius = 0.5f;
多边形状（polygon shape）
多边形状是实心的凸多边形，一个凸多边形满足多边形内任意两点之间的线段都不与多边形的边相交。Box2D中的多边形是实心的，不能是凹多边形，一个多边形有3个或3个以上顶点。
多边形的顶点是按逆时针排列（counter clockwisewinding，CCW）存储的，我们需要对CCW的概念小心一些，因为CCW是按照右手坐标系统定义的（z轴由里面指向外面），相对于你的屏幕，有可能就变成顺时针了，取决于你的坐标系统的定义。
多边形的成员是公有的（public），但是我们最好还是通过初始化函数来创建一个多边形。初始化函数创建法向量（normalvector）并且检查初始化参数是否合法（validation）。
你可以通过传入一个顶点数组来创建多边形，数组的最大容量由b2_maxPolygonVertices来控制，默认值为8。对于大多数凸多边形来说，这个值足够了。
方法b2PolygonShape::Set自动计算出凸多边形的外边界并建立恰当的缠绕顺序（边的顺序）。当点数较少的时候，方法执行效率非常高。如果你增大b2_maxPolygonVertices，这个计算的执行效率有可能变得很低，同时需要我们注意的是，这个计算函数有可能会移除我们提供的顶点或者对其重新排序，当顶点之间的距离小于b2_linearSlop这个常量时，它们就会被合并。
//This defines a triangle in CCW order
b2Vec2 vertices[3];
vertices[0].Set(0.0f, 0.0f);
vertices[1].Set(1.0f, 0.0f);
vertices[2].Set(0.0f, 0.1f);
int32 count = 3;
b2PolygonShape polygon;
polygon.Set(vertices, count);
多边形类提供了一些方便的方法来创建矩形。
void SetAsBox(float32 hx, float hy);
void SetAsBox(float32 hx, float hy, const b2Vec2& center,float32 angle);
多边形类从b2Shape继承了一个半径（radius）属性，半径属性在多边形外面创建了一个外层（skin），外层用来在堆叠场景中让多边形彼此分离。这样就能够对核心多边形（corepolygon）模拟连续碰撞（continuouscollision，Box2D中解决高速物体穿透的一种算法，由于Box2D中使用时间片来模拟，因此当物体处于高速运动时，一个时间片内的位移可能非常大，导致物体穿过在位移路径上的刚体而没有发生碰撞，Box2D中采用连续碰撞来牺牲一定的效率处理高速物体，以避免这种情况发生，译者注）。
多边形皮肤通过将多边形彼此分离来防止穿透（tunneling），这导致了形状之间有一点点的间隙。不过，你实际上看到的多边形相比于他们之间的间隙来说要大得多。
边形状（edge shape）
边形状即线段，用来帮助我们在游戏中创建自由的静态（static）环境。使用边形状的一个主要限制是，他们能够和圆形状、多边形发生碰撞，但是边形状之间不能发生碰撞。Box2D中在计算碰撞时要求碰撞的两个物体至少一个具有面积，边形状没有面积，所以他们之间不可能发生碰撞。
//This an edge shape
b2Vec2 v1(0.0f, 0.0f);
b2Vec2 v2(1.0f, 0.0f);
b2EdgeShape edge;
edge.Set(v1, v2);
很多游戏中的场景都是由多个线段首尾相连创建而成的，当一个多边形沿着线段链（chain）移动的时候，就有可能出现意想不到的问题。在下面图中我们看到，一个四边形和一个内部顶点（internalvertex）碰撞了，这种“鬼打墙”（ghost collision）现象的产生是由多边形和内部顶点生成的内部碰撞法线（internal collisionnormal）发生了碰撞而产生的。
如果edge1不存在，那么这个碰撞看起来很合理（box和edge2理应发生碰撞），但是由于edge1的存在，就导致这种碰撞看起来像是一个漏洞（bug）。但是通常情况下，在Box2D中处理物体碰撞的时候，会将它们视为孤立的（这也就是为什么有这个例子了）。
好消息是，边形状提供了一种机制用来消除这种“鬼打墙”的现象，如下图，Box2D中，通过存储相邻的节点，将它们视为影子顶点（ghostvertice），这样就能够防止内部碰撞了。
//This is an edge shape with ghost vertices.
b2Vec2 v0(1.7f, 0.0f);
b2Vec2 v1(1.0f, 0.25f);
b2Vec2 v2(0.0f, 0.0f);
b2Vec2 v3(-1.7f, 0.4f);
b2EdgeShape edge;
edge.Set(v1, v2);
edge.m_hasVertex0 = true;
edge.m_hasVertex3 = true;
edge.m_vertex0 = v0;
edge.m_vertex3 = v3;
整体看来，这种缝合的方式看起来有些费力不讨好，所以我们引出链形状（chainshape）。
链形状（chain shape）
链形状提供了方便的方法让我们通过连接线段来创建静态世界。连形状自动消除我们之前遇到的“鬼打墙”现象，并且链形状能够提供双向的碰撞模拟（链的两侧都可以发生碰撞）。
//This is a chain shape with isolated vertices
b2Vec2 vs[4];
vs[0].Set(1.7f, 0.0f);
vs[1].Set(1.0f, 0.25f);
vs[2].Set(0.0f, 0.0f);
vs[3].Set(-1.7f, 0.4f);
b2ChainShape chain;
chain.CreateChain(vs, 4);
你也许有一个卷动的游戏世界需要将多组链形状连接到一起，你可以像连接线形状（b2EdgeShape）一样，使用上面提到的影子顶点将链形状进行连接。
//Install ghost vertices
chain.SetPrevVertex(b2Vec2(3.0f, 1.0f));
chain.SetNextVertex(b2Vec2(-2.0f, 0.0f));
下面的方法可以用来创建一个环（loop）：
//Create a loop. The first and last vertices are connected.
b2ChainShape chain;
chain.CreateLoop(vs, 4);
自相交（self-intersection）的链形状（如图）是不支持的，如果你真的在游戏中创建出自相交的链形状，它有可能会好用也有可能不好用，用来处理“鬼打墙”现象的代码会假定没有自相交的链。此外，如果顶点距离太近，也可能产生问题，因此请确保所有的边长度都大于b2_linearSlop（默认定义是5mm）。
链形状的每一条边都被当做一个子形状处理，你可以通过索引（index）来访问这些边。当一个链形状被连接到一个物体（body）上时，在broad-phase碰撞树中，每一条边都有自己的外轮廓（boundingbox，见第三章中我们提到的AABB的解释）。
//Visit each child edge
for (int32 i = 0; i < chain.GetChildCount(); ++i)
{
b2EdgeShape edge;
chain.GetChildEdge(&edge, i);
}
4.3一元的几何查询（unarygeometric queries）
你可以对一个图形执行一系列的几何查询。
形状-点 测试（shape point test）
你可以测试一个点是否与形状有交叠（即点落在形状内）。通过提供一个图形变换（transformfor the shape）和一个世界中的点：
b2Transform transform;
transform.SetIdentity();
b2Vec2 point(5.0f, 2.0f);
bool hit = shape->TestPoint(transform, point);
如果形状是边形状（edge）或链形状（chain），则始终返回false，即使是闭合的链形状（loop）。
形状射线投射（shape ray cast）
你可以向形状投过一道射线，然后得到射线射入形状的入射点和法线向量。如果射线从形状内部射出，则不会得到任何入射点。下面代码中我们用到了一个子索引（child index），因为射线投射一次只能作用于一个边（对于其他形状，这个参数会被忽略）。
b2Transform transform;
transform.SetIdentity();
b2RayCastInput input;
input.p1.Set(0.0f, 0.0f, 0.0f);
input.p2.Set(1.0f, 0.0f, 0.0f);
input.maxFraction = 1.0f;
int32 childIndex = 0;
b2RayCastOutput = output;
bool hit = shape->RayCast(&output, input, transform,childIndex);
if (hit)
{
b2Vec2 hitPoint = input.p1 +output.fraction * (input.p2–input.p1);
…
}
（注：input参数中，p1和p2点定义了射线的方向，maxFraction则决定了射线段的长度，也就是定义了在这个射线上多长的范围内来进行射线投射，如果这个值设置的较小，有可能得不到任何交点，如下图所示）
4.4二元方法
碰撞模块提供了一些对等函数来对一对形状进行一些运算，包括：
· 重叠（overlap）
· 接触取样（contact manifold）
· 距离（distance）
· 碰撞时间（time of impact）
重叠
你可以用下面的方法来测试两个形状是否重合：
b2Transform xfA = …, xfB = …;
bool overlap = b2TestOverlap(shapeA, indexA, shapeB, indexB, xfA,xfB);
上面的indexA和indexB参数也是为了链形状提供的（链形状需要对每条边做检测）。
接触取样
Box2D提供了用于计算重叠对象的接触点（contactpoint）的方法，如果我们圆形-圆形或者圆形-多边形接触，我们只能够得到一个接触点和法线。当多边形和多边形接触时，我们计算得到2个接触点，这些点具有相同的法向量，因此Box2D将他们用一个结构体组装起来。接触解析器（contactsolver）利用可以利用这个方法保证堆叠对象的稳定性。
通常我们不需要去直接计算接触点，我们仅仅需要得到的模拟效果就可以了。
b2Manifold结构体定义了一个法向量和至多两个接触点，法向量和接触点使用的是本地坐标，为了给接触解析器提供方便，每个接触点都存储了法向和切向（摩擦）冲量。
b2Manifold中的数据被优化以便内部使用，如果你需要使用这些数据，最好是使用b2WorldManifold结构体来生成符合世界坐标系的法向量和接触点。你需要提供一个b2Manifold结构体，一个形状和变换（transform）和半径。
b2WorldManifold worldManifold;
worldManifold.Initialize(&manifold, transformA, shapeA.m_radius,transform, shapeB.m_radius);
for (int32 i = 0; i < manifold.pointCount; i++)
{
b2Vec2 point = worldManifold.points[i];
…
}
注意循环中使用的pointCount是原始的b2Manifold的pointCount，原因是b2WorldManifold结构体中并没有定义这个值。
在模拟过程中，形状会发生移动导致取样发生变化，接触点的数量会发生变化（增加或减少），你可以通过b2GetPointState来检测变化。
b2PointState state1[2], state2[2];
b2GetPointStates(state1, state2, &manifold1, &manifold2);
if (state1[0] == b2_removeState)
{
//process event
}
距离
b2Distance方法可以用来计算两个形状之间的距离。这个方法要求两个形状都转换为b2DistanceProxy类，对于大量的计算，在计算之前还需要初始化一些缓存对象，具体的细节请参阅b2Distance.h文件。
碰撞时间
如果两个形状都以高速运动，就会发生穿透（tunnel）现象。
b2TimeOfImpact方法用来计算两个形状的碰撞时间，称为timeof impact（TOI），b2TimeOfImpact主要是用来防止穿透现象的产生，尤其是防止运动物体穿出静态的几何体跑到外面去。
这个计算方法考虑两个形状的旋转和平移，然而如果旋转非常大的话，还是可能导致漏掉碰撞。但是函数仍然会跑高一个非重叠的时间，并且会捕捉到所有的平移碰撞。
碰撞时间函数定义了一个初始的分离轴（separatingaxis），并保证形状无法穿过这条轴。这可能会导致在结束位置附近漏掉一些碰撞，尽管如此，这是最快的也是最适合的解决碰撞的方法了。
（解释一下两幅图：上面一幅图中，第一幅图t=0的时候，物体要向t=1的位置旋转，由于t=1时发生了碰撞，因此，碰撞被检测到了，下面的一幅图，t=0和t=1时刻均没有发生碰撞，导致碰撞没有被检测到）
很难对于旋转幅度做一个严格的限制，有时候甚至是很小的旋转幅度都会导致碰撞被错过检测，一般来说，这些没有被检测到的碰撞不会影响游戏性，它们只是一闪而过而已。
碰撞时间函数需要两个形状参数（转换为b2DistanceProxy）和两个b2Sweep结构体参数，sweep结构体定义了形状初始和结束的变换。
你可以使用固定的旋转幅度去执行一次函数，在这种情况下，碰撞时间函数不会漏掉任何碰撞。
4.5动态树（dynamictree）
Box2D中用b2DynamicTree类来有效地组织大量的形状。这个类并不知道任何形状，它只是通过用户指针来操作形状的AABB（axis-alignedbounding box，前面做了解释）。
动态树是一个分层次的AABB树，每一个内部节点都有两个孩子节点，每个叶子节点都是一个单独的用户AABB。整棵树使用旋转来保持平衡，即使是在衰减的时候。
树的结构支持高效的射线投射和区域查询。例如，你的场景中可能会有上百个形状，你如果用蛮力对场景中的各个形状进行射线投射，效率会非常低，因为这个过程并没有利用形状的分布。相反的，我们可以维护一个动态树，接着对动态树进行射线投射，这样可以略过树中大量的形状。
一次区域查询使用树来找到所有与查询AABB（queryAABB）重叠的AABB，这比暴力计算高效的多，因为很多形状都会被跳过。
一般情况下，你不需要直接使用动态树，你只需要通过b2World来调用射线投射和区域查询的方法就可以了。如果你需要实例化你自己的动态树，你可以通过查看Box2D中的调用方法来学习如何使用它。
4.6 Broad-phase
在一个时间间隔（timestep）内发生的碰撞处理过程可以被分成narrow-phase和broad-phase两个阶段，在narrow-phase阶段我们计算形状之间的接触点，假设我们有N个形状，如果用遍历的方法，我们需要为N*N/2对形状执行narrow-phase。b2BroadPhase使用动态树来管理这些形状，显著地减少了narrow-phase的调用次数。
通常情况下你不会跟broad-phase直接打交道，Box2D内部会创建和维护一个broad-phase，同时，b2BroadPhase是为Box2D模拟循环而设计的，所以它可能不适合在其他情形中被使用。
