2026-04-13T02:16:26Zhttps://recercat.cat/oai/request

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

00925njm 22002777a 4500 dc Oliva Martínez, Ramon author 2012-09-05 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) Infografia Imatges tridimensionals Information display systems ANAVMG: Automatic generation of suboptimal Navmeshes for 3D virtual environments