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.
| Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:bth-19623 |
| Date | January 2020 |
| Creators | Björk, Gustav, Wester, Alexander |
| Publisher | Blekinge Tekniska Högskola, Institutionen för datavetenskap |
| Source Sets | DiVA Archive at Upsalla University |
| Language | English |
| Detected Language | English |
| Type | Student thesis, info:eu-repo/semantics/bachelorThesis, text |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0032 seconds