碰撞检测之线段检测

简介

本文主要阐述线段之间的碰撞检测原理和实现方式以及线段之间最小距离（本文方法返回的结果是距离的平方）的计算方式。

原理

在求线段最小距离之前，我们先补充一个求一点在线段上的最近点的方法。

我们计算该点在线段上的投影大小，根据投影大小我们可以知道该点在线段上的比例，然后通过这个比例求出线段上的最合适的检测点，即该点在线段上的最近点。如果检测点超出线段范围，那我们就要使其移动到线段极限位置。

求点在线段上最近点的代码如下：

private Vector3 GetClosestPointOnLineSegment(Vector3 start, Vector3 end, Vector3 point)
{
    Vector3 line = end - start;
    //dot line line 求长度平方
    float ratio = Vector3.Dot(point - start, line) / Vector3.Dot(line, line);
    ratio = Mathf.Min(Mathf.Max(ratio, 0), 1);
    return start + ratio * line;
}

该方法在求线段最小距离的时候会用到。

求线段之间的最小距离分为两种情况：

线段平行。
线段不平行。

那么我们如何判断线段是否平行？

我们可以比较两条线段的方向向量，如果两条线段的方向向量相等的话，这两条线段就平行。

1 2	//判断完全平行 bool isParallel = line1.normalized == line2.normalized;

线段平行

在线段平行的情况下，我们只需要计算一条线段的两个端点相对于另一条线段的距离，取其中最小的距离即可。

计算两个端点的原因是在某些情况下，一条线段的两个端点与另一条线段的距离是不一样的。

在左图的情况下，如果以短线段为基底，长线段两端点为检测点的话会得到长于两线段距离的结果，因此我们在计算的时候先比较线段长短再根据情况调整基底和检测点，以保证长线段作为基底，短线段的两点作为检测点。

在右图的情况下，不管是哪条线段做基底，哪条线段做检测点，都会得到一个同样的最小距离。

一致的情况

不一致的情况

//完全平行
float len1 = line1.sqrMagnitude;
float len2 = line2.sqrMagnitude;

float disStart;
float disEnd;

if (len1 > len2)
{
    disStart = (GetClosestPointOnLineSegment(start1, end1, start2) - start2).sqrMagnitude;
    disEnd = (GetClosestPointOnLineSegment(start1, end1, end2) - end2).sqrMagnitude;
}
else
{
    disStart = (GetClosestPointOnLineSegment(start2, end2, start1) - start1).sqrMagnitude;
    disEnd = (GetClosestPointOnLineSegment(start2, end2, end1) - end1).sqrMagnitude;
}

dis = Mathf.Min(disStart, disEnd);

线段不平行

在线段不平行的情况下，又分为两种情况：

线段同面。
线段不同面。

判断线段是否同面，我们就需要知道两条线段之间的距离是否为 0，如果为 0 的话，两条线段就同面。

那么我们如何判断两条线段之间的距离是否为 0 呢？

根据定理，两条直线之间的最短距离等于两条直线的中垂线的长度。因此我们只需要得到中垂线就能计算出两条直线之间的距离。

中垂线的方向向量我们可以通过向量叉乘来得到。

又根据 $中垂线长度=\dfrac{叉乘向量和两直线任意两点连线的点积}{叉乘向量的模长}$

即 $B的投影长度=\dfrac{AB 的点积}{A 的模长}$

我们就能得到两直线之间的距离，同时也是两线段平面之间的距离，也就是两线段之间的距离。

1
2
3

Vector3 normal = Vector3.Cross(line1, line2);
float len = normal.sqrMagnitude;
float dis2Line = Mathf.Pow(Mathf.Abs(Vector3.Dot(start2 - start1, normal)), 2) / len;

线段同面

在线段同面的时候，我们需要判断两条线段是否相交，如果相交的话，距离就为 0；不相交的话，我们分别计算每条线段的两个顶点相对于另一条线段的距离，最后选择最小的距离。

//同面
// 检测线段相交
bool isLineCross = CheckLineCross(start1, end1, start2, end2);
if (isLineCross)
{
    dis = 0;
}
else
{
    float disStart1 = (GetClosestPointOnLineSegment(start1, end1, start2) - start2).sqrMagnitude;
    float disEnd1 = (GetClosestPointOnLineSegment(start1, end1, end2) - end2).sqrMagnitude;
    float disStart2 = (GetClosestPointOnLineSegment(start2, end2, start1) - start1).sqrMagnitude;
    float disEnd2 = (GetClosestPointOnLineSegment(start2, end2, end1) - end1).sqrMagnitude;
    dis = Mathf.Min(disStart1, disEnd1, disStart2, disEnd2);
}

线段不同面

在线段不同面的时候，我们把其中一条线段平移到另一条线段的平面上，然后按照线段同面的方法来得到最小的距离。不过在这种情况下，线段交叉时候的距离为两个线段的中垂线的长度。

为什么不是直接用中垂线长度呢？

因为中垂线长度是直线之间的最短距离，而线段是有范围的，这个范围不一定经过中垂线的端点，在线段共面交叉的时候，中垂线的长度才是有效的。

如何平移到同一个平面？

只需要让 line2 根据中垂线方向移动中垂线长度即可。不过我们要注意移动的是正方向还是负方向，可以根据两线段任意两点的方向向量来决定。

float offset = Mathf.Sqrt(dis2Line);
//计算line2相对line1的方位
Vector3 directionStart = start2 - start1;
float direction = Vector3.Dot(directionStart, normal) > 0 ? 1 : -1;
// 检测线段相交
bool isLineCross = CheckLineCross(start1, end1, start2 - normal.normalized * (offset * direction),
    end2 - normal.normalized * (offset * direction));

if (isLineCross)
{
    dis = dis2Line;
}
else
{
    float disStart1 = (GetClosestPointOnLineSegment(start1, end1, start2) - start2).sqrMagnitude;
    float disEnd1 = (GetClosestPointOnLineSegment(start1, end1, end2) - end2).sqrMagnitude;
    float disStart2 = (GetClosestPointOnLineSegment(start2, end2, start1) - start1).sqrMagnitude;
    float disEnd2 = (GetClosestPointOnLineSegment(start2, end2, end1) - end1).sqrMagnitude;
    dis = Mathf.Min(disStart1, disEnd1, disStart2, disEnd2);
}

线段交叉检测

上文我们提到需要检测线段是否交叉，交叉检测需要进行两个步骤：

快速排斥。
跨立检测。

快速排斥是为了能够以简单的判定快速去除不相交的情况。原理和 SAT 有点类似，在 XYZ 三轴方向上如果有一个轴存在投影不相交的情况，则两线段一定不相交。

跨立检测的方法和叉乘有关，如果两条线段互相跨立，则其中一条线段的端点在另一条线段的两侧。

对于 A1A2 线段来说，判断 B1A2 和 B2A2 相对于 A1A2 的左右方向来说是否相反，是的话就证明 B1、B2 在 A1A2 两边；同理对于 B1B2 线段来说，判断 A1B1 和 A2B1 相对于 A1A2 的左右方向来说是否相反，是的话就证明 A1、A2 在 B1B2 两边。

private bool CheckLineCross(Vector3 start1, Vector3 end1, Vector3 start2, Vector3 end2)
{
    //快速排斥
    if (Mathf.Min(start1.x, end1.x) - Mathf.Max(start2.x, end2.x) > 0.01 ||
        Mathf.Min(start1.y, end1.y) - Mathf.Max(start2.y, end2.y) > 0.01 ||
        Mathf.Min(start1.z, end1.z) - Mathf.Max(start2.z, end2.z) > 0.01 ||
        Mathf.Min(start2.x, end2.x) - Mathf.Max(start1.x, end1.x) > 0.01 ||
        Mathf.Min(start2.y, end2.y) - Mathf.Max(start1.y, end1.y) > 0.01 ||
        Mathf.Min(start2.z, end2.z) - Mathf.Max(start1.z, end1.z) > 0.01)
    {
        return false;
    }

    Vector3 line1 = end1 - start1;
    Vector3 line2 = end2 - start2;

    //跨立
    if (Vector3.Cross(line1, start2 - start1).normalized == Vector3.Cross(line1, end2 - start1).normalized ||
        Vector3.Cross(line2, start1 - start2).normalized == Vector3.Cross(line2, end1 - start2).normalized)
    {
        return false;
    }

    return true;
}

这部分也可以直接用于线段的碰撞检测。

代码

线段相交检测

private bool CheckLineCross(Vector3 start1, Vector3 end1, Vector3 start2, Vector3 end2)
{
    //快速排斥
    if (Mathf.Min(start1.x, end1.x) - Mathf.Max(start2.x, end2.x) > 0.01 ||
        Mathf.Min(start1.y, end1.y) - Mathf.Max(start2.y, end2.y) > 0.01 ||
        Mathf.Min(start1.z, end1.z) - Mathf.Max(start2.z, end2.z) > 0.01 ||
        Mathf.Min(start2.x, end2.x) - Mathf.Max(start1.x, end1.x) > 0.01 ||
        Mathf.Min(start2.y, end2.y) - Mathf.Max(start1.y, end1.y) > 0.01 ||
        Mathf.Min(start2.z, end2.z) - Mathf.Max(start1.z, end1.z) > 0.01)
    {
        return false;
    }

    Vector3 line1 = end1 - start1;
    Vector3 line2 = end2 - start2;

    //跨立
    if (Vector3.Cross(line1, start2 - start1).normalized == Vector3.Cross(line1, end2 - start1).normalized ||
        Vector3.Cross(line2, start1 - start2).normalized == Vector3.Cross(line2, end1 - start2).normalized)
    {
        return false;
    }

    return true;
}

/// <summary>
/// 求两条线段的最短距离
/// </summary>
/// <param name="start1"></param>
/// <param name="end1"></param>
/// <param name="start2"></param>
/// <param name="end2"></param>
/// <returns></returns>
private float GetClosestDistanceBetweenLinesSqr(Vector3 start1, Vector3 end1, Vector3 start2, Vector3 end2)
{
    Vector3 line1 = end1 - start1;
    Vector3 line2 = end2 - start2;

    float dis = 0;
    //判断完全平行
    bool isParallel = line1.normalized == line2.normalized;
    if (isParallel)
    {
        //完全平行
        float len1 = line1.sqrMagnitude;
        float len2 = line2.sqrMagnitude;

        float disStart;
        float disEnd;

        if (len1 > len2)
        {
            disStart = (GetClosestPointOnLineSegment(start1, end1, start2) - start2).sqrMagnitude;
            disEnd = (GetClosestPointOnLineSegment(start1, end1, end2) - end2).sqrMagnitude;
        }
        else
        {
            disStart = (GetClosestPointOnLineSegment(start2, end2, start1) - start1).sqrMagnitude;
            disEnd = (GetClosestPointOnLineSegment(start2, end2, end1) - end1).sqrMagnitude;
        }

        dis = Mathf.Min(disStart, disEnd);
    }
    else
    {
        Vector3 normal = Vector3.Cross(line1, line2);
        float len = normal.sqrMagnitude;
        float dis2Line = Mathf.Pow(Mathf.Abs(Vector3.Dot(start2 - start1, normal)), 2) / len;
        //判断同面
        if (dis2Line == 0)
        {
            //同面
            // 检测线段相交
            bool isLineCross = CheckLineCross(start1, end1, start2, end2);
            if (isLineCross)
            {
                dis = 0;
            }
            else
            {
                float disStart1 = (GetClosestPointOnLineSegment(start1, end1, start2) - start2).sqrMagnitude;
                float disEnd1 = (GetClosestPointOnLineSegment(start1, end1, end2) - end2).sqrMagnitude;
                float disStart2 = (GetClosestPointOnLineSegment(start2, end2, start1) - start1).sqrMagnitude;
                float disEnd2 = (GetClosestPointOnLineSegment(start2, end2, end1) - end1).sqrMagnitude;
                dis = Mathf.Min(disStart1, disEnd1, disStart2, disEnd2);
            }
        }
        else
        {
            float offset = Mathf.Sqrt(dis2Line);
            //计算line2相对line1的方位
            Vector3 directionStart = start2 - start1;
            float direction = Vector3.Dot(directionStart, normal) > 0 ? 1 : -1;
            // 检测线段相交
            bool isLineCross = CheckLineCross(start1, end1, start2 - normal.normalized * (offset * direction),
                end2 - normal.normalized * (offset * direction));

            if (isLineCross)
            {
                dis = dis2Line;
            }
            else
            {
                float disStart1 = (GetClosestPointOnLineSegment(start1, end1, start2) - start2).sqrMagnitude;
                float disEnd1 = (GetClosestPointOnLineSegment(start1, end1, end2) - end2).sqrMagnitude;
                float disStart2 = (GetClosestPointOnLineSegment(start2, end2, start1) - start1).sqrMagnitude;
                float disEnd2 = (GetClosestPointOnLineSegment(start2, end2, end1) - end1).sqrMagnitude;
                dis = Mathf.Min(disStart1, disEnd1, disStart2, disEnd2);
            }
        }
    }

    return dis;
}

项目地址

更新日志

2024-07-13

修正平行情况下的线段检测问题。

2024-05-19

更新基础内容。