Carleton University - School of Computer Science Honours Project
Winter 2017
Comparative analysis of bounding volume hierarchies and grid partitioning for broad phase collision detection
SCS News Image
ABSTRACT
Knowing which method to use when implementing a collision detection system into a game environment can be crucial to the performance of the system. This paper utilized a testing environment to analyze the bounding volume hierarchy and grid partitioning methods of broad phase collision detection to determine which scenarios offer performance enhancements in terms of computational time and amount of memory used. It found that the optimal BVH tree took up much more memory per entity than the grid partition, but offered substantially reduced computation time. For large number of entities (approx. 3000 and up) this computation time reduction was significant, sometimes up to 10 milliseconds while taking up much more memory. However on a small number (approx. 2000 and lower) it saved less than 0.1 milliseconds, while still taking up much more memory. The BVH Tree uses up about 160KB of memory per 1000 entities, while the Grid Partition took up a base cost of 36KB + 8KB for every 1000 entities.