W. Randolph Franklin, Salles V. G. de Magalhães, and Marcus V. A. Andrade.
Exact fast parallel intersection of large 3-D triangular meshes.
In 27th International Meshing Roundtable. Albuquerque, New Mexico, 2 Oct 2018.
[full text] [slides]
BibTeX
@inproceedings{exact-fast-parallel-imr-2018,
author = "Franklin, W. Randolph and de Magalhães, Salles V. G. and Andrade, Marcus V. A.",
title = "Exact fast parallel intersection of large 3-{D} triangular meshes",
booktitle = "27th International Meshing Roundtable",
address = "Albuquerque, New Mexico",
year = "2018",
month = "2 Oct",
href = "\bibhrefpt{222-exact-fast-parallel-imr-2018}{222-exact-fast-parallel-imr-2018-talk.pdf}",
mykey = "recent marcus salles overlay parallel",
customlinkslides = "https://wrfranklin.org/p/222-exact-fast-parallel-imr-2018-talk.pdf"
}
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 separate 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.
Full text
Read the paperThe full text opens at its existing location.
Preview the full text on this page
Citation
@inproceedings{exact-fast-parallel-imr-2018,
author = "Franklin, W. Randolph and de Magalhães, Salles V. G. and Andrade, Marcus V. A.",
title = "Exact fast parallel intersection of large 3-{D} triangular meshes",
booktitle = "27th International Meshing Roundtable",
address = "Albuquerque, New Mexico",
year = "2018",
month = "2 Oct",
href = "\bibhrefpt{222-exact-fast-parallel-imr-2018}{222-exact-fast-parallel-imr-2018-talk.pdf}",
mykey = "recent marcus salles overlay parallel",
customlinkslides = "https://wrfranklin.org/p/222-exact-fast-parallel-imr-2018-talk.pdf"
}