dc.contributor |
Universitat Politècnica de Catalunya. Departament de Llenguatges i Sistemes Informàtics |
dc.contributor |
Pelechano Gómez, Núria |
dc.contributor.author |
Oliva Martínez, Ramon |
dc.date |
2012-09-05 |
dc.identifier.uri |
http://hdl.handle.net/2099.1/16508 |
dc.language.iso |
eng |
dc.publisher |
Universitat Politècnica de Catalunya |
dc.rights |
Attribution-NonCommercial-NoDerivs 3.0 Spain |
dc.rights |
info:eu-repo/semantics/openAccess |
dc.rights |
http://creativecommons.org/licenses/by-nc-nd/3.0/es/ |
dc.subject |
Àrees temàtiques de la UPC::Informàtica::Infografia |
dc.subject |
Computer graphics |
dc.subject |
Three-dimensional imaging |
dc.subject |
Visualització (Informàtica) |
dc.subject |
Infografia |
dc.subject |
Imatges tridimensionals |
dc.subject |
Information display systems |
dc.title |
ANAVMG: Automatic generation of suboptimal Navmeshes for 3D virtual environments |
dc.type |
info:eu-repo/semantics/masterThesis |
dc.description.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. |