View-Dependent Polygonal Simplification

A very brief introduction to view-dependent polygonal simplification

Interactive computer graphics applications have long used the concept of levels of detail or LODs to help manage complexity and speed rendering. High-fidelity graphics requires very detailed geometric models of each object to be rendered, be it an airplane for a flight simulator, a monster in a video game, or a piece of furniture in an archtectural walkthrough. But only some of that detail is actually necessary at a time. For example, if a video game monster is far away, it covers only a few pixels on the screen. Clearly a less detailed version of the monster would suffice. The traditional approach, then, is to create several versions of the monster, each at a different LOD. Less detail may then be allocated for small, distant, or otherwise unimportant objects.

Given a detailed 3D model, the task of creating less-detailed versions of that model is called simplification. Modern graphics hardware uses polygons to represent 3D shapes, since their mathematical simplicity lends itself to simple, regular rendering algorithms that embed well in hardware. Thus methods that create LODs from an original model are often known as polygonal simplification algorithms. How best to reduce polygon count while retaining visual appearance is an open problem, and polygonal simplification is a very current topic in computer graphics.

View-dependent simplification or VDS is a relatively recent departure from the traditional approach to polygonal simplification. Rather than creating discrete LODs in a preprocess, and choosing among them at run-time, VDS adjusts detail dynamically, retessellating objects on the fly as the viewpoint changes, and continuously, allowing a single object to span multiple levels of detail. These two features enable view-dependent simplification, in which the level of detail chosen for an object (or group of objects) is adjusted for the current viewpoint.

Advantages of VDS over traditional static LOD:

Very large objects. If an object is very large with respect to the viewpoint (for example, the terrain in a flight simulator), no single LOD can adequately represent both the portions of the object near the viewer and the portions distant from the viewer. A traditional LOD system can draw the object at high fidelity, with pleasing visual results but jerky motion due to unacceptably slow frame times, or at low fidelity, with smooth motion but poor visual quality. One solution is to subdivide the large object into smaller objects that simplify adequately, but this is difficult to do without introducing "cracks" at the subdivision boundaries. VDS, however, can draw nearby portions at high resolution and distant portions at low resolution, with a smooth degradation of detail in between.
Many very small objects. A collection of many small objects, seen at a great distance, will simplify to a collection of very simple LODs using traditional simplification. For example, suppose a model of a car engine consisting of 200 separate parts simplified to 200 cubes, requiring 1,200 polygons. Those 1,200 polygons could much better approximate the aggregate shape of the engine if the objects were allowed to merge into a single engine-shaped LOD. Traditional LOD, then, can require merging objects at some stage of simplification. Selecting which objects to merge and when to merge them is a difficult task, usually done by hand. VDS, however, offers a simple solution: treat the entire scene as a single object, to be simplified and rendered in a view-dependent fashion. The VDS algorithm can automatically merge objects as they receed from the viewer.
Topologically degenerate objects. While a few static LOD algorithms handle topological degeneracies, many assume well- behaved manifolds. The algorithm used by VDS, however, need neither require nor preserve manifold topology. This allows VDS to close holes in high-genus objects, sometimes necessary for drastic simplification.
Better fidelity. Since VDS simplifications are generated at run-time, they can use view-dependent criteria for potentially better fidelity than statically-generated view-independent LODs with the same number of polygons. For example, the varying distance of different regions of an object, or whether those regions lie on the silhouette, are inherently view-dependent factors that cannot be accounted for in a preprocess. (Note, however, that exploiting this advantage requires careful construction of the VDS vertex tree.)

Disadvantages of view-dependent simplification:

CPU Utilization. VDS requires greater CPU resources at run-time than traditional static LOD techniques, which need only pick an appropriate LOD for each object.
Graphics performance. Since the simplification in VDS is continuously shifting, acceleration techniques such as display lists and triangle strips are less practical than in traditional approaches, where each static LOD may easily be compiled ahead of time into a tri-stripped display list. This is a significant disadvantage, since modern graphics hardware often operates 2-5x faster when using these techniques. For complex enough environments, however, the more drastic simplification enabled by VDS can still lead to better overall performance and fidelity than static LOD approaches.

VDSlib is a public-domain package that implements view-dependent simplification and rendering of polygonal models. It is intended to be extremely flexible, with a callback-based API that allows developers or researchers to plug in their own criteria for simplifying, culling, and rendering the model. VDSlib emphasizes this flexibility over raw performance, and the current version is not highly optimized for speed or memory.

Back to the VDSlib home page.