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

W. Randolph Franklin, Salles V. G. de Magalhães, and Marcus V. A. Andrade. An exact and efficient 3D mesh intersection algorithm using only orientation predicates. In S3PM-2017: International Convention on Shape, Solid, Structure, & Physical Modeling, Shape Modeling International (SMI-2017) Symposium. Berkeley, California, USA, 19–23 June 2017. (poster).
[poster] [BibTeX▼]

@inproceedings{mesh-orientation-s3pm-2017,
    author = "Franklin, W. Randolph and de Magalhães, Salles V. G. and Andrade, Marcus V. A.",
    title = "An exact and efficient {3D} mesh intersection algorithm using only orientation predicates",
    booktitle = "{S3PM-2017}: International Convention on Shape, Solid, Structure, \\& Physical Modeling, Shape Modeling International {(SMI-2017)} Symposium",
    month = "19--23 June",
    address = "Berkeley, California, USA",
    host = "International Computer Science Institute",
    year = "2017",
    note = "(poster)",
    href = "\bibhrefap{}{220-mesh-orientation-s3pm-2017.pdf}",
    mykey = "parallel marcus salles overlay epug-overlay",
    customlinkposter = "https://wrfranklin.org/p/220-mesh-orientation-s3pm-2017.pdf"
}

Abstract

We present an algorithm to compute the intersection of two 3D triangulated meshes. It has applications in CAD and Additive Manufacturing, and was developed to process the largest 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.