Ny simuleringsteknik kan effektivisera datorgrafik och visualisering
Ett problem i tillämpningar inom datorgrafik och visualisering är hur kollisioner ska hanteras då objekt kommer i kontakt med varandra på dataskärmen. I en licentiatavhandling från Mälardalens högskola beskrivs nya metoder för att upptäcka kollisioner mellan kroppar i rörelse och för ray tracing av deformerbara modeller.
Avhandlingen, “Adaptive Algorithms for Collision Detection and Ray Tracing of Deformable Meshes”, är skriven av Thomas Larsson, doktorand vid Institutionen för Datavetenskap. Ett av institutionens profilområden är spelutveckling och interaktiva miljöer.
Inom datorgrafik och visualisering finns det många tillämpningar som bygger på realtidssimulering av olika förlopp, där objekten är geometriska modeller internt i datorn, men som på skärmen föreställer bestämda föremål, industriprocesser, människor eller något annat.
Ett återkommande problem är alltså vad som händer då objekt kolliderar. En kollision behöver inte vara en olycka eller ett misstag, det kan vara en önskvärd handling i ett dataspel eller i en simulering av t ex en operation där man vill följa kollisionen som kanske är när kirurgens kniv går igenom vävnaden.
Om inte särskilda åtgärder vidtas passerar modellerna rakt igenom varandra som om kollisionen, mötet mellan figurerna på skärmen, inte hade hänt. Om vi tar exemplet med kirurgen så är detta naturligtvis en stor brist att simuleringen inte efterliknar verkligheten.
Simuleringssystemet måste därför kunna avgöra vilka delar av modellerna som är i kontakt med varandra och vidta lämpliga åtgärder med hänsyn till modellernas egenskaper och rörelser.
I vissa tillämpningar vill man undvika de verkliga krockarna och därför simulerar man för att fastställa säkra krockfria rörelsebanor för objekt. Ett bra exempel på detta är simulering av en robots rörelse för att utföra ett visst arbete. Men roboten måste också kunna greppa tag om saker och förflytta dem vilket är en form av önskad kollision eller kontakt mellan modeller.
Eftersom modellerna, som ligger till grunden för tillämpningen, kan vara uppbyggda av hundratusentals geometriska element krävs det mycket effektiva metoder för att lokalisera dem som är inblandade i en viss kollision. För att klara detta krävs det datastrukturer och algoritmer som möjliggör effektiv sökning efter kontaktytor.
I många tillämpningsområden krävs dessutom att modellerna ska kunna ändra form under simuleringens gång, till exempel inom animering eller virtuell kirurgi. Detta utgör en extra utmaning, eftersom de datastrukturer som används i dessa fall måste uppdateras i betydligt större omfattning än då enbart stela kroppar används.
Även inom interaktiv ray tracing uppkommer ett liknande problem. Ray tracing är en metod för att generera realistiska syntetiska bilder av tredimensionella scener eller världar som representeras av geometriska modeller. Metoden bygger på att färdvägen för miljontals ljusstrålar beräknas från betraktarens öga och baklänges ut i scenen som ska visas på skärmen. För att kunna göra detta måste de geometriska element som strålarna skär lokaliseras på ett effektivt sätt.
I avhandlingen beskrivs nya metoder för att upptäcka kollisioner mellan kroppar i rörelse och för ray tracing av deformerbara modeller. De lösningar som föreslås är baserade på hierarkier av omgivande volymer som representerar modellerna.
Modellerna, i sin tur, representeras av polygoner som är ihopkopplade och de tillåts att ändra sin form genom att polygonernas hörnpunkter kan förflyttas godtyckligt. Olika metoder för att uppdatera hierarkierna då modellerna deformeras föreslås och utvärderas i avhandlingen.
För att undvika onödigt arbete, och därigenom vinna prestanda, föreslås bland annat ett sätt att senarelägga uppdateringar tills det visar sig absolut nödvändiga att utföra dem. Resultaten från de experiment som har utförts visar att de nya metoderna kan leda till avsevärda prestandaförbättringar jämfört med tidigare föreslagna metoder.
En ny metod för kollisionsdetektering mellan modeller som deformeras med hjälp av så kallad morphing presenteras också i avhandlingen. I detta mer specifika fall kan en särskild form av datastrukturer skapas som gör det möjligt att beräkna kontaktytor mellan kropparna med motsvarande prestanda som för helt stela kroppar.
Avhandlingen presenteras vid ett licentiatseminarium vid Mälardalens högskola.
Tid och plats: Måndag 3/11 kl 14.00, Mälardalens högskola, Sal V262, Vargens Vret, Norra Ringvägen, Västerås.
Kontaktinformation
Thomas Larsson nås via mail thomas.larsson@mdh.se eller telefon 021-10 15 14, 070-456 49 44.
