Terrain Rendering LOD Algorithm Based on Improved Restrictive Quadtree Segmentation and Variation Coefficient of Elevation

Zhenwu Wang and Xiaohua Lü

(Department of Computer Science and Technology, China University of Mining and Technology, Beijing 100083, China)

Abstract: Aiming to deal with the difficult issues of terrain data model simplification and crack disposal, the paper proposed an improved level of detail (LOD) terrain rendering algorithm, in which a variation coefficient of elevation is introduced to express the undulation of topography. Then the coefficient is used to construct a node evaluation function in the terrain data model simplification step. Furthermore, an edge reduction strategy is combined with the improved restrictive quadtree segmentation to handle the crack problem. The experiment results demonstrated that the proposed method can reduce the amount of rendering triangles and enhance the rendering speed on the premise of ensuring the rendering effect compared with a traditional LOD algorithm.

Key words: terrain data model simplification; crack disposal; level of detail (LOD) terrain rendering algorithm; variation coefficient of elevation; node evaluation function; restrictive quadtree segmentation

In recent years, virtual reality technology has become the hotspot for academic and industry researchers, and three-dimensional terrain visualization is an important application field. Generally, large-scale terrain needs render millions or tens of thousands triangular patches, which is a heavy burden for the computer system, and levels of detail (LOD) technology[1]has been applied to simplify terrain data on the premise that does not affect the vision effect, which can reduce the geometry complexity of the terrain scenes and save real-time roaming time.

The main technologies of LOD models include pyramid hierarchical data organization, node evaluation system, visibility culling, cracks repair, smoothing and graphics rendering. For a pyramid hierarchical data organization, quadtree segmentation is an important method and its different variants had been proposed.Von Herzen[2]introduced the restricted quadtree(RQT) segmentation into the LOD model, which can ensure the number of layer gap is not more than 1 among adjacent data blocks; Referring to the Geomipmapping algorithm, Ref. [3] firstly divided terrain data into quadtree, then some operations had been adopted, including down-sampling, zooming and translation; Zhang[4]proposed a novel quadtree model, which required the adjacent tiles to share one row and one column of data; Ref.[5] constructed two RQTs:the data tree is used to store terrain data, and the logic tree stored the operation information of data tree, such as node information and visibility culling information, and Hou[6]adopted a diamond block method, which actually is a variant of quadtree. For the node evaluation system, the main influential factors include the distance between terrain blocks and viewpoint[7], and the roughness of terrain blocks[8-9]. Different bounding boxes have been constructed to cut graphics, which include view frustum[10], radar view frustum[11]and square bounding box[12].For the crack repair problem, different methods have been proposed, such as edge reduction method[12-13], vertical skirt method[14]and restrictive quadtree method[15].Among all the smoothing algorithms, the geometric transition algorithm[16]is one of the most important smoothing methods. Although the research work of LOD technology has achieved remarkable results, there are some unresolved bottlenecks, for example, ① the simplification of terrain data model, especially the construction of node evaluation function; and ② the crack problem in real-time roaming among adjacent data blocks which have different display precisions, the work focuses to deal with the above referred two issues and therefore an improved LOD algorithm is proposed.

The rest of this paper is organized as follows. Section 1 gives the related work about LOD model, the details of proposed LOD algorithm are discussed in section 2 and in section 3, performance evaluation is discussed, and section 4 concludes this work.

1 Related Work

For constructing a node evaluation function, the traditional factors are visual correlation factor and topographic change factor, for example, Lei[9]proposed a least square method to express the roughness of topography. Based on the traditional factors, some researchers[17-24]introduced other factors to the node evaluation function. Wu[17]added the motion vector and observation vector into a traditional method, Zhao[18]considered the screen projection error, and Peter[19]mainly considered the object space error and screen space error. If there are too many considerations in the evaluation system, it would pose big challenges to the computer system, although it leads to more realistic and accurate visual experiences. Researchers also introduced some other methods to simplify LOD model.Dong[20]proposed a seamless terrain rendering algorithm based on GPU, which conducts coarse granularity tile mesh on CPU,and subdividing fine granularity patch mesh on GPU; Wei[21]proposed a wavelet-progressive-reconstruction algorithm to realize a smooth transition between multi-resolution models, Zhang[22]considered the topological relations between quadtree nodes and their sub-nodes to simplify the LOD model. The above methods improved the LOD algorithm according to different aspects, and how to simplify the terrain data model on the premise of guaranteed rendering quality and fluency a research emphasis. Considering visual correlation factors comprehensively, the paper introduces variation coefficient of elevation to measure the terrain roughness, which constructs the proper node evaluation function to realize the multi-resolution display for terrain data.

In the model optimization step, different methods have been proposed to eliminate the “popping” problem. Hoppe[25]adopted an edge reduction method to solve the crack problem among adjacent nodes, in which the tree depth is supposed to vary evenly; Lan[26]used linear and power functions to extract boundary cracks, and adopted edge reduction and embordering methods to eliminate cracks. Restricted quadtree[27]is an important method to handle the crack problem, and Deng[28]applied this method to realize that the level of the adjacent nodes is not more than 1, and then erased the crack points when high resolution nodes are rendered. Ref. [25] considered the sight range and vertex height difference synthetically in order to ensure a small hierarchy gap, but it cannot handle the situation where the gap between adjacent nodes is 1.In this paper, the layer gap is less than 1 during the construction of the restricted quadtree model, and if the gap is 1, this situation has been handled by judging the crack property and the relative position between node and viewpoint.

2 Description of Proposed Method

During the LOD-based terrain rendering process, it is necessary to consider a series of factors influencing the construction of the node evaluation function, the fundamental reason is that there is a balance between rendering speed and quality. This paper improved the LOD model in two aspects: the construction of node evaluation function, and the elimination of cracks.

2.1 Node evaluation function improvement

For constructing node evaluation function, the improved LOD algorithm concerns the following factors.

① Viewpoint factor

(1)

② Topographic relief factor

The paper introduces a variation coefficient of elevation[29]to describe the topographic relief, which reflects the elevation variation of each vertex of terrain unit grid, it can be defined as

(2)

(3)

The paper computes the roughness degree using the elevation value set, which includes 9 vertices in the quadrilateral block (one quadtree node). Supposing the elevation value set is {dh0,dh1,…,dh8},dh0-dh4represents the difference values of the center point respectively, and 4 edge center points before and after node subdivision are described in Fig.1. In addition, the paper also concerns the topological structure between node and its 4 sub-nodes, and adds roughness information of all the sub-nodes (dh5-dh8).

Fig.1 Roughness description

The roughness can be described by (n=9)

(4)

(5)

(6)

Combined Eqs.(1) (4), the node evaluation function of LOD model is defined as

(7)

whereC1is the dynamic error control threshold,C2is the control threshold of terrain roughness to LOD screen contribution. If Eq.(7) satisfies the condition, the data block need be further subdivided until reaching the bottom data.

2.2 Crack elimination method improvement

It leads to the crack problem that there are different numbers of vertices in adjacent nodes, which are used to construct the triangulated irregular network model, and the RQT can eliminate the cracks which constrains the relations among nodes in the quadtree. When constructing the RQT, the following relations should be satisfied[30]:

① All the vertices in the 0thlayer may participate in building grids;

② Start with theithlayer (i≥1), constraining the center vertex and vertices on the diagonals in theithdata block;

③ Start with theithlayer (i≥1),constraining the boundary vertices and the center vertices on the adjacent nodes in the vertical or horizontal directions in the current layer;

According to the above constraint rules, it can ensure that the adjacent nodes can only differ from one level of detailed data, and it has some obvious flaws, for example, it cannot deal with the situation where the layer difference is 1, however the situation cannot be ignored in most cases. Based on the RQT, the paper continues to handle the situation in which the layer difference is 1 by introducing “raised crack ”,“dropped crack” and edge reduction method, which can be a perfect combination of RQT. Ref. [14] referred to the conceptions of “raised crack” and “dropped crack”, which is described in Fig.2.

Fig.2 Raised crack and dropped crack

In Fig.2, the raised crack is ΔCDEand the dropped crack is ΔABC. From viewpointo, ΔABCneeds be handled and ΔCDEcan be ignored because the height of vertexDis higher than those of center point ofCEedge, which can reduce the workload of crack handling, the detailed process is described in Fig.3.

Fig.3 Process of crack elimination

Beyond raised and dropped cracks, some other cracks also need be further solved, described in Fig.4. There are some methods to handle the situation in Fig.4, for example, ΔMPQis regarded as one independent unit to render, but this operation may show an obviously partition on edgeMP, another method is to change the elevation value of pointQto the average elevation value ofMN, but big deviation can occur when theQvalue is too large. In addition, ΔLMPcan be divided into ΔLQMand ΔLQP, but if the data scale is large, the extra workload cannot be ignored. In this paper, an edge reduction method is adopted to handle the crack problem, which cannot bring extra triangles, although this method cannot handle the situation in which the layer gap is more than 1, it can combine with the RQT model perfectly.

Fig.4 Other crack solutions

3 Performance Evaluation

In this work, the Perlin noise method is adopted to generate terrain elevation data, and the hardware/software environment is listed as follows: CPU is Intel(R) Xeon(R) CPU E3-1226 v3 @3.30 GHz 3.30 GHz; Memory is RAM 4.00 GB; The operating system is Microsoft Windows7 Professional SP1, 32 bit, the development platform is Microsoft Visual Studio.NET 2013 and DirectX9.0c, the programming language is C++. As described in Fig.5, the marked area on the proposed LOD method uses fewer triangles than those of the traditional LOD algorithm, but it doesn’t affect the overall rendering effects.

Fig.5 Grid picture

The parameters areC1=3 andC2=30, and the grid figures are described in Fig.5.Compared with the traditional LOD method, the proposed algorithm used fewer triangles to describe the flat terrain blocks, and it has a better rendering performance in the premise that the display effects are not affected.

From Tab.1, it can be observed that the traditional LOD method screened out 2 095 421 triangles, the percentage is 99.72% and the frames per second(FPS) is 194 which is 6.08 times to the non-simplification method, the percentage of proposed method is 99.74%, the FPS is 226 which is 8.69 times to the non-simplification method.

Tab.1 Parameter comparison

In Fig.6, under different terrain scales, the FPS of proposed method is not lower than those of traditional RQT algorithm, and the detailed information of rendering triangles is shown in Tab.2.

Fig.6 FPS comparison

Vertex numberTotal trianglesnumberActual rendering triangles numberRQTProposed method2631695263381947419053105062521012502899727106419840183968027381563663

In Tab.2, the quantities of actual rendering triangles have been reduced from 19 474, 28 997, and 73 815 to 19 053, 27 106 and 63 663 when vertex numbers are 263 169, 1 050 625, and 4 198 401 respectively, the triangles have been simplified furtherly.So the proposed method can render fewer triangles and has a higher rendering speed on the premise of ensuring the rendering effects.

4 Conclusion

LOD techniques are widely used in the simplification of large-scale terrain data, although LOD algorithms have been extensively investigated worldwide, there are still some bottleneck problems in LOD models. Aiming at solving two difficult problems in LOD models, this paper presents an improved method, which uses variation coefficients of elevations to present the terrain roughness, and combines the RQT and edge reduction method to eliminate cracks, the experiment results demonstrated the validity of the proposed method. The current work focuses on the improvement of LOD algorithm itself, in the future research projects, collaboration between CPU and GPU can be introduced into the proposed method, which can promote the loading efficiency of terrain data, and another issue is to enhance the fidelity by using realistic graphics rendering technology.