A Game Developer’s Review of
SIGGRAPH 2003
Morgan McGuire <matrix@graphics3d.com>

Why is the Sky Blue? July 2003 San Diego, CA. In San Diego you can sun under perfect blue skies and watch gorgeous ocean sunsets, then head out for a night of dining and hot dancing in the Gas Lamp Quarter. You might stop to wonder why those skies are blue and sunsets red. The answer is that Rayleigh scattering favors short wavelengths, so in the afternoon the sky is suffused with blue light. As the sun drops near the horizon we are in the right orientation to observe the red wavelengths. Together, this festive atmosphere down 5th street and nugget of atmospheric wisdom from Course 1 kicked off SIGGRAPH 2003.

Rendered sky from Mark Harris's outdoor illumination talk.

The ACM special interest group on computer graphics conference draws computer scientists, artists, and film and game professionals. Scientific papers and courses introduce the newest theory and an exhibition shows off the latest practices as NVIDIA, ATI, Pixar, SGI, Sun, and others showcase their products and productions. On the creative side, the Electronic Theater contains two hours of computer generated imagery. It is augmented by a continuously running Animation Festival, art gallery, and emerging technology display.

To Infinity and Beyond

Cambridge University astrophysicist Anthony Lasenby delivered the keynote address. He invited an audience focused on triangles to consider issues of a more cosmic scale. Physicists have long theorized that just as the universe exploded from a tiny point in the Big Bang 14 billion years ago, it will some day collapse back to that point in a Big Crunch. This crunch would be the collapse of reality as we know it. Although it would not happen for an inconceivably long time, the notion of an inevitable death sentence for humanity has hung heavily over science fiction fans and astrophysicists familiar with this theory. The deciding factor for our ultimate fate is whether the universe is currently expanding fast enough. If it is, growth will fight the gravitational forces attracting all matter towards a common center. If not, we had better get started on interdimensional travel right now.

In pursuing the question, a startling fact emerged: the universe is closed in space. This means that if you traveled very fast and long enough in one direction you would come back to where you started. If this sounds strange, think of how the same argument would sound to someone who thought the Earth was flat. They measured the expansion rate as well. Good news: the universe is also expanding sufficiently fast that we are safe from the Big Crunch.

What does this have to do with graphics? The Geometric Algebra (a.k.a. Clifford Algebra) used by astrophysicists to resolve these issues can also be used to simplify movement in 3D. Game programmers typically treat straight-line motion separate from rotating motion. This complicates the process of finding in-between orientations given two positions, since the translation and rotation components must be interpolated separately. Furthermore, rotations by themselves are tricky to interpolate. Geometric algebra presents a framework where 5-dimensional "rotors" represent both 3D rotation and translation within a unified framework, and also take the pain out of rotation. This leads to smoother camera movement and character animation as well as a much cleaner theoretical framework for motion in computer graphics. How much does this idea appeal to graphics practitioners? Lasenby's $90 book on the topic sold out from the bookstore within the next hour and immediately started racking up mail-order requests.



New Tools for Game Development

Games have become pervasive at SIGGRAPH. Game developers are in the audience and behind the podiums and their games are shown in the Electronic Theater and played in the Vortechs LAN party. Most of the papers presented were relevant to game development, but a handful really stood out as ideas solid enough to begin incorporating into new projects immediately. Surprisingly, these generally were not the hottest new rendering techniques but solid behind-the-scenes algorithms appropriate for game creation tools.


Terrain Texture

Wang Tiles for Image and Texture Generation by Michael Cohen (Microsoft Research), Jonathan Shade (Wild Tangent), Stefan Hiller, and Oliver Deussen (Dresden University of Technology) is a texture synthesis method that can reduce tiling artifacts on terrains. No matter how seamless the wrapping transition and well constructed the texture, a single repeating grass or rock texture will produce visual tiling artifacts when viewed from far away. To overcome this, games currently use multiple grass tiles and assign them randomly. However, the seams are visible between the different grass textures. For a texture like rock that has larger features, these seams are completely unacceptable. The Wang Tile paper describes how to fit a set of related textures together to form an arbitrarily large plane that has no repetitive pattern and no seams. Synthesizing these textures requires only an algorithm like Wei and Levoy's 2000 paper or any of the several texture synthesis papers from last year.


Easy Motion

Anthony Fang and Nancy Pollard of Brown University presented Efficient Synthesis of Physically Valid Human Motion. Their algorithm runs an optimizer to compute physical motion from an initial set of key poses for a human body. What is amazing is how few key poses it needs. For example, say we want to generate an animation of a person swinging across a set of monkey bars. Fang's algorithm need only be told that the hands touch each rung in sequence. It uses built-in knowledge of the human body to independently deduce how to swing the arms, head, and legs for a realistic animation. This method could be adapted to create a whole sequence of skeletal animations for a game character without requiring an animator to manually guide each limb through its motions. Other examples in the paper include synthesizing walking and a gymnast's somersault dismount from a high bar.

The optimizer creates realistic motion, but games often need stylized motion. Addressing this need, Mira Dontcheva spoke on Layered Acting For Character Animation, a new animation method created with coauthors Gary Yngve and Zoran Popovic at the University of Washington. Their system allows a user to act out motion for a character one body part at a time. Unlike traditional motion capture, the layered approach allows a human being to simulate the motion of a kangaroo, dog, or spider because the acting applies to a single limb and not the whole body. By demonstrating the motion path of the spider and giving eight separate leg performances, a two-legged researcher can become an eight-legged monster. Acting is far easier than using typical animation tools like Character Studio, so now animators can be replaced with actors or even novices to create motion data. They will not be entirely out of a job, however. Someone still has to rig the skeleton within a 3D model and possibly tweak the results.

Easy Texture

Kraevoy et al's Matchmaker makes photo texture mapping easy.

Digital cameras make it easy for artists to capture realistic textures and Photoshop is the tool of choice for editing or painting them from scratch. To map a flat texture onto a 3D model, an artist assigns each 3D vertex a 2D coordinate within the texture map. Even skilled artists have to work hard to make sure this process does not distort the texture and the results often are not as good as they could be. Compare the texture maps from a typical 3D shooter to the images seen in-game. Distortions often ruin beautiful artwork and give faces an inhuman look. Alla Sheffer presented a paper on this topic, Matchmaker: Constructing Constrained Texture Maps by Vladislav Kraevoy, herself, and Craig Gotsman from the Israel Institute of Technology. Their program allows a user to make simple constraints like locking eye and mouth position in both the texture and model. It then solves for a consistent way of smoothly mapping the texture across the model. The process is akin to a traditional 2D warp but the output is 3D. Their results (pictured on the left) are incredible. The male head is texture mapped from a single photograph (mirrored to cover the whole face) and the full female body from simple front and back images. Each was produced using a few mouse clicks. Using conventional tools, these results would take hours of manipulation by a skilled artist to create.

Rendering Trees

It is common in games to simulate complex 3D objects with a single square facing the viewer. This square is called a billboard or sprite, and is textured with a picture of the 3D object to make it look convincing. Older games like Wing Commander and Doom used this technique exclusively. In new games characters and vehicles tend to be true 3D objects but explosions and trees are still rendered with billboards. One problem with billboards is that they appear to rotate as the viewer moves past since they always have the same picture. Using two or more crossing billboards with fixed orientations creates an object that appears to stay fixed in 3D, but up close the individual billboards are visible.

Billboard Clouds is a more sophisticated technique proposed by Xavier Decoret, Frédo Durand, François X. Sillion, Julie Dorsey of MIT, INRIA, and Yale. Their algorithm takes a 3D model as input and produces a set (or confusingly named "cloud") of billboards on various angles that collectively approximate the model. For distant objects the billboards appear to capture all of the complexity of the 3D model using far fewer polygons. In addition, the natural MIP-map texture filtering performed by a graphics card for small objects causes the edges of a billboard cloud to blend smoothly into the background. A true polygon object would present jagged edges that shimmer as it moves. However, it is sometimes possible to see cracks and distortions up close on a billboard cloud. While the algorithm is advertised for rendering distant objects, its greatest strength may be for rendering objects with many thin parts, like trees and scaffolding. The paper contains images of a tree and the Eiffel tower, both of which appear far nicer than their geometry counterparts typically would in a game.

Watch this Space

The shadows in many games are blurry and blocky because they are rendered with the Shadow Map technique. This algorithm captures a depth image of the scene relative to the light and compares it to the depth from the viewer. A point seen by the viewer and not by the light is in shadow and is rendered without extra illumination. This creates shadows whose blurry jagged edges reveal their underlying square depth pixels. While it is easy to interpret the blurring as a soft shadow, it is really an error created by bilinear interpolation on the depth pixels. To make the shadow boundaries crisp requires more memory than most games can afford to throw at the problem.

In 2001, Randima Fernando, Sebastian Fernandez, Kavita Bala, and Donald Greenberg from Cornell suggested Adaptive Shadow Maps for dividing up the screen according to the resolution needed. Strikes against their approach are the limited performance that comes from by GPU/CPU cooperation and viewer dependence in the remaining artifacts. In the end, it gets the job done and handles some difficult cases while cutting down on the ultimate memory requirements. Last year Marc Stamminger and George Drettakis of INRIA presented Perspective Shadow Maps to address the resolution problem. Their method is mathematically elegant but complicated to actually implement, and still fails when the viewer is looking towards the light or shadows fall nearly straight along a wall.

This year's approach is Shadow Silhouette Maps by Pradeep Sen, Michael Cammarano and Pat Hanrahan at Stanford. They use a conventional shadow map but augment it with geometric information about the silhouette edges of shadows (borrowing a page from the competing shadow volume algorithms). The edges are tracked in a separate buffer from the image and are used to control the sampling process when comparing light depth to image depth. They inherit the other flaws of shadow maps-- low resolution when the camera faces the light and 6x the cost when rendering point (instead of spot) lights-- but the blurry and blocky edges are replaced with crisp shadow edges.

Traditional shadow map (left) vs. Shadow Silhouette Map by Sen et al.