Publication

Accelerating the exact evaluation of geometric predicates with GPUs

Marcelo de Matos Menezes, Salles Viana Gomes Magalhães, W. Randolph Franklin, Matheus Aguilar de Oliveira, and Rodrigo E. O. Bauer Chichorro. Accelerating the exact evaluation of geometric predicates with GPUs. In Suzanne Shontz, Joaquim Peiró, and Ryan Viertel, editors, 28th International Meshing Roundtable. Buffalo, NY, USA, 16 Oct 2019. doi:10.5281/zenodo.3653101.
[full text] [slides]
BibTeX
@inproceedings{marcelo-gpu-geometry-imr-2019,
    author = "de Matos Menezes, Marcelo and Magalhães, Salles Viana Gomes and Franklin, W. Randolph and de Oliveira, Matheus Aguilar and Chichorro, Rodrigo E. O. Bauer",
    editor = "Shontz, Suzanne and Peiró, Joaquim and Viertel, Ryan",
    title = "Accelerating the exact evaluation of geometric predicates with {GPU}s",
    booktitle = "28th International Meshing Roundtable",
    month = "16 Oct",
    address = "Buffalo, NY, USA",
    year = "2019",
    isbn = "978-1-7334890-0-3",
    doi = "10.5281/zenodo.3653101",
    href = "\bibhrefpt{235-marcelo-gpu-geometry-imr-2019}{235-marcelo-gpu-geometry-imr-2019-talk.pdf}",
    mykey = "recent salles parallel",
    customlinkslides = "https://wrfranklin.org/p/235-marcelo-gpu-geometry-imr-2019-talk.pdf"
}

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 segment 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 289 times (when compared against a similar sequential implementation) in the evaluation of these predicates (and up to 40 times if the entire running-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, VLSI design and meshing.

Full text

Read the paper

The full text opens at its existing location.

Preview the full text on this page

Open or download the paper

Citation

Download BibTeX ↓

@inproceedings{marcelo-gpu-geometry-imr-2019,
    author = "de Matos Menezes, Marcelo and Magalhães, Salles Viana Gomes and Franklin, W. Randolph and de Oliveira, Matheus Aguilar and Chichorro, Rodrigo E. O. Bauer",
    editor = "Shontz, Suzanne and Peiró, Joaquim and Viertel, Ryan",
    title = "Accelerating the exact evaluation of geometric predicates with {GPU}s",
    booktitle = "28th International Meshing Roundtable",
    month = "16 Oct",
    address = "Buffalo, NY, USA",
    year = "2019",
    isbn = "978-1-7334890-0-3",
    doi = "10.5281/zenodo.3653101",
    href = "\bibhrefpt{235-marcelo-gpu-geometry-imr-2019}{235-marcelo-gpu-geometry-imr-2019-talk.pdf}",
    mykey = "recent salles parallel",
    customlinkslides = "https://wrfranklin.org/p/235-marcelo-gpu-geometry-imr-2019-talk.pdf"
}
← PublicationsBack to top ↑