An investigation of Signed-Volume Gilbert-Johnson-Keerthi algorithm in collision detection

Abstract

Tässä tutkielmassa esitellään Signed-Volume Gilbert-Johnson- Keerthi törmäystarkastelu-algoritmi. Videopelien fysiikkamoottoreiden, törmäystarkatelun yleinen kulku ja GJK - algoritmi itsessään käydään läpi oleellisimmilta osin. Työssä paneudutaan myös esitellyn algoritmin suorittamiseen grafiikkasuorittimella, ja esitellään siihen liittyvät tärkeimmät aiheet, kuten GPGPU ja CUDA SDK. Tutkielmaa varten tehtiin kokeita, joita varten implementoitiin esitettyjen periaatteiden mukainen simulaatio-ohjelmisto CPU ja GPU suoritukseen. Näistä kokeista saadut tulokset esitellään ja niistä keskustellaan. Myös reflektoinnin omaisia huomioita ja keskustelua vastaavanlaisen ohjelmiston implementaatiosta käydään myöhemmissä kappalesissa.

In this thesis, an investigation of the Signed-Volume Gilbert-Johnson-Keerthi collision detection algorithm is presented. The principles of video game physics engines, the general flow of the collision detection process and the GJK algorithm itself, are reviewed. Additionally, running the algorithm with graphics card, and the relevant related topics, such as GPGPU and CUDA SDK, are introduced. A simulation software was implemented for both CPU and GPU following the presented principles, and some experiments were conducted. The results acquired from the tests are discussed. In addition, some self-reflecting notions and discussion about implementing a simulation software for similar experiments, are brought up in later chapters.