分离轴定理SAT凸多边形精确碰撞检测

定理

Separating Axis Theorem，缩写SAT，中文为分离轴理论或分离轴定理，通过判断凸多边形在分离轴上的投影是否重叠来判断是否发生碰撞。

所谓的分离轴实际上是一个方向轴，该轴的选取在二维平面情况下一般为凸多边形的边的法线。

局限性：分离轴定理仅适用于凸多边形，不能用于凹多边形。但可以通过转化的方法，即将凹多边形转化为多个凸多边形，然后对多个凸多边形分别使用SAT，达到精确碰撞检测的目的

证明

证明过程可以看SAT（分离轴定理）证明 - 知乎 (zhihu.com)

代码

2D

我们先来探讨二维平面下的情况

步骤大概有如下几步:

• 获取其中一个凸多边形每个边的垂直向量（法向量）
• 点乘获得投影(这里不用除以法向量的模，因为对判断碰撞无影响)，其中所有结果中的最小值和最大值就是获得的投影（这里是把两个值当作投影线段两端点在分离轴这个一维数轴的坐标了）
• 判断投影是否相交

以下是代码，每一步还可以进一步优化，这里代码仅为阐述上述步骤

# 获取边的法向量
def getNormal(points: list)->list:
    normalVec = {}      # 法向量的集合(Set)
    for i in points:
        for j in points[points.index(i)::]:
            # edge = (i[0]-j[0], i[1]-j[1])   #边对应的向量
            vec = (j[1]-i[1], i[0]-j[0])    # 法线对应的向量。可以看出(x,y)垂直的一个向量为(-y,x)
            normalVec.add(vec)
    return list(normalVec)

# 点乘,获取所有结果中的最大值与最小值
def dotProduct(lst1:list, lst2:list)->list:
    res = []
    for i in lst1:
        for j in lst2:
            res.append(i[0]*j[0] + i[1]*j[1])
    return (min(res), max(res))

# 碰撞检测
def collided(points1:list, points2:list)->bool:
    vec = getNormal(points1)
    res1 = dotProduct(vec, points1)
    res2 = dotProduct(vec, points2)

    # 判断重影是否重叠，重叠就发生碰撞返回True
    if (res1[0]<=res2[1] and res1[0]>=res2[0]) or (res1[1]<=res2[1] and res1[1]>=res2[0]):
        return True
    else:
        return False

# ------------ 调用---------------#
# 这里存放点的列表仅做表示，获取点的方法根据自己情况来

# 存放凸多边形1顶点的列表
shape1_points = []
# 存放凸多边形2顶点的列表
shape2_points = []

print(collided(shape1_points, shape2_points))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

3D

其实3D步骤也一样，只不过分离轴凸多边形边的法向量凸多面体的面的法向量