ANAVMG: Automatic generation of suboptimal Navmeshes for 3D virtual environments

Abstract

A popular solution to solve the problem of navigation in a complex scene, consists of subdividing the scene into convex regions (cells) forming what is commonly known as a Navigation Mesh (NavMesh). A Cell-and-Portal Graph (CPG) is then created where a node of the graph corresponds to a convex region of the NavMesh and a portal is an edge shared by two cells. Path-finding can then be solved using an algorithm such as A*. Although NavMeshes are widely used on complex applications such as videogames and virtual simulations, there are not many applications to automatically generate a NavMesh appropriate for path planning, so often either the user need to refine those semi-automatic NavMeshes, or create them by hand from scratch which is extremely time consuming and a source of errors. There is therefore a need for automatic methods to generate Cell-and-Portal Graphs for navigation, from any given 3D environment with minimum user input required. This thesis focuses on solving such a complex problem. The work presented in this master thesis gets as an input any 3D virtual environment represented by a polygon soup, and provides as an output the complete CPG. The main contribution of this thesis is a novel GPU based method to generate a NavMesh for a given 3D scene. Our method has two main steps: firstly it abstracts away the information of the 3D model that represents the scene (with its slopes, steps and other obstacles) to automatically convert it into a 2D representation based on several layers of a single simple polygon (floor) that can contain holes (obstacles). Secondly, it automatically generates a suboptimal convex decomposition of this 2D representation which represents the CPG. Our method is robust against degeneracies of the starting 3D model, such as interpenetrating geometry.