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

Част I: Въведение в динамиката на твърдо тяло
Част II: Откриване на сблъсък за твърди обекти

---

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

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

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

Тази вноска ще включва по-тежка математика от Част I или Част II, така че бъдете предупредени. Ако трябва да се справите с изчисленията, отидете тук в Академия Хан . За преглед на основите на линейната алгебра можете да се обърнете към приложение в част I , а за по-сложната линейна алгебра, като умножение на матрици, Khan Academy отново доставя . Уикипедия също има страхотни статии за смятане и линейна алгебра .

Какви са ограниченията?

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

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

Пример: Ограничения за равенство

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

Нека разгледаме един прост пример. Да разгледаме частица в две измерения, с положение стр ( т ) = ( стрх ( т ), стрY. ( т )), което е функция от времето, която дава позицията на частицата в даден момент т . Ще използваме точкова нотация, за да изразим производни на времето, като по този начин, ṗ е първото производно на стр по отношение на времето, което е скоростта на частицата v ( т ), и p̈ е второто му производно или ускорението.

Нека дефинираме ограничение. Позволявам ° С да бъде следната функция на поведение:

Тази функция приема позицията на частицата като параметър и извежда разстоянието си от началния минус л . Тя ще бъде нула, когато разстоянието между частицата и началото е л . По този начин ефектът от това ограничение е да държи частицата на фиксирано разстояние л от произхода, като махало, прикрепено към произхода. Стойностите на стр които удовлетворяват ° С ( стр ) = 0са юридически позиции на частицата.

В този пример ° С е функция само на две променливи, която извежда скалар, така че можем лесно да го начертаем и да изследваме някои от неговите свойства. Ако зададем разстоянието на ограничението като 2 (т.е. л = 2), след това графиката на ° С изглежда така:

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

Показват се зелените стрелки градиенти на ° С , оценено около хиперповърхността и посочва указанията към нелегални позиции на нашата частица, където ° С ≠ 0. Ако частицата се движи по тези линии по някакъв начин, или в положителната посока (далеч от началото) или отрицателната посока (към началото), това ще наруши ограничението. По този начин силите, които генерираме за изтласкване на частицата в законни позиции, ще бъдат успоредни на тези линии.

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

Изчислителни сили за ограничаване

Би било хубаво просто да настроите стр такъв, че ° С винаги е точно нула. На практика това ще доведе до нереалистично поведение, тъй като частиците ни ще скачат и се трептят около хиперповърхността. Да запазя ° С възможно най-близо до нула, като същевременно се поддържа реалистично поведение, трябва да се използва интуитивен подход динамика, базирана на сила , и изчислете необходимата сила, която да приложите върху частицата, така че тя да задоволи ограниченията, без да нарушава законите на Нютон за движение.

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

Искаме да гарантираме, че стойността на ° С ще остане равна на нула и ще остане непроменена по време на симулацията. Това означава, че първата производна време, ° С. , също трябва да е нула.

По същия начин, за да ° С. да остане фиксирана на нула, втората производна, ° С , също трябва да е нула.

Не трябва да ограничаваме никакви допълнителни производни на ° С , тъй като втората производна е мястото, където ще бъдат приложени нашите сили на ограничение.

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

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

Предвид правно положение на стр , всички скорости ṗ които удовлетворяват ° С. ( стр ) = 0са законни скорости. В този пример това трябва да са само онези скорости, които са допирни до хиперповърхността в горното изображение.

Второто производно на ° С с уважение до т е:

Еквивалентно, при законово положение и скорост, всички ускорения p̈ които удовлетворяват ° С ( стр ) = 0са законови ускорения. В този пример това трябва да са само тези ускорения, които са директно към или далеч от началото.

Използвайки Втория закон за движение на Нютон, можем да изразим ускорението по отношение на сила. Можем да считаме, че върху частицата действат две сили: комбинация от всички външни сили е вътр , като гравитация, вятър и сили, приложени от потребителя, и силата на ограничението е ° С. Последният е този, който искаме да определим. Ако приемем, че частицата има маса м , ускорението му е:

Замествайки това в ° С = 0получаваме:

Които могат да бъдат пренаредени на:

Имаме едно уравнение и две неизвестни (двете координати на е ° С), поради което не може да бъде решен. Трябва да въведем едно допълнително условие.

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

Следователно:

Уравнението за първата производна на нашето ограничение казва това стр · ṗ = 0. От е ° С· ṗ = 0, имаме и двете е ° Си стр са ортогонални на ṗ , и така е ° Си стр са успоредни. По този начин можем да запишем едното като кратно на другото

Почти сме там! Скаларът λ представлява величина на ограничителната сила, която трябва да се приложи за да доведе системата до валидно състояние. Колкото повече се отдалечава системата ни от валидните състояния, толкова по-голяма λ ще бъде, за да го върне обратно в валидно състояние. В този момент λ е единственото ни неизвестно. Заменяйки горното в предишното ни уравнение, получаваме:

Сега можем да изчислим λ директно и получете е ° Скато го умножим с стр . Тогава ние просто кандидатстваме е ° Скъм частицата и оставете симулацията, описана в част I, да свърши останалото!

λ е известен също като a Множител на Лагранж . За всяко ограничение изчислението включва определяне на посоката на вектора на силата и е величина, λ .

Кога да приложите сили за ограничение

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

1. Изчислете всички външни сили е вътр .
2. Изчислете силите на ограничението е ° С.
3. Приложете всички сили и симулирайте движението, както е описано в част I.

Системи на ограничения

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

Настройвам

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

Държавен вектор

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

Кажете, че имаме н твърди тела, които симулираме. Позволявам Какво бъди a държавен вектор който има всички положения и ъгли на твърдите тела:

където стр i е двуизмерен вектор, представящ позицията на i -то твърдо тяло и а i е неговият ъгъл, който е скаларен. Поради това, Какво има3нелементи.

Динамика: Вторият закон на Нютон

Позволявам М да бъде следното3нот3ндиагонална матрица:

където м i е масата на i -то твърдо тяло и Аз i е моментът му на инерция.

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

и:

F има също 3н елементи, тъй като всеки е i е вектор с две измерения.

Сега можем да напишем Втория закон за движение на Нютон за целия набор от тела с един израз:

Ограничения

И накрая, нека настроим нашите поведенчески функции. Кажете, че има м ограничения, всеки от които представлява връзка във веригата от твърди тела. Ще групираме всичките си функции на поведение в една функция ° С ( Какво ):

° С ( Какво )отнема3н-измерен вектор Какво като вход и извежда an м -измерен вектор. Искаме да запазим този изход възможно най-близо до нулевия вектор, като използваме процес, подобен на този, който направихме по-горе.

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

Производни на ° С С течение на времето

Както и преди, ние също искаме производни за първи и втори път на ° С да са нулеви вектори. Нека развием тези уравнения.

Производната на ° С по отношение на времето може да се даде като:

един от начините, по които нападателите могат да получат некриптиран достъп

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

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

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

Сега можем да изразим производната на времето на ° С като:

Красив.

Второто производно на ° С ще бъде:

където:

Замествайки нашия израз на Втория закон на Нютон, имаме:

Изчисляване на вектора на силата на ограничението

Искаме втората производна на ° С да бъде нула, така че нека го настроим на нула и да пренаредим:

Това уравнение е аналогично на това, което разработихме преди за едно ограничение:

Отново броят на неизвестните е по-голям от броя на уравненията и отново можем да използваме факта, че силите на ограничението са ортогонални на скоростите, за да намерим решение:

Ние също искаме първата производна на ° С да е нула. От ° С. = 0имаме това:

и следователно можем да напишем вектора на силата на ограничението F ° С като кратно на J :

Векторът λ има м скаларни компоненти и в това умножение на матрица-вектор, всеки компонент λ i умножава ред от J (което е градиентът на i -та функция за ограничение) и ги сумира заедно. Това е

F ° С по този начин е a линейна комбинация от редовете на J , които са градиентите на функциите за ограничение. Въпреки че тази система е твърде сложна, за да може лесно да визуализира хиперповърхността, както направихме за примера с частици, тя се държи точно по същия начин като този пример: градиентите са ортогонални на хиперповърхностите на ограниченията и са посоките, в които системата не е позволено да се движи. Следователно, това е линейна комбинация от вектори, които сочат в забранените посоки, което означава, че силите на ограничението ще бъдат ограничени до тези посоки и те ще тласнат телата към валидните състояния, наложени от ограниченията.

Единственото нещо, което остава да се реши, е λ вектор, който ще определи величините на силите на ограничението. Нека се върнем към нашето основно уравнение и да заместим последния израз там:

Това е система от линейни уравнения където само λ не е известно. Има много добре известни методи за ефективно решаване на линейна система като тази. След като се реши и ние го имаме λ , можем да изчислим F ° С , приложете резултатите към твърдите тела и симулирайте полученото движение, както е показано в част I.

За подробно извеждане на тези уравнения разгледайте Andrew Witkin’s Ограничена динамика , част от Физическо моделиране: Принципи и практика курс в университета Карнеги Мелън.

Ограничения на неравенството

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

Както описахме в част II, след като сблъсъкът е открит от GJK алгоритъм , ще имаме точките за контакт на двете тела, както и повърхността, нормална в точката на контакт. Не забравяйте, че GJK е едновременно тест за сблъсък и тест за близост и че две тела могат да се считат за „сблъскващи се“, дори ако всъщност не се докосват, но разстоянието между тях е много малко. В този случай точките за контакт на двете тела се считат за точките, където те са най-близо един до друг.

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

Помислете за двойка двумерни тела ДА СЕ и Б. които се сблъскват. В момента на контакт, ДА СЕ има позиция стр ДА СЕ и ъгъл а ДА СЕ , и Б. има позиция стр Б. и ъгъл а Б. . Нека се обадим r ДА СЕ вектор, който отива от центъра на ДА СЕ до точката за контакт на ДА СЕ , и нека също дефинираме r Б. по същия начин. Позволявам н да бъде нормалният контакт, който сочи от ДА СЕ да се Б. .

Да вземем стандартна матрица за 2D въртене R ( θ )който върти вектори с даден ъгъл θ :

Можем да го използваме за завъртане на векторите r ДА СЕ и r Б. по ъглите а ДА СЕ и а Б. , съответно. Това ни позволява да дефинираме функция на поведение, ° С , като:

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

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

Тази промяна трансформира системата от линейни уравнения, която имаме, в нещо съвсем различно (и по-сложно), наречено a Проблем със смесена линейна комплементарност или MLCP. Има няколко приятни алгоритми, които могат да решат този проблем директно, като например Алгоритъм на Лемке . Ние обаче ще пропуснем подробностите тук и ще обсъдим друг подход към ограниченията, който е много популярен във физиката на игрите.

Импулсна динамика

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

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

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

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

1. Изчислете всички външни сили.
2. Приложете силите и определете получените скорости, като използвате техниките от Част I.
3. Изчислете скоростите на ограничението въз основа на поведенческите функции.
4. Приложете ограничителните скорости и симулирайте полученото движение.

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

На физически език, an импулс е интегралът на сила по отношение на времето. Това е:

Това е равно на промяна в импулс през това време.

Ако постоянна сила F се прилага за известно време з , тогава импулсът е просто:

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

Последователни импулси

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

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

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

2. Прилагайте последователно импулси за всички ограничения, за да коригирате грешките в скоростта. Повторете за няколко повторения, докато импулсите станат малки или след достигане на максимален брой повторения.

3. Използвайте новите скорости, за да симулирате движение, актуализиране на позиции, отново използвайки полуимплицитен Ойлер.

Обърнете внимание, че тези стъпки съответстват на стъпки от 2 до 4 от общата последователност от импулсни базирани времеви стъпки, описани по-горе.

Изчисляване на скоростите

Нека разгледаме уравненията. Позволявам q̇ един= q̇ ( т i -един)и q̇ 2= q̇ ( т i ). Това е, q̇ едини q̇ 2са скоростта в предишната стъпка на времето и скоростта за текущата стъпка на времето (която искаме да определим), съответно. Използвайки полуимплицитната схема на интеграция на Ойлер, предварителното, неограничен скоростта за текущата стъпка (обозначена със звездичка) е:

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

Позволявам P ° С бъде импулсът на ограничението. Разделяйки го на маса, получаваме промяната в скоростта и я прилагаме към предварителната скорост, за да получим желаната скорост, която отговаря на ограниченията:

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

където λ е отново вектор на величини.

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

Наблюдавайте това J q̇ 2+ б = 0, от q̇ 2трябва да е валидна скорост. След това, замествайки и пренареждайки валидното уравнение на скоростта, получаваме

След решаване на това уравнение за λ можем да изчислим импулса на ограничението, използвайки P ° С = J т λ и накрая актуализирайте скоростта.

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

Ограничения на неравенството

За ограниченията на неравенството трябва да ограничим импулсите и да ги поддържаме в допустимите стойности, докато ги натрупваме, така че ограниченията да не прилагат импулси в нежелани посоки или силни страни. Тази ограничителна процедура не е толкова проста, колкото просто прилагането на min / max функция, защото искаме да ограничим само крайния натрупан импулс, но не междинните импулси, генерирани по време на натрупването. Разгледайте GDC на Erin Catto 2009 презентация за подробности.

Топло стартиране

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

Проектиран Гаус-Зайдел

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

Тъй като работим върху скоростта, можем да елиминираме ускорението, като напишем приближение като съотношение между промяната на скоростта и делта времето за текущата стъпка от времето. Позволявам q̇ един= q̇ ( т i -един)и q̇ 2= q̇ ( т i ), тогава:

където отново q̇ едине скоростта, изчислена в предишната стъпка, и q̇ 2е скоростта, която искаме да намерим за текущата стъпка. От втория закон на Нютон имаме:

Замествайки нашето приближение и F ° С = J т λ , получаваме:

Учебно ръководство за архитекти за сертифицирани решения на aws

От ° С. = 0, имаме това J q̇ 2= 0 , защото q̇ 2ще бъде законна скорост, след като това бъде решено. Пренареждане и умножаване по J от двете страни получаваме:

Този MLCP е малко по-различен от този, който имаме за подхода, базиран на сила, тъй като използва приблизително ускорение. След като го решим с помощта на PGS, ще го направим λ , и тогава q̇ 2може да се изчисли с помощта на предишното уравнение:

Актуализираните позиции и ориентации следват лесно от полуимплицитната схема на Ойлер:

Интересното е, че внимателното разследване разкрива, че PGS е еквивалентна на последователни импулси! Ние правим по същество едно и също нещо тук. Топло стартиране отново може да се използва, като λ изчислена в предишната стъпка като отправна точка. Разликата е, че формулирането на последователни импулси е по-интуитивно, но формулировката на PGS е по-обща и позволява по-гъвкав код. Например, можем да експериментираме, използвайки други инструменти за решаване на MLCP.

За повече подробности относно използването на PGS в симулация, базирана на импулси, погледнете Презентация и хартия на Erin Catto от 2005 г. .

Симулиране на триене с използване на импулси

The Кулонов модел на триене е проста и работи добре. Той определя два различни случая, когато две твърди повърхности са в контакт помежду си:

• Статично триене : Устойчивост на тангенциално движение, когато повърхностите не се движат една спрямо друга, защото няма достатъчно сила за преодоляване на триенето. Силата на триене сочи в обратната посока на чистата допирателна сила и е равна на нея по величина.
• Кинетично триене : Устойчивост на тангенциално движение, когато повърхностите се плъзгат. Силата на триене сочи в противоположната посока на движение и е по-малка от нетните допирателни сили по големина.

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

където F е е силата на триене, F н е нормалната сила и μ е коефициент на триене (които могат да бъдат различни при статично и кинетично триене).

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

Където v стр е относителният вектор на скоростта в точката на контакт стр , и т е единичен вектор допирателна към повърхностите. Искаме да доведем до нула тангенциалната скорост.

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

По този начин триенето е друг пример за ограничение на неравенството.

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

Оптимизации

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

Острови

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

В горното изображение, полето Б. е статичен обект, който не се движи. Това е пода. Обектите отляво са подредени, в контакт помежду си. Ако някой от тях изобщо се движи, потенциално ще се преместят и останалите, тъй като между тях съществуват ограничения за контакт. Всяка сила или импулс, приложена към някое от тези тела, може да се разпространи в останалите тела. Триъгълникът в средата обаче просто седи сам върху неподвижната кутия Б. . Силите, приложени върху подредените обекти вляво, никога няма да повлияят на движението на триъгълника, тъй като няма връзка между нито един от подредените обекти и триъгълника. Същото може да се каже и за веригата от кутии вдясно. Всички те са свързани с революционни съединения и така движението на всеки от тях може да генерира реакция по ограниченията, влияеща върху движението на всички други кутии, които са част от веригата. Но те никога няма да повлияят на състоянието на триъгълника, нито на подредените обекти отляво, освен ако не се създаде ново ограничение между някое от тях, като ограничение за контакт / непроникване поради тяхното движение, което ги кара да се сблъскат с другия обекти.

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

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

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

Box2D прави това в своята b2World::Solve метод, който е отговорен за решаването на всички ограничения във всеки стъпка . Той изгражда островите и след това се обажда b2Island::Solve на всеки от тях. Този метод решава ограниченията в този остров, като използва последователни импулси.

Спи

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

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

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

Заключение - Физика на видеоигрите и симулация на ограничено твърдо тяло

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

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

Както обикновено, нещата на теория може да са красиви, но на практика се оказва друга история. Необходими са много умни опростявания, за да се получи стабилно и ефективно изпълнение, особено по отношение на ограничената динамика. През последните няколко години бяха направени много големи разработки по отношение на откриването на сблъсъци, времето за изчисляване на удара, разделителната способност на MLCP и т.н., но все още има много неща, които могат да бъдат подобрени. The Форум на Bullet Physics е добро място да бъдете в течение на това, което се случва в играта и света на симулация на твърда физика на тялото, особено на Дискусия за изследвания и разработки за откриване на сблъсъци и физическа симулация раздел, където членовете обсъждат съвременни физически симулационни техники от всякакъв вид.