【游戏算法】 - 碰撞检测

宋 游戏开发
  2020-08-27 19:07:05 2020-08-27 19:07:05 创建   2021-03-15 20:30:39 2021-03-15 20:30:39 更新      9k 字  50 分钟

本文介绍一些常用的碰撞检测算法。

球包围盒（2D下即圆形包围盒）

圆形包围盒

球形包围盒 是一个用最小球包裹物体的几何形状，有以下特点

  • 计算简单：判断两个球形是否相交只需比较两球心的距离与两半径之和的关系。
  • 适合动态物体：对于高速运动的物体，球形包围盒的检测效率较高。
  • 旋转不变性： 球（圆）包围盒的形状不受物体旋转影响，无需在旋转时重新计算
  • 精度较低：无法紧密贴合非球形物体，可能导致误判。

计算公式(2D圆包围盒可视y坐标为0)

（1）球心点的计算
假设物体由一组顶点 组成，球心点 的计算公式为：

其中 是顶点 的坐标。

（2）半径的计算
半径 为球心到最远顶点的距离：

其中 表示顶点 到球心 的欧几里得距离

个人认为球形包围盒适合于初步碰撞检测的实现

球包围盒算法实现 
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
40
41
42
43
44
45
46
47
48
49
50
51
#include <vector>
#include <cmath>
#include <algorithm>

struct Vector3 {
    float x, y, z;
};

struct Sphere {
    Vector3 center;
    float radius;
};

Sphere CalculateBoundingSphere(const std::vector<Vector3>& vertices) {
    Sphere result;
    float minX = vertices[0].x, maxX = vertices[0].x;
    float minY = vertices[0].y, maxY = vertices[0].y;
    float minZ = vertices[0].z, maxZ = vertices[0].z;

    for (const auto& v : vertices) {
        minX = std::min(minX, v.x);
        maxX = std::max(maxX, v.x);
        minY = std::min(minY, v.y);
        maxY = std::max(maxY, v.y);
        minZ = std::min(minZ, v.z);
        maxZ = std::max(maxZ, v.z);
    }

    result.center = { (minX + maxX) / 2.0f, (minY + maxY) / 2.0f, (minZ + maxZ) / 2.0f };

    float maxDistance = 0.0f;
    for (const auto& v : vertices) {
        float dx = v.x - result.center.x;
        float dy = v.y - result.center.y;
        float dz = v.z - result.center.z;
        float distance = std::sqrt(dx*dx + dy*dy + dz*dz);
        maxDistance = std::max(maxDistance, distance);
    }

    result.radius = maxDistance;
    return result;
}

bool CheckCollision(const Sphere& s1, const Sphere& s2) {
    float dx = s1.center.x - s2.center.x;
    float dy = s1.center.y - s2.center.y;
    float dz = s1.center.z - s2.center.z;
    float distanceSquared = dx*dx + dy*dy + dz*dz;
    float radiusSum = s1.radius + s2.radius;
    return distanceSquared <= radiusSum * radiusSum;
}
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
using System;
using System.Collections.Generic;
using System.Linq;

public class Vector3D
{
    public float X { get; set; }
    public float Y { get; set; }
    public float Z { get; set; }
    
    public Vector3D(float x, float y, float z)
    {
        X = x;
        Y = y;
        Z = z;
    }
}

public class BoundingSphere
{
    public Vector3D Center { get; set; }
    public float Radius { get; set; }
    
    public static BoundingSphere Calculate(List<Vector3D> vertices)
    {
        float minX = float.MaxValue, maxX = float.MinValue;
        float minY = float.MaxValue, maxY = float.MinValue;
        float minZ = float.MaxValue, maxZ = float.MinValue;
        
        foreach (var v in vertices)
        {
            minX = Math.Min(minX, v.X);
            maxX = Math.Max(maxX, v.X);
            minY = Math.Min(minY, v.Y);
            maxY = Math.Max(maxY, v.Y);
            minZ = Math.Min(minZ, v.Z);
            maxZ = Math.Max(maxZ, v.Z);
        }
        
        var center = new Vector3D(
            (minX + maxX) / 2,
            (minY + maxY) / 2,
            (minZ + maxZ) / 2
        );
        
        float maxRadius = 0;
        foreach (var v in vertices)
        {
            float dx = v.X - center.X;
            float dy = v.Y - center.Y;
            float dz = v.Z - center.Z;
            float distance = (float)Math.Sqrt(dx*dx + dy*dy + dz*dz);
            maxRadius = Math.Max(maxRadius, distance);
        }
        
        return new BoundingSphere
        {
            Center = center,
            Radius = maxRadius
        };
    }
    
    public static bool CheckCollision(BoundingSphere s1, BoundingSphere s2)
    {
        float dx = s1.Center.X - s2.Center.X;
        float dy = s1.Center.Y - s2.Center.Y;
        float dz = s1.Center.Z - s2.Center.Z;
        float distanceSquared = dx*dx + dy*dy + dz*dz;
        float radiusSum = s1.Radius + s2.Radius;
        return distanceSquared <= radiusSum * radiusSum;
    }
}
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
40
41
42
43
44
45
46
47
48
class Vector3D {
    constructor(public x: number, public y: number, public z: number) {}
}

class BoundingSphere {
    constructor(public center: Vector3D, public radius: number) {}

    static calculate(vertices: Vector3D[]): BoundingSphere {
        let minX = vertices[0].x, maxX = vertices[0].x;
        let minY = vertices[0].y, maxY = vertices[0].y;
        let minZ = vertices[0].z, maxZ = vertices[0].z;
        
        for (const v of vertices) {
            minX = Math.min(minX, v.x);
            maxX = Math.max(maxX, v.x);
            minY = Math.min(minY, v.y);
            maxY = Math.max(maxY, v.y);
            minZ = Math.min(minZ, v.z);
            maxZ = Math.max(maxZ, v.z);
        }

        const center = new Vector3D(
            (minX + maxX) / 2,
            (minY + maxY) / 2,
            (minZ + maxZ) / 2
        );

        let maxRadius = 0;
        for (const v of vertices) {
            const dx = v.x - center.x;
            const dy = v.y - center.y;
            const dz = v.z - center.z;
            const distance = Math.sqrt(dx*dx + dy*dy + dz*dz);
            maxRadius = Math.max(maxRadius, distance);
        }

        return new BoundingSphere(center, maxRadius);
    }

    static checkCollision(s1: BoundingSphere, s2: BoundingSphere): boolean {
        const dx = s1.center.x - s2.center.x;
        const dy = s1.center.y - s2.center.y;
        const dz = s1.center.z - s2.center.z;
        const distanceSquared = dx*dx + dy*dy + dz*dz;
        const radiusSum = s1.radius + s2.radius;
        return distanceSquared <= radiusSum * radiusSum;
    }
}
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
40
41
42
43
44
45
46
47
48
49
local Vector3 = {}
function Vector3:new(x, y, z)
    local obj = {x = x or 0, y = y or 0, z = z or 0}
    setmetatable(obj, self)
    self.__index = self
    return obj
end

local BoundingSphere = {}
function BoundingSphere:new(vertices)
    local obj = {}
    setmetatable(obj, self)
    self.__index = self
    
    local minX, maxX = vertices[1].x, vertices[1].x
    local minY, maxY = vertices[1].y, vertices[1].y
    local minZ, maxZ = vertices[1].z, vertices[1].z
    
    for _, v in ipairs(vertices) do
        minX = math.min(minX, v.x)
        maxX = math.max(maxX, v.x)
        minY = math.min(minY, v.y)
        maxY = math.max(maxY, v.y)
        minZ = math.min(minZ, v.z)
        maxZ = math.max(maxZ, v.z)
    end
    
    obj.center = Vector3:new((minX + maxX)/2, (minY + maxY)/2, (minZ + maxZ)/2)
    obj.radius = 0
    
    for _, v in ipairs(vertices) do
        local dx = v.x - obj.center.x
        local dy = v.y - obj.center.y
        local dz = v.z - obj.center.z
        local distance = math.sqrt(dx*dx + dy*dy + dz*dz)
        obj.radius = math.max(obj.radius, distance)
    end
    
    return obj
end

function BoundingSphere:checkCollision(other)
    local dx = self.center.x - other.center.x
    local dy = self.center.y - other.center.y
    local dz = self.center.z - other.center.z
    local distanceSquared = dx*dx + dy*dy + dz*dz
    local radiusSum = self.radius + other.radius
    return distanceSquared <= radiusSum * radiusSum
end

轴对齐（AABB）包围盒（Axis-Aligned Bounding Box）

AABB是一种通过轴对齐的矩形或立方体包围复杂几何体的最小体积边界框。其核心特性是：

  • 边与坐标轴平行：无论在2D还是3D中，AABB的边始终与坐标轴对齐。
  • 仅需两个点定义：通过最小点（min）和最大点（max）即可确定AABB的边界

AABB包围盒

AABB碰撞检测的优缺点分析

优点

  1. 计算效率极高
    AABB的碰撞检测仅需简单的比较操作（> 和 <），无需复杂的几何运算或矩阵变换。
  2. 实现简单
    代码逻辑直观，易于集成到游戏引擎或物理模拟系统中。
  3. 适用于大规模场景
    在包含大量物体的场景中，AABB可作为**粗略碰撞检测（Broad Phase）**的第一步，快速排除不可能发生碰撞的物体对。
    缺点
  4. 对旋转物体不敏感
    AABB始终与坐标轴对齐，当物体旋转时，包围盒体积会显著增大，导致误判（False Positive）或漏判（False Negative）。
  5. 包围精度较低
    对于不规则形状（如球体、三角形网格），AABB的冗余空间较大，可能浪费计算资源。
  6. 无法处理复杂交互
    AABB仅能检测是否发生碰撞，无法提供碰撞法线、接触点等细节信息，需结合其他方法（如OBB）进一步优化。

算法实现

AABB算法实现 
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
#include <iostream>

// 2D AABB结构体
struct AABB2D {
    float minX, minY;
    float maxX, maxY;
};

// 3D AABB结构体
struct AABB3D {
    float minX, minY, minZ;
    float maxX, maxY, maxZ;
};

// 2D碰撞检测
bool isColliding(AABB2D boxA, AABB2D boxB) {
    return (boxA.maxX > boxB.minX && boxB.maxX > boxA.minX) 
        && (boxA.maxY > boxB.minY && boxB.maxY > boxA.minY);
}

// 3D碰撞检测
bool isColliding3D(AABB3D boxA, AABB3D boxB) {
    return (boxA.maxX > boxB.minX && boxB.maxX > boxA.minX) 
        && (boxA.maxY > boxB.minY && boxB.maxY > boxA.minY) 
        && (boxA.maxZ > boxB.minZ && boxB.maxZ > boxA.minZ);
}

int main() {
    // 示例用法
    AABB2D aabb1 = {0, 0, 2, 2};
    AABB2D aabb2 = {1, 1, 3, 3};
    std::cout << "2D碰撞检测结果: " << isColliding(aabb1, aabb2) << std::endl;

    AABB3D aabb3d1 = {0, 0, 0, 2, 2, 2};
    AABB3D aabb3d2 = {1, 1, 1, 3, 3, 3};
    std::cout << "3D碰撞检测结果: " << isColliding3D(aabb3d1, aabb3d2) << std::endl;
    return 0;
}
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
40
41
42
43
44
45
46
47
48
49
50
51
using System;

// 2D AABB类
public class AABB2D
{
    public float MinX { get; set; }
    public float MinY { get; set; }
    public float MaxX { get; set; }
    public float MaxY { get; set; }
}

// 3D AABB类
public class AABB3D
{
    public float MinX { get; set; }
    public float MinY { get; set; }
    public float MinZ { get; set; }
    public float MaxX { get; set; }
    public float MaxY { get; set; }
    public float MaxZ { get; set; }
}

public class CollisionDetection
{
    // 2D碰撞检测
    public static bool IsColliding(AABB2D boxA, AABB2D boxB)
    {
        return (boxA.MaxX > boxB.MinX && boxB.MaxX > boxA.MinX) 
            && (boxA.MaxY > boxB.MinY && boxB.MaxY > boxA.MinY);
    }

    // 3D碰撞检测
    public static bool IsColliding3D(AABB3D boxA, AABB3D boxB)
    {
        return (boxA.MaxX > boxB.MinX && boxB.MaxX > boxA.MinX) 
            && (boxA.MaxY > boxB.MinY && boxB.MaxY > boxA.MinY) 
            && (boxA.MaxZ > boxB.MinZ && boxB.MaxZ > boxA.MinZ);
    }

    public static void Main()
    {
        // 示例用法
        var aabb2D1 = new AABB2D { MinX = 0, MinY = 0, MaxX = 2, MaxY = 2 };
        var aabb2D2 = new AABB2D { MinX = 1, MinY = 1, MaxX = 3, MaxY = 3 };
        Console.WriteLine("2D碰撞检测结果: " + IsColliding(aabb2D1, aabb2D2));

        var aabb3D1 = new AABB3D { MinX = 0, MinY = 0, MinZ = 0, MaxX = 2, MaxY = 2, MaxZ = 2 };
        var aabb3D2 = new AABB3D { MinX = 1, MinY = 1, MinZ = 1, MaxX = 3, MaxY = 3, MaxZ = 3 };
        Console.WriteLine("3D碰撞检测结果: " + IsColliding3D(aabb3D1, aabb3D2));
    }
}
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
// 2D AABB接口
interface AABB2D {
    minX: number;
    minY: number;
    maxX: number;
    maxY: number;
}

// 3D AABB接口
interface AABB3D {
    minX: number;
    minY: number;
    minZ: number;
    maxX: number;
    maxY: number;
    maxZ: number;
}

// 2D碰撞检测
function isColliding(boxA: AABB2D, boxB: AABB2D): boolean {
    return (boxA.maxX > boxB.minX && boxB.maxX > boxA.minX) 
        && (boxA.maxY > boxB.minY && boxB.maxY > boxA.minY);
}

// 3D碰撞检测
function isColliding3D(boxA: AABB3D, boxB: AABB3D): boolean {
    return (boxA.maxX > boxB.minX && boxB.maxX > boxA.minX) 
        && (boxA.maxY > boxB.minY && boxB.maxY > boxA.minY) 
        && (boxA.maxZ > boxB.minZ && boxB.maxZ > boxA.minZ);
}

// 示例用法
const aabb2D1: AABB2D = { minX: 0, minY: 0, maxX: 2, maxY: 2 };
const aabb2D2: AABB2D = { minX: 1, minY: 1, maxX: 3, maxY: 3 };
console.log("2D碰撞检测结果:", isColliding(aabb2D1, aabb2D2));

const aabb3D1: AABB3D = { minX: 0, minY: 0, minZ: 0, maxX: 2, maxY: 2, maxZ: 2 };
const aabb3D2: AABB3D = { minX: 1, minY: 1, minZ: 1, maxX: 3, maxY: 3, maxZ: 3 };
console.log("3D碰撞检测结果:", isColliding3D(aabb3D1, aabb3D2));
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
-- 2D AABB表
local AABB2D = {}
function AABB2D:new(minX, minY, maxX, maxY)
    return {minX = minX, minY = minY, maxX = maxX, maxY = maxY}
end

-- 3D AABB表
local AABB3D = {}
function AABB3D:new(minX, minY, minZ, maxX, maxY, maxZ)
    return {minX = minX, minY = minY, minZ = minZ, maxX = maxX, maxY = maxY, maxZ = maxZ}
end

-- 2D碰撞检测
function isColliding(boxA, boxB)
    return (boxA.maxX > boxB.minX and boxB.maxX > boxA.minX) 
        and (boxA.maxY > boxB.minY and boxB.maxY > boxA.minY)
end

-- 3D碰撞检测
function isColliding3D(boxA, boxB)
    return (boxA.maxX > boxB.minX and boxB.maxX > boxA.minX) 
        and (boxA.maxY > boxB.minY and boxB.maxY > boxA.minY) 
        and (boxA.maxZ > boxB.minZ and boxB.maxZ > boxA.minZ)
end

-- 示例用法
local aabb2D1 = AABB2D:new(0, 0, 2, 2)
local aabb2D2 = AABB2D:new(1, 1, 3, 3)
print("2D碰撞检测结果:", isColliding(aabb2D1, aabb2D2))

local aabb3D1 = AABB3D:new(0, 0, 0, 2, 2, 2)
local aabb3D2 = AABB3D:new(1, 1, 1, 3, 3, 3)
print("3D碰撞检测结果:", isColliding3D(aabb3D1, aabb3D2))

OBB包围盒（Oriented Bounding Box）

OBB包围盒
OBB包围盒是一种基于物体一阶矩数学特征构建的三维有向包围盒，其核心特征是通过协方差矩阵的特征向量确定三个主方向轴，形成可随物体旋转的最小体积长方体包围空间。
一般基于OBB包围盒的碰撞检测使用SAT分离轴定理（Separating Axis Theorem）进行相交测试。
在说明SAT之前，我们需要了解一个定义，凸多边形: 任意两个顶点间的线段位于多边形的内部或边上。与凸多边形对应的就是凹多边形，下图的左侧为凸多边形，右侧为凹多边形。
多边形
凹多边形也可以分解为多个凸多边形用于计算。
凹多边形分解
分离轴定理用于凸多边形的碰撞检测，若两个物体没有发生碰撞，则总会存在一条直线，将两个物体分离，这条直线就是分离轴。
对于SAT来说，核心是找到分离轴，也就是找到交集为空的投影，所以我们要做的就是找到一条将两个凸多边形一分为二的轴。具体的方案是寻找某个多边形的一条边，垂直这条边的直线就是这条边的投影轴，也就是我们熟知的法线，投影重叠的计算则可以使用向量计算。
SAT

算法实现

OBB-SAT算法实现 
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
#include <vector>
#include <cmath>
#include <limits>

// 通用向量类（支持2D/3D）
template<int D>
struct Vector {
    float data[D];
    
    Vector() { for (int i = 0; i < D; i++) data[i] = 0.0f; }
    Vector(float x, float y, float z = 0.0f) {
        data[0] = x;
        data[1] = y;
        if (D == 3) data[2] = z;
    }
    
    float operator[](int i) const { return data[i]; }
    float& operator[](int i) { return data[i]; }
    
    Vector<D> operator*(float s) const {
        Vector<D> result;
        for (int i = 0; i < D; i++) result[i] = data[i] * s;
        return result;
    }
    
    Vector<D> operator+(const Vector<D>& v) const {
        Vector<D> result;
        for (int i = 0; i < D; i++) result[i] = data[i] + v[i];
        return result;
    }
    
    Vector<D> operator-(const Vector<D>& v) const {
        Vector<D> result;
        for (int i = 0; i < D; i++) result[i] = data[i] - v[i];
        return result;
    }
    
    // 点积
    float dot(const Vector<D>& v) const {
        float result = 0.0f;
        for (int i = 0; i < D; i++) result += data[i] * v[i];
        return result;
    }
    
    // 叉积（仅3D）
    Vector<3> cross(const Vector<3>& v) const {
        return Vector<3>(
            data[1]*v[2] - data[2]*v[1],
            data[2]*v[0] - data[0]*v[2],
            data[0]*v[1] - data[1]*v[0]
        );
    }
    
    // 向量长度
    float length() const {
        float sum = 0.0f;
        for (int i = 0; i < D; i++) sum += data[i]*data[i];
        return std::sqrt(sum);
    }
};

// OBB结构体（支持2D/3D）
template<int D>
struct OBB {
    Vector<D> center;         // 中心点
    Vector<D> halfSize;       // 半长宽高
    std::vector<Vector<D>> axes; // 主轴方向
};

// 生成投影轴（2D专用）
template<>
std::vector<Vector<2>> generateAxes(const OBB<2>& a, const OBB<2>& b) {
    std::vector<Vector<2>> axes;
    
    // 添加两个OBB的主轴
    axes.push_back(a.axes[0]);
    axes.push_back(a.axes[1]);
    axes.push_back(b.axes[0]);
    axes.push_back(b.axes[1]);
    
    return axes;
}

// 生成投影轴（3D专用）
template<>
std::vector<Vector<3>> generateAxes(const OBB<3>& a, const OBB<3>& b) {
    std::vector<Vector<3>> axes;
    
    // 添加两个OBB的主轴
    for (int i = 0; i < 3; i++) {
        axes.push_back(a.axes[i]);
        axes.push_back(b.axes[i]);
    }
    
    // 添加交叉轴（共9个）
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            Vector<3> cross = a.axes[i].cross(b.axes[j]);
            if (cross.length() > 1e-6f) { // 避免零向量
                axes.push_back(cross);
            }
        }
    }
    
    return axes;
}

// 投影计算
template<int D>
bool project(const OBB<D>& obb, const Vector<D>& axis, float& min, float& max) {
    // 生成局部坐标系下的顶点
    std::vector<Vector<D>> localCorners = generateCorners(obb);
    
    // 转换到世界坐标系
    std::vector<Vector<D>> worldCorners;
    for (const auto& corner : localCorners) {
        Vector<D> worldPos = obb.center;
        for (int i = 0; i < D; i++) {
            worldPos = worldPos + corner[i] * obb.axes[i];
        }
        worldCorners.push_back(worldPos);
    }
    
    // 计算投影
    min = std::numeric_limits<float>::max();
    max = std::numeric_limits<float>::lowest();
    
    for (const auto& corner : worldCorners) {
        float proj = corner.dot(axis);
        min = std::min(min, proj);
        max = std::max(max, proj);
    }
    
    return true;
}

// OBB碰撞检测主函数
template<int D>
bool OBBIntersects(const OBB<D>& a, const OBB<D>& b) {
    std::vector<Vector<D>> axes = generateAxes(a, b);
    
    for (const auto& axis : axes) {
        float minA, maxA, minB, maxB;
        project(a, axis, minA, maxA);
        project(b, axis, minB, maxB);
        
        if (maxA < minB || maxB < minA)
            return false;
    }
    
    return true;
}
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
using System;
using System.Collections.Generic;

// 通用向量类（支持2D/3D）
public struct Vector<T> where T : struct {
    public T X, Y, Z;
    public int Dim => typeof(T).Name == "Double" ? 3 : 2; // 简化判断
    
    public Vector(float x, float y) {
        X = (T)(object)x;
        Y = (T)(object)y;
        Z = default;
    }
    
    public Vector(float x, float y, float z) {
        X = (T)(object)x;
        Y = (T)(object)y;
        Z = (T)(object)z;
    }
    
    public static Vector<T> operator *(Vector<T> v, float s) {
        return new Vector<T>((float)v.X * s, (float)v.Y * s, (float)v.Z * s);
    }
    
    public static Vector<T> operator +(Vector<T> a, Vector<T> b) {
        return new Vector<T>((float)a.X + (float)b.X, 
                            (float)a.Y + (float)b.Y,
                            (float)a.Z + (float)b.Z);
    }
    
    public static Vector<T> operator -(Vector<T> a, Vector<T> b) {
        return new Vector<T>((float)a.X - (float)b.X, 
                            (float)a.Y - (float)b.Y,
                            (float)a.Z - (float)b.Z);
    }
    
    public float Dot(Vector<T> v) {
        float result = (float)X * (float)v.X + (float)Y * (float)v.Y;
        if (Dim == 3) result += (float)Z * (float)v.Z;
        return result;
    }
    
    public Vector<float> Cross(Vector<float> v) {
        return new Vector<float>(
            (float)Y * v.Z - (float)Z * v.Y,
            (float)Z * v.X - (float)X * v.Z,
            (float)X * v.Y - (float)Y * v.X
        );
    }
    
    public float Length() {
        float sum = (float)X*(float)X + (float)Y*(float)Y;
        if (Dim == 3) sum += (float)Z*(float)Z;
        return (float)Math.Sqrt(sum);
    }
}

// OBB结构体（支持2D/3D）
public struct OBB<T> {
    public Vector<T> Center;
    public Vector<T> HalfSize;
    public List<Vector<T>> Axes;
}

// 生成投影轴（2D专用）
public static class OBB2D {
    public static List<Vector<float>> GenerateAxes(OBB<float> a, OBB<float> b) {
        List<Vector<float>> axes = new List<Vector<float>>();
        
        axes.AddRange(a.Axes);
        axes.AddRange(b.Axes);
        
        return axes;
    }
}

// 生成投影轴（3D专用）
public static class OBB3D {
    public static List<Vector<float>> GenerateAxes(OBB<float> a, OBB<float> b) {
        List<Vector<float>> axes = new List<Vector<float>>();
        
        foreach (var axis in a.Axes) axes.Add(axis);
        foreach (var axis in b.Axes) axes.Add(axis);
        
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                Vector<float> cross = a.Axes[i].Cross(b.Axes[j]);
                if (cross.Length() > 1e-6f) {
                    axes.Add(cross);
                }
            }
        }
        
        return axes;
    }
}

// OBB碰撞检测主函数
public static class CollisionDetector {
    public static bool OBBIntersects<T>(OBB<T> a, OBB<T> b) {
        List<Vector<float>> axes = null;
        
        if (typeof(T) == typeof(float) && ((OBB<float>)a).Axes.Count == 3) {
            axes = OBB3D.GenerateAxes((OBB<float>)a, (OBB<float>)b);
        } else {
            axes = OBB2D.GenerateAxes((OBB<float>)a, (OBB<float>)b);
        }
        
        foreach (var axis in axes) {
            float minA = float.MaxValue, maxA = float.MinValue;
            float minB = float.MaxValue, maxB = float.MinValue;
            
            Project((OBB<float>)a, axis, ref minA, ref maxA);
            Project((OBB<float>)b, axis, ref minB, ref maxB);
            
            if (maxA < minB || maxB < minA)
                return false;
        }
        
        return true;
    }
    
    private static void Project(OBB<float> obb, Vector<float> axis, ref float min, ref float max) {
        List<Vector<float>> localCorners = GenerateCorners(obb);
        List<Vector<float>> worldCorners = new List<Vector<float>>();
        
        foreach (var corner in localCorners) {
            Vector<float> worldPos = obb.Center;
            for (int i = 0; i < obb.Axes.Count; i++) {
                worldPos = worldPos + corner[i] * obb.Axes[i];
            }
            worldCorners.Add(worldPos);
        }
        
        foreach (var corner in worldCorners) {
            float proj = corner.Dot(axis);
            min = Math.Min(min, proj);
            max = Math.Max(max, proj);
        }
    }
}
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
// 通用向量类（支持2D/3D）
class Vector<T> {
    private _data: number[];
    constructor(...args: number[]) {
        this._data = args;
    }
    
    get dim(): number {
        return this._data.length;
    }
    
    get(x: number): number {
        return this._data[x];
    }
    
    dot(v: Vector<this>): number {
        let result = 0;
        for (let i = 0; i < this.dim; i++) {
            result += this._data[i] * v.get(i);
        }
        return result;
    }
    
    cross(v: Vector<this>): Vector<this> {
        if (this.dim !== 3 || v.dim !== 3) throw new Error("Cross product only for 3D vectors");
        return new Vector(
            this._data[1] * v.get(2) - this._data[2] * v.get(1),
            this._data[2] * v.get(0) - this._data[0] * v.get(2),
            this._data[0] * v.get(1) - this._data[1] * v.get(0)
        );
    }
    
    length(): number {
        let sum = 0;
        for (let i = 0; i < this.dim; i++) {
            sum += this._data[i] * this._data[i];
        }
        return Math.sqrt(sum);
    }
    
    multiply(s: number): Vector<this> {
        const result = new Array(this.dim).fill(0);
        for (let i = 0; i < this.dim; i++) {
            result[i] = this._data[i] * s;
        }
        return new Vector(...result);
    }
    
    add(v: Vector<this>): Vector<this> {
        const result = new Array(this.dim).fill(0);
        for (let i = 0; i < this.dim; i++) {
            result[i] = this._data[i] + v.get(i);
        }
        return new Vector(...result);
    }
    
    subtract(v: Vector<this>): Vector<this> {
        const result = new Array(this.dim).fill(0);
        for (let i = 0; i < this.dim; i++) {
            result[i] = this._data[i] - v.get(i);
        }
        return new Vector(...result);
    }
}

// OBB结构体（支持2D/3D）
class OBB<T> {
    center: Vector<T>;
    halfSize: Vector<T>;
    axes: Vector<T>[];
    
    constructor(center: Vector<T>, halfSize: Vector<T>, axes: Vector<T>[]) {
        this.center = center;
        this.halfSize = halfSize;
        this.axes = axes;
    }
}

// 生成投影轴（2D专用）
function generateAxes2D(a: OBB<any>, b: OBB<any>): Vector<any>[] {
    const axes: Vector<any>[] = [];
    
    axes.push(...a.axes);
    axes.push(...b.axes);
    
    return axes;
}

// 生成投影轴（3D专用）
function generateAxes3D(a: OBB<any>, b: OBB<any>): Vector<any>[] {
    const axes: Vector<any>[] = [];
    
    axes.push(...a.axes);
    axes.push(...b.axes);
    
    for (let i = 0; i < 3; i++) {
        for (let j = 0; j < 3; j++) {
            const cross = a.axes[i].cross(b.axes[j]);
            if (cross.length() > 1e-6) {
                axes.push(cross);
            }
        }
    }
    
    return axes;
}

// 投影计算
function project<T>(obb: OBB<T>, axis: Vector<T>): { min: number, max: number } {
    const localCorners = generateCorners(obb);
    const worldCorners: Vector<T>[] = [];
    
    for (const corner of localCorners) {
        let worldPos = obb.center;
        for (let i = 0; i < obb.axes.length; i++) {
            worldPos = worldPos.add(corner.get(i) * obb.axes[i]);
        }
        worldCorners.push(worldPos);
    }
    
    let min = Number.MAX_VALUE;
    let max = -Number.MAX_VALUE;
    
    for (const corner of worldCorners) {
        const proj = corner.dot(axis);
        min = Math.min(min, proj);
        max = Math.max(max, proj);
    }
    
    return { min, max };
}

// OBB碰撞检测主函数
function OBBIntersects<T>(a: OBB<T>, b: OBB<T>): boolean {
    let axes: Vector<T>[];
    
    if (a.axes.length === 3 && b.axes.length === 3) {
        axes = generateAxes3D(a, b);
    } else {
        axes = generateAxes2D(a, b);
    }
    
    for (const axis of axes) {
        const { min: minA, max: maxA } = project(a, axis);
        const { min: minB, max: maxB } = project(b, axis);
        
        if (maxA < minB || maxB < minA)
            return false;
    }
    
    return true;
}
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
-- 通用向量类（支持2D/3D）
Vector = {}
Vector.__index = Vector

function Vector.new(...)
    local args = {...}
    return setmetatable({values = args}, Vector)
end

function Vector:dim()
    return #self.values
end

function Vector:get(i)
    return self.values[i+1] -- Lua索引从0开始
end

function Vector:dot(v)
    local result = 0
    for i = 0, self:dim()-1 do
        result = result + self:get(i) * v:get(i)
    end
    return result
end

function Vector:cross(v)
    if self:dim() ~= 3 or v:dim() ~= 3 then
        error("Cross product only for 3D vectors")
    end
    return Vector.new(
        self:get(1)*v:get(2) - self:get(2)*v:get(1),
        self:get(2)*v:get(0) - self:get(0)*v:get(2),
        self:get(0)*v:get(1) - self:get(1)*v:get(0)
    )
end

function Vector:length()
    local sum = 0
    for i = 0, self:dim()-1 do
        sum = sum + self:get(i)^2
    end
    return math.sqrt(sum)
end

function Vector:multiply(s)
    local values = {}
    for i = 0, self:dim()-1 do
        values[i+1] = self:get(i) * s
    end
    return Vector.new(unpack(values))
end

function Vector:add(v)
    local values = {}
    for i = 0, self:dim()-1 do
        values[i+1] = self:get(i) + v:get(i)
    end
    return Vector.new(unpack(values))
end

function Vector:subtract(v)
    local values = {}
    for i = 0, self:dim()-1 do
        values[i+1] = self:get(i) - v:get(i)
    end
    return Vector.new(unpack(values))
end

-- OBB结构体（支持2D/3D）
OBB = {}
OBB.__index = OBB

function OBB.new(center, halfSize, axes)
    return setmetatable({
        center = center,
        halfSize = halfSize,
        axes = axes
    }, OBB)
end

-- 生成投影轴（2D专用）
function generateAxes2D(a, b)
    local axes = {}
    
    for _, axis in ipairs(a.axes) do
        table.insert(axes, axis)
    end
    
    for _, axis in ipairs(b.axes) do
        table.insert(axes, axis)
    end
    
    return axes
end

-- 生成投影轴（3D专用）
function generateAxes3D(a, b)
    local axes = {}
    
    for _, axis in ipairs(a.axes) do
        table.insert(axes, axis)
    end
    
    for _, axis in ipairs(b.axes) do
        table.insert(axes, axis)
    end
    
    for i = 1, 3 do
        for j = 1, 3 do
            local cross = a.axes[i]:cross(b.axes[j])
            if cross:length() > 1e-6 then
                table.insert(axes, cross)
            end
        end
    end
    
    return axes
end

-- 投影计算
function project(obb, axis)
    local localCorners = generateCorners(obb)
    local worldCorners = {}
    
    for _, corner in ipairs(localCorners) do
        local worldPos = obb.center:clone()
        for i = 1, #obb.axes do
            worldPos = worldPos:add(corner.values[i] * obb.axes[i])
        end
        table.insert(worldCorners, worldPos)
    end
    
    local min = math.huge
    local max = -math.huge
    
    for _, corner in ipairs(worldCorners) do
        local proj = corner:dot(axis)
        min = math.min(min, proj)
        max = math.max(max, proj)
    end
    
    return min, max
end

-- OBB碰撞检测主函数
function OBBIntersects(a, b)
    local axes
    
    if #a.axes == 3 and #b.axes == 3 then
        axes = generateAxes3D(a, b)
    else
        axes = generateAxes2D(a, b)
    end
    
    for _, axis in ipairs(axes) do
        local minA, maxA = project(a, axis)
        local minB, maxB = project(b, axis)
        
        if maxA < minB or maxB < minA then
            return false
        end
    end
    
    return true
end

GJK算法

除了包围盒算法之外，还有一种高效的碰撞检测方案，GJK算法。了解GJK算法之前，需要了解一些定义，闵可夫斯基和/差，k阶单纯形，和Support函数；

闵可夫斯基和/差

闵可夫斯基和公式

，

其中，A和B代表多边形，而a和b的点代表多边形中的点，闵可夫斯基和满足交换律。
闵可夫斯基差，其实就是做减法运算的闵可夫斯基和。

，

我们可以把凸多边形想象成无数个点的集合，若两个凸多边形有并集，则必定存在共同点
GJK-1
下面会展示不相交的多边形与相交多边形的闵可夫斯基差，可以观察一下。
GJK-2
GJK-3
GJK-4
GJK-5
上面的图中可以发现，相交的多边形闵可夫斯基差的形状是包含原点的，其实理解起来不难，因为两个多边形相交，则必然存在重合点，重合点坐标相减，便是原点（0，0）；

k阶单纯形（simplex）

k阶单纯形指的是k维空间中的多胞形，该多胞形是k+1个顶点组成的凸包，理解一下就是2D时为三角形，3D时为四面体，依次类推。

** 对于上面两个相交的多边形例子，实际应用中，其实不需要求出完整的闵可夫斯基差，只需要在闵可夫斯基差内形成一个多边形，如下图所示，并使这个多边形尽可能包围原点，这个多边形就称为单纯形。即假如单纯形包围原点，则闵可夫斯基差必然包围原点。**

Support函数

Support函数的作用是计算多边形在给定方向上的最远点。如下图所示，在向量 a 方向的最远点为 A 点，在向量 b 方向的最远点为 B 点。这里在寻找给定方向上的最远点时，需要用到向量的点乘，Support函数可以让我们构建的单纯形包含的区域更大。
GJK-6
看完上面的定义，就大概理解GJK算法的核心了，根据两个多边形以及一个初始方向，通过迭代寻找包含原点的单纯形，若包含原点，则相交，若不包含，则继续迭代单纯形。

算法实现

2D-GJK算法实现
2D-GJK算法实现 
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <vector>
#include <cmath>

struct Vector2 {
    float x, y;
    Vector2 operator-(const Vector2& other) const { return {x - other.x, y - other.y}; }
    Vector2 operator+(const Vector2& other) const { return {x + other.x, y + other.y}; }
    Vector2 operator*(float scalar) const { return {x * scalar, y * scalar}; }
    float dot(const Vector2& other) const { return x * other.x + y * other.y; }
    Vector2 normalize() const { 
        float len = std::sqrt(x*x + y*y);
        return {x/len, y/len};
    }
};

class Shape {
public:
    virtual Vector2 getSupport(const Vector2& direction) const = 0;
};

bool gjk2D(const Shape& a, const Shape& b) {
    Vector2 d = {1, 0};
    std::vector<Vector2> simplex;
    
    while (true) {
        Vector2 aSupport = a.getSupport(d);
        Vector2 bSupport = b.getSupport(-d);
        Vector2 minkowski = aSupport - bSupport;
        
        if (minkowski.dot(d) <= 0) return false;
        
        simplex.push_back(minkowski);
        
        if (simplex.size() == 2) {
            Vector2 a1 = simplex[0];
            Vector2 a2 = simplex[1];
            
            Vector2 ab = a2 - a1;
            Vector2 ao = {0, 0} - a1;
            
            if (ab.dot(ao) <= 0) continue;
            
            Vector2 abPerp = {ab.y, -ab.x};
            d = abPerp.normalize();
            
        } else if (simplex.size() >= 3) {
            Vector2 a1 = simplex[0];
            Vector2 a2 = simplex[1];
            Vector2 a3 = simplex[2];
            
            Vector2 ab = a2 - a1;
            Vector2 ac = a3 - a1;
            Vector2 ao = {0, 0} - a1};
            
            Vector2 abXac = {ab.x*ac.y - ab.y*ac.x, ab.y*ac.x - ab.x*ac.y};
            
            if (abXac.dot(ao) > 0) {
                simplex.erase(simplex.begin());
                d = abXac.normalize();
            } else {
                Vector2 acXao = {ac.x*ao.y - ac.y*ao.x, ac.y*ao.x - ac.x*ao.y};
                if (acXao.dot(ab) > 0) {
                    simplex.erase(simplex.begin()+2);
                    d = acXao.normalize();
                } else {
                    Vector2 aoXab = {ao.x*ab.y - ao.y*ab.x, ao.y*ab.x - ao.x*ab.y};
                    if (aoXab.dot(ac) > 0) {
                        simplex.erase(simplex.begin()+1);
                        d = aoXab.normalize();
                    } else {
                        return true;
                    }
                }
            }
        }
    }
}
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
using System;
using System.Collections.Generic;

public struct Vector2
{
    public float X, Y;
    public Vector2(float x, float y) { X = x; Y = y; }
    public static Vector2 operator -(Vector2 a, Vector2 b) => new Vector2(a.X - b.X, a.Y - b.Y);
    public static Vector2 operator +(Vector2 a, Vector2 b) => new Vector2(a.X + b.X, a.Y + b.Y);
    public static Vector2 operator *(Vector2 v, float s) => new Vector2(v.X * s, v.Y * s);
    public float Dot(Vector2 other) => X * other.X + Y * other.Y;
    public Vector2 Normalize() {
        float len = (float)Math.Sqrt(X*X + Y*Y);
        return new Vector2(X/len, Y/len);
    }
}

public abstract class Shape
{
    public abstract Vector2 GetSupport(Vector2 direction);
}

public class GJK2D
{
    public static bool Detect(Shape a, Shape b)
    {
        Vector2 d = new Vector2(1, 0);
        List<Vector2> simplex = new List<Vector2>();
        
        while (true)
        {
            Vector2 aSupport = a.GetSupport(d);
            Vector2 bSupport = b.GetSupport(-d);
            Vector2 minkowski = aSupport - bSupport;
            
            if (minkowski.Dot(d) <= 0) return false;
            
            simplex.Add(minkowski);
            
            if (simplex.Count == 2)
            {
                Vector2 a1 = simplex[0];
                Vector2 a2 = simplex[1];
                
                Vector2 ab = a2 - a1;
                Vector2 ao = new Vector2(0, 0) - a1;
                
                if (ab.Dot(ao) <= 0) continue;
                
                Vector2 abPerp = new Vector2(ab.Y, -ab.X);
                d = abPerp.Normalize();
                
            }
            else if (simplex.Count >= 3)
            {
                Vector2 a1 = simplex[0];
                Vector2 a2 = simplex[1];
                Vector2 a3 = simplex[2];
                
                Vector2 ab = a2 - a1;
                Vector2 ac = a3 - a1;
                Vector2 ao = new Vector2(0, 0) - a1;
                
                Vector2 abXac = new Vector2(ab.X * ac.Y - ab.Y * ac.X, ab.Y * ac.X - ab.X * ac.Y);
                
                if (abXac.Dot(ao) > 0)
                {
                    simplex.RemoveAt(0);
                    d = abXac.Normalize();
                }
                else
                {
                    Vector2 acXao = new Vector2(ac.X * ao.Y - ac.Y * ao.X, ac.Y * ao.X - ac.X * ao.Y);
                    if (acXao.Dot(ab) > 0)
                    {
                        simplex.RemoveAt(2);
                        d = acXao.Normalize();
                    }
                    else
                    {
                        Vector2 aoXab = new Vector2(ao.X * ab.Y - ao.Y * ab.X, ao.Y * ab.X - ao.X * ab.Y);
                        if (aoXab.Dot(ac) > 0)
                        {
                            simplex.RemoveAt(1);
                            d = aoXab.Normalize();
                        }
                        else
                        {
                            return true;
                        }
                    }
                }
            }
        }
    }
}
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
class Vector2 {
    constructor(public x: number, public y: number) {}
    
    subtract(other: Vector2): Vector2 {
        return new Vector2(this.x - other.x, this.y - other.y);
    }
    
    add(other: Vector2): Vector2 {
        return new Vector2(this.x + other.x, this.y + other.y);
    }
    
    multiply(scalar: number): Vector2 {
        return new Vector2(this.x * scalar, this.y * scalar);
    }
    
    dot(other: Vector2): number {
        return this.x * other.x + this.y * other.y;
    }
    
    normalize(): Vector2 {
        const len = Math.sqrt(this.x**2 + this.y**2);
        return new Vector2(this.x/len, this.y/len);
    }
}

abstract class Shape {
    abstract getSupport(direction: Vector2): Vector2;
}

function gjk2D(a: Shape, b: Shape): boolean {
    let d = new Vector2(1, 0);
    const simplex: Vector2[] = [];
    
    while (true) {
        const aSupport = a.getSupport(d);
        const bSupport = b.getSupport(d.multiply(-1));
        const minkowski = aSupport.subtract(bSupport);
        
        if (minkowski.dot(d) <= 0) return false;
        
        simplex.push(minkowski);
        
        if (simplex.length === 2) {
            const a1 = simplex[0];
            const a2 = simplex[1];
            
            const ab = a2.subtract(a1);
            const ao = new Vector2(0, 0).subtract(a1);
            
            if (ab.dot(ao) <= 0) continue;
            
            const abPerp = new Vector2(ab.y, -ab.x);
            d = abPerp.normalize();
            
        } else if (simplex.length >= 3) {
            const a1 = simplex[0];
            const a2 = simplex[1];
            const a3 = simplex[2];
            
            const ab = a2.subtract(a1);
            const ac = a3.subtract(a1);
            const ao = new Vector2(0, 0).subtract(a1);
            
            const abXac = new Vector2(ab.x * ac.y - ab.y * ac.x, ab.y * ac.x - ab.x * ac.y);
            
            if (abXac.dot(ao) > 0) {
                simplex.splice(0, 1);
                d = abXac.normalize();
            } else {
                const acXao = new Vector2(ac.x * ao.y - ac.y * ao.x, ac.y * ao.x - ac.x * ao.y);
                if (acXao.dot(ab) > 0) {
                    simplex.splice(2, 1);
                    d = acXao.normalize();
                } else {
                    const aoXab = new Vector2(ao.x * ab.y - ao.y * ab.x, ao.y * ab.x - ao.x * ab.y);
                    if (aoXab.dot(ac) > 0) {
                        simplex.splice(1, 1);
                        d = aoXab.normalize();
                    } else {
                        return true;
                    }
                }
            }
        }
    }
}
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
Vector2 = {}
Vector2.__index = Vector2

function Vector2.new(x, y)
    return setmetatable({x = x or 0, y = y or 0}, Vector2)
end

function Vector2:__sub(other)
    return Vector2.new(self.x - other.x, self.y - other.y)
end

function Vector2:__add(other)
    return Vector2.new(self.x + other.x, self.y + other.y)
end

function Vector2:__mul(scalar)
    return Vector2.new(self.x * scalar, self.y * scalar)
end

function Vector2:dot(other)
    return self.x * other.x + self.y * other.y
end

function Vector2:normalize()
    local len = math.sqrt(self.x^2 + self.y^2)
    return Vector2.new(self.x/len, self.y/len)
end

Shape = {}
Shape.__index = Shape

function Shape:new()
    local o = {}
    setmetatable(o, self)
    return o
end

function Shape:getSupport(direction)
    -- Implement shape-specific support function
end

function gjk2D(a, b)
    local d = Vector2.new(1, 0)
    local simplex = {}
    
    while true do
        local aSupport = a:getSupport(d)
        local bSupport = b:getSupport(d:__mul(-1))
        local minkowski = aSupport:__sub(bSupport)
        
        if minkowski:dot(d) <= 0 then return false end
        
        table.insert(simplex, minkowski)
        
        if #simplex == 2 then
            local a1 = simplex[1]
            local a2 = simplex[2]
            
            local ab = a2:__sub(a1)
            local ao = Vector2.new(0,0):__sub(a1)
            
            if ab:dot(ao) <= 0 then
                table.remove(simplex, 1)
                goto continue
            end
            
            local abPerp = Vector2.new(ab.y, -ab.x)
            d = abPerp:normalize()
            
            ::continue::
        elseif #simplex >= 3 then
            local a1 = simplex[1]
            local a2 = simplex[2]
            local a3 = simplex[3]
            
            local ab = a2:__sub(a1)
            local ac = a3:__sub(a1)
            local ao = Vector2.new(0,0):__sub(a1)
            
            local abXac = Vector2.new(ab.x * ac.y - ab.y * ac.x, ab.y * ac.x - ab.x * ac.y)
            
            if abXac:dot(ao) > 0 then
                table.remove(simplex, 1)
                d = abXac:normalize()
            else
                local acXao = Vector2.new(ac.x * ao.y - ac.y * ao.x, ac.y * ao.x - ac.x * ao.y)
                if acXao:dot(ab) > 0 then
                    table.remove(simplex, 3)
                    d = acXao:normalize()
                else
                    local aoXab = Vector2.new(ao.x * ab.y - ao.y * ab.x, ao.y * ab.x - ao.x * ab.y)
                    if aoXab:dot(ac) > 0 then
                        table.remove(simplex, 2)
                        d = aoXab:normalize()
                    else
                        return true
                    end
                end
            end
        end
    end
end
3D-GJK算法实现
3D-GJK算法实现 
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include <vector>
#include <cmath>

struct Vector3 {
    float x, y, z;
    Vector3 operator-(const Vector3& other) const { 
        return {x - other.x, y - other.y, z - other.z}; 
    }
    
    Vector3 operator+(const Vector3& other) const { 
        return {x + other.x, y + other.y, z + other.z}; 
    }
    
    Vector3 operator*(float scalar) const { 
        return {x * scalar, y * scalar, z * scalar}; 
    }
    
    float dot(const Vector3& other) const { 
        return x * other.x + y * other.y + z * other.z; 
    }
    
    Vector3 cross(const Vector3& other) const {
        return {
            y*other.z - z*other.y,
            z*other.x - x*other.z,
            x*other.y - y*other.x
        };
    }
    
    Vector3 normalize() const { 
        float len = std::sqrt(x*x + y*y + z*z);
        return {x/len, y/len, z/len};
    }
};

class Shape {
public:
    virtual Vector3 getSupport(const Vector3& direction) const = 0;
};

bool gjk3D(const Shape& a, const Shape& b) {
    Vector3 d = {1, 0, 0};
    std::vector<Vector3> simplex;
    
    while (true) {
        Vector3 aSupport = a.getSupport(d);
        Vector3 bSupport = b.getSupport(-d);
        Vector3 minkowski = aSupport - bSupport;
        
        if (minkowski.dot(d) <= 0) return false;
        
        simplex.push_back(minkowski);
        
        if (simplex.size() == 2) {
            Vector3 a1 = simplex[0];
            Vector3 a2 = simplex[1];
            
            Vector3 ab = a2 - a1;
            Vector3 ao = {-a1.x, -a1.y, -a1.z};
            
            if (ab.dot(ao) <= 0) continue;
            
            Vector3 abPerp = ab.cross(ao).normalize();
            d = abPerp;
            
        } else if (simplex.size() == 3) {
            Vector3 a1 = simplex[0];
            Vector3 a2 = simplex[1];
            Vector3 a3 = simplex[2];
            
            Vector3 ab = a2 - a1;
            Vector3 ac = a3 - a1;
            Vector3 ao = {-a1.x, -a1.y, -a1.z};
            
            Vector3 abcNormal = ab.cross(ac);
            
            if (abcNormal.dot(ao) > 0) {
                Vector3 abXao = ab.cross(ao);
                d = abXao.normalize();
            } else {
                Vector3 acXao = ac.cross(ao);
                if (acXao.dot(ab) > 0) {
                    d = acXao.normalize();
                } else {
                    d = abcNormal.normalize();
                }
            }
            
        } else if (simplex.size() >= 4) {
            Vector3 a1 = simplex[0];
            Vector3 a2 = simplex[1];
            Vector3 a3 = simplex[2];
            Vector3 a4 = simplex[3];
            
            Vector3 ab = a2 - a1;
            Vector3 ac = a3 - a1;
            Vector3 ad = a4 - a1;
            Vector3 ao = {-a1.x, -a1.y, -a1.z};
            
            Vector3 abcNormal = ab.cross(ac);
            if (abcNormal.dot(ao) > 0) {
                simplex.erase(simplex.begin()+3);
                d = abcNormal;
            } else {
                Vector3 acdNormal = ac.cross(ad);
                if (acdNormal.dot(ao) > 0) {
                    simplex.erase(simplex.begin()+2);
                    d = acdNormal;
                } else {
                    Vector3 adbNormal = ad.cross(ab);
                    if (adbNormal.dot(ao) > 0) {
                        simplex.erase(simplex.begin()+1);
                        d = adbNormal;
                    } else {
                        return true;
                    }
                }
            }
        }
    }
}
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
using System;
using System.Collections.Generic;

public struct Vector3
{
    public float X, Y, Z;
    public Vector3(float x, float y, float z) { X = x; Y = y; Z = z; }
    public static Vector3 operator -(Vector3 a, Vector3 b) => 
        new Vector3(a.X - b.X, a.Y - b.Y, a.Z - b.Z);
    public static Vector3 operator +(Vector3 a, Vector3 b) => 
        new Vector3(a.X + b.X, a.Y + b.Y, a.Z + b.Z);
    public static Vector3 operator *(Vector3 v, float s) => 
        new Vector3(v.X * s, v.Y * s, v.Z * s);
    public float Dot(Vector3 other) => 
        X * other.X + Y * other.Y + Z * other.Z;
    public Vector3 Cross(Vector3 other) => 
        new Vector3(
            Y * other.Z - Z * other.Y,
            Z * other.X - X * other.Z,
            X * other.Y - Y * other.X);
    public Vector3 Normalize() {
        float len = (float)Math.Sqrt(X*X + Y*Y + Z*Z);
        return new Vector3(X/len, Y/len, Z/len);
    }
}

public abstract class Shape
{
    public abstract Vector3 GetSupport(Vector3 direction);
}

public class GJK3D
{
    public static bool Detect(Shape a, Shape b)
    {
        Vector3 d = new Vector3(1, 0, 0);
        List<Vector3> simplex = new List<Vector3>();
        
        while (true)
        {
            Vector3 aSupport = a.GetSupport(d);
            Vector3 bSupport = b.GetSupport(-d);
            Vector3 minkowski = aSupport - bSupport;
            
            if (minkowski.Dot(d) <= 0) return false;
            
            simplex.Add(minkowski);
            
            if (simplex.Count == 2)
            {
                Vector3 a1 = simplex[0];
                Vector3 a2 = simplex[1];
                
                Vector3 ab = a2 - a1;
                Vector3 ao = new Vector3(0, 0, 0) - a1;
                
                if (ab.Dot(ao) <= 0) continue;
                
                Vector3 abPerp = ab.Cross(ao).Normalize();
                d = abPerp;
                
            }
            else if (simplex.Count == 3)
            {
                Vector3 a1 = simplex[0];
                Vector3 a2 = simplex[1];
                Vector3 a3 = simplex[2];
                
                Vector3 ab = a2 - a1;
                Vector3 ac = a3 - a1;
                Vector3 ao = new Vector3(0, 0, 0) - a1;
                
                Vector3 abcNormal = ab.Cross(ac);
                
                if (abcNormal.Dot(ao) > 0)
                {
                    Vector3 abXao = ab.Cross(ao);
                    d = abXao.Normalize();
                }
                else
                {
                    Vector3 acXao = ac.Cross(ao);
                    if (acXao.Dot(ab) > 0)
                    {
                        d = acXao.Normalize();
                    }
                    else
                    {
                        d = abcNormal.Normalize();
                    }
                }
                
            }
            else if (simplex.Count >= 4)
            {
                Vector3 a1 = simplex[0];
                Vector3 a2 = simplex[1];
                Vector3 a3 = simplex[2];
                Vector3 a4 = simplex[3];
                
                Vector3 ab = a2 - a1;
                Vector3 ac = a3 - a1;
                Vector3 ad = a4 - a1;
                Vector3 ao = new Vector3(0, 0, 0) - a1;
                
                Vector3 abcNormal = ab.Cross(ac);
                if (abcNormal.Dot(ao) > 0)
                {
                    simplex.RemoveAt(3);
                    d = abcNormal;
                }
                else
                {
                    Vector3 acdNormal = ac.Cross(ad);
                    if (acdNormal.Dot(ao) > 0)
                    {
                        simplex.RemoveAt(2);
                        d = acdNormal;
                    }
                    else
                    {
                        Vector3 adbNormal = ad.Cross(ab);
                        if (adbNormal.Dot(ao) > 0)
                        {
                            simplex.RemoveAt(1);
                            d = adbNormal;
                        }
                        else
                        {
                            return true;
                        }
                    }
                }
            }
        }
    }
}
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
class Vector3 {
    constructor(public x: number, public y: number, public z: number) {}
    
    subtract(other: Vector3): Vector3 {
        return new Vector3(this.x - other.x, this.y - other.y, this.z - other.z);
    }
    
    add(other: Vector3): Vector3 {
        return new Vector3(this.x + other.x, this.y + other.y, this.z + other.z);
    }
    
    multiply(scalar: number): Vector3 {
        return new Vector3(this.x * scalar, this.y * scalar, this.z * scalar);
    }
    
    dot(other: Vector3): number {
        return this.x * other.x + this.y * other.y + this.z * other.z;
    }
    
    cross(other: Vector3): Vector3 {
        return new Vector3(
            this.y * other.z - this.z * other.y,
            this.z * other.x - this.x * other.z,
            this.x * other.y - this.y * other.x
        );
    }
    
    normalize(): Vector3 {
        const len = Math.sqrt(this.x**2 + this.y**2 + this.z**2);
        return new Vector3(this.x/len, this.y/len, this.z/len);
    }
}

abstract class Shape {
    abstract getSupport(direction: Vector3): Vector3;
}

function gjk3D(a: Shape, b: Shape): boolean {
    let d = new Vector3(1, 0, 0);
    const simplex: Vector3[] = [];
    
    while (true) {
        const aSupport = a.getSupport(d);
        const bSupport = b.getSupport(d.multiply(-1));
        const minkowski = aSupport.subtract(bSupport);
        
        if (minkowski.dot(d) <= 0) return false;
        
        simplex.push(minkowski);
        
        if (simplex.length === 2) {
            const a1 = simplex[0];
            const a2 = simplex[1];
            
            const ab = a2.subtract(a1);
            const ao = new Vector3(0, 0, 0).subtract(a1);
            
            if (ab.dot(ao) <= 0) continue;
            
            const abPerp = ab.cross(ao).normalize();
            d = abPerp;
            
        } else if (simplex.length === 3) {
            const a1 = simplex[0];
            const a2 = simplex[1];
            const a3 = simplex[2];
            
            const ab = a2.subtract(a1);
            const ac = a3.subtract(a1);
            const ao = new Vector3(0, 0, 0).subtract(a1);
            
            const abcNormal = ab.cross(ac);
            
            if (abcNormal.dot(ao) > 0) {
                const abXao = ab.cross(ao);
                d = abXao.normalize();
            } else {
                const acXao = ac.cross(ao);
                if (acXao.dot(ab) > 0) {
                    d = acXao.normalize();
                } else {
                    d = abcNormal.normalize();
                }
            }
            
        } else if (simplex.length >= 4) {
            const a1 = simplex[0];
            const a2 = simplex[1];
            const a3 = simplex[2];
            const a4 = simplex[3];
            
            const ab = a2.subtract(a1);
            const ac = a3.subtract(a1);
            const ad = a4.subtract(a1);
            const ao = new Vector3(0, 0, 0).subtract(a1);
            
            const abcNormal = ab.cross(ac);
            if (abcNormal.dot(ao) > 0) {
                simplex.splice(3, 1);
                d = abcNormal;
            } else {
                const acdNormal = ac.cross(ad);
                if (acdNormal.dot(ao) > 0) {
                    simplex.splice(2, 1);
                    d = acdNormal;
                } else {
                    const adbNormal = ad.cross(ab);
                    if (adbNormal.dot(ao) > 0) {
                        simplex.splice(1, 1);
                        d = adbNormal;
                    } else {
                        return true;
                    }
                }
            }
        }
    }
}
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
Vector3 = {}
Vector3.__index = Vector3

function Vector3.new(x, y, z)
    return setmetatable({x = x or 0, y = y or 0, z = z or 0}, Vector3)
end

function Vector3:__sub(other)
    return Vector3.new(self.x - other.x, self.y - other.y, self.z - other.z)
end

function Vector3:__add(other)
    return Vector3.new(self.x + other.x, self.y + other.y, self.z + other.z)
end

function Vector3:__mul(scalar)
    return Vector3.new(self.x * scalar, self.y * scalar, self.z * scalar)
end

function Vector3:dot(other)
    return self.x * other.x + self.y * other.y + self.z * other.z
end

function Vector3:cross(other)
    return Vector3.new(
        self.y * other.z - self.z * other.y,
        self.z * other.x - self.x * other.z,
        self.x * other.y - self.y * other.x
    )
end

function Vector3:normalize()
    local len = math.sqrt(self.x^2 + self.y^2 + self.z^2)
    return Vector3.new(self.x/len, self.y/len, self.z/len)
end

Shape = {}
Shape.__index = Shape

function Shape:new()
    local o = {}
    setmetatable(o, self)
    return o
end

function Shape:getSupport(direction)
    -- Implement shape-specific support function
end

function gjk3D(a, b)
    local d = Vector3.new(1, 0, 0)
    local simplex = {}
    
    while true do
        local aSupport = a:getSupport(d)
        local bSupport = b:getSupport(d:__mul(-1))
        local minkowski = aSupport:__sub(bSupport)
        
        if minkowski:dot(d) <= 0 then return false end
        
        table.insert(simplex, minkowski)
        
        if #simplex == 2 then
            local a1 = simplex[1]
            local a2 = simplex[2]
            
            local ab = a2:__sub(a1)
            local ao = Vector3.new(0,0,0):__sub(a1)
            
            if ab:dot(ao) <= 0 then
                table.remove(simplex, 1)
                goto continue
            end
            
            local abPerp = ab:cross(ao):normalize()
            d = abPerp
            
            ::continue::
        elseif #simplex == 3 then
            local a1 = simplex[1]
            local a2 = simplex[2]
            local a3 = simplex[3]
            
            local ab = a2:__sub(a1)
            local ac = a3:__sub(a1)
            local ao = Vector3.new(0,0,0):__sub(a1)
            
            local abcNormal = ab:cross(ac)
            
            if abcNormal:dot(ao) > 0 then
                local abXao = ab:cross(ao)
                d = abXao:normalize()
            else
                local acXao = ac:cross(ao)
                if acXao:dot(ab) > 0 then
                    d = acXao:normalize()
                else
                    d = abcNormal:normalize()
                end
            end
        elseif #simplex >= 4 then
            local a1 = simplex[1]
            local a2 = simplex[2]
            local a3 = simplex[3]
            local a4 = simplex[4]
            
            local ab = a2:__sub(a1)
            local ac = a3:__sub(a1)
            local ad = a4:__sub(a1)
            local ao = Vector3.new(0,0,0):__sub(a1)
            
            local abcNormal = ab:cross(ac)
            if abcNormal:dot(ao) > 0 then
                table.remove(simplex, 4)
                d = abcNormal
            else
                local acdNormal = ac:cross(ad)
                if acdNormal:dot(ao) > 0 then
                    table.remove(simplex, 3)
                    d = acdNormal
                else
                    local adbNormal = ad:cross(ab)
                    if adbNormal:dot(ao) > 0 then
                        table.remove(simplex, 2)
                        d = adbNormal
                    else
                        return true
                    end
                end
            end
        end
    end
end
  • 标题: 【游戏算法】 - 碰撞检测
  • 作者: 宋
  • 创建于 : 2020-08-27 19:07:05
  • 更新于 : 2021-03-15 20:30:39
  • 链接: https://sxl-space.tk/2020/08/27/001_Collision-Detect/
  • 版权声明: 版权所有 © 宋，禁止转载。
目录
【游戏算法】 - 碰撞检测
  1. 1. 本文介绍一些常用的碰撞检测算法。
    1. 1.1. 球包围盒（2D下即圆形包围盒）
      1. 1.1.1. 球形包围盒 是一个用最小球包裹物体的几何形状，有以下特点
      2. 1.1.2. 计算公式(2D圆包围盒可视y坐标为0)
      3. 1.1.3. 个人认为球形包围盒适合于初步碰撞检测的实现
    2. 1.2. 轴对齐（AABB）包围盒（Axis-Aligned Bounding Box）
      1. 1.2.1. AABB碰撞检测的优缺点分析
      2. 1.2.2. 算法实现
    3. 1.3. OBB包围盒（Oriented Bounding Box）
      1. 1.3.1. 算法实现
    4. 1.4. GJK算法
      1. 1.4.1. 闵可夫斯基和/差
      2. 1.4.2. k阶单纯形（simplex）
      3. 1.4.3. Support函数
      4. 1.4.4. 算法实现
        1. 1.4.4.1. 2D-GJK算法实现
        2. 1.4.4.2. 3D-GJK算法实现