We describe how to implement Simulation of Simplicity (SoS). SoS removes geometric degeneracies in point-in-polygon queries, polyhedron intersection, map overlay, and other 2D and 3D geometric and spatial algorithms by determining the effect of adding non-Archimedian infinitesimals of different orders to the coordinates. Then it modifies the geometric predicates to emulate that, and evaluates them in the usual arithmetic. A geometric degeneracy is a coincidence, such as a vertex of one polygon on an edge of another polygon, that would have probability approaching zero if the objects were distributed i.i.d. uniformly. However, in real data, they can occur often. Especially in 3D, there are too many types of degeneracies to reliably enumerate. But, if they are not handled, then predicates evaluate wrong, and the output topology may be wrong. We describe the theory of SoS, and how several algorithms and programs were successfully modified, including volume of the union of many cubes, point location in a 3D mesh, and intersecting 3D meshes.
@inproceedings{implementing-sos-2022,
author = "Franklin, W. Randolph and de Magalhães, Salles Viana Gomes",
title = "Implementing Simulation of Simplicity for geometric degeneracies",
year = "2022",
month = "1 Nov",
booktitle = "4th {ACM SIGSPATIAL} International Workshop on Spatial Gems ({SpatialGems} 2022)",
location = "Seattle, Washington",
href = "\bibhref{234-implementing-sos-2022}",
mykey = "recent salles parallel overlay"
}
We present several simple representations of polygon and polyhedra that permit the efficient parallel computation of area and volume. They are particularly useful for computing the areas of the nonempty intersections between pairs of faces in two overlapping planar graphs in GIS, or the volumes of nonempty intersections between pairs of tetrahedra in two overlapping triangulations of a polyhedron in CAD. Both applications have been implemented on multicore Intel Xeons and tested on large datasets. The representations store the minimal types of information required for computation, and never need to store edge loops and face shells, or even most adjacency relations. The representations are sets of tuples or small fixed-size sets, and can be processed in parallel with map-reduce operations.
@incollection{minrep-gem-2022,
author = "Franklin, W. Randolph and de Magalhães, Salles Viana Gomes",
editor = "Krumm, John and Züfle, Andreas and Shahabi, Cyrus",
title = "Minimal representations of polygons and polyhedra",
booktitle = "Spatial Gems",
publisher = "ACM",
year = "2022",
volume = "1",
chapter = "5",
mykey = "recent salles overlay topology",
url = "https://www.spatialgems.net/",
href = "\bibhref{241-minrep-gem-2022}"
}
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.
@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"
}
We present several simple representations of polygon and polyhedra that permit the efficient parallel computation of area and volume. They are particularly useful for computing the areas of the nonempty intersections between pairs of faces in two overlapping planar graphs in GIS, or the volumes of nonempty intersections between pairs of tetrahedra in two overlapping triangulations of a polyhedron in CAD. Both applications have been implemented on multicore Intel Xeons and tested on large datasets. The representations store the minimal types of information required for computation, and never need to store edge loops and face shells, or even most adjacency relations. The representations are sets of tuples or small fixed-size sets, and can be processed in parallel with map-reduce operations.
@incollection{minrep-gem-2019,
author = "Franklin, W. Randolph and de Magalhães, Salles Viana Gomes",
editor = "Krumm, John",
title = "Minimal representations of polygons and polyhedra",
booktitle = "1st {ACM SIGSPATIAL} International Workshop on Spatial Gems (SpatialGems 2019)",
publisher = "ACM",
year = "2019",
month = "Nov",
mykey = "recent salles overlay topology",
url = "https://www.spatialgems.net/",
href = "\bibhref{236-minrep-gem-2019}"
}
Parover2 is a parallel algorithm and preliminary implementation to compute the area of every nonempty intersection of any face of one 2D mesh with any face from another mesh over an overlapping domain. This is the hard part of cross-interpolating data from one mesh to another, for when the faces one mesh have an attribute that would be useful for the faces of the other mesh. Parover2, implemented using a map-reduce paradigm in Thrust, can quickly process millions of faces. The expected execution time is linear in the number of intersections, which is usually linear in the number of input faces. A uniform grid quickly determines the pairs of input edges that might intersect. Local topological formulae compute the areas of the output faces from the sets of their (vertex, edge) adjacencies w/o needing to compute the faces' global topologies.
@inproceedings{parover2-vancouver-2019,
author = "Franklin, W. Randolph and de Magalhães, Salles V. G.",
title = "Computing intersection areas of overlaid 2D meshes",
booktitle = "{IGS2019} International Geometry Summit Posters' proceedings",
month = "17--21 June",
address = "Vancouver, Canada",
year = "2019",
publisher = "{Solid Modeling Association}",
href = "\bibhrefpp{231-parover2-vancouver-2019}{231-parover2-vancouver-2019-poster.pdf}",
puburl = "\url{https://igs2019.org/IGS2019-POSTER-PROCEEDINGS-LR.pdf}",
mykey = "recent parallel salles overlay",
customlinkposter = "https://wrfranklin.org/p/231-parover2-vancouver-2019-poster.pdf",
customlinkfastforward = "https://wrfranklin.org/p/231-parover2-vancouver-2019-ff.mp4"
}
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.
@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"
}
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.
@inproceedings{exact-fast-parallel-imr-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",
booktitle = "27th International Meshing Roundtable",
address = "Alberqueque, New Mexico",
year = "2018",
month = "2 Oct",
href = "\bibhrefpt{222-exact-fast-parallel-imr-2018}{222-exact-fast-parallel-imr-2018-talk.pdf}",
mykey = "recent marcus salles overlay parallel",
customlinkslides = "https://wrfranklin.org/p/222-exact-fast-parallel-imr-2018-talk.pdf"
}
We present 3D-EPUG-Overlay, an algorithm and preliminary implementation for intersecting (aka overlaying) two 3D triangulations. This operation is important in processing large geometry datasets in additive manufacturing. Much of our algorithm is a sequence of map-reduce operations, and so is easily parallelizable. We completely avoid roundoff errors and the associated topological problems by computing with rational numbers. We will handle geometric degeneracies with Simulation of Simplicity (SoS). Our target architecture is an inexpensive workstation. We have a complete 2D implementation, which has overlaid two 2D maps maps, with a total of 54,000,000 vertices and 739,000 faces, in only 322 elapsed seconds (excluding I/O) on a dual 8-core 3.4GHz Intel Xeon workstation. That time is using 16 cores, and is 11x faster than using one core. Our 3D implementation is complete except for SoS. It processes two 3D objects with a total of 6,000,000 face triangles and 3,000,000 tetrahedra in 180 elapsed seconds on 16 cores. The parallel speedup for 16 cores is a factor of 13. The execution time is almost linear in the data size, and could process much larger datasets, perhaps billions of triangles. We anticipate being able to process much larger datasets than competing SW can, and for datasets small enough for others to process, that we will be much faster and more robust on special cases.
@inproceedings{x3d-epug-siam-2017,
author = "Franklin, W. Randolph and de Magalhães, Salles V. G. and Andrade, Marcus V. A.",
title = "{3D-EPUG-Overlay}: Intersecting very large {3D} triangulations in parallel",
booktitle = "2017 {SIAM} conference on industrial and applied geometry",
year = "2017",
month = "10--12 July",
address = "Pittsburgh PA USA",
note = "(talk)",
href = "\bibhrefat{219-3d-epug-siam-2017-abs}{219-3d-epug-siam-2017.pdf}",
mykey = "overlay parallel marcus salles epug-overlay",
customlinkslides = "https://wrfranklin.org/p/219-3d-epug-siam-2017.pdf"
}
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.
@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"
}
2016
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).
[abstract▼] [details] [full text] [slides]
[BibTeX▼]
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.
@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"
}
@misc{local-talk-gatech-2016,
author = "Franklin, W. Randolph and de Magalhães, Salles Viana Gomes",
title = "Local topology and parallel overlaying large planar graphs",
note = "Talk at Georgia Tech, School of Interactive Computing. Also given at IBM Haifa, Microsoft Haifa, Ben Gurion U, and Tel Aviv U in Dec 2015",
month = "15 Feb",
year = "2016",
href = "\bibhreft{208-local-talk-gatech-2016.pdf}",
customlinkslides = "https://wrfranklin.org/p/208-local-talk-gatech-2016.pdf",
mykey = "salles overlay topology parallel"
}
We present EPUG-Overlay (Exact Parallel Uniform Grid Overlay), an algorithm to overlay two maps that is fast and parallel, has no roundoff errors, and is freely available. EPUG-Overlay combines several novel aspects. It represents coordinates with rational numbers, thereby ensuring exact computations with no roundoff errors and the ensuing sliver problems and topological impossibilities. For efficiency, EPUG-Overlay performs the map overlay in parallel, thereby utilizing the ubiquitous multicore architecture. Our application goes beyond merely using existing packages, which are inefficient when used in parallel on large problems. Indeed, overlaying two maps with 53,000,000 edges and 730,000 faces took only 322 elapsed seconds (plus 116 seconds for I/O) on a dual 8-core 3.1 GHz Intel Xeon E5-2687 workstation. In contrast, GRASS, executing sequentially and generating roundoff errors, takes 5300 seconds. The overlay operation combines two input maps (planar graphs) containing faces (polygons) separated by polyline edges (chains), into a new map, each of whose faces is the intersection of one face from each input map. Floating point roundoff errors can cause an edge intersection to be missed or the computed intersection point be in a wrong face, leading to a topological inconsistency. Thus, a program might fail to compute a valid output map at all, using any amount of time. This gets worse when the inputs are bigger or have slivers. Heuristics can ameliorate this problem, but only to an extent. By representing each coordinate as a vulgar fraction, with multiprecision numerator and denominator, the computation is exact. EPUG-Overlay also executes various useful subproblems very quickly, such as locating a set of points in a planar graph and finding all the intersections among a large set of small edges. EPUG-Overlay is built on our earlier sequential floating-point algorithm that found the areas of the overlay polygons, without finding the polygons themselves.
@inproceedings{salles-overlay-bigspatial-2015,
author = "de Magalhães, Salles V. G. and Andrade, Marcus V. A. and Franklin, W. Randolph and Li, Wenli",
title = "Fast exact parallel map overlay using a two-level uniform grid",
booktitle = "4th {ACM SIGSPATIAL} International Workshop on Analytics for Big Geospatial Data (BigSpatial)",
year = "2015",
month = "3 Nov",
address = "Bellevue WA USA",
href = "\bibhref{196-salles-overlay-bigspatial-2015}",
doi = "https://doi.org/10.1145/2835185.2835188",
mykey = "wenlili marcus salles overlay parallel"
}
@inproceedings{salles-overlay-fwcg-2015,
author = "de Magalhães, Salles V. G. and Franklin, W. Randolph and Andrade, Marcus V. A. and Li, Wenli",
title = "An efficient algorithm for computing the exact overlay of triangulations",
booktitle = "25th Fall Workshop on Computational Geometry",
year = "2015",
month = "23-24 Oct",
address = "U. Buffalo, New York, USA",
note = "(extended abstract)",
mykey = "wenlili marcus salles overlay",
href = "\bibhref{201-salles-overlay-fwcg-2015}"
}
@article{fsskn-ofmop-93,
author = "Franklin, Wm Randolph and Sivaswami, Venkateshkumar and Sun, David and Kankanhalli, Mohan and Narayanaswami, Chandrasekhar",
title = "Calculating the Area of Overlaid Polygons Without Constructing the Overlay",
year = "1994",
month = "April",
pages = "81--89",
journal = "Cartography and Geographic Information Systems",
succeeds = "f-cmopa-90",
mykey = "overlay kankanhalli chandra",
keywords = "intersection, grids, area",
href = "\bibhref{81-cagis94-overlay}"
}
1993
Wm Randolph Franklin and Mohan S. Kankanhalli.
Volumes from overlaying 3-D triangulations in parallel.
In D. Abel and B.C. Ooi, editors, Advances in Spatial Databases: Third Intl. Symp., SSD'93, volume 692 of Lecture Notes in Computer Science, pages 477–489.
Springer-Verlag, June 1993. [details] [full text]
[BibTeX▼]
@incollection{fk-vo3tp-93,
author = "Franklin, Wm Randolph and Kankanhalli, Mohan S.",
editor = "Abel, D. and Ooi, B.C.",
title = "Volumes From Overlaying 3-{D} Triangulations in Parallel",
booktitle = "Advances in Spatial Databases: Third Intl. Symp., SSD'93",
publisher = "Springer-Verlag",
month = "June",
year = "1993",
series = "Lecture Notes in Computer Science",
volume = "692",
pages = "477--489",
comment = "SSD = Symp on Large Spatial DBs, Singapore",
href = "\bibhref{78-ssd93-tet}",
keywords = "parallel computation, intersection, volume, CAD",
mykey = "kankanhalli overlay parallel"
}
@inproceedings{fs-ocamo-90-in-geom,
author = "Franklin, Wm Randolph and Sivaswami, Venkatesh",
title = "{OVERPROP} --- Calculating Areas of Map Overlay Polygons without Calculating the Overlay",
booktitle = "Canadian National Conference on Geographic Information Systems: Challenge for the 1990's",
publisher = "Canadian Institute of Surveying and Mapping",
address = "Ottawa",
pages = "1646--1654",
month = "5-8 Mar",
year = "1990",
href = "\bibhref{61-ottawa90-overlay}",
mykey = "overlay",
keywords = "intersection, area, grids"
}
@mastersthesis{sivaswami-ms,
author = "Sivaswami, Venkateshkumar",
title = "Point inclusion testing in polygons and point location in planar graphs using the uniform grid technique",
school = "Rensselaer Polytechnic Institute, Electrical, Computer, and Systems Engineering Dept.",
year = "1990",
month = "May",
mykey = "overlay"
}
1987
Wm Randolph Franklin and Peter YF Wu.
A polygon overlay system in prolog.
In Autocarto 8: Proceedings of the Eighth International Symposium on Computer-Assisted Cartography, 97–106. Baltimore, Maryland, 29 Mar – 3 April 1987. [details] [full text]
[BibTeX▼]
@inproceedings{fw-posp-87,
author = "Franklin, Wm Randolph and Wu, Peter YF",
title = "A Polygon Overlay System in Prolog",
booktitle = "Autocarto 8: Proceedings of the Eighth International Symposium on Computer-Assisted Cartography",
address = "Baltimore, Maryland",
month = "29 Mar -- 3 April",
year = "1987",
pages = "97--106",
href = "\bibhref{45-autocarto87-overlay-prolog}",
mykey = "overlay",
keywords = "intersection, artificial intelligence"
}
Overpropf overlays two maps (aka planar graphs), and computes the areas of all the nonempty intersections of any polygon of one map with any polygon of the other.
One application is to interpolate some statistic of one map over to the other. E.g., we might have the population of each polygon of one map, and wish to estimate the polygon of each polygon of the other map from the fractions of intersected areas.
It is very fast because it uses my uniform grid and my local topological formulae.