Detta arbete undersöker 4 olika algoritmer som används för bred kollisionsdetektering. De olika metoderna för bred kollisionsdetektering kan delas in i 4 olika kategorier. Algoritmerna som är valda att representera varje kategori är Bruteforce, Sweep and prune, Hierarchical grid och Bounding volume hierarchy. Fokus i arbetet ligger i att mäta deras lämplighet för spelmotorer där det är viktigt att algoritmerna kan köras i realtid. Algoritmerna körs i simulationer av olika miljöer. Där antalet objekt, hur många som är rörliga och objektens distribution varieras mellan miljöerna. I simulationerna mäts tiden det tar för varje algoritm att exekvera per frame. Resultaten av mätningarna visar Hierarchical grid är den bästa av algoritmerna för att hantera stora mängder objekt. Sweep and prune passar bäst för få objekt och Bounding volume hierarchy är ett stabilare alternativ. Resultaten kan användas för att välja en lämplig bredfas algoritm vid implementation av en spelmotor.

Denna studie gick ut på att jämföra tre olika algoritmer som har använts för bred kollisionsdetektering, dessa algoritmer var Kd-tree, Octree och Sweep and prune. Kd-tree och Octree är spatiala datastrukturer, d.v.s. att de hanterar objekt inom specifika volymer. Sweep and prune använder istället listor för att ta reda på om objekt kolliderar. Fokus låg på att se hur stor skillnad algoritmernas exekveringstid hade jämfört med ’brute force’-implementationen och jämfört med varandra. Det utfördes ett antal olika experiment på algoritmerna med ett antal olika inställningar för att kunna utvärdera hur de presterar i olika situationer. Dessa inställningar var t.ex. antalet boids, deras hastighet och hur långt de kunde se. Resultatet visade att Sweep and prune presterade bäst med en liten mängd boids medans de andra algoritmerna kom ikapp och presterade bättre när antalet objekt ökade, då Kd-tree presterade bäst överlag. Studien kan vara till hjälp med att välja vilken bred kollisionsdetekteringsalgoritm som kan tänkas implementeras för en applikation.

This thesis work investigated the advantages and disadvantages of using superquadrics (SQ) to do the collision-checking part of the Rapidly-exploring Random Trees (RRT) motion planning algorithm for higher Degree of Freedom (DoF) motion planning, comparing it with an established proximity querying method known as the Gilbert-Johnson-Keerthi (GJK) algorithm. In the RRT algorithm, collision detection is the main bottleneck, making this topic interesting to research. The SQ-based collision detection method was compared to the GJK algorithm both qualitatively and quantitatively, comparing computational speed, memory requirements, as well as the ability to handle arbitrary shapes. Furthermore, how appropriate they are in modelling a 6 DoF arm was analyzed. A qualitative comparison between the RRT algorithm and the A* algorithm was also provided, comparing their suitability for searching in higher dimensional spaces. When there were no collisions the SQ-based algorithms performed roughly at parity with the GJK algorithm in terms of computational speed. However, when a collision had occurred, the SQ-based algorithms were able to return a positive faster than the GJK algorithm, outperforming it. From a memory standpoint the SQ-based algorithms required less memory as they could leverage the explicit and implicit representations of the SQ objects, whereas the GJK algorithm requires both objects being checked for collision to be explicitly represented as convex sets of points. Regarding handling arbitrary shapes, the SQ-based algorithms have an advantage in that they can allow for certain non-convex shapes to be. Conversely, the GJK algorithm is limited to convex shapes. The GJK algorithm would thus require more geometric primitives to accurately capture the same non-convex shape. Thus, it can be concluded that the SQ-based method is more suitable for modelling a 6 DoF arm. However, a GJK-based collision detection module would in most cases be a lot more straightforward than the alternative to set up, as it is very simple to collect a set of points. Finally, both collision detection method types were implemented with the RRT algorithm. Due to the inherently random nature of the RRT algorithm the results of this set of tests could not be used to make any further conclusions beyond showing that it is possible to combine the SQbased algorithm with the RRT algorithm. Instead, one should see the RRT algorithm as a multiplicative factor applied to the inherent properties of the previously examined collision detection methods. / Detta examensarbete undersökte fördelarna och nackdelarna med att använda n:tegradsytor (NY) för att utföra kollisionsdetektion i algoritmen Raskt-utforskande Slumpmässiga Träd (RST). RST används typiskt för planeringen av system med relativt många frihetsgrader. En etablerad metod för kollisionsdetektion, Gilbert-Johnson-Keerthi-algoritmen (GJK), implementerades även i jämförelsesyfte. Då GJK-algoritmens största flaskhals ligger i kollisionsdetektionen är detta ett intressant ämne att efterforska. Den NY-baserade kollinsdetektionsmetoden jämfördes med den GJK-baserade metoden både kvantitativt och kvalitativt. Kvalitativt jämfördes beräkningshastighet och minnesåtagande, medan de kvalitativt jämfördes i deras förmåga att representera godtyckliga geometriska former. På ett högre plan diskuterades det även hur lämpliga de är för att modellera en robotarm med 6 stycken frihetsgrader. RST-algoritmen jämfördes även med en annan planeringsalgoritm, A*. Framförallt fokuserade diskussionen kring planering av system med relativt många frihetsgrader. I det fall inga kollisioner fanns presterade GJK-algoritmen ungefär lika bra som NY algoritmerna i att fastslå detta, utifrån beräkningshastighet. Men när det kom till att upptäcka existerande kollisioner presterade GJK-algoritmen sämre. Minnesmässigt använder GJK-algoritmen mer minne, då den kräver att båda objekten är explicitrepresenterade (dvs, som ett punktmoln), medan man med en NY-metod endast behöver representera ena objektet explicit och den andra implicit. Gällande förmågan att representera godtyckliga geometriska former är NY-baserade metoder bättre. Till skillnad från GJK som är begränsad till konvexa mängder kan NY uppta ickekonvexa former, exempelvis flottyrmunkformade supertoroider. En metod som använder GJKalgoritmen skulle behöva bygga upp icke-konvexa former med flera mindre konvexa komponenter. NY-metoden är således bättre för att modellera robotarmar med 6 frihetsgrader. Det är dock i praktiken lättare att implementera GJK-metoden då den endast kräver punktmoln, medan NY kräver parametrar som måste bestämmas eller finjusteras. RST-algoritmen implementerades sist, utformad så att kollisionsdetektionsmetoderna är utbytbara. Det var dock inte möjligt att dra slutsatser utifrån det testdata som erhölls, ty RSTalgoritmens slumpmässiga karaktär. RST-algoritmen kan ses som en multiplikator som endast förstorar de inneboende egenskaperna hos kollisionsdetektionsmetoderna.

Detta examensarbete har undersökt möjligheterna att kombinera multi-master databasreplikeringstekniker tillsammans med en LEMP-stack på små servrar för att öka tillgängligheten av e-Learning tjänster i avlägsna områden i Tanzania. Målet var att utvärdera kombinationen av Symmetric DS för databas synkronisering och kollitionsdetektering och resolution med e-Learning systemet Moodle. Detta gjordes genom att en litteraturstudie genomfördes och uppföjdes av implementation och konfiguration på plats i Tanzania. Slutsatsen var att de för projektet utvalda teknologierna, mjukvaran och hårdvaran var konfigurerbar i teorin men ohållbart kostsam att implementera i praktiken. / This research has investigated the possibility to combine multi-master database replication technologies together with a LEMP-stack on tiny servers to increase the availability of e-Learning services in remote areas in Tanzania. The aim was to evaluate the combination of Symmetric DS for multi master database replication and conflict detection and resolution with the e-learning system Moodle. This was done by conducting a literature study of relevant technologies followed by implementation and configuration at the location. The conclusion was that the technologies, software and hardware chosen for the project were configurable in theory but not viable to implement and maintain in practice.

Background. Neural Networks have mainly been used in behavior and gameplayrelated areas in games, but they have not yet been used specifically for intersection testing. This thesis explores the possibility to use deep neural networks for intersection testing of two 3D meshes. Objectives. The main goal of the thesis is to train a Deep Neural Network that can be used to replace traditional intersection test algorithms by having similar accuracy and a faster execution time. Methods. The research methods used in this thesis are implementation and experimentation. The deep neural network is trained using TensorFlow. Two different mesh generation techniques are implemented, one generating heightmaps and one generating planets. The two mesh types are combined to test all combinations of generated meshes. Attempts to make the network as general as possible are done through importance sampling to expose the network to tricky situations. A test application is developed where the intersection testing can be performed and compared to the Separating Axis Theorem (SAT). Heatmaps are also created to see how accurate the network is. Results. The results show that the network is accurate at classifying intersection between meshes similar to the ones it trained on. However, the network lacks generality and has bad accuracy if new meshes are introduced. The measured execution times show that the trained Deep Neural Network is 15.6 times as fast as a singlethreaded implementation of the SAT and 2.3 times as fast as the multi-threaded SAT. Conclusions. The trained network can be used as an early exit intersection test before using more expensive algorithms. The faster intersection testing can be useful in game physics by allowing faster classification of which meshes need to be tested for collisions. However, the main outcome is the shown potential for future work in the area including training a more general network, allowing variable mesh sizes, and providing information for solving collision responses. / Bakgrund. Neurala Nätverk har främst använts för beteende- och spelmekanikrelaterade områden inom spel, men de har ännu inte använts för genomskärningstester. Det här examensarbetet utförskar möjligheten att använda djupinlärning för att utföra genomskärningstester mellan två tredimensionella spelobjekt. Syfte. Huvudmålet med det här examensarbetet är att träna ett djupinlärt neuralt nätverk som kan ersätta traditionella genomskärningstestalgoritmer genom likvärdig precision och snabbare exekveringstid. Metod. Forskningsmetoderna som användes under examensarbetet är implementation och experimentation. Det djupinlärda neurala nätverket tränas med TensorFlow. Två olika spelobjektsgenereringsmetoder implementeras, där den ena genererar heightmaps och den andra genererar planeter. De två objekttyperna kombineras så att alla kombinationer av spelobjekt kan testas. För att göra nätverket så generellt som möjligt används importance sampling som utsätter nätverket för svåra situationer. Ett testprogram utvecklas där genomskärningstester kan utföras och jämföras mot Separating Axis Theorem (SAT). Grafer av typen heatmaps skapas också för att visa hur hög precision nätverket har. Resultat. Resultaten visar att nätverket har hög precision vid klassificering av spelobjekt liknande de som den tidigare har tränat på. Nätverket har sämre precision när nya spelobjekt introduceras. De uppmätta exekveringstiderna visar att det neurala nätverket är 15.6 gånger så snabbt som singeltrådade implementationen av SAT och 2.3 gånger så snabbt som den flertrådade SAT-implementationen. Slutsatser. Det tränade nätverket kan användas som ett tidig avbrott innan en dyrare algoritm används. Den snabbare genomskärningstestningen kan vara användbar i spelfysik eftersom den tillåter snabbare klassificering av vilka spelobjekt som behöver testas för kollision. Det huvudsakliga utfallet är den visade potentialen för vidare forskning inom området vilket inkluderar träning av ett mer generellt nätverk, möjlighet att variera spelobjektens storlek samt ge information för att kunna lösa kollisioner.