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

Плоскости

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

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

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

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

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

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 также реализует этот оператор в Plane. Поэтому использование следующего формата будет работать так, как и ожидалось:

var inverted_plane = -plane

var invertedPlane = -plane;

Итак, помните, главное практическое применение плоскости заключается в том, что мы можем рассчитать расстояние до неё. Итак, когда же полезно вычислять расстояние от точки до плоскости? Давайте рассмотрим несколько примеров.

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

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

В случае нормали и точки большая часть работы выполнена, поскольку нормаль уже вычислена, поэтому вычисляем 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_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);

Остальное как в предыдущем примере. Подойдут как 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 немного сложнее и будет объяснено ниже.

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

Вот пример того, для чего полезны плоскости. Представьте, что у вас есть выпуклый многоугольник. Например, прямоугольник, трапеция, треугольник или любой многоугольник, у которого ни одна из граней не загнута внутрь.

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

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

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

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.

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

Чтобы избежать этого, необходимо проверить некоторые дополнительные плоскости как разделители. Эти плоскости являются векторным произведением между ребрами полигона A и ребрами полигона B

Итак, окончательный алгоритм выглядит примерно так:

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 можно найти в следующей статье:

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

If you would like additional explanation, you should check out 3Blue1Brown's excellent video series Essence of Linear Algebra.