Exact intersection of 3D geometric models | W. Randolph Franklin, Rensselaer Polytechnic Institute, Troy NY USA

Salles V. G. de Magalhães, Marcus V. A. Andrade, W. Randolph Franklin, Wenli Li, and Maurício Gouvêa Gruppi. Exact intersection of 3D geometric models. In Geoinfo 2016, XVII Brazilian Symposium on GeoInformatics. Campos do Jordão, SP, Brazil, November 2016. Instituto Nacional de Pesquisas Espaciais (Brasil).
[full text] [slides] [BibTeX▼]

@inproceedings{salles-xsect-3d-geoinfo-2016,
    author = "de Magalhães, Salles V. G. and Andrade, Marcus V. A. and Franklin, W. Randolph and Li, Wenli and Gruppi, Maurício Gouvêa",
    title = "Exact intersection of {3D} geometric models",
    booktitle = "Geoinfo 2016, {XVII Brazilian} Symposium on GeoInformatics",
    year = "2016",
    month = "November",
    address = "Campos do Jordão, SP, Brazil",
    puburl = "\url{http://www.geoinfo.info/geoinfo\_series.htm}",
    publisher = "Instituto Nacional de Pesquisas Espaciais (Brasil)",
    mykey = "wenlili marcus salles parallel overlay epug-overlay",
    href = "\bibhrefpt{217-salles-xsect-3d-geoinfo-2016}{217-salles-xsect-3d-geoinfo-2016-talk.pdf}",
    customlinkslides = "https://wrfranklin.org/p/217-salles-xsect-3d-geoinfo-2016-talk.pdf"
}

Abstract

This paper presents 3D-EPUG-OVERLAY , an exact and parallel algorithm for computing the intersection of 3D triangulated meshes, a problem with applications in several fields such as GIS and CAD. 3D-EPUG-OVERLAY presents several innovations: it employs exact arithmetic and, thus, the computations are completely exact, which avoids topological impossibilities that are often created by floating point arithmetic. Also, it uses a uniform grid to index the geometric data and was designed to be easily parallelizable. Furthermore, we propose the use of Simulation of Simplicity to effectively ensure that all the special cases are properly handled by the algorithm.

Full Text

[download]