Detectarea coliziunii

Versiunea actuală a paginii nu a fost încă revizuită de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 29 octombrie 2018; verificările necesită 20 de modificări .

Detectarea coliziunilor este o problemă de calcul de detectare a intersecțiilor dintre două sau mai multe obiecte. Subiectul este cel mai adesea asociat cu utilizarea sa în motoare de fizică , animație pe computer și robotică . Pe lângă determinarea dacă două obiecte s-au ciocnit, sistemele de detectare a coliziunilor pot calcula timpul de impact și pot raporta o manifold de contact (set de puncte de intersecție) [1] . Răspunsul la o coliziune (ce se întâmplă atunci când este detectată o coliziune) depinde de procesul particular care este modelat. Algoritmii de detectare a coliziunilor folosesc pe scară largă conceptele din algebra liniară și geometria computațională. Algoritmii de detectare a coliziunilor sunt una dintre componentele principale ale fizicii jocurilor tridimensionale pe computer .

Prezentare generală

Funcționarea unui model fizic implică efectuarea de experimente fizice, cum ar fi jocul de biliard . Fizica ciocnirii bilelor de biliard este bine descrisă de fizica stării solide și de teoria impactului perfect elastic . Condițiile inițiale sunt stabilite de caracteristicile fizice absolut exacte ale mesei și mingiilor de biliard, precum și de coordonatele inițiale ale bilelor. Având în vedere accelerația bilei tac (probabil rezultatul unui jucător care lovește bila tac cu un stick tac), dorim să calculăm traiectoriile exacte de mișcare, viteza și locul de oprire ale tuturor bilelor folosind un program de calculator. Un motor de fizică care simulează biliardul va fi format din mai multe componente, dintre care una va fi responsabilă pentru calcularea cu precizie a ciocnirilor dintre bile. Această componentă este un exemplu de parte instabilă a modelului - erorile mici în calculele coliziunilor vor duce la modificări semnificative ale rezultatelor - pozițiile finale ale bilelor pe masă.

Jocurile pe calculator au aproximativ aceleași cerințe pentru motoarele fizice, cu excepția unor diferențe semnificative. În timp ce simularea experimentelor fizice necesită crearea celui mai precis aparat matematic care descrie lumea reală, jocurile pe calculator au nevoie de o fizică care pare doar credibilă, dar în același timp calculată în timp real , deși grosier. Compromisurile sunt permise atâta timp cât îi convine jucătorului și are un realism vizual acceptabil. Prin urmare, corpul care este verificat pentru coliziune - așa-numitul hitbox - este mai simplu decât un model de caracter tridimensional. În special, în Team Fortress 2 personajele au trei hitbox-uri:

o cutie mare (aceeași pentru toate clasele) - pentru a verifica o coliziune cu rachete;
dacă personajul trece prin deschidere - acest lucru este determinat de un paralelipiped mai mic (de asemenea, comun tuturor claselor);
pentru a verifica gloanțe - o combinație de paralelipipede, repetând aproximativ figura (fiecare clasă are propria sa).

Un sistem mai sofisticat de detectare a coliziunilor este utilizat în World of Tanks (și în alte simulatoare de vehicule militare). Aici, în loc de hitbox, este folosit un model de coliziune poligonală al rezervorului. Este mult mai dur decât modelul vizual al unui vehicul de luptă, dar vă permite să calculați cu suficientă precizie unghiul de impact asupra rezervorului unui proiectil, ceea ce este important atunci când se calculează penetrarea și/sau ricoșetul, precum și impactul proiectile cu ecrane cu balamale. Un sistem și mai sofisticat de detectare a coliziunilor este folosit în World of Warships . Aici se calculează nu numai ciocnirea unui proiectil cu un element de navă, ci și impactul efectelor unei explozii de proiectil: fragmente, o undă de șoc, ținând cont de locația detaliilor modelului de coliziune.

Detectarea coliziunilor în simulările de fizică

Motoarele fizice diferă prin modul în care reacționează la coliziuni. Unii folosesc flexibilitatea materialelor pentru a calcula forța care rezultă dintr-o coliziune și afectează rezultatul coliziunii în intervale de timp ulterioare, ceea ce este destul de costisitor din punct de vedere computațional. Unele modele calculează timpul aproximativ de coliziune folosind interpolarea liniară, după care „retrocedează” starea scenei la un anumit moment în timp și calculează coliziunea pe baza legilor conservării energiei.

Unii folosesc interpolarea liniară iterativă ( metoda lui Newton ) pentru a calcula timpul de coliziune cu o precizie mult mai mare decât restul calculelor. Metoda de detectare a coliziunilor încalcă principiul coerenței timpului pentru a putea îmbunătăți acuratețea intervalelor de timp fără a crește sarcina totală a resurselor de calcul ale sistemului.

După o coliziune neelastică , pot apărea stări speciale de alunecare sau de repaus, care, de exemplu, sunt emulate folosind constrângeri în motorul de fizică gratuit Open Dynamics Engine . Constrângerile exclud inerția și, ca urmare, instabilitatea. Implementarea repausului în termeni de grafic al scenei evită deplasările.

Cu alte cuvinte, implementările modelelor fizice sunt de obicei împărțite în două căi:

detectarea coliziunilor a posteriori ,
abordare a priori (detecție înainte de producerea coliziunii).

Pe lângă împărțirea în abordări a posteriori și a priori, aproape toți algoritmii moderni de detectare a coliziunilor sunt împărțiți într-o ierarhie de algoritmi.

Diferențele dintre abordările a posteriori și a priori

În cazul abordării a posteriori, calculul modelului se realizează prin calculul stărilor scenei la intervale scurte de timp, fiecare dintre acestea fiind verificată pentru prezența unor obiecte care se intersectează sau amplasate atât de aproape încât pot fi considerate intersectante. . La fiecare pas al simulării se creează o listă de corpuri care se intersectează, pozițiile și traiectoriile acestor corpuri sunt „corectate” ținând cont de faptul ciocnirii. Această abordare se numește a posteriori, deoarece de fapt momentul exact imediat al coliziunii este ratat și este detectat la ceva timp după ce a avut loc (sau cu ceva timp înainte, în funcție de algoritm).

Cu abordarea a priori, este creat un algoritm de detectare a coliziunilor care este capabil să prezică traiectoria mișcărilor corpurilor fizice cu mare precizie. Ciocnirile sunt descrise de acest model cu mare precizie, iar corpurile fizice, în esență, nu se găsesc niciodată într-o stare de penetrare reciprocă. Această abordare se numește a priori, deoarece momentele de ciocnire ale corpurilor sunt determinate înainte de schimbarea configurației spațiale a obiectelor din scenă.

Principalele sale avantaje provin din abordarea a posteriori. Algoritmul nu trebuie să manipuleze un număr semnificativ de variabile fizice - intrarea sa este o simplă listă de corpuri fizice, rezultatul este un subset de corpuri care se intersectează. Algoritmul nu trebuie să se ocupe de forțele de frecare, ciocniri elastice sau, chiar mai rău, inelastice și, de asemenea, să calculeze modificarea stării interne a corpurilor deformabile . În plus, algoritmul a posteriori este în esență mai simplu cu o dimensiune, deoarece în abordarea a priori trebuie să se ocupe de o axă suplimentară - timpul, de care abordarea a posteriori este ferită.

Pe de altă parte, algoritmii a posteriori duc la probleme în stadiul „corectării” întrepătrunderilor corpurilor care au avut loc, care nu apar într-o scenă fizică reală.

Avantajele abordării a priori sunt acuratețea și stabilitatea modelului. Este dificil (dar teoretic posibil) să se separe complet componenta fizică a modelului scenei de algoritmul de detectare a coliziunilor. În cele mai multe cazuri, cu excepția celor mai simple, problema prezicerii momentului de ciocnire a două corpuri din unele date inițiale nu are o soluție generală abstractizată din restul modelului. Se folosește metoda numerică de găsire a rădăcinii.

Unele corpuri se află într-o stare de contact de repaus, adică sunt în mod formal în ciocnire constantă, ceea ce nu duce la mișcări respingătoare ale corpurilor sau la întrepătrundere (de exemplu, o vază în picioare pe o masă). În toate cazurile, un contact în repaus necesită o abordare excepțională: dacă două corpuri se ciocnesc (“a posteriori”) sau alunecă (“a priori”) și mișcarea lor relativă este sub un anumit prag, frecarea este tratată ca lipire, iar ambele obiecte sunt combinate într-o singură ramură a graficului scenei .

Optimizare

Abordările evidente ale detectării coliziunilor pentru o scenă întreagă cu multe obiecte sunt destul de lente. Verificarea faptului unei coliziuni a fiecărui obiect cu fiecare este realizabilă, dar extrem de ineficientă din punct de vedere al complexității de calcul pentru un număr mare de obiecte. Verificarea obiectelor cu geometrie complexă pentru prezența unei coliziuni între ele printr-o metodă evidentă de verificare a coliziunii fețelor individuale ale corpurilor este foarte costisitoare în sine. Astfel, o cantitate semnificativă de cercetări în domeniu vizează rezolvarea problemelor de performanță.

Aplicarea coerenței temporale

În multe aplicații, configurația corpurilor fizice se modifică foarte puțin în timpul perioadei de timp iterative. Multe obiecte din scenă nu se mișcă deloc. Algoritmii sunt creați în așa fel încât rezultatele calculelor efectuate în iterația anterioară să fie folosite în următoarea, ceea ce duce la o creștere a performanței.

La nivelul detectării coliziunilor grosiere, scopul este de a găsi obiecte care se pot intersecta. Aceste perechi necesită analize suplimentare. Unul dintre acești algoritmi a fost dezvoltat de Ming Chieh Lin de la Universitatea din California din Berkeley [2] , care a propus utilizarea metodei cutiilor de delimitare, ai căror vectori de margine sunt coliniari cu vectorii de bază ai sistemului de coordonate carteziene, pentru toate N. corpuri de scena. Mai târziu, aceste casete de delimitare au devenit cunoscute sub numele de caseta de delimitare aliniată pe axă (AABB).

Fiecare paralelipiped este reprezentat de un triplu de segmente, de exemplu . Un algoritm obișnuit pentru detectarea coliziunilor cu casete de delimitare este algoritmul de „ mătură și tăiere ” [ 3 ] . Evident, două astfel de paralelipipedi și se intersectează dacă și numai dacă se intersectează cu , se intersectează cu și se intersectează cu . Se presupune că, dacă de la o iterație la alta și se intersectează, atunci este foarte probabil ca acestea să se intersecteze în continuare la următoarea iterație. De asemenea, dacă nu s-au intersectat în iterația anterioară, este foarte probabil să nu se intersecteze în următoarea. $I_1 \times I_2 \times I_3=[a_1,b_1] \times [a_2,b_2] \times [a_3,b_3]$ $I_1 \times I_2 \times I_3$ $J_1 \times J_2 \times J_3$ $I_1$ $J_{1}$ $eu_{2}$ $J_{2}$ $I_3$ $J_{3}$ $eu_{k}$ $J_{k)$

Deci, problema se rezumă la controlul iterativ de la „cadru” la „cadru” pentru care dintre segmente se intersectează. Există trei liste de intervale (una pentru fiecare axă de coordonate) și toate trei de aceeași lungime, deoarece lungimea fiecăruia este egală cu , în funcție de numărul de obiecte din scenă și, în consecință, de casetele lor de delimitare. Fiecare dintre liste corespunde unei matrice ale cărei elemente sunt egale cu 1 sau 0. - dacă segmentele și se intersectează, și în caz contrar. $n$ $M_{n\times n)$ $m_{{ij}}$ $m_{ij}=1$ $i$ $j$ $m_{ij}=0$

Să presupunem că matricea rămâne practic neschimbată de la o iterație la alta. Pentru a utiliza acest lucru, lista segmentelor de linie este conținută sub formă de puncte extreme etichetate. Fiecare element al listei are coordonatele punctului extrem și un număr unic care identifică segmentul. Lista este sortată după coordonate, iar matricea este actualizată în ordinea corespunzătoare. Este ușor de verificat că algoritmul indicat va oferi performanțe suficient de ridicate dacă configurația casetelor de delimitare nu se schimbă semnificativ într-o singură iterație. $M_{n\times n)$

În cazul corpurilor deformabile , cum ar fi redarea unui model fizic al unui țesut , nu există nicio modalitate de a utiliza o metodă mai specifică - algoritmul de eliminare a perechii descris mai jos, iar algoritmii care utilizează abordarea „ n - corpi tăiate” devin cea mai bună metodă. .

Dacă se poate impune o constrângere de valoare maximă asupra vitezei corpurilor fizice din scenă, atunci perechile de obiecte pot fi eliminate din lista de candidați la coliziuni în funcție de distanța lor inițială unul față de celălalt și de dimensiunea pasului de iterație de timp . $\Delta t$

Reducere în perechi

După ce o pereche de obiecte de scenă este selectată pentru un studiu suplimentar, este necesară o verificare mai detaliată pentru o coliziune. În multe aplicații, unele dintre obiecte (dacă configurația lor geometrică este relativ constantă, adică nu sunt supuse unor deformări severe) sunt descrise de un set de primitive de dimensiuni mici, mai ales triunghiuri. Adică există două seturi de triunghiuri și (pentru simplitate, se presupune că cardinalitatea mulțimilor este egală). $S={S_1,S_2,\dots,S_n}$ $T={T_1,T_2,\dots,T_n}$

O modalitate evidentă de a testa corpurile pentru coliziuni este de a testa toate perechile ordonate de triunghiuri pentru coliziuni. Cu toate acestea, complexitatea unui astfel de control este , ceea ce este extrem de ineficient. Devine necesar, dacă este posibil, utilizarea unui algoritm de „scădere” pentru a reduce numărul de perechi de triunghiuri care trebuie verificate. $(S_{j},T_{k})$ $\operatorname{O}(n^2)$

Cea mai utilizată familie de algoritmi este metoda volumului de limite ierarhice . Ca pas preliminar, pentru fiecare obiect (în exemplul nostru, acesta este și ) este calculată și atribuită o ierarhie de obiecte de delimitare. După aceea, la fiecare iterație de timp, când este necesară verificarea unei coliziuni între obiecte și , volumele de delimitare sunt utilizate pentru a reduce numărul de triunghiuri care se încadrează în test. Unul dintre cele mai simple tipuri de volum de delimitare este o sferă. $S$ $T$ $S$ $T$

Pentru un set de triunghiuri , sfera de mărginire poate fi calculată . Există mai multe moduri de a alege , principalul lucru este că sfera acoperă complet setul de primitive triunghiulare și, în același timp, este cât mai mică posibil. $E$ $B(E)$ $B(E)$ $B(E)$ $B(E)$

La determinarea prezenței unei coliziuni de corpuri și , este posibil în primul rând să se calculeze sferele și . Este evident că, dacă aceste sfere nu sunt intersectate, atunci ambele și nu sunt intersectate . Cu toate acestea, acest lucru nu este cu mult mai eficient decât algoritmul de tăiere n -corp. $S$ $T$ $B(S)$ $B(T)$ $S$ $T$

Fie un set de triunghiuri. Apoi poate fi împărțit în două părți: și . În mod similar, se pot partiționa și și precalcula sferele de delimitare și . $E={E_1,E_2,\dots,E_m}$ $L(E):={E_1,E_2,\dots,E_{m/2}}$ $R(E):={E_{m/2+1},\dots,E_{m-1},E_m}$ $S$ $T$ $B(L(S)),B(R(S))$ $B(L(T)),B(R(T))$

Calculul este că aceste sfere de delimitare sunt mult mai mici decât și . Și, dacă, de exemplu, și nu se intersectează, atunci nu are sens să verifici intersecțiile triunghiurilor mulțimii cu triunghiuri din . $B(S)$ $B(T)$ $B(S)$ $B(L(T))$ $S$ $L(T)$

În cursul calculelor preliminare, este posibil să se considere fiecare corp fizic reprezentat ca o mulțime de triunghiuri și să-l descompune ca un arbore binar , în care nodurile (nodurile) vor fi seturi de triunghiuri, iar descendenții lor vor fi și . Pentru fiecare nod al acestui arbore, sfera de delimitare poate fi precalculată . Într-un astfel de caz, atunci când devine necesară verificarea coliziunii următoarei perechi de corpuri, arborii lor binari precalculați de sfere de delimitare pot fi utilizați pentru a exclude o parte semnificativă din seturile de triunghiuri care trebuie verificate. $N$ $L(N)$ $R(N)$ $B(N)$

Multe implementări suplimentare ale algoritmilor „arboresc” sunt obținute prin alegerea altor obiecte stereometrice ca volume limită, mai degrabă decât sfere. Atunci când se alege un paralelipiped orientat paralel cu axele sistemului de măsurare ( ing. ax-aligned bounding box ), se obțin așa-numiții arbori AABB ( ing. AABB-Trees ). Arborii OBB (sau arborii OOBB ) se obțin prin utilizarea unei casete orientate conform propriului sistem de coordonate al obiectului. Unii dintre arbori sunt mai ușor de actualizat dacă obiectul principal se modifică. Unii copaci pot lucra cu primitive de ordin superior, cum ar fi spline , în loc de triunghiuri elementare.

Detectare precisă a coliziunilor în perechi

După ce a avut loc o reducere preliminară a perechilor de candidați pentru o posibilă coliziune, este necesar să se efectueze o verificare exactă a prezenței unei coliziuni pentru fiecare pereche rămasă.

Observația principală este că pentru oricare două obiecte convexe necontigue, există un plan astfel încât un obiect se va afla complet pe o parte a acestui plan, iar celălalt pe cealaltă. Acest fapt permite dezvoltarea unor algoritmi de detectare a coliziunilor rapide pentru obiecte convexe.

Lucrările timpurii în acest domeniu au subliniat metodele planului de separare . Două triunghiuri se ciocnesc în esență numai atunci când nu pot fi separate de un plan care trece prin trei vârfuri. Așa este, dacă triunghiurile și , unde fiecare vector este în , atunci puteți alege trei vârfuri - , trageți un plan prin toate trei și verificați dacă planul se separă. Dacă oricare dintre aceste planuri se separă, atunci triunghiurile nu se intersectează; și se intersectează dacă, dimpotrivă, niciuna dintre ele nu se desparte. Sunt 20 de astfel de avioane în total. ${v_{1},v_{2},v_{3))$ ${v_{4},v_{5},v_{6))$ $v_{j}$ $\mathbb R^3$ ${\displaystyle v_{i},v_{j},v_{k))$

Dacă triunghiurile sunt coplanare, acest test nu va avea succes complet. Cu toate acestea, puteți adăuga plane, de exemplu, perpendiculare pe fețele unui triunghi, pentru a rezolva problema în cazul general. În alte cazuri, obiectele care, de exemplu, ating marginile lor trebuie neapărat să întâlnească colțuri undeva și, prin urmare, o metodă generală de detectare a coliziunilor trebuie să poată rezolva problema coliziunii.

De atunci, s-au dezvoltat metode mai bune. În prezent, sunt disponibili algoritmi foarte rapizi pentru găsirea celor mai apropiate puncte de pe suprafața a două corpuri poliedrice convexe. În 1993, M. C. Lin a folosit o variație a metodei simplex din programarea liniară în disertația sa [4] . Ulterior, algoritmul Gilbert-Johnson-Curthy a înlocuit această abordare. Acești algoritmi se apropie de un timp de calcul constant atunci când sunt aplicați secvențial la perechi de corpuri staționare sau care se mișcă lent atunci când sunt utilizați cu date inițiale dintr-o iterație anterioară de detectare a coliziunilor.

Rezultatul tuturor acestor progrese este capacitatea de a detecta efectiv coliziunile în timp real pentru mii de corpuri în mișcare pe un computer personal sau o consolă de jocuri .

Decuparea a priori

În cazurile în care majoritatea obiectelor de pe scenă sunt nemișcate, așa cum se întâmplă adesea în jocurile pe calculator, metodele a priori care folosesc precalculări pot fi folosite pentru a accelera calculele.

În aceste situații, tăierea (căderea) este de dorit: atât „tundere n-corp”, cât și tăiere în perechi. Cu toate acestea, acești algoritmi necesită timp pentru a calcula și iau în considerare tipurile de mișcare utilizate în sistemul fizic de bază.

Când vine vorba de detectarea precisă a coliziunilor în perechi, algoritmul devine foarte dependent de traiectoria corpurilor implicate în ciocnire și pentru cel puțin un corp este necesar să se utilizeze un algoritm numeric de găsire a rădăcinii pentru a calcula momentul coliziunii.

Ca exemplu, luați în considerare două triunghiuri care se mișcă în timp: și . În orice moment, aceste două triunghiuri pot fi testate pentru intersecție folosind cele douăzeci de planuri discutate mai sus. Cu toate acestea, procesul poate fi îmbunătățit, deoarece aceste douăzeci de avioane pot fi urmărite în timp. Dacă este un avion care trece prin punctele din , atunci aceasta înseamnă că douăzeci de avioane sunt disponibile pentru urmărire. Fiecare plan trebuie urmărit în raport cu trei vârfuri, ceea ce oferă şaizeci de valori de urmărire. Folosind căutarea rădăcină pentru aceste șaizeci de funcții, se calculează timpul exact de coliziune pentru două triunghiuri date și pentru două traiectorii date. Dacă traiectoriile vârfurilor sunt considerate a fi polinoame liniare (polinoame) în , atunci ultimele șaizeci de funcții sunt polinoame cubice, iar în acest caz excepțional este posibil să găsim timpul exact de coliziune folosind formula rădăcinilor cubice. Unii experți în analiză numerică cred că utilizarea formulei rădăcinii cubice nu este la fel de stabilă numeric ca utilizarea înrădăcinării polinomiale. ${v_1(t),v_2(t),v_3(t)}$ ${v_4(t),v_5(t),v_6(t)}$ $P(u,v,w)$ $u,v,w$ $\mathbb R^3$ $t$

Partiționare spațială

Algoritmii alternativi pot fi grupați după faptul că folosesc partiționarea spațiului , care include arbori BSP , octrees și alte abordări similare . Dacă algoritmul de partiționare spațială aplicat împarte scena cu obiecte într-un set de regiuni și dacă două obiecte sunt în regiuni diferite, atunci nu sunt verificate pentru intersecții. Deoarece arborii BSP pot fi precalculați, această abordare este potrivită pentru gestionarea pereților și a altor obstacole fixe în jocuri. Acești algoritmi de partiționare a spațiului sunt în general mai vechi decât algoritmii descriși mai sus.

Detectarea coliziunilor în jocurile pe calculator

Jocurile pe calculator, în special jocurile pe consolă , trebuie să-și distribuie multe dintre sarcinile lor între resurse hardware foarte limitate și timpi foarte limitati de execuție a procesului de joc. În ciuda acestor limitări și a utilizării unor algoritmi de detectare a coliziunilor relativ primitivi și inexacți, dezvoltatorii de jocuri au reușit să creeze subsisteme de fizică credibile vizual și relativ realiste.

Pentru o perioadă destul de lungă de timp în jocurile pe calculator a existat un număr foarte limitat de obiecte care interacționau fizic între ele și, prin urmare, verificarea tuturor obiectelor pentru intersecții nu a fost o problemă. În jocurile 2D, în unele cazuri, hardware-ul a fost capabil să detecteze și să raporteze eficient pixelii care se intersectează între sprite -urile de pe ecran. În alte cazuri, eliminarea efectivă (reducerea) a fost asigurată prin simpla împărțire (ruperea în fragmente - plăci ) a ecranului și legarea fiecărui sprite de plăcuța cu care se intersectează. Cutiile de delimitare și/sau cercuri au fost folosite pentru a verifica intersecțiile pe perechi, ceea ce a fost considerat a fi destul de precis.

Jocurile 3D folosesc tehnici de partiționare spațială pentru „tunderea n-corp” și au folosit de mult una sau mai multe sfere de delimitare pentru un singur obiect 3D pentru a verifica intersecțiile perechi. Verificările precise au fost foarte rare, cu excepția jocurilor care încearcă să imite realitatea relativ precis. Dar chiar și în aceste cazuri nu se efectuează întotdeauna verificări precise pentru intersecții, ci doar în cele mai importante locuri și/sau situații din punctul de vedere al jocului.

Pe baza faptului că jocurile nu trebuie să imite cu exactitate realitatea, stabilitatea nu este esențială. Aproape toate jocurile folosesc metode de detectare a coliziunilor a posteriori , iar coliziunile sunt adesea rezolvate prin aplicarea unor reguli foarte simple. De exemplu, dacă un personaj virtual „cade printr-un perete”, acesta poate fi mutat pur și simplu înapoi la ultima sa poziție „corectă” cunoscută. Unele jocuri nu detectează deloc coliziunile, ci pur și simplu măsoară distanța parcursă de personaj și dacă această distanță este egală sau mai mare decât o distanță predeterminată pe care personajul o poate parcurge (de exemplu, lungimea unei camere de la perete). pe perete), apoi împiedicați-l să se miște mai departe.

În majoritatea jocurilor pe calculator, principalele obiecte pentru evitarea coliziunilor și pătrunderilor sunt terenul și mediul nivelului - structuri statice, neinteractive și nedistructibile (munti, copaci, clădiri, garduri etc.). În acest caz, caracterul este reprezentat doar de un punct, iar metoda de partiționare a spațiului binar oferă o modalitate viabilă, simplă și eficientă de a verifica dacă punctul care reprezintă caracterul se află sau nu în mediu. Ciocnirile dintre personaje și alte obiecte dinamice sunt luate în considerare și tratate separat.

Un simulator robust de detectare și rezoluție a coliziunilor este unul care va răspunde inteligent la orice intrare. Pe baza abordării a posteriori a detectării coliziunilor, se poate presupune că într-un joc de curse , jucătorul, care accelerează cu viteză mare într-o mașină, se va ciocni de un obstacol, cum ar fi un perete, iar sistemul de detectare a coliziunilor va detecta o coliziune după s-a întâmplat, iar în acel moment mașina va fi deja „cufundată” într-un perete sau chiar „va cădea într-un gol nesfârșit” numit „iad negru”, „iad albastru” sau „iad verde”, în funcție de culoarea dominantă. în motorul grafic . Prin urmare, mecanismul de detectare a coliziunilor a posteriori trebuie să gestioneze corect astfel de situații. Una dintre soluțiile la astfel de situații este conceptul de „detecție continuă a coliziunilor” ( ing. Continuous Collision Detection ). [5]

Note

↑ Ericsson, Christer. Detectarea coliziunilor în timp real. Elsevier, 2005, p. 13.
↑ Ming Chieh Lin . _ Algoritmul Lin-Canny pentru cele mai apropiate caracteristici . UC Berkeley (31 ianuarie 1996). Preluat la 29 iulie 2011. Arhivat din original la 10 martie 2012.
↑ Mătură și prune . GameDev.ru (30 august 2007). — Descrierea algoritmului cu exemple de cod de program. Consultat la 8 iulie 2009. Arhivat din original la 15 octombrie 2012. (Rusă)
↑ Ming Chieh Lin . _ Efficient Collision Detection for Animation and Robotics (teză) (engleză) : jurnal. - Universitatea din California din Berkeley , 1993. (link inaccesibil)
↑ Erwin Coumans. Detectarea coliziunilor continue și fizică (engleză) ( PDF ) (link indisponibil) . Sony Computer Entertainment (august 2005). Preluat la 30 iulie 2011. Arhivat din original la 10 martie 2012.

Link -uri

OZCollide este o bibliotecă gratuită, rapidă și multiplatformă de detectare a coliziunilor.
Site- ul web al Universității din Carolina de Nord la Chapel Hill despre cercetarea de detectare a coliziunilor
Un articol pe site-ul web al profesorului Steven Cameron de la Universitatea din Oxford despre detectarea coliziunilor
Cum să evitați o coliziune - articol de George Beck , Wolfram Demonstrations Project
IvanVR1. Detectare coliziuni (detecție coliziuni) . GameDev.ru (21 iunie 2002). Preluat: 29 iulie 2011. (nedefinit)