Matheus Aguilar de Oliveira · W. Randolph Franklin

2022

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.
[details] [full text]
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.
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 homepage-selected",
    url = "https://www.sciencedirect.com/science/article/abs/pii/S0010448522000616"
}
```
Marcelo de Matos Menezes, Salles Viana Gomes de Magalhães, Matheus Aguilar, W. Randolph Franklin, and Bruno Coelho. Employing GPUs to accelerate exact geometric predicates for 3D geospatial processing. In John Krumm, Andreas Züfle, and Cyrus Shahabi, editors, Spatial Gems, volume 1, chapter 11. ACM, 2022. URL: https://www.spatialgems.net/.
[details] [full text]
Abstract
This paper presents a technique to use GPUs to accelerate the computation of 3D geometric predicates. A common predicate is computing the orientation of four 3D points, which is a subproblem in applications such as intersecting two 3D meshes. Since the higher level application may require billions of evaluations, efficiency is important. Accuracy is required since floating roundoff errors can cause topological impossibilities. One solution is to compute with rational numbers, but that is difficult to implement on a GPU because rationals' sizes vary. Our solution is to compute on the GPU with interval arithmetic, but fall back to using rationals on the CPU if the interval computed on the GPU includes the origin; i.e., its sign is unknown. Our experiment with a dataset of hard rock mining drill holes show that this fallback to the CPU is rarely necessary; so that our technique gave a 17 times speedup compared to a sequential implementation.
BibTeX
```
@incollection{marcelo-employing-gem-2022,
    author = "de Matos Menezes, Marcelo and de Magalhães, Salles Viana Gomes and Aguilar, Matheus and Franklin, W. Randolph and Coelho, Bruno",
    editor = "Krumm, John and Züfle, Andreas and Shahabi, Cyrus",
    title = "Employing {GPU}s to accelerate exact geometric predicates for {3D} geospatial PROCESSING",
    booktitle = "Spatial Gems",
    publisher = "ACM",
    year = "2022",
    volume = "1",
    chapter = "11",
    mykey = "recent salles marcelo matheus bruno parallel topology",
    url = "https://www.spatialgems.net/",
    href = "\bibhref{242-marcelo-employing-gem-2022}"
}
```

2020

Marcelo de Matos Menezes, Salles Viana Gomes de Magalhães, Matheus Aguilar, W. Randolph Franklin, and Bruno Coelho. Employing GPUs to accelerate exact geometric predicates for 3D geospatial processing. In John Krumm, editor, 2nd ACM SIGSPATIAL International Workshop on Spatial Gems (SpatialGems 2020). ACM, Nov 2020. URL: https://www.spatialgems.net/.
[details] [full text]
Abstract
This paper presents a technique to use GPUs to accelerate the computation of 3D geometric predicates. A common predicate is computing the orientation of four 3D points, which is a subproblem in applications such as intersecting two 3D meshes. Since the higher level application may require billions of evaluations, efficiency is important. Accuracy is required since floating roundoff errors can cause topological impossibilities. One solution is to compute with rational numbers, but that is difficult to implement on a GPU because rationals' sizes vary. Our solution is to compute on the GPU with interval arithmetic, but fall back to using rationals on the CPU if the interval computed on the GPU includes the origin; i.e., its sign is unknown. Our experiment with a dataset of hard rock mining drill holes show that this fallback to the CPU is rarely necessary; so that our technique gave a 17 times speedup compared to a sequential implementation.
BibTeX
```
@incollection{marcelo-employing-gem-2020,
    author = "de Matos Menezes, Marcelo and de Magalhães, Salles Viana Gomes and Aguilar, Matheus and Franklin, W. Randolph and Coelho, Bruno",
    editor = "Krumm, John",
    title = "Employing {GPU}s to accelerate exact geometric predicates for {3D} geospatial PROCESSING",
    booktitle = "2nd {ACM SIGSPATIAL} International Workshop on Spatial Gems (SpatialGems 2020)",
    publisher = "ACM",
    year = "2020",
    month = "Nov",
    mykey = "salles marcelo matheus bruno parallel topology",
    url = "https://www.spatialgems.net/",
    href = "\bibhref{238-marcelo-employing-gem-2020}",
    note = "Best paper award."
}
```