Do Lógico ao Abstrato: A Ciência no Cotidiano
23 a 28 de outubro de 2017
Trabalho 8978
| ISSN | 2237-9045 |
|---|---|
| Instituição | Universidade Federal de Viçosa |
| Nível | Graduação |
| Modalidade | Pesquisa |
| Área de conhecimento | Ciências Exatas e Tecnológicas |
| Área temática | Ciência da Computação |
| Setor | Departamento de Informática |
| Bolsa | FAPEMIG |
| Conclusão de bolsa | Sim |
| Apoio financeiro | FAPEMIG |
| Primeiro autor | Marcelo de Matos Menezes |
| Orientador | MARCUS VINICIUS ALVIM ANDRADE |
| Título | Avaliação de Diferentes Métodos de Rasterização e Interseção de Triângulos com Grades Uniformes para Otimização do Método PinMesh |
| Resumo | Uma malha tridimensional ou mapa poliedral, é um conjunto de vértices, arestas e polígonos que define um formato aproximado para que objetos tridimensionais possam ser representados pelo computador. Geralmente os mapas são formados por triângulos, devido às características peculiares desse polígono, como o fato de serem sempre convexos e seus vértices serem sempre coplanares. A necessidade de se localizar determinados pontos nesse tipo de malha, ou mesmo em malhas bidimensionais, é algo recorrente nas áreas de Geometria Computacional, Computação Gráfica, Sistemas de Informação Geográfica, CAD, Jogos Digitais, entre outras. A localização em si possui aplicações diretas como, por exemplo, encontrar os pontos mais próximos de determinada região em um mapa. Pode também ser um passo intermediário para resolução de outros problemas nos quais é comum lidarmos com grandes quantidades de dados. Tal fato torna imprescindível a criação de algoritmos eficientes, cuja corretude e robustez são fundamentais, pois dependendo da aplicação, um cálculo errado pode inutilizar a solução. Pesquisas na área resultaram em algoritmos que propunham estratégias diversificadas para atacar o problema, que, embora eficientes, eram propensas à erros de precisão e/ou falhavam ao tratar os inúmeros casos degenerados intrínsecos da área. Visando eliminar tais problemas, foi criado o PinMesh que, através de técnicas como Simulation of Simplicity e aritmética exata com números racionais, trata os casos degenerados de forma consistente e não é afetado por erros de arredondamento. Além disso, o algoritmo se mostrou o mais eficiente entre os conhecidos até então, devido ao uso de uma estrutura de dados simples e eficaz, chamada Uniform Grid. Entretanto, como o PinMesh interage com o grid de forma simples, foi realizada uma avaliação de métodos alternativos para determinar a interseção entre cada triângulo da malha e as células da grade uniforme. Foram propostos e analisados dois outros métodos com o intuito de identificar se algum deles aumentaria a eficiência do algoritmo. |
| Palavras-chave | geometria computacional, localização de pontos, grades uniformes |
| Forma de apresentação..... | Painel |