Building Scalable 3D Games for the PC

There is absolutely no doubt that 3D games are the coolest thing on the PC today. Anyone who has played computer games recently, or even watched someone else play them, has surely marveled at the realistic, beautifully fluid images and smooth animations produced by high-performance PC's running current-generation game titles.

A great deal of technical innovation is spurred by the desire to advance interactive 3D gaming, both in the hardware and software R&D labs. Many PC hardware innovations, from CPUs to graphics chips to input peripherals, are a direct result of the needs of the game development community and their customers. Each new generation of hardware gives developers an excuse to push the platform further, driving it towards the breaking point.

While game developers forge ahead into new arenas, creating new and imaginative experiences for increasingly demanding audiences, they face multiple challenges from every direction. Of course, getting all this innovative 3D graphics stuff to work in real time at all is hard. But if that isn't enough of a problem, developers face another difficulty: dealing with the issue of scalability.

Harnessing the Next Great Thing

Gamers, and in turn, the game media and publishers, have come to expect that The Next Great Game will contain The Next Great Thing, when it comes to graphics and simulation of the 3D environment. This would be fine except that the gamers and publishers also want to see The Next Great Thing running on a two-year old PC, so that all the gamers of the world can play it. Developers have to make their games run on lower-performance systems to reach the widest possible audience, while still delivering a package that will keep the "lunatic fringe" gamers entertained and the press properly awestricken.

As long as the PC has existed, developers have written games designed to run on systems of widely varying performance. Scalability problems, however, have increased in recent years. For one thing, the range of performance from low end to high-end machines is increasing. This is not only due to increases in CPU clock speeds, but also factors like the introduction of expanded CPU instruction sets, aimed at enhancing 3D performance. Another factor is the monumental leap in graphics performance that has been achieved by the graphics hardware companies.

All this leaves game developers with the challenge of coming up with new ways to scale their games across that wide range of performance. We have no doubt that the developers are up to the challenge, particularly when the PC industry is doing its share to help them out. Out of this collaborative mix of minds, new techniques and algorithms to scale content have been born. Some of these new approaches are discussed in this article.

Areas for Scalability

The topic of scalability can be divided into two areas: techniques for scaling content (for example, a method for varying the polygon count of an object on the fly), and approaches to scaling the content (deciding what polygon count should be used for that object, given the current system performance).

Approaches to scalability can be classified within five major areas:

Scaling the Content

Scaling the content itself is not so much defined by any one particular algorithm, but rather the concept of adding or modifying characters, objects and scenery dynamically. Done properly, this can add to the believability of the environment without affecting gameplay or performance. The following examples llustrate this technique.

Imagine a medieval adventure game in which the player is walking a forest path on a sunny afternoon, enjoying the sights and sounds of the serene forest. Suddenly, a troll jumps out from behind a tree and attacks. In the interest of delivering consistent gameplay, the troll should attack with the same speed and degree of ferocity on both a low- or high-end system. Accordingly, the content must be designed to run on a low-end system. Using a scalable approach to design, however, the developer could include richer features designed to run on higher performance systems, such as birds flying through the trees, and squirrels running about the forest floor. These elements make the forest environment more believable, and create a more immersive experience, on systems that can handle the extra work, but these extra elements don't change the fact that a troll is trying to lop the player's head off.

This concept of 'ambient characters' has been seen in some titles already, like the 'space rodents' or flying creatures in Epic's Unreal, or the small maintenance robots in Lucas Arts' Jedi Knight. While these examples included the ambient characters on all systems, as the performance of high-end systems increases, developers have the opportunity to selectively incorporate elements like these on high-end systems to make their worlds more believable.

Flight simulators offer another example of how content can be scaled to the performance of a system. Imagine flying low over Broadway in Manhattan (hey, that's what flight sims are all about, right?).On the high-end systems, for example, the pilot would be able to see traffic lights at intersections. The developer, working from map data for the city, could have an artist model a single traffic light, and then algorithmically place the lights at every intersection. This approach would be possible only if the necessary system bandwidth is available. Same algorithms could selectively add mailboxes, parking meters, and perhaps even shrieking pedestrians. This sort of 'procedural content placement' straddles the line between scaling the game content and scaling the geometry used to represent the game characters and objects.

Scaling Geometry

The scaling of geometry is something that developers have been doing as long as there have been 3D games on the PC. A typical approach involves storing several versions of every object model, each at a different level of detail (LOD). The application swaps down to lower level of detail models as necessary, based on user selections or other criteria, such as the number of objects moving about in the scene or changes in the frame rate.

While "discrete LOD's" are commonly used, this approach has some drawbacks. One problem is that an artist has to model every one of the objects at multiple levels of detail, which is a long and tedious process. Each of these objects must then be stored on the disc, consuming space. Finally, switching from one level of detail to another can result in a visual glitch, referred to as 'popping', appearing onscreen. With these problems in mind, developers are exploring a number of other approaches to scaling geometry content.

Scaling the geometry content involves adding or removing polygons to the scene to maintain a sufficient frame rate or level of visual quality. Systems with higher performance processors and/or 3D accelerators will be able to pump more polygons to the display resulting in higher quality images. Several techniques currently exist for creating scalable geometry and more are likely to appear.

A computer graphics technique commonly used in higher end applications, but that can be used for creating scalable geometry in today's consumer applications, is to use parametric curves and surfaces. A parametric curve can best be described with an example. Assume that you are given four toothpicks and told to make a circle. First you'll probably put the toothpicks in a diamond shape in front of you, which is a rough approximation of a circle, but very rough. If you are given five, six, or fifty toothpicks, you can make shapes that more closely approximate a circle, but none would be exact (assuming that the size of the circle doesn't matter). If the size must stay the same, assume the toothpicks have the magical ability to stretch or shrink to arbitrary lengths. There would still be regions of flatness on the shape that are not typical of a "real" circle. Now, suppose you are given a piece of string and told to make a circle. Depending on your patience, you could create a circle of arbitrary precision.

This is similar to the way parametric surfaces relate to polygonal models. Suppose we're trying to model a wheel. With a polygonal model, you work with a bunch of triangles that are used to approximate the smooth, curved portions of the wheel. The approximation can be made more exact by using more, smaller triangles, but, as in the toothpick example, there will still be areas of flatness that don't exist on a "real" wheel. Using parametric surfaces, we work from a mathematical description of the wheel (for example, a center point and a radius and a width). Using the mathematical description, you can compute the precise points required to create the wheel.

During rendering of the image, the mathematical description of the object is used to generate an arbitrary number of triangles (because 3D accelerators are designed to handle triangles). Depending on the factors we've discussed (such as CPU, 3D accelerator, frame rate, and so on), you can selectively generate more or fewer triangles on the fly. Figure 1 shows an example of a parametric curve used to generate different numbers of triangles according to performance.

Most 3D modeling packages currently support modeling with parametric surfaces. In fact, 3D artists often prefer to work with them, rather than polygons. Consequently, game developers are faced with the challenge of getting the "mathematical descriptions" from the 3D modeling package and using these descriptions at runtime to generate triangles to feed to the 3D accelerator.

Parametric surfaces can really help in making a game scalable, but using this approach requires a paradigm shift on the part of the game developers (including both the artists and the programmers). There are some other techniques that don't require such a radical paradigm shift.

Let's go back to the toothpick example used earlier to illustrate the technique of progressive meshes. Suppose you're initially given a thousand toothpicks. You can use all one thousand toothpicks to make the circle and get pretty nice results. However, suppose you're told that you only have ten seconds to complete the circle. Within this limited time, you can only use some of the toothpicks, but you can still make a decent approximation of the circle. If given twenty seconds to make the circle, you could theoretically use twice as many toothpicks as you did for the ten-second circle. The quality of the circle you can make depends on the time you have to make it-up to the limit of your original thousand toothpicks.

This illustrates the basic concept of progressive meshes. The idea is that a 3D modeler creates a highly detailed version of a 3D object. Then, using the progressive mesh algorithm, information that describes how to remove triangles from the model, one-by-one, is created. This information can then be used at run-time to create models that include an arbitrary numbers of polygons (up to the maximum number of polygons originally used to create the model).

Progressive meshes enable game developers to spend less time creating artwork, because the artists don't have to create multiple levels of detail for each model in the game. Additionally, dynamic run-time decisions can be made, determining how many triangles to use to create the model, based on the available CPU, 3D accelerator, and other system characteristics.

A final technique for scaling the geometry of objects in a scene, referred to as subdivision surfaces, has recently gained popularity in the 3D graphics field. Returning to our toothpick example, assume that you're given four toothpicks and told to approximate a circle (sound familiar?). The obvious first attempt is to create the diamond shape that really doesn't look much like a circle. In a burst of creativity, you break each of the toothpicks in half. With eight, smaller toothpicks, you can make a better approximation of the circle. If you keep subdividing (breaking) the toothpicks, until you have sixteen, thirty-two, or more, you can create more accurate circles each time you repeat the process. Progressing to infinity, you would eventually end up with a precise circle.

This example illustrates the technique of subdivision surfaces. You start with a polygonal mesh that represents an object. Then, each triangle contained in the mesh is broken into four pieces that are repositioned to more closely approximate the desired object. The process can be repeated to create arbitrarily smooth, curved surfaces. Artists must contend with the challenge of creating an appropriate initial mesh that will subdivide neatly to produce the correct desired mesh. Fortunately, this process is well supported by some of the major modeling packages.

Scaling the geometry content in each scene definitely helps scale the application across a wide range of systems, but other approaches to managing scalability also exist. In a fast-moving game, developers not only have to put those polygons on screen, but they need to move them around, too. The animation process is another area in which content can be scaled.

Scaling Animation Quality

Many 3D games today use pre-stored animations to move the characters and objects in a scene. An artist positions the model (for example, a human character) in all of the poses necessary to create an animation sequence. For example, consider a 3D character that needs to be able to run, jump, and swing a sword. The artist first creates a collection of poses for each of these animated movements. This is typically done much like the way we've all created simple 2D animations, using a pencil and a pad of paper. On each page of the pad, you create the next "step" of the animation; when you flip between the pages rapidly, the animation comes alive.

When performing 3D animation, the game code typically cycles between the 3D models that represent the animation (sometimes moving the object in space at the same time, such as when a character is running or jumping). The problem is that the artists have to create all of the in-between steps. The maximum number of available steps limits the maximum frame rate of the animation. For example, for an animated running sequence, suppose that the artist creates ten steps that are designed to be played back in a one-second time frame. If the game is running at ten frames a second, then we get one step of the animation per frame. So far, so good. However, if the game is running at sixty frames a second, then we only get a new frame of the animation once every six frames. Not so good. We would be better off generating new animation steps algorithmically to correspond with our frame rate.

This is the basic idea behind interpolated, key-frame animations (or key-frame morphing). Animations are stored at some predetermined rate (say ten frames per second). Then, at run-time, the game determines how long the previous frame took and algorithmically creates a new frame that is an interpolation between two stored frames. This produces animations that always change smoothly from frame to frame, regardless of the frame rate at which the game is running. The net effect creates a satisfying experience for the gamer running the game at fifteen frames a second on a low-end system, as well as for a gamer running the game at sixty frames a second on a high-end system. If you consider the previous paper and pad animation example, this process would be the equivalent of adding pages in between existing ones, and drawing a new figure between the two neighboring ones to smooth out the animation.

A variation of the key-frame animation technique uses a key-frame of a "skeleton" to which a polygonal mesh is then attached. In its simplest form, the parts of the mesh are attached to individual "bones" of the skeleton. Picture a character running-the key-frame animation would describe the movement of the character, if you can imagine one bone for each moving part (much like you would draw a stick figure running). Then, polygonal meshes (which are boxes, in their simplest form) are attached to each bone. As the upper arm and lower arm move, a mesh is then attached to the upper arm and another mesh is attached to the lower arm.

This technique can look pretty good onscreen, but newer games use a better technique that avoids some of the problems inherent in this simple form of "skinning". The biggest problem is that the polygonal meshes attached to the bones often end up intersecting with one another. For example, the two meshes composing the upper arm/lower arm can overlap or leave a gap at the juncture. Aside from the nasty looking creases this creates, there is also a discontinuity created by the textures between overlapping meshes.

To avoid this overlap problem, developers are starting to use a technique called "single skin meshes". Basically, instead of having one mesh associated with each bone, they have one mesh for the whole model, but one or more bones influence each vertex of the mesh. At runtime, the positions of all bones affecting a vertex are used to calculate the final position of the vertex. The end result is the removal of the intersection and elimination of the texture discontinuity problems. See figure 2 for an illustration of this technique.

Single-skin meshes add some overhead to 3D-model creation and require additional CPU cycles for calculating the final vertex positions. In return for this processing overhead, the user of the game sees more visually appealing animations.

Scalable Lighting Issues

While increasing the amount of geometry in game applications provides more realistic looking objects, as well as allowing for more objects within scenes, there is more to creating a realistic looking environment than just the models in it. Lighting is another area that has a major impact on the realistic appearance of a created environment.

Calculating and displaying the lighting in a scene requires determining what light sources are in a scene, which objects they illuminate and how brightly, and how, in turn, those objects cast shadows and reflect the light.

It's difficult for developers to scale the lighting in a game, since this one element can be fairly important to the overall playability. Several possibilities for scaling the lighting do exist, however, and certain techniques can be used to make a game run across the wide range of platforms available.

Lighting effects can be scaled by choosing different lighting techniques to correspond with the relative performance of different systems. So, for example, the high-end systems can use lighting that is entirely dynamic with dynamically cast shadows and moving light sources (such as rockets). Low-end systems can have the lighting tuned down so that shadows are either non-existent or less dynamic (perhaps computed only once every other frame). Moving light sources might be removed or implemented with light maps and changing texture coordinates.

Another possibility is to use some of the scalable geometry techniques described earlier. Lighting could be calculated for a lower level-of-detail model and then, using calculated and stored connectivity information, the displayed vertices that aren't part of the lower LOD model would have their lighting values interpolated from the nearest vertices in the low LOD model.

This technique can apply well to parametric surfaces where the lighting calculations for generated surface points can be performed less often than the calculation of the surface points. Since the connectivity information is implicit in a parametric surface, it's easy to do the interpolation for the in-between vertices.

Shadows are represented in 3D applications in a number of ways. Most 3D games of the past year or two have resorted to simple shadow maps that resemble a dark circle or a blur underneath the object. In cases where the object sits on a flat ground plane, sometimes a simple geometric form of the object is 'squashed' on the ground to represent a shadow. More recently, developers are moving towards increasingly complex methods of generating shadows, such as projected textures, dynamic shadow maps, or using hardware features such as stencil buffers.

Most of these more advanced techniques of generating shadows involve calculations that chew up processor cycles, so developers need to adapt the techniques to suit low-end systems. Simpler mechanisms can be used to scale these shadow techniques across different systems. For example, if the system is incapable of handling a more complex shadow casting method, (such as using stencil buffers to create shadow volumes) then the application can be designed to switch to the more basic shadow map approach. Optionally, the application could disable shadows altogether.

Using 3D hardware accelerators that support stencil buffers, more exact shadow representations can be created based on the actual shapes of the objects casting the shadows. This technique involves creating a "shadow volume" for each object. The shadow volume is itself a 3D object, created by imagining a point at the light source and casting planes that intersect each silhouette edge of the object. This volume is then rendered through the stencil buffer to shadow all triangles that intersect the volume. In actual use, this technique produces impressive results. It can be used to generate self-shadowing of objects. An object, such as a donut, can be rendered so that it casts a shadow on itself when the light is off to one side. By using different level of detail models to create the shadow volume, this technique can also be made scalable, although in some cases artifacts can result as a byproduct of the scaling process.

You can also create shadows by rendering the object casting the shadow to a texture surface, and then using that texture as the shadow. This approach can produce more natural, softer shadow edges, and it can also be scaled in a number of ways. One scalability technique is to update the shadow's movement at half the frame rate as the rest of the application. This will minimize computations for use on lower end machines. On the down side, self-shadowing is much harder to accomplish with this technique than with the stencil buffer technique

Scaling Special Effects

Adding distinctive special effects is a great way for developers to distance their title from the competition. The kind of special effects we're talking about here include particle systems for generating smoke and fire, texture tricks, fog volumes, lens flares, and similar onscreen pyrotechnics.

Many kinds of effects can be scaled effectively.The simplest way to handle scaling is to just switch off the effect when running on lower end machines. Resourceful developers are also investigating more sophisticated ways of scaling these techniques.

Many multi-texture tricks being used by developers to increase realism in applications can be reduced or switched off to add scalability. Some of these include gloss mapping (to make objects look partially shiny), dynamic environment mapping (to reflect moving objects and not just stationary ones, detail texturing (to add detail), and bump mapping (to add surface relief).

A particle system offers a good example of the many ways in which effects can be scaled. Basically, a particle system is a collection of objects (particles) that behave according to a set of rules for the given system. They typically all move differently, but follow some global pattern. This makes them useful for depicting smoke, steam, blowing leaves, and so on. You can scale down a particle system by altering the granularity of the effect (reducing the number of particles), but increasing the particle size so that the effect has the same density, but a grainier appearance). Another way is to simplify the manner in which the individual particles are drawn. Is each one a full polygonal model, or just a sprite? Also, you can scale the manner in which particles interact with their environment. Does the application detect collisions between particles and their environment, or not? Are collisions between the particles themselves detected? Simplify the behavior and you can effectively scale down the effect for low performance systems.

Setting the Scaling Method

Every application has its own unique differences and the best techniques for supporting scalability will vary from application to application. Regardless of the method the developer chooses to build scalability into a game, another question remains: how to set the appropriate level of scaling.

The different approaches for deciding what level of content to use fit into four areas:

Typical applications apply one or more of these approaches in combination.

Letting the user set the level is probably the most common means of addressing this issue. Typically, a control panel lets the end user enable or disable features, or select the appropriate level of content. This approach is certainly the easiest to implement, and it also gives the end user some control over their experience. On the negative side, it requires that the end user understand some fairly complex performance tradeoffs and system configuration concerns. Novice users can easily become frustrated.

Some applications determine default settings according to designated hard limits. An application surveys the hardware configuration during installation (including CPU, graphics card, memory, and so on), and selects a predetermined level of content that corresponds with that level of system performance. This approach somewhat effectively matches content to system performance, but it has some drawbacks, too. One drawback is that the application may run into a configuration that the developer never anticipated. Also, factors other than those collected while determining the system configuration could adversely affect the performance. For applications that set the level of detail at install time, a hardware configuration change (such as the user upgrading their CPU or graphics card) would invalidate the settings.

Some applications employ pre-runtime profiling. Either during installation or while the application is loading, the performance of the system is measured through a series of tests. Then information returned from the testing is used to set the appropriate level of content. This approach attempts to tune the level of content to the system's performance, but it has a possible drawback. The 'test' results are assumed to be representative of the performance during game playing-- in reality, the load balance could change significantly.

Runtime profiling is considered the Holy Grail of scalability, but it is also the approach most fraught with problems. The underlying idea is that while the application is running, the current performance is measured and used in a feedback loop to tune the content level up or down. This tunes the content to the game play dynamically, but implementing this kind of system can be very difficult.

Typically, runtime profiling is accomplished by tracking a number of variables, settings, and weights, and then feeding this information back to the application. Some of the elements often used are the frame rate, distance and size of objects, object importance, pixel error, and so on. Care needs to be taken in the application design so as not to 'flip flop' back and forth between too high and too low a level of detail. This usually involves some sort of damping or maximum step size.

We hope this article has pointed out some of the challenges that game developers face when developing titles to run on the broadest range of PCs. As the gap between the high-end and low-end machines increases in coming years, developers will have to become even more resourceful to ensure that games take full advantage of the cutting edge equipment while still performing well on earlier machines. Now that you know a bit more about what is going on behind the scenes, you'll begin to notice how some of the effects and features described in this article influence the game performance of your own computer.

Dean Macri is a Senior Technical Marketing Engineer with Intel's Developer Relations Division. He is currently researching real-time physics with an emphasis on cloth simulation. He welcomes e-mail regarding NURBS and other parametric surfaces, or anything mathematical and related to real-time 3D graphics. He can be reached at [email protected].

Kim Pallister is a Technical Marketing Engineer and Processor Evangelist with Intel's Developer Relations Group. He is currently focused on realtime 3D graphics technologies and game development. He can be reached at [email protected].