Homepage of Roland Geraerts

We study how we can automatically create a data structure that represents the walkable surfaces in such an environment, and how it can be updated dynamically and efficiently when it changes. We refer to this structure as a navigation mesh. This mesh enables efficient crowd simulation, which is our next topic of research. We study and develop a crowd simulation framework and its components, which ranges from global (AI) planning to local animation. We create models for realistic crowd behaviors, which includes studying how (groups of) people move and avoid collisions in such environments, based on agent profiles and semantics (such as terrain annotations).

Annotating traversable gaps in walkable environments

The annotation process of traversable gaps in a 3D environment. An unprocessed 3D environment; The red areas are not walkable because the slope is too high or the vertical clearance to obstacles is too low; The blue areas denote the walkable areas in the environment; note that there are gaps between the steps; Our algorithm identifies and fills these gaps with the green polygons such that agents can continuously navigate the environment.

Abstract

Autonomous agents typically need a navigation mesh of a 3D virtual environment to allow efficient path planning. This mesh needs as input a continuous representation of the walkable areas. However, the walkable environment, i.e. the parts of the 3D environment that an agent can walk on, may contain gaps due to the filtering steps performed to compute it, because of modelling errors in the 3D model, or simply be part of the geometry.

We provide an algorithm that identifies and fills these gaps. We detect gaps, up to a given size, between pairs of boundary edges of the walkable environment, and fill them with polygons. We employ a heuristic for choosing which pairs of edges should be connected.

We compare our algorithm to Recast, a voxel-based method for navigation mesh generation. 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 good results. However, our method is currently slower than Recast, and requires more memory.

References

Jordi L. Vermeulen, Arne Hillebrand and Roland Geraerts. Annotating traversable gaps in walkable environments. In International Conference on Robotics and Automation, pp. 3045-3052, 2018, (Brisbane, Autralia).