Compression of Multi-Resolution Terrain Data Based on Binary Tree

Abstract:

In order to overcome the incontinuity and redundancy of data storage caused by the grids in representing the multi-resolution terrain, an adaptive hierarchical triangulation based on binary tree is used to represent the multi-resolution terrain model. It realizes the representation of the terrain data at different levels of detail and enables data compression by local omission of data values. The structure of binary tree is stored using a bit code of the underlying binary tree, while the height data are stored using an array, and relative pointers which allow a selective tree traversal. This method realizes the continuity and reduces the data volume in data storage of multi-resolution digital elevation model (DEM), and it is possible to work directly on the compressed data. We show that significant compression rates can be obtained already for small threshold values, and in a visualization application, it is possible to extracted and drawn triangulations at interactive rates.

• Periodical: Applied Mechanics and Materials (Volumes 220-223)
• Pages: 2628-2634
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.220-223.2628
• Online since: November 2012
• Authors: Jian Jun Bai, Chao De Yan
• Keywords: Binary Tree, Compression, Digital Elevation Model, Grids, Multi-Resolution

References

[1] Cohen-Or D., and Levanoni, Y., Temporal Continuity of Levels of Detail in Delaunay Triangulated Terrain. Proceedings of the IEEE Visualization '96, (1996) Oct. 27 -Nov. 1 ; San Francisco, CA, USA

DOI: 10.1109/visual.1996.567600

[2] Hoppe H., Smooth View-Dependent Level-of-Detail Control and Its Application to Terrain Rendering. Proceedings of the IEEE Visualization '98, (1998) October 18-23; Research Triangle Park ,North Carolina, USA

DOI: 10.1109/visual.1998.745282

[3] Hoppe H., Progressive Meshes. Proceedings of SIGRAPH 96, (1996) August 4-9; New Orleans, Louisiana, USA

[4] Lindstrom P. and Pascucci V., Terrain Simplification Simplified: A General Framework for View-Dependent Out-of-Core Visualization. IEEE Transactions on Visualization and Computer Graphics, 2002, 8(3): 239-254.

DOI: 10.1109/tvcg.2002.1021577

[5] Lindstrom P., Koller D, Faust and Gregory., A Real-Time Continuous Level of Detail Rendering of Height Fields. Proceedings of SIGRAPH 96, (1996) August 4-9; New Orleans, Louisiana, USA

DOI: 10.1145/237170.237217

[6] Lindstrom P. and Pascucci V., Visualization of Large Terrains Made Easy. Proceedings of the IEEE Visualization 2001, (2001) Oct. 21-26; San Diego, CA, USA

DOI: 10.1109/visual.2001.964533

[7] Duchaineau M., Wolinsky M., Sigeti D.E., Miller M.C., Aldrich C.,Mineev and Weinstein M.B., ROAMing Terrain: Real—time Optimally Adapting Meshes. Proceedings of the IEEE Visualization '97, (1997) Oct. 19-24; Phoenix, AZ, USA

DOI: 10.1109/visual.1997.663860

[8] RÖttger S., Heidrich W., Slussallek P. and Seidel H-P., Real-Time Generation of Continuous Levels of Detail for Height Fields. in Proc. 6th Int. Conf. In Central Europe on Computer Graphics and Visualization, 1998, 315-322

[9] Gerstner T., Multiresolution Visualization and Compression of Global Topographic Data. Geoinformatica, 2003, 7(1): 7-23

[10] Pajarola, R., Access to Large Scale Terrain and Image Databases in Geoinformation Systems[D]. PhD Dissertation, Swiss Federal Institute of Technology (ETH) Zürich, 1998, 100pp

[11] Pajarola, R., Large Scale Terrain Visualization Using the Restricted Quadtree Triangulation. Proceedings of the IEEE Visualization '98, (1998) October 18-23; Research Triangle Park ,North Carolina, USA

DOI: 10.1109/visual.1998.745280

[12] Katajainen J. Tree compression and Optimization with Applications. International Journal of Foundations of Computer Science, Vol.1 No.4(1990), 425-447