The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences. Vol. XXXVII. Part B5. Beijing 2008 
695 
model data, which will not fit into main memory entirely, 
especially for terrain walking through application, it must to 
organize the digital height map data in tiles. The tiles 
management algorithm aims at maintaining the largest square 
area around the view point; those squares of tiles assure the user 
can always look around at any point of view. The size of the tile 
is set according to the available main memory which makes it 
adaptive to the mobile device that is used for visualization. On 
the other hand, in order to subdivide those tiles based on 
quad-tree properly, this paper uses a simple strategy. For each 
level /, with grid spacing S ¡= 2 1 in world space, it is let the 
desired active region be the square of size VlS l X nS l . Each tile 
is represented by hierarchical quad-tree data structure. The 
top-level node in this tree structure represents the area of the 
entire tile, its children each represent one fourth of the terrain 
area, their children in turn each cover one sixteenth of the area, 
etc, and then each tile will be encode and store into a array 
(see figure 1). 
To subdivide the tiles, a criterion or a set of criteria is needed. 
According to the criterion, terrains are represented in various 
resolution meshes. In this paper, the criterion is difference 
height difference of terrains, and the algorithm sets a threshold 
of height to compare with the maximum height difference of 
subdividing grids. 
Algorithm 1 Adaptive tiling based on quad-tree 
if not subdividing tile then 
MAX= maximum height difference of tile 
if MAX > THRESHOLD then 
subdivide the tile into square grids 
max = maximum height difference of grid 
if max > THRESHOLD then 
continue to subdivide the grid 
else 
stop subdividing, encode the grids which been 
subdivided and record them into database 
end if 
Figurel. Hierarchy of tile based on quad-tree 
One advantage of having this particular terrain block layout is 
that one such block can be optimized for rendering, using one 
draw-primitive call for the entire block and, even better, using 
grid indexing to get rid of multiple transformations of vertices. 
Pyramid representation is used to define each block of size. A 
pyramid is a multi-resolution hierarchy for a data set. Same 
approach when dealing with image textures is known as 
mipmapping. It helps in dynamic multi-resolution level of detail 
mesh simplification of height map data. 
Then the tiles will be subdivided according to terrains. 
Intuitively, those fluctuant areas hold more details and need 
refine mesh to represent and even areas only need coarse mesh 
to represent (see Figure 2). 
Even areas need 
not to be 
subdivided any 
more 
4. ADAPTIVE LOADING TILES AND RENDERING 
For mobile devices have less memory to run programs, it is 
impossible to load triangles entirely of terrains into memory 
(the client’s memory). With our solution the database is made of 
a set of tiles, each one containing the regular terrain elevations 
of a tile. A metadata file which records a description of the tiles 
grid (tiles size, number of tiles, positioning etc.) is first fetched 
(or loaded) and its information are then used to manage the 
adaptive tiling. 
4.1 Tile data structure 
In theory, tiles can be divided in any size and any forms, but for 
the sake of simplicity this paper only consider the specific case 
of tile of square form, and the specific case of tile of size 
W = h = (2” + i) and its data store in an array whose 
resolution ( W X h ) stores elevation value of the sampled 
terrain area. The memory representation of a tile is a vertex 
buffer that embeds the 3D coordinates together with their 
properties just as texture coordinates normal. 
Structure of triangle 
typedef struct 
{ 
m_TriangleVex[3] ; // vertex 3D coordinates 
m_TriTextCoord[3] ; // texture coordinates 
m_TriangleNormal[3] ; // vertex normals 
}STRUCT TRIANGLE 
Tile data structure 
typedef vector<STRUCT_TRIANGLE> VEC TRIANGLE ; 
typedef map<GRID_CODE, VEC TRIANGLE ,lpGridCode> 
MAP DEMTRIS MESH ; 
The multi-resolution is generated by creating a set of coarse to 
fine tiles. A tile is defined by connecting only the vertices with 
( Z X j ) coordinates (within the W X h array). By the grid 
index, we can find the tiles which want to be load in client 
memory soon. 
Figure 2. Adaptive subdivision of tiles based on quad-tree 
4.2 Adaptive rendering tiles 
View-frustum culling techniques are used to control substantial 
amount of polygons in the rendering pipeline. Only those tiles