Permission to make digital or hard copies of part or all of this work for personal or classroom u is granted without fee provided that copies are not made or distributed for profit or direct commercial advantage and that copies show this notice on the first page or initial screen of a display along with the full citation. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwi, to republish, to post on rvers, to redistribute to lists, or to u any component of this work in other works requires prior specific permission and/or a fee.Permissions may be requested from Publications Dept., ACM, Inc., 1515 Broadway, New York, NY 10036 USA, fax +1 (212) 869-0481, or T-spline Simplification and Local Refinement
Thomas W.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 super-fluous control points that significantly interfere with the design pro-cess.This paper prents an algorithm for eliminating such su-perfluous 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 prents a new T-spline local refinement algorithm and answers two funda-mental open questions on T-spline theory.
CR Categories:I.3.5[Computer Graphics]:Computational Ge-ometry and Object Modeling—curve,surface,solid and object rep-rentations;
Keywords:NURBS surfaces,T-splines,subdivision surfaces,lo-cal refinement,knot removal
1Introduction
A rious 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 rve no pur-po 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 n,
superfluous.
Figure 1:Head modeled (a)as a NURBS with 4712control points and (b)as a T-spline with 1109control 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 gr
id 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 T-splines 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 2shows 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/3as many control
points.
Figure 3:NURBS head model,converted to a T-spline.Superfluous control points are a rious nuisance for designers,not merely becau they require the designer to deal with more data,but also becau they can introduce unwanted ripples in the surface as can be en 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 rip-ples.Figure 1.a shows a NURBS head model.Figure 1shows the
© 2004 ACM 0730-0301/04/0800-0276 $5.00
respective NURBS and T-spline control meshes for the surfaces in Figure 3.Over 3/4of the 4712NURBS control points are super-fluous and do not appear in the T-spline control mesh.
This paper prents an algorithm for converting a NURBS model into a T-spline model.The process eliminates most superfluous control points.The algorithm was ud to convert the NURBS model in Figure 1.a into the T-spline model in Figure 1.b.Conver-sion from NURBS to T-spline can be lossless (such as in the ca of CAD objects like the car door)or an approximation error can be specified.An error threshold of 1%was ud in the example in Fig-ure 1,and the only obrvable 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 cond that it takes to convert from NURBS to T-spline using the algorithm prented in this paper.We refer to this conversion process as T-spline simplification.Our algorithm makes heavy u of the operation of T-spline local refinement,introduced in [Sederberg et al.2003].However,[Seder-berg et al.2003]left this operation on uncertain footing.It was shown that in certain situations,a control point can be inrted into a particular location in a T-mesh topology only if some additional control points are also added.Furthermore,the number of addi-tional control points can be quite large using the local refine
ment algorithm in [Sederberg et al.2003].This problem is illustrated in Figure 4.a,which shows a T-mesh into which we wish to inrt con-trol point P .The initial control points are the red,unlabeled ones.The algorithm in [Sederberg et al.2003]requires the additional in-rtion of all eight control points labeled V .[Sederberg et al.2003]concluded with an open question :Do there exist T-spline topolo-gies into which it is impossible to inrt a requested control point?This paper answers that question by prenting a new local re-finement algorithm with which it is provably always possible to in-rt a requested control point.Furthermore,the number of addi-tional control points needed is reduced significantly.The algorithm is illustrated in Figure 4.b,where we inrt P while only perform-ing a single additional inrtion V .This new local refinement al-gorithm plays a key role in the T-spline simplification algorithm prented in this
paper.我轻轻的来
Figure 4:Local refinement using the old algorithm and the new algorithm.
The paper is organized as follows.Section 2surveys perti-nent literature on B-spline knot removal and inrtion.Section 3prents a brief review of T-splines.Section 4provides equations for refining T-spline blending functions,introduces the notion of T-spline spaces,and prents the improved algorithm for local re-finement (knot inrtion)into a T-spline.This ction also answers a cond open question by prenting necessary and sufficient con-ditions for a T-spline to be standard (i.e.,a T-spline who blending functions form a partition of unity),and introduces mi-standard T-splines,a surprising type of rational T-spline in which some control
points have weights =1,yet the T-spline is equivalent to a poly-nomial B-spline surface (all weights =1).Section 5prents the algorithm for local knot removal in a T-spline (of which B-spline is a special ca).Section 6concludes with some examples and discussion.
We restrict our discussion to the ca of degree three B-splines and T-splines.However,adapting the algorithms to T-NURCCs (the arbitrary-topology version of T-splines)is straightforward.
2Prior Work
Local refinement of NURBS curves and surfaces is accomplished through knot inrtion,an exact process that does not alter the shape of the curve or surface.Several algorithms exist for knot inrtion.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 inrtion have also been developed.
Knot inrtion is a fundamental algorithm that can be ud 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 inrtion include providing tools for straightforward evalua-tion of points on curves/surfaces,tesllation,rendering,and other geometric processing algorithms [Lane and Rienfeld 1980];per-forming bas conversion such as converting a B-spline curve to a B´e zier [Boehm 1981];adding extra degrees of freedom for shape modification or editing [Fory and Bartels 1988].
Knot inrtion works well to locally refine a B-spline curve:in-rting 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 becau the inrtion of one knot into either of the surface knot vectors ca
us an entire row or col-umn of control points to be inrted [Lyche et al.1985].This prob-lem has been addresd by hierarchical B-splines for local refine-ment and multiresolution editing [Fory and Bartels 1988;Fory and Wong 1998;Gonzalez-Ochoa and Peters 1999].[Kraft 1997]prents a multilevel spline space that is a linear span of tensor product B-splines on different,hierarchically ordered grid levels.A lection mechanism for B-splines is provided,which guarantees linear independence to form a basis.[Weller and Hagen 1995]gen-eralizes tensor-product B-spline surfaces by allowing the domain partition with knot gments and knot rays.The approach is re-stricted to so-called mi-regular bas.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 bad,permit local refinement.
Knot removal is the inver of knot inrtion [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 incread by removing knots.Like knot inrtion,knot removal can also be ud to perform bas conversion,multiresolution analysis,and wavelet decomposition [Daehlen and Lyche 1992].
While knot inrtion for a B-spline curve is always possible with-out error,deleting a knot without changing the curve is possible only when the two adjacent curve gments are C l continuous with l >n −m where n is the degree of the curve and m is the multiplic-ity of the knot.Therefore knot removal usually involves approxi-mation.In practice,for a B-spline curve,if a control point almost satisfies a knot removal condition,the inver 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 sur-faces.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 col-umn 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 cloly follows the idea of spline wavelet decomposition (e [Lyche et al.2001]and its references)and thresholding (e,for exam-ple,[Schr¨o der and Sweldens 1995]).For spline wavelet decompo-sition on the sphere using tensor product B-splines e [Lyche and Schumaker 2000].
3T-splines
This ction gives a brief review of T-splines as prented in [Seder-berg 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 degener-ates to a B-spline surface.
Knot information for T-splines is expresd using knot inter-vals,non-negative numbers that indicate the difference between two knots.A knot interval is assigned to each edge in the T-mesh.Fig-ure 5shows the pre-image of a portion of a T-mesh in (s ,t )param-eter space;the d i and e i 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 inter-vals on the opposing side.For example,in Figure 5on face F 1,e 3+e 4=e 6+e 7,and on face F 2,d 6+d 7=d 9.
It is possible to infer a local knot coordinate system from the knot intervals on a T-mesh.To impo a knot coordinate system,we first choo a control point who pre-image will rve as the origin for the parameter domain (s ,t )=(0,0).For the example in Figure 5,we designate (s 0,t 0)to be the knot origin.
Once a knot origin is chon,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,tho knot val
ues are labeled s i and t i .Bad on our choice of knot origin,we have s 0=t 0=0,s 1=d 1,s 2=d 1+d 2,s 3=d 1+d 2+d 3,t 1=e 1,t 2=e 1+e 2,and so forth.Likewi,each control point has knot coordinates.For example,the knot coordinates for P 0are (0,0),for P 1are (s 2,t 2+e 6),for P 2are (s 5,t 2),and for P 3are (s 5,t 2+e 6)
.
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 F 1if and only if e 3=e 6and therefore also e 4=e 7.
The knot coordinate system is ud 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
P i B i (s ,t )
(1)
where P i =(x i ,y i ,z i ,w i )are control points in P 4who weights are
五台山冬天能去吗w i ,and who Cartesian coordinates are 1
w i
(x i ,y i ,z i ).Likewi,the Cartesian coordinates of points on the surface are given by
∑n i =1(x i ,y i ,z i )B i (s ,t )∑n i =1
w i B i (s ,t ).
(2)
The blending functions in (1)are B i (s ,t )and are given by
B i (s ,t )=N [s i 0,s i 1,s i 2,s i 3,s i 4](s )N [t i 0,t i 1,t i 2,t i 3,t i 4](t )
(3)
运用的近义词where N [s i 0,s i 1,s i 2,s i 3,s i 4](s )is the cubic B-spline basis function
associated with the knot vector
s i =[s i 0,s i 1,s i 2,s i 3,s i 4]
(4)
and N [t i 0,t i 1,t i 2,t i 3,t i 4](t )is associated with the knot vector
t i =[t i 0,t i 1,t i 2,t i 3,t i 4].
圣罗兰广告语(5)as illustrated in Figure 6.The designer is free to adjust the
weights
Figure 6:Knot lines for blending function B i (s ,t ).
w i to obtain additional shape control,as in rational B-splines.As we shall e 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 tensor-product rational B-spline surface.The difference between the T-spline equation and a B-spline equation is in how the knot vectors s i and t i are determined for each blending function B i (s ,t ).Knot vectors s i (4)and t i (5)are inferred from the T-mesh neighborhood of P i .Since we will refer to the rule whereby the knot vectors are inferred,we formally state it as
Rule 1.Knot vectors s i (4)and t i (5)for the blending function of P i are determined as follows.(s i 2,t i 2)are the knot coordinates of P i .Consider a ray in parameter space R (α)=(s i 2+α,t i 2).Then s i 3and s i 4are the s coordinates of the first two s -edges intercted by the ray (not including the initial (s i 2,t i 2)).By s -edge,we mean a vertical line gment of constant s .The other knots in s i and t i are found in like manner.
We illustrate Rule1by a few examples.The knot vectors for P1 in Figure5are 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 the knot vectors are determined for each blending function,the T-spline is defined using(1)and(3).
4T-spline Local Refinement
This ction prents our new algorithm for local refinement of T-splines.Blending function refinement plays an important role in this algorithm,and is reviewed in Section4.1.The notion of T-spline spaces is introduced in Section4.2.This concept is ud in the local refinement algorithm in Section4.3and in the T-spline simplification algorithm in Section5.
4.1Blending 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 subquence of˜s,then N[s0,s1,s2,s3,s4](s)can be written as a linear combination of the m−4B-spline basis functions defined over the substrings of length5in˜s.
We now prent all basis function refinement equations for the ca m=6.Equations for m>6can be found by repeated applica-tion of the 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−s0and 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−s0and 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=1and d3=s4−k
s4−s1.If k≤s0or k≥s4,N(s)does not
change.
A T-spline function B(s,t)can undergo knot inrtion in either s or t,thereby splitting it into two scaled blending functions that sum to the initial one.Further inrtion into the resultant scaled blend-ing functions yields a t of scaled blending functions that sum to the original.For example,Figure7.a shows the knot vectors for a T-spline blending function B1,and Figure7.b shows a refinement of the knot vectors in Figure7.a.By appropriate application of (6)—(9),we can obtain
B1(s,t)=c11˜B1(s,t)+c21˜B2(s,t)+c31˜B3(s,t)+c41˜B4(s,t).(10)
4.2T-spline Spaces
We define a T-spline space to be the t of all T-splines that have the same T-mesh topology,knot intervals,and knot coordinate system. Thus,a T-spline space can be reprented by the diagram of a pre-image of a T-mesh such as in Figure5.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 S1is said to be a subspace of S2(denoted S1⊂S2)if local refinement of a
T-spline
Figure7:Sample Refinement of B1(s,t).
in S1will produce a T-spline in S2(discusd in Section4.3).If T1 is a T-spline,then T1∈S1means that T1has a control grid who topology and knot intervals are specified by S1.
Figure8illustrates a nested quence of T-spline spaces,that is, S1⊂S2⊂S3⊂···⊂S n
.
Figure8:Nested quence of T-spline spaces.
Given a T-spline P(s,t)∈S1,denote by P the column vector of control points for P(s,t),and given a cond T-spline˜P(s,t)∈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,2is 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 B i(s,t)can be written as a linear combination of the˜B j(s,t):
B i(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 P i.(15)
Thus,the element at row j and column i of M1,2in(11)is c j i.In this manner,it is possible tofind transfor
mation matrices M i,j that maps any T-spline in S i to an equivalent T-spline in S j,assuming S i⊂S j.
The definition of a T-spline subspace S i⊂S j means more than simply that the preimage of S j has all of the control points that the preimage of S i has.Recall how in Figure4,it is not possible to sim-ply add P to the existing T-mesh without adding other control points as well.Section4.3prents insight into why that is,and prents our local refinement algorithm for T-splines.This,of cour,will allow us to compute valid superspaces of a given T-spline space.
4.3Local Refinement Algorithm
T-spline local refinement means to inrt 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 inrtion,since the ad-dition of control points to a T-mesh must be accompanied by knots inrted into neighboring blending functions.
The refinement algorithm we now prent has two phas:the topology pha,and the geometry pha.The topology pha iden-tifies which(if any)control points must be inrted 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 prented in Section4.2.
We now explain the topology pha 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 blend-ing function,and each blending function’s knot vectors are defined by Rule1.In our discussion,we temporarily decouple the blending functions from the T-mesh.This means that during theflow of the algorithm,we temporarily permit the existence of blending func-tions that violate Rule1,and control points to which no blending functions are attached.
Our discussion distinguishes three possible violations that can occur during the cour of the refinement algorithm:•Violation1A blending function is missing a knot dictated by Rule1for the current T-mesh.
•Violation2A blending function has a knot that is not dictated by Rule1for the current T-mesh.感冒头疼
•Violation3A control point has no blending function associ-ated 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 pha of our local refinement algorithm consists of the steps:
1.Inrt all desired control points into the T-mesh.
2.If any blending function is guilty of Violation1,perform the
necessary knot inrtions into that blending function.
3.If any blending function is guilty of Violation2,add an ap-
propriate control point into the T-mesh.
4.Repeat Steps2and3until there are no more
violations.
Figure9:Local refinement example.
Resolving all cas of Violation1and2will automatically resolve all cas of Violation3.
We illustrate the algorithm with an example.Figure9.a shows an initial T-mesh into which we wish to inrt one control point, P2.Becau the T-mesh in Figure9.a is valid,there are no vio-lations.But if we simply inrt P2into the T-mesh(Figure9.b) without changing any of the blending functions,we introduce v-eral violations.Since P2has knot coordinates(s3,t2),four blending functions become guilty of Violation1:tho centered at(s1,t2), (s2,t2),(s4,t2),and(s5,t2).To resolve the violations,we must inrt a knot at s3into each of tho blending functions,as dis-cusd in Section4.1.The blending function centered at(s2,t2)is N[s0,s1,s2,s4,s5](s)N[t0,t1,t2,t3,t4](t).Inrting a knot s=s3into 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)(Fig-ure9.c)and d2N[s1,s2,s3,s4,s5](s)N[t0,t1,t2,t3,t4](t)(Figure9.d) as given in(8).
The blending function c2N[s0,s1,s2,s3,s4](s)N[t0,t1,t2,t3,t4](t) in Figure9.c satisfies Rule1.Likewi,the refinements of the blending functions centered at(s1,t2),(s4,t2),and(s5,t2)all sat-i
sfy Rule1.However,the t knot vector of blending function
d 2N [s 1,s 2,s 3,s 4,s 5](s )N [t 0,t 1,t 2,t 3,t 4](t )shown in Figur
e 9.d is guilty o
f Violation 2becau the blendin
g function’s t knot vec-tor is [t 0,t 1,t 2,t 3,t 4],but Rule 1does not call for a knot at t 3.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 P 3in Inrting that con-trol point fixes the ca of Violation 2,but it creates a new ca of Violation 1.As shown in Figure 9.f,the blending function centered at (s 2,t 3)has an s knot vector that does not include s 3as required by Rule 1.Inrting s 3into that knot vector fixes the problem,and there are no further violations of Rule 1.
This algorithm is always guaranteed to terminate,becau the only blending function refinements and control point inrtions must involve knot values that initially exist in the T-mesh,or that were added in Step 1.In the worst ca,the algorithm would ex-tend all partial rows of control points to cro
镪怎么读
ss the entire surface.In practice,the algorithm typically requires few if any additional new control points beyond the ones the ur wants to inrt.
In summary,this refinement algorithm has two significant ad-vantages over the algorithm in [Sederberg et al.2003]:It is guaran-teed to always work,and it normally requires far fewer unrequested control point inrtions (as noted in Section 1and illustrated in Fig-ure 4).
4.4Converting a T-spline into a B-spline surface
This refinement algorithm makes it easy to convert a T-spline ∈S 1into an equivalent B-spline surface ∈S n :simply compute the transformation matrix M 1,n as discusd in Section 4.2.
[Sederberg et al.2003]defines a standard T-spline to be one for
which,if all weights w i =1,then ∑n i =1w i B i (s ,t )≡∑n i =1B i (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 M 1,n sums to 1.
The inrtion algorithm can produce a surprising result:a T-spline for which not all w i =1but yet ∑n i =1w i B i (s ,t )≡1.We dub this a mi-standard T-spline.Figure 10shows two simple examples of mi-standard T-splines.The integers (1and 2)next to some edges are knot intervals.To verify that the
T-splines
Figure 10:Semi-standard T-splines.
are mi-standard,convert them into B-spline surfaces;the control point weights will all be one.
The notion of T-spline spaces in Section 4.2enables a more preci definition of mi-standard and non-standard T-splines.A mi-standard T-spline space S is one for which there exists some element
s of S for which ∑n i =1w i B i (s ,t )≡1,and not all w i =1.A non-standard T-spline space is one for which no elements exist for which ∑n i =1w i B i (s ,t )≡1.The definitions are more preci be-cau they allow for the notion of a rational T-spline (weights not all =1)that is either standard,mi-standard,or non-standard.The distinction is made bad on which type of T-spline space it belongs to.
5T-spline Simplification
By T-spline simplification we mean the process of removing su-perfluous control points,as discusd in Section 1.Although not entirely straightforward,it is possible to derive a T-spline knot re-moval algorithm that is esntially the inver of the local refine-ment algorithm in Section 4.3.Such an algorithm is uful to re-move 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 quence of T-spline spaces
S 0⊂S 1⊂...⊂S n (16)as discusd in Section 4.2.T n ∈S n is the surface (a T-spline or
NURBS)that we wish to simplify.Denote by T i ∈S i the best least squares approximation to T n (e [Lyche 1993]).Choo S 0to con-sist of a 4×4grid of control points such that the domain of T 0and T n are the same.Denote by P i the vector of control points for T i .Then D i ,n =(M i ,n P i −P n )∈S n express the approximation error (e Section 4.2for the meaning of M i ,n ).Refinement of S i into S i +1is done by splitting offending faces in half.D i ,n is ud to identify offending faces.An offending face in S i is one who domain [s min ,s max ]×[t min ,t max ]contains the knot coordinates of a control point in D i ,n who length exceeds the threshold.Each
con-
Figure 11:Identifying and splitting offending faces in S i .trol point in D i ,n belongs to P 4.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 D i ,n is always 0.This measure of length will also work fairly well for rational surfaces if the error tolerance is small.
Figure 11illustrates this procedure.The control points D 1,D 2,and D 3in Figure 11.a are control points in D i ,n who length is greater than the error threshold.The four shaded faces in Fig-ure 11.a contain one of tho three points,and are flagged for split-ting.We experimented with veral different ways to split faces and found that the most important principle is that faces should,in gen-eral,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 D 3in Figure 11.a is split with line L 4in Fig-ure 11.b,and the face that contains D 1is split with line L 1.D 2is on the border between two faces,both of which are split.The face containing L 2has three interior s knot lines and three interior t knot lines,so either direction could have been chon for the split.
When we speak of splitting a face,we mean performing a local refinement in which the two endpoints
of the line gment ud to split the face are inrted into the T-mesh using the topology pha of the local refinement algorithm in Section 4.3.The refinement algorithm will sometimes need to inrt a few additional control
