Detekcija kolizija

master's thesis

• Author: Ana Parać
• Mentor: Mladen Jurak (mentor)
• Committee member: Mladen Jurak (predsjednik povjerenstva)
• Committee member: Marko Vrdoljak (član povjerenstva)
• Committee member: Nenad Antonić (član povjerenstva)
• Committee member: Sonja Štimac (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2020-02-28, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

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.

Abstract (english)

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.

• Keywords: računalne igre; virtualna stvarnost; robotika; kolizija; tuneliranje; C++; Box2D; Sfml
• Keywords (english): computer games; virtual reality applications; robotics; collision; tunneling; C++; Box2D; Sfml
• Language: croatian
• URN:NBN: urn:nbn:hr:217:322782
• Study programme: Title: Computer Science and Mathematics; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra računarstva i matematike (magistar/magistra računarstva i matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2020-09-21 11:10:56