An Efficient and Exact Parallel Algorithm for Intersecting Large 3-D Triangular Meshes Using Arithmetic Filters. (March 2020)

• Record Type: Journal Article
• Authors: de Magalhães, Salles Viana Gomes; Franklin, W. Randolph; Andrade, Marcus Vinícius Alvim
• Is Part Of: Computer aided design. Volume 120(2020)
• Publication Date: 2020-03
• Subjects: Boolean operations -- 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.2019.102801
• Languages: English
• ISSNs: 0010-4485

Abstract

Abstract: We present 3D-EPUG-Overlay, a fast, exact, parallel, memory-efficient, algorithm for computing the intersection between two large 3-D triangular meshes with geometric degeneracies. Applications include CAD/CAM, CFD, GIS, and additive manufacturing. 3D-EPUG-Overlay combines 5 techniques: multiple precision rational numbers to eliminate roundoff errors during the computations; Simulation of Simplicity to properly handle geometric degeneracies; simple data representations and only local topological information to simplify the correct processing of the data and make the algorithm more parallelizable; a uniform grid to efficiently index the data, and accelerate testing pairs of triangles for intersection or locating points in the mesh; and parallel programming to exploit current hardware. 3D-EPUG-Overlay is up to 101 times faster than LibiGL, and comparable to QuickCSG, a parallel inexact algorithm. 3D-EPUG-Overlay is also more memory efficient. In all test cases, 3D-EPUG-Overlay 's result matched the reference solution. It is freely available for nonprofit research and education at https://github.com/sallesviana/MeshIntersection . Graphical abstract: Highlights: A novel algorithm for intersecting triangulated meshes is presented. The method uses 5 techniques to achieve both exactness and efficiency in time and space. All the computation is performed exactly and special cases are properly handled. The approach has been implemented and compared against other state of the art methods. This algorithm parallelizes well and has excellent performance.