Konzeption und vergleichende Evaluierung von Algorithmen zur Kollisionserkennung im Kontext von dynamischen, gekoppelten Simulationen

In this bachelor thesis existing approaches for collision detection are described, analyzed and improved. For that purpose the procedure of collision detection with a Distance Prism Hierarchy and the procedure of collision detection by Spatial Hashing have been examined in a cloth simulator. Different implementations of these algorithms were tested. Thus for the Spatial Hashing the runtime of an implementation by HashMaps was compared with arrays and an implementation by HashSets was compared with lists. Also a reverse Spatial Hashing was tested. Besides optimization methods for the collision detection process were designed, implemented and investigated. For that purpose redundant and unnecessary calculations were eliminated and the collision information of the preceding simulation step was used. Furthermore the performance of the actualization of the required data structures was analyzed and improved. To do this, a procedure called Lazy Update has been developed. It reduces calculations in the update process of the data structure, while approximated states are admitted. Special attention was paid to the fact, that no negative visual effects arise by the use of this procedure and no redundant calculations occur. Also a Required Update procedure was conceived to eliminate calculations in a simulation step, whose results are not used in the current step. In the analysis these compiled procedures showed great accelerations of the algorithms