Integration method of TINs and Grids for multi-resolution surface modeling

Abstract

Highly detailed surface models and their real-time applications are increasingly popular in architecture, construction and other design and engineering fields. However, new and related problems have emerged concerning the efficient management of the resulting large datasets and the seamless integration of heterogeneous data. Moreover, the increasingly common requirements of local high-fidelity modeling combined with large-scale landscapes lead to difficulty in the seamless multi-resolution representation of hybrid triangulated irregular networks (TINs) and Grids. This paper presents a hybrid data structure with high-efficiency and a related organizational method for the seamless integration of multi-resolution models. This approach is characterized by (1) a self-adaptive algorithm for feature-preserving surface partitioning, (2) an efficient hybrid index structure for combined Grid and TIN surfaces, and (3) a view-dependent scheduling strategy with access to Grids of necessary resolution, giving priority to the dynamic loading of TINs. Experiments using typical real design datasets of highway constructions are able to achieve accuracy-preserved and real-time availability of results that prove the validity and efficiency of this approach.

Keywords:

• surface modeling
• TIN
• Grid
• LoDs
• high fidelity

1. Introduction

Large-scale realistic landscape models and/or highly detailed surface models have become increasingly popular in the architecture, construction engineering, and other fields (1). The local high-fidelity surface modeling embedded in large-scale landscapes facilitates not only the macro-overviews but also the local accuracy of the analysis (1 , 2 , 3 , 4). Two crucial aspects are (1) the efficient management of the resulting large datasets for real-time applications and (2) the seamless and high-fidelity integration of heterogeneous multi-resolution data.

Triangulated irregular network (TIN) and Grid are two common data models used to represent surfaces which have advantages in flexible performance and as a compact-regular data structure, respectively (1). These data models are therefore suitable for the representation of multi-resolution geographical objects with different morphological characteristics: Grid is used for the large-scale and continuous terrain surfaces, while TIN is better for the local and elaborate buildings, transportation facilities, etc. Consequently, given the variety in the amount of data and the levels of detail (LoD) between the different data sources during their high-fidelity integration, discrepancies and corresponding difficulties are obviously emerging with regard to the following: (1) the inconsistency in geometry, topology, and semantics between heterogeneous datasets; (2) the diverse resolutions and accuracies that originating from different data sources and design standards, both in the homogeneous and heterogeneous datasets; (3) the gap between the enormous volume and the processing capabilities of current workstations, which increases the difficulties in real-time applications of integrated highly detailed datasets. Existing investigations of solutions for these problems can be divided into two categories: unified Grid- or TIN structure-based multi-resolution methods and hybrid methods (4 , 5). The first category, which is based on geometric homogenization between heterogeneous, multi-resolution datasets, typically includes the Grid-based (6 , 7) and TIN-based methods (4 , 8 , 9 , 10 , 11 , 12). Compared with the simple regular data structure of the Grid-based model, the TIN-based model has a better ability to represent more detailed morphological features with a more complex topological structure. The second category, which geometrically combines both the Grid-based and TIN-based models, primarily addresses the problems of improving the topological validity or structure optimization with a finite data volume for visualization applications (5 , 13).

This paper aims to represent multi-resolution, large-scale surface models and proposes a comprehensive approach for the seamless integration of TINs and Grids and the related high-efficiency organization of the multi-resolution heterogeneous surface datasets with the unified coordinate system embedded in 3D space. The remainder of this paper is organized as follows: Section 2 introduces a multi-resolution hybrid surface structure integrating TINs and Grids. Section 3 presents the methodology for high-efficiency organization of large integration datasets. The experimental results and further analyses are outlined in Section 4. Finally, concluding remarks are presented in Section 5.

2 Multi-resolution hybrid surface structure integrating TINs and Grids

A complex surface model usually consists of a type of mesh model that is seamlessly integrated with multi-resolution source data within different structures. To maintain a good trade-off between feature fidelity and mesh cost, an effective solution for the complex surface representation can be achieved by applying the hybrid multi-resolution model of the global Grids and the locally embedded TINs within LoD. In particular, the hybrid structure makes it possible and convenient to refine the existing Grid-based structures by adding the necessary details to the local regions of interest without the requirement of increasing the whole grid resolution or converting the whole terrain model into a TIN-based representation (14). Therefore, assuming that the initial surface can be represented by a Grid-based surface model with multiple LoDs, from high resolution to low resolution, the proposed complex multi-resolution surface LoD(S) can be defined as the integrated abstraction of multi-level TINs and Grids:

where S_i represents a surface tile; RM and FM represent the geometrical models of the Grid-based regular surface tile (R-Tile) and the TIN-based feature-crossed surface tile (F-Tile), respectively; O_x and O_y are the down-left corner coordinates of the Grid tiles; N_r and N_c are the numbers of rows and columns of the Grid tiles; R_x and R_y are the resolutions of the grid cells of the R-Tiles; Z is the elevation set of the Grid vertices; V_c and T_c are the vertex and triangle array of constrained Delaunay TIN (CD-TIN); and V_f and T_f belong to the feature TIN (F-TIN). The proposed multi-resolution hybrid surface structure is illustrated in Figure 1.

Figure 1 Multi-resolution hybrid surface structure integrating TINs and Grids.

Each LoDi is an aggregation of regularly subdivided and special adjoining surface tiles, these tiles do no overlap, regardless of whether they exist in the same LoD or in different LoDs. Each surface tile can be encoded as either a R-Tile with no detailed features represented by Grid or as a F-Tile represented by TIN. Particularly, each F-Tile is composed of two feature boundary-correlative parts: a set of feature TINs (F-TINs), which usually represents high-detail features, and a constrained delaunay TIN (CD-TIN) constrained by the original Grid and the feature boundaries.

Based on the high-detail source data, the highest LoD tiles in this model could be first created using a quad-tree partition with the help of common boundary profiling algorithms (15), which take into account the different spatial distributions of the features, including (1) blocking for the continuous area objects; (2) sectioning for the linear objects, and (3) assigning for the discrete objects. Subsequently, layer by layer generalization of each surface tile, including a comprehensive generalization of geometry, topology, semantics, and texture, could be employed to create the upper LoDs. Different generalization strategies are required by Grids, CD-TINs, and F-TINs: (1) the commonly used suction method for Grid, (2) classical mesh simplification algorithms for CD-TIN (16), and (3) the semantics-constrained generalization of F-TIN including complex man-made features containing internal structure and authentic architectural components (17).

3 High-efficiency organization of large integrated datasets

3.1 Adaptive surface partition

For the fast surface partitioning and the highly efficient index of the large-scale hybrid datasets, the quad-tree organization of multi-resolution surfaces is employed, and the tree nodes are used to represent the surface tiles of different LoDs, as shown in Figure 1. The critical issue of hybrid surface partitioning is the size of the F-Tiles composed of CD-TIN and F-TIN. The larger the tile size, the larger the data volume becomes, which may result in I/O bottlenecks. The smaller the tile size, the more difficulties will emerge in the partitioning of the CD-TIN. Therefore, we suggest the following rules to determine the proper tile size:

•	Rule 1: The number of triangles included in any F-Tile Si cannot exceed x (maximum number of triangles).
•	Rule 2: The area ratio of the feature-crossed region to another region must not be less than u times the possible minimum area ratio.

It can be concluded that if S_i is a higher-LoD surface tile and S_i FM, then S_j FM and S_i is the corresponding lower-LoD surface tile of S_i Moreover, it is strictly defined that if a triangle t_k in FM or a square q_k in RM exists, it must be contained by one and only one tile, that is, if q_k   S_i and q_k  S_j , then k = j. After the total number of triangles of the feature is determined, the minimum number of F-Tiles c is computed using x. Subsequently, the minimum bounding rectangle of the whole feature is computed. Finally, the result n can be adjusted according to the total performance of the selected system.

After the partitioning of geometrical models, the corresponding images/textures will also be partitioned according to the partitioned surfaces to supporting an accordantly dynamic scheduling. It is worth mentioning that the objects in each surface tile should be optimized according to the merging of the surfaces having the same material/texture into one object to reduce the cost of repeatedly preparing the same material/texture for further applications, such as efficient rendering.

3.2 Out-of-core data organization

Because the integration datasets from multi-resolution surface modeling often far exceed the size of the main memory, it is necessary to store the surface data in external storage and then load the surface tiles dynamically into the memory, using efficient out-of-core data management. As illustrated in Figure 2, after the surface partitioning, the grid surface tiles in each LoD layer of RM can be initially stored in a database table, the name of which is recorded by the ST_GRID_Table field in the LoD layer table. Here, each surface tile ID (indicated as ST_ID) is not assigned a unique number by a binary combination of the tile’s row and column indexes. All of the surface tile types (indicated as ST_TYPE) are initially encoded as RM.

Figure 2 Out-of-core surface data management.

After the surface integration, a new table will be created, namely, ST_UPDATE_Table. This table can be regarded as an updated version of the ST_GRID_Table. It records all of the F-Tiles and the appropriate updated dataset of CD-TIN and F-TIN. For crack elimination in scene rendering, which is illustrated in the following section, the surface tile boundary data will also be stored.

3.3 View-dependent multi-resolution scheduling strategy

The view-dependent multi-resolution scheduling strategy has become a critical technique in large-scale, interactive visualization of massive terrain surfaces. The typical LoD assignment of the surface tiles from a certain point of view is shown in Figure 3(a). Based on the proposed hybrid surface structure, more attention is focused on the following dynamic scheduling rules:All-Priority Rule: When different types of tiles with the same level are accessed as quad-tree leaf nodes using a traditional view-dependent scheduling strategy, the LoD priority will be given to the F-Tiles, that is, their levels will be automatically changed to the next finer level. This rule is useful when the CD-TIN and F-TIN regions are must be quickly identified at a higher level of detail from among the surrounding grid-based tiles of the same LoD.Along-Roaming Rule: To roam along the transit-line features (e.g. highway, subway or railway), it is most useful to observe such features at higher LoD when they are located directly ahead at a user-defined distance. If one F-Tile is in the specified range, it will be automatically changed to the highest level in the current quad-tree partition, regardless of level at which this tile was initially accessed. As shown in Figure 3(b), after this rule is applied, the tile that is directly ahead will continue to be split into four leaf nodes.

Figure 3 View-dependent multi-resolution scheduling strategies. (a) LoD spatial distribution of surface tiles according to classical quad-tree partitioning. (b) Adjusted view-dependent scheduling result after application of the along-roaming rule.

One of the most serious challenges in maintaining the surface visual continuity is the reliable elimination of cracks between the adjacent surface tiles with different structures and resolutions. The so-called T-junction phenomenon along the higher and lower resolution grid tile edges in the RM model can be easily removed by applying a mesh refinement algorithm. However, the problem is more complicated in the multi-resolution hybrid surface structure as there are three additional types of cracks between the adjacent tiles. The first type exists between Grid and CD-TIN, and it can be removed by applying the improved mesh refinement algorithm, as depicted in Figure 4(b). The second type of crack occurs between CD-TIN and CD-TIN and is caused by boundary intersection, with the same feature generating two points that coincide on the X–Y plane, although the adjacent tiles have different heights. Therefore, this type of crack can be eliminated equalizing the tile heights, as shown in Figure 4(c). The last type occurs between F-TIN and F-TIN and can be avoided when the lower F-TIN is created by applying the mesh simplification algorithms, which collapse inside the triangles, as illustrated in Figure 4(d).

Figure 4 Seamless visualization strategies within multi-resolution and neighboring surfaces. (a) T-junction (shaded in gray) between neighboring tiles with different resolutions. (b) Elimination of cracks between neighboring surface tiles: mesh refinement within Grid and mesh refinement between Grid and CD-TIN (shaded in yellow). (c) Crack (shaded in gray) between CD-TIN and CD-TIN. (d) Elimination of a crack using classical mesh simplification algorithms, which collapse inside triangles.

4 Experimental results and analysis

To validate the correctness and effectiveness of the proposed approach, a detailed dataset, involving highway construction model, is employed (Figure 5). This model is a complex surface model with multi-resolution and heterogeneous structure. This model includes the following design data: 23.7 km of highway data with a best resolution of 0.2 m and a variety of different features, such as roadbeds, side slopes, tunnels, bridges, etc.; 10.0 m resolution terrain survey data covering the highway areas; 10.0 m Ground Sampling Distance (GSD) satellite images covering the outskirts of highway areas and 2.5 m GSD aerial images covering the main highway areas and 10.0 m resolution aerial images covering the other highway areas. The total amount of data in terms of geometry, material and texture/images is 1.25 GB.

Figure 5 The original complex surface models of Tongcheng-Jieshang highway. (a) Highway models described by 85,114 triangles. (b) Terrain models described by 16,744,220 grid cells.

Based on the adaptive surface partitioning, the original dataset is firstly divided into 141 F-Tiles and 408 R-Tiles. In accordance with the hierarchical semantic relationships of highway models as shown in Figure 5(a), each surface tile is first generalized by removing trivial features from the leaf nodes. Subsequently, Delaunay and Boolean operators are employed among the retained features to classify reconstruction meshes and their topologies. In the next step, the semantics of the newly created surfaces are updated with the extraction of high-level semantics. The experimental dataset is, therefore, generalized into three LoDs.

The distance domain of the LoD scheduling is calculated according to the theory of “perceptual metric,” as illustrated by Zhu et al. (18). Examples of the multi-constraint generalization and view-dependent scheduling of a typical F-Tile are given in Figure 6. The results are consistent with respect to geometry, topology, and semantics.

Figure 6 The results of multi-constraint generation of LoD surface models. (a) LoD generalization of a F-Tile. (b) The distance domain of LoD scheduling.

The results of the seamless integration of the multi-resolution TINs and Grids, including the integration of (1) CD-TIN and F-TIN, (2) multi-resolution F-TINs and (3) multi-resolution Grids, are illustrated in Figure 7. The results demonstrate that the proposed method can achieve high fidelity in 3D roaming.

Figure 7 The results of the seamless integration of multi-resolution TINs and Grids. (a) Seamless scene integrated multi-resolution TINs and Grids. (b) Integration of CD-TIN and F-TIN. (c) Integration of multi-resolution F-TINs. (d) Integration of multi-resolution Grids.

Table 1 and Figure 8 illustrate the experimental results of the visualization efficiency with large-scale surface models. The software is installed in a Windows 7 OS environment based on a hardware platform equipped with (1) CPU: Intel(R) Core(TM) i7 920@ 2.67 GHz; (2) Memory: 4.00 GB; (3) NVIDIA Quadro NVS 135 M. The relatively stable frame rates demonstrate the effectiveness of our method.

Table 1. Analysis of view-dependent multi-resolution scheduling.

Views	No. of triangles/grid cells	No. of F-tiles/R-tiles	Frame rate of our method (unit: FPS)
(a)	9164/54,227	31/66	49.9
(b)	7019/45,822	17/27	53.7
(c)	6447/19,220	7/4	62.3
Original model	85,114/16,744,220	141/408	–

Figure 8 Multi-resolution scheduling based on view distance and quad-tree.

5 Concluding remarks

The integration method of TINs and Grids is widely considered to be an effective method for the representation of complex surface models. Addressing the coherent difficulties in the seamless integration of multi-resolution 3D surface models from large-scale heterogeneous datasets, this paper presents a highly efficient hybrid data structure integrating TINs and Grids, as well as a related organizational method that partitions the surface models using data adaptive strategies. Additionally, a view-dependent scheduling strategy with access to Grids of necessary resolution gives priority to the dynamic loading of TINs. This approach is able to provide consistent modeling, which preserves the local high-fidelity combined with large-scale landscapes and multi-scale real-time applications of the hybrid LoD surface models. The experimental results from a typical real highway model demonstrate the practicality and reliability of this approach in supporting multi-resolution 3D surface modeling and real-time application.

Notes on contributors

Xie Xiao is a successive postgraduate and doctoral student since September. 2009 in the state key laboratory of information engineering in surveying, mapping and remote sensing at Wuhan University. Her main research interests are 3D modeling, real-time GIS and virtual geographic environments.

Xu Weiping is a PhD student in the state key laboratory of information engineering in surveying, mapping and remote sensing at Wuhan University, Wuhan, China. His main research interests are 3D modeling, 3D GIS and virtual geographic environments.

Zhu Qing received his BS degree in 1986 and Master degree in 1989 in railway engineering from Southwest Jiaotong University, Chengdu, Sichuan, China. He received his PhD degree in railway engineering from Northern Jiaotong University, Beijing, China in 1995. He is a professor in the Faculty of Geosciences and Environmental Engineering of Southwest Jiaotong University, Chengdu, Sichuan, China. His main research interests are digital photogrammetry, real-time GIS and virtual geographic environments.

Zhang Yeting received his PhD degree in photogrammetry and remote sensing from Wuhan University, China in 2008. His main research interests are spatial database technology, 3D GIS and virtual geographic environments.

Du Zhiqing received his PhD degree in photogrammetry and remote sensing from Wuhan University, Wuhan, China in 2007. His main research interests are virtual geographic environments, 3D city modeling, disaster management and cultural heritage protection.

Acknowledgment

The work described in this paper was supported by National Natural Science Foundation of China (No. 41171311; No. 41021061) and National Basic Research Program of China (No. 2012CB725300).