miniatyr|Kolliderande biljardbollar i en virtuell miljö är ett klassiskt exempel på där kollisionsdetektion behövs.
Kollisionsdetektion (engelska: collision detection) är det beräkningsproblem som består i att avgöra om, när och var två eller flera objekt i ett virtuellt rum skär varandra eller kommer i kontakt med varandra. Området är ett klassiskt problem inom datavetenskap och datorgrafik, med tillämpningar inom bland annat fysiksimulering, datorspel, robotik och autonoma system.
Översikt Kollisionsdetektion är nära knuten till beräkning av avstånd mellan objekt. Två objekt kolliderar när avståndet mellan dem blir noll eller negativt, men i praktiska tillämpningar krävs oftast mer information än enbart avstånd, exempelvis kontaktpunkt och tidpunkt för kontakt.
När många objekt förekommer samtidigt blir problemet snabbt beräkningsmässigt kostsamt. En naiv metod kräver att alla objekt jämförs parvis, vilket för objekt ger tester. Därför delas kollisionsdetektion ofta upp i en grov och en fin fas.
Grovfas I grovfasen (broad phase) försöker man snabbt sortera bort objektpar som uppenbart inte kan kollidera. Målet är att minska antalet objekt som måste undersökas med mer exakta metoder.
Rumsuppdelning En vanlig metod är att dela upp rummet i enklare delområden. Om två objekt inte befinner sig i samma delområde behöver de inte testas mot varandra. Exempel på sådana datastrukturer är okträd, quadtree och binär rumsuppdelning.
Omslutande volymer En annan vanlig metod är att omge objekt med förenklade geometriska former, så kallade omslutande volymer (bounding volumes). Om de omslutande volymerna inte skär varandra kan de verkliga objekten inte heller göra det. Vanliga typer är axelparallella begränsningsboxar (AABB), orienterade begränsningsboxar (OBB), klot och k-DOP:er.
Hierarkier av omslutande volymer För komplexa objekt används ofta hierarkier av omslutande volymer (BVH, bounding volume hierarchy). Då organiseras volymerna i en trädstruktur där stora volymer innehåller mindre delvolymer. Genom att traversera trädet kan stora delar av ett objekt snabbt uteslutas från vidare testning.
Finfas Objekt som inte kan separeras i grovfasen går vidare till finfasen (narrow phase), där mer exakta algoritmer avgör om en verklig kollision föreligger och ofta även beräknar kontaktpunkt och kontakttid.
Konvexa objekt För konvexa objekt används ofta algoritmer som bygger på separerande plan eller närmaste-punkt-beräkningar. En av de mest kända är Gilbert–Johnson–Keerthi-avståndsalgoritmen (GJK), som används för att bestämma avstånd eller kollision mellan konvexa kroppar i tre dimensioner.
Deformerbara objekt Kollisionsdetektion blir mer komplicerad när objekten deformeras, exempelvis tyg, mjuka kroppar eller anatomiska modeller i medicinsk simulering. Då måste både yttre kollisioner och självkollisioner hanteras effektivt.
Tillämpningar Kollisionsdetektion används i många områden där virtuella eller simulerade objekt interagerar i rum.
Datorgrafik och fysiksimulering Inom datorgrafik och fysikmotorer används kollisionsdetektion för att förhindra att objekt passerar genom varandra och för att kunna beräkna realistiska stötar, friktion och kontaktkrafter.
Datorspel I datorspel används kollisionsdetektion bland annat för att avgöra när en spelarkaraktär träffar en vägg, ett projektilanfall träffar en motståndare eller ett fordon kolliderar med omgivningen. I realtidsspel kombineras ofta enklare och snabbare metoder med lokalt mer precisa tester för att hålla nere beräkningskostnaden.
Äldre tvådimensionella spel kunde i vissa fall använda hårdvarustöd för att registrera överlappning mellan spritear eller mellan sprites och bakgrundslager. I andra fall räckte det med enklare uppdelning av skärmen och testning med rektanglar eller cirklar kring spelobjekt.
I tredimensionella spel används ofta rumsuppdelning för grov gallring och enklare omslutande volymer för snabba parvisa tester. Exakta kollisionstester används mer sparsamt, särskilt i spel där beräkningskostnaden måste hållas låg.
Eftersom datorspel normalt inte behöver efterlikna verklig fysik exakt används ofta diskreta, efterhandsbaserade metoder för kollisionshantering. Om en figur till exempel hamnar inne i en vägg kan spelmotorn flytta tillbaka figuren till en tidigare giltig position i stället för att lösa kontakten med en fysikaliskt korrekt modell.
Bristfällig kollisionsdetektion kan ge upphov till uppenbara fel i spel, såsom att figurer fastnar i väggar eller passerar genom hinder. Big Rigs: Over the Road Racing har ofta nämnts som ett extremt exempel på detta, eftersom spelet enligt samtida recensioner i praktiken saknade fungerande kollisioner mot flera objekt i spelvärlden.
Träffrutor miniatyr|Exempel på träffrutor i ett fightingspel. Den gröna ytan markerar figurens träffyta, medan den röda markerar attackens träffzon.
En träffruta (engelska: hitbox) är en osynlig geometrisk form som används i realtidsbaserad kollisionsdetektion i datorspel. Den är ofta en rektangel i tvådimensionella spel eller ett rätblock i tredimensionella spel och följer ett synligt objekt, exempelvis en figur eller ett vapen.
I synnerhet i fightingspel skiljer man ofta mellan träffrutor som orsakar skada och sårbarhetsrutor (hurtboxes) som markerar var en figur kan träffas. En attack registreras när attackens träffruta överlappar motståndarens sårbarhetsruta.
Begreppen är dock inte helt standardiserade mellan olika spel och utvecklingsmiljöer. I vissa sammanhang används hitbox som samlingsnamn för flera typer av kollisionszoner.
Robotik Inom robotik används kollisionsdetektion för rörelseplanering, hinderundvikning och manipulering, där det är nödvändigt att avgöra om robotens länkar eller verktyg riskerar att kollidera med omgivningen eller med varandra.
Se även Fysikmotor Datorgrafik Robotik
Referenser
Kategori:Datavetenskap Kategori:Datorgrafik Kategori:Robotik Kategori:Datorspelsteknik Kategori:Datorspelstermer