Oh!Coder

Coding Life

第四章 碰撞模块

| Comments

声明:此文章翻译自Box2D v2.2.0用户手册,仅供学习参考。

4.1 关于

碰撞模块包括了形状以及操作形状的方法。模块也包括了动态树(dynamic tree)和broad-phase算法来提高大系统碰撞检测的速度。

碰撞模块的设计独立于动力学系统之外。例如,你可以在游戏中除了物理系统之外的其他方面单独使用动态树(dynamic tree)。

4.2 形状

形状描述了碰撞几何体,在物理模拟中可独立使用,你可以对形状进行多种操作。

b2Shape作为Box2D形状的基类,定义了如下方法:

  • 判断一个点是否与形状重叠
  • 向形状投射一条射线
  • 计算形状的AABB
  • 计算形状的质量属性

另外,每一个形状有一个类型成员和对应的半径。半径甚至会应用于多边形中,下面还将会对此进行讨论。

4.3 圆形(Circle Shapes)

圆形有坐标点和半径。

圆形是实心的。你不能够创建一个空心的圆形。即便如此,你还可以使用多边形形状来创建线段链。

1
2
3
b2CircleShape circle;
circle.m_p.Set(2.0f, 3.0f);
circle.m_radius = 0.5f;

4.4 多边形(Polygon Shapes)

多边形形状是实心凸多边形。所谓一个多边形为凸多边形,即多边形上所有线段中任意两个顶点间的连线都与此多边形的边无交点。多边形是实心的,永远都不会是空心。一个多边形至少需要由3个或更多顶点组成。

pic

你必须按照逆时针(counter clockwise winding,CCW)的方向创建一个多边形。对于这一点我们需要小心,逆时针是相对于右手坐标系统而言的,其中z轴指向平面外面。在你的屏幕上可能是顺时针方向,这取决于你的坐标系统是如何约定的。

pic

虽然多边形的成员变量的访问权限是public,但是你仍然需要使用相应的初始化方法来创建一个多边形。初始化方法会创建法向量并验证其合法性。

你可以通过一个顶点数组来创建多边形。数组的最大值被b2_maxPolygonVertices所控制,它的默认值是8,这足以描述大多数凸多边形。

1
2
3
4
5
6
7
8
//This defines a triangle in CCW order.
b2Vec2 vertices[3];
vertices[0].Set(0.0f, 0.0);
vertices[1].Set(1.0f, 0.0f);
vertices[2].Set(0.0f, 1.0f);
int32 count = 3;
b2PolygonShape polygon;
polygon.Set(vertices, count);

多边形有一些定义好的创建盒子(boxes)的初始化方法。

1
2
void SetAsBox(float32 hx, float32 hy);
void SetAsBox(float32 hx, float32 hy, const v2Vec2& center, float32 angle);

多边形从b2Shape继承了半径。半径围绕多边形创建了一个外壳(skin)。在多边形重叠的情况下,外壳可以保持多边形之间短距离分离。这使得核心多边形(译者注:外壳包裹着的多边形)可以进行持续碰撞。

pic

多边形的外壳可以通过保持多边形的分离防止隧道效应(译者注:所谓隧道效应就是在单个时间步长内两个多边形瞬间互相穿透的情况,示意图可见4.13)的发生。两个形状之间存在细微的差距。多边形会隐藏任何细微的差距,在你的眼前只会有更大的视觉范围。

pic

4.5 边缘形状(Edge Shape)

边缘由多条线段组成。它可以自由的让你为游戏创建一个静态的环境。边缘形状的一个主要限制是不能和自己进行碰撞检测,只能与圆形和多边形进行碰撞检测。Box2D中使用的碰撞算法涉及到的两个碰撞形状中至少有一个形状要有体积(volume)。边缘形状没有体积,所以边缘与边缘之间不能够进行碰撞。

1
2
3
4
5
//This an edge shape.
b2Vec2 v1(0.0f, 0.0f);
b2Vec2 v2(1.0f, 0.0f);
b2EdgeShape edge;
edge.Set(v1, v2);

在很多游戏环境中,会把多个边缘形状的点与点之间进行首尾连接。当一个多边形沿着边缘链滑动的时候会出现莫名其妙的效果。在下图中我们看到一个盒子正要和内部顶点进行碰撞。一个幽灵(ghost)碰撞借此将会发生,当盒子与内部顶点进行相撞的同时,会产生一个内部碰撞法向量。

pic

如果edge1不产生这次碰撞看起来效果会很好。但是当前的edge1产生的这个碰撞看起来就像是一个bug。但是正常情况下Box2D中两个形状的碰撞,看起来就像是把两个形状进行了隔离。

幸运的是,边缘形状提供了通过存储相邻的幽灵(ghost)顶点机制来消除幽灵(ghost)碰撞。Box2D使用存储后的幽灵(ghost)顶点来防止内部碰撞。

pic

1
2
3
4
5
6
7
8
9
10
11
//This 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;

一般情况下,将边缘形状拼接在一起这种方法看起来有些浪费和繁琐。这也将引出我们下一个形状类型。

4.6 链形状(Chain Shapes)

链形状提供了一种高效的方法来同时连接多条边儿,从而为你的游戏创建静态的游戏世界。链形状自动消除幽灵(ghost)碰撞并提供了两面碰撞。

pic

1
2
3
4
5
6
7
8
//This a chain shape with isolated vertices
b2Vec2 vs[4];
vs[0].Set(1.7f, 0.0f);
vs[1].Set(1.0f, 0.25);
vs[2].Set(0.0f, 0.0f);
vs[3].Set(-1.7f, 0.4f);
b2ChainShape chain;
chain.CreateChain(vs, 4);

你也许有一个可以滚屏的游戏世界并且希望把几条链连接在一起。你可以使用幽灵(ghost)顶点把这些链连接在一起,就像使用b2EdgeShape一样。

1
2
3
//Install ghost vertics
chain.SetPrevVertex(b2Vec2(3.0f, 1.0f));
chain.SetNextVertex(b2Vec2(-2.0f, 0.0f));

你也可以自动创建一个环状连接。

1
2
3
//Create a loop. The first and last vertices are connected.
b2ChainShape chain;
chain.CreateLoop(vs, 4);

其实并不支持链形状的自相交(self-intersection)。这可能正常工作,也可能不能正常工作。代码为了防止幽灵(ghost)碰撞,假设链形状没有自相交。

pic

链形状的每一条边都被看做是一个子形状,并且可以通过索引进行访问。

1
2
3
4
5
6
7
//Visit each child edge.
for(int32 i = 0;i < chain.GetChildCount(); ++i)
{
    b2EdgeShape edge;
    chain.GetChildEdge(&edge, i);
    ...
}

4.7 形状的点测试(In Shape Point Test)

你可以测试一个点是否与形状有重叠。你需要为形状提供一个转换矩阵和所要测试的点。

1
2
3
4
b2Transform transform;//译者注:此处原版手册有误:b2Transfrom
transform.SetIdentity();
b2Vec2 point(5.0f,  2.0f);
bool hit = shape->TestPoint(transform, point);

边缘和链形状总是返回false,即便链形状是环路形状。

4.8 形状的光线投射(Shape Ray Cast)

你可以使用光线射向形状来获得第一个交点和法向量。如果光线的起点在形状内部,就不能算作有交点。因为射向链形状的射线每次只是检测一条边,所以链形状中包含一个孩子索引(child index)。

1
2
3
4
5
6
7
8
9
10
11
12
13
b2Transform  transform; //译者注:此处原版手册有误:b2Transfrom
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;
b2RayCastOutput output;
bool hit = shape->RayCast(&output,input,transform,childIndex);
if(hit)
{
    b2Vec2 hitPoint=input.p1+output.fraction*(input.p2-input.p1);
    ...
}

4.9 对等方法(Bilateral Functions)

碰撞模块包含了一些对等方法,对等方法每次需要传入一对形状,然后会得出相应结果。这些对等方法包括:

  • 重叠(Overlap)
  • 接触取样(Contact manifolds)
  • 距离(Distance)
  • 撞击时间(Time of impact)

4.10 重叠(Overlap)

使用下面的方法你可以对两个形状进行测试:

1
2
b2Tranform xfA = ..., xfB = ...;
bool overlap = b2TestOverlap(shapeA,indexA,shapeB,indexB,xfA,xfB);

还有你必须为链形状中每一个事例提供相应的子索引。

4.11 接触取样(Contact Manifolds)

Box2D有方法来计算重叠的形状之间的接触。例如我们考虑圆与圆或者圆与多边形,我们只能得到一个接触和法向量。多边形与多边形我们可以得到两个接触。因为这两个接触共享同一个法向量,所以Box2D把它们分组到了同一个取样(manifold)结构里。接触求解器(contact solver)利用这个结构体来改进堆的稳定性。

pic

一般情况下你不需要直接对接触取样进行计算,但是你可能会喜欢模拟过程中产生的结果。

b2Manifold结构存储了一个法向量和相应的两个接触。法向量和接触以局部坐标系进行存储。为方便接触求解器处理,每一个点存储了法向冲量和切向(摩擦力)冲量。

存储在b2Manifold结构中的数据被内部有效的使用。如果你需要这些数据,最好的办法是通过b2WorldManifold结构生成世界坐标系的法向量和坐标。为此,你需要提供b2Manifold结构和b2Transform结构以及半径。

1
2
3
4
5
6
7
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];
    ...
}

模拟过程中形状可能会移动位置,取样可能会改变。接触可能会被添加或移除。你可以使用b2GetPointStates来进行检测。

1
2
3
4
5
6
b2PointState state1[2], state2[2];
b2GetPointStates(state1, state2, &manifold1, &manifold2);
if(state1[0] == b2_removeState)
{
    //process event
}

4.12 距离(Distance)

b2Distance方法可以被用来计算两个形状之间的距离。使用此方法需要把两个形状转换成一个b2DistanceProxy。为了提高内部调用的效率,在外部开始调用b2Distance方法时,内部做了一个缓冲,以提高计算两个形状之间距离最近点的效率。详细可以参见b2Distance.h头文件。

pic

4.13 撞击时间(Time of Impact)

如果两个形状快速移动,它们可能在一个时间步长内彼此穿越对方。

pic

b2TimeOfImpact用来确定当两个形状运动时的冲撞时间。这称为撞击时间(time of impact,TOI)。b2TimeOfImpact方法主要是预防隧道效应。特别是为了防止运动中的物体和静态几何体发生隧道效应,避免冲到几何体的外面。

此方法考虑到了两个形状的旋转和平移,不管怎样,如果旋转过大,方法依然可能会丢失碰撞。尽管如此,此方法仍然会报告无重叠时间并且捕获所有平移碰撞。

撞击方法标注了一个简易的分离轴来确保形状不会和此轴交叉。很明显在最终位置这会丢失一些碰撞。虽然这种方式可能会丢失碰撞,但是它运行很快,并且能充分预防隧道效应。

pic

pic

很难对旋转角度的大小做一个限制。有可能在小角度旋转的地方丢失碰撞。一般情况下,旋转碰撞的丢失不会影响游戏的体验。

方法需要两个形状(转换成b2DistanceProxy)和两个b2Sweep结构体。b2Sweep结构体定义了形状开始和结束之间的转换。

你可以使用固定的旋转角度来展示一个形状演员(shape cast)。这样,撞击时间方法将不会丢失任何碰撞。

4.14 动态树(Dynamic Tree)

Box2D使用b2DynamicTree类来有效的组织大量的形状。此类并不知道形状是什么。相反,使用用户数据(user data)指针来操纵轴对齐包围盒(axis-aligned bounding boxes,AABBs)。

动态树继承自AABB树。树上的每一个节点都有两个孩子。叶节点是一个单独的用户(user)AABB。即便是惰性输入(degenerate input),整个树也可以使用旋转保持平衡。

树结构支持高效的光线投射(ray casts)和区域查询(region queries)。例如,你可以在你的场景中使用数百个形状。你可以尝试使用一条光线强行照射场景里的每一个形状。这会是低效的,因为这没有利用被分开了的形状。相反,使用动态树并且让光线投射到树上。射到树上的光线则会跳过大量的形状。

区域查询(region query)使用树来找到和AABB有重叠的所有叶节点。这比直接遍历的方法更加高效,因为跳过了很多形状。

pic

pic

一般情况下你将不会直接使用动态树。相比而言,你会通过使用b2World类来实现光线投射(ray casts)和区域查询(region queries)。如果你计划创建自己的动态树,你可以通过看看Box2D如何使用动态树。

4.15 Broad-phase

在一个物理步长内,碰撞处理可以被划分成narrow-phase和broad-phase两个阶段。在narrow-phase阶段计算一对形状的接触。假设有N个形状,直接使用蛮力进行计算,我们需要调用N*N/2次narrow-phase算法。

b2BroadPhase类通过使用动态树降低了管理数据方面的开销。这极大的降低了调用narrow-phase算法的次数。

一般情况下,你不需要直接和broad-phase打交道。Box2D来内部来创建和管理broad-phase。另外,b2BroadPhase是使用Box2D的模拟循环的思路来设计的,所以它可能不适合用于其他用途。

Comments