polygon models with high quality textures should be preferred.
Another idea behind the use of preprocessed models is to save
considerable amount of rebuilding time. In this study we used
such models from Geometric and Dark Basic companies. Our
library contains nearly 1000 objects consist of vehicles,
buildings, people, animals, trees, bushes, fences etc.
1.5 Rendering Performance Issues
It is a known fact that developments in the graphics hardware
dramatically reduced the time needed to render VEs. But
parallel to this development the demand for more realism
increases the complexity of the VEs. The most well known
techniques for handling this complexity are:
e LOD Management,
e Visibility Culling,
e Object Organization.
In LOD management, main idea is to render same object with
different number of polygons considering the distance with the
virtual position of the observer. Throughout this paper the
virtual location where the user observes VE is called as Virtual
eye (V-eye). Objects that are far from V-eye rendered in a low-
polygon form. The problem of removing redundant data that are
not to be displayed is named as visibility culling. Back face
culling, frustum culling and occlusion culling achieve typical
reduction. Back face culling is simply described as not drawing
the inner faces of the closed shape objects since they are
invisible to the V-eye. The viewing volume of perspective
projection is called as frustum. In frustum culling objects that
are outside of the viewing volume are not sent to the graphics
pipeline. This method is useful when polygonal cost of the
object is high. As the name implies occlusion culling is
discarding the objects that are occluded such as objects behind a
wall. Depth buffer mechanism of 3D graphics libraries prevents
drawing occluded objects. The problem in here is to do this job
prior to rendering phase and minimize the workload of graphics
hardware. Object organization defines the hierarchical
organization of objects according to binary, quad or octal trees
or according to some other criteria such as objects in the room.
2. IMPLEMENTATION
We developed an application that can render dynamic crowded
outdoor scenes in real-time. The excessive number of objects in
the virtual environment is probably the most significant
capability of our system. Common features of this software and
the methodology that we used are explained in this part.
2.1 Terrain Modeling
Terrain modeling is one of the most popular research topics of
3D computer graphics. This issue can be divided into two sub
problems: generating geometric terrain model and painting or
texturing terrain surface.
2.1.1 Geometric Terrain Models: Various types of Digital
Elevation Models (DEM) are used to construct geo-specific
terrain models whereas pre-rendered grey-scale bitmap images
or 2D array of height values that are known as heightmap are
used to construct generic models. Our implementation supports
popular DEM formats. The outdoor scenes sometimes contain
more than a million polygons. An average hardware accelerated
graphics card cannot display that many polygons in real-time. A
7.5 minute DEM that covers 1:25K scale map contains 203401
616
International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B5. Istanbul 2004
height points which corresponds to 405000 triangles. When we
consider the frame rates that should be met it is clear that it is
necessary to reduce the number of polygons that are going to be
rendered. Many research papers have dealt with different LOD
algorithms and aggressive frustum culling. Famous methods for
terrain rendering are the LOD algorithm (Lindstrom et al,
1996) and Real-time Optimally Adapting Meshes (ROAM)
method (Duchaineau et al, 1997). These methods and
derivatives eliminate some of the triangles by combining them
with other triangles. In this study we implemented these basic
algorithms to improve performance.
We also designed a terrain editor in which user can generate
generic terrain models by using the tools provided. User can
define the width and length of the terrain model and the interval
of height points: At this point we let user to create a random
base map if he wants. The random functions used by compilers
are not appropriate to produce generic terrain models due to
discontinuities of the functions they produce. It is possible that
very high and very low two points might be side by side. A
random function should change smoothly in order to be used in
terrain model generation. Ken Perlin proposed a method known
as Perlin noise, which became very popular in many fields
including motion picture industry (Perlin, 1984). This method
has been widely used in computer graphics. To create Perlin
noise one first generates a random sequence with maximum
allowable dynamic amplitude range. This sequence is smoothed
using interpolation techniques. As a next step another random
sequence with twice the frequency and half the dynamic range
is created and interpolated. This procedure is repeated until the
desired spatial resolution is obtained. Finally all intermediate
random sequences are combined by addition. As it can be easily
seen in Figure 1, sum of noises looks like a silhouette of a
mountainous area. We used 2D Perlin noise functions to
generate generic terrain model.
2D Perlin Noise and
Sum of Noise Functions
1D Perlin Noise
TTL 4 és J
utm it! a f ol
Figure 1. Illustration of Perlin Noise
The user can modify this model with mouse or use it directly. In
the Terrain Editor module, Gaussian equation is used to edit the
terrain model. The point that the user clicks with the mouse is
considered as the centre point. The region around this point can
be raised or lowered to create hills or pits. It is possible to
change the parameters of the Gaussian function in order to
generate different shapes. Repetitive operations enable the user
to create the terrain that he wants. The user can also use a flat
terrain model as a starting template. There are two additional
functions that can be used for fine-tuning. First one is
convolution function that smoothes the model and the second
one is addition of random noise that makes the model rough.
All of the operations can be performed either on a 2D
heightmap image or in a 3D model. Terrain Editor tool is also
vel
not
2.1
me
VI
his
su
ey
W
th:
co
ca
co
de
qu
as
pr
