Attention: Here be dragons

This is the latest (unstable) version of this documentation, which may document features not available in or compatible with released stable versions of Godot.

Checking the stable version of the documentation...

Поглиблена векторна алгебра

Площини

Скалярний добуток має ще одну цікаву властивість з одиничними векторами. Уявіть, що перпендикуляр до цього вектора (і через початок координат) проходить площину. Площини ділять весь простір на додатні (над площиною) та від'ємні (під площиною), і (всупереч поширеній думці) ви також можете використовувати їх математику у 2D:

Одиничні вектори, перпендикулярні до поверхні (тобто вони описують орієнтацію поверхні), називаються векторами одиничної нормалі. Хоча зазвичай їх скорочено називають нормалями. Нормалі з'являються на площинах, у тривимірній геометрії (щоб визначити, де знаходиться кожна грань або вершина) тощо. Нормаль є одиничним вектором, але його називають нормаллю через його використання. (Так само, як ми називаємо (0,0) початком координат!).

Площина проходить повз початок координат, а її поверхня перпендикулярна до одиничного вектора (або нормалі). Сторона, на яку вказує вектор, є позитивним півпростором, тоді як інша сторона є негативним півпростором. У 3D це точно так само, за винятком того, що площина є нескінченною поверхнею (уявіть собі нескінченний плаский аркуш паперу, який можна орієнтувати та який закріплений у початку координат), а не лінію.

Відстань до площини

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

var distance = normal.dot(point)

var distance = normal.Dot(point);

При чому не просто відстанню. Якщо точка знаходиться в нижньому півпросторі, то відстань буде від'ємною:

Так ми можемо дізнатись, з якого боку площини знаходиться точка.

Подалі від центру

Я знаю, про що ти думаєш! Поки що це чудово, але справжні літаки є скрізь у космосі, не лише проходять через початок координат. Ти хочеш справжньої дії літака, і ти хочеш її зараз.

Пам'ятайте, що площини не лише розділяють простір надвоє, а й мають полярність. Може статись так, що дві площини ідеально збігаються одна з одною, але вони дивляться у протилежні боки, а їх верхні та нижні напівпростори поміняні місцями.

Враховуючи це, опишімо площину, через нормаль N та відстань до початку координат D, яка є числом. Таким чином площину можна описати як N і D. Наприклад:

Для тривимірної математики 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);

Решта так само, як у попередньому прикладі. Точка_a або точка_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
    }
}

Круто, а? Але все може бути навіть краще! Доклавши трохи більше зусиль ми можемо дізнатись чи перетинаються між собою два опуклих багатокутники. Спосіб зробити це називається „теорема про розділову гіперплощину“. Її використовують більшість інженерів та фізиків для визначення зіткнень об'єктів.

Для точки достатньо просто перевірити, чи площина повертає додатну відстань, щоб визначити, чи знаходиться точка зовні. Для іншого многокутника нам потрібно знайти площину, де всі той інші точки многокутника повертають додатну відстань до неї. Ця перевірка виконується з площинами A відносно точок B, а потім з площинами B відносно точок A:

У коді, це виглядає приблизно ось так:

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 ми розглядали їх як набір двовимірних площин(прямих)? Ви могли визначити чи точка була всередині опуклої фігури або чи дві двовимірні фігури перетинаються.

Цей підхід працює і в 3D. Якщо два 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, почитайте цю статтю:

Матриці та перетворення

Якщо вам потрібні додаткові пояснення, вам слід переглянути чудову серію відео 3Blue1Brown «Суть лінійної алгебри» <https://www.youtube.com/watch?v=fNk_zzaMoSs&list=PLZHQObOWTQDPD3MizzM2xVFitgF8hE_ab>`_.