Това е част II от нашата поредица от три части по физика на видеоигрите. За останалата част от тази серия вижте:

Част I: Въведение в динамиката на твърдо тяло
Част III: Симулация на ограничено твърдо тяло

---

В част I от тази поредица изследвахме твърди тела и техните движения. В тази дискусия обаче обектите не са взаимодействали помежду си. Без допълнителна работа, симулираните твърди тела могат да преминават един през друг или да се „проникват“, което е нежелателно в повечето случаи.

За да симулираме по-реалистично поведението на твърди обекти, трябва да проверяваме дали те се сблъскват помежду си всеки път, когато се движат, и ако го правят, трябва да направим нещо по въпроса, като например прилагане на сили, които променят скоростите им, така че че ще се движат в обратната посока. Тук е особено важно разбирането на физиката на сблъсъците разработчици на игри .

В част II ще разгледаме стъпката за откриване на сблъсък, която се състои от намиране на двойки тела, които се сблъскват между евентуално голям брой тела, разпръснати около 2D или 3D свят. В следващата и последна вноска ще говорим повече за „решаването“ на тези сблъсъци, за да се елиминират взаимните прониквания.

За преглед на концепциите за линейна алгебра, посочени в тази статия, можете да се обърнете към линеен алгебра краш курс в част I .

Физика на сблъсъка във видеоигрите

В контекста на симулациите на твърдо тяло сблъсък се случва, когато формите на две твърди тела се пресичат или когато разстоянието между тези форми падне под малък толеранс.

Ако имаме н тела в нашата симулация, изчислителната сложност на откриване на сблъсъци с двойни тестове е ИЛИ ( н 2), номер, който кара компютърните учени да се свиват. Броят на двойните тестове нараства квадратично с броя на телата и определянето дали две форми в произволни позиции и ориентации се сблъскват вече не е евтино. За да оптимизираме процеса на откриване на сблъсък, ние обикновено го разделяме на две фази: широка фаза и тясна фаза .

Широката фаза е отговорна за намирането на двойки твърди тела, които са потенциално сблъскване и изключване на двойки, които със сигурност не се сблъскват, измежду целия набор от тела, които са в симулацията. Тази стъпка трябва да може да се мащабира наистина добре с броя на твърдите тела, за да сме сигурни, че ще останем добре под ИЛИ ( н 2)сложност във времето. За да се постигне това, тази фаза обикновено използва разделяне на пространството свързан с ограничаващи обеми които установяват горна граница за сблъсък.

Тесната фаза действа върху двойките твърди тела, открити от широката фаза, които може да се сблъскат. Това е стъпка за усъвършенстване, при която определяме дали сблъсъците действително се случват и за всеки намерен сблъсък изчисляваме точките за контакт, които ще бъдат използвани за разрешаване на сблъсъците по-късно.

В следващите раздели ще говорим за някои алгоритми, които могат да се използват в широка и тясна фаза.

Широка фаза

В широката фаза на физиката на сблъсъка за видеоигри трябва да идентифицираме кои двойки твърди тела биха могли, може да се сблъскват. Тези тела могат да имат сложни форми като многоъгълници и многогранници и това, което можем да направим, за да ускорим това, е да използваме по-проста форма, за да обхванем обекта. Ако тези ограничаващи обеми не се пресичат, тогава действителните форми също не се пресичат. Ако те се пресичат, тогава действителните форми биха могли, може пресичат.

Някои популярни типове ограничителни обеми са ориентирани ограничителни кутии (OBB), кръгове в 2D и сфери в 3D. Нека разгледаме един от най-простите ограничителни обеми: подравнени по оста ограничителни кутии (AABB) .

AABB получават много любов от програмистите по физика, защото са прости и предлагат добри компромиси. Двумерна AABB може да бъде представена от структура като тази на езика C:

typedef struct { float x; float y; } Vector2; typedef struct { Vector2 min; Vector2 max; } AABB;

min полето представлява местоположението на долния ляв ъгъл на полето и max полето представлява горния десен ъгъл.

За да проверим дали две AABB се пресичат, трябва само да разберем дали техните проекции се пресичат по всички координатни оси:

BOOL TestAABBOverlap(AABB* a, AABB* b) d2y > 0.0f) return FALSE; return TRUE;

Този код има същата логика на b2TestOverlap функция от Box2D двигател (версия 2.3.0). Той изчислява разликата между min и max и на двете AABB, и в двете оси, и в двата реда. Ако някоя от тези стойности е по-голяма от нула, AABB не се пресичат.

Шаблон на документ за дизайн на високо ниво

Въпреки че тестът за припокриване AABB е евтин, това няма да помогне много, ако все пак правим двойни тестове за всяка възможна двойка, тъй като все още имаме нежеланото ИЛИ ( н 2)сложност във времето. За да сведем до минимум броя на тестовете за припокриване на AABB, можем да използваме някакъв вид разделяне на пространството , който работи на същите принципи като индекси на база данни които ускоряват заявките. (Географски бази данни, като например PostGIS , всъщност използват подобни структури от данни и алгоритми за техните пространствени индекси.) В този случай обаче AABB ще се движат постоянно, така че като цяло трябва да пресъздаваме индекси след всяка стъпка от симулацията.

Има много алгоритми за разделяне на пространство и структури от данни, които могат да се използват за това, като еднакви решетки , четворки в 2D, octrees в 3D и пространствено хеширане . Нека разгледаме по-отблизо два популярни алгоритма за пространствено разделяне: сортиране и почистване и ограничаващи йерархии на обема (BVH).

Алгоритъмът за сортиране и почистване

The сортирайте и пометете метод (алтернативно известен като почистване и подрязване ) е един от любимите избори сред програмистите по физика за използване при симулация на твърдо тяло. The Физика на куршума двигателят, например, има изпълнение на този метод в btAxisSweep3 клас.

Проекцията на един AABB върху единична координатна ос е по същество интервал[ б , е ](т.е. начало и край). В нашата симулация ще имаме много твърди тела и по този начин много AABB, а това означава много интервали. Искаме да разберем кои интервали се пресичат.

В алгоритъма за сортиране и почистване вмъкваме всички б и е стойности в един списък и го сортирайте възходящо по скаларните им стойности. Тогава ние метене или прекоси списъка. Когато а б стойност се среща, съответстващият й интервал се съхранява в отделен списък с активни интервали , и винаги когато е стойност се среща, съответстващият й интервал се премахва от списъка с активни интервали. Във всеки момент всички активни интервали се пресичат. (Разгледайте Дисертация на Дейвид Бараф , стр. 52 за подробности. Предлагам да използвате този онлайн инструмент за да видите файла с послепис.) Списъкът с интервали може да се използва повторно на всяка стъпка от симулацията, където можем ефективно да пресортираме този списък, като използваме вмъкване сортиране , което е добре при сортирането на почти сортирани списъци.

В две и три измерения, стартирането на сортирането и почистването, както е описано по-горе, върху една координатна ос ще намали броя на директните тестове за пресичане на AABB, които трябва да бъдат извършени, но печалбата може да е по-добра за една координатна ос от друга. Следователно се прилагат по-сложни варианти на алгоритъма за сортиране и почистване. В неговата книга Откриване на сблъсък в реално време (стр. 336), Кристър Ериксън представя ефективна вариация, при която съхранява всички AABB в един масив и за всяко изпълнение на сортирането и почистването се избира една координатна ос и масивът се сортира по min стойност на AABBs в избраната ос, използвайки бърз сорт . След това масивът се обхожда и се извършват тестове за припокриване AABB. За да определите следващата ос, която трябва да се използва за сортиране, отклонение на центъра на AABBs се изчислява и оста с по-голяма дисперсия се избира за следващата стъпка.

Динамични обемни дървета

Друг полезен метод за пространствено разделяне е динамично ограничаващо дърво на обема , също известен като Dbvt . Това е вид йерархия на ограничаващ обем .

Dbvt е двоично дърво, в което всеки възел има AABB, който ограничава всички AABB на своите деца. AABB на самите твърди тела са разположени в листните възли. Обикновено Dbvt се „заявява“, като се дава AABB, за който бихме искали да открием кръстовища. Тази операция е ефективна, тъй като децата на възли, които не пресичат заявения AABB, не трябва да бъдат тествани за припокриване. Като такава, AABB заявка за сблъсък започва от корена и продължава рекурсивно през дървото само за AABB възли, които се пресичат с заявената AABB. Дървото може да бъде балансирано чрез ротации на дървета , както в AVL дърво .

Box2D има сложна реализация на Dbvt в b2DynamicTree клас . The b2BroadPhase клас отговаря за изпълнението на широката фаза и използва екземпляр от b2DynamicTree за изпълнение на AABB заявки.

Тясна фаза

След широката фаза на физиката на сблъсъка на видеоигрите имаме набор от двойки твърди тела, които са потенциално сблъскване. По този начин за всяка двойка, като се имат предвид формата, разположението и ориентацията на двете тела, трябва да разберем дали те всъщност се сблъскват; ако се пресичат или ако разстоянието им попада под малка стойност на толеранс. Също така трябва да знаем кои точки на контакт са между сблъскващите се тела, тъй като това е необходимо за разрешаване на сблъсъците по-късно.

Изпъкнали и вдлъбнати форми

Като общо правило във физиката на видеоигрите не е тривиално да се определи дали две произволни фигури се пресичат или да се изчисли разстоянието между тях. Обаче едно свойство, което е от решаващо значение за определяне колко е трудно, е изпъкналост на формата. Формите могат да бъдат и двете изпъкнал или вдлъбнат и с вдлъбнати форми е по-трудно да се работи, така че имаме нужда от някои стратегии за справяне с тях.

При изпъкнала форма отсечка от линията между всякакви две точки във формата винаги попада изцяло във формата. Въпреки това за вдлъбната (или „неизпъкнала“) форма, същото не е вярно за всички възможни сегменти на линии, свързващи точки във формата. Ако можете изобщо да намерите поне един сегмент от линия, който попада извън формата, тогава формата е вдлъбната.

Изчислително е желателно всички форми да са изпъкнали в симулация, тъй като имаме много мощни алгоритми за тестване на разстояние и пресичане, които работят с изпъкнали форми. Не всички обекти обаче ще бъдат изпъкнали и обикновено ги заобикаляме по два начина: изпъкнал корпус и изпъкнало разлагане.

The изпъкнал корпус на форма е най-малката изпъкнала форма, която я съдържа напълно. За вдлъбнат многоъгълник в две измерения би било като да забиете пирон по всеки връх и да увиете гумена лента около всички нокти. За да се изчисли изпъкналият корпус за многоъгълник или многоъгълник или по-общо за набор от точки, добър алгоритъм за използване е бърз корпус алгоритъм, който има средна времева сложност от ИЛИ ( н дневник н ).

Очевидно, ако използваме изпъкнал корпус, за да представим вдлъбнат обект, той ще загуби своите вдлъбнати свойства. Нежеланото поведение, като сблъсъци „призрак“ може да стане очевидно, тъй като обектът все още ще има вдлъбната графична представа. Например, колата обикновено има вдлъбната форма и ако използваме изпъкнал корпус, за да я представим физически и след това поставим кутия върху нея, кутията може да изглежда като плаваща в горното пространство.

Като цяло изпъкналите корпуси често са достатъчно добри, за да представят вдлъбнати обекти, или защото нереалните сблъсъци не са много забележими, или техните вдлъбнати свойства не са от съществено значение за каквото и да е симулирано. В някои случаи обаче може да искаме вдлъбнатият обект да се държи физически като вдлъбната форма. Например, ако използваме изпъкнал корпус за физическо представяне на купа, няма да можем да поставим нищо вътре в нея. Обектите просто ще се носят върху него. В този случай можем да използваме a изпъкнало разлагане на вдлъбнатата форма.

Изпъкналите алгоритми за разлагане получават вдлъбната форма и връщат набор от изпъкнали форми, чието обединение е идентично с оригиналната вдлъбната форма. Някои вдлъбнати форми могат да бъдат представени само от голям брой изпъкнали форми и те могат да станат прекалено скъпи за изчисляване и използване. Приближаването обаче често е достатъчно добро и така алгоритми като V-HACD произведете малък набор от изпъкнали многогранници от вдлъбнат многоъгълник.

В много случаи на физика на сблъсъци обаче изпъкналото разлагане може да се извърши ръчно, от художник. Това елиминира необходимостта от данъчно представяне с алгоритми за декомпозиция. Тъй като производителността е един от най-важните аспекти в симулациите в реално време, обикновено е добра идея да създадете много прости физически изображения за сложни графични обекти. Изображението по-долу показва едно възможно изпъкнало разлагане на 2D кола, използващо девет изпъкнали форми.

Тестване за пресичания - Теорема за разделящата ос

The теорема за разделителната ос (SAT) заявява, че две изпъкнали фигури не се пресичат тогава и само ако съществува поне една ос, където ортогоналните проекции на фигурите по тази ос не се пресичат.

Обикновено е по-визуално интуитивно да се намери линия в 2D или равнина в 3D, която разделя двете фигури, което на практика е един и същ принцип. Като „разделителна ос“ може да се използва вектор, ортогонален на линията в 2D, или нормалният вектор на равнината в 3D.

Двигателите на физиката на играта имат редица различни класове форми, като кръгове (сфери в 3D), ръбове (сегмент от една линия) и изпъкнали полигони (полиедри в 3D). За всяка двойка тип фигура те имат специфичен алгоритъм за откриване на сблъсък. Най-простият от тях вероятно е алгоритъмът кръг-кръг:

typedef struct { float centerX; float centerY; float radius; } Circle; bool CollideCircles(Circle *cA, Circle *cB) { float x = cA->centerX - cB->centerX; float y = cA->centerY - cB->centerY; float centerDistanceSq = x * x + y * y; // squared distance float radius = cA->radius + cB->radius; float radiusSq = radius * radius; return centerDistanceSq <= radiusSq; }

Въпреки че SAT се прилага за кръгове, много по-просто е просто да проверите дали разстоянието между техните центрове е по-малко от сумата от техните радиуси. Поради тази причина SAT се използва в алгоритъма за откриване на сблъсъци за специфични двойки класове форми, като изпъкнал полигон срещу изпъкнал полигон (или многогранници в 3D).

За всяка двойка фигури има безкраен брой оси, които можем да тестваме за разделяне. По този начин определянето на коя ос да се тества първо е от решаващо значение за ефективното внедряване на SAT. За щастие, когато тестваме дали двойка изпъкнали полигони се сблъскат, можем да използваме нормалите на ръбовете като потенциални разделителни оси. Нормалният вектор н на ръба е перпендикулярна на вектора на ръба и сочи извън многоъгълника. За всеки ръб на всеки многоъгълник просто трябва да разберем дали всички върхове на другия многоъгълник са пред на ръба.

Ако някой тест премине - тоест, ако за който и да е ръб всички върхове на другия многоъгълник са пред от него - тогава полигоните не се пресичат. Линейната алгебра предоставя лесна формула за този тест: даден е ръб на първата фигура с върхове да се и б и връх v от другата форма, ако( v - да се ) н е по-голямо от нула, тогава върхът е пред ръба.

За многогранниците можем да използваме нормалите на лицето, а също и кръстосаното произведение на всички комбинации от ръбове от всяка форма. Това звучи като много неща за тестване; обаче, за да ускорим нещата, можем да кешираме последната разделителна ос, която използвахме, и да опитаме да я използваме отново в следващите стъпки от симулацията. Ако кешираната разделителна ос вече не разделя фигурите, можем да търсим нова ос, започвайки от лица или ръбове, които са в съседство с предишното лице или ръб. Това работи, защото телата често не се движат или въртят много между стъпките.

Box2D използва SAT, за да тества дали два изпъкнали полигона се пресичат в неговия алгоритъм за откриване на сблъсък полигон-полигон в b2CollidePolygon.cpp .

Изчислително разстояние - Алгоритъмът на Гилбърт-Джонсън-Кирти

В много случаи на физика на сблъсъци искаме да разгледаме обектите, които се сблъскват, не само ако действително се пресичат, но и ако са много близо един до друг, което изисква да знаем разстоянието между тях. The Гилбърт-Джонсън-Кеерти (GJK) алгоритъм изчислява разстоянието между две изпъкнали форми, както и техните най-близки точки. Това е елегантен алгоритъм, който работи с неявно представяне на изпъкнали форми чрез поддържащи функции, суми на Минковски и симплекси, както е обяснено по-долу.

Функции за поддръжка

ДА СЕ поддържаща функция с ДА СЕ( д )връща точка на границата на фигуратаДА СЕкойто има най-високата проекция върху вектора д . Математически, той има продукт с най-много точки с д . Това се нарича a опорна точка , и тази операция е известна още като подкрепа за картографиране . Геометрично тази точка е най-отдалечената точка на фигурата в посока д .

Намирането на опорна точка на многоъгълник е относително лесно. За опорна точка за вектор д , просто трябва да преминете през върховете му и да намерите този, който има продукт с най-много точки д , като този:

Vector2 GetSupport(Vector2 *vertices, int count, Vector2 d) { float highest = -FLT_MAX; Vector2 support = (Vector2){0, 0}; for (int i = 0; i highest) { highest = dot; support = v; } } return support; }

Истинската сила на поддържащата функция обаче е, че улеснява работата с форми като конуси, цилиндри и елипси, наред с други. Доста е трудно да се изчисли разстоянието между такива фигури директно и без алгоритъм като GJK обикновено ще трябва да ги дискретизирате в многоъгълник или многоъгълник, за да направите нещата по-прости. Това обаче може да доведе до допълнителни проблеми, тъй като повърхността на многогранник не е толкова гладка, колкото повърхността на, да речем, сфера, освен ако полиедърът е много подробен, което може да доведе до лоша производителност по време на откриване на сблъсък. Могат да се проявят и други нежелани странични ефекти; например „многогранна“ сфера може да не се търкаля гладко.

За да получим опорна точка за сфера, центрирана върху началото, трябва просто да се нормализира д (т.е. изчисли д / || д ||, който е вектор с дължина 1 (единична дължина), който все още сочи в същата посока на д ) и след това го умножаваме по радиуса на сферата.

Проверете Документът на Джино ван ден Берген за да намерите повече примери за поддържащи функции за цилиндри и конуси, наред с други форми.

Нашите обекти, разбира се, ще бъдат изместени и завъртени от началото в пространството за симулация, така че трябва да можем да изчислим опорни точки за трансформирана форма. Използваме афинна трансформация т ( х ) = R х + ° С за да изместим и завъртим нашите обекти, където ° С е вектор на изместване и R е матрица на въртене . Тази трансформация първо завърта обекта около произхода и след това го превежда. Поддържащата функция за трансформирана формаДА СЕе:

Минковски Суми

The Сума на Минковски от две формиДА СЕиБ.се определя като:

Това означава, че изчисляваме сумата за всички точки, съдържащи се вДА СЕиБ.. Резултатът е като надуване ДА СЕсБ..

По същия начин дефинираме Разлика на Минковски като:

което можем да запишем и като сумата на МинковскиДА СЕс-Б:

трябва ли да научите C или C++

За изпъкналДА СЕиБ.,A⊕Bсъщо е изпъкнала.

Едно полезно свойство на разликата на Минковски е, че ако тя съдържа произхода на пространството, формите се пресичат, както се вижда на предишното изображение. Защо така? Защото, ако две фигури се пресичат, те имат поне една обща точка, която лежи на едно и също място в пространството, а тяхната разлика е нулевият вектор, който всъщност е началото.

Друга хубава характеристика на разликата на Минковски е, че ако тя не съдържа началото, минималното разстояние между началото и разликата на Минковски е разстоянието между фигурите.

Разстоянието между две фигури се определя като:

С други думи, разстоянието междуДА СЕиБ.е дължината на най-краткия вектор, който тръгва отДА СЕда сеБ.. Този вектор се съдържа вA⊖Bи това е с най-малка дължина, което следователно е най-близкото до произхода.

Обикновено не е лесно изрично да се изгради сумата на Минковски от две фигури. За щастие и тук можем да използваме картографиране на поддръжка, тъй като:

Симплекси

Алгоритъмът GJK търси итеративно точката на разликата на Минковски най-близо до началото. Прави това, като изгражда поредица от симплекси които са по-близо до произхода във всяка итерация. Симплекс - или по-точно, a k-симплекс за цяло числода се- е изпъкналият корпус наk + 1 афинно независим точки в k-мерно пространство. Тоест, ако за две точки те не трябва да съвпадат, за три точки допълнително не трябва да лежат на една и съща права, а ако имаме четири точки, те също не трябва да лежат на една и съща равнина. Следователно 0-симплексът е точка, 1-симплексът е отсечка от права, 2-симплексът е триъгълник, а 3-симплексът е тетраедър. Ако премахнем точка от симплекс, ние намаляваме нейната размерност с единица и ако добавим точка към симплекс, увеличаваме нейната размерност с единица.

GJK в действие

Нека да съберем всичко това, за да видим как работи GJK. За определяне на разстоянието между две фигуриДА СЕиБ., започваме като вземаме тяхната разлика на МинковскиA⊖B. Търсим най-близката точка до началото на получената фигура, тъй като разстоянието до тази точка е разстоянието между оригиналните две фигури. Ние избираме някаква точка v вA⊖B, което ще бъде приблизителното ни разстояние. Определяме и празен набор от точкиIN, който ще съдържа точките в текущия тестов симплекс.

След това влизаме в цикъл. Започваме с получаване на точката за подкрепа в = sA⊖B(- v ), точката наA⊖Bчиято проекция върху v е най-близо до произхода.

Ако|| в ||не е много по-различно от|| v ||и ъгълът между тях не се е променил много (според някои предварително дефинирани допустими отклонения), това означава, че алгоритъмът се е сближил и можем да се върнем|| v ||като разстоянието.

В противен случай добавяме в да сеIN. Ако изпъкналият корпус наIN(т.е. симплексът) съдържа началото, формите се пресичат и това също означава, че сме готови. В противен случай намираме точката в симплекса, която е най-близо до началото и след това нулираме v да бъде това ново най-близко приближение. Накрая премахваме всички точки вINкоито не допринасят за изчисляването на най-близката точка. (Например, ако имаме триъгълник и най-близката точка до началото се намира в един от ръбовете му, можем да премахнем точката отINтова не е връх на този ръб.) След това повтаряме същите тези стъпки, докато алгоритъмът се сближи.

Следващото изображение показва пример за четири повторения на алгоритъма GJK. Синият обект представлява разликата на МинковскиA⊖Bа зеленият вектор е v . Тук можете да видите как v усъвършенства в най-близката точка до произхода.

За подробно и задълбочено обяснение на алгоритъма GJK вижте статията Бърза и здрава реализация на GJK за откриване на сблъсък на изпъкнали обекти , от Джино ван ден Берген. Блогът за dyn4j двигателят по физика също има страхотен пост на GJK .

Box2D има реализация на алгоритъма GJK в b2Distance.cpp , в b2Distance функция. Той използва само GJK по време на изчисление на удара в своя алгоритъм за непрекъснато откриване на сблъсък (тема, която ще обсъдим по-долу).

Физическият механизъм на Chimpunk използва GJK за всички откривания на сблъсъци и внедряването му е в cpCollision.c , в GJK функция. Ако алгоритъмът GJK отчита пресичане, той все още трябва да знае кои са точките на контакт, заедно с дълбочината на проникване. За целта използва разширяващия се политопен алгоритъм, който ще проучим по-нататък.

Определяне на дълбочината на проникване - разширяващият се политопен алгоритъм

Както беше посочено по-горе, ако формитеДА СЕиБ.се пресичат, GJK ще генерира симплексINкойто съдържа произхода, вътре в разликата на МинковскиA⊖B. На този етап знаем само, че формите се пресичат, но при проектирането на много системи за откриване на сблъсъци е желателно да можем да изчислим колко пресичане имаме и какви точки можем да използваме като точки на контакт, така че ние се справяме с сблъсъка по реалистичен начин. The Разширяване на многоъгълния алгоритъм (EPA) ни позволява да получим тази информация, започвайки от мястото, където GJK е спряла: със симплекс, който съдържа произхода.

The дълбочина на проникване е дължината на минимален вектор за превод (MTV), което е най-малкият вектор, по който можем да преведем пресичаща се форма, за да я отделим от другата форма.

Когато две форми се пресичат, тяхната разлика на Минковски съдържа началото, а точката на границата на разликата на Минковски, която е най-близо до началото, е MTV. EPA алгоритъмът намира тази точка чрез разширяване на симплекса, който GJK ни даде в многоъгълник; последователно подразделяне на ръбовете му с нови върхове.

Първо, намираме ръба на най-близкия до началото на симплекса и изчисляваме опорната точка в разликата на Минковски в посока, която е нормална на ръба (т.е. перпендикулярна на него и сочеща извън полигона). След това разделяме този ръб, като добавяме към него тази опорна точка. Повтаряме тези стъпки, докато дължината и посоката на вектора не се променят много. След като алгоритъмът се сближи, имаме MTV и дълбочината на проникване.

Използвайки GJK в комбинация с EPA, получаваме подробно описание на сблъсъка, независимо дали обектите вече се пресичат или са достатъчно близо, за да се счита за сблъсък.

EPA алгоритъмът е описан в статията Заявки за близост и изчисляване на дълбочината на проникване върху 3D игрови обекти , също написана от Джино ван ден Берген. Блогът dyn4j също има пост за EPA .

Непрекъснато откриване на сблъсък

Представените до момента техники за физика на видеоигрите извършват откриване на сблъсъци за статична снимка на симулацията. Това се казва дискретно откриване на сблъсък и игнорира какво се случва между предишната и текущата стъпки. Поради тази причина някои сблъсъци може да не бъдат открити, особено за бързо движещи се обекти. Този проблем е известен като тунелиране .

Техниките за непрекъснато откриване на сблъсък се опитват да намерят кога две тела се сблъскаха между предишната и настоящата стъпка на симулацията. Те изчисляват време на удара , за да можем да се върнем назад във времето и да обработим сблъсъка в този момент.

Времето на удара (или времето на контакт) т ° С е моментът на времето, когато разстоянието между две тела е нула. Ако можем да напишем функция за разстоянието между две тела по време, това, което искаме да намерим, е най-малкото корен на тази функция. По този начин времето за изчисляване на въздействието е a проблем с намирането на корен .

За времето на изчисляване на въздействието ние разглеждаме състоянието (положението и ориентацията) на тялото в предишната стъпка във времето т i -един, и в текущата стъпка във времето т i . За да улесним нещата, приемаме линейно движение между стъпките.

Нека опростим проблема, като приемем, че фигурите са кръгове. За два кръга ° С едини ° С 2, с радиус r едини r 2, където техният център на маса х едини х 2съвпадат с техния центроид (т.е. естествено се въртят около центъра на масата), можем да запишем функцията за разстояние като:

Имайки предвид линейното движение между стъпките, можем да напишем следната функция за позицията на ° С единот т i -единда се т i

Това е линейна интерполация от х един( т i -един)да се х един( т i ). Същото може да се направи и за х 2. За този интервал можем да напишем друга функция за разстояние:

Задайте този израз равен на нула и получавате a квадратно уравнение На т . Корените могат да бъдат намерени директно с помощта на квадратна формула . Ако кръговете не се пресичат, квадратната формула няма да има решение. Ако го направят, това може да доведе до един или два корена. Ако има само един корен, тази стойност е времето на въздействие. Ако има два корена, най-малкият е времето на удара, а другият е времето, когато кръговете се разделят. Имайте предвид, че времето на удара тук е число от 0 до 1. Това не е време в секунди; това е просто число, което можем да използваме, за да интерполираме състоянието на телата до точното място, където се е случил сблъсъкът.

Непрекъснато откриване на сблъсък за не-кръгове

Записването на функция за разстояние за други видове фигури е трудно, най-вече защото разстоянието им зависи от ориентацията им. Поради тази причина обикновено използваме итеративни алгоритми, които придвижват обектите все по-близо и по-близо на всяка итерация, докато те не станат достатъчно близо да се счита за сблъскващи се.

The консервативен напредък алгоритъм премества телата напред (и ги върти) итеративно. Във всяка итерация той изчислява горна граница за изместване. Оригиналният алгоритъм е представен в Brian Mirtich’s PhD Thesis (раздел 2.3.2), който разглежда балистичното движение на телата. Тази хартия от Erwin Coumans (авторът на Bullet Physics Engine) представя по-опростена версия, която използва постоянни линейни и ъглови скорости.

Алгоритъмът изчислява най-близките точки между фигуритеДА СЕиБ., рисува вектор от една точка до друга и проектира скоростта върху този вектор, за да изчисли горната граница за движение. Той гарантира, че нито една точка на тялото няма да се премести извън тази проекция. След това тя напредва телата напред с тази сума и се повтаря, докато разстоянието падне под малка стойност на толеранс.

В някои случаи може да отнеме твърде много итерации, за да се сближат, например, когато ъгловата скорост на едно от телата е твърде висока.

Разрешаване на сблъсъци

След като бъде открит сблъсък, е необходимо да се променят движенията на сблъскващите се обекти по реалистичен начин, като например да се накарат те да се отскочат един от друг. В следващата и последна част от тези теории ще обсъдим някои популярни методи за разрешаване на сблъсъци във видеоигри.

Препратки

Ако се интересувате от по-задълбочено разбиране за физиката на сблъсъка, като алгоритми и техники за откриване на сблъсъци, книгата Откриване на сблъсък в реално време , от Кристър Ериксън, е задължително.

Тъй като откриването на сблъсъци разчита много на геометрията, статията на ApeeScape Изчислителна геометрия в Python: от теория към приложение е отлично въведение в темата.

Свързани: Уводен урок за програмиране на роботи