The best URL for this page is https://wrfranklin.org/ aka httpsCOLONSLASHSLASHwrfranklinDOTorg. Some mail systems rewrite URLs in the body of messages, so my email signature block can be made wrong.
Email is the best way to contact me; e.g., at web23ATwrfranklinDOTorg. I have many addresses; a surprising failure mode is a correspondent combining the user and hostname from two different addresses. Even that works when I own the domain.
For the past 2 years, I've been a private sponsor of several GIS and geometry related conferences that I've enjoyed attending, and benefited from, over the decades. They include-
Sponsored the travel of ten GIS Cup winners and international students. The reasons were to raise interest in the contest, in which my students and I came first in 2018 second in 2015 and 2016, and hence raise interest in this field, and to encourage international students to continue in this field.
I created this course based on my interests and skills, and taught it up to Fall 2022. It was great fun. Unfortunately it's unlikely to be offered again, because I retired (at age 70). However, ECSE is trying to run a similar course. If you are an RPI student who is interested, tell ECSE. My material is freely available for nonprofit research and education; I welcome a note if you find it useful.
My current big unsolved problem is to use Nvidia GPUs to compute the volumes of all the nonempty intersections between the tetrahedra in two different 3D triangulations of the same polyhedron.
Generally, I develop and implement fast parallel algorithms on very large geometric datasets in CAD and GIS. I've also modeled and processed large terrain databases, e.g., to compress, to compute hydrography and visibility, and to site observers, and compressed 5D environmental data sets. The algorithms are the fastest in their class; awards are listed below.
This paper presents a technique for employing high-performance computing for accelerating the exact evaluation of geometric predicates. Arithmetic filters are implemented using interval arithmetic to reduce the necessity of exact arithmetic while ensuring the results of the predicates are still exact. Furthermore, the computation with interval arithmetic is offloaded to a CUDA-enabled GPU. If the GPU detects that some results cannot be trusted, the corresponding predicates are re-evaluated in parallel on the CPU using arbitrary-precision rational numbers. As a case study, a red-blue 3D triangle intersection algorithm has been implemented. Since the intervals are implemented using floating-point numbers, the parallel computing power of GPUs for processing these numbers led to a speedup of up to 1936 times (when compared against a similar sequential implementation) in the evaluation of these predicates (and up to 414 times if the entire runnning-time of the algorithm is considered). The excellent performance associated to the exactness makes this technique suitable for accelerating geometric operations in fields such as CAD, GIS and 3D modeling.
@article{marcelo-gpu-predicates-2021,
author = "de Matos Menezes, Marcelo and Magalhães, Salles Viana Gomes and de Oliveira, Matheus Aguilar and Franklin, W. Randolph and de Oliveira Bauer Chichorro, Rodrigo Eduardo",
editor = "Peiro, Joaquim and Shontz, Suzanne and Viertel, Ryan",
title = "Fast parallel evaluation of exact geometric predicates on {GPU}s",
month = "September",
year = "2022",
number = "103285",
note = "Special Issue: 28th International Meshing Roundtable: Mesh Modeling for Simulations and Visualization",
journal = "J. Computer Aided Design",
doi = "https://doi.org/10.1016/j.cad.2022.103285",
href = "\bibhref{239-marcelo-gpu-predicates-2021}",
mykey = "recent salles marcelo matheus rodrigo parallel topology",
url = "https://www.sciencedirect.com/science/article/abs/pii/S0010448522000616"
}
This paper presents a technique to use GPUs to accelerate the computation of 3D geometric predicates. A common predicate is computing the orientation of four 3D points, which is a subproblem in applications such as intersecting two 3D meshes. Since the higher level application may require billions of evaluations, efficiency is important. Accuracy is required since floating roundoff errors can cause topological impossibilities. One solution is to compute with rational numbers, but that is difficult to implement on a GPU because rationals' sizes vary. Our solution is to compute on the GPU with interval arithmetic, but fall back to using rationals on the CPU if the interval computed on the GPU includes the origin; i.e., its sign is unknown. Our experiment with a dataset of hard rock mining drill holes show that this fallback to the CPU is rarely necessary; so that our technique gave a 17 times speedup compared to a sequential implementation.
@incollection{marcelo-employing-gem-2022,
author = "de Matos Menezes, Marcelo and de Magalhães, Salles Viana Gomes and Aguilar, Matheus and Franklin, W. Randolph and Coelho, Bruno",
editor = "Krumm, John and Züfle, Andreas and Shahabi, Cyrus",
title = "Employing {GPU}s to accelerate exact geometric predicates for {3D} geospatial PROCESSING",
booktitle = "Spatial Gems",
publisher = "ACM",
year = "2022",
volume = "1",
chapter = "11",
mykey = "recent salles marcelo matheus bruno parallel topology",
url = "https://www.spatialgems.net/",
href = "\bibhref{242-marcelo-employing-gem-2022}"
}
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 describe how to implement Simulation of Simplicity (SoS). SoS removes geometric degeneracies in 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 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 = "November",
booktitle = "Spatial Gems 2022 (ACM SIGSPATIAL)",
location = "Seattle, Washington",
href = "\bibhref{234-implementing-sos-2022}",
mykey = "recent salles parallel overlay"
}
We present an efficient algorithm, with implementations, for computing the connected components within a 3-D cube of voxels, also known as the Euclidean union-find problem. There may be over $10^9$ voxels. The components may be 8-connected or 26-connected. Computing connected components has applications ranging from material failure in concrete under increasing stress to electrical conductivity in complex metal objects to elasticity in 3D printed parts. On key to efficiency is representing voxels by 1-D \emphruns of adjacent voxels. As a special case, 2-D connected components of images may easily be computed.
@incollection{connect-gem-2021,
author = "Franklin, W. Randolph and de Magalhães, Salles Viana Gomes and Landis, Eric N",
editor = "Krumm, John",
title = "Fast {3-D} {Euclidean} connected components",
booktitle = "3rd {ACM SIGSPATIAL} International Workshop on Spatial Gems (SpatialGems 2021)",
publisher = "ACM",
year = "2021",
month = "2 nov",
location = "Beijing, China (virtual)",
mykey = "recent salles landis connect topology 2021",
url = "https://www.spatialgems.net/",
href = "\bibhref{240-connect-gem-2021}"
}
This paper presents a system that sites (finds optimal locations for) thousands of radio transmitter towers on terrains of up to two billion elevation posts. Applications include cellphone towers, camera systems, or even mitigating environmental visual nuisances. The transmitters and receivers may be situated above the terrain. The system has been parallelized with OpenMP to run on a multicore CPU.
@misc{siting-thousands-2020,
author = "Franklin, W. Randolph and de Magalhães, Salles Viana Gomes and Li, Wenli",
title = "Siting thousands of radio transmitter towers on terrains with billions of points",
year = "2020",
eprint = "2006.16783",
archivePrefix = "arXiv",
primaryClass = "eess.SP",
note = "arXiv 2006.16783",
href = "\bibhref{237-siting-thousands-2020}",
mykey = "recent salles parallel visibility visviewshedsiting wenlili"
}
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}"
}
This paper presents a technique for employing high-performance computing for accelerating the exact evaluation of geometric predicates. Arithmetic filters are implemented using interval arithmetic to reduce the necessity of exact arithmetic while ensuring the results of the predicates are still exact. Furthermore, the computation with interval arithmetic is offloaded to a CUDA-enabled GPU. If the GPU detects that some results cannot be trusted, the corresponding predicates are re-evaluated in parallel on the CPU using arbitrary-precision rational numbers. As a case study, a red-blue segment intersection algorithm has been implemented. Since the intervals are implemented using floating-point numbers, the parallel computing power of GPUs for processing these numbers led to a speedup of up to 289 times (when compared against a similar sequential implementation) in the evaluation of these predicates (and up to 40 times if the entire running-time of the algorithm is considered). The excellent performance associated to the exactness makes this technique suitable for accelerating geometric operations in fields such as CAD, GIS, VLSI design and meshing.
@inproceedings{marcelo-gpu-geometry-imr-2019,
author = "de Matos Menezes, Marcelo and Magalhães, Salles Viana Gomes and Franklin, W. Randolph and de Oliveira, Matheus Aguilar and Chichorro, Rodrigo E. O. Bauer",
editor = "Shontz, Suzanne and Peiró, Joaquim and Viertel, Ryan",
title = "Accelerating the exact evaluation of geometric predicates with {GPU}s",
booktitle = "28th International Meshing Roundtable",
month = "16 Oct",
address = "Buffalo, NY, USA",
year = "2019",
isbn = "978-1-7334890-0-3",
doi = "10.5281/zenodo.3653101",
href = "\bibhrefpt{235-marcelo-gpu-geometry-imr-2019}{235-marcelo-gpu-geometry-imr-2019-talk.pdf}",
mykey = "recent salles parallel",
customlinkslides = "https://wrfranklin.org/p/235-marcelo-gpu-geometry-imr-2019-talk.pdf"
}
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 a fast linear time algorithm that uses a block-cut tree for identifying upstream features from a set of starting points in a network. Our implementation has been parallelized and it can process a dataset with 32 million features in less than 8 seconds on a 8-core workstation. This problem is the 2018 ACM SIGSPATIAL CUP challenge and presents several applications mainly on the field of utility networks. Our code is freely available for nonprofit research and education at https://github.com/sallesviana/FastUpstream
@inproceedings{salles-giscup-2018,
author = "de Magalhães, Salles Viana Gomes and Franklin, W. Randolph and dos Santos Ferreira, Ricardo",
title = "Fast Analysis of Upstream Features on Spatial Networks {(GIS Cup)}",
note = "Winner (1st place)",
booktitle = "Proceedings of the 26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems",
series = "SIGSPATIAL '18",
year = "2018",
isbn = "978-1-4503-5889-7",
location = "Seattle, Washington",
pages = "622--625",
numpages = "4",
acmid = "3276474",
publisher = "ACM",
address = "New York, NY, USA",
keywords = "GISCUP, graph algorithms, parallel programming, spatial networks",
href = "\bibhrefpt{228-salles-giscup-2018}{228-salles-giscup-2018-talk.pdf}",
customlinkslides = "https://wrfranklin.org/p/228-salles-giscup-2018-talk.pdf",
mykey = "recent salles parallel sallesgiscup2018",
doi = "https://doi.org/10.1145/3274895.3276474"
}
This paper describes data structures and algorithms for efficient implementation of GIS operations for large datasets on multicore Intel CPUs and on NVIDA GPUs. Typical operations are boolean combinations of polygons and map overlay. Efficient parallelization prefers simple regular data structures, such as structures of arrays of plain old datatypes. Warps of 32 threads are required to execute the same instruction (or be idle). Ideally, the data used by adjacent threads is adjacent in memory. Minimizing storage is important, as is accessing it in a regular pattern. That disparages pointers, linked lists, and trees. That implies that explicitly representing global topology is bad. If using only local topological formulae is sufficient, then it will be much faster. E.g., for many operations on a 2-D map (aka planar graph), the set of oriented edges suffices. Each edge knows the locations of its endpoints and the ids of its adjacent polygons. Any mass operation, such as area computation or point location, can be implemented as a map-reduce. All these techniques also apply in 3D to CAD/CAM and additive manufacturing. Indeed they are more important there.
@inproceedings{par-ds-bigspatial-2018,
author = "Franklin, W. Randolph and de Magalhães, Salles V. G. and Andrade, Marcus V. A.",
title = "Data Structures for Parallel Spatial Algorithms on Large Datasets (Vision paper)",
address = "Seattle, {USA}",
month = "6 Nov",
booktitle = "Proceedings of {BigSpatial'18}: 7th {ACM SIGSPATIAL} Workshop on Analytics for Big Geospatial Data",
year = "2018",
href = "\bibhrefpt{227-par-ds-bigspatial-2018}{227-par-ds-bigspatial-2018-talk.pdf}",
customlinkslides = "https://wrfranklin.org/p/227-par-ds-bigspatial-2018-talk.pdf",
mykey = "recent marcus salles topology parallel"
}
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"
}
2017
W. Randolph Franklin.
Applications of geometry.
In Kenneth H Rosen, editor, Handbook of Discrete and Combinatorial Mathematics, Discrete Mathematics and Its Applications, chapter 13.8, pages 998–1022.
CRC Press, 2nd edition, 1 Dec 2017.
[abstract▼] [details] [full text]
[BibTeX▼]
Geometry overlays the entire computing spectrum, having applications in almost every area of science and engineering, including astrophysics, molecular biology, mechanical design, fluid mechanics, computer graphics, computer vision, geographic information systems, robotics, multimedia, and mechanical engineering. The growing availability of large geometric databases is a major driver of the increase in applications. GIS mapping databases containing most of the world's roads enable route planning applications. Airborne LIDAR creates terrain elevation databases. That enables observer visibility computation, with applications ranging from radio tower siting to visual nuisance mitigation. Laser scanners produce 3D point clouds recording the surfaces of objects from buildings down to sculptures and even people. The ensuing applications include deducing the structure of those objects' surfaces.
@incollection{handbook-geoapps-2017,
author = "Franklin, W. Randolph",
editor = "Rosen, Kenneth H",
title = "Applications of Geometry",
booktitle = "Handbook of Discrete and Combinatorial Mathematics",
edition = "2nd",
series = "Discrete Mathematics and Its Applications",
pages = "998--1022",
publisher = "{CRC} Press",
year = "2017",
month = "1 Dec",
chapter = "13.8",
mykey = "recent",
isbn = "9781584887805",
href = "\bibhref{230-handbook-geoapps-2017}",
puburl = "https://www.crcpress.com/Handbook-of-Discrete-and-Combinatorial-Mathematics-Second-Edition/Rosen/p/book/9781584887805"
}
Professional summary
Professor, ECSE Dept, RPI
BSc (Toronto)
AM, PhD, Applied Math (Harvard)
Program Director, Numeric, Symbolic, and Geometric Computation Program, CISE, National Science Foundation, 2000—2002
Visiting Professor, UC Berkeley, 1985—1986
Visiting positions at Genoa, Laval, CSIRO Canberra, National University of Singapore, 1992—1993.
Long resume
— (Education - Professional Career - Publications - Presentations - Synergistic Activities and Service - Grad Students - Teaching or Course Development - Hardware Used - Professional Memberships - Major Research Grants), including postal address, email (GPG welcomed), phone
