This is a old page written in 1998 as an introductory text to familiarize people new to the issues with virtual terrain.
This page is intended to make sense to a person with no more than a little math skill, computer familiarity, and interest in the subject of 3D graphics. If there is any point at which it's not clear, please let me know so that i can add some detail or explain it better.
What's the first thing to do when creating a virtual world of a real place? Think about how large an area it is. The size of the area will affect many things such as the amount of detail you can expect to have. The island of Hawai‘i is about 130 by 150 kilometers - that's a very large area.
If you drew a rectangle of that size around the island, about half of it would be water. Assuming that the water area is flat can be a helpful simplification, unless we want to model the underwater parts of the island as well.
Next, think about where to get files, maps and photos ("terrain data") to describe the world. For Hawai‘i, we're lucky that its part of the USA, because the U.S. Geological Survey (USGS) provides a large amount of data for cheap or free. There are several kinds of data available, including:
- elevation data (height above sea level)
- vector data (e.g.. roads and rivers)
- land classification (e.g.. forest, agriculture, city, etc.)
- aerial photos (but not for Hawai‘i)
Elevation comes in the form of a DEM file (Digital Elevation Map). This is a fairly simple format, and there is code available for reading it. DEM files use one of two coordinate systems: Latitude-longitude, or UTM. The best, high-resolution files use UTM, so it's useful to become familiar with it.
The data arrives on a CDROM. It takes around 80 separate DEM files to cover the island, in either 30m or 10m resolution. You can get an idea of what the data looks like by using a program like Global Mapper. In fact, there are a lot of programs that can read terrain data, but after a great deal of research and experimentation i found that none of them can read all the available data and let you fly over the island, so some new software must be developed.
I wrote a program called VTBuilder to read multiple DEM files and merge them together. It writes a very simple format that i call BT (for Binary Terrain). So, now we have a single large, compact file representing the elevation of the entire island.
How can we render it? First, we have to decide what we're going to run it on. Traditionally, SGI machines were used for large terrain projects of this nature, but they are still much too expensive and rare, which limits the number of people i can share the island with. So, i chose to target normal PCs running Windows NT with OpenGL-based graphics cards.
The VTP program Enviro reads the elevation data and uses OpenGL to render it. However, even using the 30m data, we're talking about 43 million triangles. (That's a elevation grid of around 4300 by 5000 points, which is 21.5 million squares, then each square gets drawn as two triangles since that's what computers know how to draw, which results in 43 million triangles.) Even though only a fraction of the island may be visible at any time, this is just too much to render smoothly on even the most expensive graphics cards. Without sufficient framerate, it would look like a slow slideshow rather than a virtual world.
Fortunately, most of the triangles in the distance are too small to see, so we don't have to draw them. This can make rendering much faster. There are numerous approaches, generally known as LOD (level-of-detail) algorithms, for rendering reduced detail in the distance.
The VTP software implements three of the popular algorithms for doing LOD on terrain elevation. The process of removing the polygons that don't need to be drawn is known as culling. The algorithm can cull efficiently at real-time speed, and the amount of detail can be traded off against speed as needed.
Once we have a way to render the elevation grid, we have a plain white lump of land in the shape of the island How do we color the ground? Through texture-mapping, which simply means applying a picture of the island to the ground. Where does the picture come from? The USGS has no hawaiian imagery, so i surveyed what other sources of aerial and satellite imagery were available. The area is too large to cover with aerial photographs, so that leaves satellites. Finding high-resolution color satellite imagery proved to be difficult and expensive, but finally i managed to acquire 10m data for the entire island. The color quality still isn't great, but it's probably the best the industry can produce until newer, higher-resolution satellites go into orbit.
A 10m image covering the island is around 560 MB, which is far too much texture data for graphics cards to handle, so i surveyed the field of support for large texture maps. There are now affordable graphics cards than can handle 32 MB or 64 MB of texture RAM, which allows for a 4096*4096 ground texture, or 2048*2048 with enough left over for trees, roads, etc.
Roads are useful for several reasons. For instance, say you're planning a vacation, and want to see what's its like to drive to the beach before you depart, or want to see what the view will look like driving down the mountain. Fortunately, road data, composed of 2D vectors is also easily acquired for a small fee from the USGS. It also arrives as 80 files on CDROM, in the DLG-O format, which is easy to read.
I wrote code to read the DLG-O files and convert the 2D line segments into 3D strips of triangles, which are then "draped" onto the elevation map. This approach isn't perfect for several reasons, but it's suitable for some uses. The DLG file doesn't tell you how many lanes each road has, nor whether it's paved or not, but it does include 4WD roads and a fair number of trails.
Rivers are also available in the same format, and they could be similarly turned into draped strips, but i haven't done that yet because it probably won't look very good to have rivers elevated off the ground.
I haven't yet found data for where the fences are, but they are a significant detail of the landscape, especially on the northern part of the island which is largely ranchland. One "educated guess" is to place the fence alongside the road whenever the road goes through pasture. Another good approximation would be to put fences on property boundaries. Unfortunately, property lines are only available in paper, not electronic form. I wrote some code to generate fence posts and wires for any given line on the ground.
The most glaringly missing thing is trees. To add them, we need to answer some questions. What kind of trees and shrubs are commonly found on the island? Where are they found? How large and how densely do they grow? There are no detailed maps of species density, but there are rough maps of vegetation zones, which indicate the mix of species that would grow in an area under "natural conditions", ie. if nobody has developed the land. Another method is to try to analyze the satellite image and vary the density of the vegetation with the color of the map - brown means desert, light green typically indicates pasture or agriculture, and dark green is usually forest.
Then, we have to build models of the plants and place them on the terrain. The detailed and slow way is to build actual, fully 3D models of trees, but this is far too many polygons to render in realtime (currently). The quick-n-dirty method is to create a billboard, basically a flat picture of the tree, which looks passable from a distance. I gathered some pictures and made some billboards: 1 each for macadamia, Hapu‘u, papaya and 4 for ohi‘a, the most common tree on the island. Ohi‘a is a difficult tree because it grows very differently in different places, depending on altitude, soil and rainfall, so those factors also need to be taken into consideration when placing vegetation.
My current approach is to automatically scatter a random mixture of all 7 billboard on the terrain based on how dense the vegetation looks on the satellite image. By giving each billboard a different scale and rotation, it starts to give the impression of natural vegetation. I only render trees that are less than a few kilometers away, and there is far too much spacing between the trees, but it's still much too slow.
Eventually, we're going to want 3D models of trees, especially when you get close to them. I keep track of current software for generating plants, but there's nothing available yet that could generate a realistic model of any of my desired plants.
Also conspicuously missing are clouds. This proves to be very difficult because atmospheric rendering is still an area of research. The only approach currently feasible for realtime rendering is to use a "cloud layer", a thin plane at a fixed elevation with a cloud texture map on it. This would be passable if we were modelling, say, Kansas, looking up at clouds from the ground. However, Hawai‘i has a tremendous range of elevation to it, and most of the clouds are lower than the height of the mountains. As you go up Mauna Kea (4000m), you would pass right through the cloud layer and it would look fake.
Sky color (day and night, sunrise and sunset) is easier to simulate, by adding a colored "sky dome" that surrounds the island. I added one of these to the island, and it even has a correct star map that goes across the sky at night.
Turning on haze (global fog) can add a touch of realism. The haze color should match the color of sky at the horizon, so that the island grows more hazy into the distance. This works fairly well, but does not work at all during sunrise or sunset, since the color of the horizon is not uniform.
Another problem is that when you are walking or flying close to the ground, it looks extremely flat. This is because we only have elevation grid posts every 10 meters at best, or 100 meters at worst. The real island has lots of dips and lumps that can't be represented with such a widely spaced mesh. Real terrain has a "fractal" nature, meaning that the closer you look, the more detail you find. There are some algorithms for doing this, but many are quite complicated and i haven't attempted any implementation yet.
A potentially good approach, regardless of specific algorithm, may be to define a "local patch", a high-resolution grid that replaces the standard grid when you get close enough. The local patch would be generated only when needed, so you don't have to represent the entire island in memory. These local patches would also provide the ability to realistically carve the paths of roads and rivers into the ground. Some care (such as a gradual morph) would have to be taken to prevent the visible switching-in of the local patch detail as you approach it.
For many uses of the virtual island, such as tourism, we'll want to have animals. Seeing a mongoose scurry across the road, or a pueo (hawaiian owl) fly overhead at dusk are things that people remember from their vacations. So, i collected information on animals commonly found on the island.
One of the more interesting animals is the feral pig. It is a pest that damages the environment, and hunting it is encouraged. I envision a potentially popular usage for the virtual island would be to give people the chance to hunt the pigs. Such a simulation would be simultaneously scenic, challenging, educational, violent, and have an environmental message - something for everyone!
It's a fairly large amount of work to find a 3D model for an animal, texture-map it, define its motion and train it to locomote across the terrain or though the air or water - progress notes are online.
Right now, my elevation mesh is too widely spaced to carve riverbeds, and rivers don't look right if you just drape them on the terrain. So, i've put off rivers for now, but it's good to start thinking about how to model and simulate water.
Ocean tends to look really fake if you make it a solid color. So, i created some very large, flat polygons extending to the horizon, and put a water texture on them. It's not that realistic (for instance, the detail is static, too low-frequency and doesn't vary with time of day) but it's a first step.
I've generated some screenshots and keep track of some rough performance results, though they're changing rapidly. Overall development notes for the island are also available.
Using SeaBeam data license from the University of Hawai‘i, i was able to implement a visit to the emerging undersea volcano Loihi, but the data isn't redistributable.
There is an endless list of current challenges and areas for improvement. For example:
- The draped roads are always dipping "into the ground" because of the terrain LOD algorithm. I need a whole new approach for building the roads, which would probably work for rivers as well.
- The satellite image, even at full resolution, is much too blurry when you are close to the ground, e.g.. walking or driving. I need a set of realistic "geotypical" ground textures, a way to blend them together, and some way to know which texture to use for which area.
- Lighting: the sun rises and sets, but the mountains don't cast shadows. There is some promising research which might allow us to have realtime dynamic accurate lighting.
- Vegetation: in addition to producing billboards for many more species, a much better scheme for plant distribution is needed. For starters, roads and other developed areas need to be treated specially so that wild plants don't grow there. Then, species distribution in each vegetation zone needs to be estimated. I plan to combine a plant GIS database from the USGS BRD with first-hand observation.