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/.
[full text]
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}"
}
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.
Full text
Read the paperThe full text opens at its existing location.
Preview the full text on this page
Citation
@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}"
}