Graphics Reference
In-Depth Information
we start with a polygonization and keep eliminating vertices until our polygonization
is coarse enough. However, there is a reverse aspect. For example, in cartography one
may have lots of data points (vertices) specifying a terrain and one would like a more
compact polygonized surface representation of it. Similar situations arise in areas of
scientific visualization and computer vision. Solving these problems is what one refers
to as
refinement
. It is a “top-down” process and, in fact, is usually considered to
include the polygonization problems for parameterized objects described earlier in
the section. (Interpret a parameterized object as one defined by its points and thus
defined by an infinite number of “vertices”.)
The simplification problem is fairly well understood for curves, but less so for sur-
faces. One can sometimes avoid simplification by not generating excessive data in the
first place by using an adaptive subdivision method. Algorithm 14.3.1, when applied
in reverse, is a variant of what is commonly called the
Douglas-Peucker algorithm
that is used in cartography and scene analysis. We start with a polygonized curve and
consider the segment from the first to the last point. If the other points are close
enough to the segment we throw them away and replace the original curve with the
segment; otherwise, we divide the curve into two and repeat the process for the two
halves.
Multiresolution modeling
is an area where one runs into the simplification
problem. In this type of modeling one wants to be able to zoom in and out of levels
of detail for the geometry. This is important for flight simulation and video games,
for example.
14.4
Trimmed Surfaces
Surfaces are often designed in a piecewise manner. For example, one may start with
a collection of surface patches and then add blends or fillets (see Section 15.6) between
them to get the final global surface. This involves “trimming” away parts of the
original patches. Also, when one performs set operations on solids, such as in CSG,
the resulting surface patches are best described as trimmed patches. For that reason,
the ability to represent trimmed surfaces is important for modelers and we now
discuss some approaches to doing this.
Most parameterized surface patches have a parameterization function p(u,v) that
has a rectangular domain. This means that the obvious way to display such a surface
is to evaluate p(u,v) on a grid of parameter values in its domain and then to display
the corresponding grid of lines, in the case of a wireframe display, or to use the grid
rectangles or triangles as an approximation to the surface patch in some scan line or
z-buffer algorithm. Trimming a surface patch involves restricting the domain of p(u,v)
to an arbitrary subregion that will not be rectangular in general. The boundary of the
subregion is called a
trimming curve
. In the context of blending, such curves are also
called
contact
or
link curves
. Polygonizing trimmed regions is not so simple. It may
get even more complicated if there is more than one parameterized patch involved
and the trimming overlaps patches. A number of algorithms have been developed over
the years to deal with such issues. We shall begin with a brief overview of some of
the existing algorithms. Keep in mind though that, in the end, all the algorithms want
a polygonization of the trimmed surface that has all the same properties that we
