Dissertação
Fast and exact evaluation of geometric predicates using graphics processing units
Avaliação rápida e exata de predicados geométricos utilizando unidades de processamento gráfico
Registro en:
MENEZES, Marcelo de Matos. Avaliação rápida e exata de predicados geométricos utilizando unidades de processamento gráfico. 2021. 63 f. Dissertação (Mestrado em Ciência da Computação) - Universidade Federal de Viçosa, Viçosa. 2021.
Autor
Menezes, Marcelo de Matos
Institución
Resumen
Floating point arithmetic’s finite precision presents a major challenge in the field of computational geometry, since even carefully designed algorithms may fail due to round-off errors. While there has been research to develop exact geometric algorithms, the existing techniques so far can still be improved performance-wise. In this work we propose a fast and exact method for efficient geometric predicate evaluation using the graphics process- ing unit, in which, by implementing arithmetic filtering on the GPU, the computation of most predicates can be performed without round-off errors. The (few) results that are unreliable are reevaluated using arbitrary precision rational numbers in parallel on the CPU. We measured the efficiency of our method by implementing geometric algorithms in 3 case studies: 2D segment-segment intersection, 3D segment-triangle intersection, and 3D triangle-triangle intersection. At each step, new techniques were proposed for eliminating the current performance bottleneck. In our last experiments, a comparison of our method against a sequential CPU implementation yielded speedups of up to 1936× for intersection evaluation, and 414× for the entire running time of the algorithm. The achieved efficiency shows that our technique is ideal for accelerating exact geometric computations, and fields such as CAD, GIS, and 3D modeling should benefit from it. Keywords: Computational geometry. Exact computation. Arithmetic filtering. GPGPU. A precisão finita da aritmética de ponto flutuante é um grande desafio na área de geometria computacional, uma vez que algoritmos desenvolvidos cuidadosamente podem falhar devido a erros de arredondamento. Embora existam pesquisas voltadas ao desenvolvi- mento de algoritmos geométricos exatos, as técnicas existentes até então ainda podem ser melhoradas em termos de desempenho. Neste trabalho é proposto um método eficiente e exato para avaliação de predicados geométricos utilizando a unidade de processamento gráfico, no qual, através de uma implementação de filtragem de aritmética na GPU, a maior parte dos predicados podem ser calculados sem erros de arredondamento. Os (poucos) resultados que não são confiáveis, são reavaliados usando números racionais de precisão arbitrária em paralelo na CPU. A eficiência do método foi medida com implementações de algoritmos geométricos em 3 estudos de caso: interseção de segmentos em 2D, interseção de segmento e triângulo em 3D e interseção de triângulos em 3D. Em cada passo, novas técnicas foram propostas para acelerar os gargalos de desempenho. Nos úl- timos experimentos, uma comparação do método contra uma implementação sequencial na CPU resultou em aceleração (speedups) de até 1936× para avaliação de interseções, e 414× considerando o tempo total do algoritmo. Tal eficiência mostra que a técnica de- scrita nesse trabalho é ideal para acelerar a computação exata de predicados geométricos, o que deve beneficiar áreas como CAD, SIG e modelagem 3D. Palavras-chave: Geometria computacional. Computação exata. Filtragem de aritmética. GPGPU. Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)