Introduction

During the last years computers are more and more used for visualization of different kind of data. Due to the fast technological progress it is now possible to handle large data sets. Viewing and manipulating of CAD models, medical data created by computer tomography, or digital elevation models constructed from satellite images is no longer restricted to supercomputers. Although mid-range graphic workstations can do all these things, there is the law of nature that computers are too slow. In the same amount as computational speed is increasing, the user's demands are also increasing (or even more). Some performance problems can (only) be solved by waiting six months for the next computer generation. But intelligent algorithms for the rendering of triangle meshes can achieve on today's hardware a performance otherwise not to be expected within the next years. This article explains a method called Progressive Meshes introduced by HUGUES HOPPE in [5] and extended in [6,8].

One common approach to speed up graphics output is multiresolution, all objects are availabe at different resolutions. Among these resolutions the coarsest one sufficient to meet some user-defined fidelity goal is actually used for rendering. One can not expect to gain as dramatic improvements as with other problems (e.g. using binary search with instead of trivial search with T(n)=O(n)). Nevertheless the number of primitives required for an adequate approximation is usually much less than the total number of primitives for the whole model. It is desirable to have an output-sensitive algorithm, i.e. one with a rendering time of T(n,m)=O(m), where n is the size of the data set, and m is the area on screen covered by the projection of the object. An algorithm with this property can speed up rendering by two ways:

• Small objects that are far enough away from the camera occupy only a small fraction of the display area. They can be approximated with few primitives without visual loss of accuracy.
• Large objects that are only partly visible don't need to be sent to the graphics pipeline as a whole. Those parts lying outside the view volume¹ are clipped.

Note that reducing the number of triangles not necessarily reduces the number of pixels drawn. Instead, the geometry subsystem (see [3]) gets less work to do preventing it from being the performance bottleneck. Progressive Meshes as described in [6] support these features and are explained in more detail in section 3.