Please use this identifier to cite or link to this item:
http://hdl.handle.net/1843/ESBF-9GXMPR
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.advisor1 | Luiz Chaimowicz | pt_BR |
dc.contributor.referee1 | Gisele Lobo Pappa | pt_BR |
dc.contributor.referee2 | Soraia Raupp Musse | pt_BR |
dc.creator | Eduardo Penha Castro Fantini | pt_BR |
dc.date.accessioned | 2019-08-13T13:53:07Z | - |
dc.date.available | 2019-08-13T13:53:07Z | - |
dc.date.issued | 2014-01-20 | pt_BR |
dc.identifier.uri | http://hdl.handle.net/1843/ESBF-9GXMPR | - |
dc.description.abstract | The Art Gallery Problem consists in determining the minimum number of observers required to cover an environment such that each point of space is seen by at least one observer. This is a NP-Hard problem well known in the field of computational geometry. In the literature, several restrictions are applied to 2D and 3D environments to study and solve the problem in polynomial time, for example the use of simple polygons, orthogonal and planar environments, etc. In this work we present an approximate and polynomial solution based on metaheuristic genetic algorithms that can be applied to general 3D environments without any restriction and, therefore, applicable in shooter games and also real-world environments. The methodology uses the techniques of (i) computer graphics to generate sample points in the environment, (ii) ray-mesh intersection test to generate a graph of visibility between the samples and (iii) genetic algorithms to find and optimize the minimum set of observers. The maps of the game Counter-Strike were used to analyze the placement of small groups of observers in complex environments with obstacles. The game engines Half-Life and Irrlicht were used to apply the ray-mesh intersection test in 3D environments. A series of experiments were performed and the results show that our methodology is capable of obtaining a good coverage of complex spaces with a small number of agents observing. | pt_BR |
dc.description.resumo | O Problema da Galeria de Arte consiste em determinar o número mínimo de guardas necessários para cobrir um ambiente tal que cada ponto no espaço é coberto por, pelo menos, um observador. Neste trabalho, apresentamos uma abordagem genética que pode ser aplicada a ambientes 3D genéricos sem qualquer restrição, uma lacuna existente no estado da arte até então. A metodologia utiliza técnicas de (i) computação gráfica para gerar pontos de amostragem no ambiente, (ii) teste de interseção raio-malha para gerar um gráfico de visibilidade entre as amostras e (iii) algoritmos genéticos para encontrar e minimizar o conjunto de observadores. Os mapas do jogo Counter-Strike foram utilizados como ambientes de entrada e os motores de jogo Half-Life e Irrlicht foram usados para gerar os grafos de visibilidade. Uma série de experimentos foram realizados, e os resultados mostram que nossa metodologia é capaz de obter uma boa cobertura de espaços complexos com um pequeno número de guardas. | pt_BR |
dc.language | Português | pt_BR |
dc.publisher | Universidade Federal de Minas Gerais | pt_BR |
dc.publisher.initials | UFMG | pt_BR |
dc.rights | Acesso Aberto | pt_BR |
dc.subject | Geometria Computacional | pt_BR |
dc.subject | Problema de galeria de arte | pt_BR |
dc.subject | Computação Natural | pt_BR |
dc.subject | Jogos digitais | pt_BR |
dc.subject | Computação Gráfica | pt_BR |
dc.subject.other | Geometria computacional | pt_BR |
dc.subject.other | jogos digitais | pt_BR |
dc.subject.other | Computação | pt_BR |
dc.subject.other | Computação gráfica | pt_BR |
dc.title | Cobertura em ambientes 3D arbitrários: o problema da galeria de arte em jogos de tiro | pt_BR |
dc.type | Dissertação de Mestrado | pt_BR |
Appears in Collections: | Dissertações de Mestrado |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
eduardofantini.pdf | 28.94 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.