Kollisionsdetektion

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 29. oktober 2018; checks kræver 20 redigeringer .

Kollisionsdetektion er et beregningsmæssigt problem med at detektere skæringspunkter mellem to eller flere objekter. Emnet er oftest forbundet med dets brug i fysikmotorer , computeranimation og robotteknologi . Ud over at bestemme, om to objekter er stødt sammen, kan kollisionsdetektionssystemer beregne kollisionstiden og rapportere en kontaktopsamler (sæt af skæringspunkter) [1]. Reaktionen på en kollision (hvad der sker, når en kollision detekteres) afhænger af den særlige proces, der modelleres. Kollisionsdetektionsalgoritmer gør udstrakt brug af koncepter fra lineær algebra og beregningsgeometri. Kollisionsdetektionsalgoritmer er en af hovedkomponenterne i fysikken i tredimensionelle computerspil .

Oversigt

Funktionen af en fysisk model involverer at udføre fysiske eksperimenter, såsom at spille billard . Fysikken ved kolliderende billardkugler er godt beskrevet af faststoffysik og teorien om perfekt elastisk stød . De indledende betingelser er fastsat af billardbordets og kuglernes absolut nøjagtige fysiske egenskaber, samt kuglernes indledende koordinater. I betragtning af stødboldens acceleration ( formodentlig resultatet af en spiller, der slår stødbolden med en stødpind), ønsker vi at beregne de nøjagtige baner for bevægelse, hastighed og stop for alle bolde ved hjælp af et computerprogram. En fysikmotor, der simulerer billard , vil bestå af flere komponenter, hvoraf den ene vil være ansvarlig for nøjagtigt at beregne kollisioner mellem bolde. Denne komponent er et eksempel på en ustabil del af modellen - små fejl i kollisionsberegninger vil føre til væsentlige ændringer i resultaterne - de endelige placeringer af boldene på bordet.

Computerspil har omtrent de samme krav til fysikmotorer, med undtagelse af nogle væsentlige forskelle. Mens simulering af fysiske eksperimenter kræver skabelsen af det mest nøjagtige matematiske apparat, der beskriver den virkelige verden, har computerspil brug for fysik, der kun ser troværdig ud, men samtidig beregnet i realtid , omend groft. Kompromiser er tilladt, så længe det passer spilleren og har acceptabel visuel realisme. Derfor er kroppen, der kontrolleres for kollision - den såkaldte hitbox - enklere end en tredimensionel karaktermodel . Specielt i Team Fortress 2 har karakterer tre hitboxe:

en stor boks (den samme for alle klasser) - for at kontrollere for en kollision med missiler;
om karakteren passerer gennem åbningen - dette bestemmes af en mindre parallelepipedum (også fælles for alle klasser);
at tjekke for kugler - en kombination af parallelepipeder, der groft gentager figuren (hver klasse har sin egen).

Et mere sofistikeret kollisionsdetektionssystem bruges i World of Tanks (og nogle andre militære køretøjssimulatorer). Her anvendes i stedet for en hitbox en polygonal kollisionsmodel af tanken. Det er meget grovere end den visuelle model af et kampkøretøj, men det giver dig mulighed for med tilstrækkelig nøjagtighed at beregne anslagsvinklen på tanken af et projektil, hvilket er vigtigt ved beregning af penetration og / eller rikochet, såvel som påvirkningen af projektiler med hængslede skærme. Et endnu mere sofistikeret kollisionsdetektionssystem bruges i World of Warships . Her beregnes ikke kun kollisionen af et projektil med et skibselement, men også virkningen af virkningerne af et projektiludbrud: fragmenter, en stødbølge, under hensyntagen til placeringen af detaljerne i kollisionsmodellen.

Kollisionsdetektion i fysiksimuleringer

Fysikmotorer adskiller sig i den måde, de reagerer på kollisioner. Nogle bruger materialers fleksibilitet til at beregne den kraft, der er resultatet af en kollision og påvirker resultatet af kollisionen i efterfølgende tidsintervaller, hvilket er ganske beregningsmæssigt dyrt. Nogle modeller beregner den omtrentlige kollisionstid ved hjælp af lineær interpolation, hvorefter de "ruller tilbage" scenens tilstand på et bestemt tidspunkt og beregner kollisionen ud fra lovene om energibevarelse.

Nogle bruger iterativ lineær interpolation ( Newtons metode ) til at beregne kollisionstiden med en meget højere nøjagtighed end resten af beregningerne. Kollisionsdetekteringsmetoden bryder med princippet om tidssammenhæng for at kunne forbedre nøjagtigheden af tidsintervaller uden at øge den samlede belastning af systemets computerressourcer.

Efter en uelastisk kollision kan der forekomme specielle glide- eller hviletilstande, som for eksempel emuleres ved hjælp af begrænsninger i den frie fysikmotor Open Dynamics Engine . Begrænsninger udelukker inerti og som følge heraf ustabilitet. Implementering af hvile i form af en scenegraf undgår forskydninger.

Med andre ord er implementeringer af fysiske modeller normalt opdelt i to veje:

kollisionsdetektion a posteriori ,
a priori tilgang (detektion før kollisionen indtræffer).

Ud over opdelingen i a posteriori og a priori tilgange er næsten alle moderne kollisionsdetektionsalgoritmer opdelt i et hierarki af algoritmer.

Forskelle mellem a posteriori og a priori tilgange

I tilfælde af a posteriori-tilgangen realiseres beregningen af modellen gennem beregning af scenetilstande med korte tidsintervaller, som hver kontrolleres for tilstedeværelsen af skærende objekter eller er placeret så tæt på, at de kan anses for at krydse hinanden . . Ved hvert trin af simuleringen oprettes en liste over krydsende kroppe, positionerne og banerne for disse kroppe "korrigeres" under hensyntagen til kollisionens kendsgerning. Denne tilgang kaldes a posteriori, fordi det umiddelbare nøjagtige øjeblik for kollisionen faktisk er overset og detekteres et stykke tid efter det skete (eller noget tid før, afhængigt af algoritmen).

Med a priori-tilgangen skabes en kollisionsdetektionsalgoritme, der er i stand til at forudsige bevægelsesbanen for fysiske kroppe med høj nøjagtighed. Kollisioner er beskrevet af denne model med høj nøjagtighed, og fysiske kroppe befinder sig i bund og grund aldrig i en tilstand af gensidig penetration. Denne tilgang kaldes a priori, da tidspunkterne for kollisioner af kroppe bestemmes før ændringen i den rumlige konfiguration af objekterne i scenen.

Dens vigtigste fordele stammer fra den a posteriori-tilgang. Algoritmen behøver ikke at manipulere et betydeligt antal fysiske variable - dens input er en simpel liste over fysiske kroppe, resultatet er en delmængde af krydsende kroppe. Algoritmen behøver ikke at håndtere friktionskræfter, elastiske eller endnu værre uelastiske kollisioner og beregner også ændringen i den indre tilstand af deformerbare legemer . Derudover er a posteriori-algoritmen i det væsentlige enklere med én dimension, da man i a priori-tilgangen skal forholde sig til en ekstra akse - tid, som den a posteriori-tilgang er skånet for.

På den anden side fører a posteriori algoritmer til problemer på stadiet med at "korrigere" de indtrængninger af kroppe, der har fundet sted, som ikke forekommer i en virkelig fysisk scene.

Fordelene ved a priori-tilgangen er modellens nøjagtighed og stabilitet. Det er svært (men teoretisk muligt) fuldstændigt at adskille den fysiske komponent af scenemodellen fra kollisionsdetektionsalgoritmen. I de fleste tilfælde, bortset fra de simpleste, har problemet med at forudsige tidspunktet for sammenstød mellem to kroppe ud fra nogle indledende data ikke en generel løsning abstraheret fra resten af modellen. Den numeriske metode til at finde roden bruges.

Nogle kroppe er i en tilstand af hvilekontakt, det vil sige, at de formelt set er i konstant kollision, hvilket ikke fører til frastødende bevægelser af kroppe eller til indtrængning (f.eks. en vase, der står på et bord). I alle tilfælde kræver en kontakt i hvile en exceptionel tilgang: hvis to kroppe kolliderer ("a posteriori") eller glider ("a priori") og deres relative bevægelse er under en vis tærskel, behandles friktion som klæbning, og begge genstande kombineres til en enkelt gren af scenegrafen .

Optimering

De åbenlyse tilgange til kollisionsdetektion for en hel scene med mange objekter er ret langsomme. Det er praktisk muligt at kontrollere, om hvert objekt kolliderer med hvert objekt, men ekstremt ineffektivt med hensyn til beregningsmæssig kompleksitet for et stort antal objekter. Kontrol af objekter med kompleks geometri for tilstedeværelsen af en kollision med hinanden ved en indlysende metode til at kontrollere kollisionen af individuelle ansigter af kroppe er meget dyrt i sig selv. En betydelig mængde forskning på området er således rettet mod at løse præstationsproblemer.

Anvendelse af tidsmæssig sammenhæng

I mange applikationer ændres konfigurationen af fysiske kroppe meget lidt i løbet af den iterative tidsperiode. Mange genstande i scenen bevæger sig slet ikke. Algoritmer er skabt på en sådan måde, at resultaterne af beregningerne foretaget i den foregående iteration bruges i den næste, hvilket fører til en stigning i ydeevnen.

På niveauet for grov kollisionsdetektion er målet at finde objekter, der potentielt kan krydse hinanden. Disse par kræver yderligere analyse. En af disse algoritmer blev udviklet af Ming Chieh Lin fra University of California i Berkeley [2] , som foreslog brugen af metoden til afgrænsningsbokse, hvis kantvektorer er kolineære med basisvektorerne i det kartesiske koordinatsystem, for alle N scenelegemer. Senere blev disse afgrænsningsbokse kendt som den Axis-aligned bounding box (AABB).

Hvert parallelepipedum er repræsenteret af en tripel af segmenter, for eksempel . En almindelig algoritme til at detektere afgrænsningsbokskollisioner er " sweep and prune " -algoritmen [ 3 ] . Det er klart, at to sådanne parallelepipeder og skærer, hvis og kun hvis skærer med , skærer med og skærer med . Det antages, at hvis fra én gang iteration til den næste og skærer hinanden, så er det meget sandsynligt, at de stadig vil skære hinanden ved næste iteration. Også, hvis de ikke krydsede hinanden i den forrige iteration, er det meget sandsynligt, at de ikke krydser hinanden i den næste. $I_1 \times I_2 \times I_3=[a_1,b_1] \times [a_2,b_2] \times [a_3,b_3]$ $I_1 \ gange I_2 \ gange I_3$ $J_1 \ gange J_2 \ gange J_3$ $I_1$ $J_{1}$ $I_{2}$ $J_{2}$ $I_3$ $J_{3}$ $I_{k}$ ${\displaystyle J_{k))$

Så problemet kommer ned til iterativ kontrol fra "ramme" til "ramme", for hvilke af segmenterne krydser hinanden. Der er tre lister over intervaller (en for hver af koordinatakserne), og alle tre af samme længde, da længden af hver er lig med , i henhold til antallet af objekter i scenen og dermed deres afgrænsningsfelter. Hver af listerne svarer til en matrix, hvis elementer er lig med 1 eller 0. - hvis segmenterne og skærer hinanden, og ellers. $n$ ${\displaystyle M_{n\times n))$ $m_{{ij}}$ $m_{ij}=1$ $jeg$ $j$ $m_{ij}=0$

Antag, at matricen forbliver praktisk talt uændret fra den ene iteration til den næste. For at bruge dette er listen over linjesegmenter indeholdt i form af mærkede ekstreme punkter. Hvert element på listen har koordinaterne for yderpunktet og et unikt tal, der identificerer segmentet. Listen er sorteret efter koordinater, og matrixen opdateres i passende rækkefølge. Det er let at verificere, at den angivne algoritme vil give tilstrækkelig høj ydeevne, hvis konfigurationen af afgrænsningskasser ikke ændres væsentligt i én iteration. ${\displaystyle M_{n\times n))$

I tilfælde af deformerbare legemer , såsom gengivelse af en fysisk model af et væv , er der ingen måde at bruge en mere specifik metode - parelimineringsalgoritmen beskrevet nedenfor, og algoritmer, der bruger " n -body pruning"-tilgangen bliver den bedste metode .

Hvis der kan pålægges en maksimal værdibegrænsning på hastigheden af fysiske kroppe i scenen, kan par af objekter fjernes fra listen over kollisionskandidater baseret på deres indledende afstand fra hinanden og størrelsen af tidsiterationstrinnet . $\Delta t$

Parvis reduktion

Efter at et par sceneobjekter er valgt til yderligere undersøgelse, kræves en mere detaljeret kontrol for en kollision. I mange applikationer er nogle af objekterne (hvis deres geometriske konfiguration er relativt konstant, det vil sige, de ikke er udsat for alvorlig deformation) beskrevet af et sæt små primitiver, for det meste trekanter. Det vil sige, at der er to sæt trekanter og (for nemheds skyld antages det, at mængdernes kardinalitet er ens). $S={S_1,S_2,\dots,S_n}$ $T={T_1,T_2,\dots,T_n}$

En oplagt måde at teste kroppe for kollision er at teste alle ordnede trekanter for kollision. Imidlertid er kompleksiteten af en sådan kontrol , hvilket er ekstremt ineffektivt. Det bliver nødvendigt, hvis det er muligt, at bruge en "droppe"-algoritme til at reducere antallet af trekanter, der skal kontrolleres. $(S_{j},T_{k})$ $\operatørnavn{O}(n^2)$

Den mest udbredte familie af algoritmer er den hierarkiske bounding volume- metode . Som et indledende trin beregnes og tildeles for hvert objekt (i vores eksempel er dette og ) et hierarki af afgrænsende objekter. Derefter, ved hver gang iteration, når det er påkrævet at kontrollere for en kollision mellem objekter og , bruges afgrænsningsvolumener til at reducere antallet af trekanter, der falder ind under testen. En af de enkleste typer af afgrænsningsvolumen er en kugle. $S$ $T$ $S$ $T$

For et sæt trekanter kan den afgrænsende kugle beregnes . Der er flere måder at vælge på , det vigtigste er, at kuglen fuldstændigt dækker sættet af trekantede primitiver og samtidig er så lille som muligt. $E$ $B(E)$ $B(E)$ $B(E)$ $B(E)$

Ved bestemmelse af tilstedeværelsen af en kollision af kroppe og , er det muligt først og fremmest at beregne sfærerne og . Det er indlysende, at hvis disse sfærer ikke er gennemskåret, så er både og ikke gennemskåret . Dette er dog ikke meget mere effektivt end n -body beskæringsalgoritmen. $S$ $T$ $B(S)$ $B(T)$ $S$ $T$

Lad være et sæt trekanter. Så kan det deles i to dele: og . På samme måde kan man partitionere og og forudberegne afgrænsningssfærerne og . $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))$

Beregningen er, at disse afgrænsende kugler er meget mindre end og . Og hvis, for eksempel, og ikke skærer, så giver det ingen mening at kontrollere skæringspunkterne mellem trekanter i sættet med trekanter fra . $B(S)$ $B(T)$ $B(S)$ $B(L(T))$ $S$ $L(T)$

I løbet af foreløbige beregninger er det muligt at betragte hvert fysisk legeme repræsenteret som et sæt trekanter og nedbryde det som et binært træ , hvor noderne (knuderne) vil være sæt af trekanter, og deres efterkommere vil være og . For hver knude i dette træ kan afgrænsningssfæren forudberegnes . I et sådant tilfælde, når det bliver nødvendigt at kontrollere kollisionen af det næste par af kroppe, kan deres forudberegnede binære træer af afgrænsende sfærer bruges til at udelukke en væsentlig del fra de trekanter, der skal kontrolleres. $N$ $L(N)$ $R(N)$ $B(N)$

Mange yderligere implementeringer af "træ"-algoritmer opnås ved at vælge andre stereometriske objekter som afgrænsningsvolumener i stedet for sfærer. Ved valg af et parallelepipedum orienteret parallelt med målesystemets akser ( eng. axis-aligned bounding box ) opnås de såkaldte AABB-træer ( eng. AABB-Trees ). OBB træer (eller OOBB træer ) fås ved at bruge en kasse orienteret efter objektets eget koordinatsystem. Nogle af træerne er nemmere at opdatere, hvis hovedobjektet ændres. Nogle træer kan arbejde med højere ordens primitiver såsom splines i stedet for elementære trekanter.

Nøjagtig parvis kollisionsdetektion

Efter at en foreløbig reduktion af par af kandidater til en mulig kollision har fundet sted, er det nødvendigt at foretage en nøjagtig kontrol for tilstedeværelsen af en kollision for hvert resterende par.

Den vigtigste observation er, at for to konvekse ikke-sammenhængende objekter eksisterer der et plan, således at det ene objekt vil ligge helt på den ene side af dette plan, og det andet på den anden. Dette faktum gør det muligt at udvikle hurtige kollisionsdetektionsalgoritmer for konvekse objekter.

Tidligt arbejde på dette område skitserede adskillelsesplanmetoderne . To trekanter støder i det væsentlige kun sammen, når de ikke kan adskilles af et plan, der går gennem tre hjørner. Dette er tilfældet, hvis trekanterne og , hvor hver vektor er i , så kan du vælge tre hjørner - , tegne en plan gennem alle tre og kontrollere, om planet adskiller. Hvis nogen af disse planer adskilles, så skærer trekanterne ikke hinanden; og krydser hinanden, hvis ingen af dem tværtimod skiller. Der er 20 sådanne fly i alt. ${v_{1},v_{2},v_{3))$ ${v_{4},v_{5},v_{6))$ $v_{j}$ $\mathbb R^3$ ${\displaystyle v_{i},v_{j},v_{k))$

Hvis trekanterne er koplanære, vil denne test ikke være fuldstændig vellykket. Du kan dog tilføje planer, for eksempel vinkelret på overfladerne af en trekant, for at løse problemet i det generelle tilfælde. I andre tilfælde skal genstande, der for eksempel rører ved deres kanter, nødvendigvis også møde hjørner et eller andet sted, og derfor skal en generel kollisionsdetektionsmetode kunne løse problemet med kollisionen.

Siden da er der udviklet bedre metoder. I øjeblikket er meget hurtige algoritmer tilgængelige til at finde de nærmeste punkter på overfladen af to konvekse polyedriske legemer. I 1993 brugte M. C. Lin en variation af simpleksmetoden fra lineær programmering i sin afhandling [4] . Efterfølgende erstattede Gilbert-Johnson-Curthy-algoritmen denne tilgang. Disse algoritmer nærmer sig konstant beregningstid, når de anvendes sekventielt på par af stationære eller langsomt bevægende kroppe, når de bruges med indledende data fra en tidligere iteration af kollisionsdetektion.

Resultatet af alle disse fremskridt er evnen til effektivt at registrere kollisioner i realtid for tusindvis af bevægelige kroppe på en typisk personlig computer eller spillekonsol .

A priori klipning

I tilfælde, hvor de fleste af objekterne på scenen er ubevægelige, som det ofte er tilfældet i computerspil, kan a priori-metoder ved hjælp af forberegninger bruges til at fremskynde beregningerne.

I disse situationer er beskæring (dropping) ønskelig: både "n-body pruning" og parvis beskæring. Disse algoritmer tager dog tid at beregne og tage højde for de bevægelsestyper, der bruges i det underliggende fysiske system.

Når det kommer til nøjagtig parvis kollisionsdetektion, bliver algoritmen meget afhængig af banen for de kroppe, der er involveret i kollisionen, og for mindst én krop er det nødvendigt at bruge en numerisk rodfindingsalgoritme til at beregne kollisionsøjeblikket.

Som et eksempel kan du overveje to trekanter, der bevæger sig i tiden: og . På ethvert givet tidspunkt kan disse to trekanter testes for skæring ved hjælp af de tyve planer diskuteret ovenfor. Processen kan dog forbedres, da disse tyve fly kan spores over tid. Hvis det er et fly, der passerer gennem punkterne i , betyder det, at tyve fly er tilgængelige for sporing. Hvert plan skal spores med hensyn til tre hjørner, hvilket giver tres sporingsværdier. Ved at bruge rodopslaget for disse tres funktioner beregnes den nøjagtige kollisionstid for to givne trekanter og for to givne baner. Hvis toppunktbanerne anses for at være lineære polynomier (polynomier) i , så er de sidste tres funktioner kubiske polynomier, og i dette undtagelsestilfælde er det muligt at finde den nøjagtige kollisionstid ved hjælp af formlen for terningrødder. Nogle eksperter i numerisk analyse mener, at brugen af terningerodsformlen ikke er numerisk så stabil som at bruge polynomiumroddannelse. ${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$

Rumlig partitionering

Alternative algoritmer kan grupperes ved, at de bruger rumopdeling , som inkluderer BSP-træer , oktræer og andre lignende metoder . Hvis den anvendte rumlige opdelingsalgoritme opdeler scenen med objekter i et sæt områder, og hvis to objekter er i forskellige områder, kontrolleres de ikke for skæringspunkter. Da BSP-træer kan forudberegnes, er denne tilgang velegnet til håndtering af vægge og andre faste forhindringer i spil. Disse rumopdelingsalgoritmer er generelt ældre end de ovenfor beskrevne algoritmer.

Kollisionsdetektion i computerspil

Computerspil, især konsolspil , skal fordele mange af deres opgaver mellem meget begrænsede hardwareressourcer og meget begrænsede spilprocesudførelsestider. På trods af disse begrænsninger og brugen af relativt primitive og unøjagtige kollisionsdetektionsalgoritmer har spiludviklere været i stand til at skabe visuelt troværdige og relativt realistiske fysikundersystemer.

I temmelig lang tid i computerspil var der et meget begrænset antal objekter, der fysisk interagerede med hinanden, og derfor var det ikke et problem at tjekke alle objekter for kryds. I 2D-spil var hardwaren i nogle tilfælde i stand til effektivt at detektere og rapportere krydsende pixels mellem sprites på skærmen. I andre tilfælde blev effektiv kassering (reduktion) tilvejebragt ved simpel fliselægning (brydning i fragmenter - fliser ) af skærmen og binding af hver sprite til flisen, som den skærer. Afgrænsningskasser og/eller cirkler blev brugt til at kontrollere for parvise skæringspunkter, hvilket blev anset for at være ret nøjagtigt.

3D-spil bruger rumlige opdelingsteknikker til "n-body pruning" og har længe brugt en eller flere afgrænsende sfærer til et enkelt 3D-objekt for at kontrollere parvise skæringspunkter. Nøjagtige kontroller har været meget sjældne, bortset fra spil, der forsøger at efterligne virkeligheden relativt præcist. Men selv i disse tilfælde udføres der ikke altid nøjagtig kontrol for kryds, men kun på de vigtigste steder og/eller situationer set fra spillets synspunkt.

Baseret på det faktum, at spil ikke behøver at efterligne virkeligheden nøjagtigt, er stabilitet ikke kritisk. Næsten alle spil bruger a posteriori kollisionsdetektionsmetoder, og kollisioner løses ofte ved at anvende meget enkle regler. For eksempel, hvis en virtuel karakter "falder gennem" en væg, kan den simpelthen flyttes tilbage til sin sidst kendte "korrekte" position. Nogle spil gør slet ikke kollisionsdetektion, men måler blot den afstand, som karakteren har tilbagelagt, og hvis denne afstand er lig med eller større end en forudbestemt afstand, som karakteren kan gå (f.eks. længden af et rum fra væggen til væg), så forhindre ham i at bevæge sig længere.

I de fleste computerspil er hovedobjekterne for at undgå kollisioner og gennemtrængninger terrænet og miljøet på niveauet - statiske, ikke-interaktive og ikke-nedbrydelige strukturer (bjerge, træer, bygninger, hegn osv.). I dette tilfælde er tegnet repræsenteret af kun et punkt, og den binære rumopdelingsmetode giver en levedygtig, enkel og effektiv måde at kontrollere, om punktet, der repræsenterer karakteren, er i miljøet eller ej. Kollisioner mellem karakterer og andre dynamiske objekter betragtes og håndteres separat.

En robust kollisionsdetektering og opløsningssimulator er en, der vil reagere intelligent på ethvert input. Baseret på den efterfølgende tilgang til kollisionsdetektering kan det antages, at i et racerspil vil spilleren, der accelererer med høj hastighed i en bil, støde ind i en forhindring, såsom en mur, og kollisionsdetektionssystemet vil detektere en kollision efter det er sket, og på det tidspunkt vil bilen allerede være "dykket" ind i en væg eller vil endda "falde ind i et endeløst tomrum" kaldet "sort helvede", "blåt helvede" eller "grønt helvede", afhængigt af den dominerende farve i grafikmotoren . Derfor skal a posteriori kollisionsdetektionsmekanisme håndtere sådanne situationer korrekt. En af løsningerne på sådanne situationer er konceptet "continuous collision detection" ( eng. Continuous Collision Detection ). [5]

Noter

↑ Ericsson, Christer. Kollisionsdetektion i realtid. Elsevier, 2005, s. 13.
↑ Ming Chieh Lin . _ Lin-Canny nærmeste funktioner- algoritme . UC Berkeley (31. januar 1996). Hentet 29. juli 2011. Arkiveret fra originalen 10. marts 2012.
↑ Fej og beskær . GameDev.ru (30. august 2007). — Beskrivelse af algoritmen med eksempler på programkode. Hentet 8. juli 2009. Arkiveret fra originalen 15. oktober 2012. (Russisk)
↑ Ming Chieh Lin . _ Efficient Collision Detection for Animation and Robotics (afhandling) (engelsk) : tidsskrift. - University of California i Berkeley , 1993. (utilgængeligt link)
↑ Erwin Coumans. Kontinuerlig kollisionsdetektion og fysik (engelsk) ( PDF ) (utilgængeligt link) . Sony Computer Entertainment (august 2005). Hentet 30. juli 2011. Arkiveret fra originalen 10. marts 2012.