高等向量数学

平面

点乘对于单位向量还有一个有趣的性质. 想象垂直于这个向量(通过原点)经过一个平面. 平面将整个空间划分为正(在平面上)和负(在平面下),(与普遍的看法相反)您也可以在2D中使用它们的数学:

../../_images/tutovec10.png

垂直于表面的单位向量(因此, 它们描述了表面的方向)称为 单位法向量 . 不过, 它们通常只是缩写为 法线 . 法线出现在平面, 3D几何中(以确定每个面或顶点的侧边), 等等. 一个 法线 就是一个 单位向量 , 但是由于它的使用, 它被称为 法线 .(就像我们说坐标(0,0)就是原点一样!).

它就像看起来那样简单. 平面经过原点, 它的表面垂直于单位向量(或 法线 ). 指向向量的一边是正半空间, 而另一边是负半空间. 在3维空间中, 这完全相同, 除了平面是一个无限的表面(想象一张无限伸展的平坦纸张, 它固定在原点)而不是直线.

到平面的距离

现在, 我们很清楚了平面是什么, 让我们再回到点乘上. 单位向量 和任何 空间点 之间的点乘(是的, 这次我们在向量和位置之间进行点乘), 将返回 从点到平面的距离 :

var distance = normal.dot(point)
var distance = normal.Dot(point);

但不仅仅是绝对距离, 如果点在负半空间中, 距离也是负的:

../../_images/tutovec11.png

这使我们能够知道点在平面的哪一侧.

远离原点

我知道您在想什么!到目前为止, 这还不错, 但 真正的 平面在空间中无处不在, 而不仅仅是通过原点的平面. 您想要真正的 平面 , 您 现在 就想行动起来.

记住, 平面不仅把空间分成两半, 而且它们还有 极性 . 这意味着有可能有完全重叠的平面, 但是它们的负半空间和正半空间是相反的.

记住这一点, 让我们将整个平面描述为 法线 N距原点的距离 标量 D . 因此, 我们的平面将由N和D表示, 例如:

../../_images/tutovec12.png

对于3维的情况,Godot提供了一个 Plane 内置类型来处理这个问题.

基本上,N和D可以表示空间中的任何平面, 无论是对于2D还是3D(取决于变量N的维数), 数学上对于两者都是一样的. 和以前差不多, 但D是原点沿N方向移动到平面的距离. 例如, 想象一下您想在到达平面上的一个点, 您会这样做:

var point_in_plane = N*D
var pointInPlane = N * D;

这将拉伸(调整大小)法线向量并使其接触平面. 这个数学可能看起来很疑惑, 但实际上比看起来简单得多. 如果我们想再说一遍, 从点到平面的距离, 我们也会这样做, 但是要调整距离:

var distance = N.dot(point) - D
var distance = N.Dot(point) - D;

使用内置函数做同样的事情:

var distance = plane.distance_to(point)
var distance = plane.DistanceTo(point);

这将再次返回一个正或负的距离.

翻转平面的极性可以通过同时对N和D取负来完成. 这将导致平面处于相同的位置, 但是具有反转的负半空间和正半空间:

N = -N
D = -D
N = -N;
D = -D;

当然,Godot也在 Plane 中实现这个操作, 像这样:

var inverted_plane = -plane
var invertedPlane = -plane;

这将按预期工作.

所以, 记住, 平面就是这样, 它的主要用途就是计算到它的距离. 那么, 为什么计算一个点到一个平面的距离是有用的呢?非常有用!让我们来看一些简单示例.

在二维空间中构造平面

平面显然不是从哪儿冒出来的, 所以必须构造. 在2D中构造它们很简单, 这可以从法线(单位向量)和点, 或者用2维空间中的两个点来完成.

针对法线和点的情况, 大部分工作已经完成, 因为当法线已经计算出来时, 只需从法线和点的点乘得到D.

var N = normal
var D = normal.dot(point)
var N = normal;
var D = normal.Dot(point);

对于空间中的两个点, 实际上会有两个平面同时经过它们, 它们共享相同的空间, 但是法线方向相反. 为了从这两个点计算面的法线, 必须首先获得方向向量, 然后将向任何一边旋转90°:

# Calculate vector from `a` to `b`.
var dvec = (point_b - point_a).normalized()
# Rotate 90 degrees.
var normal = Vector2(dvec.y, -dvec.x)
# Alternatively (depending the desired side of the normal):
# var normal = Vector2(-dvec.y, dvec.x)
// Calculate vector from `a` to `b`.
var dvec = (pointB - pointA).Normalized();
// Rotate 90 degrees.
var normal = new Vector2(dvec.y, -dvec.x);
// Alternatively (depending the desired side of the normal):
// var normal = new Vector2(-dvec.y, dvec.x);

其余的与前面的示例相同,point_a或point_b都可以工作, 因为它们在相同的平面中:

var N = normal
var D = normal.dot(point_a)
# this works the same
# var D = normal.dot(point_b)
var N = normal;
var D = normal.Dot(pointA);
// this works the same
// var D = normal.Dot(pointB);

在3D中做同样的操作稍微复杂一些, 下面将进一步解释.

平面的一些示例

这里有一个简单的示例, 说明平面的用途. 假设您有一个 多边形. 例如, 矩形, 梯形, 三角形或任何没有向内弯曲的多边形.

对多边形的每个部分, 我们计算出经过该部分的平面. 一旦我们有了平面的列表, 我们就可以做些分类的事情, 例如检查一个点是否在多边形内部.

我们遍历所有平面, 如果我们能找到使得点到平面的距离为正的平面, 那么点在多边形之外. 如果我们不能, 那么这一点就在多边形内部.

../../_images/tutovec13.png

代码应该是这样的:

var inside = true
for p in planes:
    # check if distance to plane is positive
    if (p.distance_to(point) > 0):
        inside = false
        break # with one that fails, it's enough
var inside = true;
foreach (var p in planes)
{
    // check if distance to plane is positive
    if (p.DistanceTo(point) > 0)
    {
        inside = false;
        break; // with one that fails, it's enough
    }
}

很酷, 是吧?但这可以变得更好!稍加努力, 类似的逻辑将让我们知道两个凸多边形是否重叠. 这叫做分离轴定理(或SAT), 大多数物理引擎都用这个来检测碰撞.

对于一个点, 仅仅检查一个平面是否返回正距离就足以判断该点是否在外面. 对于一个多边形, 我们必须找到一个平面, 使得另一个多边形上的所有点到它的距离为正. 这种可以用A平面对B点进行检查, 然后用B平面对A点进行检查:

../../_images/tutovec14.png

代码应该是这样的:

var overlapping = true

for p in planes_of_A:
    var all_out = true
    for v in points_of_B:
        if (p.distance_to(v) < 0):
            all_out = false
            break

    if (all_out):
        # a separating plane was found
        # do not continue testing
        overlapping = false
        break

if (overlapping):
    # only do this check if no separating plane
    # was found in planes of A
    for p in planes_of_B:
        var all_out = true
        for v in points_of_A:
            if (p.distance_to(v) < 0):
                all_out = false
                break

        if (all_out):
            overlapping = false
            break

if (overlapping):
    print("Polygons Collided!")
var overlapping = true;

foreach (Plane plane in planesOfA)
{
    var allOut = true;
    foreach (Vector3 point in pointsOfB)
    {
        if (plane.DistanceTo(point) < 0)
        {
            allOut = false;
            break;
        }
    }

    if (allOut)
    {
        // a separating plane was found
        // do not continue testing
        overlapping = false;
        break;
    }
}

if (overlapping)
{
    // only do this check if no separating plane
    // was found in planes of A
    foreach (Plane plane in planesOfB)
    {
        var allOut = true;
        foreach (Vector3 point in pointsOfA)
        {
            if (plane.DistanceTo(point) < 0)
            {
                allOut = false;
                break;
            }
        }

        if (allOut)
        {
            overlapping = false;
            break;
        }
    }
}

if (overlapping)
{
    GD.Print("Polygons Collided!");
}

正如您所看到的, 平面是非常有用的, 然而这只是冰山一角. 您可能想知道非凸多边形会发生什么. 这通常只是通过将凹多边形分割成较小的凸多边形来处理, 或者使用诸如BSP(现在使用得不多)之类的技术.

三维碰撞检测

这是另一个奖励, 是对耐心并跟上这个漫长的教程的奖励. 这是另一条锦囊妙计. 这可能不能直接拿来使用(Godot已经可以进行了相当棒的碰撞检测了), 但是几乎所有的物理引擎和碰撞检测库都使用它的原理:)

还记得把2D中的凸形转换成2D平面阵列对碰撞检测有用吗?您可以检测一个点是否在任何凸形状内, 或者两个2D凸形状是否重叠.

嗯, 这在3D中也适用, 如果两个3D多面体形状碰撞, 您将无法找到分离平面. 如果发现一个分离平面, 那么形状肯定不会发生碰撞.

要得到分离平面意味着多边形A的所有顶点都在平面的一侧, 而多边形B的所有顶点都在另一侧. 该平面始终是多边形A或多边形B的面向平面之一.

然而在3D中, 这种方法存在一个问题, 因为在某些情况下可能找不到分离平面. 下面就是这种情况的一个示例:

../../_images/tutovec22.png

为了避免这种情况, 一些额外的平面需要作为分隔器被测试, 这些平面是多边形A的边和多边形B的边的叉乘

../../_images/tutovec23.png

所以最后的算法是这样的:

var overlapping = true

for p in planes_of_A:
    var all_out = true
    for v in points_of_B:
        if (p.distance_to(v) < 0):
            all_out = false
            break

    if (all_out):
        # a separating plane was found
        # do not continue testing
        overlapping = false
        break

if (overlapping):
    # only do this check if no separating plane
    # was found in planes of A
    for p in planes_of_B:
        var all_out = true
        for v in points_of_A:
            if (p.distance_to(v) < 0):
                all_out = false
                break

        if (all_out):
            overlapping = false
            break

if (overlapping):
    for ea in edges_of_A:
        for eb in edges_of_B:
            var n = ea.cross(eb)
            if (n.length() == 0):
                continue

            var max_A = -1e20 # tiny number
            var min_A = 1e20 # huge number

            # we are using the dot product directly
            # so we can map a maximum and minimum range
            # for each polygon, then check if they
            # overlap.

            for v in points_of_A:
                var d = n.dot(v)
                max_A = max(max_A, d)
                min_A = min(min_A, d)

            var max_B = -1e20 # tiny number
            var min_B = 1e20 # huge number

            for v in points_of_B:
                var d = n.dot(v)
                max_B = max(max_B, d)
                min_B = min(min_B, d)

            if (min_A > max_B or min_B > max_A):
                # not overlapping!
                overlapping = false
                break

        if (not overlapping):
            break

if (overlapping):
   print("Polygons collided!")
var overlapping = true;

foreach (Plane plane in planesOfA)
{
    var allOut = true;
    foreach (Vector3 point in pointsOfB)
    {
        if (plane.DistanceTo(point) < 0)
        {
            allOut = false;
            break;
        }
    }

    if (allOut)
    {
        // a separating plane was found
        // do not continue testing
        overlapping = false;
        break;
    }
}

if (overlapping)
{
    // only do this check if no separating plane
    // was found in planes of A
    foreach (Plane plane in planesOfB)
    {
        var allOut = true;
        foreach (Vector3 point in pointsOfA)
        {
            if (plane.DistanceTo(point) < 0)
            {
                allOut = false;
                break;
            }
        }

        if (allOut)
        {
            overlapping = false;
            break;
        }
    }
}

if (overlapping)
{
    foreach (Vector3 edgeA in edgesOfA)
    {
        foreach (Vector3 edgeB in edgesOfB)
        {
            var normal = edgeA.Cross(edgeB);
            if (normal.Length() == 0)
            {
                continue;
            }

            var maxA = float.MinValue; // tiny number
            var minA = float.MaxValue; // huge number

            // we are using the dot product directly
            // so we can map a maximum and minimum range
            // for each polygon, then check if they
            // overlap.

            foreach (Vector3 point in pointsOfA)
            {
                var distance = normal.Dot(point);
                maxA = Mathf.Max(maxA, distance);
                minA = Mathf.Min(minA, distance);
            }

            var maxB = float.MinValue; // tiny number
            var minB = float.MaxValue; // huge number

            foreach (Vector3 point in pointsOfB)
            {
                var distance = normal.Dot(point);
                maxB = Mathf.Max(maxB, distance);
                minB = Mathf.Min(minB, distance);
            }

            if (minA > maxB || minB > maxA)
            {
                // not overlapping!
                overlapping = false;
                break;
            }
        }

        if (!overlapping)
        {
            break;
        }

    }
}

if (overlapping)
{
    GD.Print("Polygons Collided!");
}

更多信息

关于在Godot中使用向量数学的更多信息, 请参见以下文章:

如果你需要进一步的解释, 你可以看看3Blue1Brown的绝佳的系列视频 "线性代数的本质": https://www.youtube.com/watch?v=fNk_zzaMoSs&list=PLZHQObOWTQDPD3MizzM2xVFitgF8hE_ab