Cum funcționează detectarea coliziunilor / obiectelor 3D? (Programare, Algoritm, Structuri De Date, 3D, Detectarea Coliziunii)

jmasterx a intrebat.

Întotdeauna m-am întrebat acest lucru. Într-un joc precum GTA în care există zeci de mii de obiecte, cum știe jocul de îndată ce te afli pe un pachet de sănătate?

Nu se poate să existe un ascultător de evenimente pentru fiecare obiect? Nici iterația nu este bună? Mă întrebam doar cum se face de fapt.

Comentarii

  • Bună întrebare! Știu multe despre structurile individuale de nivel scăzut și metodele de programare a jocurilor, dar de multe ori m-am întrebat cum sunt puse toate împreună. –  > Por RBarryYoung.
6 răspunsuri
charstar

Nu există un răspuns unic la acest lucru, dar lumile mari sunt adesea împărțite în spațiu prin utilizarea a ceva de genul quadtree sau kd-tree ceea ce aduce timpii de căutare pentru găsirea celor mai apropiați vecini sub timpul liniar (putere fracționară, sau în cel mai rău caz O( N^(2/3) ) pentru un joc 3D). Aceste metode sunt adesea denumite BSP pentru partiționarea spațială binară.

În ceea ce privește detectarea coliziunilor, fiecare obiect are, de asemenea, în general, o volum delimitat mesh (set de poligoane care formează o coajă convexă) asociat acestuia. Aceste ochiuri de plasă foarte simplificate (uneori doar un cub) nu sunt desenate, dar sunt utilizate în detectarea coliziunilor. Cea mai rudimentară metodă constă în crearea unui plan perpendicular pe linia care leagă punctele mediane ale fiecărui obiect cu planul care intersectează linia în punctul median al acesteia. În cazul în care volumul delimitat al unui obiect are puncte de ambele părți ale acestui plan, este vorba de o coliziune (trebuie doar să testați unul dintre cele două volume delimitate în raport cu planul). O altă metodă este cea îmbunătățită GJK îmbunătățit. Dacă doriți un tutorial pe care să îl parcurgeți, consultați Lecția de OpenGL #30 de la NeHe Productions.

De altfel, volumele delimitate pot fi utilizate și pentru alte optimizări, cum ar fi ceea ce se numește interogări de ocluzie. Acesta este un proces de determinare a obiectelor care se află în spatele altor obiecte (ocluzatori) și, prin urmare, nu trebuie procesate/prestate. Volumele de delimitare pot fi, de asemenea, utilizate pentru eliminarea frusturilor care este procesul de determinare a obiectelor care se află în afara volumului de vizualizare a perspectivei (prea aproape, prea departe sau dincolo de unghiul câmpului vizual) și care, prin urmare, nu trebuie să fie redate.


După cum a menționat Kylotan, utilizarea unui volum delimitat poate genera rezultate fals pozitive atunci când se detectează ocluzia și pur și simplu nu funcționează deloc pentru anumite tipuri de obiecte, cum ar fi toroizii (de exemplu, privirea prin gaura unei gogoși). Obținerea corectă a ocluziei obiectelor de acest tip este un alt subiect pe portal-culling.

Comentarii

  • +1. În anii ’80 am făcut modelare 3D pentru arhitecți și a trebuit să folosim toate trucurile de optimizare de sub soare pentru a le face să funcționeze în timp rezonabil pe PC-urile din acea epocă. Aceste două abordări erau foarte sus pe listă. –  > Por Joe Mabel.
  • Un răspuns excelent! Tocmai am început să implementez niște chestii de joc pe cont propriu (vezi aici: stackoverflow.com/questions/1916259/…), iar volumele delimitate au fost una dintre ideile care mi-au venit pentru a prefiltra foarte costisitoare de detectare a coliziunilor. Nici măcar nu mi-a trecut prin cap că aș putea să o reutilizez pentru detectarea ocluziei. Aceasta este o imensă ajutor! –  > Por RBarryYoung.
  • Problema cu utilizarea volumelor de delimitare grosiere pentru ocluzie este că, uneori, veți obține rezultate fals pozitive (de exemplu, crezând că un obiect este ascuns de cilindrul de delimitare al unui om, când, de fapt, ar trebui să îl puteți vedea prin picioarele și peste umerii lui). Într-adevăr, volumul de ocluzie care face autoritate ar trebui să fie mai mic decât obiectul în cauză –  > Por Kylotan.
  • +1 la comentariul lui Kylotan. Absolut adevărat. Pot să încerc să clarific mai bine acest lucru. –  > Por charstar.
  • Volumul delimitat grosier vă oferă doar o primă aproximație: apoi trebuie de fapt să să faci comparație. Dar înseamnă că poți elimina ieftin o mulțime de lucruri care nici măcar nu sunt aproape unul de celălalt, pentru a nu fi vreodată examinate îndeaproape (și costisitor). –  > Por Joe Mabel.
joshperry

Quadtrees și Octrees, un alt quadtree, sunt modalități populare, folosind partiționarea spațiului, pentru a realiza acest lucru. Exemplul de mai târziu arată o reducere cu 97% a procesării față de o căutare brutală pereche cu pereche pentru coliziuni.

Celion

O tehnică comună în motoarele de fizică a jocurilor este metoda „sweep-and-prune”. Aceasta este explicată în notele lui David Baraff de la SIGGRAPH (a se vedea capitolul Motion with Constraints). Havok folosește cu siguranță această metodă, cred că este o opțiune în Bullet, dar nu sunt sigur de PhysX.

Ideea este că vă puteți uita la suprapunerile AABB-urilor (casetele de delimitare aliniate pe axă) pe fiecare axă; dacă proiecția AABB-urilor a două obiecte se suprapun pe toate cele trei axe, atunci AABB-urile trebuie să se suprapună. Puteți verifica fiecare axă relativ rapid prin sortarea punctelor de început și de sfârșit ale AABB-urilor; există o mare coerență temporală între cadre, deoarece, de obicei, majoritatea obiectelor nu se mișcă foarte repede, astfel încât sortarea nu se schimbă prea mult.

Odată ce sweep-and-prune detectează o suprapunere între AABB-uri, puteți face o verificare mai detaliată a obiectelor, de exemplu, sferă vs. cutie. În cazul în care verificarea detaliată relevă o coliziune, puteți rezolva coliziunea prin aplicarea de forțe și/sau declanșa un eveniment de joc sau reda un efect sonor.

kingchris

Corect. În mod normal, nu există un ascultător de evenimente pentru fiecare obiect. Adesea există o structură arborescentă non-binară în memorie care imită harta jocurilor dvs. Imaginați-vă o hartă de metrou / subterană. această structură de memorie este o colecție de lucruri din joc. Tu, jucătorul, monștrii și obiectele pe care le poți ridica sau obiectele care ar putea să explodeze și să-ți facă rău. Astfel, pe măsură ce jucătorul se deplasează în joc, pointerul obiectului jucătorului este mutat în structura de memorie a jocului/mapei.

a se vedea Cum ar trebui ca entitățile jocului meu să cunoască lucrurile din jurul lor?

wojakzek

Aș dori să vă recomand cartea solidă a lui Christer Ericson despre detectarea coliziunilor în timp real. Aceasta prezintă elementele de bază ale detectării coliziunilor, oferind în același timp referințe privind eforturile de cercetare contemporane.

Real-Time Collision Detection (The Morgan Kaufmann Series in Interactive 3-D Technology)

user224564

Se pot folosi o mulțime de optimizări. în primul rând – orice obiect (să zicem cu indicele i, de exemplu) este delimitat de un cub, cu coordonate centrale CXi,CYi, și dimensiunea SiÎn al doilea rând – detectarea coliziunii funcționează cu estimări:

a) Găsiți toate perechile de cuburi i,j cu condiția: Abs(CXi-CXj)<(Si+Sj) AND Abs(CYi-CYj)<(Si+Sj)

b) Acum se lucrează numai cu perechile obținute în a). Calculăm distanțele dintre ele mai precis, ceva de genul Sqrt(Sqr(CXi-CXj)+Sqr(CYi-CYj))În acest moment, obiectele sunt reprezentate ca seturi de câteva numere de figuri simple – cuburi, sfere, conuri – și folosim formule geometrice pentru a verifica intersecțiile acestor figuri.

c) Obiectele de la punctul b) cu intersecții detectate sunt procesate ca și coliziuni, cu calcularea fizică etc.

utilizator3396151

Comentarii

  • Răspuns bun. Mulțumesc pentru includerea formulelor practice. –  > Por RBarryYoung.