Tutorial de fizică a jocurilor video - Partea a II-a: Detectarea coliziunilor pentru obiecte solide

Aceasta este partea a II-a a seriei noastre de trei părți despre fizica jocurilor video. Pentru restul acestei serii, vezi:

Partea I: O introducere în dinamica corpului rigid
Partea a III-a: Simularea corpului rigid constrâns

În partea I a acestei serii, am explorat corpurile rigide și mișcările lor. În acea discuție, totuși, obiectele nu au interacționat între ele. Fără o muncă suplimentară, corpurile rigide simulate pot trece direct unele prin altele sau „se pot întrepătrunde”, ceea ce este de nedorit în majoritatea cazurilor.

Pentru a simula mai realist comportamentul obiectelor solide, trebuie să verificăm dacă acestea se ciocnesc între ele de fiecare dată când se mișcă, iar dacă se mișcă, trebuie să facem ceva în privința asta, cum ar fi aplicarea unor forțe care le modifică vitezele, deci că se vor deplasa în sens opus. Aici înțelegerea fizicii coliziunilor este deosebit de importantă pentru dezvoltatorii de jocuri.

În partea a II-a, vom acoperi etapa de detectare a coliziunii, care constă în găsirea perechilor de corpuri care se ciocnesc într-un număr posibil mare de corpuri împrăștiate în jurul unei lumi 2D sau 3D. În următoarea și ultima parte, vom vorbi mai multe despre „rezolvarea” acestor ciocniri pentru a elimina interpenetrările.

Pentru o trecere în revistă a conceptelor de algebră liniară la care se face referire în acest articol, vă puteți referi la cursul intensiv de algebră liniară din partea I.

Fizica coliziunilor în jocurile video

În contextul simulărilor de corpuri rigide, o coliziune are loc atunci când formele a două corpuri rigide se intersectează sau când distanța dintre aceste forme scade sub o toleranță mică.

Dacă avem n corpuri în simularea noastră, complexitatea computațională a detectării coliziunilor cu teste pe perechi este O ( n 2 ) , un număr care îi face pe informaticieni să se înfioreze. Numărul de teste în perechi crește pătratic cu numărul de corpuri, iar determinarea dacă două forme, în poziții și orientări arbitrare, se ciocnesc nu este deja ieftină. Pentru a optimiza procesul de detectare a coliziunilor, îl împărțim în general în două faze: fază largă și fază îngustă .

Faza largă este responsabilă pentru găsirea perechilor de corpuri rigide care pot fi ciocnite și excluderea perechilor care cu siguranță nu se ciocnesc, din întregul set de corpuri care se află în simulare. Acest pas trebuie să poată scala foarte bine cu numărul de corpuri rigide pentru a ne asigura că rămânem bine sub complexitatea timpului O ( n 2 ) . Pentru a realiza acest lucru, această fază utilizează, în general , partiționarea spațiului cuplată cu volume de limite care stabilesc o limită superioară pentru coliziune.

Faza îngustă operează pe perechile de corpuri rigide găsite de faza largă care s-ar putea ciocni. Este o etapă de rafinare în care determinăm dacă coliziunile au loc cu adevărat și pentru fiecare coliziune care este găsită, calculăm punctele de contact care vor fi folosite pentru a rezolva coliziunile mai târziu.

În secțiunile următoare vom vorbi despre câțiva algoritmi care pot fi utilizați în faza largă și faza îngustă.

Faza larga

În faza generală a fizicii coliziunilor pentru jocurile video, trebuie să identificăm ce perechi de corpuri rigide s- ar putea ciocni. Aceste corpuri pot avea forme complexe, cum ar fi poligoane și poliedre, și ceea ce putem face pentru a accelera acest lucru este să folosim o formă mai simplă pentru a cuprinde obiectul. Dacă aceste volume limită nu se intersectează, atunci și formele reale nu se intersectează. Dacă se intersectează, atunci formele reale s- ar putea intersecta.

Unele tipuri populare de volume de delimitare sunt casete de delimitare orientate (OBB), cercurile în 2D și sferele în 3D. Să ne uităm la unul dintre cele mai simple volume de delimitare: casete de delimitare aliniate pe axe (AABB) .

AABB-urile primesc multă dragoste de la programatorii de fizică, deoarece sunt simple și oferă compromisuri bune. Un AABB bidimensional poate fi reprezentat printr-o structură ca aceasta în limbajul C:

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

Câmpul min reprezintă locația colțului din stânga jos al casetei, iar câmpul max reprezintă colțul din dreapta sus.

Pentru a testa dacă două AABB se intersectează, trebuie doar să aflăm dacă proiecțiile lor se intersectează pe toate axele de coordonate:

 BOOL TestAABBOverlap(AABB* a, AABB* b) { float d1x = b->min.x - a->max.x; float d1y = b->min.y - a->max.y; float d2x = a->min.x - b->max.x; float d2y = a->min.y - b->max.y; if (d1x > 0.0f || d1y > 0.0f) return FALSE; if (d2x > 0.0f || d2y > 0.0f) return FALSE; return TRUE; }

Acest cod are aceeași logică a funcției b2TestOverlap din motorul Box2D (versiunea 2.3.0). Acesta calculează diferența dintre min și max ale ambelor AABB, în ambele axe, în ambele ordine. Dacă oricare dintre aceste valori este mai mare decât zero, AABB-urile nu se intersectează.

Chiar dacă un test de suprapunere AABB este ieftin, nu va ajuta prea mult dacă facem în continuare teste pe perechi pentru fiecare pereche posibilă, deoarece încă avem complexitatea timpului O ( n 2 ) nedorită. Pentru a minimiza numărul de teste de suprapunere AABB, putem folosi un fel de partiționare a spațiului , care funcționează pe aceleași principii ca indicile bazei de date care accelerează interogările. (Bazele de date geografice, cum ar fi PostGIS, folosesc de fapt structuri de date și algoritmi similari pentru indecșii lor spațiali.) În acest caz, totuși, AABB-urile se vor mișca în mod constant, așa că, în general, trebuie să recreăm indici după fiecare pas al simulării.

Există o mulțime de algoritmi de partiționare a spațiului și structuri de date care pot fi utilizate pentru aceasta, cum ar fi grile uniforme, quadtrees în 2D, octrees în 3D și hashing spațial. Să aruncăm o privire mai atentă la doi algoritmi populari de partiționare spațială: sortare și măturare și ierarhii de volum de limite (BVH).

Algoritmul de sortare și măturare

Metoda de sortare și măturare (cunoscută alternativ ca măturare și tăiere ) este una dintre alegerile preferate printre programatorii de fizică pentru utilizarea în simularea corpului rigid. Motorul Bullet Physics, de exemplu, are o implementare a acestei metode în clasa btAxisSweep3 .

Proiecția unui AABB pe o singură axă de coordonate este în esență un interval [ b , e ] (adică început și sfârșit). În simularea noastră, vom avea multe corpuri rigide și, prin urmare, multe AABB-uri și asta înseamnă multe intervale. Vrem să aflăm ce intervale se intersectează.

În algoritmul de sortare și măturare, inserăm toate valorile b și e într-o singură listă și le sortăm crescător după valorile lor scalare. Apoi măturăm sau parcurgem lista. Ori de câte ori este întâlnită o valoare b , intervalul său corespunzător este stocat într-o listă separată de intervale active și ori de câte ori este întâlnită o valoare e , intervalul corespunzător este eliminat din lista de intervale active. În orice moment, toate intervalele active se intersectează. (Consultați teza de doctorat a lui David Baraff, p. 52 pentru detalii. Vă sugerez să utilizați acest instrument online pentru a vizualiza fișierul postscript.) Lista de intervale poate fi reutilizată la fiecare pas al simulării, unde putem resortați eficient. această listă utilizând sortarea prin inserare, care este bun la sortarea listelor aproape sortate.

În două și trei dimensiuni, rularea sortării și măturarii, așa cum este descris mai sus, pe o singură axă de coordonate va reduce numărul de teste directe de intersecție AABB care trebuie efectuate, dar rezultatul poate fi mai bun pe o axă de coordonate decât pe alta. Prin urmare, sunt implementate variații mai sofisticate ale algoritmului de sortare și măturare. În cartea sa Real-Time Collision Detection (pagina 336), Christer Ericson prezintă o variantă eficientă în care stochează toate AABB-urile într-o singură matrice, iar pentru fiecare rulare de sortare și măturare, este aleasă o axă de coordonate și matricea este sortată după valoarea min a AABB-urilor în axa aleasă, folosind quicksort. Apoi, matricea este parcursă și sunt efectuate teste de suprapunere AABB. Pentru a determina următoarea axă care ar trebui utilizată pentru sortare, se calculează varianța centrului AABB-urilor și se alege axa cu varianță mai mare pentru următorul pas.

Arbori de volum de limite dinamice

O altă metodă utilă de partiționare spațială este arborele de volum de limite dinamice , cunoscut și sub numele de Dbvt . Acesta este un tip de ierarhie a volumului de limite.

Dbvt este un arbore binar în care fiecare nod are un AABB care limitează toate AABB-urile copiilor săi. AABB-urile corpurilor rigide în sine sunt situate în nodurile frunzelor. De obicei, un Dbvt este „interogat” dând AABB pentru care am dori să detectăm intersecții. Această operație este eficientă deoarece copiii nodurilor care nu intersectează AABB interogat nu trebuie să fie testați pentru suprapunere. Ca atare, o interogare de coliziune AABB începe de la rădăcină și continuă recursiv prin arbore numai pentru nodurile AABB care se intersectează cu AABB interogat. Arborele poate fi echilibrat prin rotații ale copacilor, ca într-un arbore AVL.

Box2D are o implementare sofisticată a Dbvt în clasa b2DynamicTree . Clasa b2BroadPhase este responsabilă pentru efectuarea fazei ample și folosește o instanță a b2DynamicTree pentru a efectua interogări AABB.

Faza ingusta

După faza largă a fizicii coliziunilor jocurilor video, avem un set de perechi de corpuri rigide care se pot ciocni. Astfel, pentru fiecare pereche, având în vedere forma, poziția și orientarea ambelor corpuri, trebuie să aflăm dacă acestea se ciocnesc, de fapt; dacă se intersectează sau dacă distanța lor se încadrează sub o valoare mică de toleranță. De asemenea, trebuie să știm ce puncte de contact sunt între corpurile care se ciocnesc, deoarece acest lucru este necesar pentru a rezolva coliziunile mai târziu.

Forme convexe și concave

Ca regulă generală a fizicii jocurilor video, nu este trivial să se determine dacă două forme arbitrare se intersectează sau să se calculeze distanța dintre ele. Cu toate acestea, o proprietate care este de o importanță critică pentru a determina cât de greu este este convexitatea formei. Formele pot fi fie convexe , fie concave , iar formele concave sunt mai greu de lucrat, așa că avem nevoie de câteva strategii pentru a le face față.

Într-o formă convexă, un segment de linie între oricare două puncte din formă se încadrează întotdeauna complet în interiorul formei. Cu toate acestea, pentru o formă concavă (sau „non-convexă”), nu același lucru este valabil pentru toate segmentele de linie posibile care conectează punctele din formă. Dacă puteți găsi cel puțin un segment de linie care se încadrează în afara formei, atunci forma este concavă.

Din punct de vedere computațional, este de dorit ca toate formele să fie convexe într-o simulare, deoarece avem o mulțime de algoritmi puternici de testare a distanței și a intersecției care funcționează cu forme convexe. Totuși, nu toate obiectele vor fi convexe și, de obicei, lucrăm în jurul lor în două moduri: înveliș convex și descompunere convexă.

Carcasa convexă a unei forme este cea mai mică formă convexă care o conține în totalitate. Pentru un poligon concav în două dimensiuni, ar fi ca și cum ați bate un cui pe fiecare vârf și a înfășura o bandă de cauciuc în jurul tuturor cuielor. Pentru a calcula carcasa convexă pentru un poligon sau poliedru, sau, mai general, pentru un set de puncte, un algoritm bun de utilizat este algoritmul quickhull , care are o complexitate de timp medie de O ( n log n ) .

Evident, dacă folosim o carcasă convexă pentru a reprezenta un obiect concav, acesta își va pierde proprietățile concave. Comportamentul nedorit, cum ar fi coliziunile „fantomă”, poate deveni evident, deoarece obiectul va avea în continuare o reprezentare grafică concavă. De exemplu, o mașină are de obicei o formă concavă, iar dacă folosim o carcasă convexă pentru a o reprezenta fizic și apoi punem o cutie pe ea, cutia ar putea părea că plutește în spațiul de deasupra.

În general, carcasele convexe sunt adesea suficient de bune pentru a reprezenta obiecte concave, fie pentru că ciocnirile nerealiste nu sunt foarte vizibile, fie pentru că proprietățile lor concave nu sunt esențiale pentru orice este simulat. În unele cazuri, totuși, am putea dori ca obiectul concav să se comporte fizic ca o formă concavă. De exemplu, dacă folosim o carcasă convexă pentru a reprezenta fizic un bol, nu vom putea pune nimic în interiorul acestuia. Obiectele vor pluti pe deasupra. În acest caz, putem folosi o descompunere convexă a formei concave.

Algoritmii de descompunere convexă primesc o formă concavă și returnează un set de forme convexe a căror unire este identică cu forma concavă inițială. Unele forme concave pot fi reprezentate doar printr-un număr mare de forme convexe, iar acestea ar putea deveni prohibitiv de costisitoare de calculat și utilizat. Cu toate acestea, o aproximare este adesea suficient de bună și astfel, algoritmi precum V-HACD produc un set mic de poliedre convexe dintr-un poliedru concav.

În multe cazuri de fizică a coliziunilor, totuși, descompunerea convexă poate fi făcută manual, de către un artist. Acest lucru elimină necesitatea taxării performanței cu algoritmi de descompunere. Deoarece performanța este unul dintre cele mai importante aspecte în simulările în timp real, este în general o idee bună să creați reprezentări fizice foarte simple pentru obiecte grafice complexe. Imaginea de mai jos arată o posibilă descompunere convexă a unei mașini 2D folosind nouă forme convexe.

Testarea intersecțiilor - Teorema axei de separare

Teorema axei de separare (SAT) afirmă că două forme convexe nu se intersectează dacă și numai dacă există cel puțin o axă în care proiecțiile ortogonale ale formelor de pe această axă nu se intersectează.

De obicei, este mai intuitiv din punct de vedere vizual să găsești o linie în 2D sau un plan în 3D care separă cele două forme, ceea ce este de fapt același principiu. Un vector ortogonal cu linia în 2D sau vectorul normal al planului în 3D poate fi folosit ca „axă de separare”.

Motoarele de fizică de joc au o serie de clase diferite de forme, cum ar fi cercuri (sfere în 3D), margini (un singur segment de linie) și poligoane convexe (poliedre în 3D). Pentru fiecare pereche de tip de formă, acestea au un algoritm specific de detectare a coliziunilor. Cel mai simplu dintre ele este probabil algoritmul cerc-cerc:

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

Chiar dacă SAT se aplică cercurilor, este mult mai simplu să verificați dacă distanța dintre centrele lor este mai mică decât suma razelor lor. Din acest motiv, SAT este utilizat în algoritmul de detectare a coliziunilor pentru perechi specifice de clase de forme, cum ar fi poligon convex împotriva poligonului convex (sau poliedre în 3D).

Pentru orice pereche de forme, există un număr infinit de axe pe care le putem testa pentru separare. Astfel, determinarea axei de testat este crucială pentru o implementare eficientă a SAT. Din fericire, atunci când testăm dacă o pereche de poligoane convexe se ciocnește, putem folosi normalele marginilor ca potențiale axe de separare. Vectorul normal n al unei muchii este perpendicular pe vectorul muchiei și punctează în afara poligonului. Pentru fiecare muchie a fiecărui poligon, trebuie doar să aflăm dacă toate vârfurile celuilalt poligon sunt în fața muchiei.

Dacă trece vreun test – adică dacă, pentru orice muchie, toate vârfurile celuilalt poligon sunt în fața acestuia – atunci poligoanele nu se intersectează. Algebra liniară oferă o formulă ușoară pentru acest test: având în vedere o muchie pe prima formă cu vârfurile a și b și un vârf v pe cealaltă formă, dacă ( v - a ) · n este mai mare decât zero, atunci vârful este în față a marginii.

Pentru poliedre, putem folosi normalele feței și, de asemenea, produsul încrucișat al tuturor combinațiilor de muchii din fiecare formă. Asta sună ca o mulțime de lucruri de testat; totuși, pentru a accelera lucrurile, putem stoca în cache ultima axă de separare pe care am folosit-o și să încercăm să o folosim din nou în următorii pași ai simulării. Dacă axa de separare din cache nu mai separă formele, putem căuta o nouă axă pornind de la fețele sau muchiile care sunt adiacente feței sau muchiei anterioare. Acest lucru funcționează deoarece corpurile adesea nu se mișcă sau nu se rotesc mult între pași.

Box2D folosește SAT pentru a testa dacă două poligoane convexe se intersectează în algoritmul său de detectare a coliziunii poligon-poligon din b2CollidePolygon.cpp.

Distanța de calcul - algoritmul Gilbert-Johnson-Keerthi

În multe cazuri de fizică a coliziunilor, dorim să considerăm că obiectele se ciocnesc nu numai dacă se intersectează efectiv, ci și dacă sunt foarte aproape unele de altele, ceea ce ne impune să cunoaștem distanța dintre ele. Algoritmul Gilbert-Johnson-Keerthi (GJK) calculează distanța dintre două forme convexe și, de asemenea, punctele lor cele mai apropiate. Este un algoritm elegant care funcționează cu o reprezentare implicită a formelor convexe prin funcții suport, sume Minkowski și simplexuri, așa cum se explică mai jos.

Funcții de suport

O funcție de suport s A ( d ) returnează un punct de la limita formei A care are cea mai mare proiecție pe vectorul d . Din punct de vedere matematic, are cel mai mare produs punctual cu d . Acesta se numește punct de sprijin , iar această operație este cunoscută și sub denumirea de mapare a suportului . Din punct de vedere geometric, acest punct este cel mai îndepărtat punct de pe formă în direcția lui d .

Găsirea unui punct de sprijin pe un poligon este relativ ușoară. Pentru un punct de sprijin pentru vectorul d , trebuie doar să treceți prin vârfurile sale și să găsiți cel care are cel mai mare produs punctual cu d , astfel:

 Vector2 GetSupport(Vector2 *vertices, int count, Vector2 d) { float highest = -FLT_MAX; Vector2 support = (Vector2){0, 0}; for (int i = 0; i < count; ++i) { Vector2 v = vertices[i]; float dot = vx * dx + vy * dy; if (dot > highest) { highest = dot; support = v; } } return support; }

Cu toate acestea, puterea reală a unei funcții de sprijin este aceea că ușurează lucrul cu forme precum conuri, cilindri și elipse, printre altele. Este destul de dificil să calculezi distanța dintre astfel de forme în mod direct și, fără un algoritm precum GJK, de obicei, ar trebui să le discretizezi într-un poligon sau poliedru pentru a simplifica lucrurile. Cu toate acestea, acest lucru ar putea duce la alte probleme, deoarece suprafața unui poliedru nu este la fel de netedă ca suprafața, de exemplu, a unei sfere, cu excepția cazului în care poliedrul este foarte detaliat, ceea ce poate duce la performanțe slabe în timpul detectării coliziunilor. Pot apărea și alte reacții adverse nedorite; de exemplu, o sferă „poliedrică” s-ar putea să nu se rostogolească fără probleme.

Pentru a obține un punct de sprijin pentru o sferă centrată pe origine, trebuie doar să normalizăm d (adică să calculăm d / || d || , care este un vector cu lungimea 1 (unitatea de lungime) care arată încă în aceeași direcție din d ) și apoi o înmulțim cu raza sferei.

Consultați lucrarea lui Gino van den Bergen pentru a găsi mai multe exemple de funcții de sprijin pentru cilindri și conuri, printre alte forme.

Obiectele noastre vor fi, desigur, deplasate și rotite de la origine în spațiul de simulare, așa că trebuie să fim capabili să calculăm puncte de sprijin pentru o formă transformată. Folosim o transformare afină T ( x ) = R x + c pentru a deplasa și roti obiectele noastre, unde c este vectorul deplasării și R este matricea de rotație . Această transformare rotește mai întâi obiectul în jurul originii, apoi îl translată. Funcția suport pentru o formă transformată A este:

Sume Minkowski

Suma Minkowski a două forme A și B este definită astfel:

Aceasta înseamnă că calculăm suma pentru toate punctele conținute în A și B. Rezultatul este ca și cum umflați A cu B .

În mod similar, definim diferența Minkowski ca:

pe care o putem scrie și ca sumă Minkowski a lui A cu -B :

Pentru convex A și B , A⊕B este de asemenea convex.

O proprietate utilă a diferenței Minkowski este că, dacă conține originea spațiului, formele se intersectează, așa cum se poate vedea în imaginea anterioară. De ce este asta? Pentru că dacă două forme se intersectează, ele au cel puțin un punct în comun, care se află în aceeași locație în spațiu, iar diferența lor este vectorul zero, care este de fapt originea.

O altă caracteristică frumoasă a diferenței Minkowski este că, dacă nu conține originea, distanța minimă dintre origine și diferența Minkowski este distanța dintre forme.

Distanța dintre două forme este definită ca:

Cu alte cuvinte, distanța dintre A și B este lungimea celui mai scurt vector care merge de la A la B. Acest vector este cuprins în A⊖B și este cel cu lungimea cea mai mică, care în consecință este cel mai apropiat de origine.

În general, nu este simplu să construiești în mod explicit suma Minkowski a două forme. Din fericire, putem folosi maparea de asistență și aici, deoarece:

Simplexuri

Algoritmul GJK caută în mod iterativ punctul din diferența Minkowski cel mai apropiat de origine. O face prin construirea unei serii de simplexuri care sunt mai aproape de origine în fiecare iterație. Un simplex – sau mai precis, un k-simplex pentru un întreg k – este învelișul convex a k + 1 puncte afine independente într-un spațiu k-dimensional. Adică, dacă pentru două puncte, ele nu trebuie să coincidă, pentru trei puncte în plus nu trebuie să se afle pe aceeași linie, iar dacă avem patru puncte, nici ele nu trebuie să se afle pe același plan. Prin urmare, 0-simplex este un punct, 1-simplex este un segment de linie, 2-simplex este un triunghi și 3-simplex este un tetraedru. Dacă scoatem un punct dintr-un simplex, îi decrementăm dimensionalitatea cu unu, iar dacă adăugăm un punct la un simplex îi creștem dimensionalitatea cu unu.

GJK în acțiune

Să punem toate acestea împreună pentru a vedea cum funcționează GJK. Pentru a determina distanța dintre două forme A și B , începem prin a lua diferența lor Minkowski A⊖B . Căutăm cel mai apropiat punct de origine pe forma rezultată, deoarece distanța până la acest punct este distanța dintre cele două forme originale. Alegem un punct v din A⊖B , care va fi aproximarea distanței noastre. De asemenea, definim un set de puncte gol W , care va conține punctele din simplexul de test curent.

Apoi intrăm într-o buclă. Începem prin a obține punctul de sprijin w = s A⊖B (- v ) , punctul de pe A⊖B a cărui proiecție pe v este cea mai apropiată de origine.

Dacă || w || nu este mult diferit de || v || iar unghiul dintre ele nu s-a schimbat prea mult (după niște toleranțe predefinite), înseamnă că algoritmul a convergit și putem reveni || v || ca distanta.

În caz contrar, adăugăm w la W . Dacă carcasa convexă a lui W (adică simplexul) conține originea, formele se intersectează și asta înseamnă și că am terminat. În caz contrar, găsim punctul din simplex care este cel mai apropiat de origine și apoi resetăm v pentru a fi această nouă aproximare cea mai apropiată. În cele din urmă, eliminăm orice puncte din W care nu contribuie la calculul punctului cel mai apropiat. (De exemplu, dacă avem un triunghi, iar cel mai apropiat punct de origine se află într-una dintre muchiile sale, putem elimina punctul din W care nu este un vârf al acestei muchii.) Apoi repetăm ​​acești pași până la algoritmul converge.

Următoarea imagine arată un exemplu de patru iterații ale algoritmului GJK. Obiectul albastru reprezintă diferența Minkowski A⊖B iar vectorul verde este v . Puteți vedea aici cum v se apropie de cel mai apropiat punct de origine.

Pentru o explicație detaliată și aprofundată a algoritmului GJK, consultați lucrarea A Fast and Robust GJK Implementation for Collision Detection of Convex Objects , de Gino van den Bergen. Blogul pentru motorul de fizică dyn4j are și o postare grozavă pe GJK.

Box2D are o implementare a algoritmului GJK în b2Distance.cpp, în funcția b2Distance . Folosește GJK doar în timpul calculării impactului în algoritmul său pentru detectarea continuă a coliziunilor (un subiect pe care îl vom discuta mai jos).

Motorul de fizică Chimpunk folosește GJK pentru toate detectarea coliziunilor, iar implementarea sa este în cpCollision.c, în funcția GJK . Dacă algoritmul GJK raportează intersecția, mai trebuie să știe care sunt punctele de contact, împreună cu adâncimea de penetrare. Pentru a face acest lucru, folosește algoritmul expansiv al politopului, pe care îl vom explora în continuare.

Determinarea adâncimii de penetrare - algoritmul politopului în expansiune

După cum sa menționat mai sus, dacă formele A și B se intersectează, GJK va genera un simplex W care conține originea, în interiorul diferenței Minkowski A⊖B . În această etapă, știm doar că formele se intersectează, dar în proiectarea multor sisteme de detectare a coliziunilor, este de dorit să putem calcula câtă intersecție avem și ce puncte putem folosi ca puncte de contact, astfel încât gestionăm coliziunea într-un mod realist. Expanding Polytope Algorithm (EPA) ne permite să obținem acele informații, începând de unde a rămas GJK: cu un simplex care conține originea.

Adâncimea de penetrare este lungimea vectorului de translație minimă (MTV), care este cel mai mic vector de-a lungul căruia putem transla o formă care se intersectează pentru a o separa de cealaltă formă.

Când două forme se intersectează, diferența lor Minkowski conține originea, iar punctul de la limita diferenței Minkowski care este cel mai apropiat de origine este MTV. Algoritmul EPA găsește acest punct prin extinderea simplexului pe care GJK ni l-a dat într-un poligon; subdivând succesiv muchiile sale cu noi vârfuri.

În primul rând, găsim marginea simplexului cel mai apropiat de origine și calculăm punctul de sprijin în diferența Minkowski într-o direcție care este normală muchiei (adică perpendiculară pe aceasta și îndreptată în afara poligonului). Apoi împărțim această margine adăugând acest punct de sprijin. Repetăm ​​acești pași până când lungimea și direcția vectorului nu se schimbă prea mult. Odată ce algoritmul converge, avem MTV-ul și adâncimea de penetrare.

Folosind GJK în combinație cu EPA, obținem o descriere detaliată a coliziunii, indiferent dacă obiectele se intersectează deja sau doar suficient de aproape pentru a fi considerate o coliziune.

Algoritmul EPA este descris în lucrarea Proximity Queries and Penetration Depth Computation on 3D Game Objects , scrisă tot de Gino van den Bergen. Blogul dyn4j are și o postare despre EPA.

Detectare continuă a coliziunilor

Tehnicile de fizică a jocurilor video prezentate până acum realizează detectarea coliziunilor pentru o imagine statică a simulării. Aceasta se numește detectare discretă a coliziunilor și ignoră ceea ce se întâmplă între pașii anteriori și actuali. Din acest motiv, este posibil ca unele coliziuni să nu fie detectate, în special pentru obiectele care se mișcă rapid. Această problemă este cunoscută sub numele de tunel .

Tehnicile de detectare continuă a coliziunilor încearcă să găsească când două corpuri s-au ciocnit între pasul anterior și cel curent al simulării. Ei calculează timpul de impact , astfel încât apoi să ne întoarcem în timp și să procesăm coliziunea în acel moment.

Timpul impactului (sau timpul contactului) t c este momentul în care distanța dintre două corpuri este zero. Dacă putem scrie o funcție pentru distanța dintre două corpuri de-a lungul timpului, ceea ce dorim să găsim este cea mai mică rădăcină a acestei funcții. Astfel, timpul de calcul al impactului este o problemă de găsire a rădăcinii .

Pentru momentul calculării impactului, luăm în considerare starea (poziția și orientarea) corpului în pasul anterior la momentul ti -1 și în pasul curent la momentul ti . Pentru a simplifica lucrurile, presupunem o mișcare liniară între pași.

Să simplificăm problema presupunând că formele sunt cercuri. Pentru două cercuri C 1 și C 2 , cu raza r 1 și r 2 , unde centrul lor de masă x 1 și x 2 coincid cu centroidul lor (adică se rotesc în mod natural în jurul centrului lor de masă), putem scrie funcția distanță. la fel de:

Având în vedere mișcarea liniară între pași, putem scrie următoarea funcție pentru poziția lui C 1 de la t i -1 la t i

Este o interpolare liniară de la x 1 ( t i -1 ) la x 1 ( t i ) . Același lucru se poate face și pentru x 2 . Pentru acest interval putem scrie o altă funcție de distanță:

Setați această expresie egală cu zero și obțineți o ecuație pătratică pe t . Rădăcinile pot fi găsite direct folosind formula pătratică. Dacă cercurile nu se intersectează, formula pătratică nu va avea o soluție. Dacă o fac, ar putea rezulta una sau două rădăcini. Dacă are o singură rădăcină, acea valoare este timpul de impact. Dacă are două rădăcini, cea mai mică este momentul impactului, iar cealaltă este momentul în care cercurile se separă. Rețineți că timpul de impact aici este un număr de la 0 la 1. Nu este un timp în secunde; este doar un număr pe care îl putem folosi pentru a interpola starea corpurilor în locul exact în care s-a produs coliziunea.

Detectare continuă a coliziunilor pentru non-cercuri

Scrierea unei funcții de distanță pentru alte tipuri de forme este dificilă, în primul rând pentru că distanța lor depinde de orientările lor. Din acest motiv, folosim, în general, algoritmi iterativi care mută obiectele din ce în ce mai aproape la fiecare iterație până când sunt suficient de aproape pentru a fi considerate ciocnind.

Algoritmul de avansare conservator deplasează corpurile înainte (și le rotește) iterativ. În fiecare iterație calculează o limită superioară pentru deplasare. Algoritmul original este prezentat în teza de doctorat a lui Brian Mirtich (secțiunea 2.3.2), care ia în considerare mișcarea balistică a corpurilor. Această lucrare a lui Erwin Coumans (autorul Bullet Physics Engine) prezintă o versiune mai simplă care utilizează viteze liniare și unghiulare constante.

Algoritmul calculează cele mai apropiate puncte dintre formele A și B , desenează un vector de la un punct la altul și proiectează viteza pe acest vector pentru a calcula o limită superioară a mișcării. Acesta garantează că niciun punct de pe corp nu se va deplasa dincolo de această proiecție. Apoi înaintează corpurile cu această sumă și se repetă până când distanța scade sub o valoare mică de toleranță.

Poate fi nevoie de prea multe iterații pentru a converge în unele cazuri, de exemplu, când viteza unghiulară a unuia dintre corpuri este prea mare.

Rezolvarea coliziunilor

Odată ce o coliziune a fost detectată, este necesar să se schimbe mișcările obiectelor care se ciocnesc într-un mod realist, cum ar fi determinându-le să sară unele de altele. În următoarea și ultima parte a acestei teorii, vom discuta câteva metode populare de rezolvare a coliziunilor în jocurile video.

Referințe

Dacă sunteți interesat să obțineți o înțelegere mai profundă despre fizica coliziunilor, cum ar fi algoritmii și tehnicile de detectare a coliziunilor, cartea Real-Time Collision Detection , de Christer Ericson, este un must-have.

Deoarece detectarea coliziunilor se bazează în mare măsură pe geometrie, articolul lui Toptal Computational Geometry in Python: From Theory to Application este o introducere excelentă a subiectului.