Bridging gaps in walkable environments

Abstract

In crowd simulation, a navigation mesh of an environment is typically generated to allow efficient path planning. Some methods for navigation mesh generation require as input a representation of the walkable environment, that is, the parts of the environment that a human would be able to walk across. In a previous Master's thesis, Polak developed a filtering pipeline that extracts such a walkable environment from a 3D environment. A shortcoming of this method is that the result often contains gaps; for instance, stairs will yield a series of free-floating steps, with no information indicating that it is possible to walk from one step to the next.

In this thesis, we provide an algorithm extending the existing pipeline that tries to solve this. We detect gaps, up to a given size, between pairs of boundary edges of the walkable environment, and fill them with a quad. For connections between different cycles of boundary edges, we make a heuristic choice based on projected distance when there are multiple destinations for a given segment of a boundary edge. For connections between boundary edges in the same cycle, we project all the quads onto the ground plane and take their union, lifting the result back to 3D to fill the gap.

We compare our algorithm to two voxel-based methods of navigation mesh generation: Recast and NEOGEN. We find that our method gives more accurate results in many environments: it retains the exact representation of the walkable environment, semantically separates the gaps from the walkable areas, and requires no tweaking of parameters to obtain optimal results. However, there are some open problems that still need to be solved for our method to work fully automatically in practice, such as dealing with obstacles and the interaction of more than two cycles of boundary edges.