Fast exact parallel 3D mesh intersection algorithm using only orientation predicates | W. Randolph Franklin, Rensselaer Polytechnic Institute, Troy NY USA

Salles V. G. de Magalhães, W. Randolph Franklin, and Marcus V. A. Andrade. Fast exact parallel 3D mesh intersection algorithm using only orientation predicates. In 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL 2017). Los Angeles Area, CA, USA, 7–10 Nov 2017.
[full text] [slides] [BibTeX▼]

@inproceedings{salles-parallel-mesh-sigspatial-2017,
    author = "de Magalhães, Salles V. G. and Franklin, W. Randolph and Andrade, Marcus V. A.",
    title = "Fast exact parallel {3D} mesh intersection algorithm using only orientation predicates",
    year = "2017",
    month = "7--10 Nov",
    booktitle = "25th {ACM SIGSPATIAL} International Conference on Advances in Geographic Information Systems {(ACM SIGSPATIAL 2017)}",
    address = "{Los Angeles Area, CA, USA}",
    href = "\bibhrefpt{223-salles-parallel-mesh-sigspatial-2017}{223-salles-parallel-mesh-sigspatial-2017-talk.pdf}",
    mykey = "salles marcus parallel",
    customlinkslides = "https://wrfranklin.org/p/223-salles-parallel-mesh-sigspatial-2017-talk.pdf"
}

Abstract

We present an algorithm to compute the intersection of two 3D triangulated meshes. It has applications in GIS, CAD and Additive Manufacturing, and was developed to process big datasets quickly and correctly. The speed comes from simple regular data structures that parallelize very well. The correctness comes from using multiple-precision rational arithmetic to prevent roundoff errors and the resulting topological inconsistencies, and symbolic perturbation (simulation of simplicity) to handle special cases (geometric degeneracies). To simplify the symbolic perturbation, the algorithm employs only orientation predicates. This paper focuses on the challenges and solutions of the implementing symbolic perturbation. Our preliminary implementation has intersected two objects totalling 8M triangles in 11 elapsed seconds on a dual 8-core Xeon. The competing LibiGL took 248 seconds and CGAL took 2726 seconds. Our software is freely available for nonprofit research.

Full Text

[download]