Journal of Computer Science and Technology ›› 2018, Vol. 33 ›› Issue (6): 1192-1203.doi: 10.1007/s11390-018-1881-9

Special Issue: Computer Graphics and Multimedia

• Computer Graphics and Multimedia • Previous Articles     Next Articles

Back-to-Front Ordering of Triangles in Digital Terrain Models over Regular Grids

Jesús Alonso1, Robert Joan-Arinyo1,2,3,*   

  1. 1. Informatics in Engineering Group, Technical University of Catalonia, 08028 Barcelona, Catalonia;
    2. Center for Biomedical Engineering Research, Sant Joan de Déu Research Institute, 08028 Barcelona, Catalonia;
    3. Visualization, Interaction and Virtual Reality Group, Technical University of Catalonia, 08028 Barcelona, Catalonia
  • Received:2017-07-11 Revised:2018-09-26 Online:2018-11-15 Published:2018-11-15
  • Contact: Robert Joan-Arinyo,
  • About author:Jesús Alonso is an assistant professor at the Department of Computer Science of the Technical University of Catalonia (UPC), Barcelona. He obtained his M.Sc. degree in computer science from the UPC in 2004 and he is a researcher of the UPC where his research is mainly devoted to video games. He has been the director of the UPC Multimedia and Image Center as well as the manager of a number of teaching programas including video games development, game design, digital art, animation and mobile apps.
  • Supported by:
    This work was supported by the Spanish Ministerio de Economia y Competitivided and European Regional Development Fund (FEDER) under Grant No. TIN2017-88515-C2-1-R.

Visiting triangles that conform a digital terrain model is a core operation in a number of fields like animation and video games or generating profiles, cross-sections, and contours in civil engineering. Performing the visit in an efficient manner is an issue specially when the output of the traversal depends in some way on additional parameters or information changing over time, for example, a moving point of view. In this work we report a set of rules that, given a digital terrain model defined over a regular grid and an arbitrary point of view outside the terrain, define a total back-to-front order in the set of digital terrain model triangles with respect to the point. The set of rules is minimal, complete and correct. To assess how the rules perform, we have implemented a CPU-based algorithm for realistically rendering height fields defined over regular grids. The algorithm does not make use of the z-buffer or shaders featured by our graphics card. We show how our algorithm is implemented and show visual results obtained from synthetic and real data. We further discuss the algorithm performance with respect to two algorithms:a naive algorithm that visits triangles according to grid indices and does not solve the hidden line problem, and the z-buffer provided by the graphics card featured by our computer. Our algorithm allows real-time interaction when the point of view arbitrarily moves in 3D space and we show that its performance is as good as that of the z-buffer graphics card.

Key words: back-to-front ordering; digital terrain model; elevation terrain model; triangle strip; visibility;

[1] Fan M, Tang M, Dong J. A review of real time terrain rendering techniques. In Proc. the 8th International Conference on Computer Supported Cooperative Work in Design, May 2004, pp.685-691.
[2] Pajarola R, Gobetti E. Survey of semiregular multiresolution models for interactive terrain rendering. The Visual Computer, 2007, 23(8):583-605.
[3] Losasso F, Hoppe H. Geometry clipmaps:Terrain rendering using nested regular grids. ACM Transactions on Graphics, 2004, 23(3):779-776.
[4] Engel W. ShaderX2:Shader Programming Tips & Tricks with DirectX 9. Wordware Publishing Inc., 2004.
[5] Frieder G, Gordon D, Reynolds R A. Back-to-front display of voxel-based objects. IEEE Computer Graphics and Applications, 1985, 5(1):52-60.
[6] Wang S L C, Staudhammer J. Visibility determination on projected grid surfaces. IEEE Computer Graphics & Applications, 1990, 10(4):36-43.
[7] Anderson D P. Hidden line elimination in projected grid surfaces. ACM Transactions on Graphics, 1982, 1(4):274-288.
[8] Swan Ⅱ J E. Object-ordered rendering of discrete objects[Ph.D. Thesis]. Department of Computers and Information Science, The Ohio State University, 1998.
[9] Yoon H S, Jung M J, Han J H. Alternation of level-of-detail construction and occlusion culling for terrain rendering. In Proc. the 1st International Symposium on Computational and Information Science, December 2004, pp.1161-1167.
[10] Bhattacharjee S, Narayanan P J. Real-time painterly rendering of terrains. In Proc. the 6th IEEE Indian Conference on Computer Vision, Graphics and Image Processing, December 2008, pp.568-575.
[11] Chen G, Sander P V, Nehab D, Yang L, Hu L. Depthpresorted triangle lists. ACM Transactions on Graphics, 2012, 31(6):Article No. 160.
[12] Deb S, Bhattacharjee S, Patidar S, Narayanan P J. Realtime streaming and rendering terrains. In Proc. the 5th IEEE Indian Conference on Computer Vision, Graphics and Image Processing, December 2006, pp.276-288.
[13] Samet H. The Design and Analysis of Spatial Data Structures. Addison-Wesley, 1990.
[14] Agrawal A, Radhakrishna M, Joshi R C. Geometry-based mapping and rendering of vector data over LOD phototextured 3D terrain models. In Proc. the 14th International Conference in Central Europe on Computer Graphics, Visualization and Computer Vision, January 2006, pp.1-8.
[1] Liu-Xin Zhang (张柳新), Member, CCF, Ming-Tao Pei (裴明涛), Member, CCF and Yun-De Jia (贾云得), Senior Member, CCF. Multiview Visibility Estimation for Image-Based Modeling [J]. , 2011, 26(6): 1000-1010.
[2] Fei Wu(吴 飞), Senior Member, CCF, Ya-Hong Han(韩亚洪), and Yue-Ting Zhuang(庄越挺), Member, IEEE. Multiple Hypergraph Clustering ofWeb Images by MiningWord2Image Correlations [J]. , 2010, 25(4): 750-760.
[3] Xue-Hou Tan. Searching a Polygonal Region by a Boundary Searcher [J]. , 2009, 24(3): 505-516.
[4] Xue-Hou Tan and Bo Jiang. Searching a Polygonal Region by Two Guards [J]. , 2008, 23(5 ): 728-739 .
[5] Wen-Cheng Wang, Feng Wei, and En-Hua Wu. View Dependent Sequential Point Trees [J]. , 2006, 21(2): 181-188 .
Full text



[1] Liu Mingye; Hong Enyu;. Some Covering Problems and Their Solutions in Automatic Logic Synthesis Systems[J]. , 1986, 1(2): 83 -92 .
[2] Chen Shihua;. On the Structure of (Weak) Inverses of an (Weakly) Invertible Finite Automaton[J]. , 1986, 1(3): 92 -100 .
[3] Gao Qingshi; Zhang Xiang; Yang Shufan; Chen Shuqing;. Vector Computer 757[J]. , 1986, 1(3): 1 -14 .
[4] Chen Zhaoxiong; Gao Qingshi;. A Substitution Based Model for the Implementation of PROLOG——The Design and Implementation of LPROLOG[J]. , 1986, 1(4): 17 -26 .
[5] Huang Heyan;. A Parallel Implementation Model of HPARLOG[J]. , 1986, 1(4): 27 -38 .
[6] Min Yinghua; Han Zhide;. A Built-in Test Pattern Generator[J]. , 1986, 1(4): 62 -74 .
[7] Tang Tonggao; Zhao Zhaokeng;. Stack Method in Program Semantics[J]. , 1987, 2(1): 51 -63 .
[8] Min Yinghua;. Easy Test Generation PLAs[J]. , 1987, 2(1): 72 -80 .
[9] Zhu Hong;. Some Mathematical Properties of the Functional Programming Language FP[J]. , 1987, 2(3): 202 -216 .
[10] Li Minghui;. CAD System of Microprogrammed Digital Systems[J]. , 1987, 2(3): 226 -235 .

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
  Copyright ©2015 JCST, All Rights Reserved