Törmäyksen tunnistus 3D-ympäristössä
Huotari, Marko (2011)
Julkaisun pysyvä osoite on
https://urn.fi/URN:NBN:fi:amk-201103253578
https://urn.fi/URN:NBN:fi:amk-201103253578
Tiivistelmä
Tämä työ keskittyi tutkimaan kuinka kahden kappaleen törmäys havaitaan 3D-ympäristössä.
Törmäyksen tunnistaminen on usean ongelman kokonaisuus esim. malleissa saattaa olla kymmeniä tuhansia polygoneja, jolloin kappaleiden törmäyksen tunnistus polygoneista laskettuna on yleensä laskennallisesti mahdotonta. Yleinen käytäntö on rakentaa mallin ympärille peite, jolle törmäyksen tunnistus tehdään.
Ympäröivä peite on jokin tunnettu geometrinen kappale, joka sisältää kaikki mallin pisteet esim. pallo, laatikko tms. Ympäröivät peitteet ovat olennainen osa törmäyksen tunnistusta ja tästä syystä tämä työ jakaantui kahteen osaan. Ensimmäinen osa käsittelee ympäröiviä peitteitä ja toinen osa törmäystapahtuman tunnistusta.
Ympäröivistä peitteistä käsiteltiin orientoitunut laatikko ja konveksi peite. Orientoitunut laatikko on laatikko, jonka orientaatio kuvaa mallin tai pistejoukon orientaatiota, jonka ympärille se on määrätty. Orientoitunut laatikko määrättiin tässä työssä pääkomponentti analyysin avulla. Konveksi peite on pienin mahdollinen konveksi kappale joka voidaan määrätä pistejoukon ympärille. Tässä työssä on esitetty algoritmi konveksi peitteen määräämiseen.
Törmäyksen tunnistus keskittyi tässä työssä ongelmaan, jos käytössä on useita erilaisia ympäröiviä peitteitä esim. pallo, laatikko tms. tarvitaanko jokaiseen tilanteeseen oma algoritmi vai onko olemassa algoritmeja, jotka havaitsevat törmäyksen erilaisilla kappaleilla. Algoritmit jotka tässä työssä esiteltiin, ovat Gilber-Johnson-Keerthi (GJK) ja Chung-Wang. Molemmat algoritmit havaitsevat törmäyksen mielivaltaisilla konvekseilla kappaleilla ja molemmat perustuvat Minkowskin erotukseen.
Törmäyksen tunnistaminen on usean ongelman kokonaisuus esim. malleissa saattaa olla kymmeniä tuhansia polygoneja, jolloin kappaleiden törmäyksen tunnistus polygoneista laskettuna on yleensä laskennallisesti mahdotonta. Yleinen käytäntö on rakentaa mallin ympärille peite, jolle törmäyksen tunnistus tehdään.
Ympäröivä peite on jokin tunnettu geometrinen kappale, joka sisältää kaikki mallin pisteet esim. pallo, laatikko tms. Ympäröivät peitteet ovat olennainen osa törmäyksen tunnistusta ja tästä syystä tämä työ jakaantui kahteen osaan. Ensimmäinen osa käsittelee ympäröiviä peitteitä ja toinen osa törmäystapahtuman tunnistusta.
Ympäröivistä peitteistä käsiteltiin orientoitunut laatikko ja konveksi peite. Orientoitunut laatikko on laatikko, jonka orientaatio kuvaa mallin tai pistejoukon orientaatiota, jonka ympärille se on määrätty. Orientoitunut laatikko määrättiin tässä työssä pääkomponentti analyysin avulla. Konveksi peite on pienin mahdollinen konveksi kappale joka voidaan määrätä pistejoukon ympärille. Tässä työssä on esitetty algoritmi konveksi peitteen määräämiseen.
Törmäyksen tunnistus keskittyi tässä työssä ongelmaan, jos käytössä on useita erilaisia ympäröiviä peitteitä esim. pallo, laatikko tms. tarvitaanko jokaiseen tilanteeseen oma algoritmi vai onko olemassa algoritmeja, jotka havaitsevat törmäyksen erilaisilla kappaleilla. Algoritmit jotka tässä työssä esiteltiin, ovat Gilber-Johnson-Keerthi (GJK) ja Chung-Wang. Molemmat algoritmit havaitsevat törmäyksen mielivaltaisilla konvekseilla kappaleilla ja molemmat perustuvat Minkowskin erotukseen.