We develop and implement fast parallel algorithms on very large geometric datasets. Applications include CAD and GIS. Parallel tools include CUDA and OpenMP. HW includes dual 28-core Intel Xeon with 256GB of main memory, Intel Xeon Phi, and Nvidia GTX 1080. The algorithms are the fastest in their class; awards are listed below.

**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.

My 17 PhD and 70 masters students (who graduated).

Brief Bio — GPG key (I welcome GPG-encrypted email.) — Vcard

*including postal address, email (GPG welcomed), phone*

Teaching, Teaching Techniques 2016.

**Search my wiki:** You can search my wiki by using the search box at the top
right of most pages. (This does not search my pages that are not part of
the wiki, such as pages over 10 years old. However, google works there.)

ECSE-4750 Computer Graphics Fall 2016.

For researchers: A preliminary list of our **available software** is at http://wrfranklin.org/Software

Office hours:

- Mon and Thurs 3pm in JEC6026 (usually). If it's something important, you're welcome to email first.
- After almost every Computer Graphics class, I stay as long as there are questions. That would be Mon and Thurs in Darrin (aka DCC aka CC) 324 about 5:30 and Wed in Sage 5101 about 7:30.
- If you just want a form signed then just before class also works. That's Mon and Thurs 3:50 in DCC324 and Wed 5:50 in Sage 5101.
- If none of those times are convenient then email to discuss another time. Mon, Wed, and Thurs afternoons are best.
- If you'd like a form signed, then pin it by my door JEC6026. Do not slide it under the door.
- If you me a PDF of the form; I'll email back a PDF of the signed form.

Click on a heading below to expand that section. Expand all sections below Hide all sections below

## 2016 Papers and Talks

- Wenli Li, W. Randolph Franklin, Salles V. G. Magalhães, Marcus V. A. Andrade and David L. Hedin.
**3D Segmented ODETLAP Compression**. In*(submitted)*, 2016.*(paper).* - David Hedin and W. Randolph Franklin.
**NearptD: A Parallel Implementation of Exact Nearest Neighbor Search using a Uniform Grid**. In*Canadian Conference on Computational Geometry*, Vancouver Canada, Aug 2016.*(paper).* - W. Randolph Franklin.
**Minimum spatial representations**. , 2016.*(unpublished)*.*(paper).* - Salles V. G. Magalhães, Marcus V. A. Andrade , W. Randolph Franklin and Wenli Li.
**PinMesh -- Fast and exact 3D point location queries using a uniform grid**.*Computer & Graphics Journal, special issue on Shape Modeling International 2016*. doi: 10.1016/j.cag.2016.05.017, 2016.*(http://www.sciencedirect.com/science/article/pii/S0097849316300607 online 17 May). Awarded a reproducibility stamp, http://www.reproducibilitystamp.com/.*.*(paper, talk).* - Chaulio R. Ferreira, Marcus V. A. Andrade, Salles V. G. Magalhães and W. Randolph Franklin.
**An efficient external memory algorithm for terrain viewshed computation**.*ACM Trans. on Spatial Algorithms and Systems*, 2(2). doi: 10.1145/2903206, 2016.*(paper).* - W. Randolph Franklin and Salles Viana Gomes de Magalhães.
**Local topology and parallel overlaying large planar graphs**. , 15 Feb 2016.*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*.*(talk).* - Max J Egenhofer, Keith C Clarke, Song Gao, Teriitutea Quesnot, W. Randolph Franklin, May Yuan and David Coleman.
**Contributions of GIScience over the Past Twenty Years**. In Harlan Onsrud and Werner Kuhn, editor,*Advancing Geographic Information Science: The Past and Next Twenty Years*, chapter 1, pages 9-34. GSDI association press. 978-0-9852444-4-6, 2016.*(paper).* - Mehrad Kamalzare, Thomas F. Zimmie, Barbara Cutler and W. Randolph Franklin.
**A New Visualization Method to Evaluate Sediment Transport and Erosion**.*Geotechnical Testing Journal*, 39(3). doi: 10.1520/GTJ20140226, May 2016.*(paper).*

## Paper and Talk Awards

- Awarded a Reproducibility Stamp at the International Geometry Summit 2016.
Salles V. G. Magalhães, Marcus V. A. Andrade , W. Randolph Franklin and Wenli Li.
**PinMesh -- Fast and exact 3D point location queries using a uniform grid**.*Computer & Graphics Journal, special issue on Shape Modeling International 2016*. doi: 10.1016/j.cag.2016.05.017, 2016.*(http://www.sciencedirect.com/science/article/pii/S0097849316300607 online 17 May). Awarded a reproducibility stamp, http://www.reproducibilitystamp.com/.*.*(paper, talk).* - Winner (2nd place),
**GISCUP 2015**: Salles V. G. Magalhães, Marcus V. A. Andrade, W. Randolph Franklin and Wenli Li.**Fast path planning under polygonal obstacle constraints**. In*4th GIS-focused algorithm competition, GISCUP 2015, co-located with ACM SIGSPATIAL GIS*, Bellevue WA USA, 4 Nov 2015.*(paper).* - Winner of the Best Paper Award (2nd place),
**AGILE 2012**: Salles V. G. Magalhães, Marcus V. A. Andrade, W. Randolph Franklin and Guilherme C. Pena.**A new method for computing the drainage network based on raising the level of an ocean surrounding the terrain**. In Jérome Gensel and Didier Josselin and Danny Vandenbroucke, editor,*Bridging the Geographic Information Sciences: International AGILE'2012 Conference*, pages 391-407. Springer. 978-3-642-29062-6, 24-27 April 2012. (URL)*(paper, talk).* - Winner of best paper award,
**Geoinfo 2013**: Chaulio R. Ferreira, Marcus V. A. Andrade, Salles V. G. Magalhães, W. R. Franklin and Guilherme C. Pena.**A Parallel Sweep Line Algorithm for Visibility Computation**. In*Geoinfo 2013, XIV Brazilian Symposium on GeoInformatics*, Campos do Jordão, SP, Brazil, 24-27 Nov 2013.*(paper).* - Winner of the best fast forward presentation award,
**ACM SIGSPATIAL GIS 2009**: Tsz-Yam Lau, You Li, Zhongyi Xie and W. Randolph Franklin.**Sea Floor Bathymetry Trackline Surface Fitting Without Visible Artifacts Using ODETLAP**. In*17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS 2009)*, Seattle WA USA, 4-6 Nov 2009.*(paper, video, talk: pptx, pdf, poster: pptx, pdf).*

## Research Summary

**Geometry** has been my overriding interest since high
school in the 1960s. Geometry is the "branch of mathematics
that deals with the measurement, properties, and
relationships of points, lines, angles, surfaces, and
solids"
(Merriam–Webster dictionary). The *Geo* in geometry
is from the Greek Γη meaning, ''earth, ground,
land''. (The American Heritageï¿½ Book of English Usage). My major
recently concluded project was
*Geo**, a DARPA–funded project for
representing and operating on terrain, that is, elevation.

My big long-term unsolved problem is to devise a **mathematics of terrain**, which would respect its physical properties. To date, I've been nibbling around the edges.

One recently ended project (Cutler, Zimmie, Franklin. NSF CMMI-0835762: CDI-Type I: Fundamental Terrain Representations and Operations) attempted to predict how erosion occurs in levee failure by overtopping, and, after a failure, to reverse-simulate what happened.

A earlier major project was *Geo**, funded by DARPA,
studied representing and operating on terrain, that is, elevation.

I've applied the same underlying principles in Computational Geometry producing algorithms useful for large datasets, mostly in 3D, and usually implemented.

Both topics are applications of my long term theme of
emphasizing small, simple, and fast data structures and
algorithms. Note that efficiency in both space and time can
become *more* important as machines get faster. This
research is applicable to computational cartography,
computer graphics, computational geometry, and geographic
information science.

17 PhD students (7 currently employed at a college), and
70 masters students have been graduated under my
advisement,
*(names and theses or projects)*.

My research has been externally funded by the National Science Foundation under Grants ENG-7908139, ECS-8021504, ECS-8351942, CCF-9102553, CCF-0306502, DMS-0327634, CMMI-0835762 and IIS-1117277 by DARPA/DSO, via the NGA, under the GeoStar program, by the US Army Topographic Engineering Center, and by IBM, Sun Microsystems, and Schlumberger-Doll Research.

Many of the algorithms have been implemented. The code is available for nonprofit research and education. RPI Computer graphics group

- A
**2-slide summary**of my research is here. - A good summary talk is this:

*Geometric Operations on Millions of Objects*.

- An overview talk of the future of the field is my keynote talk at GeoInfo 2013, XIV Brazilian Symposium on GeoInformatics.
- Some research results that I particularly like are here.

## Research on Overlaying 3D Meshes

The main goal is to overlay two 3D meshes to produce a new mesh, where each output tetrahedron is part of the intersection of two input tetrahedra, one from each input mesh. Secondary goals are to process meshes with tens of millions of tetrahedra with an expected time linear in the input size. We will achieve this by combining give techniques.

- minimal geometric representations, for simplicity and parallelizability,
- uniform grid, for fast intersection detection,
- rational numbers, to prevent roundoff errors,
- Simulation of Simplicity, to handle degeneracies, and
- OpenMP, for parallel speedup.

We have already overlaid two 2D meshes (aka embedded planar graphs). Our big example combined US Water Bodies with US Block Boundaries, which total 54,000,000 vertices, and 737,000 faces. This took only 149 elapsed seconds (plus 116s for I/O).

We have also implemented PinMesh, which locates a point in a 3D mesh, again combining the above five techniques. Its preprocessing time is linear and query time constant. The largest test case had 50M faces. Preprocessing took 14 seconds on a dual 8-core Xeon, while querying averaged 0.6 microseconds per point. This work won a reproducability stamp at the International Geometry Summit 2016.

Both programs are freely available to other nonprofit researchers and educators. Both programs scale up and scale down. They could process orders-of-magnitude larger datasets, if those were available. On much smaller datasets, they achieve sub-second performance.

This is Salles Viana Gomez de Magalhaes's PhD thesis.

## Research on Lossily Compressing 3D Datasets

The goal is to lossily compress 3D arrays of environmental data. For a given maximum error, our compressed file is typically 1/3 the size of that produced by JP3D. The data size is up to 160x256x256. Our ideas also extend to 4D and higher datasets.

The original motivation was to interpolate raster terrain surfaces from elevation contours. Existing techniques had many problems. The input contours were visible as terraces in the output surface. Those techniques interpolated a surface between two adjacent contours, so that nothing encouraged continuity of slope across a contour.

My solution was ODETLAP, which expresses the surface as the solution of an overdetermined sparse linear system. The contours provide known points; the surface between them the unknown points. For each unknown point, an equation is created making it the average of its four neighbors, as with a Laplacian. Each known point has that equation (in contrast to a Laplacian) and also has a second equation making it equal to its known value. The two types of equations can be weighted to emphasize either smoothness or accuracy. Then a best fit is found for this this overdetermined, inconsistent, system.

Although inspired by a Laplacian, ODETLAP's properties are quite different. E.g., local extrema are generated inside a set of nested contours. Inconsistency is a powerful tool that is underappreciated by other researchers.

The idea extends to higher dimensional datasets. It exploits the data's autocorrelation in each dimension. The challenge with ODETLAP is that it is compute and memory intensive.

The compressed dataset is a subset of the original dataset's points, selected greedily, and coded compactly. ODETLAP is used to reconstruct the dataset from them.

This is part of Wenli Li's PhD thesis.

## Research on Terrain Visibility, Viewshed, Observer Siting

Given a large DEM terrain, we have efficient parallel (using both OpenMP and CUDA) algorithms to compute

- the viewshed of an observer,
- the visibility index, i.e., the viewshed's area, of every point,
- how to site multiple observers to jointly cover the most terrain, perhaps while requiring the observers to be intervisible.

Here is some of our published work. There are links to papers and talks.

- Chaulio R. Ferreira, Marcus V. A. Andrade, Salles V. G. Magalhães and W. Randolph Franklin.
**An efficient external memory algorithm for terrain viewshed computation**.*ACM Trans. on Spatial Algorithms and Systems*, 2(2). doi: 10.1145/2903206, 2016.*(paper).* - Max J Egenhofer, Keith C Clarke, Song Gao, Teriitutea Quesnot, W. Randolph Franklin, May Yuan and David Coleman.
**Contributions of GIScience over the Past Twenty Years**. In Harlan Onsrud and Werner Kuhn, editor,*Advancing Geographic Information Science: The Past and Next Twenty Years*, chapter 1, pages 9-34. GSDI association press. 978-0-9852444-4-6, 2016.*(paper).* - Mehrad Kamalzare, Thomas F. Zimmie, Barbara Cutler and W. Randolph Franklin.
**A New Visualization Method to Evaluate Sediment Transport and Erosion**.*Geotechnical Testing Journal*, 39(3). doi: 10.1520/GTJ20140226, May 2016.*(paper).* - Mehrad Kamalzare, Thomas F. Zimmie, Zhongxian Chen, Christopher Stuetzle, Barbara Cutler and W Randolph Franklin.
**Computer Erosion Modeling Considering Soil Hydraulic Conductivity**.*Journal of Geotechnical and Transportation Engineering*, 1(1), 22 June 2015.*http://jgtte.com/issues/Online/Paper%201.pdf*.*(paper).* - Maurício G. Gruppi, Salles V. G. Magalhães, Marcus V. A. Andrade, W. Randolph Franklin and Wenli Li.
**Using Rational Numbers and Parallel Computing to Efficiently Avoid Round-Off Errors on Map Simplification**. In*Geoinfo 2015, XVI Brazilian Symposium on GeoInformatics*, Campos do Jordão, SP, Brazil, 29 Nov - 2 Dec 2015.*(paper, talk).* - Salles V. G. Magalhães, Marcus V. A. Andrade, W. Randolph Franklin and Wenli Li.
**Fast path planning under polygonal obstacle constraints**. In*4th GIS-focused algorithm competition, GISCUP 2015, co-located with ACM SIGSPATIAL GIS*, Bellevue WA USA, 4 Nov 2015.*Winner (2nd place)*.*(paper).* - Salles V. G. Magalhães, Marcus V. A. Andrade, W. Randolph Franklin and Wenli Li.
**Fast exact parallel map overlay using a two-level uniform grid**. In*4th ACM SIGSPATIAL International Workshop on Analytics for Big Geospatial Data (BigSpatial)*, Bellevue WA USA, 3 Nov 2015.*(paper).* - Thiago L. Gomes, Salles V. G. Magalhães, Marcus V. A. Andrade, W. Randolph Franklin and Guilherme C. Pena.
**Efficiently computing the drainage network on massive terrains with an external memory flooding process**.*Geoinformatica*. doi: 10.1007/s10707-015-0225-y, Apr 2015.*http://link.springer.com/article/10.1007/s10707-015-0225-y*.*(paper).* - Guilherme C. Pena, Marcus V.A. Andrade, Salles V.G. Magalhães, W. R. Franklin and Chaulio R. Ferreira.
**An Improved Parallel Algorithm using GPU for Siting Observers on Terrain**. In*16th International Conference on Enterprise Information Systems (ICEIS 2014)*, pages 367-375, Lisbon, 27-30 April 2014.*(paper, talk).* - Chaulio R. Ferreira, Marcus V. A. Andrade, Salles V. G. Magalhães, W. R. Franklin and Guilherme C. Pena.
**A parallel algorithm for viewshed computation on grid terrains**.*Journal of information and data management*, 5(1), 2014.*invited*.*(paper).* - Guilherme Pena, Salles Magalhães, Marcus Andrade, Randolph Franklin, Chaulio Ferreira, Wenli Li and Daniel Benedetti.
**An efficient GPU multiple-observer siting method based on sparse-matrix multiplication**. In*3rd ACM SIGSPATIAL International Workshop on Analytics for Big Geospatial Data (BigSpatial) 2014*, Dallas TX USA, 4 Nov 2014.*(paper, talk).* - Wenli Li, W. Randolph Franklin, Daniel N. Benedetti and Salles V. G. Magalhães.
**Parallel Multiple Observer Siting on Terrain**. In*22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL 2014)*, Dallas, Texas, USA, 4-7 Nov 2014.*(paper, poster).* - Chaulio R. Ferreira, Marcus V. A. Andrade, Salles V. G. Magalhães, W. R. Franklin and Guilherme C. Pena.
**A Parallel Sweep Line Algorithm for Visibility Computation**. In*Geoinfo 2013, XIV Brazilian Symposium on GeoInformatics*, Campos do Jordão, SP, Brazil, 24-27 Nov 2013.*Winner of best paper award, http://www.geoinfo.info/geoinfo2013/index.php*.*(paper).* - Salles V. G. Magalhães, Marcus V. A. Andrade and W. Randolph Franklin.
**Multiple Observer Siting in Huge Terrains Stored in External Memory**.*International Journal of Computer Information Systems and Industrial Management (IJCISIM)*, 3, 2011.*(paper).* - Marcus V. A. Andrade, Salles V. G. Magalhães, Mirella A. Magalhães, W. Randolph Franklin and Barbara M. Cutler.
**Efficient viewshed computation on terrain in external memory**.*Geoinformatica*. doi: 10.1007/s10707-009-0100-9, 2010.*(online 26 Nov 2009)*. (URL)*(paper).* - Daniel M. Tracy, W. Randolph Franklin, Barbara Cutler , Marcus A Andrade, Franklin T Luk, Metin Inanc and Zhongyi Xie.
**Multiple observer siting and path planning on lossily compressed terrain**. In*Proceedings of SPIE Vol. 6697 Advanced Signal Processing Algorithms, Architectures, and Implementations XVII*, San Diego CA. International Society for Optical Engineering, 27 August 2007.*paper 6697-16*.*(paper).* - Daniel M. Tracy, W Randolph Franklin and Franklin Luk.
**Multiple Observer Siting on a Compressed Terrain (extended abstract)**. In*16th Fall Workshop on Computational Geometry*, Smith College, Northampton MA, 10-11 Nov 2006.*(abstract, poster).* - W. Randolph Franklin and Christian Vogt.
**Tradeoffs when multiple observer siting on large terrain cells**. In Andreas Riedl and Wolfgang Kainz and Gregory Elmes, editor,*Progress in Spatial Data Handling: 12th International Symposium on Spatial Data Handling*, pages 845-861. Springer, 2006.*ISBN 978-3-540-35588-5*.*(paper, talk).* - W. Randolph Franklin and Christian Vogt.
**Efficient observer siting on large terrain cells (extended abstract)**. In*GIScience 2004: Third International Conference on Geographic Information Science*, U Maryland College Park, 20-23 Oct 2004.*(paper, talk).* - W. Randolph Franklin.
**Siting observers on terrain**. In Dianne Richardson and Peter van Oosterom, editor,*Advances in Spatial Data Handling: 10th International Symposium on Spatial Data Handling*, pages 109-120, 2002.*(paper).* - W. Randolph Franklin.
**Approximating visibility**. In*GIScience 2000*, Savannah, Georgia, USA, 30 Oct 2000.*(paper).* - Wm Randolph Franklin and Clark Ray.
**Higher isn't Necessarily Better: Visibility Algorithms and Experiments**. In Thomas C. Waugh and Richard G. Healey, editor,*Advances in GIS Research: Sixth International Symposium on Spatial Data Handling*, pages 751-770, Edinburgh. The International Geographical Union's Commission on Geographical Information Systems and The Association for Geographic Information, 5-9 Sept 1994.*(paper).*

Here are some related papers on 3D object visibility:

- Wm Randolph Franklin and Mohan Kankanhalli.
**Parallel Object-Space Hidden Surface Removal**. In*Proceedings of SIGGRAPH'90*, pages 87-94, Aug 1990.*(paper).* - Wm Randolph Franklin and Varol Akman.
**Adaptive Grid for polyhedral visibility in object space, an implementation**.*Computer Journal*, 31(1):56-60, Feb 1988.*(paper).* - Wm Randolph Franklin.
**A linear time exact hidden surface algorithm**. In Kenneth I. Joy and others, editor,*Tutorial: Computer Graphics: Image Synthesis*, pages 218-224. , 1988. - Wm Randolph Franklin and Varol Akman.
**A simple and efficient haloed line algorithm for hidden line elimination**.*Computer Graphics Forum*, 6(2):103-109, May 1987.*(paper).* - Wm Randolph Franklin.
**An exact hidden sphere algorithm that operates in linear time**.*Comput. Graph. Image Process.*, 15:364-379, 1981.*(paper).* - Wm Randolph Franklin.
**A linear time exact hidden surface algorithm**.*Comput. Graph.*, 14(3):117-123, 1980.*(paper).* - Wm Randolph Franklin.
**Combinatorics of hidden surface algorithms**. . PhD thesis,*Center for Research in Computing Technology, Harvard Univ.*, Jun 1978.*(parts: 1, 2, 3, 4).* - W. Randolph Franklin.
**Prism — A Prism Plotting Program**. In Allan H. Schmidt, editor,*Mapping Software and Cartographic Data Bases*, pages 75-79. , 1979. - Wm Randolph Franklin and Harry R. Lewis.
**3-D Graphic Display of Discrete Spatial Data By Prism Maps**. In*Proc. SIGGRAPH'78*, pages 70-75, Aug 1978.*(paper).*

Enjoy!

## More Research Details

These are on a separate page, whose table of contents follows.

**Contents of page Research ...** (hide)

- 1. Computational cartography research
- 1.1 Alternate Terrain Reps
- 1.2 Parallel and distributed cartography computation
- 1.3 Hydrography, bathymetry
- 1.4 Erosion modeling
- 1.5 GeoStar
- 1.6 Visibility, Multi-observer siting, Path planning
- 1.7 Gridding contours
- 1.8 Overlaying two maps (aka Planar graphs)
- 1.9 Logic programming for map overlay
- 1.10 Triangulated irregular network
- 1.11 Prism
- 1.12 General cartography

- 2. Computational geometry research
- 2.1 Fundamentals
- 2.2 Local data structures for polyhedra
- 2.3 Parallel and distributed geometry algorithms
- 2.4 Connected components in $E^3$
- 2.5 Linear time object space hidden surfaces
- 2.6 Nearest points in E
^{2}and E^{3} - 2.7 All near point pairs in E
^{3} - 2.8 Overlaying 3D triangulations
- 2.9 UNION2, UNION3, and Boolean operations and their mass properties
- 2.10 Perimeter and area of the union of circles
- 2.11 Octree creation
- 2.12 Edge intersection
- 2.13 Misc papers

- 3. Other research topics
- 4. Open topics
- 5. Old program solicitations
- 6. Short notes
- 7. Advice
- 8. Proposal writers cheat sheet
- 9. Workshop organizers cheat sheet
- 10. Software notes and reviews

## Misc

Advice to: Grad Student Applicants Apparently only ONE person a year reads this — DQE Examineesknow your material — Doctoral Candidacy Examineeshave a plan — Job Seekers particularly for older professionals

Textbook Reviewing CriteriaMake it easy to teach a good course

Famous RPI graphics–related grads It is possible to survive RPI and prosper

RPI pages: Academic calendarWhen do classes start and end; holidays