Salles V. G. de Magalhães, W. Randolph Franklin, and Marcus V. A. Andrade.
An efficient and exact parallel algorithm for intersecting large 3-d triangular meshes using arithmetic filters.
J. Computer Aided Design, March 2020.
online 2019-12-19.
doi:https://doi.org/10.1016/j.cad.2019.102801.
[full text]
BibTeX
@article{salles-exact-cad-2019,
author = "de Magalhães, Salles V. G. and Franklin, W. Randolph and Andrade, Marcus V. A.",
title = "An efficient and exact parallel algorithm for intersecting large 3-D triangular meshes using arithmetic filters",
journal = "J. Computer Aided Design",
note = "online 2019-12-19",
year = "2020",
month = "March",
volume = "120",
doi = "https://doi.org/10.1016/j.cad.2019.102801",
href = "\bibhref{232-salles-exact-cad-2019}",
mykey = "recent marcus salles parallel overlay"
}
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.
Full text
Read the paperThe full text opens at its existing location.
Preview the full text on this page
Citation
@article{salles-exact-cad-2019,
author = "de Magalhães, Salles V. G. and Franklin, W. Randolph and Andrade, Marcus V. A.",
title = "An efficient and exact parallel algorithm for intersecting large 3-D triangular meshes using arithmetic filters",
journal = "J. Computer Aided Design",
note = "online 2019-12-19",
year = "2020",
month = "March",
volume = "120",
doi = "https://doi.org/10.1016/j.cad.2019.102801",
href = "\bibhref{232-salles-exact-cad-2019}",
mykey = "recent marcus salles parallel overlay"
}