DragonWind

王者荣耀解剖(三):碰撞检测

对于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;
}

盒和盒之间的碰撞检测

SAT分离轴定理

一维

假设是一维,如何判断两条线段是否相交呢?

假设两条线段分别为

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,这里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呢?这里我们直接用结论:对于二维物体来说,投影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;
}

GJK算法

核心思想

先说最核心的思想,以二维为例:

假设两个形状相交,是不是一定至少有一个点,这个点既在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