Semantic navigation meshes for complex outdoor terrains

Traditional navigation meshes are typically based on splitting the terrain into connected convex regions representing walkable cells. This works well for almost flat terrains where obstacles are clearly defined by walls or holes. When applied to complex outdoor environments with many changes in terrain height and slope, traditional approaches fail to correctly identify the walkable areas. Current navigation meshes require the user to specify the character's maximum step size and slope, and then classify the environment as walkable or non-walkable, thus limiting the flexibility to adjust paths to the agents' characteristics. Even if some terrain properties are then computed to add semantics to the navigation mesh, many cells could cover a wide range of values, as this information was ignored during its generation. In this paper, we present a novel approach to generate semantic navigation meshes, where the generated cells have a coherent and low-variance range of values for the chosen semantics (e.g., slope). Cell generation is performed with a semantic partitioning based on a region-growing algorithm. Our navigation mesh allows us to preserve the full complexity of the terrain without forcing a binary decision between walkable and non-walkable and provides useful semantics for the pathfinding algorithm.