The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences. Vol. XXXVII. Part B5. Beijing 2008 
694 
During pre-processing, terrains are represented as 
multi-resolution meshes, which can be generated from bottom 
to top (or refmed-to-coarse, in which a full resolution model is 
created at first. Then triangles are merged recursively until a 
screen space error tolerance is exceeded), or from top to bottom, 
(or coarse-to-refined, which generates a coarsest-grained model 
at first, then refines it). The computation complexity depends on 
the vertex number in the original mesh model. So the latter is 
much simpler. 
The multi-resolution representation are arranged in one or more 
quad-trees (or its equivalent, triangle bin-trees), or represented 
as wavelets. At run time, proper levels are selected. 
Most of the following approaches are based on the management 
of triangulated irregular networks (TINs) which provide the best 
approximation for a given number of faces, but require the 
tracking of mesh adjacencies and refinement dependencies. The 
mesh is refined in real-time according different strategies. 
[Lindstrom et al. 1996] introduce a real-time smooth and 
continuous LOD reduction using a mesh defined by right 
triangles recursively subdivided according a user-specified 
image quality metric. Some hierarchies use Delaunay 
triangulations [e.g. Cohen-Or and Levanoni 1996; Cignoni et al 
1997; Rabinovich and Gotsman 1997] while others allow 
arbitrary connectivities [e.g. De Floriani et al 1997; Hugues 
Hoppe 1998; El-Sana and Varshney 1999]. In [Duchaineau et al. 
1997], the authors introduced ROMAing method as a very 
efficient algorithm based on triangle diamonds managed with 
split and merge operations performed using priority queues. The 
algorithm now is widely used in games industry, but its 
implementation is tedious according to [Blow 2000]. In 2002, 
[Levenberg] propose to reduce the CPU overhead of the 
previous binary-triangle-tree-based LOD algorithms by 
manipulating aggregate triangles instead of simple triangles. 
In a recent paper, Losasso and Hoppe [2004] apply the clipmap 
[Tanner et al. 1998] concept to geometry for large terrains 
rendering. Their GPU accelerated method is based on a set of 
nested regular grids centered about the viewer. Geometry 
continuity is guaranteed by using transition regions between 
two grid levels using the GPU vertex shader. They use a 
compression algorithm to load the full terrain model in memory. 
However, this still requires the full CPU power to compute 
vertex indices at every frame. In a more recent paper, 
Asirvatham and Hoppe [2005] enhanced the approach by 
performing nearly all computations on the GPU. Furthermore, 
even if the method is very efficient, it relies on shaders, which is 
not practicable to handheld devices and/or mobile devices. 
Ideally, view-dependent LOD algorithms adaptively refine and 
coarsen the mesh based on screen-space geometric error, the 
deviation in pixels between the mesh and the original terrain. 
Screen-space error combines the effects of (1) viewer distance, 
(2) surface orientation, and (3) surface geometry. Since surface 
orientation seldom provides significant LOD gain, many 
schemes choose to ignore it. One common refinement criterion 
[Blow 2000] stores at each vertex a radius defining an enclosing 
sphere. The pre-computed radius encodes the local surface 
approximation error, such that the neighborhood of the vertex is 
refined if and only if the viewpoint enters the sphere. In 
view-dependent algorithms, a terrain can be thought of as a 
displacement map over trivial planner geometry. Some recent 
papers have proposed hardware schemes for adaptive 
tessellation of displacement maps [Gumhold and Hiittner 1999; 
Doggett and Hirche 2000; Moule and McCool 2002]. So far 
these schemes have only been simulated on relatively simple 
grids, and they assume that the entire grid is memory-resident. 
2.2 Out-of-core technique 
With this aim in view, some other approaches propose to 
perform either out-of-core rendering (local solution) or 
streaming (networked solution) of the models. 
[Pajarola 1998] extends the restricted quad-tree triangulation of 
Lindstrom [1996] with another vertex selection algorithm and 
amore intuitive triangle strip construction method. This is 
combined with dynamic scene management and progressive 
meshing to perform out-of-core rendering. More recently 
[Cignoni et al. 2003b; Cignoni et al. 2003a] described a 
technique for out-of-core management and rendering of large 
textured terrains named batched dynamic adaptive meshes 
(BDAM). BDAM is based on a pair of bin-trees of small TINs 
that are computed and optimized off-line. The batched 
host-to-graphics communication model guarantees overall 
geometric continuity, exploits programmable GPU’s, a 
compressed out of core representation and a speculative 
pre-fetching for hiding disk latency. These solutions are still 
impracticable for our objectives since they rely on low latencies 
between mass storage and main memory. Furthermore, these 
solutions also present high CPU costs. 
Other methods rely on the web. [Reddy et al. 1999] described 
TerraVision II that is a geo-referenced VRML97 terrains 
viewer. A quad-tree hierarchy of the VRML97 LOD mode 
which induces a lot of data redundancy and no care is taken to 
ensure continuity between different grid levels. A more 
advanced solution proposed by [Aubault 2003] relies on a 
wavelet encoding to perform terrain streaming and 
multi-resolution rendering. Still, this very efficient solution 
requires to fetch the entire model into server’s memory and to 
perform costly computations on it. 
3. TERRAIN REPRESENTATION 
A terrain (elevations) can be defined in several ways. First of all 
it can be defined as an arbitrary mesh also known as 
Triangulated Irregular Networks (TINs). This method does not 
put any restriction on the terrain, and has been used in terrain 
rendering. TINs provide the best approximation for a given 
number of terrain faces. However the algorithms are very 
complex, consume more memory, and are not very efficient for 
view-dependent simplification. So another method is proposed 
to define the terrain as a height map, which is a grid structure 
that is equally spaced in the x and y directions. The z value is 
used as the height information. The grids data are simple and 
disciplinary, and consume less memory. But grids DEM are not 
very flexible to describe terrains with uniform criterion. If the 
grid space of height field is too wide, it tends to lost detail of 
terrains especially at fluctuant region. If the grid space is too 
narrow, there will be a lot of redundancy. In order to solve the 
problem, this paper proposes a dynamic adaptive 
multi-resolution modelling to represent terrain based on 
quad-tree. It has chosen terrain representation as height map as 
it allows fast collision detection between moving objects 
(including camera) and the terrain. It also supports use of 
hierarchical data structures for fast and easy view frustum 
culling. 
Considering visualization of very large real world digital terrain