Extracting walkable areas from 3D environments

Abstract

Systems for real-time navigation in games and simulations commonly expect the environment to be given in a simplified representation: a navigation mesh. Creating such a mesh automatically can be challenging, especially for 3D environments. This is because, firstly, it may be complex to compute some of the constraints that traversable surfaces must adhere to, such as having a minimum vertical clearance to obstacles. Secondly, in practice, environments are created with mainly visualisation in mind. As such, they often contain errors that are difficult to see, but misrepresent the intended geometry and topology. For example, they can impair the connectivity of the environment, causing traversable surfaces to be wrongly disconnected from each other.

Currently, the common approach to deal with these challenges is to approximate the navigable surfaces in the environment with a grid of voxels. While this provides good robustness, it cannot guarantee a good output.

In this thesis, we present a surface-based method to extract walkable areas in an exact manner. We lessen the complexity of the problem by using a filtering pipeline of relatively simple processing steps. These are, firstly, filters that determine which part of the surface is walkable, checking for steepness and vertical clearance to obstacles. Second are repair filters, which resolve specific errors, namely degeneracies, vertex duplication and intersections. And lastly, we include filters that prepare for navigation mesh generation by removing small regions, simplifying the geometry and subdividing the environment into non-overlapping 2D layers. To avoid numerical robustness issues, we implement the geometric algorithms with arbitrary precision.

We have created a working implementation of the pipeline and discuss the results of experiments performed with it. They illustrate that our exact method is highly accurate, in contrast to volumetric approaches. However, they also highlight that more work is needed before the pipeline can be successfully used in practice. This includes performance optimisation, controlled conversion to limited precision and additional filters to deal with, for example, gaps. Nevertheless, the results indicate that it is feasible to achieve exact and robust walkable area extraction through our approach. By building on these results, it may become possible to automatically create accurate navigation meshes for arbitrary 3D environments. This would enable the use of high-quality navigation methods in games and simulations with minimal effort.