Up to date

This page is up to date for Godot 4.2. If you still find outdated information, please open an issue.

Продвинутая векторная математика¶

Плоскости¶

Скалярное произведение имеет одно интересное свойство с единичными векторами. Вообразите что перпендикуляр к такому вектору(и через начальную точку) проходит через плоскость. Плоскости разделяют все пространство на положительное (над плоскостью) и отрицательное (под плоскостью), и (вопреки популярному мнению) вы сможете также использовать его в 2D:

Единичные вектора которые перпендикулярны плоскости (так, что они описывают ориентацию поверхности) называются единичными векторами нормали. Хотя, обычно это сокращают до нормалей. Нормали имеются в плоскостях, 3D геометрии (чтобы определять которая из сторон или вершин скользит), и т.д. Нормаль это единичный вектор, но называется нормалью поскольку имеет такое предназначение. (Так же как мы называем (0,0) Началом координат !).

The plane passes by the origin and the surface of it is perpendicular to the unit vector (or normal). The side towards the vector points to is the positive half-space, while the other side is the negative half-space. In 3D this is exactly the same, except that the plane is an infinite surface (imagine an infinite, flat sheet of paper that you can orient and is pinned to the origin) instead of a line.

Расстояние до самолета¶

Теперь, когда понятно, что такое плоскость, вернемся к скалярному произведению. Скалярное произведение между единичным вектором и любой точкой в пространстве (да, на этот раз мы делаем скалярное произведение между вектором и положением) возвращает расстояние от точки до плоскости:

var distance = normal.dot(point)

var distance = normal.Dot(point);

Но не только абсолютное расстояние: если точка находится в отрицательном полупространстве, расстояние тоже будет отрицательным:

Это позволяет нам определить, на какой стороне плоскости находится точка.

Вдали от источника¶

Я знаю, что вы думаете! Пока что это хорошо, но реальные плоскости есть повсюду в пространстве, а не только проходят через начало координат. Вы хотите настоящего плоскостного действия, и вы хотите этого сейчас.

Помните, что плоскости не только делят пространство на две части, но и обладают полярностью. Это означает, что можно иметь идеально перекрывающиеся плоскости, но их отрицательное и положительное полупространства поменяются местами.

Имея это в виду, давайте опишем полную плоскость как нормальную N и скаляр расстояния от начала координат D. Таким образом, наша плоскость обозначается буквами N и D. Например:

Для 3D-математики 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 also implements this operator in Plane. So, using the format below will work as expected:

var inverted_plane = -plane

var invertedPlane = -plane;

So, remember, the plane's main practical use is that we can calculate the distance to it. So, when is it useful to calculate the distance from a point to a plane? Let's see some examples.

Построение плоскости в 2D¶

Плоскости явно не появляются из ниоткуда, поэтому их надо строить. Построить их в 2D легко, это можно сделать либо по нормали (единичному вектору) и точке, либо по двум точкам в пространстве.

In the case of a normal and a point, most of the work is done, as the normal is already computed, so calculate D from the dot product of the normal and the point.

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_a.direction_to(point_b)
# 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 = pointA.DirectionTo(pointB);
// 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);

The rest is the same as the previous example. Either point_a or point_b will work, as they are in the same plane:

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);

Doing the same in 3D is a little more complex and is explained further down.

Несколько примеров плоскостей¶

Here is an example of what planes are useful for. Imagine you have a convex polygon. For example, a rectangle, a trapezoid, a triangle, or just any polygon where no faces bend inwards.

Для каждого сегмента многоугольника мы вычисляем плоскость, проходящую через этот сегмент. Получив список плоскостей, мы можем делать изящные вещи, например проверять, находится ли точка внутри многоугольника.

Проходим все плоскости, если удается найти плоскость, в которой расстояние до точки положительное, то точка находится вне многоугольника. Если не можем, то точка внутри.

Код должен быть примерно таким:

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 (Separating Axis Theorem)), и большинство физических движков используют ее для обнаружения столкновений.

В случае с точкой достаточно просто проверить, возвращает ли плоскость положительное расстояние, чтобы определить, находится ли точка снаружи. С другим многоугольником мы должны найти плоскость, в которой все другие полигоны точки возвращают положительное расстояние до него. Эта проверка выполняется с плоскостями А по точкам В, а затем с плоскостями В по точкам А:

Код должен быть примерно таким:

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 (который в настоящее время мало используется).

Обнаружение столкновений в 3D¶

Это еще один бонус, награда за терпение и понимание хода мысли этого длинного руководства. Вот еще одна мудрость. Возможно, это не что-то для прямого использования (Godot уже неплохо справляется с обнаружением столкновений), но оно используется почти всеми физическими движками и библиотеками обнаружения столкновений :)

Помните, преобразование выпуклой формы в 2D в массив 2D плоскостей было полезно для обнаружения столкновений? Вы могли определить, находится ли точка внутри какой-либо выпуклой формы или перекрываются две выпуклые двумерные формы.

Что ж, это работает и в 3D: если две трехмерные многогранные фигуры сталкиваются, вы не сможете найти разделяющую плоскость. Если разделяющая плоскость найдена, то фигуры точно не сталкиваются.

Немного обновить разделяющую плоскость означает, что все вершины многоугольника A находятся на одной стороне плоскости, а все вершины многоугольника B — на другой стороне. Эта плоскость всегда является одной из граней либо многоугольника A, либо многоугольника B.

In 3D though, there is a problem to this approach, because it is possible that, in some cases a separating plane can't be found. This is an example of such situation:

To avoid it, some extra planes need to be tested as separators, these planes are the cross product between the edges of polygon A and the edges of polygon B

So the final algorithm is something like:

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!");
}

Дополнительная информация¶

For more information on using vector math in Godot, see the following article:

Матрицы и преобразования

If you would like additional explanation, you should check out 3Blue1Brown's excellent video series "Essence of Linear Algebra": https://www.youtube.com/watch?v=fNk_zzaMoSs&list=PLZHQObOWTQDPD3MizzM2xVFitgF8hE_ab