Real-Time Rendering, Third Edition, 3rd Edition

i

i

i

i

i

i

i

i

Chapter 12

Polygonal Techniques

“It is indeed wonderful that so simple a figure as the triangle is

so inexhaustible.”

—Leopold Crelle

Up to this point, we have assumed that the model we rendered is available

in exactly the format we need, and with just the right amount of detail. In

reality, we are rarely so lucky. Modelers and data capture devices have their

own particular quirks and limitations, giving rise to ambiguities and errors

within the data set, and so within renderings. This chapter discusses a

variety of problems that are encountered within polygonal data sets, along

with some of the fixes and workarounds for these problems. In addition,

techniques to efficiently render polygonal models are presented.

The overarching goals for polygonal representation (or any other rep-

resentation, for that matter) in computer graphics are visual accuracy and

speed. “Accuracy” is a term that depends upon the context: For a machine

part, it may mean that the model displayed falls within some tolerance

range; for an aircraft simulation game, what is important is the overall

impression. The way a model is used is a key differentiator. An engineer

wants to control and position a part in real time and wants every bevel and

chamfer on the machine part visible at every moment. Compare this to a

game, where if the frame rate is high enough, minor errors or inaccuracies

in a given frame are allowable, since they may not occur where attention is

focused, or may disappear in the next frame. In interactive graphics work it

is important to know what the boundaries are to the problem being solved,

since these determine what sorts of techniques can be applied.

The main topics covered in this chapter are tessellation, consolidation,

optimization,andsimplification. Polygons can arrive in many different

forms and may have to be split into more tractable primitives, such as trian-

gles or quadrilaterals; this process is called triangulation or, more generally,

tessellation.

1

Consolidation is our term for the process that encompasses

1

“Tessellation” is probably the most frequently misspelled word in computer graphics,

531

i

i

i

i

i

i

i

i

532 12. Polygonal Techniques

merging and linking polygonal data, as well as deriving new data, such as

normals, for surface shading. Optimization means grouping and ordering

the polygonal data so it will render more rapidly. Simplification is taking

such linked data and attempting to remove unnecessary or insignificant

features within it.

Triangulation ensures that data is displayable and displayed correctly.

Consolidation further improves data display and often increases speed, by

allowing computations to be shared. Optimization techniques can increase

speed still further. Simplification can provide even more speed by removing

unneeded polygons.

12.1 Sources of Three-Dimensional Data

There are a number of ways a model can be created or generated:

• Directly typing in the geometric description.

• Writing programs that create such data, (this is called procedural

modeling).

• Transforming data found in other forms into surfaces or volumes, e.g.,

taking protein data and converting it into spheres, cylinders, etc.

• Using modeling programs.

• Sampling a real model at various points, using a three-dimensional

digitizer.

• Reconstruction from one or more photographs of the same object

(called photogrammetry; using a pair of photos is called stereopho-

togrammetry).

• Using three-dimensional scanning technologies.

• Using some combination of these techniques.

Our focus is on polygonal data generated by these methods. One com-

mon thread of most of these techniques is that they can represent their

models in polygonal form. Knowing what data sources will be used in an

application is important in determining what sort of data can be expected,

and so in knowing what techniques are applicable.

In the modeling world, there are two main types of modelers: solid-

based and surface-based. Solid-based modelers are usually seen in the area

and “frustum” is a close second.