Detekcija kolizija

diplomski rad

• Autor: Ana Parać
• Mentor: Mladen Jurak (mentor)
• Član povjerenstva: Mladen Jurak (predsjednik povjerenstva)
• Član povjerenstva: Marko Vrdoljak (član povjerenstva)
• Član povjerenstva: Nenad Antonić (član povjerenstva)
• Član povjerenstva: Sonja Štimac (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Prirodoslovno-matematički fakultet; (Matematički odsjek); Zagreb
• Datum i država obrane: 2020-02-28, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

U ovom radu proučavamo jedan od najvažnijih problema u računalnim igrama koji pronalazimo i u brojnim drugim domenama kao što su aplikacije virtualne stvarnosti i robotika. Započinjemo s razmatranjem jednostavnih testova. Zbog uočenih ograničenja jednostavnih testova, uvodimo metodu razdvajajućih osi koja rezultira mogućnošću ispitivanja kolizije na svim konveksnim objektima. Opisujemo njezinu primjenu te navodimo njezine prednosti. Zatim izlažemo primjere algoritama za utvrđivanje kolizije bazirane na metodi razdvajajućih osi te uz to proučavamo pridruženi problem utvrđivanja kontaktnih skupova. Prethodno opisane algoritme proširujemo na 3D objekte te na slučajeve kada se objekti kreću konstantnom linearnom brzinom. Nadalje proučavamo problem tuneliranja te njegova potencijalna rješenja. Peto poglavlje posvećujemo promatranju problem testiranja kolizije na nekonveksnim objektima i konveksnim objektima izrazito velike složenosti koji zahtijevaju izgradnju posebnih struktura, tzv. graničnih oblika. Uz to, govorimo o nekoliko mogućih optimizacija preciznosti i brzine algoritama. Naposljetku demonstriramo rad navedenih algoritama izradom programa u C++-u uz korištenje biblioteka Box2D za fiziku igre te Sfml za izradu grafike.

Sažetak (engleski)

In this thesis, we study one of the most important issues occurring in computer games, which can also be found in many other domains, such as virtual reality applications and robotics. We begin by reviewing simple tests. Due to the observed limitations of simple tests, the method of separating axes is introduced, which results in the possibility of collision testing on all convex shapes. We explain the application of the method, and list its strengths. Furthermore, we present the appropriate collision detection algorithms based on the separating axis theorem, and we examine the associated problem of contact sets determination. We extend the algorithms to 3D objects and to cases where objects are moving at constant linear velocity. Moreover, we analyse the problem of tunneling and its potential solutions. The fifth chapter deals with the problem of collision testing on non-convex objects and convex objects of extremely high complexity, which require the construction of a special structure, the so-called bounding boxes. In addition, we discuss several possible optimizations in order to improve the precision and speed of the algorithms. Finally, we demonstrate the effectiveness of the algorithms by creating a program in C++, using the Box2D library for the game physics and Sfml for the game graphics.

• Ključne riječi: računalne igre; virtualna stvarnost; robotika; kolizija; tuneliranje; C++; Box2D; Sfml
• Ključne riječi (engleski): computer games; virtual reality applications; robotics; collision; tunneling; C++; Box2D; Sfml
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:322782
• Studijski program: Naziv: Računarstvo i matematika; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra računarstva i matematike (mag. inf. et math.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2020-09-21 11:10:56