Chapter 4 碰撞模块
4.1 关于
碰撞模块包含了形状和操作形状的函数。该模块还包含了动态树(dynamic tree)和broad-phase，用于加快大型系统的碰撞处理速度。
碰撞模块被设计为可用于动态系统之外的地方。例如，你可以将动态树用于你的游戏中，除了物理之外的目的。
然而，Box2D 的主要目标是提供一个刚体物理引擎。因此对于一些应用来说，使用碰撞模块会感觉受到限制。同样的，我也不是很想将之写成文档，并形成API。
4.2 形状
形状描述了可相互碰撞的几何对象，它的使用独立于物理模拟。最起码，你应该知道如何创建shape，并将之附加到刚体上。
b2Shape是个基类，Box2D的各种形状都实现了这个基类。此基类定义了几个函数：
• 判断一个点与形状是否有重叠。
• 在形状上执行光线投射(ray cast)。
• 计算形状的AABB。
• 计算形状的质量。
另外,，每个形状都有成员变量：类型(type)和半径(radius)。 对于多边形，半径也是有意义的，下面会进行讨论。
需要注意的是shape并不知道body，也与力学系统无关。Shape采用一种紧凑格式来进行存储，这种格式经过尺寸和性能的优化。因此，shape并不方便移动，你必须通过手动的设置形状顶点来移动shape。然而，当使用fixture将shape添加到body上之后，shape就会和他的宿主body一起移动。总之：
• 当一个shape没有添加到body上时，它的顶点用世界坐标系来表示。
• 当一个shape添加到body上时，它的顶点用局部坐标系来表示。
圆形
圆形有位置和半径。圆形是实心的，你没有办法使圆形变成空心。
b2CircleShape circle;
circle.m_p.Set(2.0f, 3.0f);
circle.m_radius = 0.5f;
多边形
Box2D的多边形是实心的凸(Convex)多边形。在多边形内部任意选择两点，作一线段，如果所有的线段跟多边形的边都不相交，这个多边形就是凸多边形。多边形是实心的，而不是空心的。一个多边形必须有3个或以上的顶点。
多边形的顶点以逆时针（counter clockwise winding，CCW）的顺序存储。我们必须很小心，逆时针是相对于右手坐标系统来说的，这坐标系下，Z轴指向平面外面。有可能相对于你的屏幕，就变成顺时针了，这取决于你自己的坐标系统是怎么规定的。
多边形的成员变量具有public访问权限，但是你应该使用初始化函数来创建多边形。初始化函数会创建法向量(normal vectors)，并检查参数的合法性。
创建多边形时，你可以传递一个包含顶点的数组。数组大小最多是b2_maxPolygonVertices，这数值默认是8。这已足够描述大多数的凸多边形了。
b2PolygonShape::Set 函数会自动计算凸包（convex hull），并建立时针序。这个函数在顶点数少的时候，是非常快的。但如果你增大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, 1.0f);
int32 count = 3;
b2PolygonShape polygon;
polygon.Set(vertices, count);
多边形有一些方便的函数来创建box。
void SetAsBox(float32 hx, float32 hy);
void SetAsBox(float32 hx, float32 hy, const b2Vec2& center, float32 angle);
多边形从b2Shape中继承了半径。通过半径，在多边形的周围创建了一个保护层(skin)。堆叠的情况下，此保护层让多边形之间保持稍微分开。这使得可以在核心多边形上执行连续碰撞。
多边形保护层通过保持多边形的分离来防止隧穿效应。这会导致形状之间有小空隙。你的显示可以比多边形大些，来隐藏这些空隙。
边框形状（Edge shapes）
边框形状由一些线段组成。它们可辅助为你的游戏创建一个形状自由的静态环境。边框形状的主要限制在于它们能够与圆形和多边形碰撞，但它们之间却不会碰撞。Box2D使用的碰撞算法要求两个碰撞物体中至少有一个有体积。边框形状没有体积。所以边框形状之间的碰撞是不可能的。
// This an edge shape.
b2Vec2 v1(0.0f, 0.0f);
b2Vec2 v2(1.0f, 0.0f);
b2EdgeShape edge;
edge.Set(v1, v2);
在很多情况下，游戏环境是若干个边框形状首尾相连构成的。当多边形沿着边框链滑动的时候，会导致一个异常的行为。在下图中，我们可以看到一个box和一个内部顶点之间的碰撞。当多边形和一个内部顶点碰撞时，会产生一个内部碰撞法线，这会导致“幽灵”碰撞现象。
如果edge1不存在的话，这个碰撞看起来还算正常。edge1存在的话，这个内部碰撞就像是Bug了。但是通常当Box2D处理两个形状的碰撞时，会单独处理他们的。
幸运的是，边框形状提供了一种机制来消除幽灵碰撞——存储用于调整的幽灵顶点。Box2D使用这些幽灵顶点来阻止内部碰撞。
// 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;
通常情况下，用这种方式将边框缝合到一起是有些浪费和无聊的。这就为我们引入了链接形状（chain shapes）的概念。
链接形状（Chain Shapes）
链接形状提供了一种有效的方式，来将许多边框连接在一起，用以构建你的静态游戏世界。链接形状自动消除幽灵碰撞，并提供两侧的碰撞。
// This 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));
你也可以自动创建一个环。
// Create a loop. The first and last vertices are connected.
b2ChainShape chain;
chain.CreateLoop(vs, 4);
不支持自相交的链接形状。它可能正常工作，也可能不会。防止幽灵碰撞的代码假定链接中没有自相交存在。同样的，非常接近的顶点也会导致问题。需要确保你的所有边框都比b2_linearSlop (5mm)长。
链接中的每个边框都被认为是一个子形状，并能用索引来访问。当一个链接形状被连到body上时，每个边框在碰撞检测树上都会有它自己的包围盒（bounding box）。
// Visit each child edge.
for (int32 i = 0; i < chain.GetChildCount(); ++i)
{
b2EdgeShape edge;
chain.GetChildEdge(&edge, i);
…
}
4.3 单元几何查询（Unary Geometric Queries）
你可以在一个单独的形状上，执行一系列的几何查询。
形状点测试（Shape Point Test）
你可以测试一个点是否与形状有所重叠。你需要提供一个形状的变换以及世界坐标上的一个点。
b2Transfrom transform;
transform.SetIdentity();
b2Vec2 point(5.0f, 2.0f);
bool hit = shape->TestPoint(transform, point);
边框和链接形状总是返回false，即使链接是一个环。
形状的光线投射(Shape Ray Cast)
你可以用光线射向形状，得到它们之间的第一个交点和法向量。如果在形状内部开始投射，就当成没有交点。链接形状包含儿子索引，是因为光线投射一次只会检测一个边框。
b2Transfrom 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);
…
}
4.4 对等函数
碰撞模块包含一些对等函数，它们接受一对形状参数，并计算出结果。这些函数包括：
• 重叠
• 接触形
• 距离
• 撞击时间
重叠
你可以用这个函数测试两个形状是否重叠。
b2Transform xfA = …, xfB = …;
bool overlap = b2TestOverlap(shapeA, indexA, shapeB, indexB, xfA, xfB);
如果是链接形状的话，你还必须提供子形状的索引。
接触形（Contact Manifolds）
Box2D有一些用来计算重合形状之间的接触点的函数。考虑一下圆与圆，圆与多边形的碰撞，我们只会得到一个接触点和一个向量。多边形与多边形的碰撞，我们可 以得到两个接触点。这些接触点具有相同的法向量，所以Box2D将它们归成一组，构成manifold结构。接触求解器将利用这个结构，以改善堆叠的稳定性。
通常你不需要直接计算接触形，但你可能会使用在模拟过程中已处理好的结果。
b2Manifold结构含有一个法向量和最多两个接触点。向量和接触点都是相对于局部坐标系。为方便接触求解器处理，每个接触点都存储了法向冲量和切向(摩擦）冲量。
存储在b2WorldManifold结构中的数据为内部使用做了优化。如果你需要这些数据，最好的方法是使用b2WorldManifold结构生成世界坐标下的接触向量和点。你需要提供b2Manifold结构和形状的转换及半径。
b2WorldManifold worldManifold;
worldManifold.Initialize(&manifold, transformA, shapeA.m_radius,
transformB, shapeB.m_radius);
for (int32 i = 0; i < manifold.pointCount; ++i)
{
b2Vec2 point = worldManifold.points[i];
…
}
注意worldmanifold使用的点数量来自于manifold.
模拟过程中，形状会移动而manifold可能会改变。接触点有可能会添加或移除。你可以使用b2GetPointStates来检查状态。
b2PointState state1[2], state2[2];
b2GetPointStates(state1, state2, &manifold1, &manifold2);
if (state1[0] == b2_removeState)
{
// process event
}
距离
b2Distance函数可以用来计算两个形状之间的距离。距离函数需要两个形状都被转成b2DistanceProxy。重复调用距离函数的时候，Box2D会使用缓冲的方式使之热启动。你可以在b2Distance.h 中看到实现的细节。
(译注：热启动是相对于冷启动而言的。一般情况下，机器热启动时，由于初始化的东西较少，而具有更快的速度。这里将机器热启动的概念，拓展推广到函数热启动，含义都是类似的。)
撞击时间
如果两个形状快速移动，它们可能会在一个时间步内穿过对方。
b2TimeOfImpact函数用于确定两个形状运动时碰撞的时间。这称为撞击时间(time of impact, TOI)。b2TimeOfImpact的主要目的是防止隧穿效应。特别是，它设计来防止运动的物体隧穿过静态的几何形状。
这个函数考虑了形状的旋转和平移，但如果旋转足够大，这函数还是会错过碰撞。函数仍然会报告一个非重叠的时间，并捕捉到所有的平移碰撞。
撞击时间函数定义了一条初始的分离轴，并确保形状没有越过这条轴。这可能会在最终位置错过一些碰撞。尽管如此，这种方法在防止隧穿方面已经快速并足够适用了。
很难去限定旋转角的范围，有些情况下，就算是很小的旋转角也会导致错过碰撞。通常，就算错过了一些碰撞，也不会影响到游戏的好玩性。游戏往往会忽略这些碰撞。
这函数需要两个形状(转换成b2DistanceProxy)和两个b2Sweep结构。b2Sweep结构定义了形状的开始和结束时的转换。
你可以在固定旋转角的情况下去执行这个计算撞击时间的函数，这样就不会错过任何碰撞。
4.5 动态树
Box2D使用b2DynamicTree来高效地组织大量的形状。这个类并不知道形状的存在。取而代之，它通过用户数据指针来操作轴对齐包围框(AABB)。
动态树是分层的AABB树。树的每个内部节点都有两个子节点。叶子节点是用户的AABB。这个树使用旋转来保持树的平衡，即使是在退化的输入（degenerate input）的情况下。
(译注：degenerate input在算法上是指最坏情况的输入。例如要对一个数组进行升序排列。通常情况下的输入，一般是随机的数字序列。而一个降序的数字序列在这里就算是degenerate input了。)
这种树结构支持高效的光线投射(ray casts)和区域查询(region queries)。比如，场景中有数百个形状，你想对场景执行光线投射，如果采用蛮力，就需要对每个形状都进行投射。这是很低效的，并没有利用到形状的分布信息。替代方法是，你维护一棵动态树，并对树进行光线投射。在遍历树的时候，可以跳过大量的形状。
区域查询使用树来查找跟需查询的AABB有重叠的所有叶节点。这比蛮力算法高效得多，因为很多形状会被直接跳过。
通常你并不会直接用到动态树。你会通过b2World类来执行光线投射和区域查询。如果你想创建自己的动态树，你可以去看看Box2D是怎么使用动态树的。
4.6 Broad-phase
物理步内的碰撞处理可以分成两个阶段: narrow-phase和broad-phase。narrow-phase时，我们去计算两个形状之间的接触点。假设有N个形状，使用蛮力算法的话，就需要执行 N*N/2次narrow-phase。
Tb2BroadPhase类使用了动态树来减少管理数据方面的开销。这可以大幅度减少narrow-phase的调用次数。
通常你不会直接和broad-phase交互。Box2D自己会在内部创建并管理broad-phase。另外要注意，b2BroadPhase是设计用于Box2D中的物理模拟，它可能不适合处理其它情况。