W. Randolph Franklin, Professor

Brief Bio       Long resume

Email - Vcard - GPG key- phone: +1.518.276.6077 (let it ring many times)- Travel Directions to 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.
• supervised 14 PhD and 68 masters graduates, (list).

2.1  Recent Masters and PhD grads

Doctoral Graduate

• You Li, CUDA-accelerated HD-ODETLAP: a high dimensional geospatial data compression framework, 2011.

Masters Graduates

• Luke Perkins, An Integrated Approach to Choke Point Detection and Region Decomposition, 2010.
• Jeffrey Sult, Computational analysis of first-person shooter levels, Apr 2011.
• Michael J Snyder, Using The HTML5 Canvas Element For A Web-Based Multi-User Painting Application, Apr 2011.

Complete list

2.2  Recent Publications

1. . Salles V. G. Magalh{\~a}es, Marcus V. A. Andrade and W. Randolph Franklin. International Journal of Computer Information Systems and Industrial Management (IJCISIM), 3, 2011. (URL) (paper).
2. . Tsz-Yam Lau and W. Randolph Franklin. Cartography and Geographic Information Science, 38(2):162-174, apr 2011. (paper).
3. . W. Randolph Franklin. In 25th International Cartographic Conference, Paris, 3--8 July 2011. (paper, talk).
4. . Zhongxian Chen, Christopher S. Stuetzle, Barbara M. Cutler, Jared A. Gross, W. Randolph Franklin and Thomas F. Zimmie. In Geo-Frontiers 2011: Advances in geotechnical engineering, Dallas TX, 13--16 March 2011. (URL) (paper).
5. . W. Randolph Franklin, Zhongyi Xie, Eddie Lau and You Li. In ICA Workshop on Advances in Sensors and Algorithms for Topographic and Thematic Mapping, Orlando, Florida. The International Cartographic Association (ICA) Commission on Mapping from Satellite Imagery, 19 Nov 2010. (paper, talk).
6. . You Li and W. Randolph Franklin. In Geospatial Data and Geovisualization: Environment, Security, and Society, a special joint symposium of ISPRS Technical Commission IV \& AutoCarto 2010, Orlando, Florida, 15--18 Nov 2010. (paper, talk).
7. . Jared A. Gross, Christopher S. Stuetzle, Zhongxian Chen andBarbara Cutler, W. Randolph Franklin and Thomas F. Zimmie. In ICSE-5 5th international conference on scour and erosion, San Francisco, 7--10 Nov 2010. (paper, talk).
8. . Zhongyi Xie, W. Randolph Franklin and Dan Tracy. In 18th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS 2010), San Jose, CA, USA, 2--5 Nov 2010. (PhD Dissertation Showcase). (paper, poster).
9. . You Li, Tsz-Yam Lau, Chris Stuetzle, Peter Fox and W. Randolph Franklin. In 18th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS 2010), San Jose, CA, USA, 2--5 Nov 2010. (PhD Dissertation showcase). (paper, talk).
10. . Zhongxian Chen, Christopher Stuetzle, Barbara Cutler, Jared Gross, W. Randolph Franklin and Thomas Zimmie. In 18th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS 2010), San Jose, CA, USA, 2--5 Nov 2010. (poster). (paper, poster).
11. . Tsz-Yam Lau and W. Randolph Franklin. In 20th Annual Fall Workshop on Computational Geometry (FWCG 2010), Stony Brook University, Stony Brook, NY 11794, USA, 29--30 Oct 2010. (extended abstract and talk). (abstract, talk).
12. . W. Randolph Franklin. In 20th Annual Fall Workshop on Computational Geometry (FWCG 2010), Stony Brook University, Stony Brook, NY 11794, USA, 29--30 Oct 2010. (extended abstract and talk). (abstract, talk).
13. . W. Randolph Franklin and Barb Cutler. In DARPA GRID2 workshop, 18--19 Aug 2010. (talk).
14. . Christopher S. Stuetzle, Zhongxian Chen, Barbara Cutler, W. Randolph Franklin, Jared Gross, Katrina Perez and Thomas Zimmie. In 7th International Conference on Physical Modelling in Geotechnics (ICPMG 2010), Zurich, 20--24 Jun 2010. (paper, talk).

Complete list

1. NSF IIS-1117277: CGV: Small: Towards a mathematics of terrain, sole PI: WRF. $500,000 (expected), 8/1/2011-7/31/2014 (expected).
   Terrain, in this project, is defined as the elevation of the earth's surface above some reference geoid. Over the last few decades, ever larger quantities of terrain data with higher accuracy in (x, y) and z have become available. Improved bathymetry data of the sea floor has also been collected, and elevation data for other planets and their satellites is now available (for a generalized definition of "terrain"). The PI's goal in this project is to develop and validate a new mathematical representation of terrain, which will be closer to the physics of how terrain is formed and be designed to represent legal realistic terrain more easily than unrealistic terrain. Aside from constituting an interesting application of deeper mathematics in its own right, such a foundation for terrain representation that is geologically sound will enable the design of operators such as compression and siting from first principles. This work will generalize and extend the PI's previous successful terrain representation and algorithms work, such as ODETLAP. The new terrain representation will be a sequence of parameterized transformations of various classes inspired by the physics of how terrain is formed. Modeling the real world, the transformations will be nonlinear (e.g., real river valleys cannot be superimposed and added). Nonlinearity is powerful, but difficult to study. The first class of transformations, called scooping, will model how river valleys form, and will guarantee to produce only hydrologically valid terrain. Erosion, deposition and hill creation transformations will also be studied. Each class of transformation has many design options; for example, should fewer and more powerful, rather than many but less powerful, transformations be used? The PI's goal is to encode the terrain in as few bits as possible while satisfying, in addition to RMS error, richer, application-dependent, metrics such as multi-observer siting to maximize viewshed, and then path planning to avoid those observers. Hydrological accuracy and visual recognizability are other metrics. This project continues the PI's collaboration with Professor Marcus Andrade at the Federal University of Vicosa in Brazil. Project outcomes will be validated by means of extensive tests on real terrain databases.
   Broader Impacts: The simplest implication of this work will be more compact terrain compression algorithms. Thus, this research will allow larger terrain datasets to be accessed and processed by consumers in portable products such as GPS navigators. Easier access to large terrain databases will facilitate a probability distribution over possible realistic terrain, which in turn will allow optimizing operations such as multi-observer siting and path planning (the former has applications ranging from cell phone tower siting to surveillance, while the latter is important for energy conservation during transportation). Hydrological applications of better large terrain data include floodplain planning (flood damage in the US amounted to $50,000,000,000 during the 1990s). Through involvement of graduate students in the PI's research and through his graduate courses, this project will also help to increase the educated workforce in a foundational discipline that is important to American productivity and future economic prosperity.
2. NSF CMMI-1158899: RAPID: Flood and Erosion Reconnaissance: Hurricanes Irene and Lee, Upstate New York and Western New England, PI: Tom Zimmie, co-PIs: Barb Cutler and WRF. $30,123, 9/20/2011-8/31/2012.

To students wanting to take ECSE-4750 Computer Graphics this fall:

If you lack specific prereqs but have a good computing background, then you are still welcome. Come to the first class with the paperwork. We always find room for everyone.

The big change for 2011 is a new textbook: Sumanta Guha, Computer Graphics Through OpenGL, From Theory to Experiments.

• Computer Graphics Fall 2011 home page
• ECSE-2500, Engineering Probability, Spring 2011, Home Page
• ECSE-4750 Computer Graphics Fall 2010
• ECSE-2500 Engineering Probability, Spring 2010
• ECSE-2610 Computer Components & Operations (COCO), Spring 2010
• ECSE-4750 Computer Graphics Fall 2009
• ECSE-6800 Advanced Computer Graphics Spring 2009 
• Older courses
• Advice To Grad Student Applicants
• Advice To DQE Examinees
• Advice to Job Seekers
• Textbook Reviewing Criteria
• Teaching philosophy (Jan 2007)
• Famous RPI graphics-related grads

RPI pages:

• Academic calendar
• Class schedule

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" ¹. The Geo in geometry is from the Greek Γη meaning, ''earth, ground, land''. ². My major recently concluded project was Geo*, a DARPA-funded project for representing and operating on terrain, that is, elevation.

My current project, NSF/CDI Fundamental Terrain Representations and Operations ³, attempts to predict how erosion occurs in levee failure by overtopping, and, after a failure, to reverse-simulate what happened.

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

RPI Computer graphics group

These are on a separate page.

This was my 2005-2009 DARPA project. Details are here. A good summary is this Geo* talk (7/2010), Videos in talk: 1, 2, 3.

Key points include these.

1. efficient hi-res visibility computation on terrain,
2. multiple observer siting to maximize joint viewshed,
3. ODETLAP, an extension of the Laplacian PDE to an overdetermined system of equations, which is used in many of the following results,
4. extremely compact lossy terrain (elevation) compression,
5. terrain compression that reconstructs slopes accurately,
6. lossily compressed terrain supports motion-planning (path planning),
7. path planning with sophisticated cost metric on large terrain, and
8. a better surface fitting procedure for bathymetry data that is very unevenly spaced.

ICA Workshop on Advances in Sensors and Algorithms for Topographic and Thematic Mapping, 19 Nov 2010

W. Randolph Franklin, Zhongyi Xie, Eddie Lau and You Li, Algorithms for terrain and bathymetric sensor data

Abstract: We present three algorithic advances and a research topic in processing topographic and bathymetric sensor data. They are (i) lossy terrain compression that maintains slope accuracy, (ii) bathymetric surface fitting to irregular tracklines, (iii) lossy compression of 5D environmental data, and (iv) terrain modeling to maintain hydrological validity. ♦ The purpose is to attack several issues raised by the large amounts of data now available, with an eventual goal of a unified system.

ICSE-5, 5th international conference on scour and erosion, San Francisco, 7-10 Nov 2010

J.A. Gross, C.S. Stuetzle, Z. Chen, B. Cutler, W.R. Franklin, and T. Zimmie. Simulating Levee Erosion with Physical Modeling Validation

Abstract: This paper studies rill and gully initiation and propagation on levees, dams, and general earth embankments. It specifically studies where these erosion features occur, and how long a particular embankment can sustain overtopping before breaching and catastrophic failure. This contrasts to previous levee erosion analysis, which has primarily concerned the final effects of erosion, such as soil loss, depth of scour and breach width. This paper describes the construction of scaled-down physical models of levees composed of different homogeneous sands, as well as sand-clay mixtures, and their laboratory testing in a 200g geotechnical centrifuge. A 3-D laser range scanner captured the surface features of the physical model, before and after erosion. The resulting data is utilized in developing digital simulations of the rill erosion process. Those simulations combine 3-D Navier-Stokes fluid simulations and a segmented height field data structure to produce an accurate portrayal of the erosive processes, which will be validated by physical modeling.

18th international research symposium on computer-based cartography and GIScience (Autocarto 2010)

2 accepted abstracts:

1. Tsz-Yam Lau and W. Randolph Franklin, Completing fragmentary river networks via induced terrain
2. You Li and W. Randolph Franklin, 4D-ODETLAP: A Novel High-dimensional Compression Method on Time-varying Geospatial Data

ACM SIGSPATIAL GIS 2010

1. 2 accepted PhD showcase papers:
   1. You Li, Tsz-Yam Lau, Chris Stuetzle, Peter Fox and W. Randolph Franklin, 3D oceanographic data compression using 3D-ODETLAP
   2. Zhongyi Xie, W. Randolph Franklin and Dan Tracy, Slope Preserving Lossy Terrain Compression
2. 1 accepted poster paper:
   1. Zhongxian Chen, Christopher Stuetzle, Barbara Cutler, Jared Gross, W. Randolph Franklin, Thomas Zimmie, Quantitative analysis of simulated erosion for different soils
      Abstract: Levee overtopping can lead to failure and cause catastrophic damage, as was the case during Hurricane Katrina. We present a computer simulation of erosion to study the development of the rills and gullies that form along an earthen embankment during overtopping. We have coupled 3D Smoothed Particle Hydrodynamics with an erodibility model to produce our simulation, and our soil data structure allows us to model the crumbling of overhangs that occur during the erosion process. We have conducted analogous physical erosion experiments in a laboratory for comparison. Quantitative analysis of our simulation results and change detection between the initial and final geometries allow us to compare the computer simulations to the physical experiments. We also perform temporally and spatially varying analysis of our simulation results and compare soil types with different erodibilities. With these two comparison techniques, we are able to evaluate the accuracy of computer simulations of erosion.

20th Annual Fall Workshop on Computational Geometry, October 29-30, 2010, Stony Brook University

W. Randolph Franklin, Towards a mathematics of terrain

Abstract:

We present a first step towards a mathematics of terrain. Our goal is to allow the representation of only legal terrain, somewhat as the design of George Orwell's \emph{Newspeak} prevented the expression of bad thoughts. A second goal is to use a rich mathematical system so to minimize what needs to be stated explicitly, and to enforce global consistencies. Our long-term metric of success will be, what new things can we do with these ideas? We begin by studying terrain's properties.

DARPA GRID2 Workshop, 19 Aug 2010

WR Franklin and B Cutler. KNOWMESH - Meshless geometry with knowledge representation

We've enjoyed success with two quite different data structures, and would be happy for others to adopt them, but that's not DARPA-hard, so here's a more ambitious proposal. My talk's organization: (i) Our two recent data structure projects: Geo* with ODETLAP and Segmented height field with tetrahedral mesh. (ii) KNOWMESH definition. (iii) Two proposed KNOWMESH applications: GIS and architecture. ...

talk.

Hybrid intelligent systems (HIS), Atlanta 2010

Salles V. G. de Magalhães, Marcus V. A. Andrade, and W. Randolph Franklin. Siting observers in huge terrains stored in external memory

Abstract: We present an algorithm and implementation for EmSite, which sites multiple (perhaps hundreds) of observers on a DEM terrain that is too large to store in internal memory. EmSite has been implemented in C++. Tests show it to use a median of 19% fewer observers to obtain the same joint visibility index (coverage) on huge terrains, compared to a naive partitioning of the terrain into subregions. This will permit more efficient positioning of facilities such as mobile phone towers, fire observation towers, and vigilance systems. paper.

7th International Conference on Physical Modelling in Geotechnics (ICPMG), Zurich 2010

C S Stuetzle, J Gross, Z Chen, B Cutler, WR Franklin, K Perez, & T Zimmie. Computer simulations and physical modelling of erosion

Abstract: Research is being done to study the details and progress of soil erosion on levees and dams, including the formation and progression of rills and gullies on the slopes, and eventually to final breaching. These detailed observations of erosion differ from the typical predictions of only the maximum erosion or scour depths, for example around submerged bridge piers. Computer simulations and geotechnical centrifuge modelling will, in the future, be validated using these observations. For testing, single layer sand models were utilized, and will be followed by clayey and mixed soils, and increased number of layers. The computer simulations will incorporate 3-D Navier-Stokes fluid simulations, and a novel segmented height field extended to allow soil undercuts was developed. The primary intent of the research is to study small-scale erosion on earthen embankments and, ultimately, develop novel and robust erosion software, validated by physical modelling.

paper, talk.

(submitted)

W. R. Franklin, Parallel Volume Computation of the Union of Many Cubes

We present an algorithm and implementation for computing volumes and areas of the union of many congruent axis-aligned cubes. Its expected execution time is linear. It has been tested to 100M cubes. The ideas extend to any mass property of the union of any polyhedra, and to online computations as more inputs are added. The algorithm is mostly a series of map-reduce operations and so parallelizes quite well. Inserting a new cube and recomputing takes constant expected time.

The algorithm combines local topological formulae with a uniform grid. It does not build a computation tree of height log(N), but rather computes all the possibly relevant intersections in one step. It is an exact computation, not a sampling or cellular decomposition technique. Most of the operations are a map-reduce, and so they parallelize quite well, better than more complicated data structures. paper.

FWCG2009

Christopher S. Stuetzle, Zhongxian Chen, Katrina Perez, Jared Gross, Barbara Cutler, W. Randolph Franklin, and Thomas Zimmie. Segmented height field and smoothed particle hydrodynamics in erosion simulation. extended abstract.

ACM SIGSPATIAL GIS2009

Tsz-Yam Lau, You Li, Zhongyi Xie, and W. Randolph Franklin. Sea floor bathymetry trackline surface fitting without visible artifacts using ODETLAP. paper, poster: pptx|pdf, fast forward talk. video. Awarded the best fast forward presentation.

FWCG2008

Operating on large geometric datasets, Fall Workshop in Computational Geometry (FWCG) 2008, 1 Nov 2008, extended abstract, talk, (11/2/2008). Longer papers and talks on the same topic:

1. Analysis of mass properties of the union of millions of polygedra
2. Mass properties of the union of millions of identical cubes]
3. related talk
4. earlier but more detailed talk

ACMGIS2008

3 presentations by my students at 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM GIS 2008), Irvine CA, 5-7 Nov 2008.

1. Parallel ODETLAP for terrain compression and reconstruction. paper, talk.
2. Path planning on a compressed terrain. poster.
3. Evaluating hydrology preservation of simplified terrain representations. PhD student poster (won a best poster award), fast forward presentation.

1. HW I have used (at least a little)
2. How to program a low-level machine
3. How to program a slightly higher level machine
4. Recent additions to my website
5. Random things that don't fit anywhere else