W. Randolph Franklin, Salles V. G. de Magalhães, and Marcus V. A. Andrade.
Exact fast parallel intersection of large 3-D triangular meshes (extended abstract).
In 28th Annual Fall Workshop on Computational Geometry. Queens College, CUNY, New York City, 26–27 Oct 2018.
[full text]
BibTeX
@inproceedings{exact-fast-parallel-fwcg-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 (extended abstract)",
booktitle = "28th Annual Fall Workshop on Computational Geometry",
address = "Queens College, {CUNY}, New York City",
year = "2018",
month = "26--27 Oct",
href = "\bibhref{229-exact-fast-parallel-fwcg-2018}",
mykey = "recent marcus salles overlay parallel topology"
}
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 at https://github.com/sallesviana/MeshIntersection . The full version of this paper is being presented at the 2018 International Meshing Roundtable; it is currently online at https://project.inria.fr/imr27/files/2018/09/1035.pdf.
Full text
Read the paperThe full text opens at its existing location.
Preview the full text on this page
Citation
@inproceedings{exact-fast-parallel-fwcg-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 (extended abstract)",
booktitle = "28th Annual Fall Workshop on Computational Geometry",
address = "Queens College, {CUNY}, New York City",
year = "2018",
month = "26--27 Oct",
href = "\bibhref{229-exact-fast-parallel-fwcg-2018}",
mykey = "recent marcus salles overlay parallel topology"
}