Methods for avoiding round-off errors on 2D and 3D geometric simplification

• Ano de defesa: 2016
• Autor(a) principal: Gruppi, Maurício Gouveia
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: eng
• Instituição de defesa: Universidade Federal de Viçosa
• Palavras-chave em Português: Algoritmos; Programação paralela (Computação); Geometria Computacional; Números racionais; Ciência da Computação
• Link de acesso: http://www.locus.ufv.br/handle/123456789/9401

In this work, we evaluated the occurrence of round-off errors on floating-point arith- metic for the problem of 2D and 3D geometric simplification. Round-off errors may lead algorithms to produce topologically inconsistent results, that is, results that fail to preserve crucial features of the original model. Some algorithms are designed to avoid such inconsistencies, however, they are usually implemented with floating- point arithmetic. Even these algorithms may fail to output topologically consistent results due to round-off errors. In order to overcome this issue, two methods were proposed: EPLSimp for polyline simplification, and UGSimp, for triangular mesh simplification. On both methods, preemptive tests are carried out to detect and pre- vent topological inconsistencies. Such tests use multiple precision rational numbers instead of floating-point numbers. The use of rational numbers does not present round-off errors. Nevertheless, it causes an increase on the execution time of the algorithms. To compensate for this performance loss, both algorithms were imple- mented using a parallel computing paradigm. As result, the methods presented do not output topologically inconsistent models. Tests have shown a considerable performance gain with parallel implementations of the proposed approaches.