A Deep Neural Network Approach for Intersection Testing of Two 3D Meshes

Sammanfattning: 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.