Graphics Reference
In-Depth Information
a dynamic way from one scan beam to the next. Alternatively, one could do some post-
processing of the trapezoids. Actually, the problem of thin triangles or trapezoids is
only part of the problem. As we pointed out in Section 14.3, how the domain of a
parameterization is polygonized has, in principle, little bearing on the polygonization
of the surface that this polygonization induces. If getting a uniform polygonization
for a trimmed surface is important, then an approach like in [ChPP98] could be
considered.
We shall end this section with a few words about a problem related to trimming
curves. A trimming curve for a parametric surface p(u,v) is usually assumed to be a
curve g(t) in parameter space of the parameterization p(u,v). One may need to deal
with the trimming curve p(g(t)) in the surface directly. The general problem is to find
an appropriate representation of the composite of two functions given a representa-
tion for each separately. For example, suppose that both g(t) and p(u,v) have a Bézier
representation, can one represent the composite p(g(t)) as a Bézier curve? Among
other applications, an affirmative answer would be useful for data exchange between
CAD systems. The representation of composite functions has been studied for various
types of functions. We shall leave the reader with one reference for this subject. In
[LasB95] it is shown how the composite of a Bézier trimming curve and a Bézier
tensor product surface can be given an explicit Bézier representation.
14.5
Implicit Shapes
14.5.1
Implicit Curves
This section considers ways to find and describe the solutions to a polynomial equa-
tion of the form
(
)
= 0
fxy
,
.
(14.8)
We shall look at rasterization, marching, and algebraic geometry approaches.
In Sections 2.9.2 and 2.9.3 we tried to generate a solution to a special class of such
equations on a pixel-by-pixel basis. A number of rasterization algorithms exist for the
general case of equation (14.8). The simpler ones, such as [Chan88], may fail at sin-
gularities. An algorithm that also works at singularities is described by Taubin
([Taub94]). The basic idea of the algorithm is to traverse all the pixels (thought of as
squares) and to output those that the curve intersects. Of course, it is much too inef-
ficient to look at every pixel since the curve would only intersect a few. Therefore,
Taubin uses an approach similar to the Warnock visible surface algorithm. One checks
if the screen is intersected by the curve. If it is not, then one is done. If it is, then it
is subdivided into four rectangular pixel areas and the same process is repeated for
each of the subrectangles. One keeps subdividing until one gets down to an individ-
ual pixel. The key element in the algorithm was coming up with an efficient test
whether the curve intersected a box. Actually, Taubin achieves efficiency by not having
a yes-or-no test but rather an “approximate” maybe-or-no test. However, and this is
an important condition in order to get a correct algorithm, if it said “maybe,” then
eventually it would say no to any of the subrectangles that were not intersected. We
