More Web Proxy on the site http://driver.im/

research-article

Public Access

TerraNNI: Natural Neighbor Interpolation on 2D and 3D Grids Using a GPU

Authors:

Pankaj K. Agarwal,

Thomas MølhaveAuthors Info & Claims

ACM Transactions on Spatial Algorithms and Systems (TSAS), Volume 2, Issue 2

Article No.: 7, Pages 1 - 31

https://doi.org/10.1145/2786757

Published: 21 June 2016 Publication History

Abstract

With modern focus on remote sensing technology, such as LiDAR, the amount of spatial data, in the form of massive point clouds, has increased dramatically. Furthermore, repeated surveys of the same areas are becoming more common. This trend will only increase as topographic changes prompt surveys over already scanned areas, in which case we obtain large spatiotemporal datasets.

An initial step in the analysis of such spatial data is to create a digital elevation model representing the terrain, possibly over time. In the case of spatial (spatiotemporal, respectively) datasets, these models often represent elevation on a 2D (3D, respectively) grid. This involves interpolating the elevation of LiDAR points on these grid points.

In this article, we show how to efficiently perform natural neighbor interpolation over a 2D and 3D grid. Using a graphics processing unit (GPU), we describe different algorithms to attain speed and GPU-memory tradeoffs. Our experimental results demonstrate that our algorithms not only are significantly faster than earlier ones but also scale to much bigger datasets that previous algorithms were unable to handle.

References

[1]

P. K. Agarwal, L. Arge, and K. Yi. 2005. I/O-efficient construction of constrained Delaunay triangulations. In Proceedings of the European Symposium on Algorithms. 355--366.

Digital Library

[2]

A. Aggarwal and J. S. Vitter. 1988. The input/output complexity of sorting and related problems. Communications of the ACM 31, 9 (1988), 1116--1127.

Digital Library

[3]

D. Attali and J.-D. Boissonnat. 2004. A linear bound on the complexity of the Delaunay triangulation of points on polyhedral surfaces. Discrete & Computational Geometry 31, 3 (2004), 369--384.

Digital Library

[4]

C. B. Barber, D. P. Dobkin, and H. Huhdanpaa. 1996. The Quickhull algorithm for convex hulls. ACM Transactions on Mathematical Software 22, 4 (1996), 469--483.

Digital Library

[5]

J.-D. Boissonnat and F. Cazals. 2000. Smooth surface reconstruction via natural neighbour interpolation of distance functions. In Proceedings of the 16th Annual ACM Symposium on Computer Geometry. 223--232.

Digital Library

[6]

CGAL Development Team. 2014. Cgal, Computational Geometry Algorithms Library. (2014). http:// www.cgal.org.

[7]

A. Danner, A. Breslow, J. Baskin, and D. Wilikofsky. 2012. Hybrid MPI/GPU interpolation for grid DEM construction. In Proceedings of the 20th International Conference on Advances in Geographic Information Systems (SIGSPATIAL’12). ACM, New York, NY, 299--308. 2424321.2424360

Digital Library

[8]

A. Danner, T. Mølhave, K. Yi, P. K. Agarwal, L. Arge, and H. Mitasova. 2007. TerraStream: From elevation data to watershed hierarchies. In Proceedings of the 15th Annual ACM International Symposium on Advances in Geographic Information Systems (GIS’07). ACM, New York, NY, 1--8. 10.1145/1341012.1341049

Digital Library

[9]

M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf. 1997. Computational Geometry -- Algorithms and Applications. Springer Verlag.

Digital Library

[10]

H. Edelsbrunner, D. Letscher, and A. Zomorodian. 2000. Topological persistence and simplification. In Proceedings of the IEEE Symposium on Foundations in Computer Science 454--463.

Digital Library

[11]

H. Edelsbrunner and E. P. Mücke. 1994. Three-dimensional alpha shapes. ACM Transactions on Graphics 13, 1 (1994), 43--72.

Digital Library

[12]

Q. Fan, A. Efrat, V. Koltun, S. Krishnan, and S. Venkatasubramanian. 2005. Hardware-assisted natural neighbor interpolation. In Proceedings of the 7th Workshop on Algorithm Engineering and Experiments (ALENEX’05).

[13]

T. G. Farr, P. A. Rosen, E. Caro, R. Crippen, R. Duren, S. Hensley, M. Kobrick, M. Paller, E. Rodriguez, L. Roth, D. Seal, S. Shaffer, J. Shimada, J. Umland, M. Werner, M. Oskin, D. Burbank, and D. Alsdorf. 2007. The shuttle radar topography mission. Reviews in Geophysics 45 (2007). http://dx.doi.org/10.1029/ 2005RG000183

[14]

S. Ghosh, A. E. Gelfand, and T. Mølhave. 2012. Attaching uncertainty to deterministic spatial interpolations. Statistical Methodology 9, 1--2 (January--March 2012), 251--264.

[15]

GRASS Development Team. 2014. GRASS GIS Homepage. http://www.baylor.edu/grass/. (2014).

[16]

R. Hemsley. 2009. Interpolation on a magnetic field. (2009). http://code.google.com/p/interpolate3d/.

[17]

P. C. Kyriakidis and A. G. Journel. 1999. Geostatistics space-time models: A review. Mathematical Geology 31, 6 (1999), 651--684. http://www.springerlink.com/index/H5L4K7V760045748.pdf.

[18]

N. Lebeck, T. Mølhave, and P. K. Agarwal. 2013. Computing highly occluded paths on a terrain. In Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (SIGSPATIAL’13). ACM, New York, NY, 14--23.

Digital Library

[19]

L. Li and P. Revesz. 2002. A comparison of spatio-temporal interpolation methods. In Geographic Information Science. Vol. 2478. Springer, 145--160.

Digital Library

[20]

J. Mateu, F. Montes, and M. Fuentes. 2003. Recent advances in space-time statistics with applications to environmental data: An overview. Geophysical Research 108, 8774 (2003).

[21]

E. Miller. 1997. Towards a 4d-GIS: Four dimensional interpolation utilizing kriging. In Innovations in GIS 4, Z. Kemp (Ed.). 181--197.

[22]

H. Mitasova, L. Mitas, W. M. Brown, D. P. Gerdes, I. Kosinovsky, and T. Baker. 1995. Modeling spatially and temporally distributed phenomena: New methods and tools for GRASS GIS. International Journal of Geographical Information Systems 9, 4 (1995), 433--446.

[23]

H. Mitasova, M. Overton, and R. S. Harmon. 2005. Geospatial analysis of a coastal sand dune field evolution: Jockey’s ridge, North Carolina. Geomorphology 72, 1--4 (2005), 204--221.

[24]

T. Mølhave, P. K. Agarwal, L. Arge, and M. Revsbæk. 2010. Scalable algorithms for large high-resolution terrain data. In Proceedings of the 1st International Conference and Exhibition on Computing for Geospatial Research & Application. ACM.

Digital Library

[25]

NOAA. 2014. NOAA Coastal Services Center, LIDAR Data Retrieval Tool. (2014). http://csc-s-maps-q.csc.noaa.gov/dataviewer/viewer.html?keyword=lidar.

[26]

NVIDIA. 2010. CUDA Homepage. http://nvidia.com/cuda. (2010). 3.0.

[27]

S. J. Owen. 1992. An Implementation of Natural Neighbor Interpolation in Three Dimensions. Master’s thesis.

[28]

J. D. Owens, D. Luebke, N. Govindaraju, M. Harris, J. Krüger, A. Lefohn, and T. J. Purcell. 2007. A survey of general-purpose computation on graphics hardware. Computer Graphics Forum 26, 1 (2007), 80--113.

[29]

S. Park, L. Linsen, O. Kreylos, J. D. Owens, and B. Hamann. 2006. Discrete Sibson interpolation. IEEE Transactions on Visualization and Computer Graphics 12, 2 (March 2006), 243--253.

Digital Library

[30]

S. Shekhar and H. Xiong (Eds.). 2008. Encyclopedia of GIS. Springer.

Digital Library

[31]

R. Sibson. 1981. A brief description of natural neighbour interpolation. In Interpreting Multivariate Data, V. Barnet (Ed.). John Wiley & Sons, Chichester, 21--36.

[32]

N. Sukumar, B. Moran, and T. Belytschko. 1998. The natural element method in solid mechanics. International Journal of Numerical Methods in Engineering 43, 5 (1998), 839--887.

[33]

TPIE Development Team. 2014. Templated Portable I/O Environment (TPIE). http://madalgo.au.dk/tpie. (2014).

[34]

D. Watson. 1992. Contouring: A Guide to the Analysis and Display of Spatial Data. Oxford, Pergamon.

[35]

C. K. Wikle, L. M. Berliner, and N. Cressie. 1998. Hierarchical Bayesian space-time models. Environmental and Ecological Statistics 5, 2 (1998), 117--154.

[36]

S. You and J. Zhang. 2012. Constructing natural neighbor interpolation based grid DEM using CUDA. In Proceedings of the 3rd International Conference on Computing for Geospatial Research and Applications (COM.Geo’12). ACM, New York, NY, Article 28, 6 pages. 2345316.2345349

Digital Library

Cited By

Fellegara RIuricich FSong YFloriani L(2023)Terrain trees: a framework for representing, analyzing and visualizing triangulated terrainsGeoinformatica10.1007/s10707-022-00472-327:3(525-564)Online publication date: 1-Jul-2023
https://dl.acm.org/doi/10.1007/s10707-022-00472-3
Jasek KPasternak MMiluski WBugaj JGrabka M(2021)Application of Gaussian Radial Basis Functions for Fast Spatial Imaging of Ground Penetration Radar Data Obtained on an Irregular GridElectronics10.3390/electronics1023296510:23(2965)Online publication date: 28-Nov-2021
https://doi.org/10.3390/electronics10232965
Varghese JSubash SK P SN V BG A(2020)Adaptive Switching Interpolation Filter for Restoring Impulse Corrupted Digital ImagesIET Image Processing10.1049/iet-ipr.2019.1445Online publication date: 14-May-2020
https://doi.org/10.1049/iet-ipr.2019.1445

Index Terms

TerraNNI: Natural Neighbor Interpolation on 2D and 3D Grids Using a GPU
1. Software and its engineering
2. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Natural neighbor interpolation based grid DEM construction using a GPU
GIS '10: Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems

With modern LiDAR technology the amount of topographic data, in the form of massive point clouds, has increased dramatically. One of the most fundamental GIS tasks is to construct a grid digital elevation model (DEM) from these 3D point clouds. In this ...
Constructing natural neighbor interpolation based grid DEM using CUDA
COM.Geo '12: Proceedings of the 3rd International Conference on Computing for Geospatial Research and Applications

Constructing digitial elevation model(DEM) from dense LiDAR points becomes increasingly important. Natural Neighbor Interpolation (NNI) is a popular approach to DEM construction from point datasets but is computationally intensive. In this study, we ...
TerraNNI: natural neighbor interpolation on a 3D grid using a GPU
GIS '11: Proceedings of the 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems

With modern focus on LiDAR technology the amount of topographic data, in the form of massive point clouds, has increased dramatically. Furthermore, due to the popularity of LiDAR, repeated surveys of the same areas are becoming more common. This trend ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Spatial Algorithms and Systems

ACM Transactions on Spatial Algorithms and Systems Volume 2, Issue 2

Invited Papers from ACM SIGSPATIAL

July 2016

107 pages

ISSN:2374-0353

EISSN:2374-0361

DOI:10.1145/2960926

Editor:
Hanan Samet
University of Maryland, College Park

Issue’s Table of Contents

Copyright © 2016 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 21 June 2016

Accepted: 01 May 2015

Revised: 01 March 2015

Received: 01 August 2014

Published in TSAS Volume 2, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
526
Total Downloads

Downloads (Last 12 months)66
Downloads (Last 6 weeks)11

Reflects downloads up to 28 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Fellegara RIuricich FSong YFloriani L(2023)Terrain trees: a framework for representing, analyzing and visualizing triangulated terrainsGeoinformatica10.1007/s10707-022-00472-327:3(525-564)Online publication date: 1-Jul-2023
https://dl.acm.org/doi/10.1007/s10707-022-00472-3
Jasek KPasternak MMiluski WBugaj JGrabka M(2021)Application of Gaussian Radial Basis Functions for Fast Spatial Imaging of Ground Penetration Radar Data Obtained on an Irregular GridElectronics10.3390/electronics1023296510:23(2965)Online publication date: 28-Nov-2021
https://doi.org/10.3390/electronics10232965
Varghese JSubash SK P SN V BG A(2020)Adaptive Switching Interpolation Filter for Restoring Impulse Corrupted Digital ImagesIET Image Processing10.1049/iet-ipr.2019.1445Online publication date: 14-May-2020
https://doi.org/10.1049/iet-ipr.2019.1445

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Figures

Tables

Media

View Issue’s Table of Contents