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.