Using voxelised spaces for the generation and visualisation of dynamic evacuation routes

Abstract

In the modern world, evacuating a building in a safe and orderly manner remains a challenge. Fire-based emergencies in a building are dynamic environments that can be simulated to better understand, analyse, and contribute to safer and smarter buildings. While different spatial representations exist, voxels provide a structured, flexible and efficient 3-dimensional grid for applications like analysis, classification, surface reconstruction and simulation. Furthermore, voxels implicitly contain topological and spatial relations that are relevant for 3-dimensional events such as evacuations in a rapidly changing building, with a fire spanning multiple floors.

Voxels can suffer from the problem of scale and resolution, where high resolution voxel scenes take up a lot of memory space. For this, there are solutions that make more efficient data storage for voxels possible. These include but are not limited to: the regular voxel grid, the sparse voxel octree, directed acyclic graphs and the use of space filling curves. Finding the shortest safe path for the evacuees is a challenge, especially if the area is dynamic, and there are other actors that have to share the space. Many different pathfinding algorithms exist, each with their own speciality, such as A*, any-angle pathfinding algorithms like Theta* and incremental algorithms like D*-Lite. 

In this thesis, we look at whether voxelised indoor spaces can form the basis for evacuation simulations with multiple actors in a dynamic situation. We do this by comparing both the voxel data structure and pathfinding algorithm combinations in a dynamic evacuation simulation application. The comparison is done by looking at the quality of the paths, if the algorithms are able to adapt to a dynamic situation and the performance of the paths, both in computation times and memory load.

These experiments reveal that a time-aware variant of A* is able to outperform the other algorithms, when applied on a sparse Morton grid. Additionally, it shows that the use of a sparse Morton grid is preferable to implementing a full octree or the use of a non-sparse regular voxel grid for dynamic multi-actor voxel scenes. Finally, the experiments show that dynamic events can be added into pathfinding algorithms by separating walking the path from finding the path, and using a data structure that is time-aware.