-
简介
本文是阐述如何在
2D
动作游戏中进行精确而高效的碰撞检测。这里的碰撞是基于多边形而不是基于精灵
的。这两者之间
在设计上会有不同。
基于精灵的碰撞检测是通过精灵之间的重叠的像素来完成的。而多边形使用向量数学来精确计算交点，时间和碰撞
方向。
虽然多边形仅仅是精灵的一个近似，但是它比精灵系统要高级。
< br>
?
可以精确模拟逼真的简单物理学，例如反弹，摩擦，斜面的滑行
?
碰撞检测可以更精确的用于高速精
灵系统。在基于精灵的系统中，如果物体移动过快就会在跳过另一个物体。
?
基于向量数学因此可以扩展到
3D
，然而精灵碰撞系统被严格限制在
2D
的情况下。
特性
本文使用的算法只适用于凸多边
形，例如三角形，四边形，六边形，圆形。对于非凸多边形，你可以将其分解为多个凸多
边形，例如三角形。
算法可以用于快速移动或慢速移动的多边
形。不管物体移动多快，碰撞都不会丢失。它也可以处理重叠的问题，并促使交
叠物体分
离。
演示也支持分割多边形交叉。这可以用于子弹的建模。
同时提供了简单的物体系统，弹力，一些基本的摩擦和静摩擦力。用于确保物体不会从斜面上滑
落。
有一个刚体系统的例子，使用了
Chrsi
Hecker
的物理教程。
限制
有序碰撞。就是说并不是有序的
进行碰撞。这对于快速移动的物体会出现一定的问题。一旦碰撞被检测到，它就被直接处
理了。理想状态下你可能需要找到一个碰撞点并处理它，然后寻找更多的碰撞。但是对于
2D
动作游戏，这通常是不必要的。
一、分离坐标轴方法
这个方法是碰撞检测的核心。它的规则非常简单并且非常易于实现。
这个方法也非常快并且非常可靠，因为计算中没有使
用除法操作，下面给出一个简单的基
于两个
BOX
的碰撞检测的例子。
算法试图在两个物体之间找到一个合适平面，如果这个平面存
在，那么物体就没有相交。
为了测试物体是否是分开的，简单
的方法是投影这个物体到平面的法线上，并比较两者之间的间距看二者是否重叠。
显然有无数的平面可以用来分割两个物体。但是已经经过证明的是：你只需要使用一部分平面
来进行测试，对于
BOX
从
上图中可以
看出平面的法线为
BOX B
的长轴。
对于
BOX
来说需要测试的分割平面是
那些法线等于两个
BOX
的轴向的平面。因此对于两个
BOX
来说，你只需要测试
4
< br>个
分割平面即可。在这四个平面里，一旦发现一个分割平面可以分割
BOX
那么你就可以断定这两个
BOX
是不相交的。
如果四个平面都不能分割
BOX
，那么这两个
BOX
一定是相交的，也就是出现了碰撞。
可以扩展这个算法到普
通的多边形，算法是相同的，只用需要测试的平面的数量改变了。并且分割平面在每个多边形边的
垂直方向上又有一个法线。在下图中，你可以看到两个分割平面用于测试。在红色的平面上你可以看到两
个间隔是重叠的。然
而，在蓝色的平面上间隔是不重叠的，因此，蓝色的平面的是分割平
面，因此物体是不相交的。
现在，
我们有一个算法来检测两个多边形是否是相交的。代码可以分为三个部分：
a)
生成需要测试的分离轴
b)
计算每一个多边形在分离轴法线上的投影
c)
检测这些投影是否相交
bool
Intersect
(
Polygon
A
,
Polygon
B
)
{
for
(
I
=
0
;
I
<
A
.
nu
m_edges
;
I
++)
{
Vector N
=
Vector
(-
A
.
Ed
geDir
[
I
].
< br>y
,
A
.
EdgeDir
[
I
].
x
);
if
(
AxisSeparatePolygons
(
N
,
A
,
B
))
returnfalse
;
}
for
(
I
=
0
;
I
<
B
.
nu
m_edges
;
I
++)
{
Vector N
=
Vector
(-
B
.
Ed
geDir
[
i
].
< br>y
,
B
.
EdgeDir
[
I
].
x
);
if
(
AxisSeparatePolygons
(
N
,
A
,
B
))
returnfalse
;
}
returntrue
;
}
void
CalculateInterval
(
Vector
Axis
,
Polygon P
,<
/p>
float
&
min
< br>,
float
&
max
)
{
float
d
=
Axis dot P
.
vertex
[
0
];
//
从坐标原点开始计算向量
min
=
max
=
d
;
for
(
I
=
0
;
I
<
P
.
nu
m_vertices
;
I
++)
{
float
d
=
P
.
ve
rtex
[
I
]
dot Axis
;
if
(
d
<
min
)
min
=
d
;
elseif
(
d
>
max
)
max
=
d
;
}
}
算法检测
2D
多边形之间的碰撞，这个算法非常的快速和适用。边的方向不需要单位化，因此你可
以避免存贮边的方向，
并通过多边形的顶点直接得到边的方向。
for
(
J
=
A
.
nu
m_vertices
-
1
,
I
=
0
;
I
<
A
.
nu
m_vertices
;
J
=
I
,
I
++)
{
Vector E
=
A
.
vertex
[
I
]
- A
.
v
ertex
[
J
];
< br>
Vector N
=
Ve
ctor
(-
E
.
y
,
E
.
x
);
if
(
AxisSeparatePo
lygons
(
N
,
< br> A
,
B
))
returnfalse
;
}
二、用于碰撞响应的扩展分离坐标轴方法
检测多边形相交是非常有用的方法，但是可以做更多的事情。当多边形相交时，我想将他们移开以避免他们相 交。
分离轴的方法可以非常好的用于这种情况，但是还需要作
一些额外的工作。必须返回相交的深度，和推开多边形将它们分
离的方向。相交的深度和
方向的组合称为
MTD
，或者最小平移距离。这是用于将物体分
离的的最小向量。
为了计算
MTD<
/p>
，我们可以使用分离坐标轴。
当物体
相交时，我们可以计算两个物体在每一个分离轴上的投影间隔。两个间隔交叠的部分提供了一个推动向量，你需要
将其应用到其中一个物体上以便物体在轴上的投影停止交叠
“推动向量”你需要应用于
A
上将
A
推开，这样就可以使
< br>A
和
B
分开。
< br>
显然，不能沿着一个随机的轴来推开物体。候选轴是投影在该轴上两个间隔之间
交叠最小的那个。并且这个推动向量提供
了最小平移距离。
bool
Intersect
(
Polygon
A
,
Polygon
B
,
Vector
&
MTD
)
{
//
电位分离轴。他们被转换成推动
vectors Vector Axis
[
32
];
//
每个多边形最大的
16
个顶点的
int
iNumAxis
=
0
;
for
(
J
=
A
.
num_vertices -
1
,
I
=
0
;
I
<
A
.
num_vertices
;
J
=
I
,
I
++)
{
Vector E
=
A
.
vertex
[
I
]
- A
.
v
ertex
[
J
];
< br>
Axis
[
iNumAxis
++]=
Vector
(-
E
.
y
< br>,
E
.
x
);
if
(
AxisSeparatePo
lygons
(
N
,
< br> A
,
B
))
returnfalse
;
}
for
(
J
=
B
.
num_vertices - 1
,
I
=
0
;
I
<
B
.
nu
m_vertices
;
J
=
I
,
I
++)
{
Vector E
=
B
.
vertex
[
I
]
- B
.
v
ertex
[
J
];
< br>
Axis
[
iNumAxis
++]=
Vector
(-
E
.
y
< br>,
E
.
x
);
if
(
AxisSeparatePo
lygons
(
N
,
A
,
B
))
returnfalse
;
}
//
找到所有的分离向量之间的
MTD
MTD
=
FindMTD
(
Axis
,
iNumAxis
);
//
确保将向量
a
< br>推动远离
b
Vector D
=
A
.
Position - B
.
Position
;
if
(
D dot MTD
<
0.0f
)
MTD
=-
MTD
;
returntrue
;
}
bool
AxisSeparatePolygons
(
Vector
&
Axis
,
Polygon
A
,
Polygon
B
)
{
float
mina
,
maxa
;
float
minb
,
maxb
;
Calcu
lateInterval
(
Axis
,
A
,
mina
,
maxa
);
Calc
ulateInterval
(
Axis
,
B
,
minb
,
maxb
);
if
(
mina
>
maxb
||
minb
>
maxa
)
returntrue
;
//
查找间隔重叠
float
d0
=
maxa
-
minb
;
float
d1
=
maxb
-
mina
;
float
depth
=(
d0
<
d1
)?
d0
:
d1
;
//
将分离轴为推力矢量（重新恢复正常的轴乘区间重叠）
float
axis_length_squared
=
Axis
dot Axis
;
Axis
*=
depth
/
axis_length_squared
;
returnfalse
;
}
Vector FindMTD
(
Vector
*
PushVectors
,
int
iNumVectors
)
{
Vector
MTD
=
PushVector
[
0
];
float
mind2
=
PushVector
[
0
]
dot PushVector
[
0
];
for
(
int
I
=
1
;
I
<
iNumVectors
;
I
++)
{
float
d2
=
PushVector
[
I
]*
PushVector
[
I
];
if
(
d2
<
mind2
)
{
mind2
=
d2
;
MTD
=
PushVector<
/p>
[
I
];
}
}
return
MTD
;
}
一旦得
到了
MTD
向量，可以使用如下的方式将他们分开。
n
+=
MTD
*
0.5f
;
B
.
Position
-=
MTD
*
0.5f
;
显然，如果物体
A
是静态的，那么
B
将被完全的
MTD
推开（
on-=MTD
）而
A
将不会被推开。
三、对快速移动的物体做进一步扩展
上述方法处理慢速移动物体时会取得非常好的效果。但是当物体移动的非常快时，碰撞系统将失去准确性，丢失碰
撞，或
者允许物体之间相互穿越，这可不是我们所期望的。
这里我们还是使用分离坐标轴的方法，并进一步扩展，并使
用该算法检测未来某时刻的碰撞和交叠。
原理还是相同的，可以使用下面的图片解释：
现在需要使用投影数学。如果投影间隔没有相交，将速度投影
到分离轴上，并计算两个间隔的碰撞时间。
相对于静态分离轴算法，我们需要测试一个扩展的轴。显然这个是速度矢量轴。
那么我们现在有
3
个选择：
1
．
间隔交叠
2
．
间隔不相交，但是将在未来某个时刻发生碰撞
3
．
间隔不相交，并且不会在未来发生碰撞
第三种可能性意味着物体不会在该帧处发生碰撞，而且分离轴真正分离了物体。因此物体不会发生碰撞。
AxisSeparatePolyg
ons()
函数将反映这种现象，并返回重叠量或者碰撞时间。为了区别两者，当检测到
交叠时，将返
回一个负值。如果检测到未来的碰撞，将返回一个正值。该函数看起来如下
：
bool
AxisSeparatePolygons
(
Vector
Axis
,
Polygon
A
,
Polygon
B
,
Vector
Offset
,
Vector Vel
,
float<
/p>
&
t
,
float
tmax
);
这里
Offset
< br>是多边形
A
和多边形
B
之间的相对距离，并且
Vel
是多边形
A
相对于多边形
B
的相
对速度。
求解碰撞平面的算法与
MTD
非常相似。只是碰撞将优于交叠，如果检测到未来的碰撞
，将选择最新的一个。
如果没有
发现碰撞并且只检测到了交叠，那么就像以前一样，选择交叠最小的那个轴。
碰撞检测函数将返回碰撞的法向，还有碰撞的深度（负值）
和碰撞时间（正值）之一。最后的伪代码如下…
bool
Collide
(
const
Vector
*
A
,
int
Anum
,
const
Vector
*
B
,
int
Bnum
,
const
Vector
&
xOffset
,
const
Vector
&
xVel
,
Vector
&
N
,
float
&
t
)
{
if
(!
A
||!
B
)
returnfalse
;
// All the
separation axes
//
note : a maximum of 32 vertices per poly is
supported
Vector
xAxis
[
64
];
float
taxis
[
64
];
int
iNumAxes
=
0
;
xA
xis
[
iNumAxes
]=
Vector
(-
xVel
.
y
,
xVel
.
x
);
float
fVel2
=
xVel
*
xVel
;
if
(
fVel2
< br>>
0.00001f
)
{
if
(!
IntervalIntersect
(
A
,
Anum
,
B
,
Bnum
,
xAxis
[
iNumAxes
],
t
))
returnfalse
;
iNumAxes
++;
}
//
测试分离轴
A
<
/p>
for
(
int
j
=
Anum
-
< br>1
,
i
=
0
;
i
<
Anum
;
j
=
i
,
i
++)
{
Vector E0
=
A
[
j
];
Vector E1
=
A
[
i
];
Vector E
=
E1
-
E0
;
xA
xis
[
iNumAxes
]=
Vector
(-
E
.
y
,
E
.
x
);
if
(!
I
ntervalIntersect
(
A
,
Anum
,
B
,
Bnum
,
xAxis
[
iNumAxes
],
t
))
returnfalse
;
iNumAxes
++;
,
,
,
taxis
[
iNumAxes
],
,
taxis
[
iNumAxes
],
xOffset
xVel
xOffset
xVel
}
//
测试分离轴
B
<
/p>
for
(
int
j
=
Bnum
-
< br>1
,
i
=
0
;
i
<
Bnum
;
j
=
i
,
i
++)
{
Vector E0
=
B
[
j
];
Vector E1
=
B
[
i
];
Vector E
=
E1
-
E0
;
xA
xis
[
iNumAxes
]=
Vector
(-
E
.
y
,
E
.
x
);
if
(!
IntervalIntersect
(
A
,
Anum
,
B
,
Bnum
,
xAxis
[
iNumAxes
],
xOffset
,
xVel
,
t
))
returnfalse
;
iNumAxes
++;
}
if
(!
FindMTD
(
xAxis
,
taxis
,
iNumAxes
,
N
,
t
))
returnfalse
;
//
确保多边形被彼此推开。
if
(
N
*
xOffset
<
0.0f
)
N
=-
N
;
returntrue
;
}
bool
AxisSeparatePolygons
(
Vector
N
,
Polygon
A
,
Polygon
B
,
Vector
Offset
,
Vector Vel
,
float
&
t
< br>,
float
tmax
)
{
float
min0
,
max0
;
float
min1
,
max1
;
Ca
lculateInterval
(
N
,
A
,
min0
,
max0
);
Ca
lculateInterval
(
N
,
B
,
min1
,
max1
);
float
h
=
Offset dot
N
;
min0
+=
h
;
max0
+=
h
;
float
d0
=
min0
-
max1
;
//
如果重叠
, do < 0
<
/p>
taxis
[
iNumAxes
],
float
d1
=
min1
-
max0
;
//
如果重叠
, d1 > 0
//
分离，测试动态间隔
if
(
d0
>
0.0f
||
d1
>
0.0f
)
{
float
v
=
Vel dot
N
;
//
速度很小，所以只能进行重叠测试。
if
(
f
abs
(
v
)<
0.0000001f
)
returnfalse
;
float
t0
=-
d0
/
v
;
//
时间影响
D0
达到
0
float
t1
=
d1
/
v
;
//
时间影响
D0
达到
1
//
排序时间。
if
(
t0
>
t1
)
{
float
temp
=
t0
;
t0
=
t1
;
t1
=
temp
;
}
//
取最小值
taxis
=(
t0
>
0.0f
)?
t0
:
t1
;
//
交叉时间太晚或时间，没有碰撞
if
(
taxis
< br><
0.0f
||
taxis
>
tmax
)
returntrue
;
returnfalse
;
}
else
{
//
重叠。得到的区间，作为
最小的
|D0|
和
|D1|
//
返回负数以标记为重叠
taxis
=(
d0
>
d1
)?
d0
:
d1
;
returnfalse
;
-
-
-
-
-
-
-
-
-
上一篇：创建一个无向图并统计每个顶点的度
下一篇：常用数学术语的英语表达