To access the full text documents, please follow this link:

ANAVMG: Automatic generation of suboptimal Navmeshes for 3D virtual environments
Oliva Martínez, Ramon
Universitat Politècnica de Catalunya. Departament de Llenguatges i Sistemes Informàtics; Pelechano Gómez, Núria
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.
Àrees temàtiques de la UPC::Informàtica::Infografia
Computer graphics
Three-dimensional imaging
Visualització (Informàtica)
Imatges tridimensionals
Information display systems
Attribution-NonCommercial-NoDerivs 3.0 Spain
Universitat Politècnica de Catalunya

Show full item record

Related documents

Other documents of the same author

Oliva Martínez, Ramon; Pelechano Gómez, Núria
Oliva Martínez, Ramon; Pelechano Gómez, Núria