2026-04-05T10:47:16Zhttps://recercat.cat/oai/request

oai:recercat.cat:2099.1/165082025-07-22T20:01:34Zcom_2072_1033col_2072_452951

ANAVMG: Automatic generation of suboptimal Navmeshes for 3D virtual environments Oliva Martínez, Ramon Àrees temàtiques de la UPC::Informàtica::Infografia Computer graphics Three-dimensional imaging Visualització (Informàtica) Infografia Imatges tridimensionals Information display systems 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. 2012-09-05 Master thesis http://creativecommons.org/licenses/by-nc-nd/3.0/es/ Open Access Attribution-NonCommercial-NoDerivs 3.0 Spain Universitat Politècnica de Catalunya