Population explosion: a new crowd-animation technique lets researchers visualize densely populated virtual environments in real time. (techwatch).

Crowds are a virtual-reality developer's nightmare. With today's commercial tools, it is nearly impossible to render large numbers of independent humans in a scene without compromising either image quality or real-time interaction. The main difficulty centers on the large number of elements that need to be visualized and animated. The challenge has come to the forefront recently with the appearance of many highly detailed geometric models of towns and cities that are in need of believable virtual inhabitants to enhance their realism.

Toward this end, graphics researchers Franco Tecchia, Yiorgos Chrysanthou, and Celine Loscos in the Computer Science Department of London's University College are engineering a virtual population explosion with their development of a real-time system for generating densely populated urban environments. The method uses image-based rendering to maintain image quality and hardware-based collision detection to keep the digital people from bumping into each other and objects in the environment.

The image-based rendering approach is an alternative to traditional polygonal rendering methods utilized in most virtual environments. "With the classical approach, thousands of polygons are needed for each avatar to achieve good image quality. For this reason, rendering a crowd has so far been too CPU-intensive for real-time applications," says Tecchia. In contrast, image-based rendering relies on simple geometric representations for each character, and thus streamlines the rendering process. "We are able to display, in real time, scenes populated by up to 10,000 on-screen virtual characters."

The new system requires only one polygon per human, each of which is mapped with a pre-computed texture to depict the human from different viewpoints. Thanks to the exponential growth in recent years in dedicated texture memory on low-end PCs, the system is able to store a large number of different views of a human character, sampled while performing a walking animation.

Bring in the Crowds

The first phase of the new crowd-rendering system is the creation of a large set of sample views. For the initial test implementations, the researchers produced 8 images as seen from 16 different viewpoints at a certain height above the Y-axis. These were then mirrored to create 32 different views spaced 11.25 degrees apart, which are stored as textures. The system creates a visual representation of each human by pasting one of these images onto a single polygon having the correct orientation to the camera. For each frame, the system analyzes the relationship between each human and the viewpoint in order to select the appropriate image. To visually represent animated figures, the system stores in texture memory snapshots from different frames of an animation for the same model and selects different textures at each frame.

The principle disadvantage to this approach is the amount of texture memory that is necessary, says Tecchia. "We found 16MB of dedicated texture memory to be the minimum requisite for decent image quality. Currently, we are using up to 64MB, but in general, the more the better." To minimize the memory requirements, the system takes advantage of certain constraints of virtual environments that allow a reduction in the number of necessary images. For example, in scenes with large crowds, most of them appear to be far away from the viewpoint. Also, each human can have his or her own movement direction, but the possible rotations are usually limited to the Y-axis. Finally, adds Tecchia, "we will rarely have a view of some human as seen from below, so we can undersample these views."