# A Fast Scheduling Method for Massive Oblique Photography 3D Models

Authors: Ruibo Chen; Ruichao Qu; Jiaxing Chen; Jiangtao Lei; Yitan Luo; Rundong Liu; Zhanyu Ma
Journal: Wireless Communications and Mobile Computing
 (2022)

---

## Abstract

In view of the large amount of oblique photography 3D model data and the fact that high-performance hardware devices cannot load and render massive oblique photography 3D models at one time, this paper provides a fast scheduling method for massive oblique photography 3D models: get the tile radius, side length, scheduling range, and other parameters from the original data, normalize the original tile to a hundred grid, use a regular grid + quadtree + hexadecimal tree to build a tile spatial index, resample the tile data at each level to generate the elevation model DEM and the real radiographic image TDOM, and use the DEM+TDOM method to reconstruct the layered and block top-level 3D model to achieve rapid scheduling and rendering of massive oblique photography 3D models. Experiments show that the method is efficient and feasible and can meet the visualization and real-time interaction requirements of massive urban 3D models.


---

## Body

## 1. Introduction

The Ministry of Natural Resources has issued the “Technical Outline for Real 3D China Construction,” which clarifies that the construction content of real 3D China includes three levels of real 3D construction: terrain level, city level, and component level [1], with city-level real 3D model data. Generally, oblique photogrammetry technology is used for production, and the amount of 3D model data of the scene can reach TB level or even massive, far exceeding the storage and management capabilities of ordinary computers. At the same time, it puts forward higher requirements for the organization and scheduling of massive 3D data. Due to the complex data structure of the 3D model and the large amount of data, it often causes difficulties in transmission and rendering, which in turn affects the visualization efficiency. Therefore, it is necessary to establish a reasonable 3D model organization structure, management, and scheduling method to optimize the model calling mechanism and accelerate the loading and operation of 3D models, the process of rendering and thus visualization. In the case of massive 3D data, the effect of the above optimization is more obvious. At present, methods such as improving quadtree [2–8], octree, KD tree, and three-dimensional R tree are commonly used or combined (referenced) to organize construction and scheduling.At present, GIS technology is developing rapidly, but how to meet the application of massive 3D data is an urgent problem to be solved. Oblique photography technology has its obvious advantages, that is, it can meet the needs of rapid acquisition and rapid modeling of large-scale 3D data. It has high precision, low cost, high efficiency, and real effects. It will be very promising in projects such as smart city construction, but how to apply massive 3D data conveniently and efficiently is its pain point.With the development of computer technology, the use of high-performance hardware equipment to load and render oblique photography 3D model data has played a certain role, but it is still impossible to load and render city-level 3D model data at one time [9, 10]. The model data organization method is optimized, and a new spatial index is constructed by using the regular segmentation method. Move and load the tilted model within a certain range. This method has better effect when loading a small scene range, but in a large scene range, more tile files need to be loaded to realize the display of the entire large scene, thus affecting the efficiency of scheduling and system performance. In response to these problems, this paper provides a fast scheduling method for massive 3D models of oblique photography: take the tile in the 3D data of oblique photography as the basic unit, obtain parameters such as center point, LOD (levels of detail) scheduling range, specify the number of levels, and use the method of combining regular grid + quadtree and hexadecimal tree that hierarchically grade all tiles according to regular grid, and resample the tile data of each level to generate an elevation model DEM and a real projection image TDOM. The top-level 3D model is reconstructed in layers and blocks, and the rapid scheduling and display of inclined 3D model data in a large scene range are realized.


## 2. Scheduling Method of Massive Oblique Photography 3D Model

### 2.1. Obtaining the Original Parameters

The tile pyramid model is a common multiresolution hierarchy structure, which is often used in 2D maps and 3D terrain services. The change of the visible field range dynamically selects the tiles suitable for the resolution to load.During the data production process, the oblique photography 3D model will generate metadata files according to the actual location of the survey area and organize the oblique photography 3D model data in a folder formed by the tile + grid row and column number that stores the 3D model data of different levels in the grid unit. Based on the metadata file and the 3D model data at each level in the tile folder, the original parameters of the oblique photography 3D model are calculated and obtained: radius dR, side length dS, and top-level LOD scheduling range dRange. On the basis of reading the original parameter data, calculate the distance coefficientn of LOD (levels of detail) according to the following formula:
(1)2n=dRangedR.Among them,n is the LOD distance coefficient of the tile, dRange is the scheduling range of the top LOD, and dR is the tile radius.


### 2.2. Organization of Oblique Photography Model Based on Regular Grid + Quadtree + Hexadecimal Tree

Spatial index, also known as spatial access method, is a description of data location information stored on the medium and refers to a data structure arranged in a certain order according to the location and shape of spatial objects or a certain spatial relationship between spatial objects, which contains general information about the spatial object, such as the object’s identifying bounding rectangle and a pointer to the spatial object entity. As an auxiliary spatial data structure, the spatial index is between the spatial operation algorithm and the spatial object. It improves the speed and efficiency of the spatial operation by excluding the spatial objects that are not related to the specific spatial operation. In recent years, one of the main functions of the rapid development of geographic information system is to retrieve spatial data and query the required information. As the key technology of spatial database and geographic information system, the performance of spatial index technology will directly affect the storage efficiency of spatial data and the performance of spatial retrieval, which is related to the overall performance of geographic information system. There are two commonly used object segmentation methods in GIS at present, the regular segmentation method and the object-based segmentation method. The spatial indexes corresponding to these two partitioning methods are spatial indexes based on regular grids (grid indexes, BSP tree indexes, and quadtree indexes) and spatial indexes based on object partitioning (R-tree family indexes). Among these index structures, grid spatial index, quadtree spatial index, and R-tree series spatial index are the most common. Efficient and rapid planning and establishment of a spatial index of real 3D model data is an important way to improve the rapid retrieval efficiency of oblique photography 3D model data.The method of establishing spatial index based on grid or R-tree, quadtree, etc. is widely used in the management of spatial data such as terrain and images [11], but in the 3D model of oblique photography, the index is only established inside the tile and the massive. In the process of scheduling and loading of oblique photography 3D model data, all tiles are only loaded in series, which cannot meet the needs of fast loading in practical applications. Therefore, this paper combines the convenience of regular grid division and the advantages of quadtree and hexadecimal in constructing spatial index in oblique photography model [12, 13], using regular grid + quadtree + hexadecimal tree way to construct a spatial index of oblique photographic models.


### 2.3. Building a Tile Hierarchical Block Grid Dictionary

The 3D model data of oblique photography is usually stored in the form of tile folders, and each tile stores the model data of various levels. During data production, the smaller the grid size used, the more tiles will be. Considering the actual situation of production operations, the grid size is usually between 100 m and 200 m. In the data scheduling of the oblique photography 3D model, the grid of the original data needs to be further hierarchically gridded to meet the needs of dynamic scheduling. The specific process of hierarchical gridization of the original tile in this paper is shown in Figure1.
(1)
The specified level grid contains the original number of tiles, calculates the size of the new grid, and normalizes itFigure 1
Process for building tile grid fields.According to the tile side length dS of the original data and the number of original tile contained in the gridn2, calculate the grid size according to formula (2):
(2)dGrideSide=dS×n.Among them, dGridSide is the grid size, dS is the original tile side length, andn is the base number of the original grids contained in the grid.The grid size dGridSide is shown in formula (3), so that the grid is an integer multiple:
(3)dGridSide=INTn×2×dRange2+50100×100.Among them, DGridSide is the grid size, dRange is the original Tile scheduling range, andn is the base number of the original grids included in the grid.
(2)
Establish a hierarchical block grid dictionary to determine the original Tile attributionLoop through all the original tile data, read the center point of each tile data, and determine the tile grid to which the tile center point belongs. If there is no corresponding tile grid in the tile grid dictionary, add an entry in the dictionary, such as follows: If there is, add it. The specific process is shown in Figure2:Figure 2
Regular grid establishment process.


### 2.4. Quadtree + Hextree Algorithm to Build Spatial Index

The quadtree index is a tree-structured data index proposed by Tayeb in 1998. Its principle is to divide a rectangular area into four subareas, and each subarea is divided into quarters again, recursively from top to bottom and operates until the number of elements contained in each subregion is less than or equal to the specified capacity. The quadtree has obvious spatial characteristics. According to the spatial characteristics of the quadtree, it can be used to make a spatial index.In the process of tile gridization and building a hierarchical block grid dictionary, the grid to which each tile belongs to has been determined. The hierarchies use different methods to build spatial indexes. This paper divides the hierarchy into three stages: the top layer, the middle layer, and the bottom layer. The top layer uses a regular grid to build a spatial index, and the number of grids on the8×8 top layer is the way to build a hexadecimal tree. The specific determination method of each stage is calculated by formula (4):
(4)TopLy=2x,x=0MiddleLy=2x,1≤x<2n/2BottomLy=2x,2n/2≤x≤n.,nisamultipleof2Among them, TopLy is the top-level range, MiddleLy is the middle level range, BottomLy is the bottom level range,x is the number of layers of the current layer, and n is the total number of layers of the layer.


### 2.5. DEM+TDOM Reconstruction Hierarchical Block Top Model

After the original oblique photographic data tile is layered and gridded, in order to speed up the fast loading of a certain block of data scheduled to the corresponding level, this paper rewrites the layered and divided tile data on the basis of the layered and divided grid. Build the top-level model data, so that after scheduling to a grid at the corresponding level, the top-level model data of the grid can be quickly scheduled and loaded, increasing the buffer time for scheduling more detailed model data and improving the smooth rendering of massive 3D model data. Based on the spatial index, the top-level model of the hierarchical block grid is reconstructed. The specific process is shown in Figure3.
(1)
Read the value in the block grid dictionary, and fit the radius dBlockR of the block grid by the least squares fitting method(2)
Resample to generate a tiled grid DEM (digital elevation model). Read the vertices of all tile data under the grid, merge to generate a discrete point array,100m×100m, resample the grid, calculate the elevation value of the corresponding grid point, and generate a block grid DEM file(3)
Generate a tiled grid TDOM (true projection image). Load the merged tile top-level data into the scene, set the pitch angle of the camera in the 3D scene to -90°, set the projection relationship to orthographic projection, and save the effect content in the scene to obtain a real projection image(4)
The top-level model of mesh construction and graphics is composed of block meshes. The DEM generated in (2) is used to construct an irregular triangular network as a skeleton, and the real projective image generated in (3) is textured to generate top-level model data(5)
Calculate the LOD viewing distance dEye of the top model data according to formula (5), and set it to the top model(5)dEye=dBlockR×2n/2.Figure 3
Reconstruction of layered and block top-level model.Among them, dEye is the LOD viewing distance, DBlockR is the block grid radius, andn is the level
(6)
Save the hierarchical block top model data


## 2.1. Obtaining the Original Parameters

The tile pyramid model is a common multiresolution hierarchy structure, which is often used in 2D maps and 3D terrain services. The change of the visible field range dynamically selects the tiles suitable for the resolution to load.During the data production process, the oblique photography 3D model will generate metadata files according to the actual location of the survey area and organize the oblique photography 3D model data in a folder formed by the tile + grid row and column number that stores the 3D model data of different levels in the grid unit. Based on the metadata file and the 3D model data at each level in the tile folder, the original parameters of the oblique photography 3D model are calculated and obtained: radius dR, side length dS, and top-level LOD scheduling range dRange. On the basis of reading the original parameter data, calculate the distance coefficientn of LOD (levels of detail) according to the following formula:
(1)2n=dRangedR.Among them,n is the LOD distance coefficient of the tile, dRange is the scheduling range of the top LOD, and dR is the tile radius.


## 2.2. Organization of Oblique Photography Model Based on Regular Grid + Quadtree + Hexadecimal Tree

Spatial index, also known as spatial access method, is a description of data location information stored on the medium and refers to a data structure arranged in a certain order according to the location and shape of spatial objects or a certain spatial relationship between spatial objects, which contains general information about the spatial object, such as the object’s identifying bounding rectangle and a pointer to the spatial object entity. As an auxiliary spatial data structure, the spatial index is between the spatial operation algorithm and the spatial object. It improves the speed and efficiency of the spatial operation by excluding the spatial objects that are not related to the specific spatial operation. In recent years, one of the main functions of the rapid development of geographic information system is to retrieve spatial data and query the required information. As the key technology of spatial database and geographic information system, the performance of spatial index technology will directly affect the storage efficiency of spatial data and the performance of spatial retrieval, which is related to the overall performance of geographic information system. There are two commonly used object segmentation methods in GIS at present, the regular segmentation method and the object-based segmentation method. The spatial indexes corresponding to these two partitioning methods are spatial indexes based on regular grids (grid indexes, BSP tree indexes, and quadtree indexes) and spatial indexes based on object partitioning (R-tree family indexes). Among these index structures, grid spatial index, quadtree spatial index, and R-tree series spatial index are the most common. Efficient and rapid planning and establishment of a spatial index of real 3D model data is an important way to improve the rapid retrieval efficiency of oblique photography 3D model data.The method of establishing spatial index based on grid or R-tree, quadtree, etc. is widely used in the management of spatial data such as terrain and images [11], but in the 3D model of oblique photography, the index is only established inside the tile and the massive. In the process of scheduling and loading of oblique photography 3D model data, all tiles are only loaded in series, which cannot meet the needs of fast loading in practical applications. Therefore, this paper combines the convenience of regular grid division and the advantages of quadtree and hexadecimal in constructing spatial index in oblique photography model [12, 13], using regular grid + quadtree + hexadecimal tree way to construct a spatial index of oblique photographic models.


## 2.3. Building a Tile Hierarchical Block Grid Dictionary

The 3D model data of oblique photography is usually stored in the form of tile folders, and each tile stores the model data of various levels. During data production, the smaller the grid size used, the more tiles will be. Considering the actual situation of production operations, the grid size is usually between 100 m and 200 m. In the data scheduling of the oblique photography 3D model, the grid of the original data needs to be further hierarchically gridded to meet the needs of dynamic scheduling. The specific process of hierarchical gridization of the original tile in this paper is shown in Figure1.
(1)
The specified level grid contains the original number of tiles, calculates the size of the new grid, and normalizes itFigure 1
Process for building tile grid fields.According to the tile side length dS of the original data and the number of original tile contained in the gridn2, calculate the grid size according to formula (2):
(2)dGrideSide=dS×n.Among them, dGridSide is the grid size, dS is the original tile side length, andn is the base number of the original grids contained in the grid.The grid size dGridSide is shown in formula (3), so that the grid is an integer multiple:
(3)dGridSide=INTn×2×dRange2+50100×100.Among them, DGridSide is the grid size, dRange is the original Tile scheduling range, andn is the base number of the original grids included in the grid.
(2)
Establish a hierarchical block grid dictionary to determine the original Tile attributionLoop through all the original tile data, read the center point of each tile data, and determine the tile grid to which the tile center point belongs. If there is no corresponding tile grid in the tile grid dictionary, add an entry in the dictionary, such as follows: If there is, add it. The specific process is shown in Figure2:Figure 2
Regular grid establishment process.


## 2.4. Quadtree + Hextree Algorithm to Build Spatial Index

The quadtree index is a tree-structured data index proposed by Tayeb in 1998. Its principle is to divide a rectangular area into four subareas, and each subarea is divided into quarters again, recursively from top to bottom and operates until the number of elements contained in each subregion is less than or equal to the specified capacity. The quadtree has obvious spatial characteristics. According to the spatial characteristics of the quadtree, it can be used to make a spatial index.In the process of tile gridization and building a hierarchical block grid dictionary, the grid to which each tile belongs to has been determined. The hierarchies use different methods to build spatial indexes. This paper divides the hierarchy into three stages: the top layer, the middle layer, and the bottom layer. The top layer uses a regular grid to build a spatial index, and the number of grids on the8×8 top layer is the way to build a hexadecimal tree. The specific determination method of each stage is calculated by formula (4):
(4)TopLy=2x,x=0MiddleLy=2x,1≤x<2n/2BottomLy=2x,2n/2≤x≤n.,nisamultipleof2Among them, TopLy is the top-level range, MiddleLy is the middle level range, BottomLy is the bottom level range,x is the number of layers of the current layer, and n is the total number of layers of the layer.


## 2.5. DEM+TDOM Reconstruction Hierarchical Block Top Model

After the original oblique photographic data tile is layered and gridded, in order to speed up the fast loading of a certain block of data scheduled to the corresponding level, this paper rewrites the layered and divided tile data on the basis of the layered and divided grid. Build the top-level model data, so that after scheduling to a grid at the corresponding level, the top-level model data of the grid can be quickly scheduled and loaded, increasing the buffer time for scheduling more detailed model data and improving the smooth rendering of massive 3D model data. Based on the spatial index, the top-level model of the hierarchical block grid is reconstructed. The specific process is shown in Figure3.
(1)
Read the value in the block grid dictionary, and fit the radius dBlockR of the block grid by the least squares fitting method(2)
Resample to generate a tiled grid DEM (digital elevation model). Read the vertices of all tile data under the grid, merge to generate a discrete point array,100m×100m, resample the grid, calculate the elevation value of the corresponding grid point, and generate a block grid DEM file(3)
Generate a tiled grid TDOM (true projection image). Load the merged tile top-level data into the scene, set the pitch angle of the camera in the 3D scene to -90°, set the projection relationship to orthographic projection, and save the effect content in the scene to obtain a real projection image(4)
The top-level model of mesh construction and graphics is composed of block meshes. The DEM generated in (2) is used to construct an irregular triangular network as a skeleton, and the real projective image generated in (3) is textured to generate top-level model data(5)
Calculate the LOD viewing distance dEye of the top model data according to formula (5), and set it to the top model(5)dEye=dBlockR×2n/2.Figure 3
Reconstruction of layered and block top-level model.Among them, dEye is the LOD viewing distance, DBlockR is the block grid radius, andn is the level
(6)
Save the hierarchical block top model data


## 3. Experimental Results and Analysis

This paper selects the oblique photography 3D data of four main urban areas of a city in Guangxi Zhuang Autonomous Region to verify and test the fast scheduling method provided in this paper. This paper selects the oblique photography 3D data of four main urban areas of a city in Guangxi Zhuang Autonomous Region to verify and test the fast scheduling method provided in this paper. The specific data is shown in Table1. To validate our method, all validation tests are performed on the same desktop computer (CPU: Intel i7 8-core 16-thread; graphics card: NVIDIA Quadro P5000; memory 32 GB; solid-state disk: 4 TB).Table 1
Introduction of experimental data.
Data areaAmount of data (unit: GB)Number of tilesCity 165.252880City 271.275254City 394.476392City 4136.6411760In this paper, the comparison between the conventional method and the method in this paper in terms of loading time and memory usage and the comparison between the method in this paper and the mainstream 3D platforms at home and abroad in terms of scheduling efficiency, loading time, and display clarity are shown, and the specific experimental analysis is as follows:(1)
The conventional method and the method in this paper are compared in terms of loading time and memory usageFrom Table2 and Figure 4, the loading time and the specific values of memory occupied, as well as the line graph, it can be seen that the scheduling loading time of the method in this paper is only about 1/5 of that of the conventional method, and the memory usage is only 2/5 of that of the conventional method. Left and right, the efficiency of scheduling and loading of oblique photography 3D models has been greatly improved
(2)
In order to compare and analyze the scheduling method in this paper and the scheduling display of mainstream 3D platforms at home and abroadTable 2
Load time/memory usage comparison.
Data areaLoad time (unit: milliseconds)Occupied memory (unit: MB)Normal methodThe method of this paperNormal methodThe method of this paperCity 1107821052885.6356.4City 21848028951308.4458.9City 32359035701393.5479.7City 44128569551807.5692.1Figure 4
Load time/occupied memory comparison chart.From Table3, we can compare and analyze the same data of mainstream 3D platform scheduling at home and abroad. It can be seen that the method in this paper has obvious advantages in terms of scheduling time, efficiency, data display clarity, and memory usage and can realize the optimization of massive inclined 3D models, fast scheduling and display of data.Table 3
Comparison of domestic and foreign mainstream three-dimensional platforms and the scheduling method in this paper.
PlatformData is displayed for the first timeTime (ms)All dataDisplay time (ms)Data schedulingEfficiencyDataClarityMemory usage (MB) when data is clearThe method of this paper1007000FasterKeep it original700A domestic platform 110035000GenerallyKeep it original1950A domestic platform 210012730Faster, scheduling stops when switching locationsKeep it original1630a foreign platform10050800SlowerClear when close1450


## 4. Conclusion

The 3D model of the city is the basis for constructing a digital city. Due to its different modeling methods and different usage environments, there is currently no unified 3D model standard for cities [14–18]. Regardless of the format, the 3D model has the characteristics of complex data structure and huge amount of data, which poses a huge challenge to data storage, transmission, and especially the visualization process. Therefore, it is necessary to design a reasonable and efficient 3D model data organization and management method to realize the rapid visualization of model data. This paper conducts research on 3D model data acquisition, preprocessing, organization, storage, management, scheduling methods, rendering, etc., and according to experiments [19–21], it is verified that the method in this paper can improve the scheduling and rendering efficiency of massive oblique photography 3D models.Based on the research and analysis of the existing oblique photography 3D model data organization and scheduling methods, based on tile, a regular grid + quadtree + hexadecimal tree is used to construct a spatial index to organize and manage tile data. On this basis, the layered and block top-level DEM is reconstructed by regular grid sampling, the top-level TDOM is obtained by orthographic projection, and the top-level 3D model of the layered block is reconstructed by using DEM+TDOM to realize fast scheduling of massive oblique photography 3D models. The advantages of this method in the rapid scheduling of massive oblique photography 3D models are verified by experimental comparison and analysis, and the application in the self-developed 3D platform has achieved good results, but there are still some problems [22–27], such as the first loading. It takes a long time to build the spatial index and the top-level 3D model when using the data, and further research and improvement are required.



---

*Source: 8217220-2022-08-30.xml*