Multiresolution curves.
We describe a multiresolution curve representation, based on wavelets, that conveniently supports a variety of operations: smoothing a curve; editing the overall form of a curve while preserving its details; and approximating a curve within any given error tolerance for scan conversion. We present methods to support continuous levels of smoothing as well as direct manipulation of an arbitrary portion of the curve; the control points, as well as the discrete nature of the underlying hierarchical representation, can be hidden from the user. The multiresolution representation requires no extra storage beyond that of the original control points, and the algorithms using the representation are both simple and fast.
Introduction
A good representation for curves should allow for flexible editing, smooth-
ing, and scan conversion. In particular, a representation for curves should
support:
ffl the ability to change the overall "sweep" of a curve while maintaining its
fine details, or "character" (Figure 3);
ffl the ability to change a curve's ``character'' without affecting its overall

Figure

ffl the ability to edit a curve at any continuous level of detail, allowing an
arbitrary portion of the curve to be affected through direct manipulation

Figure

ffl continuous levels of smoothing, in which undesirable features are removed
from a curve (Figure 2);
ffl curve approximation, or "fitting," within a guaranteedmaximum error tol-
erance, for scan conversion and other applications (Figures 8 and 9).
In this paper, we show how a multiresolution curve representation can provide
a single, unified framework for addressing all of these issues. It requires
no extra storage beyond that of the original m control points, and the algorithms
that use it are both simple and fast, typically linear in m.
There are many applications of multiresolution curves, including computer-aided
design, in which cross-sectional curves are frequently used in the specification
of surfaces; keyframeanimation, in which curves are used to control
parameter interpolation; 3D modeling and animation, in which "backbone"
curves are manipulated to specify object deformations; graphic design, in
which curves are used to describe regions of constant color or texture; font
design, in which curves represent the outlines of characters; and pen-and-ink
illustration, in which curves are the basic elements of the finished piece. In
all of these situations, the editing, smoothing, and approximation techniques
we describe can be powerful tools.
1.1 Related work
Some of the algorithms supported by multiresolution curves are completely
new, to our knowledge, such as the ability to edit a curve at any continuous
level of detail, and the ability to change a curve's character without affecting
its overall sweep. However, the majority of applications described in this
paper have already been addressed in one form or another. Although the
algorithms we describe compare favorably, in and of themselves, with most
of this previous work, it is the convenience with which the multiresolution
representation supports such a wide variety of operations that makes it so
useful. Here we survey some of these previous techniques.
Forsey and Bartels [13] employ hierarchical B-splines to address the problem
of editing the overall form of a surface while maintaining its details.
Their original formulation requires the user to design an explicit hierarchy
into the model. In later work [14], they describe a method for recursively fitting
a hierarchical surface to a set of data by first fitting a coarse approximation
and then refining in areas where the residual is large. This construction
is similar in spirit to the filter bank process used in multiresolution analy-
sis, as described in Section 2.1. One significant difference is that in their
formulation there are an infinite number of possible representations for the
same surface, whereas the multiresolution curve representation is unique for
a given shape. Fowler [15] and Witkin and Welch [28] also describe methods
in which editing can be performed over narrower or broader regions of
a surface; however, in neither of these works is there an attempt to preserve
the higher-resolution detail beneath the edited region.
Curve and surface smoothing algorithms that minimize various energy
norms have also been studied; these are surveyed in Hoschek and Lasser
[16]. One example is the work of Celniker and Gossard [7], in which a fairness
functional is applied to hand-drawn curves, as well as to surfaces. The
method we describe is really a least-squares type of smoothing, which is
much simpler but supports continuous levels of smoothing that behaves quite
reasonably and intuitively in practice.
Many schemes for approximating curves within specified error tolerances
have also been explored [2, 20, 23, 27]. Most of this research has centered
on various forms of knot removal for representing curves efficiently with
non-uniform B-splines. In this paper, we look at the very practical concern
of producing a small number of B-ezier segments that approximate the
curve well, since these segments are the standard representation for curves
in PostScript [1], the most common page description language. Our requirements
are also somewhat different than those of most previous curve-fitting
methods. In particular, for our application of scan conversion we do not require
any particular continuity constraints for the approximating curve. Relaxing
this condition allows for potentially much higher compression rates.
1.2

Overview

The next section discusses the theory of multiresolution analysis, and develops
a multiresolution representation for B-spline curves. Sections 3, 4, and 5
describe how this representation can be used to support efficient smoothing,
editing, and scan conversion. Finally, Section 6 suggests some areas for future
research. The details of the multiresolution curve formulation can be
found in the appendices.
2 Theory of multiresolution curves
In this section, we discuss the theory of wavelets and multiresolution analy-
sis, and weshowhow it can be applied to representingendpoint-interpolating
B-spline curves.
2.1 Wavelets and multiresolution analysis
Wavelets are a simple mathematical tool that have found a wide variety of
applications in recent years, including signal analysis [22], image processing
[11], and numerical analysis [6]. In this section, we sketch the basic ideas
behind wavelets and multiresolution analysis. Rather than presenting the
classical multiresolution analysis developed by Mallat [22], we present here
a slightly generalized version of the theory, following Lounsbery et al. [19],
that is more convenient for our application of representing open curves. 1
Consider a discrete signal C n , expressed as a column vector of samples
In our application, the samples c n
i could be thought of as a
curve's control points in IR 2 .
Suppose we wish to create a low-resolution version C n01 of C n with a
fewer number of samples m 0 . The standard approach for creating the m 0
samples of C n01 is to use some form of filtering and downsampling on
the m samples of C n . This process can be expressed as a matrix equation
where A n is an m 0 2m matrix.
Since C n01 contains fewer samples than C n , it is intuitively clear that some
amountof detail is lost in this filtering process. If A n is appropriatelychosen,
it is possible to capture the lost detail as another signal D n01 , computed by
is an which is related to matrix A n .
The pair of matrices A n and B n are called analysis filters. The process of
splitting a signal C n into a low-resolution version C n01 and detail D n01
is called decomposition.
If A n and B n are chosen correctly, then the original signal C n can be recovered
from C n01 and D n01 by using another pair of matrices P n and Q n
called synthesis filters, as follows:
Recovering C n from C n01 and D n01 is called reconstruction.
Note that the procedure for splitting C n into a low-resolution part C n01
and a detail part D n01 can be applied recursively to the new signal C n01 .
Thus, the original signal can be expressed as a hierarchy of lower-resolution
signals shown in Figure 1.
This recursive process is known as a filter bank.
A
A .
. D
A

Figure

1: The filter bank.
Since the original signal C n can be recovered from the sequence C 0 , D 0 ,
sequence can be thought of as a transform of the original
signal, known as a wavelet transform. Note that the total size of the
1 The more general theory described here differs from Mallat's original formulation
by relaxing his condition that the basis functions must be translates and scales of one
another.
is the same as that of the original signal C n ,
so no extra storage is required.
Wavelet transforms have a number of properties that make them attractive
for signal processing. First, if the filters A j , are constructed
to be sparse, then the filter bank operation can be performed very quickly -
often in O(m) time. Second, for many of the signals encountered in prac-
tice, a large percentage of the entries in the wavelet transform are negligible.
Wavelet compression methods can therefore approximate the original set of
samples in C n by storing only the significant coefficients of the wavelet
transform. Impressive compression ratios have been reported for univariate
signals as well as for images [11].
As suggested by the treatment above, all that is needed for performing a
wavelet transform is an appropriate set of analysis and synthesis filters A j ,
To see how to construct these filters, we associate with
each signal C n a function f n (u) with u 2 [0; 1] given by
where 8 n (u) is a row matrix of basis functions [OE n
called
scaling functions. In our application, for example, the scaling functions are
the endpoint-interpolating B-splines basis functions, in which case the function
would be an endpoint-interpolating B-spline curve. 2
The scaling functions are required to be refinable; that is, for all j in [1; n]
there must exist a matrix P j such that
In other words, each scaling function at level j 0 1 must be expressible as
a linear combination of "finer" scaling functions at level j. As suggested by
the notation, the refinement matrix in equation (5) turns out to be the same
as the synthesis filter P j .
Next, let V j be the linear space spanned by the set of scaling functions 8 j .
The refinement condition on 8 j implies that these linear spaces are nested:
Choosing an inner product for the basis
functions in V j allows us to define W j as the orthogonal complement
of V j in V j+1 , that is, the space W j whose basis functions 9
are such that 8 j and 9 j together form a basis
for V j+1 and every / j
i (u) is orthogonal to every OE j
i (u) under the chosen
inner product. The basis functions /
i (u) are called wavelets.
We can now construct the synthesis filter Q j as the matrix that satisfies
Equations (5) and (6) can be expressed as a single equation by concatenating
the matrices together:8 j01 9 j01= 8
Finally, the analysis filters A j and B j are formed by the matrices satisfying
the inverse relation:8 j01 9 j01 3
Note
are both square matrices. Thus,
from which it is easy to prove a number of useful identities:
where 0 and 1 are the matrix of zeros and the identity matrix, respectively.
2 For simplicity of notation, we often omit the explicit dependence on u when writing
f n and 8 n .
2.2 Multiresolution endpoint-interpolating B-splines
In our application, we build a multiresolution analysis for B-spline curves.
In this paper, we restrict our attention to the common case of cubic B-splines
defined on a knot sequence that is uniformly spaced everywhere except at
its ends, where its knots have multiplicity 4. Such B-splines are commonly
referred to as endpoint-interpolating cubic B-splines. These curves are discussed
in detail in many texts on computer-aided design [4, 12, 16].
The multiresolution framework described in Section 2.1 is very general. To
construct our multiresolution curves from endpoint-interpolating cubic B-
splines, we need to make several choices, as enumerated below:
1. Choose the scaling functions 8 j (u) for all j in [0; n].
This choice determines the synthesis filters P j . For each level j, we
would like a basis for the endpoint-interpolating cubic B-spline curves
with segments. The basis functions for these curves are the
endpoint-interpolating cubic B-splines, which are refinable, as
required by equation (5).
2. Select an inner product for any two functions f and g in V j .
This choice determines the orthogonal complement spaces W j . We use
the standard form hf
R
f(u)g(u)du.
3. Select a set of wavelets 9 j (u) that span W j .
This choice determines the synthesis filters Q j . Together, the synthesis
filters determine the analysis filters A j and B j by
equation (9). We use the set of 2 j minimally-supported functions that
span W j .


Appendix

A contains more details on the specific wavelets we use and their
derivation. A similar construction has also been independently proposed
by Chui and Quak [9]. Note that multiresolution constructions can be built
for other types of splines as well, such as uniform B-splines [8], and non-uniform
B-splines with arbitrary knot sequences [21]. A recent construction
applicable to subdivision surfaces is discussed by Lounsbery et al. [19].
Note that becauseboth the scaling functionsand wavelets in our construction
have compact support, the synthesis filters P j and Q j have a banded struc-
ture, allowing reconstruction in O(m) time. However, a potential weakness
of our construction is that the analysis filters A j and B j are dense, which
wouldseem to imply an O(m 2 )-time decomposition algorithm. Fortunately,
there is a clever trick, due to Quak and Weyrich [25], for performing the
decomposition in linear time. The implementation of their algorithm is described
in Appendix B.
Smoothing
In this section, we address the following problem: Given a curve with m
points C, construct a best least-squares-error approximating curve
with m. Here, we will assume that both
curves are endpoint-interpolating uniform B-spline curves.
The multiresolution analysis framework allows this problem to be solved
trivially, for certain values of m and m 0 . Assume for the moment that
nonnegative integers j. Then the
control points C 0 of the approximating curve are given by
In other words, we simply run the decomposition algorithm, as described by
equation (1), until a curve with just m 0 control points is reached. Note that
this process can be performed at interactive speeds for hundreds of control
points using the linear-time algorithm described in Appendix B.
One notable aspect of the multiresolution curve representation is its discrete
nature. Thus, in our application it is easy to construct approximating curves
with 4, 5, 7, 11, or any 2 j points efficiently, for any integer
level j. However, there is no obvious way to quickly construct curves that
have "levels" of smoothness in between.
The best solution we have found is to define a fractional-level curve f j+t (u)
for some 0 - t - 1 in terms of a linear interpolation between its two nearest
integer-level curves f j (u) and f j+1 (u), as follows:
These fractional-level curves allow for continuous levels of smoothing. In
our application a user can move a control slider and see the curve transform
continuously from its smoothest (4 control point) form, up to its finest (m
control point) version. Some fractional-level curves are shown in Figure 2.

Figure

2: Smoothinga curve continuously. From left to right: the original curve
at level 8.0, and smoother versions at levels 5.4 and 3.1.
Editing
Suppose we have a curve C n and all of its low-resolution and detail parts
Multiresolution analysis allows for
two very different kinds of curve editing. If we modify some low-resolution
version C j and then add back in the detail D
have modified the overall sweep of the curve (Figure 3). On the other hand,
if we modify the set of detail functions D leave
the low-resolution versions C intact, we will have modified the
character of the curve, without affecting its overall sweep (Figure 6). These
two types of editing are explored more fully below.
4.1 Editing the sweep
Editing the sweep of a curve at an integer level of the wavelet transform is
simple. Let C n be the control points of the original curve f n (u), let C j
be a low-resolution version of C n , and let b
C j be an edited version of C j ,
given by b
. The edited version of the highest-resolution
curve b
can be computed through reconstruction:
Note that editing the sweep of the curve at lower levels of smoothing j affects
larger portions of the high-resolution curve f n (u). At the lowest level,
the entire curve is affected; at the highest level, when
only the narrow portion influenced by one original control point is affected.
The kind of flexibility that this multiresolution editing allows is suggested
in

Figures

and 4.
In addition to editing at integer levels of resolution, it is natural to ascribe
meaning to editing at fractional levels as well. We would like the portion of
the curve affected when editing at fractional level to interpolate the
portions affected at levels j and j + 1. Thus, as t increases from 0 to 1, the
portion affected should gradually narrow down from that of level j to that
of level demonstrated in the lower part of Figure 4.
Consider a fractional-level curve f j+t (u) given by equation (11). Let C j+t
be the set of control points associated with this curve; that is,
We can obtain an expression for C j+t by equating the right-hand sides of
equations (11) and (12), and then applying equations (5) and (3):
Suppose now that one of the control points c j+t
i is modified by the user.
In order to allow the portion of the curve affected to depend on t in the
manner described above, the system will have to automatically move some
of the nearby control points when c j+t
i is modified. The distance that each
of these control points is moved is inversely proportional to t: for example,
(a) (b) (c) (d)

Figure

3: Changingthe overall sweep of a curve without affecting its character.
Given the original curve (a), the system extracts the overall sweep (b). If the
user modifies the sweep (c), the system can reapply the detail (d).24

Figure

4: The middle of the dark curve is pulled. Upper: Editing at integer
levels 1, 2, 3, and 4. Lower: Editing at fractional levels between 2.0 and 3.0.
when t is near 0, the control points in C j+t are moved in conjunction so
that the overall effect approaches that of editing a single control point at
level the nearby control points are not moved at all, since
the modified curve should correspond to moving just a single control point
at level j + 1.
Let 1C j+t be a vector describing how each control point of the fractional-
level curve is modified: the i-th entry of 1C j+t is the user's change to the
i-th control point; the other entries reflect the computed movements of the
other control points. Rather than solving for 1C j+t explicitly, our approach
will be to break this vector into two components, a vector 1C j of changes
to the control points at level j, and a vector 1D j of changes to the wavelet
coefficients at level j:
Next, define 1 '
C j+t to be the user's change to the control points at level
t, that is, a vector whose i-th entry is 1c j+t
i and whose other entries
are 0. Define also a new vector 1 '
C j as a change to control points at level j
necessary to make the modified control point c j+t
i move to its new position.
We choose the vector that is 0 everywhere, except for one or two entries,
dependingon the index i of the modified control point. By examiningthe i-th
row of the refinement matrix P j+1 , we can determine whether the modified
control point is maximally influenced by either one control point c j+1
k or
two control points c j+1
k and c j+1
k+1 at level j + 1. In the former case, we
set 1'c j
k to be 1c j+t
i;k . In the latter case, we set 1'c j
k and 1'c j
k+1 to be
1c j+t
i;k .
Note that applying either change alone, 1 '
C j+t or 1 '
would cause the selected
control point to move to its new position; however, the latter change
would cause a larger portion of the curve to move. In order to have a
"breadth" of change that gradually decreasesas t goes from 0 to 1, we can interpolate
between these two vectors, using some interpolation function g(t):
Thus, 1C j+t will still move the selected control point to its new position,
and it will also now control the "breadth" of change as a function of t.
Finally, equatingthe right-hand sides of equations(13) and (14), multiplying
with either A j+1 or B j+1 , and employing the identities (10) yields the two
expressions we need:
We now have the choice of any function g(t) that allows 1D j to increase
monotonically from 0 to 1. The function g(t):=t 2 is an obvious choice that
we have found to work well in practice.
The changes to the high-resolution control points are then reconstructed using
a straightforward application of equation (3):
The fractional-level editing defined here works quite well in practice. Varying
the editing level continuouslygivesa smoothand intuitive kind of change
in the region of the curve affected, as suggested by Figure 4. Because the
algorithmic complexity is just O(m), the update is easily performed at interactive
rates, even for curves with hundreds of control points.
4.1.1 Editing with direct manipulation
The fractional-level editing described above can be easily extended to accommodate
direct manipulation, in which the user tugs on the smoothed
curve directly rather than on its defining control points [3, 13, 15, 18]. To
use direct manipulation when editing at level j t, we make use of the
pseudo-inverse of the scaling functions at levels j and j + 1.
More precisely, suppose the user drags a point of the curve f j+t (u 0 ) to a
new position f j+t We can compute the least-squares change to
the control points 1 '
C j+t at levels j and using the pseudo-inverses
These two equations should be interpreted as applying to each dimension x
and y separately. That is, ffi should be a scalar (say, the change in x), and the
left-hand side and the pseudo-inverses should both be column-matrices of
scalars. The modified control points of the highest-resolution curve can then
be computed in the same fashion outlined for control-point manipulation, by
applying equations (15) and (16).
Note that the first step of the construction, equation (17), can be computed
in constant time, since for cubic B-splines at most four of the entries of each
pseudo-inverse are non-zero. The issue of finding the parameter value u 0 at
which the curve passes closest to the selection point is a well-studied problem
in root-finding, which can be handled in a number of ways [27]. In our
implementation, we scan-convert the curve once to find its parameter value
at every illuminated pixel. This approach is easy to implement, and appears
to provide a good trade-off between speed and accuracy for an interactive
system.
For some applications, it maybemore intuitive to drag on the high-resolution
curve directly, rather than on the smoothed version of the curve. In this case,
even when the curve's display resolution is at its highest level, it may still
be useful to be able to tug on the curve at a lower editing resolution. In this
way, varying levels of detail on the curve can be manipulated by dragging a
single point: as the editing resolution is lowered, more and more of the curve
is affected. This type of control can be supported quite easily by setting ffi to
be the change in the high-resolution curve at the dragged point f n (u 0 ), and
using the same equations (17) above.
4.1.2 Editing a desired portion of the curve
One difficulty with curve manipulation methods is that their effect often
depends on the parameterization of the curve, which does not necessarily
correspond to the curve's geometric embedding in an intuitive fashion. The
manipulation that we have described so far suffers from this same difficulty:
dragging at a particular (possibly fractional) level different
points along the curve will not necessarily affect constant-length portions of
the curve. However, we can use the multiresolution editing control to compensate
for this defect in direct manipulation, as follows (Figure 5).
Let h be a parameter, specified by the user, that describes the desired length
of the editable portion of the curve. The parameter h can be specified using
any type of physical units, such as screen pixels, inches, or percentage of
(a) Non-uniform pararameterization.
(b) On left, change is narrow.
(c) Near middle, change is broad.
(d) Equal-breadth changes.

Figure

5: Curve (a) has a parameterization that is non-uniform with respect to
its length. Direct manipulation on the left part of the curve (b) affects a much
smaller fraction of the curve than does direct manipulation at the same level
in the middle (c). The last figure (d) shows that a specified fraction of the curve
can be edited, with the system determining the appropriate editing level.
the overall curve length. The system computes an appropriate editing level '
that will affect a portion of the curve of about h units in length, centered at
the point f n being dragged.
We estimate ' as follows. For each integer-level editing resolution j, let
the length of f n (u) affected by editing the curve at the
point easily estimated by scan-converting the
curve f n (u) to determine the approximate lengths of its polynomial seg-
ments, and then summing over the lengths of the segments affected when
editing the curve at level j and parameter position u 0 . Next, define j0
and j+ to be, respectively, the smallest and largest values of j for which
To choose the editing level ', we use linear
interpolation between these two bounding levels j0 and j+ :
Finally, by representing ' in terms of an integer level j and fractional off-set
t, we can again apply equation (17), followed by equations (15) and (16),
as before. Though in general this construction does not precisely cover the
desired portion h, in practice it yields an intuitive and meaningful control.

Figure

5 demonstrates this type of editing for a curve with an extremely
non-uniform geometric embedding.
4.2 Editing the character of the curve
Another form of editing that is naturally supported by multiresolution curves
is one of editing the character of a curve, without affecting its overall sweep.
Let C n be the control points of a curve, and let C
D n01 denote the components of its multiresolution decomposition. Editing
the character of the curve is simply a matter of replacing the existing set
of detail functions D some new set b
reconstructing.
With this approach, we have been able to develop a "curve character library"
that contains different detail functions, which can be interchangeablyapplied
to any set of curves. The detail functions in the library have been extracted
from hand-drawn strokes; other (for example, procedural) methods of generating
detail functions are also possible. Figure 6 demonstrates how the character
of curves in an illustration can be modified with the same (or different)
detail styles. The interactive illustration system used to create this figure is
described in a separate paper [26].

Figure

Changing the character of a curve without affecting its sweep.
4.3 Orientation of detail
A parametric curve in two dimensions is most naturally represented as two
separate functions, one in x and one in y: fy (u)). Thus,
it seems reasonable to represent both the control points C j and detail functions
using matrices with separate columns for x and y. However, encoding
the detail functions in this mannerembeds all of the detail of the curve in
a particular xy-orientation. As demonstrated in Figure 7, this representation
does not always provide the most intuitive control when editing the sweep
of the curve.
Original curve. Fixed xy-orientation. Detail relative to the tangent.

Figure

7: Editing the sweep of a curve using a fixed xy-orientation of detail
versus orientation relative to the tangent of the curve.
As an alternative, we employ a method similar to that of Forsey and Bartels
[13] for representing detail with respect to the tangent and normal to
the curve at a coarser level. Specifically, for computing the reference frame
for orienting a detail coefficient d j
i , we use the tangent and normal of the
curve f j01 (u 0 ) at a parameter position u 0 corresponding to the maximum
value of the wavelet / j
(u). Note that the curve f(u) is no longer a simple
linear combination of the scaling functions 8 0 and wavelets 9
change of coordinates must be performed at each level of reconstruction for
the wavelet coefficients D j . However, this process is linear in the number
of control points, so it does not increase the computational complexity of the
algorithm.
We have experimented with both normalized and unnormalized versions of
the reference frame; the two alternative versions yield different but equally
reasonable behavior. Figure 6 uses the unnormalized tangents whereas the
rest of the figures in this paper use normalized tangents.
5 Scan conversion and curve compression
Using "curve character libraries" and other multiresolution editing features,
it is easy to create very complex curves with hundreds or potentially thousands
of control points. In many cases (such as in this paper), these curvesare
printed in a very small form. Conventional scan conversionmethods that use
all the complexity of these curves are wasteful, both in terms of the network
traffic to send such large files to the printer, and in terms of the processing
time required by the printer to render curves of many control points within
a few square pixels. We therefore explore a form of curve compression that
is suitable for the purposes of scan conversion. The algorithm requires an
approximate curve to have a guaranteed error tolerance, in terms of printer
pixels, from the original curve. However, it does not require any particular
continuity constraints, as are usually required in data-fitting applications.
As discussed in Section 3, the simple removal of wavelet coefficients can
be used to achieve a least-squares, or L 2 , error metric between an original
curve and its approximate versions. However, for scan conversion, an L 2
error metric is not very useful for measuring the degree of approximation: an
approximate curve e
f(u) can be arbitrarily far from an original curve f n (u)
and still achieve a particular L 2 error bound, as long as it deviates from the
original over a small enough segment. In order to scan convert a curve to
some guaranteed precision-measured, say, in terms of maximum deviation
in printer pixels-we need to use an L 1 norm on the error. There are many
ways to achievesuch a bound. Themethoddescribed here is a simple and fast
one, althoughmethods with higher compression ratios are certainly possible.
a segment of the cubic B-spline curve
defined by the four control points c j
i+3 . Note that each segment
i corresponds to exactly two segments s j+1
2i and s j+1
2i+1 at level j +1.

Figure

8: Scan-converting a curve within a guaranteed
maximum error tolerance. From left to right, the figures
used 5%, 21%, 46%, and 78% of the possible number of
B-ezier segments. Error is less than 1/400 inch.

Figure

9: Same curves as above, but drawn at constant size.
Our objective is to build a new approximatingcurve e
f(u) for f(u)by choosing
different segments at different levels such that jj e
less than some user-specified ffl for all values of u.
Assume, for the moment, that we have some function
returns a bound on the L 1 error incurred from using the segment s j
i of
some approximate curve f j (u) in place of the original segments of f n (u)
to which it corresponds. We can scan-convert a curve to within any error
tolerance ffl by passing to the recursive routine DrawSegment the single segment
0 corresponding to the lowest-level curve f 0 (u). This routine recursively
dividesthe segment to varying levels so that the collection of segments
it produces approximates the curve to within ffl.
procedure DrawSegment(s j
if
Output segment s j
i as a portion of e
else
procedure
To construct the ErrBound routine, let M j be the B-spline-to-B-ezier-basis
conversion matrix [4] for curves with be a
column vector with entries e j
defined by
The vector E j provides a measure of the distance that the B-ezier control
points migrate when reconstructing the more detailed curve at level j from
the approximate curve at level j 0 1. Since B-ezier curves are contained
within the convex hull of their control points, the magnitudes of the entries
of conservative bounds on approximations to the curve due to
truncating wavelet coefficients.
A bound ffi j
i on the L 1 error incurred by replacing segment s j
i with its approximation
at level j 0 1 is given by
The ErrBound routine can then be described recursively as follows:
procedure
return 0
else
return maxfErrBound(s j+1
procedure
An efficient implementation of the ErrBound routine would use dynamic
programming or an iterative (rather than recursive) procedure to avoid re-computing
error bounds. In practice, the routine is fast enough in its recursive
form that we have not found this optimization to be necessary, at least
for scan converting curves with hundreds of control points.
The approximate curve e f(u) is described by a set of B-ezier segments, which
we use to generate a PostScript file [1]. Note that the scan-conversion algo-
rithm, as described, produces approximate curves e
f(u) that are not even C 0
continuous where two segments of different levels abut. Since we are only
concerned with the absolute error in the final set of pixels produced, relaxing
the continuity of the original curve is reasonable for scan conversion. We
can achieve C 0 continuity, however, without increasing the prescribed error
tolerance, by simply averaging together the end control points for adjacent
B-ezier segments as a post-process. We have found that these C 0 curves look
slightly better than the discontinuous curves; they also have a more compact
representation in PostScript. Figures 8 and 9 demonstratecompressionof the
same curve rendered at different sizes.
6 Extensions and future work
This paper describes a multiresolution representation for endpoint-interpo-
lating B-spline curves, and shows how this single representation supports a
variety of display and editing operations in a simple and efficient manner.
We believe that the operations described are very general and can be readily
extended to other types of objects described by a multiresolution analysis.
There are many directions for future research, including:
Handling discontinuities. An important extension is to generalize the multiresolution
curve representation and editing operations to respect discontinuities
of various orders that have been intentionally placed into a curve
by the designer. This extension would allow the techniques to be applied
more readily to font design, among other applications. One approach is to
try using the multiresolution analysis defined on non-uniform B-splines by
D-hlen and Lyche [10].
Sparse representations. Our algorithms have so far used only complete
wavelet decompositions of the curve's original control points. However, in
order to support curve editing at an arbitrarily high resolution, it would be
convenient to have a mechanism in place for extending the wavelet representation
to a higher level of detail in certain higher-resolution portions of
the curve than in others. One such sparse representation might use pruned
binary trees to keep track of the various wavelet coefficients at different levels
of refinement, in a manner very similar to the one used by Berman et al.
for representing multiresolution images [5].
Textured strokes. For illustrations, it is useful to associate other properties
with curves, such as color, thickness, texture, and transparency, as demonstrated
by Hsu and Lee [17]. These quantities may be considered extra dimensions
in the data associated with each control point. Much of the machinery
for multiresolution editing should be applicable to such curves. As a
preliminary test of this idea, we have extended our curve editor with a thickness
dimension. The thickness along the curve is governed by the thick-
Figure

10: Two curves of varying thickness.
nesses defined at the control points. It is possible to modify this parameter
at any level of resolution, just as one edits the position of the curve.

Figure

shows curves with varying thickness. Ultimately, we would like
to combine stroke editing with multiresolution image editing [5], perhaps
providing a unified framework for object-oriented ("MacDraw-like") and
image-oriented ("MacPaint-like") interactive design programs.
Surfaces. Another obvious extension of these techniques is to surfaces. As
a test of multiresolution surface editing, we built a surface editor that allows
a user to modify a bicubic tensor-product B-spline surface [4, 12, 16] at different
levels of detail. Figure 11 shows several manipulations applied to a
surface over 1225 control points modeling a human face. It is worth noting
that tensor-product surfaces are limited in the kinds of shapes they can
model seamlessly. Lounsbery et al. [19] discuss a multiresolution representation
for subdivision surfaces of arbitrary topology. Many of the techniques
described in this paper shouldextend directly to their surfaces as well. In par-
ticular, fractional-level display and editing are applicable in the same way
as for curves and tensor-product surfaces. In addition, the compression technique
for scan-converting curves might also be used for rendering simplified
versions of polyhedra within guaranteed error tolerances.

Figure

Surface manipulation at different levels of detail. From left to right:
original, narrow change, medium change, broad change.

Acknowledgements

We would like to thank Tony DeRose, Ronen Barzel, and Leena-Maija
Reissell for very helpful discussions during the development of these ideas,
and Sean Anderson for implementing the tensor-product B-spline surface
editor.
This work was supported by an NSF National Young Investigator award
(CCR-9357790), by the University of Washington Graduate Research and
Royalty Research Funds (75-1721 and 65-9731), and by industrial gifts from
Adobe, Aldus, and Xerox.



--R

PostScript Language Reference Manual.
Realtime spline curves from interactively sketched data.
A technique for the direct manipulation of spline curves.
An Introduction to Splines for Use in Computer Graphics and Geometric Modeling.
Multiresolution painting and compositing.
Fast wavelet transforms and numerical algorithms I.
Deformable curve and surface finite elements for free-form shape design
An Introduction to Wavelets.
Wavelets on a bounded interval.
Decomposition of splines.
Image compression through wavelet transform coding.
Curves and Surfaces for Computer Aided Geometric Design.
Hierarchical B-spline refinement
Tensor products and hierarchical fitting.
Geometric manipulation of tensor product surfaces.
Fundamentals of Computer Aided Geometric Design.
Skeletal strokes.
Direct manipulation of free-form deformations
Multiresolution surfaces of arbitrary topological type.
Knot removal for parametric B-spline curves and surfaces

A theory for multiresolution signal decomposition: The wavelet representation.

Numerical Recipes.
Decomposition and reconstruction algorithms for spline wavelets on a bounded interval.
Interactive pen-and-ink illustration
An interactive curve design system based on the automatic fitting of hand-sketched curves
Variational surface modeling.
--TR
An introduction to splines for use in computer graphics MYAMPERSANDamp; geometric modeling
Knot removal for parametric B-spline curves and surfaces
A Theory for Multiresolution Signal Decomposition
Real time spline curves from interactively sketched data
Deformable curve and surface finite-elements for free-form shape design
Decomposition of splines
Variational surface modeling
Direct manipulation of free-form deformations
Geometric manipulation of tensor product surfaces
Curves and surfaces for computer aided geometric design (3rd ed.)
An introduction to wavelets
Fundamentals of computer aided geometric design
Multiresolution painting and compositing
Interactive pen-and-ink illustration
Hierarchical B-spline refinement
Curve-fitting with piecewise parametric cubics

--CTR
Joohyung Cho , Kunwoo Lee, Surface fairing preserving continuity with neighboring surfaces based on wavelet transform, Proceedings of the fifth ACM symposium on Solid modeling and applications, p.324-325, June 08-11, 1999, Ann Arbor, Michigan, United States
Andrew Certain , Jovan Popovic , Tony DeRose , Tom Duchamp , David Salesin , Werner Stuetzle, Interactive multiresolution surface viewing, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.91-98, August 1996
Andrew Witkin , Zoran Popovic, Motion warping, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.105-108, September 1995
Georges-Pierre Bonneau , Stefanie Hahmann , Gregory M. Nielson, BLaC-Wavelets: a multiresolution analysis with non-nested spaces, Proceedings of the 7th conference on Visualization '96, p.43-48, October 28-29, 1996, San Francisco, California, United States
David Bargeron , Tomer Moscovich, Reflowing digital ink annotations, Proceedings of the SIGCHI conference on Human factors in computing systems, April 05-10, 2003, Ft. Lauderdale, Florida, USA
Matthias Eck , Tony DeRose , Tom Duchamp , Hugues Hoppe , Michael Lounsbery , Werner Stuetzle, Multiresolution analysis of arbitrary meshes, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.173-182, September 1995
Pak Chung Wong , R. Daniel Bergeron, Authenticity Analysis of Wavelet Approximations in Visualization, Proceedings of the 6th conference on Visualization '95, p.184, October 29-November 03, 1995
Michael P. Salisbury , Sean E. Anderson , Ronen Barzel , David H. Salesin, Interactive pen-and-ink illustration, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, p.101-108, July 1994
Gershon Elber, Multiresolution curve editing with linear constraints, Proceedings of the sixth ACM symposium on Solid modeling and applications, p.109-119, May 2001, Ann Arbor, Michigan, United States
Julien Lenoir , Laurent Grisoni , Philippe Meseure , Yannick Rmion , Christophe Chaillou, Smooth constraints for spline variational modeling, Proceedings of the 2nd international conference on Computer graphics and interactive techniques in Australasia and South East Asia, June 15-18, 2004, Singapore
Yuta Okabe , Suguru Saito , Masayuki Nakajima, Paintbrush rendering of lines using HMMs, Proceedings of the 3rd international conference on Computer graphics and interactive techniques in Australasia and South East Asia, November 29-December 02, 2005, Dunedin, New Zealand
Shigeo Takahashi , Yoshihisa Shinagawa , Tosiyasu L. Kunii, A feature-based approach for smooth surfaces, Proceedings of the fourth ACM symposium on Solid modeling and applications, p.97-110, May 14-16, 1997, Atlanta, Georgia, United States
Giancarlo Amati, A multi-level filtering approach for fairing planar cubic B-spline curves, Computer Aided Geometric Design, v.24 n.1, p.53-66, January, 2007
J. Stollnitz , Tony D. DeRose , David H. Salesin, Wavelets for Computer Graphics: A Primer, Part 2, IEEE Computer Graphics and Applications, v.15 n.4, p.75-85, July 1995
M. Bertram, Biorthogonal loop-subdivision wavelets, Computing, v.72 n.1-2, p.29-39, April 2004
J. Stollnitz , Tony D. DeRose , David H. Salesin, Wavelets for Computer Graphics: A Primer, Part 1, IEEE Computer Graphics and Applications, v.15 n.3, p.76-84, May 1995
Muhammad Sarfraz , Mohammed Ali Siddiqui, Development of a multi-resolution framework for NUBS, Information Sciences: an International Journal, v.163 n.4, p.239-251,
Hans Pedersen , Karan Singh, Organic labyrinths and mazes, Proceedings of the 4th international symposium on Non-photorealistic animation and rendering, June 05-07, 2006, Annecy, France
Michael Gleicher, Motion path editing, Proceedings of the 2001 symposium on Interactive 3D graphics, p.195-202, March 2001
Celine Latulipe , Stephen Mann , Craig S. Kaplan , Charlie L. A. Clarke, symSpline: symmetric two-handed spline manipulation, Proceedings of the SIGCHI conference on Human Factors in computing systems, April 22-27, 2006, Montral, Qubec, Canada
Georges Winkenbach , David H. Salesin, Computer-generated pen-and-ink illustration, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, p.91-100, July 1994
Jehee Lee , Sung Yong Shin, A hierarchical approach to interactive motion editing for human-like figures, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.39-48, July 1999
Steven J. Gortler , Michael F. Cohen, Hierarchical and variational geometric modeling with wavelets, Proceedings of the 1995 symposium on Interactive 3D graphics, p.35-ff., April 09-12, 1995, Monterey, California, United States
Denis Zorin , Peter Schrder , Wim Sweldens, Interactive multiresolution mesh editing, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.259-268, August 1997
Leif Kobbelt , Swen Campagna , Jens Vorsatz , Hans-Peter Seidel, Interactive multi-resolution modeling on arbitrary meshes, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.105-114, July 1998
T. Freeman , Joshua B. Tenenbaum , Egon C. Pasztor, Learning style translation for the lines of a drawing, ACM Transactions on Graphics (TOG), v.22 n.1, p.33-46, January
Aaron Hertzmann , Nuria Oliver , Brian Curless , Steven M. Seitz, Curve analogies, Proceedings of the 13th Eurographics workshop on Rendering, June 26-28, 2002, Pisa, Italy
Gene C.-H. Chuang , C.-C. Jay Kuo, Cartoon Animation and Morphing with Wavelet Curve Descriptor, Multidimensional Systems and Signal Processing, v.8 n.4, p.423-447, Oct. 1997
Sungchan Kim , Kunwoo Lee , Taesik Hong , Mincheol Kim , Moonki Jung , Youngjae Song, An integrated approach to realize multi-resolution of B-rep model, Proceedings of the 2005 ACM symposium on Solid and physical modeling, p.153-162, June 13-15, 2005, Cambridge, Massachusetts
Karan Singh, Interactive curve design using digital French curves, Proceedings of the 1999 symposium on Interactive 3D graphics, p.23-30, April 26-29, 1999, Atlanta, Georgia, United States
Julien Lenoir , Laurent Grisoni , Christophe Chaillou , Philippe Meseure, Adaptive resolution of 1D mechanical B-spline, Proceedings of the 3rd international conference on Computer graphics and interactive techniques in Australasia and South East Asia, November 29-December 02, 2005, Dunedin, New Zealand
Doug DeCarlo , Anthony Santella, Stylization and abstraction of photographs, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
Matt Anderson , Eric McDaniel , Stephen Chenney, Constrained animation of flocks, Proceedings of the ACM SIGGRAPH/Eurographics symposium on Computer animation, July 26-27, 2003, San Diego, California
Martin Bertram, Single-knot wavelets for non-uniform B-splines, Computer Aided Geometric Design, v.22 n.9, p.849-864, December 2005
Stefanie Hahmann , Basile Sauvage , Georges-Pierre Bonneau, Area preserving deformation of multiresolution curves, Computer Aided Geometric Design, v.22 n.4, p.349-367, May 2005
Christopher G. Healey , Laura Tateosian , James T. Enns , Mark Remple, Perceptually based brush strokes for nonphotorealistic visualization, ACM Transactions on Graphics (TOG), v.23 n.1, p.64-96, January 2004
Wei Guofu , Chen Falai, Four-point wavelets and their applications, Journal of Computer Science and Technology, v.17 n.4, p.473-480, July 2002
Leif Kobbelt , Peter Schrder, A multiresolution framework for variational subdivision, ACM Transactions on Graphics (TOG), v.17 n.4, p.209-237, Oct. 1998
Kun Zhou , Jin Huang , John Snyder , Xinguo Liu , Hujun Bao , Baining Guo , Heung-Yeung Shum, Large mesh deformation using the volumetric graph Laplacian, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
Markus H. Gross , Oliver G. Staadt , Roger Gatti, Efficient Triangular Surface Approximations Using Wavelets and Quadtree Data Structures, IEEE Transactions on Visualization and Computer Graphics, v.2 n.2, p.130-143, June 1996
Hans J. Wolters, Geometric modeling applications in rational drug design: a survey, Computer Aided Geometric Design, v.23 n.6, p.482-494, August 2006
Michael Lounsbery , Tony D. DeRose , Joe Warren, Multiresolution analysis for surfaces of arbitrary topological type, ACM Transactions on Graphics (TOG), v.16 n.1, p.34-73, Jan. 1997
Frdo Durand, An invitation to discuss computer depiction, Proceedings of the 2nd international symposium on Non-photorealistic animation and rendering, June 03-05, 2002, Annecy, France
curve fitting;curve smoothing;direct manipulation;curve compression;scan conversion;wavelets;curve editing