PC based Virtual Reality engine for terrain modelling

Peter Dornbach

E-mail: jet@inf.bme.hu
Department of Process Control
Technical University of Budapest


This paper presents Eagles, a new PC-based experimental environment for Virtual Reality, which is especially suitable for tasks involving terrain modelling. The current environment is configured as a helicopter simulator. The paper introduces the methods to put this complex task to a PC without any special graphical hardware. The scenes of the animation are more realistic than in many previous environments while the frame rate of the system is over 10 frames per second on a high-end PC in 640x480 screen resolution.

Figure 1. Screen shots from the helicopter simulator


Virtual Reality, Aircraft Simulation, Computer Graphics

You can download the helicopter simulator demo from here. (1.8 Mbyte ZIP file, runs under DOS.)


  1. Introduction
  2. The architecture
  3. Resource handling
  4. The rendering modules
    1. Colour management
    2. Rendering the sky
    3. Rendering the terrain
      1. Structure of the terrain data
      2. The method of rendering
    4. The rendering of objects
  5. Comparison with other simulators
    1. AH-64D Longbow
    2. Hind
    3. Comanche 3
    4. Comparing requirements
  6. Bibliography
  7. Credits

1. Introduction

In the last decade, a new generation of aircraft simulators evolved due to the available cheap computing power on the market. There are basically two kinds of simulation engines:

Military and civilian professional aircraft simulators are used to train aircraft personnel. This is usually cheaper and less dangerous than to train people in a real aircraft. Beyond that, the crew can train situations that they cannot or can rarely learn in real aircraft, because the conditions are extreme or dangerous. These simulation engines usually have a lot of expensive graphics hardware to produce awesome graphics.

The other kind of simulators are used by the computer games industry. Because of obvious business reasons, the game has to be widely available, therefore it has to run on cheap personal computers. Until a short time age, this usually lead to limited success mainly because of hardware limitations.

The newest hardware of today bring a lot of computing power with a reasonable price, which makes it possible to create professional quality simulators on personal computers. This computing capacity is less than those available in today's professional simulation engines or 3D graphic workstations, but the personal computers also have several advantages:

These simulators usually use a world of polygons and techniques such as Gouraud-shading and texture mapping at the rendering process. Some simulators also introduce new ideas. However, there are a lot of differences amongst the products in the emphasis of the different techniques, and the result is often a program, which performs good in one area, but poor in the other one.

Eagles is an experimental application for the techniques of a such system, that tries to use the best method in each part of the rendering process. We will have a look at the features of the software in this document. The first section introduces the choice of programming environment and the structure of the program. The following sections have a look at the different components.

2. The architecture

With a PC, we do not usually have special hardware to support real-time graphical applications, so we have to produce extremely fast code and especially efficient algorithms for scene generation. Because of that, some low-level parts of the rendering engine are written in assembly language, while most of the code is in C++, and is fully object-oriented. The engine runs directly under DOS, but it works fine with some restrictions under other operating systems that allow running DOS programs such as Windows 95 and NT.

Eagles consists of several modules:

Although the program is performing some kind of world simulation, the simulator does not introduce many new methods or realistic simulation, so this paper does not contain information about it.

Now let us have a look at the components!

3. Resource handling

The resource manager's task is to provide the required resources for the other parts of the program. A resource is a single file, which is translated into a C++ object at loading time. Resources are packed into larger files (.SIM files) that act as a library for resources. Current known resource formats include some well known formats such as PCX (for textures), WAV (for sound samples) and MOD (for background music), as well as some other formats invented especially for this environment. These formats are: Details of these formats will be discussed later.

The resource loading strategy is quite unusual. The traditional approach for these systems splits the available memory into parts for each kind of resource. This method is safe, because you will always have the memory for resources, but it is quite inefficient. The memory manager of Eagles works very much like a virtual memory manager of a modern operating system, except that the virtual memory area on the disk is read-only, so the manager does not need to write data back to the hard disk. The resources are stored in several files. Each time the program wants a resource, the resource manager checks whether it is in the memory or not, and loads it if necessary, thus the largest part of the memory memory serves as a "cache" for disk resources, resulting in a very efficient memory usage. The final programs runs fine on a DOS-based system with as low as 4 megabytes of main memory.

This new approach is more flexible, but it is not so safe with critical resources. We call a resource critical when the system is unable to continue the simulation without it. For example, if the system is unable to load the physical parameters of the helicopter into the memory, the simulation engine will be unable to calculate a lot of important data, thus the whole system will fail. In the case of Eagles, it is theoretically possible, that at some point the system will not have the required memory for loading a resource, thus the simulation has to stop.

To reduce this effect, there are two kind of access methods for the resources. At the first one, if the resource manager is unable to load a resource, it will stop the simulation. So if a procedure wants to load a resource with this method, it does not have to pay attention of checking the result, because this method will always return a correct value. This method is applied to critical data such as object geometry data or colour tables.

The other method may fail, and return NULL instead of a valid pointer. But this causes little difficulties since it is applied only to non-critical data such as object textures or sound data. The both methods ensure that the less valuable resources do not obstruct the loading of more valuable ones.

Because the resources are loaded into memory on demand, the manager is efficient only if the storage medium provides quick access times and high data transfer rate. Most modern hard disks satisfy these criteria, because the average seek time is low, usually around 10ms ( [HDD] ). Therefore, the loading of resources is very smooth. However, even the newest 10x or 12x speed CD-ROM drives may be too slow because the average seek time is well beyond 100ms. ( [CDROM] )

The resource manager acts like a DBMS, but it is much simpler as an actual DBMS, because the database is read-only, so it does not have to worry about transactions and structures that allow efficient update of the database.

4. The rendering modules

The scene is built up basically from three different components: the sky, the terrain and the objects in the world. To obtain the highest possible efficiency of the rendering algorithm, three different kind of rendering strategies are used to render the three components. In this section, we will have a look at these strategies.

To obtain the highest possible speed in the rendering process, we had to introduce some constraints. These constraints do not allow the viewer to view the world of any possible angle. To be more concrete, the pitch and the yaw of the viewing angle is limited, because that simplifies two rendering methods of the three significantly.

Figure 2. Pitch and yaw angles are limited

4.1 Colour management

The program works in indexed-colour video mode with 256 colours, because that mode allows nice pictures while providing fast image generation compared to hi-colour and true-colour video modes. The 256-colour palette is not totally fixed, it is divided up into three parts. Those parts may be changed if the components of the world change, i.e. we use another terrain or another sky texture. The first 128 colours belong to the terrain, the next 96 to the objects and the last 32 to the sky. Actually, the 96 colours maintained for the objects are fixed, but the other two parts are not.

The basic unit of the simulation is a mission. A mission file determines which terrain and which sky to use. The mission file stores the palette to be used with the specific mission. This allows the programmer, for example to use the same sky bitmap with different palettes in different missions. In one mission, the regular palette may be used, while in a night mission he/she may use a darkened version of the palette.

Two tables are also required to produce some effects. Because the program uses an indexed colour mode, the calculation of the Gouraud-shading used at the terrain rendering is not straightforward. The shading table is used to help shading calculations. The basic idea is the following: let us suppose, that we have two colours, both represented by a one-byte indexes to the palette entry. (Actually, the index may be only in the range of 0..127, because we use only 128 colours for the terrain). We would like to compute several colours, that fall between our two selected ones, and are also in the palette. So, we calculate the RGB representations of the two colours, and we linearly interpolate the RGB values of the colours between them. Then, we choose the nearest colour from the palette for each RGB value between the two colours. But if we fix the number of intermediate colours, then the results of a such calculation may be pre-computed for all the possible cases. Eagles uses 8 intermediate colours, and so the size of the table is 128*128*8 bytes = 128 Kbytes.

The second table is called effect table, and is used to produce atmospheric effects such as fog, smoke, and fade of the furthest parts of the terrain. This table is for all the 256 colours, not just for the terrain colours. The table consists of several sub-tables. One sub-table is responsible for one effect, e.g. darkening the colours by 50%. It is an array of 256 bytes, and it contains the nearest colours for the darkened original colours. With a sub-table, darkening a part of the screen can be performed quite quickly, this pseudo-code explains it:

for each pixel(x,y) to be darkened {
  byte oldvalue= screen_array [y] [x];
  byte newvalue= sub_table [oldvalue];
  screen_array [y] [x]= newvalue;

4.2 Rendering the sky

The simulator uses the painter's algorithm at the rendering process. First, the sky is rendered. This section introduces the rendering method used for sky drawing and proves its efficiency.

Because the pitch and yaw values of the viewpoint are limited, the rendering engine can use a very simple model for the sky. Instead of dealing with a lot of geometrical objects, the sky is simply a texture map. The renderer copies the appropriate part of the texture onto the screen, which is described by a rectangle on the texture map. If the viewer turns to the left, the renderer will shift the viewing rectangle to the left on the texture map. If the viewer is increasing its pitch, the rectangle goes down. If the viewer is rotating to the left, the viewing rectangle will rotate to the right.

This process allows only constant sky, but it is not a bad approximation of the reality, if the viewer is moving only slowly within the world and is at low altitudes.

Figure 3. The screen space and the texture space

The sky renderer renders the sky bitmap onto the screen in columns, from left to right, and uses some tricks to improve the speed. First, it takes one screen column, and for each screen pixel in the column calculates the corresponding texel on the texture bitmap. Then, it calculates the difference of the texture coordinates between screen pixels below each other. For the next columns, it will calculate only the texture coordinate of the top pixel, then the next coordinates will be approximated by adding the values of the first column. In fact, instead of texture coordinates, the algorithm may calculate directly with memory pointers, which will allow even quicker image generation. The above optimisations make it possible to draw 4 pixels of the sky with only 11 assembly instructions.

Because we add the difference values of the first column instead of calculating the correct ones, the resulting image will not be as accurate as it could be with regular texture mapping algorithms. However, the resulting image artifacts will not be significant, if we choose the texture map properly, and we avoid using sharp boundaries in the map, as it can be seen on Figure 4.

(a) A bitmap with sharp boundaries
Have a look at the line of horizon. The line is totally straight on the texture map, but not on the screen because of the inaccurate drawing method. This effect is also observable on other parts of the screen.

(b) The actual bitmap
The effect is much less visible if the texture does not contain sharp boundaries.

Figure 4. The inaccuracy in sky rendering

4.3 Rendering the terrain

The main ideas about the terrain renderer came when we had a closer look on [MARS]. In this small program, the terrain rendering is extremely quick. The algorithm is quite similar to that one that this paper will introduce below, but it has several constraints: In the Colour Management section, we already introduced a table which makes the rendering of a multi-coloured terrain easier, but to get a usable simulation engine, we have to get rid of this strict constraint of the viewing direction. The paper shows first the data structure used to store the terrain data to deal with the new conditions, then it introduces the rendering process itself.

4.3.1 Structure of the terrain data

The terrain itself is stored as a height-field array. Imagine, that we cut a rectangular area from a real terrain, then we divide it up into x*y small rectangles parallel to the edges, so that we will get x*y pieces of elementary terrain patches. Then we store the height and colour for each patch in a 2-dimensional array. This is already much more efficient than storing a lot of polygons, because we need to store only two numbers per terrain patch instead of storing the polygon data: coordinates of vertices, vertex indices, etc.

The process can easily result in a huge amount of data, that consumes a lot of memory and processing time. For example, if we want to store a 10 km * 10 km square from the terrain with 10 m resolution along both axes, that results in 1,000,000 surface patches, which will consume 2 Mb-16 Mb of memory (depending on how we store height and colour).

To reduce memory usage, the surface data is divided up into 128*128 patch sized areas, and each area is stored and loaded into memory independently. These areas are called segments. The simulator stores the height of the surface patch in one byte, and the colour in another byte (chosen from the colour palette introduced by the Colour Management section). So the total storage requirement of a segment will be 128*128*2 bytes = 32 Kbytes. These segments are stored directly in .SEG resources files.

The terrain renderer also takes use of the fact that we do not need to show the further parts of the terrain in such detail as the closest ones. It uses the same idea as mipmapping. The terrain is stored in different resolutions, and the renderer uses data from lower resolution segments while it draws the further parts of the terrain to the screen. In the current application, the base terrain consists of 1024*1024 terrain patches at the highest resolution. The terrain resolution is approximately 10 meters per terrain patches, so the whole terrain covers a 10 km * 10 km area. Then the same terrain is stored with 512*512, 256*256 and 128*128 patches.

Figure 5. The structure of the segments
The segments on the left, middle and right show the same area in decreasing detail level.

This approach leads us to several advantages. First, the rendering engine needs to keep less data in the memory and reload the data less often from hard disk. The other, and most important advantage is, that we have to render much less surface patches while maintaining almost the same visual quality. A quick calculation to prove this: in the helicopter simulator the base terrain visibility is approximately 2.5 km, that is equal to 250 patches. So, we have (2*250)^2= 250000 patches within the visibility range. Let us assume that the viewer sees one quarter of the patches at the same time, because the others are behind the viewer or out of the screen. In this case, the renderer has to render 62500 patches to calculate one image. With the new method, the visibility in each map is approximately 32 patches. That means, that we have to worry about less than (2*32)^2=4096 patches per level, that is 16000 patches total. If we see only the quarter of them, as in the previous case, the renderer needs to render only 4000 patches, which is about 15 times less, than with the conventional method.

The new rendering mechanism also allows us to use different detail levels of the terrain and different visibility range depending on the viewpoint's altitude.

4.3.2 The method of rendering

So, the number of polygons in the visibility range is in the magnitude of 15,000. That is still quite a lot to sort and draw with the conventional polygon rendering methods, especially if we would like to use some kind of shading or texture mapping, not just plain polygons. Because of that, the terrain renderer works in a special way.

In the previous section, we saw that the terrain data is stored in some detail levels. Now, we are going to have a look at the rendering process itself within one detail level.

Fortunately, the terrain data is arranged into a matrix, thus we do not have to worry about polygon depth sorting before using the painter's algorithm. So, we start the rendering with the furthest patches, and then closing in.

First, the algorithm calculates the locations on the screen (if it is on the screen at all) for the furthest visible terrain patches, round the viewer. The process in marked with dark blue arrows on Figure 6. Then, the algorithm calculates the parameters of the lines connecting the points on the screen. Then, it does it again for nearer surface patches. This is marked with light blue arrows on the figure. Then, the algorithm connects the resulting dark blue and light blue lines on the screen in every column of pixels (marked by the red arrows).

Figure 6. The process of terrain rendering

The above process is faster than rendering a lot of polygons. However, it has several disadvantages. The main disadvantage is, that it produces acceptable image quality only when the viewer looks nearly horizontally (both pitch and yaw values are near zero). But this is not a serious disadvantage for some kind of applications, like the helicopter simulator.

In the real application, this rendering method is extended to all the detail levels of the terrain.

4.4 The rendering of objects

The object renderer does not come up with many new ideas. The main source for the polygon rendering and visibility calculations is [PCGPE].

The objects are stored in OBF files on the disk, and are translated to C++ classes during the loading process. The structures used in the file format and in the C++ classes map directly onto each other. For each object, vectors store the locations of all the vertices in the object, and several normal vectors also required for rendering. These vertices can be used to build polygons. Different types of polygons include:

Solid filled polygons -
The engine supports both constant-colour and shaded polygons.
Atmospheric effect polygons -
When drawing these polygons, the renderer usually applies a darkening or lightening effect for all the pixels covered by the polygon. The effect is performed by the the effect table explained by the Colours section. This is ideal for modelling smoke, glass material, etc.
Texture mapped polygons -
This kind has several variants. It may be constant colour or shaded. Both of these can be transparent, in that case the totally black parts of the texture will be treated as transparent.
Gouraud shaded polygons -
The current engine support only plain shading, but this could be extended to texture mapped shaded polygons.

Figure 7. The different polygons in the helicopter simulator

These polygons can be used to build the objects. The objects also contain some information about the spatial location of different parts to make the visibility calculations faster. The method is very similar to BSP-trees, but instead of putting each polygon into the tree, the polygons are grouped into convex groups, and only the groups are stored in the leafs of the tree.

The visibility calculation between the objects themselves is performed with the painter's algorithm. Before rendering the whole scene, all the objects in the world are sorted according to their distance, and they are drawn from further to closer ones, synchronously with the terrain.

The objects are also allowed to contain other objects, and scale or rotate those objects. A such connection point can have an activation function, i.e. a function in the source, which will be called by the object renderer subsystem every time the child object within the parent object is drawn. This activation function may modify certain parameters of the connection, it may rotate or scale the child object, or determine what is going to be the child object. This allows us to create many dynamic simulation effects, e.g. rotating rotor, dynamic weapon pylons etc.

The object subsystem supports also detail levels. Each object can have several detail levels. The current detail level being used for the object depends on the viewing distance. The designer can determine for each part of the object, from what distance should it be visible. This can be useful to decrease the complexity of objects if they are at a great distance from the viewer.

5. Comparison with other simulators

This is a comparison with the techniques used in some currently available PC-based commercial helicopter simulator games. The description of these techniques below is based only on the screen shots and descriptions available about these simulators, so they may be quite unaccurate.

Because these ones are commercial products, they are usually produced with a lot more effort than Eagles. Therefore, they seem to be more professional than the simulator presented in this paper. However, Eagles provides good graphics and simulation speed, and in some aspects it may be better than the commercial opponents.

5.1 AH-64D Longbow

The first simulator is AH-64D Longbow ([LONGBOW]) from Jane's Combat Simulations, a part of Electronic Arts. The game was released in June, 1996, and comes on a single CD-ROM. According to the company's claims, it is made with more than 20 man-years of effort and covers more than 20,000 square kilometres of landscape.

The sky model is more sophisticated that the one in Eagles, and gives a more realistic view.

Unlike in Eagles, the terrain is modeled with texture mapped polygons. There seems to be a trick in the texture mapping to reduce the memory requirement of textures, because the whole texture map seems to be built up from patches of one colour. This could be achieved via the vector quantisation method described by [VQTEXTURE]. The terrain renderer gives an overall good impression, but the geometric complexity of the landscape is obviously less than in the simulator presented in this paper.

The 3D graphical model of the helicopters is very detailed, they appear almost photo-realistic on the screen. This is mainly because the aircrafts have more complex geometric models than in Eagles.

Figure 8a. Screen shots from AH-64D Longbow ( [LONGBOW] )
These screen shots are available at the official Longbow homepage.

5.2 Hind

Hind was marketed in October 1996 by Interactive Magic on one CD-ROM. Compared to the other products, the game features quite extensive modeling of what is happening in the real world. Individual soldiers are modeled with different weapons.

Surprisingly, the simulator tries to achieve good visional quality by increasing the geometric complexity of the world. It models the aircraft and the world with more polygons and less texture maps, as we can find in the usual approach. The helicopters and other objects within the world are quite impressive.

Hind uses the same technique for terrain modeling. The method was good for the objects in the world, but it is not very effective with the terrain. While Longbow used extensive texture-mapping to hide the simple geometric model of the landscape, this simulator uses almost plain polygons in many cases, which makes the terrain to look quite artificial.

Figure 8b. Screen shots from Hind ( [HIND] )
The first two images are available at the official Hind homepage.
The third image is from the review of GamesDomain.

5.3 Comanche 3

Comanche 3 ( [COMANCHE3] )is the long-awaited sequel of Comanche by NovaLogic. The game is currently still under development, and the final version is to be released in March 1997. At the moment, there is no information available about the game itself.

The screen shots seem to be quite impressive. According to the information from the company, the simulation engine uses VoxelSpace 2 technology for terrain rendering. This is the advanced version of VoxelSpace, which is originated from Comanche, and is quite similar to the terrain renderer of Eagles.

The polygon engine produces is also very high quality. It seems, that it uses some anti-aliasing technique as well, so together with the terrain engine they produce incredibly realistic images.

Figure 8c. Official screen shots from Comanche 3 ( [COMANCHE3] )
The screen shots are available at the official Comanche 3 page

5.4 Comparing requirements

To provide a full comparison, this section contains the recommended requirements for the simulators presented in this section. The source of the data for Hind and Longbow is [GD], the source of Comanche 3 data is [COMANCHE3], and the Eagles data is based on the author's experiments.

NameTarget OSCPUMemoryHD SpaceCD-ROM drive
AH-64D LongbowDOSPentium-133 16 Mbyte97 Mbyte4x speed
HindDOS or Win95Pentium-75 8 Mbyte15 Mbyte2x speed
Comanche 3DOS or Win95* ***
EaglesDOSPentium-100 4 Mbyte****

Table 1. The recommended hardware for the simulators
* : Data not available
** : Data not available or not meaningful

6. Bibliography

The following list contains textual documents, interactive help systems and some executable programs. These information sources were used to produce the simulation engine and the article:

Szirmay-Kalos L. (Editor) : Theory of Three-Dimensional Computer Graphics, Akademiai kiado, 1995
Specifications for different CD-ROM products:
Optics Storage Maverick 8622
Aztech 10x Speed CD-ROM drives
Comanche 3 - by NovaLogic
GamesDomain, world wide web site
Specifications for different hard disk products:
Quantum Fireball ST Online Overview
Seagate Barracuda Family Specifications
Western Digital Corporation - Hard Drive Products
Hind - Games Domain Review
Interactive Magic's Hind
AH-64D Longbow - Games Domain Review
Jane's Combat Simulations - Ah-64D Longbow
Martian Terrain Renderer by Tim Clarke
PC Games Programmers Encyclopaedia, Version 1.0 by misc. authors
Tiny Module Player, Version 2.11 by Carlos Hasan
Rendering from Compressed Textures, by Andrew C. Beers, Maneesh Agrawala, and Navin Chaddha, Proc. SIGGRAPH '96
Watcom C/C++ Programmer's FAQ, Version 2.1 by Paul Hsieh

7. Credits

The author would like to express his thanks to the following people and organizations:

All brands and names appearing in this text are registered trademarks of the respective companies.

Last modified on 6-3-1997