W Randolph Franklin home page
... (old version) Login

This is my old home page. It has some content that hasn't been transferred. The most interesting is on old Research.

Nevertheless, you probably want my current home page.

2017 papers:

  1. bibtexsummary:[/wrf.bib,salles-parallel-mesh-sigspatial-2017]
  2. bibtexsummary:[/wrf.bib,parcube-bigspatial-2017]
  3. bibtexsummary:[/wrf.bib,mesh-orientation-s3pm-2017]
  4. bibtexsummary:[/wrf.bib,x3d-epug-siam-2017]

RPI articles:

  1. about a completed project that I was part of:

A Game-Changing Approach: Using the X-Box Kinect as a Sensor to Conduct Centrifuge Research. Team of Rensselaer Researchers Develop New Visualization Method to Evaluate Erosion Quantity and Pattern, Nov 8, 2016, by Jessica Otitigbe. The story was also published in Inside Rensselaer, 2016-11-30.

  1. on my student Salles Viana Gomes de Magalhães:

The Winning Algorithm, Oct 17, 2016, by Mary Martialay.

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 18 PhD and 70 masters students (who graduated).

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

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

Google scholar profile

Recent Grants

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

Recent teaching

For researchers: A preliminary list of our available software is at https://wrf.ecse.rpi.edu/Software

Office hours:

  1. 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.
  2. If none of those times are convenient then email to discuss another time. Mon and Thurs afternoons and some Wed afternoons are best.
  3. If you'd like a form signed, then pin it by my door JEC6026. Do not slide it under the door.
  4. 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

  1. bibtexsummary:[/wrf.bib,efficient-large-acmgis-2016]
  2. bibtexsummary:[/wrf.bib,salles-xsect-3d-geoinfo-2016]
  3. bibtexsummary:[/wrf.bib,wenli-gpu-horizons-fwcg-2016]
  4. bibtexsummary:[/wrf.bib,salles-giscup-2016]
  5. bibtexsummary:[/wrf.bib,wenli-gpu-siting-2016]
  6. bibtexsummary:[/wrf.bib,wenli-odetlap-2016]
  7. bibtexsummary:[/wrf.bib,hedin-nearptd-2016]
  8. bibtexsummary:[/wrf.bib,minspatial-2016]
  9. bibtexsummary:[/wrf.bib,salles-pinmesh-smi-2016]
  10. bibtexsummary:[/wrf.bib,chaulio-tiledvs-tsas-2016]
  11. bibtexsummary:[/wrf.bib,local-talk-gatech-2016]
  12. bibtexsummary:[/wrf.bib,egenhofer-advancing-2016]
  13. bibtexsummary:[/wrf.bib,kamalzare-gtj-2016]

Paper and Talk Awards

  1. Winner (2nd place), GISCUP 2016:
  2. Awarded a Reproducibility Stamp at the International Geometry Summit 2016.
  3. Winner (2nd place), GISCUP 2015:
  4. Winner of the Best Paper Award (2nd place), AGILE 2012:
  5. Winner of best paper award, Geoinfo 2013:
  6. Winner of the best fast forward presentation award, ACM SIGSPATIAL GIS 2009:

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.

  1. minimal geometric representations, for simplicity and parallelizability,
  2. uniform grid, for fast intersection detection,
  3. rational numbers, to prevent roundoff errors,
  4. Simulation of Simplicity, to handle degeneracies, and
  5. 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

  1. the viewshed of an observer,
  2. the visibility index, i.e., the viewshed's area, of every point,
  3. 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.

  1. bibtexsummary:[/wrf.bib,chaulio-tiledvs-tsas-2016]
  2. bibtexsummary:[/wrf.bib,egenhofer-advancing-2016]
  3. bibtexsummary:[/wrf.bib,kamalzare-gtj-2016]
  4. bibtexsummary:[/wrf.bib,kamalzare-jgtte-2015]
  5. bibtexsummary:[/wrf.bib,mauricio-rational-geoinfo-2015]
  6. bibtexsummary:[/wrf.bib,salles-giscup-2015]
  7. bibtexsummary:[/wrf.bib,salles-overlay-bigspatial-2015]
  8. bibtexsummary:[/wrf.bib,gomes-emflow-2015]
  9. bibtexsummary:[/wrf.bib,iceis-2014]
  10. bibtexsummary:[/wrf.bib,chaulio-jidm-2014]
  11. bibtexsummary:[/wrf.bib,bigspatial-2014]
  12. bibtexsummary:[/wrf.bib,li-acmgis-2014]
  13. bibtexsummary:[/wrf.bib,chaulio-geoinfo-2013]
  14. bibtexsummary:[/wrf.bib,magalhaes-ijcisim-2011]
  15. bibtexsummary:[/wrf.bib,andrade-geoinfo-ext-viewshed-2008]
  16. bibtexsummary:[/wrf.bib,dt-wrf-spie-2007]
  17. bibtexsummary:[/wrf.bib,tracy-fwcg-2006]
  18. bibtexsummary:[/wrf.bib,wrf-sdh2006]
  19. bibtexsummary:[/wrf.bib,wrf-siting-apr2004]
  20. bibtexsummary:[/wrf.bib,wrf-site]
  21. bibtexsummary:[/wrf.bib,wrf-savannah]
  22. bibtexsummary:[/wrf.bib,fr-hinbv-94]

Here are some related papers on 3D object visibility:

  1. bibtexsummary:[/wrf.bib,fk-poshs-90-in-geom]
  2. bibtexsummary:[/wrf.bib,fa-agpvo-88-in-geom]
  3. bibtexsummary:[/wrf.bib,f-ltehs-88]
  4. bibtexsummary:[/wrf.bib,fa-sehla-87]
  5. bibtexsummary:[/wrf.bib,f-ehsao-81]
  6. bibtexsummary:[/wrf.bib,f-ltehs-80-in-geom]
  7. bibtexsummary:[/wrf.bib,f-chsa-78]
  8. bibtexsummary:[/wrf.bib,wrf-prism-hu]
  9. bibtexsummary:[/wrf.bib,fl-3gdds-78]


More Research Details

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


My homepage URL

  1. The new URL of my homepage is https://wrf.ecse.rpi.edu/ . Please update your bookmarks to this. Thanks.
  2. http://wrf.ecse.rpi.edu/ also works.
  3. http://wrfranklin.org/ permanently redirects there. It will continue to work for the indefinite future.
  4. https://wrfranklin.org/ gives a browser error because wrfranklin.org doesn't have an SSL certificate.

I welcome questions and problem reports.