T-spline Simplification and Local Refinement
ThomasW. Sederberg, David L. Cardon
G. Thomas Finnigan, Nicholas S. North
Brigham Young University
Jianmin Zheng
Nanyang Technological University
Tom Lyche
Oslo University
Abstract
A typical NURBS surface model has a large percentage of superfluous
control points that significantly interfere with the design process.
This paper presents an algorithm for eliminating such superfluous
control points, producing a T-spline. The algorithm can
remove substantially more control points than competing methods
such as B-spline wavelet decomposition. The paper also presents
a new T-spline local refinement algorithm and answers two fundamental
open questions on T-spline theory.
CR Categories: I.3.5 [Computer Graphics]: Computational Geometry
and Object Modeling—curve, surface, solid and object representations;
Keywords: NURBS surfaces, T-splines, subdivision surfaces, local
refinement, knot removal
1 Introduction
A serious weakness with NURBS models is that NURBS control
points must lie topologically in a rectangular grid. This means that
typically, a large number of NURBS control points serve no purpose
other than to satisfy topological constraints. They carry no
significant geometric information. In Figure 1.a, all the red NURBS
control points are, in this sense, superfluous.
Figure 1: Head modeled (a) as a NURBS with 4712 control points
and (b) as a T-spline with 1109 control points. The red NURBS
control points are superfluous.
T-splines [Sederberg et al. 2003] are a generalization of NURBS
surfaces that are capable of significantly reducing the number of
superfluous control points. Figure 1.b shows a T-spline control grid
which was obtained by eliminating the superfluous control points
from the NURBS model. The main difference between a T-mesh
(i.e., a T-spline control mesh) and a NURBS control mesh is that Tsplines
allow a row of control points to terminate. The final control
point in a partial row is called a T-junction. The T-junctions are
shown in purple in Figure 1.b.
Figure 2: Car door modeled as a NURBS and as a T-spline.
Figure 2 shows another example in which the superfluous control
points in a NURBS are removed to create a T-spline. The T-spline
model is geometrically equivalent to the NURBS model, yet has
only 1=3 as many control points.
Figure 3: NURBS head model, converted to a T-spline.
Superfluous control points are a serious nuisance for designers,
not merely because they require the designer to deal with more data,
but also because they can introduce unwanted ripples in the surface
as can be seen by comparing the forehead in the NURBS model in
Figure 3.a with that of the T-spline model in Figure 3.b. Designers
can waste dozens of hours on models such as this in tweaking the
NURBS control points while attempting to remove unwanted ripples.
Figure 1.a shows a NURBS head model. Figure 1 shows the
respective NURBS and T-spline control meshes for the surfaces in
Figure 3. Over 3=4 of the 4712 NURBS control points are superfluous
and do not appear in the T-spline control mesh.
This paper presents an algorithm for converting a NURBS model
into a T-spline model. The process eliminates most superfluous
control points. The algorithm was used to convert the NURBS
model in Figure 1.a into the T-spline model in Figure 1.b. Conversion
from NURBS to T-spline can be lossless (such as in the case
of CAD objects like the car door) or an approximation error can be
specified. An error threshold of 1% was used in the example in Figure
1, and the only observable difference between the two models
is that the conversion to T-splines removed the unwanted ripples in
the forehead. Thus, a problem for which designers can waste hours
of time is resolved in the split second that it takes to convert from
NURBS to T-spline using the algorithm presented in this paper.
We refer to this conversion process as T-spline simplification.
Our algorithm makes heavy use of the operation of T-spline local
refinement, introduced in [Sederberg et al. 2003]. However, [Sederberg
et al. 2003] left this operation on uncertain footing. It was
shown that in certain situations, a control point can be inserted into
a particular location in a T-mesh topology only if some additional
control points are also added. Furthermore, the number of additional
control points can be quite large using the local refinement
algorithm in [Sederberg et al. 2003]. This problem is illustrated in
Figure 4.a, which shows a T-mesh into which we wish to insert control
point P. The initial control points are the red, unlabeled ones.
The algorithm in [Sederberg et al. 2003] requires the additional insertion
of all eight control points labeled V. [Sederberg et al. 2003]
concluded with an open question : Do there exist T-spline topologies
into which it is impossible to insert a requested control point?
This paper answers that question by presenting a new local refinement
algorithm with which it is provably always possible to insert
a requested control point. Furthermore, the number of additional
control points needed is reduced significantly. The algorithm
is illustrated in Figure 4.b, where we insert P while only performing
a single additional insertion V. This new local refinement algorithm
plays a key role in the T-spline simplification algorithm
presented in this paper.
Figure 4: Local refinement using the old algorithm and the new
algorithm.
The paper is organized as follows. Section 2 surveys pertinent
literature on B-spline knot removal and insertion. Section 3
presents a brief review of T-splines. Section 4 provides equations
for refining T-spline blending functions, introduces the notion of
T-spline spaces, and presents the improved algorithm for local refinement
(knot insertion) into a T-spline. This section also answers
a second open question by presenting necessary and sufficient conditions
for a T-spline to be standard (i.e., a T-spline whose blending
functions form a partition of unity), and introduces semi-standard Tsplines,
a surprising type of rational T-spline in which some control
points have weights 6= 1, yet the T-spline is equivalent to a polynomial
B-spline surface (all weights = 1). Section 5 presents the
algorithm for local knot removal in a T-spline (of which B-spline
is a special case). Section 6 concludes with some examples and
discussion.
We restrict our discussion to the case of degree three B-splines
and T-splines. However, adapting these algorithms to T-NURCCs
(the arbitrary-topology version of T-splines) is straightforward.
2 Prior Work
Local refinement of NURBS curves and surfaces is accomplished
through knot insertion, an exact process that does not alter the shape
of the curve or surface. Several algorithms exist for knot insertion.
The Oslo algorithm [Cohen et al. 1980] computes so-called discrete
B-splines to define the B-spline basis transformation from a refined
space of splines to a subspace. Boehm’s algorithm [Boehm 1980]
works directly with the B-spline coefficients. Mathematical insights
like the blossoming principle [Seidel 1988; Goldman and Lyche
1993] for knot insertion have also been developed.
Knot insertion is a fundamental algorithm that can be used both
as a mathematical tool for understanding and analyzing B-splines
and as a practical tool for manipulating and rendering B-spline
curves and surfaces [Goldman and Lyche 1993]. Applications of
knot insertion include providing tools for straightforward evaluation
of points on curves/surfaces, tessellation, rendering, and other
geometric processing algorithms [Lane and Riesenfeld 1980]; performing
bases conversion such as converting a B-spline curve to a
B´ezier [Boehm 1981]; adding extra degrees of freedom for shape
modification or editing [Forsey and Bartels 1988].
Knot insertion works well to locally refine a B-spline curve: inserting
one knot involves updating only a few control points in a
local region. However, for a tensor-product B-spline surface, true
local refinement is not possible because the insertion of one knot
into either of the surface knot vectors causes an entire row or column
of control points to be inserted [Lyche et al. 1985]. This problem
has been addressed by hierarchical B-splines for local refinement
and multiresolution editing [Forsey and Bartels 1988; Forsey
and Wong 1998; Gonzalez-Ochoa and Peters 1999]. [Kraft 1997]
presents a multilevel spline space that is a linear span of tensor
product B-splines on different, hierarchically ordered grid levels.
A selection mechanism for B-splines is provided, which guarantees
linear independence to form a basis. [Weller and Hagen 1995] generalizes
tensor-product B-spline surfaces by allowing the domain
partition with knot segments and knot rays. The approach is restricted
to so-called semi-regular bases. CHARMS [Grinspun et al.
2002] provides a method to produce adaptive refinements for 3D
finite elements. The basic idea is to refine the basis functions, not
elements. T-splines [Sederberg et al. 2003], the surface formulation
upon which this paper is based, permit local refinement.
Knot removal is the inverse of knot insertion [Handscomb 1987].
A primary motivation of knot removal is data reduction [Lyche
1993]. The problem is to minimize the number of knots subject to
an error tolerance. Another application of knot removal is shape
fairing [Farin et al. 1987]. The continuity order can be increased by
removing knots. Like knot insertion, knot removal can also be used
to perform bases conversion, multiresolution analysis, and wavelet
decomposition [Daehlen and Lyche 1992].
While knot insertion for a B-spline curve is always possible without
error, deleting a knot without changing the curve is possible
only when the two adjacent curve segments are Cl continuous with
l > n??m where n is the degree of the curve and m is the multiplicity
of the knot. Therefore knot removal usually involves approximation.
In practice, for a B-spline curve, if a control point almost
satisfies a knot removal condition, the inverse Oslo algorithm can
be performed to delete the knot [Lyche and Mørken 1987] and the
resulting curve will not deviate from the original curve very much.
[Lyche and Mørken 1987] also generalizes the algorithm to surfaces.
For a B-spline surface, when all control points of a row or
column nearly satisfy the knot removal condition, a knot can be
deleted. However, it does not often happen that a whole row or column
of control points satisfies the condition simultaneously. The
hierarchical or multiresolution approach [Daehlen and Lyche 1992]
can avoid this problem.
The T-spline simplification algorithm in this paper most closely
follows the idea of spline wavelet decomposition (see [Lyche
et al. 2001] and its references) and thresholding (see, for example,
[Schr¨oder and Sweldens 1995]). For spline wavelet decomposition
on the sphere using tensor product B-splines see [Lyche and
Schumaker 2000].
3 T-splines
This section gives a brief review of T-splines as presented in [Sederberg
et al. 2003]. A control grid for a T-spline surface is called a
T-mesh. If a T-mesh forms a rectangular grid, the T-spline degenerates
to a B-spline surface.
Knot information for T-splines is expressed using knot intervals,
non-negative numbers that indicate the difference between two
knots. A knot interval is assigned to each edge in the T-mesh. Figure
5 shows the pre-image of a portion of a T-mesh in (s;t) parameter
space; the di and ei denote the knot intervals. Knot intervals
are constrained by the relationship that the sum of all knot intervals
along one side of any face must equal the sum of the knot intervals
on the opposing side. For example, in Figure 5 on face F1,
e3 +e4 = e6 +e7, and on face F2, d6 +d7 = d9.
It is possible to infer a local knot coordinate system from the
knot intervals on a T-mesh. To impose a knot coordinate system,
we first choose a control point whose pre-image will serve as the
origin for the parameter domain (s;t) = (0;0). For the example in
Figure 5, we designate (s0;t0) to be the knot origin.
Once a knot origin is chosen, we can assign an s knot value to
each vertical edge in the T-mesh topology, and a t knot value to each
horizontal edge in the T-mesh topology. In Figure 5, those knot
values are labeled si and ti. Based on our choice of knot origin, we
have s0 = t0 = 0, s1 = d1, s2 = d1 +d2, s3 = d1 +d2 +d3, t1 = e1,
t2 = e1 +e2, and so forth. Likewise, each control point has knot
coordinates. For example, the knot coordinates for P0 are (0;0), for
P1 are (s2;t2+e6), for P2 are (s5;t2), and for P3 are (s5;t2 +e6).
Figure 5: Pre-image of a T-mesh.
One additional rule for T-meshes explained in [Sederberg et al.
2003] is that if a T-junction on one edge of a face can legally be
connected to a T-junction on an opposing edge of the face (thereby
splitting the face into two faces), that edge must be included in the
T-mesh. Legal means that the sum of knot vectors on opposing
sides of each face must always be equal. Thus, a horizontal line
would need to split face F1 if and only if e3 = e6 and therefore also
e4 = e7.
The knot coordinate system is used in writing an explicit formula
for a T-spline surface:
P(s;t) = (x(s;t);y(s;t); z(s;t);w(s;t)) =
nå
i=1
PiBi(s;t) (1)
where Pi = (xi;yi; zi;wi) are control points in P4 whose weights are
wi; and whose Cartesian coordinates are 1
wi
(xi;yi; zi). Likewise, the
Cartesian coordinates of points on the surface are given by
åni
=1(xi;yi; zi)Bi(s;t)
åni
=1wiBi(s;t)
: (2)
The blending functions in (1) are Bi(s;t) and are given by
Bi(s;t) = N[si0; si1; si2; si3; si4](s)N[ti0;ti1;ti2;ti3;ti4](t) (3)
where N[si0; si1; si2; si3; si4](s) is the cubic B-spline basis function
associated with the knot vector
si = [si0; si1; si2; si3; si4] (4)
and N[ti0;ti1;ti2;ti3;ti4](t) is associated with the knot vector
ti = [ti0;ti1;ti2;ti3;ti4]: (5)
as illustrated in Figure 6. The designer is free to adjust the weights
Figure 6: Knot lines for blending function Bi(s;t).
wi to obtain additional shape control, as in rational B-splines. As
we shall see in Section 4, weights also play an important role in our
new local refinement algorithm.
The T-spline equation is very similar to the equation for a tensorproduct
rational B-spline surface. The difference between the Tspline
equation and a B-spline equation is in how the knot vectors
si and ti are determined for each blending function Bi(s;t). Knot
vectors si (4) and ti (5) are inferred from the T-mesh neighborhood
of Pi. Since we will refer to the rule whereby the knot vectors are
inferred, we formally state it as
Rule 1. Knot vectors si (4) and ti (5) for the blending function of
Pi are determined as follows. (si2;ti2) are the knot coordinates of
Pi. Consider a ray in parameter space R(a) = (si2 +a;ti2). Then
si3 and si4 are the s coordinates of the first two s-edges intersected
by the ray (not including the initial (si2;ti2)). By s-edge, we mean a
vertical line segment of constant s. The other knots in si and ti are
found in like manner.
We illustrate Rule 1 by a few examples. The knot vectors for P1
in Figure 5 are s1 = [s0; s1; s2; s3; s4] and t1 = [t1;t2;t2 +e6;t4;t5].
For P2, s2 = [s3; s4; s5; s6; s7] and t2 = [t0;t1;t2;t2 +e6;t4]. For P3,
s3 = [s3; s4; s5; s7; s8] and t3 = [t1;t2;t2 +e6;t4;t5]. Once these knot
vectors are determined for each blending function, the T-spline is
defined using (1) and (3).
4 T-spline Local Refinement
This section presents our new algorithm for local refinement of Tsplines.
Blending function refinement plays an important role in
this algorithm, and is reviewed in Section 4.1. The notion of Tspline
spaces is introduced in Section 4.2. This concept is used in
the local refinement algorithm in Section 4.3 and in the T-spline
simplification algorithm in Section 5.
4.1 Blending Function Refinement
If s = [s0; s1; s2; s3; s4] is a knot vector and ˜s is a knot vector with
m knots with s a subsequence of ˜s, then N[s0; s1; s2; s3; s4](s) can be
written as a linear combination of the m??4 B-spline basis functions
defined over the substrings of length 5 in ˜s.
We now present all basis function refinement equations for the
case m = 6. Equations for m > 6 can be found by repeated application
of these equations.
If s = [s0; s1; s2; s3; s4], N(s) = N[s0; s1; s2; s3; s4](s), and ˜s =
[s0;k; s1; s2; s3; s4] then
N(s) = c0N[s0;k; s1; s2; s3](s)+d0N[k; s1; s2; s3; s4](s) (6)
where c0 = k??s0
s3??s0
and d0 = 1. If ˜s = [s0; s1;k; s2; s3; s4],
N(s) = c1N[s0; s1;k; s2; s3](s)+d1N[s1;k; s2; s3; s4](s) (7)
where c1 = k??s0
s3??s0
and d1 = s4??k
s4??s1
. If ˜s = [s0; s1; s2;k; s3; s4],
N(s) = c2N[s0; s1; s2;k; s3](s)+d2N[s1; s2;k; s3; s4](s) (8)
where c2 = k??s0
s3??s0
and d2 = s4??k
s4??s1
. If ˜s = [s0; s1; s2; s3;k; s4],
N(s) = c3N[s0; s1; s2; s3;k](s)+d3N[s1; s2; s3;k; s4](s) (9)
where c3 = 1 and d3 = s4??k
s4??s1
. If k s4, N(s) does not
change.
A T-spline function B(s;t) can undergo knot insertion in either s
or t, thereby splitting it into two scaled blending functions that sum
to the initial one. Further insertion into these resultant scaled blending
functions yields a set of scaled blending functions that sum to
the original. For example, Figure 7.a shows the knot vectors for a
T-spline blending function B1, and Figure 7.b shows a refinement
of the knot vectors in Figure 7.a. By appropriate application of
(6)—(9), we can obtain
B1(s;t) = c11
˜B
1(s;t)+c21
˜B
2(s;t)+c31 ˜B3(s;t)+c41
˜B
4(s;t): (10)
4.2 T-spline Spaces
We define a T-spline space to be the set of all T-splines that have the
same T-mesh topology, knot intervals, and knot coordinate system.
Thus, a T-spline space can be represented by the diagram of a preimage
of a T-mesh such as in Figure 5. Since all T-splines in a given
T-spline space have the same pre-image, it is proper to speak of the
pre-image of a T-spline space. A T-spline space S1 is said to be a
subspace of S2 (denoted S1 S2) if local refinement of a T-spline
Figure 7: Sample Refinement of B1(s;t).
in S1 will produce a T-spline in S2 (discussed in Section 4.3). If T1
is a T-spline, then T1 2 S1 means that T1 has a control grid whose
topology and knot intervals are specified by S1.
Figure 8 illustrates a nested sequence of T-spline spaces, that is,
Figure 8: Nested sequence of T-spline spaces.
Given a T-spline P(s;t) 2 S1, denote by P the column vector of
control points for P(s;t), and given a second T-spline ˜P(s;t) 2 S2,
such that P(s;t) ˜P(s;t). Denote by ˜P the column vector of control
points for ˜P(s;t). There exists a linear transformation that maps P
into ˜P. We can denote the linear transformation
M1;2P = ˜P: (11)
The matrix M1;2 is found as follows.
P(s;t) is given by (1), and
˜P
(s;t) =
˜n
å
j=1
˜P
j ˜B j(s;t) (12)
Since S1 S2, each Bi(s;t) can be written as a linear combination
of the ˜B j(s;t):
Bi(s;t) =
˜n
å
j=1
c j
i
˜B
j(s;t): (13)
We require that
P(s;t) ˜P(s;t): (14)
This is satisfied if
˜P
j =
nå
i=1
c j
i Pi: (15)
Thus, the element at row j and column i of M1;2 in (11) is c j
i . In
this manner, it is possible to find transformation matrices Mi; j that
maps any T-spline in Si to an equivalent T-spline in S j , assuming
Si Sj .
The definition of a T-spline subspace Si Sj means more than
simply that the preimage of S j has all of the control points that the
preimage of Si has. Recall how in Figure 4, it is not possible to simply
add P to the existing T-mesh without adding other control points
as well. Section 4.3 presents insight into why that is, and presents
our local refinement algorithm for T-splines. This, of course, will
allow us to compute valid superspaces of a given T-spline space.
4.3 Local Refinement Algorithm
T-spline local refinement means to insert one or more control points
into a T-mesh without changing the shape of the T-spline surface.
This procedure can also be called local knot insertion, since the addition
of control points to a T-mesh must be accompanied by knots
inserted into neighboring blending functions.
The refinement algorithm we now present has two phases: the
topology phase, and the geometry phase. The topology phase identifies
which (if any) control points must be inserted in addition to the
ones requested. Once all required new control points are identified,
the Cartesian coordinates and weights for the refined T-mesh are
computed using the linear transformation presented in Section 4.2.
We now explain the topology phase of the algorithm.
An important key to understanding this discussion is to keep
in mind how in a T-spline, the blending functions and T-mesh are
tightly coupled: To every control point there corresponds a blending
function, and each blending function’s knot vectors are defined
by Rule 1. In our discussion, we temporarily decouple the blending
functions from the T-mesh. This means that during the flow of the
algorithm, we temporarily permit the existence of blending functions
that violate Rule 1, and control points to which no blending
functions are attached.
Our discussion distinguishes three possible violations that can
occur during the course of the refinement algorithm:
Violation 1 A blending function is missing a knot dictated by
Rule 1 for the current T-mesh.
Violation 2 A blending function has a knot that is not dictated
by Rule 1 for the current T-mesh.
Violation 3 A control point has no blending function associated
with it.
If no violations exist, the T-spline is valid. If violations do exist,
the algorithm resolves them one by one until no further violations
exist. Then a valid superspace has been found.
The topology phase of our local refinement algorithm consists of
these steps:
1. Insert all desired control points into the T-mesh.
2. If any blending function is guilty of Violation 1, perform the
necessary knot insertions into that blending function.
3. If any blending function is guilty of Violation 2, add an appropriate
control point into the T-mesh.
4. Repeat Steps 2 and 3 until there are no more violations.
Figure 9: Local refinement example.
Resolving all cases of Violation 1 and 2 will automatically resolve
all cases of Violation 3.
We illustrate the algorithm with an example. Figure 9.a shows
an initial T-mesh into which we wish to insert one control point,
P2. Because the T-mesh in Figure 9.a is valid, there are no violations.
But if we simply insert P2 into the T-mesh (Figure 9.b)
without changing any of the blending functions, we introduce several
violations. Since P2 has knot coordinates (s3;t2), four blending
functions become guilty of Violation 1: those centered at (s1;t2),
(s2;t2), (s4;t2), and (s5;t2). To resolve these violations, we must
insert a knot at s3 into each of those blending functions, as discussed
in Section 4.1. The blending function centered at (s2;t2) is
N[s0; s1; s2; s4; s5](s)N[t0;t1;t2;t3;t4](t). Inserting a knot s = s3 into
the s knot vector of this blending function splits it into two scaled
blending functions: c2N[s0; s1; s2; s3; s4](s)N[t0;t1;t2;t3;t4](t) (Figure
9.c) and d2N[s1; s2; s3; s4; s5](s)N[t0;t1;t2;t3;t4](t) (Figure 9.d)
as given in (8).
The blending function c2N[s0; s1; s2; s3; s4](s)N[t0;t1;t2;t3;t4](t)
in Figure 9.c satisfies Rule 1. Likewise, the refinements of the
blending functions centered at (s1;t2), (s4;t2), and (s5;t2) all satisfy
Rule 1. However, the t knot vector of blending function
d2N[s1; s2; s3; s4; s5](s)N[t0;t1;t2;t3;t4](t) shown in Figure 9.d is
guilty of Violation 2 because the blending function’s t knot vector
is [t0;t1;t2;t3;t4], but Rule 1 does not call for a knot at t3. This
problem cannot be remedied by refining this blending function; we
must add an additional control point into the T-mesh.
The needed control point is P3 in Figure 9.e. Inserting that control
point fixes the case of Violation 2, but it creates a new case of
Violation 1. As shown in Figure 9.f, the blending function centered
at (s2;t3) has an s knot vector that does not include s3 as required
by Rule 1. Inserting s3 into that knot vector fixes the problem, and
there are no further violations of Rule 1.
This algorithm is always guaranteed to terminate, because the
only blending function refinements and control point insertions
must involve knot values that initially exist in the T-mesh, or that
were added in Step 1. In the worst case, the algorithm would extend
all partial rows of control points to cross the entire surface. In
practice, the algorithm typically requires few if any additional new
control points beyond the ones the user wants to insert.
In summary, this refinement algorithm has two significant advantages
over the algorithm in [Sederberg et al. 2003]: It is guaranteed
to always work, and it normally requires far fewer unrequested
control point insertions (as noted in Section 1 and illustrated in Figure
4).
4.4 Converting a T-spline into a B-spline surface
This refinement algorithm makes it easy to convert a T-spline 2
S1 into an equivalent B-spline surface 2 Sn: simply compute the
transformation matrix M1;n as discussed in Section 4.2.
[Sederberg et al. 2003] defines a standard T-spline to be one for
which, if all weights wi =1, then åni
=1wiBi(s;t)
=1 Bi(s;t)1.
This means that the denominator in (2) is identically equal to one;
hence, the blending functions provide a partition of unity and the
T-spline is polynomial. Thus, an algebraic statement of necessary
and sufficient conditions for a T-spline to be standard is each row
of M1;n sums to 1.
The insertion algorithm can produce a surprising result: a Tspline
for which not all wi = 1 but yet åni
=1 wiBi(s;t) 1. We
dub this a semi-standard T-spline. Figure 10 shows two simple
examples of semi-standard T-splines. The integers (1 and 2) next
to some edges are knot intervals. To verify that these T-splines
Figure 10: Semi-standard T-splines.
are semi-standard, convert them into B-spline surfaces; the control
point weights will all be one.
The notion of T-spline spaces in Section 4.2 enables a more
precise definition of semi-standard and non-standard T-splines. A
semi-standard T-spline space S is one for which there exists some
elements of S for which åni
=1wiBi(s;t) 1, and not all wi = 1. A
non-standard T-spline space is one for which no elements exist for
which åni
=1 wiBi(s;t) 1. These definitions are more precise because
they allow for the notion of a rational T-spline (weights not
all = 1) that is either standard, semi-standard, or non-standard. The
distinction is made based on which type of T-spline space it belongs
to.
5 T-spline Simplification
By T-spline simplification we mean the process of removing superfluous
control points, as discussed in Section 1. Although not
entirely straightforward, it is possible to derive a T-spline knot removal
algorithm that is essentially the inverse of the local refinement
algorithm in Section 4.3. Such an algorithm is useful to remove
a single control point. However, it is difficult to remove large
numbers of control points in this fashion.
Instead, our knot removal algorithm adapts multi-resolution
techniques as follows. Consider a nested sequence of T-spline
spaces
as discussed in Section 4.2. Tn 2 Sn is the surface (a T-spline or
NURBS) that we wish to simplify. Denote by Ti 2 Si the best least
squares approximation to Tn (see [Lyche 1993]). Choose S0 to consist
of a 4 4 grid of control points such that the domain of T0
and Tn are the same. Denote by Pi the vector of control points for
Ti. Then Di;n = (Mi;nPi ??Pn) 2 Sn expresses the approximation
error (see Section 4.2 for the meaning of Mi;n). Refinement of Si
into Si+1 is done by splitting offending faces in half. Di;n is used
to identify offending faces. An offending face in Si is one whose
domain [smin; smax][tmin;tmax] contains the knot coordinates of a
control point in Di;n whose length exceeds the threshold. Each con-
Figure 11: Identifying and splitting offending faces in Si.
trol point in Di;n belongs to P4. We take as its length the square
root of the sum of the squares of the four components. All of our
examples have been standard T-splines and polynomial B-splines,
so the fourth element of each control point in Di;n is always 0. This
measure of length will also work fairly well for rational surfaces if
the error tolerance is small.
Figure 11 illustrates this procedure. The control points D1, D2,
and D3 in Figure 11.a are control points in Di;n whose length is
greater than the error threshold. The four shaded faces in Figure
11.a contain one of those three points, and are flagged for splitting.
We experimented with several different ways to split faces and
found that the most important principle is that faces should, in general,
be split roughly in half in the direction which the face has the
most knot lines. Specifically, if a face has m interior knot lines in
the s direction and n interior knot lines in the t direction and m > n,
then split along the (m+1)=2th knot line in the s direction. Thus,
the face that contains D3 in Figure 11.a is split with line L4 in Figure
11.b, and the face that contains D1 is split with line L1. D2 is
on the border between two faces, both of which are split. The face
containing L2 has three interior s knot lines and three interior t knot
lines, so either direction could have been chosen for the split.
When we speak of splitting a face, we mean performing a local
refinement in which the two endpoints of the line segment used to
split the face are inserted into the T-mesh using the topology phase
of the local refinement algorithm in Section 4.3. The refinement
algorithm will sometimes need to insert a few additional control
points into the T-mesh in order to satisfy Rule 1. The refinement
algorithm must be invoked, or else we will not form a nested sequence
of T-spline spaces.
In summary, our algorithm parallels the methods of B-spline
wavelet decomposition [Daehlen and Lyche 1992] with two important
differences. First, we use a nested sequence of T-spline spaces
instead of B-spline spaces. This allows us to split only the faces
where the error is too large. Second, we do not formally compute
a decomposition. In fact, we have no need to store the sequence of
Ti; they are used to identify which faces to split in forming Si+1 and
can then be discarded.
Figure 12: (a) T-spline representation of B-spline wavelet decomposition
with 1926 control points. The red control points are superfluous.
(b) The results of direct T-spline simplification, with 1109
control points. Approximation error = 1:5%.
It is noteworthy that similar results can be obtained by performing
B-spline wavelet decomposition, thresholding the small coefficients,
and then constructing a T-spline from the remaining nonzero
wavelet coefficients. We implemented such an algorithm using
the B-spline wavelet decomposition method in [Daehlen and
Lyche 1992]. The non-zero wavelet terms were then merged into
a T-spline using the local refinement algorithm in Section 4.3. We
used an error threshold of 1:5%, which is the same value used in
computing the T-spline simplification. The T-spline created using
B-spline wavelet decomposition in Figure 12.a required 74% more
control points than the direct T-spline simplification algorithm. We
believe that this is mainly due to the extra control points that the
local refinement algorithm often inserts. We stress that Figure 12.a
is a T-spline, and not merely a tensor product grid. The conversion
from B-spline wavelets to T-splines does not produce as many
T-junctions as our direct T-spline simplification algorithm.
6 Results and Discussion
We conclude by presenting the results of performing T-spline simplification
on three commercial-quality NURBS models that were
provided to us courtesy of Zygote Media Group, Inc. In each case,
the artists who created these models exercised care to avoid superfluous
control points. Yet, our algorithm succeeded in eliminating
about half of the control points. Furthermore, these models are
comprised of several different NURBS surfaces. Using the techniques
presented in [Sederberg et al. 2003], it is possible to merge
adjoining NURBS surfaces into a single air-tight T-spline, without
adding new control points. By contrast, merging them into a single
NURBS can cause the number of control points in the merged
model to increase dramatically. The image in Figures 13.a , 14.a,
and 15.a were all rendered using the T-spline control grid. The red
control points in Figures 13.c , 14.c, and 15.c denote T-junctions.
Figure 13: Model of a Frog (courtesy of Zygote Media Group, Inc.)
Figure 14: Model of a Triceratops (courtesy of Zygote Media
Group, Inc.)
Figure 15: Model of a Woman (courtesy of Zygote Media Group,
Inc.)
In summary, the local refinement algorithm presented in Section
4.3 performs much more efficiently than the algorithm
in [Sederberg et al. 2003]. Furthermore, it is shown that this algorithm
always works. The T-spline simplification algorithm is able
to identify and remove a large percentage of superfluous control
points, even in high-quality NURBS models.
Most of the examples in this paper have focused on T-spline simplification
in which an existing NURBS model is converted into
a T-spline. However, a potentially more common design scenario
would be one in which an artist begins from scratch to create a
T-spline model. In this setting, the local refinement algorithm in
Section 4.3 will allow a designer to create a model that at each step
has a minimal number of superfluous control points to get in the
way. Figure 16 illustrates how this capability can simplify the design
process. The artist begins with the coarse model in Step 1,
then performs a series of refinements by adding control points in
regions where more detail is called for, and then adjusting those
control points. Note how the control point insertion is local to the
Figure 16: Initial steps in creating a model of a head using Tsplines.
(f) is the result of converting (e) into a NURBS surface.
region being refined. Figure 16.f shows the result of converting the
T-spline in Figure 16.e into a NURBS.
In closing, we pose two open questions. First, Section 4.4
presents an algebraic statement of necessary and sufficient conditions
for a T-spline space to be standard. What is the topological
interpretation of those conditions? That is, what T-mesh configurations
yield a standard T-spline? Second, in this paper we have
referred to T-spline blending functions instead of basis functions.
Are T-spline blending functions always linearly independent (and
hence can they rightly be called basis functions)?
7 Acknowledgments
We gratefully recognize excellent feedback from several reviewers.
The first five authors were supported in part by NSF grant CCR-
9912411. Jianmin Zheng is partially supported by URC-SUG of
Nanyang Technological University.
References
BOEHM, W. 1980. Inserting new knots into B-spline curves.
Computer-Aided Design 12 (July), 199–201.
BOEHM, W. 1981. Generating the Bezier points of B-spline curves
and surfaces. Computer-Aided Design 13 (Nov.), 365–366.
COHEN, E., LYCHE, T., AND RIESENFELD, R. F. 1980. Discrete
B-spline subdivision techniques in computer-aided geometric
design and computer graphics. Computer Graphics and Image
Processing 14 (Oct.), 87–111.
DAEHLEN, M., AND LYCHE, T. 1992. Decomposition of splines.
In Mathematical Methods in Computer Aided Geometric Design
II, Academic Press, New York, T. Lyche and L. L. Schumaker,
Eds., 135–160.
FARIN, G., REIN, G., SAPIDIS, N., AND WORSEY, A. J. 1987.
Fairing cubic B-spline curves. Computer Aided Geometric Design
4, 1-2 (July), 91–103.
FORSEY, D. R., AND BARTELS, R. H. 1988. Hierarchical B-spline
refinement. In Computer Graphics (SIGGRAPH ’88 Proceedings),
J. Dill, Ed., vol. 22, 205–212.
FORSEY, D., AND WONG, D. 1998. Multiresolution surface reconstruction
for hierarchical b-splines. In Graphics Interface,
57–64.
GOLDMAN, R. N., AND LYCHE, T. 1993. Knot Insertion and
Deletion Algorithms for B-Spline Curves and Surfaces. Philadelphia:
SIAM.
GONZALEZ-OCHOA, C., AND PETERS, J. 1999. Localizedhierarchy
surface splines (less). In Proceedings of the 1999 symposium
on Interactive 3D graphics, ACM Press, 7–15.
GRINSPUN, E., KRYSL, P., AND SCHR¨O DER, P. 2002. CHARMS:
a simple framework for adaptive simulation. In Proceedings of
SIGGRAPH02, ACM Press, 281–290.
HANDSCOMB, D. 1987. Knot elimination: reversal of the Oslo
algorithm. International Series of Numerical Mathematics 81,
103–111.
KRAFT, R. 1997. Adaptive and linearly independent multilevel
B-splines. In Surface Fitting and Multiresolution Methods, Vanderbilt
University Press, A. L. Mhaut, C. Rabut, and L. L. Schumaker,
Eds., vol. 2, 209–218.
LANE, J. M., AND RIESENFELD, R. F. 1980. A theoretical development
for the computer generation of piecewise polynomial
surfaces. IEEE Transactions on Pattern Analysis and Machine
Intelligence PAMI-2, 1 (Jan.), 35–46.
LYCHE, T., AND MØRKEN, K. 1987. Knot removal for parametric
B-spline curves and surfaces. Computer Aided Geometric Design
4, 3 (Nov.), 217–230.
LYCHE, T., AND SCHUMAKER, L. L. 2000. A multiresolution
tensor spline method for fitting functions on the sphere. SIAM
Journal of Scientific Computing 22, 724–746.
LYCHE, T., COHEN, E., AND MØRKEN, K. 1985. Knot line refinement
algorithms for tensor product B-spline surfaces. Computer
Aided Geometric Design 2, 1-3, 133–139.
LYCHE, T., MORKEN, K., AND QUAK, E. 2001. Theory and
algorithms for non-uniform spline wavelets. In Multivariate Approximation
and Applications, N. Dyn, D. Leviatan, D. Levin,
and A. Pinkus, Eds. Cambridge University Press, 152–187.
LYCHE, T. 1993. Knot removal for spline curves and surfaces. In
Approximation Theory VII, Academic Press, E.W. Cheney, C. K.
Chui, and L. L. Schumaker, Eds., 207–227.
SCHR¨O DER, P., AND SWELDENS, W. 1995. Spherical wavelets:
Efficiently representing functions on the sphere. In Proceedings
of SIGGRAPH 95, 161–172.
SEDERBERG, T. W., ZHENG, J., BAKENOV, A., AND NASRI, A.
2003. T-splines and T-nurccs. ACM Transactions on Graphics
22, 3 (July), 477–484.
SEIDEL, H.-P. 1988. Knot insertion from a blossoming point of
view. Computer Aided Geometric Design 5, 1 (June), 81–86.
WELLER, F., AND HAGEN, H. 1995. Tensor product spline spaces
with knot segments. In Mathematical Methods for Curves and
Surfaces, M. Daehlen, T. Lyche, and L. L. Schumaker, Eds. Vanderbilt
University Press, Nashville, 563–572.