Graphics Reference
In-Depth Information
([Kost91]). Kosters deals both with curves and surfaces and defines what he calls
angle
parameterizations
. These correspond to special reparameterizations that are computed
numerically from the original parameterizations using their first and second deriva-
tives. Using these parameterizations one simply uses a fine enough
uniform
subdivi-
sion of the domain of the parameterization to get the desired polygonization of the
curve or surface. Kosters also discusses the advantages and disadvantages of his
approach compared with recursive subdivision. For surfaces, two advantages are that
it is easier and works better for boundaries. Recursive subdivision methods are more
flexible.
We end the discussion of approximations to parametric curves and surfaces with
some observations. The first relates to the amount of work that is involved in subdi-
vision. Computing functions can sometimes be a lot of work, but in certain cases it
can be done relatively efficiently. Specifically, subdivision of B-splines corresponds to
knot insertion and subdivision of Bézier objects corresponds to de Casteljau subdivi-
sion. Second, a common approach to polygonization is to find a single step size, so
that the linear approximation corresponding to the subdivision using that uniform
step size is guaranteed to be within the desired tolerance over the entire domain of
the parameterization. It is important here that this step size is not chosen too con-
servatively; otherwise, one does a lot of extra work subdividing more than would be
necessary. Zheng and Sederberg ([ZheS00]) describe an algorithm for rational curves
and surfaces that produces step sizes that are substantially larger than obtained by
previous methods. Finally, many polygonization algorithms for surfaces work only
for parameterizations with rectangular or triangular domains and do not work for
trimmed surfaces. We shall consider that case in Section 14.4 and indirectly revisit
the whole polygonization problem.
Next, we consider tilers for implicit objects but shall restrict ourselves to general
comments. Sections 14.5 and 14.6 will describe some specific algorithms. Implicit
tilers are also referred to as
isosurface generation algorithms
when the data is pre-
sented in the form of values of a function f and one wants to extract from that data
the surface defined by an equation f(
p
) = c. In general, at the top level the tilers in
question end up dealing with data associated to the vertices of some sort of spatial
partitioning. In other words, space has been divided into polygonal cells, typically
squares or triangles in the two-dimensional case, and polyhedral cells, typically cubes
or tetrahedra in the three-dimensional case. The tilers fall into two classes:
discrete
tilers
that deal with discrete data and
continuous tilers
that deal with continuous data.
By discrete data we mean data obtained either experimentally, such as medical
data from MRI or CT scans, or from volumetric computations, such as discrete grids
from fluid flow simulations. The data typically corresponds to contour data for some
unknown function. In the continuous data case we assume that we actually have a
(smooth) function whose zeros define the object, in addition to having a cell decom-
position with data at the vertices.
In both the discrete and continuous data case the goal of the tilers is to determine
a linear approximation to the curve or surface that the data is assumed to be speci-
fying. Specifically, one wants to determine how the object intersects the edges and/or
faces of the cells and create a polygonization of the object from that information. In
the discrete data case one has to interpolate the given data at the vertices of the cells
to find intersections. In the continuous data case, the intersection can be computed
accurately. If the cells in our partition are of different sizes, then our tiler is called an
