I am excited to announce that TerraNNI, the project from my undergraduate senior thesis, is being open-sourced.
For those who have not heard of the project, TerraNNI is a tool for taking LIDAR data, common for geographic information systems (GIS), and creating high-resolution grid digital elevation models (DEMs). Most GIS take DEMs as an input and can perform a wide range of tasks, such as flood mapping, line-of-sight computations, and city planning. The amount of LIDAR data available is growing quite fast. TerraNNI makes full use of this large quantity of data to efficiently produce large-scale, high-resolution DEMs.
In most of these cases, LIDAR data is 3D spatial data and we produced a 2D grid DEM where each grid point has some estimated elevation. Looking forward, we are beginning to see the rise of spatial-temporal data (4D) which offers the opportunity to perform more complex geographic studies such as change detection on terrains. Making use of new spatial-temporal data, TerraNNI provides efficient, scalable, high-resolution volumetric grid DEM construction. In this case, we produce a 3D grid, with axes x,y in space and t time; again each grid point has an estimated elevation. We expect this tool to become increasingly useful as LIDAR data becomes even more prevalent.
On a technical level, TerraNNI was an interesting project, incorporating computational geometry, GPU programming, and I/O efficient computing. The program performs an approximation of natural neighbor interpolation (NNI), which is based on the Voronoi diagram. It makes heavy use of the graphics card for most of the computations, using both OpenGL and CUDA. We also use TPIE for efficient disk access, since data sets can be much larger than the computer’s memory. TerraNNI is one of the fastest programs for producing high-resolution grid DEMs and one of the first to be able to perform 3D natural neighbor interpolation.
Please download TerraNNI from Github and give it a try for yourself. Let me know if you run into any problems. Also feel free to look at our two papers about the project
- Natural Neighbor Interpolation Based Grid DEM Construction Using a GPU (from ACM GIS 2010)
- TerraNNI: Natural Neighbor Interpolation on a 3D Grid Using a GPU (from ACM GIS 2011)