Fast parallel evaluation of exact geometric predicates on GPUs | W. Randolph Franklin, Rensselaer Polytechnic Institute, Troy NY USA

Marcelo de Matos Menezes, Salles Viana Gomes Magalhães, Matheus Aguilar de Oliveira, W. Randolph Franklin, and Rodrigo Eduardo de Oliveira Bauer Chichorro. Fast parallel evaluation of exact geometric predicates on GPUs. J. Computer Aided Design, September 2022. Special Issue: 28th International Meshing Roundtable: Mesh Modeling for Simulations and Visualization. URL: https://www.sciencedirect.com/science/article/abs/pii/S0010448522000616, doi:https://doi.org/10.1016/j.cad.2022.103285.
[full text] [BibTeX▼]

@article{marcelo-gpu-predicates-2021,
    author = "de Matos Menezes, Marcelo and Magalhães, Salles Viana Gomes and de Oliveira, Matheus Aguilar and Franklin, W. Randolph and de Oliveira Bauer Chichorro, Rodrigo Eduardo",
    editor = "Peiro, Joaquim and Shontz, Suzanne and Viertel, Ryan",
    title = "Fast parallel evaluation of exact geometric predicates on {GPU}s",
    month = "September",
    year = "2022",
    number = "103285",
    note = "Special Issue: 28th International Meshing Roundtable: Mesh Modeling for Simulations and Visualization",
    journal = "J. Computer Aided Design",
    doi = "https://doi.org/10.1016/j.cad.2022.103285",
    href = "\bibhref{239-marcelo-gpu-predicates-2021}",
    mykey = "recent salles marcelo matheus rodrigo parallel topology",
    url = "https://www.sciencedirect.com/science/article/abs/pii/S0010448522000616"
}

Abstract

This paper presents a technique for employing high-performance computing for accelerating the exact evaluation of geometric predicates. Arithmetic filters are implemented using interval arithmetic to reduce the necessity of exact arithmetic while ensuring the results of the predicates are still exact. Furthermore, the computation with interval arithmetic is offloaded to a CUDA-enabled GPU. If the GPU detects that some results cannot be trusted, the corresponding predicates are re-evaluated in parallel on the CPU using arbitrary-precision rational numbers. As a case study, a red-blue 3D triangle intersection algorithm has been implemented. Since the intervals are implemented using floating-point numbers, the parallel computing power of GPUs for processing these numbers led to a speedup of up to 1936 times (when compared against a similar sequential implementation) in the evaluation of these predicates (and up to 414 times if the entire runnning-time of the algorithm is considered). The excellent performance associated to the exactness makes this technique suitable for accelerating geometric operations in fields such as CAD, GIS and 3D modeling.

Full Text

[download]