抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >

碰撞检测之射线与 AABB 和 OBB

算法碰撞检测

发布于：2023年10月15日

次浏览

字数：2k 字

时长：9 分钟

简介

射线检测可以用于拾取物体、判断前方是否有障碍物、判断是否碰撞等场景，本文介绍射线与 AABB 以及射线与 OBB 的检测原理。射线与 AABB 检测的原理是由射线与 OBB 检测简化而来，因此放在一起介绍。

原理

当我们判断一条射线是否与一个矩形相交的时候，我们可以判断射线和矩形四条边的延长线的交点之间的关系。（slab 碰撞检测）

如图所示，我们有一条绿色射线与黑色矩形相交，得到四个点 P1、P2、P3、P4。其中在 y 轴方向的交点为 P1、P2，在 x 轴方向的交点为 P3、P4；我们有一条紫色射线与黑色矩形相交，得到四个点 P1’、P2’、P3’、P4’。其中在 x 轴方向的交点为 P1’、P2’，在 y 轴方向的交点为 P3’、P4’。

观察图像我们可以发现，当射线与圆相交的时候，P1P2 与 P3P4 在射线上存在相交的部分，当射线与圆不相交的时候，P1’P2’与 P3’P4’在射线上不存在相交的部分。

因此我们可以得到一个结论：当矩形两个方向轴上的四条边的延长线与射线相交的时候，所有轴向上的最小交点比最大交点要小，并且所有最小交点的最大值比所有最大交点的最小值都要小，这时候射线与矩形相交。

即：每个轴两条边的两个交点中的近点 P1、P3 中的最大值，要比远点 P2、P4 中的最小值还小，这样射线就与矩形相交。

所以对于射线与矩形，我们有$max(P1,P3)<min(P2,P4)$，化为通式的话就是$max(Pmin_x,Pmin_y)<min(Pmax_x,Pmax_y)$

拓展到三维空间也是一样，二维空间是比较两个轴，三维空间就是比较三个轴，也要满足$max(Pmin_x,Pmin_y,Pmin_z)<min(Pmax_x,Pmax_y,Pmax_z)$的关系。

在 OBB 中

我们设射线 R 的起点为 C1，长度为 t，方向为 Dir；平面 S 的法线为 n，平面中一点为 D，平面到 R 起点的距离为 d，平面与射线的交点为 P，我们可以得到

射线的方程为： $P=C1+t*Dir$

平面的方程为： $Dot(P,n)=d$

当射线与平面相交的时候，两个方程的值相等，我们可以得到如下关系： $Dot(C1+t*Dir,n)=d$

由于点乘符合分配律，所以方程化为： $Dot(C1,n)+Dot(t*Dir,n)=d$

我们想要求出射线的长度 t，因此方程改造一下变成： $Dot(t*Dir,n)=d-Dot(C1,n)$

由于点乘符合结合律，所以方程化为： $t*Dot(Dir,n)=d-Dot(C1,n)$

化简得到： $t=(d-Dot(C1,n))/Dot(Dir,n)$

因为我们不知道 d，所以根据平面方程，我们可以得到： $t=(Dot(P,n)-Dot(C1,n))/Dot(Dir,n)$

由分配律，我们最终得到： $t=(Dot(P-C1,n))/Dot(Dir,n)$

在 OBB 包围盒中，最大点和最小点分别横跨三个最大面和最小面，因此满足方程：

$Dot(P_{min},n)=d$

$Dot(P_{max},n)=d$

所以，三个最小面的最小距离为： $t=(Dot(P_{min}-C1,n))/Dot(Dir,n)$

三个最大面的最大距离为： $t=(Dot(P_{max}-C1,n))/Dot(Dir,n)$

最后，我们只需要判断$max(t_{min_x},t_{min_y},t_{min_z})<min(t_{max_x},t_{max_y},t_{max_z})$就能知道是否相交。

交点只要带入射线方程即可得到。

需要注意的是，我们都是以射线和包围盒方向轴同向为正方向，因此当方向相反的时候（$Dot(Dir,n)<0$），我们要交换$t_{min}$和$t_{max}$的值。

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
//包围盒数据结构
public class CollisionData : MonoBehaviour
{
    public Vector3 center = Vector3.zero;
    public float radius = 1.0f;
    public Vector3 direction = Vector3.zero;
    public Vector3[] vertexts = new Vector3[8];
    public Vector3[] axes = new Vector3[3];
}
---------------------------------------------
/// <summary>
/// 射线和OBB检测
/// <param name="data1"></param>
/// <param name="data2"></param>
/// </summary>
private bool CollisionRay2OBB(CollisionData data1,CollisionData data2)
{
    //判断不在OBB内
    Vector3 centerDis = data1.center - data2.center;
    float ray2ObbX = Vector3.Dot(centerDis, data2.axes[0]);
    float ray2ObbY = Vector3.Dot(centerDis, data2.axes[1]);
    float ray2ObbZ = Vector3.Dot(centerDis, data2.axes[2]);
    bool checkNotInside = ray2ObbX < -data2.extents[0] || ray2ObbX > data2.extents[0] ||
        ray2ObbY < -data2.extents[1] || ray2ObbY > data2.extents[1] ||
        ray2ObbZ < -data2.extents[2] || ray2ObbZ > data2.extents[2];
    //判断反向情况
    bool checkFoward = Vector3.Dot(data2.center - data1.center, data1.direction) < 0;
    if (checkNotInside && checkFoward)
    {
        return false;
    }

    //判断是否相交
    Vector3 min = Vector3.zero;
    Vector3 minP = data2.vertexts[4] - data1.center;
    min.x = Vector3.Dot(minP, data2.axes[0]);
    min.y = Vector3.Dot(minP, data2.axes[1]);
    min.z = Vector3.Dot(minP, data2.axes[2]);

    Vector3 max = Vector3.zero;
    Vector3 maxP = data2.vertexts[2] - data1.center;
    max.x = Vector3.Dot(maxP, data2.axes[0]);
    max.y = Vector3.Dot(maxP, data2.axes[1]);
    max.z = Vector3.Dot(maxP, data2.axes[2]);


    Vector3 projection = Vector3.zero;
    projection.x = 1 / Vector3.Dot(data1.direction, data2.axes[0]);
    projection.y = 1 / Vector3.Dot(data1.direction, data2.axes[1]);
    projection.z = 1 / Vector3.Dot(data1.direction, data2.axes[2]);

    Vector3 pMin = Vector3.Scale(min, projection);
    Vector3 pMax = Vector3.Scale(max, projection);

    if (projection.x < 0) Swap(ref pMin.x, ref pMax.x);
    if (projection.y < 0) Swap(ref pMin.y, ref pMax.y);
    if (projection.z < 0) Swap(ref pMin.z, ref pMax.z);


    float n = Mathf.Max(pMin.x, pMin.y, pMin.z);
    float f = Mathf.Min(pMax.x, pMax.y, pMax.z);

    Debug.Log(n + " " + f);
    Debug.Log(pMin + " " + pMax);
    Debug.Log(projection);

    bool res = false;
    if (!checkNotInside)
    {
        res = true;
        Vector3 point = data1.center + data1.direction * f;

        ConsoleUtils.Log("碰撞点", point);
    }
    else
    {
        if (n < f && data1.radius >= n)
        {
            res = true;
        }
        else
        {
            return false;
        }

        Vector3 point = data1.center + data1.direction * n;

        ConsoleUtils.Log("碰撞点", point);
    }
    return res;
}

在 AABB 中

由于 AABB 包围盒的方向轴与坐标轴一致，所以我们可以简化方程。

在 X 轴上，我们有$t_{yz}=(Dot(P-C1,n_{yz}))/Dot(Dir,n_{yz})$

又因为$n_{yz}=(1,0,0)$，只有 x 上有值

所以$t_{yz}=(P.x-C1.x)/Dir.x$

同理可得其他面也是这样，因此最后我们可以得到如下方程：

$t=(P-C1)/Dir$

其他部分就和射线与 OBB 的算法一致。

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
//包围盒数据结构
public class CollisionData : MonoBehaviour
{
    public Vector3 center = Vector3.zero;
    public float radius = 1.0f;
    public Vector3 direction = Vector3.zero;
    public Vector3 max = Vector3.zero;
    public Vector3 min = Vector3.zero;
}
---------------------------------------------
/// <summary>
/// 射线和AABB检测
/// <param name="data1"></param>
/// <param name="data2"></param>
/// </summary>
private void CollisionRay2AABB(CollisionData data1,CollisionData data2)
{
    //判断是否不在AABB内
    bool checkNotInside = data1.center.x > data2.max.x || data1.center.x < data2.min.x ||
        data1.center.y > data2.max.y || data1.center.y < data2.min.y ||
        data1.center.z > data2.max.z || data1.center.z < data2.min.z;
    //判断反向情况
    bool checkForawd = Vector3.Dot(data2.center - data1.center, data1.direction) < 0;
    if (checkNotInside && checkForawd)
    {
        line1.Collided(false);
        line2.Collided(false);
        return;
    }

    //判断是否相交
    Vector3 min = data2.min - data1.center;
    Vector3 max = data2.max - data1.center;

    Vector3 projection = new Vector3(1 / data1.direction.x, 1 / data1.direction.y, 1 / data1.direction.z);

    Vector3 pMin = Vector3.Scale(min, projection);
    Vector3 pMax = Vector3.Scale(max, projection);

    if (data1.direction.x < 0) Swap(ref pMin.x, ref pMax.x);
    if (data1.direction.y < 0) Swap(ref pMin.y, ref pMax.y);
    if (data1.direction.z < 0) Swap(ref pMin.z, ref pMax.z);

    float n = Mathf.Max(pMin.x, pMin.y, pMin.z);
    float f = Mathf.Min(pMax.x, pMax.y, pMax.z);

    if (!checkNotInside)
    {
        line1.Collided(true);
        line2.Collided(true);
        Vector3 point = data1.center + data1.direction * f;

        ConsoleUtils.Log("碰撞点", point);
    }
    else
    {
        if (n < f && data1.radius >= n)
        {
            line1.Collided(true);
            line2.Collided(true);
        }
        else
        {
            line1.Collided(false);
            line2.Collided(false);
            return;
        }

        Vector3 point = data1.center + data1.direction * n;

        ConsoleUtils.Log("碰撞点", point);
    }
}

其他情况

和射线与圆相交检测一样，当射线在包围盒内的时候一定相交；当射线与包围盒相反的时候一定不相交。

对于 AABB 来说，只要判断射线起点和 AABB 包围盒的最大最小点的关系就可以判断是否在包围盒内，对于 OBB 来说要把射线起点映射到 OBB 坐标系中，然后按照 AABB 的方式来判断。

碰撞检测示例工程

更新日志

2024-03-21

  1. 修复描述错误。

2023-10-15

  1. 更新基本内容。

更新于：2024年9月18日

算法

C#

碰撞检测

AABB

OBB

射线

评论