CMRT09: Object Extraction for 3D City Models, Road Databases and Traffic Monitoring - Concepts, Algorithms, and Evaluation
110
usually very huge and mobile platforms have limited
computation resource (CPU power, memory, storage, and
wireless network speed). There are several techniques have
been proposed to visualize, navigate, interact, and query
database systems in virtual environment.
2.1 3D Rendering techniques
Early studies on 3D maps often attempted to use mobile devices
with direct model view software. In 3D computer graphics,
numerous rendering techniques are available to cope with
complex virtual environment, including discrete and continuous
multi-resolution geometry and texture representations, view-
frustum culling, occlusion culling, imposter techniques, and
scene-graph optimizations (Akine-Moller and Haines 2002).
Visualizations of virtual 3D city models and large terrain
require an efficient management of large-scale texture data,
such as images of building facades, aerial photography pictures
of the terrain, and level-of-details (LOD) management for
hierarchy of mesh refinement operations for large
heterogeneous 3D object collections. Although these rendering
techniques enable real-time rendering of complex 3D scene,
they still cannot be rendered on mobile devices due to limited
computational resources and power.
In order to efficient mobile 3D rendering, numerous techniques
have been approached. Royan et al (2003) describe client-server
architecture for mobile 3D virtual city visualizations based on a
progressive and hierarchical representation for 3D geo-virtual
environments. In his approach, the server firstly pre-computes
multi-resolution representations of terrain models and building
models, and then sends these data about visible areas to the
mobile clients progressively. However, this method need clients
implement rendering task dynamically and it is difficult to
mobile devices due to the broad variety of hardware and
software solutions for mobile 3D graphics (e.g. OpenGLES,
Mobile 3D Graphics API for J2ME) (J. Dollncr, B. Hagodorn
and S. Schmidt 2006).
Another principle solution consists in server-side 3D rendering
and the progressive, compressed transmission of image
sequences. Cheng et al. (2004) investigate a client-server
approach for visualizing complex 3D models on thin clients
applying real-time MPEG-4 streaming to compress, transmit,
and visualize rendered image sequences. They identify the
MPEG-4 encoding speed as bottleneck of client-server 3D
rendering, and devise a fast motion estimation process for the
MPEG-4 encoding.
2.2 Data Model
The main purpose of navigation application is to interpret the
process such as “whereby people determine where they are,
where everything else is, and how to get to particular objection
or places” (Jul and Furnas 1997). The task can be distinguished
into three kinds, naive search, targeted search, and exploration
(Darken and Sibert 1996). To do this, users need builds up a
mental model of the virtual environment by forming linear
maps and combining them to spatial maps (Ingram and Benford
1995), and corporate task-based constraints on the navigation
parameters (e.g. viewer position and orientation).
At the present time, a lot of work has been done which mainly
aim at how to enhance the visualization efficiency and many
sophisticated data structures have been designed. For example,
a number of LOD algorithms have been developed to create a
hierarchy of mesh refinement operations to adapt the surface
and decimate polygons thus reducing complexity of
computation without affecting the quality of scenes. (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.
But applications of 3D navigation suffer from a lack of data
standards and flexible distribution techniques. The virtual 3D
models frequently are implemented as graphic models without
explicitly modeling semantic and topological relations.
Therefore, the data can only be used for visualization purpose
but not as a basis for higher-level functionality such as
simulations, analysis tasks, or spatial data mining.
3. OFFLINE DATA PREPARATIONS
Before geo resources can be efficiently accessed at runtime, the
datasets including digital elevation models (DEM), aerial
photographs, entity models and their facade images need to be
prepared and organized in an offline process. The main purpose
of this process is to define the data structures, compress the
spatial data, reduce the data redundancy and enhance the
rendering efficiency.
In recent years, there have been many techniques purposed to
partition and organize data with multiple resolution into
hierarchical structure. The most common ones are Quad-tree,
BSP (Binary Space Partitioning) tree and Octree. In our
approach, we designed a pyramid mode for multi-resolution
virtual environment and partition the whole world into different
levels and block in terms of latitude and longitude. As each
level of pyramid data has its own specific storage unit (Here
these units are called as tiles) and access needs, for each level /,
with grid spacing S ,= Sx2~' in world space, it is let the
desired active region be the square of size nS, x nS, ■ Here the
parameter of S represents the total space of the area.
When multi-resolution pyramid is generating, each level of
pyramid is represented by hierarchical quad-tree data structure
and one tile corresponds to a certain range of region, where the
width and height of the tiles are measured in decimal degrees.
Child nodes are generated from a parent node by equally
splitting the parent node tile into 4 quadrants. Each child nodes
tile has half the width and height of the parent node tile. 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
(see figure 1). The root node of the tree is denoted as levels of 0,
and is centered on the latitude </> = 0° and longitude 2 = 0°, so
