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

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

de Jong, Michiel (TU Delft Architecture and the Built Environment)

Voûte, R.L. (mentor)
van Oosterom, P.J.M. (graduation committee)

Delft University of Technology

Geomatics

2022-06-17

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.

Voxels
Pathfinding
Dynamic
Evacuation planning
Indoor
3D

http://resolver.tudelft.nl/uuid:0b5e90b8-6ca1-4cd8-b5db-31539bddad1d

Student theses

master thesis

© 2022 Michiel de Jong