“Bicentenário da Independência: 200 anos de ciência, tecnologia e inovação no Brasil e 96 anos de contribuição da UFV”.
8 a 10 de novembro de 2022
Trabalho 17468
| 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 | CNPq |
| Conclusão de bolsa | Sim |
| Apoio financeiro | CNPq |
| Primeiro autor | Henrique Campos Padula |
| Orientador | SALLES VIANA GOMES DE MAGALHAES |
| Título | PinMesh: utilização de Uniform Grid e Flood Fill na resolução de predicados geométricos |
| Resumo | PinMesh: utilização de Uniform Grid e Flood Fill na resolução de predicados geométricos Henrique C. Padula e Salles Viana G.de Magalhaes Um dos principais desafios dentro da geometria computacional consiste em lidar com números de ponto flutuante, devido principalmente ao fato de sua representação finita, levando a possíveis erros de arredondamento. Uma possível solução para tal problema de robustez consiste no uso de números racionais com precisão arbitrária, porém, tal abordagem possui um grande custo computacional devido a impossibilidade de utilização do hardware especializado e da necessidade de um grande número de dígitos à medida que as operações forem se acumulando. Nesse contexto, o PinMesh surge como um algoritmo robusto para o processamento de predicados geométricos, fazendo otimizações para reduzir o grande custo computacional da abordagem anteriormente citada. Na análise de predicados geométricos, é de nosso interesse muitas vezes apenas o sinal de um determinado valor, sendo assim, a utilização de uma aritmética exata não é sempre necessária. Portanto, é possível filtrar os pontos nos quais será necessário utilizar números racionais com precisão arbitrária, reduzindo assim, o custo total das operações. Uma outra otimização, consiste em dividir o espaço analisado em uma grade de células de tamanho igual, nos possibilitando fazer indexações que auxiliam no processamento. Neste trabalho, propomos o uso da grade para indexar células que estão inteiramente dentro de um poliedro, pois por definição, qualquer ponto dessa célula também estará dentro do poliedro, fazendo com que a consulta nesses pontos possa ser executada com complexidade constante. Uma outra propriedade interessante é a de que se uma célula está inteiramente dentro de um poliedro, todas as células que fazem parte do mesmo componente conexo também estarão, portanto, propomos também a utilização do algoritmo de flood fill para a partir de uma célula indexada, conseguir definir o index para todo o componente conexo ao qual aquela célula pertence. Em predicados compostos por tetrameshs, não teremos células vazias dentro do poliedro, portanto, tal otimização surge como uma forma de expandir a utilização do algoritmo para casos em que temos meshs diferentes de tetraedros, tornando o algoritmo como um todo mais genérico |
| Palavras-chave | geometria, mesh, otimização |
| Forma de apresentação..... | Painel |
| Link para apresentação | Painel |
|---|