Fast Parallel Evaluation of Exact Geometric Predicates on GPUs. (September 2022)

• Record Type: Journal Article
• Authors: de Matos Menezes, Marcelo; Viana Gomes de Magalhães, Salles; Aguilar de Oliveira, Matheus; Randolph Franklin, W.; de Oliveira Bauer Chichorro, Rodrigo Eduardo
• Is Part Of: Computer aided design. Volume 150(2022)
• Publication Date: 2022-09
• Subjects: Geometric predicates -- Parallel programming -- Exact computation -- Polyhedron intersection; Computer-aided design -- Periodicals; Engineering design -- Data processing -- Periodicals; Computer graphics -- Periodicals; Conception technique -- Informatique -- Périodiques; Infographie -- Périodiques; Computer graphics; Engineering design -- Data processing; Periodicals; Electronic journals; 620.00420285
• DOI: 10.1016/j.cad.2022.103285
• Languages: English
• ISSNs: 0010-4485

Abstract

Abstract: This paper accelerates the exact evaluation of large numbers of 3D geometric predicates with an algorithm whose work is partitioned between the CPU and the GPU on a high-performance computer to exploit the relative strengths of each. The test algorithm computes all the red–blue intersections between a set of red 3D triangles and another set of blue 3D triangles. A sequence of filters is employed that progressively eliminates more and more red–blue pairs that do not intersect, finally leaving only the actual intersections. Initially, a uniform grid is constructed on the GPU to identify pairs of nearby triangles. Then, these pairs are tested for intersection with single-precision interval arithmetic on the GPU. The ambiguous cases are next filtered with double-precision interval arithmetic on the multi-core CPU, and finally the hard cases are re-evaluated in parallel on the CPU using arbitrary-precision rational numbers. The parallel speedup for the whole algorithm was up to 414 times. It took only 1.17 s to find the 18M intersections between two datasets containing a total of 14M triangles. The intersection computation was sped up by up to 1936 times. The techniques that gave this excellent performance should be useful for parallelizing other geometric algorithms in fields such as CAD, GIS, and 3D modeling. Graphical abstract: Highlights: A novel framework for exactly evaluating geometric predicates is presented. Predicates are evaluated using interval arithmetic on the GPU. Unreliable results are detected and exactly re-evaluated on the CPU. Detecting the intersection of red–blue triangles has been evaluated as a case study. A speedup of up to 1936 times against the sequential implementation has been observed.