Outdoors Scene Graphs

The first outdoors games were just plain terrain renderers simple flight simulators with coarse meshes. The advent of faster graphics cards has allowed for greater realism, and today, we can do much more than render vast areas of land. Cities, forests, and rivers can all be displayed to convey the sense of size and fullness players have learned to expect. But rendering realistic outdoor environments does not come without a host of challenges and restrictions that you should be aware of. In this section, we will explore them, exposing some well-known approaches to some of these problems.

To begin with, outdoors scenarios are significantly bigger than indoors-only levels. Often spanning several square kilometers, the amount of geometry required to fill these levels is simply huge. How many triangles does a forest have? Well, recall that we did the math a couple of chapters ago and reached the conclusion that Yosemite National Park is about 25 billion triangles. Assuming approximately 100 bytes per triangle, which is reasonable, we get 2.5 trillion bytes, or 2.5 terabytes. That's quite a challenge in terms of fill rate, bus speed, and memory footprint.

There are three obvious conclusions to this analysis. First, we will need to use instance-based engines, so we don't store each geometry piece individually but as an instance that we will repeat many times. Storing unique geometry would require a huge amount of storage space. Second, some kind of LOD analysis will be required to maintain a decent performance level. Third, a fast routine to discard an object (based on its size and distance) will be required.

A popular approach is to combine a primitive table with some clever spatial indexing and LODs to ensure that we can display a realistic, full environment at interactive frame rates. To begin with, we will have a primitive list, which is nothing but an array holding the fundamental building blocks of our scenario, similar to the old-school sprite tables used to hold tiles in a side scroller. This table will store each unique geometrical entity in our game world. For a forest, for example, we will need several types of trees as well as some stones and plants. Clearly, we won't store each tree, but just a few, which, once combined, will provide enough variation for the game. From my experience, 10 to 15 good quality trees are all you need to create a good-looking forest.

Each object should then come with LOD support, so we can vary its triangle rate depending on distance. Discrete LODs, probably with alpha-blending, are the most popular technique. Other, more sophisticated methods such as progressive meshes can be used as well, but we need to be aware of some potential pitfalls. Remember that a progressive mesh recomputes the representation as a combination of vertex splits and edge collapses dynamically. The key is to reuse the solution for several frames, so we are not recomputing the object model in each frame. So how can we do that in an instance-based game world? Quite possibly, the same tree will appear at varying distances within a single frame, making us recompute it too frequently and slowing down the application.

Once we have our primitive list, equipped with LODs, we need to decide how to access spatial information. For large scenarios, it is fundamental to allow fast queries such as "Which objects are in our view frustum?" and so on. We simply cannot afford to traverse the instance list object by object. Imagine a large game level, spanning many miles. We will then store the map in a spatial index. I recommend using a regular grid with each bucket holding a list of <primitiveid, position> pairs. By using a spatial index, we can quickly scan only that portion of the map surrounding the player, not the whole thing. The choice of a gridlike approach offers great performance at the cost of some extra memory footprint. But it surely pays off at render time. Other approaches such as quadtrees work equally well, but they are designed for static geometry only. A grid can easily be tailored so items can continually move around without degrading performance.

The spatial index should then be used for two different purposes. Using a frustum test, we will need to know which objects lie within the viewing frustum, and process only those. Here I recommend using not the four lateral planes, but the far Z plane as well. This way we can incorporate Z clipping elegantly. Add some fog so objects do not pop in too abruptly, and you are all set. Then, the second purpose of the spatial index is to aid in computing collision detection. Here we can restrict the search to the cell the player is staying in and the nine neighboring cells. Only objects located in these cells will be checked, so our collision detection can be considered effectively as independent of the level size.

There is a downside to all these great features, and that is memory footprint. A grid spatial index will eat some of your precious resources, so make sure you select the cell size carefully to control memory usage. Indexing a 1x1 km with a cell size of 10 meters (great for speedy collision detection) involves slicing it into 10,000 cells. Even if each cell is just a <primitiveid, position> pair (assuming only one object per cell), the resulting structure will only be a couple of megabytes in size.