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.
i
i
i
i
i
i
i
i
12.1. Sources of Three-Dimensional Data 533
of computer aided design (CAD), and often emphasize modeling tools that
correspond to actual machining processes, such as cutting, drilling, etc.
Internally, they will have a computational engine that rigorously manipu-
lates the underlying topological boundaries of the objects. For display and
analysis, such modelers have faceters. A faceter is software that turns the
internal model representation into polygons that can then be displayed. For
example, a model that appears as a sphere internally may be represented
by a center point and a radius, and the faceter could turn it into any num-
ber of triangles or quadrilaterals in order to represent it. Sometimes the
best rendering speedup is the simplest: Turning down the visual accuracy
required when the faceter is employed can increase speed and save storage
space by generating fewer polygons.
An important consideration within CAD work is whether the faceter
being used is designed for graphical rendering. For example, there are
faceters for the finite element method (FEM), which aim to split the surface
into nearly equal-area triangles; such tessellations are strong candidates for
consolidation and simplification, as they contain much graphically useless
data, while also providing no vertex normals. Similarly, some faceters
produce sets of triangles that are ideal for creating actual physical objects
using stereolithography, but that lack vertex normals and are often ill suited
for fast graphical display.
Surface-based modelers do not have a built-in concept of solidity; in-
stead, all objects are thought of in terms of their surfaces. Like solid mod-
elers, they may use internal representations and faceters to display objects
such as spline or subdivision surfaces (see Chapter 13). They may also
allow direct manipulation of surfaces, such as adding or deleting polygons
or vertices. This sort of tool can be used to lower the polygon count of a
model.
There are other types of modelers, such as implicit surface (including
“blobby” metaball) creation systems [117], which work with concepts such
as blends, weights, and fields. These modelers can create impressive organic
effects by generating surfaces that are defined by the solution to some
function f(x, y, z) = 0. Polygonalization techniques are then used to
create sets of polygons for display. See Section 13.3.
Data can also be generated from satellite imagery, by laser scanning, air-
borne LIDAR (light detection and ranging) [571], or other three-dimensional
scanners, by various medical scanning devices (in which image slices are
generated and recombined), and by photogrammetry and computational
photography techniques [1048]. Meshes produced are strong candidates for
simplification techniques, as the data is often sampled at regular intervals,
and many samples have a negligible effect on the visual perception of the
data. Some of these techniques generate nothing more than point clouds,
with no inherent connectivity between the points. Reconstructing meshes
i
i
i
i
i
i
i
i
534 12. Polygonal Techniques
from these samples can be difficult, so alternate rendering techniques such
as point rendering may be used instead (see Section 14.9).
There are many other ways in which polygonal data is generated for
surface representation. The key is to understand how that data was cre-
ated, and for what purpose. Often, the data is not generated specifically
for graphical display, or even if it is, various assumptions made by the de-
signers about the renderer may no longer hold. There are many different
three-dimensional data file formats in existence [912, 1087], and translat-
ing between any two is often not a lossless operation. Understanding what
sorts of limitations and problems may be encountered with incoming data
is a major theme of this chapter.
12.2 Tessellation and Triangulation
Tessellation is the process of splitting a surface into a set of polygons. Here,
we focus on tessellating polygonal surfaces; curved surface tessellation is
discussed in Section 13.6. Polygonal tessellation can be undertaken for a
variety of reasons. The most common is that almost all graphics APIs and
hardware are optimized for triangles. Triangles are almost like atoms, in
that any surface can be made out of them and rendered. Converting a
complex polygon into triangles is called triangulation. There are other rea-
sons to tessellate polygons. The renderer may handle only convex polygons
(such tessellation is called convex partitioning). The surface may need to
be subdivided (meshed) in order to store at each vertex the effect of shad-
ows or interreflections using radiance transfer techniques [288]. Figure 12.1
shows examples of these different types of tessellation. Nongraphical rea-
sons for tessellation include requirements such as having no polygon be
larger than some given area, or for triangles to have angles at their ver-
tices all be larger than some minimum angle. While angle restrictions are
normally a part of nongraphical applications such as finite element anal-
ysis, these can also serve to improve the appearance of a surface. Long,
Figure 12.1. Various types of tessellation. The leftmost polygon is not tessellated, the
next is partitioned into convex regions, the next is triangulated, and the rightmost is
uniformly meshed.
i
i
i
i
i
i
i
i
12.2. Tessellation and Triangulation 535
Figure 12.2. Warped quadrilateral viewed edge-on, forming an ill-defined bowtie or
hourglass figure, along with the two possible triangulations.
thin triangles are worth avoiding, if possible, as different shades among the
vertices will be interpolated over a long distance.
One of the first processes a surface tessellator normally needs to per-
form is to determine how best to project a three-dimensional polygon into
two dimensions. This is done to simplify the problem and so simplify the
algorithms needed. One method is to determine which one of the xyz coor-
dinates to discard in order to leave just two; this is equivalent to projecting
the polygon onto one of three planes, the xy,theyz,orthexz.Thebest
plane is usually the one in which the polygon has the largest projected area
(this same technique is used in Section 16.9 for point-in-polygon testing).
This plane can be determined by computing the area on each projection
plane, or by simply throwing away the coordinates corresponding to the
coordinate of greatest magnitude in the polygon’s normal. For example,
given the polygon normal (−5, 2, 4), we would throw away the x coordinates
because −5 has the greatest magnitude.
The projected area test and polygon normal test are not always equiv-
alent, depending on the way in which the normal is computed and whether
the polygon is flat. Some modelers create polygon facets that can be badly
warped. A common case of this problem is the warped quadrilateral that
is viewed nearly edge-on; this may form what is referred to as an hourglass
or a bowtie quadrilateral. Figure 12.2 shows a bowtie quadrilateral. While
this figure can be triangulated simply by creating a diagonal edge, more
complex warped polygons cannot be so easily managed. Casting these onto
the xy, xz,oryz plane that gives the largest projected area will eliminate
most, but not all, self-intersection problems. If using this plane leads to
self-intersection (in which a polygon’s edge crosses itself), we may con-
sider casting upon the average plane of the polygon itself. The average
plane is computed by taking the three projected areas and using these to
form the normal [1077]. That is, the area on the yz plane forms the x
component, xz the y,andxy the z. This method of computing an aver-
age normal is called Newell’s formula. If self-intersection is a possibility,
then a laborious comparison among the polygon’s edges and splitting is
required. If the polygon has a large number of edges, then a plane sweep
can be used so as to limit the amount of edge/edge testing that is done [82].
See Section 16.16 for efficient methods for performing the intersection test
itself.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.