Dynamic indoor environment modeling using binary space partitioning techniques

Abstract

The gaming industry has been booming partly because of the evolution of games with highly intensive graphics. There are many factors to improve the performance of a game, software algorithms being one of them. There are currently lots of rendering techniques in the market and the aim of this final year project is to review an old but powerful rendering technique using Binary Space Partition (BSP) in a dynamic indoor environment. BSP tree is a data structure that is a hierarchical subdivision of n dimensional space into convex subspaces. [1] BSP is a powerful rendering technique but is only limited to static scene. This is due to the fact that BSP tree is pre‐generated based on a 3D model. Changing the tree structure dynamically is very expensive. The project therefore aims to develop a simulation on a dynamic 3D indoor scene using BSP rendering technique. BSP dynamic changes like changing camera views, collision detection, adding objects and deleting objects were implemented in this project. Intelligent path finding was also implemented to simulate the whole project. C++ programming language was also used to develop the project from scratch. Finally, different types of tests were conducted to evaluate the efficiency of the algorithm that was implemented in the different areas. The results were than discussed and evaluated.