Issue: Volume: 24 Issue: 1 (January 2001)

Full Stream Ahead

Big models and real-time interaction can spell big trouble for the Web, but they can also spell big success for applications relying on consistent, high-quality 3D content delivery-from e-commerce to collaborative engineering to entertainment. Such applications rely on the fast transmission of visually realistic 3D objects to capture and keep the interest and excitement of end users, yet the cost of visual realism is large datasets. The enormous number of polygons needed to represent 3D objects and scenes in a pleasing manner places a tremendous burden on maintenance, storage, and computational resources.

Only recently, with advances in 3D graphics boards, have modelers and animators been able to display high-quality images in real time. Researchers are now scrambling to develop techniques to deliver the same high-quality 3D content over the Internet quickly and reliably. Toward this end, graphics experts at Tel Aviv University have thrown their hats into the ring with the development of a novel 3D streaming technology. The system uses a technique through which polygonal meshes are compressed into a progressive stream (minimizing requisite storage space) and delivered to client computers using asynchronous transmission.
A gleaming kettle model retains its glossy finish during its journey across the Internet thanks to a technique that minimizes the size of a 3D content stream for Web delivery without compromising the rendering quality and speed of the first view to reach

"The key point is that the compressed stream inherently contains levels of detail such that any prefix of the stream represents a coherent approximation of the 3D model," says Daniel Cohen-Or, an associate professor at Tel Aviv University and one of the chief architects of the new streaming technology. "Thus, the end user can view and interact with an approximation of the 3D models up to the optimal level of detail, enabling real-time interaction and a quicker response time."

The system is founded on the premise that the initial view of (and ability to interact with) a 3D object is critical because users are reluctant to wait out long download times. "The image of true interactive 3D models should appear on the end-user screen at least as fast as common still images appear, without compromising the rendering quality," says Daniel Cohen-Or. For this to happen, he notes, "it is crucial to minimize the overall size of the 3D content stream and the rendering time of the first view."

The first component of the streaming technique is a lossless mesh-compression method. A "mesh" refers to the collection of polygons (typically triangles) that form one or more 3D surfaces in space, which together define an object's geometry. In order to compress such data without losing information, both the geometric information and the connectivity information (the relationships among vertices and triangles) must be maintained. The Tel Aviv team achieves this using a hierarchical-decomposition technique in which, in a preprocess, a simplification algorithm is applied to the original triangular mesh to iteratively remove sets of vertices, generating a series of less-detailed models encoded into a compressed stream. Each parcel of compressed data includes a progressive approximation of the original 3D shape. On the client side, the process is reversed: The incoming data stream iteratively adds vertices to the progressive triangular mesh.

The challenge to such an approach rests in the fact that removing a vertex from a triangulation requires removing all of the edges connected to that vertex, which in turn requires generating a new set of triangles (called a patch) to cover the resulting hole. This precludes the direct reconstruction of the removed vertices. The new system uses a two-step process to compensate for this. First, when all of the holes have been triangulated, the system interpolates the patches to predict a set of points that will serve as a base for what are called displacement vectors. These represent the changes in magnitude and direction of the removed vertices from the predicted location.
Computer-generated characters such as Alfie and a Pokemon dinosaur can make their Web presence known with a novel technique that compresses large models without sacrificing detail, and delivers them across the Web in a progressive stream.

Next, each patch is color-coded (adjacent patches cannot be as signed the same color). During the reconstruction phase, the "decoder" detects the patches based on the color of the triangles, and the triangles of each recovered patch are removed. The system predicts the correct location of the removed vertices based on known vertices and their immediate neighbors, then adds the associated displacement vector to the predicted point to recover the original location of the vertex. Finally, the vertices of the patch are connected to the inserted vertex. This progressive approach helps to compensate for low network bandwidth and transmission latency. Moreover, says Cohen-Or, "it effectively reduces the cost of quality-of-service delivery of 3D content over the Internet."
The original model of this motorcycle contains 300,000 triangles. Using the progressive compression technique, this view contains only 20,000 triangles, but still maintains the important details.

To develop a commercial implementation of this technology, Cohen-Or has formed a company called Enbaya. To date, Enbaya has developed a 3D delivery network through which a user uploading a 3D model to a company's servers receives a link to a compressed, Web-ready version of the model. The compressed file format is integrated into the X3D framework. (X3D is a next-generation, extensible 3D graphics specification that extends the capabilities of VRML.) The client system requires a small plug-in to process the incoming streams. The plug-in consists of multiple threads running in parallel: one to read the streams from the servers, others to decode the streams and produce usable data structures, and another to render the scene as the data is produced.

Development of the technology is ongoing. According to Efi Fogel, Enbaya's chief technology officer, "we are currently focusing our energies on extending the asynchronous transmission concept and the associated file format to support a range of free-form surfaces, animation sequences, and online collaboration applications." Information on the progressive-compression technology can be found at

Diana Phillips Mahoney is chief technology editor of Computer Graphics World.