Graphics Reference
In-Depth Information
their tasks. For example, we pointed out that smooth objects are typically rendered by
rendering collections of line segments for curves and collections of facets for surfaces.
Some of the intersection algorithms were based on piecewise linear approximations.
There are many other CAD/CAM applications where one wants or needs such approx-
imations. Another is the grid or mesh representations needed for finite element models.
In all such situations it is important that the shapes of the original objects were
matched sufficiently faithfully. The reader might have gotten the impression that to
accomplish this one simply has to subdivide enough in some straightforward way, but
there is more to it than that. This section discusses some issues that have to be looked
at when deciding on an approximation. In fact, we shall look at the general topic of
how to “polygonize” objects. That term will mean representing an object by an organ-
ized collection of edges or facets, depending on the dimension of the object. The terms
“tile,” “tesselate,” or “discretize” are sometimes used to mean the same thing as “poly-
gonize.” The term “tile” is especially popular when it comes to implicit objects.
Although there are many algorithms for polygonizing objects, they are not all
equally good. Their worth depends on the particular application, but one cannot make
choices if one does not understand the issues involved. Some properties that one
usually wants the polygonized object to have are:
(1) One wants it to be a good approximation to the shape of the original object.
Its points should be within a specified distance from the object.
(2) It should be efficient. Usually this means that we want to use as little space
as possible to achieve property (1), but the time an algorithm takes to produce
the approximation may also play a role. Ideally, the linearization should be
adaptive with fewer edges or facets in places where the object is relatively flat.
(3) In the case of surfaces, one would like “well-shaped” facets. For example,
facets that are thin slivers are bad for finite element methods.
(4) The approximation should not have “cracks” and have the same topology
locally as the part of the object it is approximating.
We start our discussion of polygonization algorithms by looking at some that
apply to parametric objects. In this case we really have two problems. First, we have
to polygonize the domain of the parameterization and second, we often want to ensure
that this polygonization will get mapped to a “good” polygonization of the actual
object. By “good” one means that, in the case of surfaces, the approximating facets
have a reasonable size and shape. As we just mentioned, long thin facets are consid-
ered bad. The hard part is the second problem because the domain of a parameteri-
zation is just an interval in the case of curves and typically a rectangle in the case of
surfaces. The exception is trimmed surfaces, but those will be considered in Section
14.4. It would be nice if a good polygonization of the domain of a parameterization
would induce a good polygonization of the object, but for that to happen, the para-
meterization would have to be close to a similarity transformation and that is rarely
the case.
Suppose that p : [a,b] Æ
R
n
defines a parametric curve. We can approximate the
curve by a polygonal one by dividing its domain into k intervals a = u
0
< u
1
< ...< u
k
= b and use the polygonal curve defined by
p
i
= p(u
i
). The common choice is to use
the uniform subdivision u
i
= a + i (b - a)/k. This may not be a good choice, however,
for two reasons:
