对于Moba游戏来说,碰撞检测是重要的组成部分。王者用的SAT。
这个简单,判断两个球心的距离 和 两个球的半径之和 的大小。
public override bool VCollisionSphere.Intersects(VCollisionSphere s)
{
ConditionalUpdateShape();
s.ConditionalUpdateShape();
//判断球心的距离和半径的
long num = worldRadius + s.worldRadius;
return (worldPos - s.worldPos).sqrMagnitudeLong <= num * num;
}
先说结论:找到盒子中离球心最近的点的距离,判断是否大于球的半径即可。
原理:球可以看成以球心为中心、半径为 R 的所有点的集合。只要盒子中存在一个点落在球内,就说明球和盒子发生了碰撞。
如何找到呢?
假设有一条线段(a,b),有一个点p(x),怎么找到这条线段上离点p最近的点呢?
先看第一种情况:
1 4 5
不难看出最近的点是4
再看第二种情况:
4 5 8
不难看出最近的点是8
再看第三种情况(点p是6):
4 6 10
不难看出最近的点是6
那有什么算法能准确而不是“不难看出”呢?
有一种算法,我们先取线段(a,b)的中点m,获得从m到p的向量n=(p-m);
然后从起始点m出发,朝着向量n的方向行走,努力靠近p点,来成为最近点,但是行走到了线段边界就不能再行走。
4 5的中点m(4.5),朝着1方向走,走到边界4。
4 5的中点m(4.5),朝着8方向走,走到边界5。
4 10的中点m(7),朝着6方向走,最终走到了6。
为什么要是中点?因为在不确定最近点的情况下,中点的平均行走距离是适中的。
代码如下
float ClosestPoint(float a,float b,float p){
//找到中心点
var m = (a + b) / 2;
//找到前进方向
var n = Normalize(p - m);
//尝试从中心点沿着方向往前走,直到走到目标点或者碰到边界
while(true){
//dx足够小
seek += n * dx;
if(seek == p)
return seek;
if(seek < a)
return a;
if(seek > b)
return b;
}
}
//更简化的方法
//直接找到需要前进方向和想要前进的距离
var n = p - m;
//直接看距离是否被边缘卡住
return Clamp(m + n , a , b);
}
给定一个矩形和目标点,怎么找到矩形中离目标点最近的那个点呢?
同样的思想,我们找到矩形中心点,分别按照矩形的两个方向努力朝着目标点走,直到走到了或者碰到了边界。
代码如下
Vector2 ClosestPoint(Vector2 center,Vector2 extends,Vector2 axis0,Vector2 axis1,Vector2 target){
//指向的向量
var len = target-center;
//从中心点努力朝着0轴走
var move0 = Dot(len,axis0);
//然后clamp到边界,得到位移
move0 = Clamp(move0,-extends.x,extends.x);
//进而得到目标点
var pos0 = move0 * axis0;
//从中心点努力朝着1轴走
var move1 = Dot(len,axis1);
//然后clamp到边界
move1 = Clamp(move1,-extends.y,extends.y);
//进而得到目标点
var pos1 = move1 * axis1;
//结果就是
return center + pos0 + pos1;
}
其实和二维的差不多,只不过轴多了一条。
public VInt3 VCollisionBox.ClosestPoint(VInt3 targetPoint)
{
//找到到目标的向量
VInt3 lhs = targetPoint - worldPos;
//中心点
VInt3 vInt = worldPos;
//盒子的三条边的一半
int num = worldExtends.x * 1000;
int num2 = worldExtends.y * 1000;
int num3 = worldExtends.z * 1000;
//先沿着axis[0]轴走,clamp到-x和x,找到沿着这根轴要走多远
//然后再乘axis[0],或者走之后的结果
//加到中心点
vInt += IntMath.Divide(axis[0], Mathf.Clamp(VInt3.Dot(ref lhs, ref axis[0]), -num, num), 1000000L);
//axis[1]一样
vInt += IntMath.Divide(axis[1], Mathf.Clamp(VInt3.Dot(ref lhs, ref axis[1]), -num2, num2), 1000000L);
//axis[2]一样
return vInt + IntMath.Divide(axis[2], Mathf.Clamp(VInt3.Dot(ref lhs, ref axis[2]), -num3, num3), 1000000L);
}
public override bool VCollisionBox.Intersects(VCollisionSphere s)
{
ConditionalUpdateShape();
s.ConditionalUpdateShape();
//提前粗检测
//球的Radius就是半径
//盒的Radius就是三条边中最长的那条边的一半
_tempRadius = worldRadius + s.WorldRadius;
_tempDist = worldPos - s.WorldPos;
if (_tempDist.sqrMagnitudeLong > _tempRadius * _tempRadius)
{
return false;
}
//找到盒子中离球心最近的那个点
//如果那个点到球心的距离小于球的半径,则发生Intersect
VInt3 vInt = s.WorldPos;
long num = s.WorldRadius;
VInt3 vInt2 = ClosestPoint(vInt);
return (vInt - vInt2).sqrMagnitudeLong <= num * num;
}
假设是一维,如何判断两条线段是否相交呢?
假设两条线段分别为
Amin Amax Bmin Bmax
他们分离有两种情况
Amin Amax
Bmin Bmax
以及
Bmin Bmax
Amin Amax
不难得出,只要满足
Amax < Bmin或者Bmax<Amin
即可认定两条线段分离,否则相交。
代码如下:
bool SAT(Amin,Amax,Bmin,Bmax){
if(Amax < Bmin ||
Bmax < Amin){
return false;
}
return true;
}
那如果是二维呢?
这里我们直接用一个结论:
拿一根投影P,如果两个二维物体在这根投影P下的两条线段,分离,那么认为这两个二维物体也是分离的。
如果对于若干个(具体多少个后面会讲)投影P,都不分离,那么认为是不分离的。
代码如下
bool SAT(Obj objA,Obj objB){
//获取需要检测的全部投影P,我们认为都是单位向量
var projs = new();
projs.Add(GetProjs(objA));
projs.Add(GetProjs(objB));
//遍历全部投影P,检测是否分离
foreach(var p in projs){
if(!SAT(objA,objB,p)){
return false;
}
}
//如果都不分离,那么有相交
return true;
}
先看二维物体如何投影到P,这里P可以认为是一个方向向量(x,y)。
先看一个点A如何投影到P:
我们知道,两根向量的点乘的结果,就是一根向量在另一根向量的投影再乘这根向量的长度。由于P是方向向量,所以点乘的结果就是投影的长度。
假设一个点A(x,y),一个方向向量P(x,y),我们可以找到原点,原点到A是一根向量,原点到P是一根方向向量,于是点A到方向向量P的点乘就是
| A | P | Cosθ |
| 其中 | P | =1 |
其中也即(XAXP , YAYP)
代码如下:
Vector2 ProjPoint(Vector2 point,Vector2 p){
//这里约定p是单位向量
return point*p;
}
比如对于一个三角形来说,Tri(x1,y1,x2,y2,x3,y3),它的三个顶点在方向向量P(x,y)的投影分别是P0,P1,P2。于是这个三角形的投影的线段就是(Pmin,Pmax)
然后另一个三角形也依法炮制,得到两条线段,就退化成了判断一维是否相交。
代码如下:
bool SAT(Obj objA,Obj objB,Vector2 p){
//把每个顶点投影到p上
foreach(var t in objA.Triangles){
projsA.Add(ProjPoint(t,p));
}
//把每个投影投影到p上
foreach(var t in objB.Triangles){
projsB.Add(ProjPoint(t,p));
}
//得到两条线段,退化成了一维是否相交
return SAT(projsA.min,projsA.max,projsB.min,projsB.max);
}
判断几根投影P呢?这里我们直接用结论:对于二维物体来说,投影P只要包括所有边的法线即可。比如三角形,就是3个。比如四边形,就是4个。但是也存在几根投影P一样的,比如矩形的对边平行。
求法线也简单,先求边,就是(x1-x2,y1-y2)。再求法线,(x,y)的法线就是(-y,x)。(x,y)·(-y,x)=0。
对于投影P来说,不一定需要是单位向量,因为只是判断线段相对长度。
代码如下:
List<Vector2> GetProjs(Obj obj){
//依次遍历obj的每个顶点
for(int i=0;i<obj.Triangles.Count;i++){
//找到两个顶点连接的一条边
if(i == obj.Triangles.Count-1){
line = obj.Triangles[i] - obj.Triangles[0];
}else{
line = obj.Triangles[i] - obj.Triangles[i+1];
}
//根据边求出边的法线
var n = new Vector2(-line.y,line.x);
//根据需要是否进行归一化
n = n.normalized;
result.Add(n);
}
return result;
}
之前我们判断两个线段是否相交,是通过二者的min和max。
新方法,是找到两个线段的中心点m1和m2
再找到两个线段的一半长度(半径)r1和r2
| 于是只要 | m1-m2 | > r1+r2,二者就分离。 |
投影半径优化:传统计算投影半径的方法是,把二维物体所有顶点做投影,找到最小值和最大值,距离的一半就是投影半径。
对于矩形,可以进一步优化:
对于矩形,我们不需要分别求四个顶点的投影。因为矩形任意一个顶点相对于中心的位移,都可以由两个半边向量相加得到。根据点积的分配律,顶点在投影轴上的位置就等于两个半边向量投影之和。
我们知道,对于一个矩形来说,组成结构包括:
中心点c(x,y)
| 半边长度 | a | 和边方向a |
| 半边长度 | b | 和边方向b |
| 于是我们可以直接计算,从中心点,沿着方向a走 | a | 个长度,再沿着方向b走 | b | 个长度,等价于在投影P一共走了多少个长度(即投影半径)。 |
如何计算呢?
| a | abs((a · p)) + | b | abs((b · p)) |
再计算两个矩形的中心距离在p上的投影,即
abs((c2-c1) · p)
只要比较这两个的大小,即可
同样地,对于三维物体来说,朴实的做法是:
找到所有需要检测的投影P,包括:
A每个面的法向量
B每个面的法向量
以及A的所有边方向 × B的所有边方向
然后对于这些投影P,分别把三维物体的投影计算出来,就是把三维物体所有顶点求出在投影P的长度,然后找到最小值和最大值构成一条线段。
类似二维的做法,只需要找到中心点往a b c三条边方向走的长度和,在P上的投影,与二者中心距离在P上的投影比较即可。
另外,对于盒子来说,其轴更少,只需检测这些投影:
盒子A的三个面的法向量(等价于盒子A的三条轴方向);
盒子B的三个面的法向量(等价于盒子B的三条轴方向);
盒子A的三条轴方向 × 盒子B的三条轴方向 (共9个);
一共3+3+9 = 15条
于是:
代码如下
bool SAT(Obj objA,Obj objB){
//找到所有需要检测的投影
var projs = GetProjs(objA,objB);
//对于所有的投影,开始检测
foreach(var p in projs){
if(!SAT(objA,objB,p)){
return false;
}
}
return true;
}
bool SAT(Obj objA,Obj objB,Vector3 p){
//找到A的投影半径
var pa = 0;
pa += objA.worldExtends.x * Abs(Dot(objA.axis[0],p)); pa += objA.worldExtends.y * Abs(Dot(objA.axis[1],p));
pa += objA.worldExtends.z * Abs(Dot(objA.axis[2],p));
//找到B的投影半径
var pb = 0;
pb += objB.worldExtends.x * Abs(Dot(objB.axis[0],p)); pb += objB.worldExtends.y * Abs(Dot(objB.axis[1],p));
pb += objB.worldExtends.z * Abs(Dot(objB.axis[2],p));
//找到A和B的中心距离的投影长度
var distance = Abs(Dot(objA.center - objB.center,p));
return pa+pb < distance;
}
List<Vector3> GetProjs(Obj objA,Obj objB){
var result = new();
//这里可以归一化 也可以不归一化 不影响结果 因为比较的是相对值
result.Add(objA.axis[0]);
result.Add(objA.axis[1]);
result.Add(objA.axis[2]);
result.Add(objB.axis[0]);
result.Add(objB.axis[1]);
result.Add(objB.axis[2]);
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
result.Add(Cross(objA.axis[i],objB.axis[j]));
}
}
return result;
}
实际代码如下:
public bool VCollisionBox.IntersectsOBB(VCollisionBox b)
{
//必要的Shape更新,跟随其持有Actor的location和forward
ConditionalUpdateShape();
b.ConditionalUpdateShape();
//粗检测
//worldRadius是最长的那条边的一半
//worldPos就是中心点的世界坐标
//如果两个中心点距离都比最长边加起来还要大,说明不可能碰撞
long num = worldRadius + b.worldRadius;
if ((worldPos - b.worldPos).sqrMagnitudeLong > num * num)
{
return false;
}
//下面这些是化简后的算法,实际思想和上面一致
//保存3根轴*3根轴=9根的点积
VInt3 vInt = new VInt3(IntMath.Divide(VInt3.Dot(ref axis[0], ref b.axis[0]), 1000), IntMath.Divide(VInt3.Dot(ref axis[0], ref b.axis[1]), 1000), IntMath.Divide(VInt3.Dot(ref axis[0], ref b.axis[2]), 1000));
VInt3 vInt2 = new VInt3(IntMath.Divide(VInt3.Dot(ref axis[1], ref b.axis[0]), 1000), IntMath.Divide(VInt3.Dot(ref axis[1], ref b.axis[1]), 1000), IntMath.Divide(VInt3.Dot(ref axis[1], ref b.axis[2]), 1000));
VInt3 vInt3 = new VInt3(IntMath.Divide(VInt3.Dot(ref axis[2], ref b.axis[0]), 1000), IntMath.Divide(VInt3.Dot(ref axis[2], ref b.axis[1]), 1000), IntMath.Divide(VInt3.Dot(ref axis[2], ref b.axis[2]), 1000));
//取9根的绝对值
VInt3 rhs = vInt.abs;
VInt3 rhs2 = vInt2.abs;
VInt3 rhs3 = vInt3.abs;
//保存两个盒子的中心距离
VInt3 lhs = b.worldPos - worldPos;
//保存中心距离分别对三条轴的投影
lhs = new VInt3(IntMath.Divide(VInt3.Dot(ref lhs, ref axis[0]), 1000), IntMath.Divide(VInt3.Dot(ref lhs, ref axis[1]), 1000), IntMath.Divide(VInt3.Dot(ref lhs, ref axis[2]), 1000));
//接下来是15条轴的分别检测:
//num2是物体a 以物体a的x轴为投影 的投影半径
int num2 = worldExtends.x * 1000;
//num3是物体b 以物体a的x轴为投影 的投影半径
int num3 = VInt3.Dot(ref b.worldExtends, ref rhs);
//lhx.x就是中心距离对物体a的x轴为投影 的值
//进行比较
if (Mathf.Abs(lhs.x) * 1000 > num2 + num3)
{
return false;
}
//以物体a的y轴为投影
num2 = worldExtends.y * 1000;
num3 = VInt3.Dot(ref b.worldExtends, ref rhs2);
if (Mathf.Abs(lhs.y) * 1000 > num2 + num3)
{
return false;
}
//以物体a的z轴为投影
num2 = worldExtends.z * 1000;
num3 = VInt3.Dot(ref b.worldExtends, ref rhs3);
if (Mathf.Abs(lhs.z) * 1000 > num2 + num3)
{
return false;
}
//以物体b的x轴为投影
num2 = worldExtends.x * rhs.x + worldExtends.y * rhs2.x + worldExtends.z * rhs3.x;
num3 = b.worldExtends.x * 1000;
if (Math.Abs(lhs.x * vInt.x + lhs.y * vInt2.x + lhs.z * vInt3.x) > num2 + num3)
{
return false;
}
//以物体b的y轴为投影
num2 = worldExtends.x * rhs.y + worldExtends.y * rhs2.y + worldExtends.z * rhs3.y;
num3 = b.worldExtends.y * 1000;
if (Math.Abs(lhs.x * vInt.y + lhs.y * vInt2.y + lhs.z * vInt3.y) > num2 + num3)
{
return false;
}
//以物体b的z轴为投影
num2 = worldExtends.x * rhs.z + worldExtends.y * rhs2.z + worldExtends.z * rhs3.z;
num3 = b.worldExtends.z * 1000;
if (Math.Abs(lhs.x * vInt.z + lhs.y * vInt2.z + lhs.z * vInt3.z) > num2 + num3)
{
return false;
}
//下面是3x3=9个叉乘轴的投影
// A 在 Ax × Bx 上的投影半径
num2 = worldExtends.y * rhs3.x + worldExtends.z * rhs2.x;
// B 在 Ax × Bx 上的投影半径
num3 = b.worldExtends.y * rhs.z + b.worldExtends.z * rhs.y;
// 中心差在 Ax × Bx 上的投影,与两个半径之和比较
if (Mathf.Abs(lhs.z * vInt2.x - lhs.y * vInt3.x) > num2 + num3)
{
return false;
}
num2 = worldExtends.y * rhs3.y + worldExtends.z * rhs2.y;
num3 = b.worldExtends.x * rhs.z + b.worldExtends.z * rhs.x;
if (Mathf.Abs(lhs.z * vInt2.y - lhs.y * vInt3.y) > num2 + num3)
{
return false;
}
num2 = worldExtends.y * rhs3.z + worldExtends.z * rhs2.z;
num3 = b.worldExtends.x * rhs.y + b.worldExtends.y * rhs.x;
if (Mathf.Abs(lhs.z * vInt2.z - lhs.y * vInt3.z) > num2 + num3)
{
return false;
}
num2 = worldExtends.x * rhs3.x + worldExtends.z * rhs.x;
num3 = b.worldExtends.y * rhs2.z + b.worldExtends.z * rhs2.y;
if (Mathf.Abs(lhs.x * vInt3.x - lhs.z * vInt.x) > num2 + num3)
{
return false;
}
num2 = worldExtends.x * rhs3.y + worldExtends.z * rhs.y;
num3 = b.worldExtends.x * rhs2.z + b.worldExtends.z * rhs2.x;
if (Mathf.Abs(lhs.x * vInt3.y - lhs.z * vInt.y) > num2 + num3)
{
return false;
}
num2 = worldExtends.x * rhs3.z + worldExtends.z * rhs.z;
num3 = b.worldExtends.x * rhs2.y + b.worldExtends.y * rhs2.x;
if (Mathf.Abs(lhs.x * vInt3.z - lhs.z * vInt.z) > num2 + num3)
{
return false;
}
num2 = worldExtends.x * rhs2.x + worldExtends.y * rhs.x;
num3 = b.worldExtends.y * rhs3.z + b.worldExtends.z * rhs3.y;
if (Mathf.Abs(lhs.y * vInt.x - lhs.x * vInt2.x) > num2 + num3)
{
return false;
}
num2 = worldExtends.x * rhs2.y + worldExtends.y * rhs.y;
num3 = b.worldExtends.x * rhs3.z + b.worldExtends.z * rhs3.x;
if (Mathf.Abs(lhs.y * vInt.y - lhs.x * vInt2.y) > num2 + num3)
{
return false;
}
num2 = worldExtends.x * rhs2.z + worldExtends.y * rhs.z;
num3 = b.worldExtends.x * rhs3.y + b.worldExtends.y * rhs3.x;
if (Mathf.Abs(lhs.y * vInt.z - lhs.x * vInt2.z) > num2 + num3)
{
return false;
}
return true;
}
先说最核心的思想,以二维为例:
假设两个形状相交,是不是一定至少有一个点,这个点既在a里面又在b里面。
于是我们遍历a包含的所有的点,
再遍历b包含的所有的点,
如果发现有两个点坐标相同,那么就说明a和b相交。
于是我们可以把a包含的所有的点 分别 减去b包含的所有的点,得到一个集合,所谓闵可夫斯基差。
[ C=A-B={a-b\mid a\in A,b\in B} ]
也就是 A 中任意一个点,减去 B 中任意一个点,得到所有可能的差向量。
如果这个集合中存在点(0,0),就满足。
推广一下,其实对一维、三维都适用。(注意只适用于凸包)
假设两条线段
1 4
3 6
我们求出他们的闵可夫斯基差,就是[1-6,4-3] = [-5,1],经过了原点,说明有碰撞。
二维如果也能像一维那样简单就好了,遗憾的是,不能。
有一种方法是,遍历两个形状的顶点,分别求出他们的差,构成一个集合。
然后在这个集合中构建凸包,检测凸包是否包含原点。
用一根橡皮筋套住所有点,橡皮筋收紧后形成的轮廓,就是凸包。
Andrew 单调链。代码如下:
bool GJK(List<Vector2> points){
//移除相同点
points.RemoveDupicate();
//首先按照x大小排序,x相同按y大小排序
points.Sort();
//从左往右构建下凸壳
List<Vector2> lower=new();
foreach(var p in points){
//先拿两个点构成线段
if(lower.Count < 2){
lower.Add(p);
continue;
}
//尝试加入一个点
lower.Add(p);
//检测是否满足构成下凸壳
CheckValid(lower);
}
//从右往左构建上凸壳
List<Vector2> higher=new();
foreach(var p in points.Reverse()){
//先拿两个点构成线段
if(higher.Count < 2){
higher.Add(p);
continue;
}
//尝试加入一个点
higher.Add(p);
//检测是否满足构成下凸壳
CheckValid(higher);
}
//构建凸壳
var result = new();
//移除共点
lower.RemoveAt(0);
higher.RemoveAt(0);
result.Add(lower);
result.Add(higher);
//判断原点在不在里面
return CheckContainsZero(result);
}
void CheckValid(List<Vector2> points){
if(points.Count < 3){
return;
}
//找到最新的三个点
var a = points[points.Count-3];
var b = points[points.Count-2];
var c = points[points.Count-1];
//判断旋转方向
bool valid = true;
if(Cross(a-b,a-c)<=0){
valid=false;
}
if(!valid){
points.Remove(b);
CheckValid(points);
}
}
//判断是否包含原点 约定凸包按逆时针排序
bool CheckContainsZero(List<Vector2> points){
//遍历所有顶点
for(int i=0;i<points.Count;i++){
//叉乘
float b = Cross(points[(i+1) % points.Count] - points[i],(0,0) - points[i]);
if(b < 0){
return false;
}
}
return true;
}
其实类似,两个物体的顶点求差,构成集合。
通过集合构建凸体。
这块比较复杂,先略过。
Obj BuildHull(List<Vector3> points){
}
判断凸体是否包含原点。
//判断物体是否包含原点
bool CheckContainsZero(List<Triangle> triangles){
//遍历所有三角形
for(int i=0;i<triangles.Count;i++){
//叉乘找到法向量
var n = Cross(triangles[i].p0 - triangles[i].p1,triangles[i].p0 - triangles[i].p2);
//点乘找到值
var d =Dot((0,0,0) - triangles[i].p0 , n);
//在三角面的外面 不满足
if(d>0){
return false;
}
}
return true;
}
见第五章
王者荣耀解剖(五):碰撞检测之GJK