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

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 grafiikkasu...

Full description

Bibliographic Details
Main Author: Koivistoinen, Juha
Other Authors: Informaatioteknologian tiedekunta, Faculty of Information Technology, Informaatioteknologia, Information Technology, Jyväskylän yliopisto, University of Jyväskylä
Format: Master's thesis
Language:eng
Published: 2019
Subjects:
Online Access: https://jyx.jyu.fi/handle/123456789/66828
_version_ 1826225719737319424
author Koivistoinen, Juha
author2 Informaatioteknologian tiedekunta Faculty of Information Technology Informaatioteknologia Information Technology Jyväskylän yliopisto University of Jyväskylä
author_facet Koivistoinen, Juha Informaatioteknologian tiedekunta Faculty of Information Technology Informaatioteknologia Information Technology Jyväskylän yliopisto University of Jyväskylä Koivistoinen, Juha Informaatioteknologian tiedekunta Faculty of Information Technology Informaatioteknologia Information Technology Jyväskylän yliopisto University of Jyväskylä
author_sort Koivistoinen, Juha
datasource_str_mv jyx
description 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.
first_indexed 2019-12-16T21:07:33Z
format Pro gradu
free_online_boolean 1
fullrecord [{"key": "dc.contributor.advisor", "value": "Nieminen, Paavo", "language": "", "element": "contributor", "qualifier": "advisor", "schema": "dc"}, {"key": "dc.contributor.advisor", "value": "Rossi, Tuomo", "language": "", "element": "contributor", "qualifier": "advisor", "schema": "dc"}, {"key": "dc.contributor.author", "value": "Koivistoinen, Juha", "language": "", "element": "contributor", "qualifier": "author", "schema": "dc"}, {"key": "dc.date.accessioned", "value": "2019-12-16T12:09:13Z", "language": null, "element": "date", "qualifier": "accessioned", "schema": "dc"}, {"key": "dc.date.available", "value": "2019-12-16T12:09:13Z", "language": null, "element": "date", "qualifier": "available", "schema": "dc"}, {"key": "dc.date.issued", "value": "2019", "language": "", "element": "date", "qualifier": "issued", "schema": "dc"}, {"key": "dc.identifier.uri", "value": "https://jyx.jyu.fi/handle/123456789/66828", "language": null, "element": "identifier", "qualifier": "uri", "schema": "dc"}, {"key": "dc.description.abstract", "value": "T\u00e4ss\u00e4 tutkielmassa esitell\u00e4\u00e4n Signed-Volume Gilbert-Johnson- Keerthi t\u00f6rm\u00e4ystarkastelu-algoritmi. Videopelien fysiikkamoottoreiden, t\u00f6rm\u00e4ystarkatelun yleinen kulku ja GJK - algoritmi itsess\u00e4\u00e4n k\u00e4yd\u00e4\u00e4n l\u00e4pi oleellisimmilta osin. Ty\u00f6ss\u00e4 paneudutaan my\u00f6s esitellyn algoritmin suorittamiseen grafiikkasuorittimella, ja esitell\u00e4\u00e4n siihen liittyv\u00e4t t\u00e4rkeimm\u00e4t aiheet, kuten GPGPU ja CUDA SDK. Tutkielmaa varten tehtiin kokeita, joita varten implementoitiin esitettyjen periaatteiden mukainen simulaatio-ohjelmisto CPU ja GPU suoritukseen. N\u00e4ist\u00e4 kokeista saadut tulokset esitell\u00e4\u00e4n ja niist\u00e4 keskustellaan. My\u00f6s reflektoinnin omaisia huomioita ja keskustelua vastaavanlaisen ohjelmiston implementaatiosta k\u00e4yd\u00e4\u00e4n my\u00f6hemmiss\u00e4 kappalesissa.", "language": "fi", "element": "description", "qualifier": "abstract", "schema": "dc"}, {"key": "dc.description.abstract", "value": "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,\nare brought up in later chapters.", "language": "en", "element": "description", "qualifier": "abstract", "schema": "dc"}, {"key": "dc.description.provenance", "value": "Submitted by Paivi Vuorio (paelvuor@jyu.fi) on 2019-12-16T12:09:13Z\nNo. of bitstreams: 0", "language": "en", "element": "description", "qualifier": "provenance", "schema": "dc"}, {"key": "dc.description.provenance", "value": "Made available in DSpace on 2019-12-16T12:09:13Z (GMT). No. of bitstreams: 0\n Previous issue date: 2019", "language": "en", "element": "description", "qualifier": "provenance", "schema": "dc"}, {"key": "dc.format.extent", "value": "60", "language": "", "element": "format", "qualifier": "extent", "schema": "dc"}, {"key": "dc.format.mimetype", "value": "application/pdf", "language": null, "element": "format", "qualifier": "mimetype", "schema": "dc"}, {"key": "dc.language.iso", "value": "eng", "language": null, "element": "language", "qualifier": "iso", "schema": "dc"}, {"key": "dc.rights", "value": "In Copyright", "language": "en", "element": "rights", "qualifier": null, "schema": "dc"}, {"key": "dc.subject.other", "value": "GPU", "language": "", "element": "subject", "qualifier": "other", "schema": "dc"}, {"key": "dc.subject.other", "value": "CPU", "language": "", "element": "subject", "qualifier": "other", "schema": "dc"}, {"key": "dc.subject.other", "value": "GJK", "language": "", "element": "subject", "qualifier": "other", "schema": "dc"}, {"key": "dc.subject.other", "value": "GPGPU", "language": "", "element": "subject", "qualifier": "other", "schema": "dc"}, {"key": "dc.subject.other", "value": "collision detection", "language": "", "element": "subject", "qualifier": "other", "schema": "dc"}, {"key": "dc.subject.other", "value": "spatial partition", "language": "", "element": "subject", "qualifier": "other", "schema": "dc"}, {"key": "dc.subject.other", "value": "parallel thinking", "language": "", "element": "subject", "qualifier": "other", "schema": "dc"}, {"key": "dc.subject.other", "value": "physics engine", "language": "", "element": "subject", "qualifier": "other", "schema": "dc"}, {"key": "dc.subject.other", "value": "game engine", "language": "", "element": "subject", "qualifier": "other", "schema": "dc"}, {"key": "dc.subject.other", "value": "video game physics", "language": "", "element": "subject", "qualifier": "other", "schema": "dc"}, {"key": "dc.title", "value": "An investigation of Signed-Volume Gilbert-Johnson-Keerthi algorithm in collision detection", "language": "", "element": "title", "qualifier": null, "schema": "dc"}, {"key": "dc.type", "value": "master thesis", "language": null, "element": "type", "qualifier": null, "schema": "dc"}, {"key": "dc.identifier.urn", "value": "URN:NBN:fi:jyu-201912165320", "language": "", "element": "identifier", "qualifier": "urn", "schema": "dc"}, {"key": "dc.type.ontasot", "value": "Pro gradu -tutkielma", "language": "fi", "element": "type", "qualifier": "ontasot", "schema": "dc"}, {"key": "dc.type.ontasot", "value": "Master\u2019s thesis", "language": "en", "element": "type", "qualifier": "ontasot", "schema": "dc"}, {"key": "dc.contributor.faculty", "value": "Informaatioteknologian tiedekunta", "language": "fi", "element": "contributor", "qualifier": "faculty", "schema": "dc"}, {"key": "dc.contributor.faculty", "value": "Faculty of Information Technology", "language": "en", "element": "contributor", "qualifier": "faculty", "schema": "dc"}, {"key": "dc.contributor.department", "value": "Informaatioteknologia", "language": "fi", "element": "contributor", "qualifier": "department", "schema": "dc"}, {"key": "dc.contributor.department", "value": "Information Technology", "language": "en", "element": "contributor", "qualifier": "department", "schema": "dc"}, {"key": "dc.contributor.organization", "value": "Jyv\u00e4skyl\u00e4n yliopisto", "language": "fi", "element": "contributor", "qualifier": "organization", "schema": "dc"}, {"key": "dc.contributor.organization", "value": "University of Jyv\u00e4skyl\u00e4", "language": "en", "element": "contributor", "qualifier": "organization", "schema": "dc"}, {"key": "dc.subject.discipline", "value": "Tietotekniikka", "language": "fi", "element": "subject", "qualifier": "discipline", "schema": "dc"}, {"key": "dc.subject.discipline", "value": "Mathematical Information Technology", "language": "en", "element": "subject", "qualifier": "discipline", "schema": "dc"}, {"key": "yvv.contractresearch.funding", "value": "0", "language": "", "element": "contractresearch", "qualifier": "funding", "schema": "yvv"}, {"key": "dc.type.coar", "value": "http://purl.org/coar/resource_type/c_bdcc", "language": null, "element": "type", "qualifier": "coar", "schema": "dc"}, {"key": "dc.rights.accesslevel", "value": "openAccess", "language": null, "element": "rights", "qualifier": "accesslevel", "schema": "dc"}, {"key": "dc.type.publication", "value": "masterThesis", "language": null, "element": "type", "qualifier": "publication", "schema": "dc"}, {"key": "dc.subject.oppiainekoodi", "value": "602", "language": "", "element": "subject", "qualifier": "oppiainekoodi", "schema": "dc"}, {"key": "dc.subject.yso", "value": "algoritmit", "language": null, "element": "subject", "qualifier": "yso", "schema": "dc"}, {"key": "dc.subject.yso", "value": "videopelit", "language": null, "element": "subject", "qualifier": "yso", "schema": "dc"}, {"key": "dc.subject.yso", "value": "algorithms", "language": null, "element": "subject", "qualifier": "yso", "schema": "dc"}, {"key": "dc.subject.yso", "value": "video games", "language": null, "element": "subject", "qualifier": "yso", "schema": "dc"}, {"key": "dc.format.content", "value": "fulltext", "language": null, "element": "format", "qualifier": "content", "schema": "dc"}, {"key": "dc.rights.url", "value": "https://rightsstatements.org/page/InC/1.0/", "language": null, "element": "rights", "qualifier": "url", "schema": "dc"}, {"key": "dc.type.okm", "value": "G2", "language": null, "element": "type", "qualifier": "okm", "schema": "dc"}]
id jyx.123456789_66828
language eng
last_indexed 2025-02-18T10:55:13Z
main_date 2019-01-01T00:00:00Z
main_date_str 2019
online_boolean 1
online_urls_str_mv {"url":"https:\/\/jyx.jyu.fi\/bitstreams\/5cb63358-5244-4beb-a160-e7744a936c74\/download","text":"URN:NBN:fi:jyu-201912165320.pdf","source":"jyx","mediaType":"application\/pdf"}
publishDate 2019
record_format qdc
source_str_mv jyx
spellingShingle Koivistoinen, Juha An investigation of Signed-Volume Gilbert-Johnson-Keerthi algorithm in collision detection GPU CPU GJK GPGPU collision detection spatial partition parallel thinking physics engine game engine video game physics Tietotekniikka Mathematical Information Technology 602 algoritmit videopelit algorithms video games
title An investigation of Signed-Volume Gilbert-Johnson-Keerthi algorithm in collision detection
title_full An investigation of Signed-Volume Gilbert-Johnson-Keerthi algorithm in collision detection
title_fullStr An investigation of Signed-Volume Gilbert-Johnson-Keerthi algorithm in collision detection An investigation of Signed-Volume Gilbert-Johnson-Keerthi algorithm in collision detection
title_full_unstemmed An investigation of Signed-Volume Gilbert-Johnson-Keerthi algorithm in collision detection An investigation of Signed-Volume Gilbert-Johnson-Keerthi algorithm in collision detection
title_short An investigation of Signed-Volume Gilbert-Johnson-Keerthi algorithm in collision detection
title_sort investigation of signed volume gilbert johnson keerthi algorithm in collision detection
title_txtP An investigation of Signed-Volume Gilbert-Johnson-Keerthi algorithm in collision detection
topic GPU CPU GJK GPGPU collision detection spatial partition parallel thinking physics engine game engine video game physics Tietotekniikka Mathematical Information Technology 602 algoritmit videopelit algorithms video games
topic_facet 602 CPU GJK GPGPU GPU Mathematical Information Technology Tietotekniikka algorithms algoritmit collision detection game engine parallel thinking physics engine spatial partition video game physics video games videopelit
url https://jyx.jyu.fi/handle/123456789/66828 http://www.urn.fi/URN:NBN:fi:jyu-201912165320
work_keys_str_mv AT koivistoinenjuha aninvestigationofsignedvolumegilbertjohnsonkeerthialgorithmincollisiondetection AT koivistoinenjuha investigationofsignedvolumegilbertjohnsonkeerthialgorithmincollisiondetection