Computer GraphicsShi-Min HuShi Min HuTsinghua UniversityTsinghua UniversityToday s TopicsToday’s Topics•Why splines?•B-Spline Curves and properties •B-Spline surfacesB Spline surfaces•NURBS curves and SurfacesWhy to introduce B Spline(BWhy to introduce B-Spline (B样条)•Bezier curve/surface has many advantages, but they have two main shortcomings:e e cu ve/su ace ca ot be od ed oca y–Bezier curve/surface cannot be modified locally(局部修改).–It is very complex to satisfy geometric continuityIt i l t ti f t i ti itconditions for Bezier curves or surfaces joining.•History of B-splinesI1946S h b d li b d–In 1946, Schoenberg proposed a spline-basedmethod to approximate curves.–It’s motivated by runge-kutta problem ininterpolation: high degree polynomial may surge p g g p y y g upper and down–Why not use lower degree piecewise polynomial Wh t l d i i l i lwith continuous joining?–that’s Spline–But people thought it’s impossible to use Spline in shape design because complicatedin shape design, because complicated computation–In 1972, based on Schoenberg’s work, Gordon I1972b d S h b’k G d and Riesenfeld introduced “B-Spline” and lots of corresponding geometric algorithms.f di i l i h–B-Spline retains all advantages of Bezier curves, and overcomes the shortcomings of Bezier curves.•Tips for understanding B-Spline?–Spline function interpolation is well known, it can Spline function interpolation is well known it canbe calculated by solving a tridiagonalequations(三对角方程).i–For a given partition of an interval, we cancompute Spline curve interpolation similarly.–All splines over a given partition will form aAll splines over a given partition will form alinear space. The basis function of this linearspace is called B-Spline basis function.i ll d B S li b i f i–Similar to Bezier Curve using Bernstein basis functions, B-Spline curves uses B-Spline basis f nctions B Spline c r es ses B Spline basis functions.B-Spline curves and it’s p Properties•Formula of B-Spline Curve.n ]1,0[),()(,0∈=Σ=t t B P t P n i i n i are control points ∑==i k i i t N P t P 0,)()(–are control points. –(i=0,1,..,n) are the i-th B-Spline basis function ),,1,0(n i P i L =)(,t N k i of order k. B-Spline basis function is a order k (degree k -1) piecewise polynomial (分段多项式) determined by the knot vector, which is a non-decreasing set of numbers.g•Demo of B-splineThe story of order & degree•The story of order°ree–G Farin: degree, Computer Aided Geometric Design –Les Piegl: order, Computer Aided DesignL Pi l d C Aid d D iB Spline Basis Function B-Spline Basis Function•Definition of B-Spline Basis Function –de Boor-Cox recursion formula:⎧⎩⎨<<=+Otherwiset x t t N i i i 01)(11,−−,,11,111()()()i i k i k i k i k i k i i k i t t t t N t N t N t t t t t +−+−+−++=+−−–Knot Vector: a sequence of non-decreasing number L L L k n k n n n k k t t t t t t t t +−++−,,,,,,,,,,11110L L L•, i = 01k=•, i = 02k=⎧⎩⎨<<=+Otherwiset x t t N i i i 01)(11,,,11,111()()()i i k i k i k i k i k i i k i t t t t N t N t N t t t t t +−+−+−++−−=+−−B Spline Basis Function B-Spline Basis Function•Questions:–What is nonzero domain(非零区间) of B-Splinebasis function ?)(,t N k i –How many knots does it need?Wh t i th d fi iti d i ()f th –What is the definition domain(定义区间) of the curves?4,4()()i i P t PN t =∑0i =B Spline Basis Function B-Spline Basis Function•take k=4, n=4 as example 4,4()()i i P t PN t =∑876543210,,,,,,,,t t t t t t t t t 0i=B Spline Basis Function B-Spline Basis Function•Properties:N ti it d l l t–Non-negativity and local support •is non-negativeis a non ero pol nomial on ,()i k N t ]•is a non-zero polynomial on ⎧∈≥+t t t t N k i i ],[0[,i i k t t +,()i k N t –Partition of Unity⎩⎨=otherwisek i 0)(,•The sum of all non-zero order k basis functions onis 1 ∑n 11[,]k n t t −+=+−∈=i n k k i t t t t N011,],[1)(B Spline Basis Function B-Spline Basis Function•Properties:Diff ti l ti f th b i f ti–Differential equation of the basis function:,,11,11111()()()i k i k i k i k i i k i k k N t N t N t t t t t −+−+−++−−′=+−−–Please compare with the Bernstein base:)]B 10 )],()([)(1,1,1,n i t B t B n t n i n i n i ⋅⋅⋅=−=′−−−;,,,B SplineB-Spline•Category(分类) of B-Splineg g p–General Curves could be categorized to two groups by checking if the start point and the endpoint areoverlapped:•Open Curves•Close CurvesClose Curves–According to the distribution(分布) of the knots inknot vector, B-Spline could be classified to theknot vector B Spline could be classified to thefollowing four groups:Uniform B-Spline(均匀B样条)U if B S li–(1) Uniform B-Spline,,,,,,,,•The knots are uniformed distributed, like 0,1,2,3,4,5,6,7•This kind of knot vector defines uniform B-Spline basisfunctionuniform B-Spline of Degree 3if B S li f D3Quasi Uniform B Spline(Quasi-Uniform B-Spline(准均匀B样条)–(2) Quasi-Uniform B-Splinep•Different from uniform B-Spline, it has:–the start-knot and end-knot have repetitiveness(重复度) of k–Uniform B-Spline does not retain the “end point” property ofBezier Curve, which means the start point and end point ofuniform B-Spline are no-longer the same as the start point andend point of the control points. However, quasi-Uniform B-end point of the control points However quasi Uniform BSpline retains this “end point” propertyQuasi-uniform B-Spline curve of degree 3Piecewise Bezier Curve(Piecewise Bezier Curve(分段Bezier曲线)–(3) Piecewise Bezier Curvep()•the start-knot and end-knot have repetitiveness(重复度)of kp•all other knots have repetitiveness of k-1•Then each curve segment will be Bezier curvesPiecewise B-Spline Curve of degree 3Piecewise Bezier Curve(分段Bezier曲线) Piecewise Bezier Curve(•For piecewise Bezier curve, the different pieces of th l ti l i d d t M i ththe curve are relatively independent. Moving the control point will only influence the corresponding piece of curve, while other pieces of curves will be not change. Furthermore, the algorithms for Bezier not change.Furthermore,the algorithms for Bezier could also be used for piecewise Bezier Curve.•But this method need more data to define the curve (more control points, more knots).Non-uniform B-Spline (非均匀B p (样条)–(4) Non-uniform B-Spline•The knot vectors satisfy T t t t =L e o vec o s sa s y conditions that the sequence of knots is non-)01[,,,]n k +decreasing(非递减). –repetitiveness of two end knots, <= k –repetitiveness of other knots, <= k-1•This kind of knot vector defines the non-uniformB-Spline.Properties of B Spline Curves Properties of B-Spline Curves•Properties of B-Spline curvesL l(–Local(局部性)•The curve in interval is only affected ],[1+∈i i t t t by at most k control points , and is independent of other control points.),,1(i k i j P j L +−=•Changing the position of control point will only affect the curve on interval i P only affect the curve on interval),(k i i t t +n∑==i k i i t N P t P 0,)()(Properties of B Spline Properties of B-Spline–Continuity(连续性)P()i i d f i i•P(t) is continuous at a node of repetitiveness r.–Convex hull(凸包性)1k r C −−•A B-spline curve is contained in the convex hullof its control polygon More specifically if t is of its control polygon. More specifically, if t is in knot span , then P(t) is in the h ll f t l i t n i k t t i i ≤≤−+1),,(1convex hull of control points ik i P P ,,1L +−Properties of B Spline Properties of B-Spline–Piecewise polynomial (分段多项式)•In every knot span, P(t) is a polynomial of t whose y p ()p ydegree is less than k.–Derivative formula(Derivative formula(导数公式)′′nn)()()(0,0,'===⎟⎠⎞⎜⎝⎛=∑∑i k i i i k i i t N P t N P t P ],[)()1(111,111+−−=−+−∈⎟⎟⎠⎞⎜⎜⎝⎛−−−=∑n k k i ni i k i i i t t t t N t t P PkProperties of B SplineProperties of B-Spline–Variation Diminishing Property(变差缩减性)•this means no straight line intersects a B-splinethi t i ht li i t t B licurve more times than it intersects the curve'scontrol polygons.t l l–Geometry invariability(几何不变性)•The shape and position of curve are independentwith the choosing of coordinate system(坐标系).Properties of B Spline Properties of B-Spline–Affine invariability(仿射不变性)nI h h f f i i i i bl d h∑=+−∈=i n k k i i t t t t N P A t P A 011,],[,)(][)]([•It means that the form of equation is invariable under the affine transformation.–Line holding(直线保持性)•It means that if the control polygon degenerates to a line,the B-Spline curve also degenerates to a line.Properties of B Spline Properties of B-Spline–Flexibility(灵活性)U i B S li C il t t•Using B-Spline Curve we can easily construct special cases such as line segment(线段), cusp(尖)t t li ()点), tangent line(切线).•For example, for B-Spline of order 4 (degree 3), if li l dyou want to construct a line segment, you only need to specify collinear (共线). 321,,,+++i i i i P P P P •you only need to let12i i i P P P ++==Properties of B Spline Properties of B-Spline相•If you want the curve tangent(相切) to a specific line L,you only need to specify on line L, and21,,++i i i P P P repetitiveness of less than 2.3+i t iP 1+i P 2+i P P )(tPP 4+i (a)四顶点共线(b)二重顶点和三重顶点−i P 23()重节点和三重节点(c)二重节点和三重节点(d)三顶点共线图.1.26 三次B样条曲线的一些特例De Boor Algorithm De Boor Algorithm•To compute P(t) (a point on the curve), you could use B-Spline formula, but it is more efficient to use de pBoor algorithm.De Boor Algorithm:•De Boor Algorithm:)()()(,,==∑∑jki ink i i t NP t N P t P 10−+−+−==⎤⎡−+−=jk i i k j i i t N tt t N t t P )()(111,111,1−++−=+++−+⎤⎡−−⎥⎦⎢⎣−−∑jk i i k j i k i i k i k i i k i i t t t t t t t t ],[)(11,1111+−+−=−−+−+∈⎥⎦⎢⎣−+−=∑j j k i k j i i i k i i i k i t t t t N P t t P t tDe Boor Algorithm De Boor Algorithm•Let⎧⋅⋅⋅+−+−==k k i r P ,,2,1,0,⎪⎪⎨−−+−−=−−−+−t P t t t t t P t t t t jj j t P r i r k i r i i i r i ),()()(]1[1]1[][•Then⎪⎪⎩⋅⋅⋅++−++−=−⋅⋅⋅=−+−+j r k j r k j i k r ir k i i r k i ,,2,1;1,,2,1∑∑−==jk i ijki it N t Pt NP t P 1,]1[,)()()()(•This is De Boor Algorithm.+−=+−=k j i k j i 21De Boor Algorithm De Boor Algorithm•The recursion of De Boor Algorithm is as shown below:01P P 1[1]j k P −+M 22[1][2]333j k j k j k j k j k P PP P P −+−+−+−+−+→→→[1][2][1]k j jjjP PPP−→→M M M M nP MDe Boor Algorithm De Boor Algorithm•Geometric meaning (几何意义)of De Boor Algorithm–It has an intuitive geometric interpretation: corner g pcutting (割角).•It means that using line segment to cut][][r r It means that using line segment to cut corner . Begin frompolygon1i i P P +]1[−r i P ⋅⋅⋅polygon , after k-1 steps of cutting, fi ll i j k j k j P P P +−+−21P −P P j we finally get point on the curve P(t).)(]1[t r j +−k j P −P]1[P 4+−k j 1+−k j 2+k j jKnot Insertion Knot Insertion •Knot insertion–An important tool for practical interactive use of B-p pspline, which allows one to add a new knot to a B-spline without changing the shape or its degree.For spline without changing the shape or its degree. For instance, one may want to insert additional knots in order to be able to raise flexibility of shape control order to be able to raise flexibility of shape control.•Insert a new knot t to a knot span Th k t t b[]1,+i i t t •The knot vector becomes:[]k n i i t t t t t t T ++=,,,,,,,1101L L •denoted as:[]11121111101,,,,,,,1++++=k n i i i tt t t t t T L LKnot Insertion Knot Insertion•The new knot sequence defines a new group of B-Spline Basis F nctions The original c r e Spline Basis Functions. The original curve P(t)can be expressed by this new group of BasisFunctions and new control points , which are unknown.1jP +=111n t N P t P ∑=0,)()(j kjjKnot Insertion Knot Insertion•Boehm gives a formula for computing new control points:p ⎪⎧+−==1,,1,0 ,11k i j P P j j L ββ⎪⎩⎨++−==−+−=+−=−−1,,1 ,,,2 ,)1(111n r i j P P r i k i j P P P j jj j j j j L L ββj t t −=β•r is the repetitiveness of newly inserted knot in the knot jk j j t t −−+1s t e epet t ve ess o ew y se ted ot t t e ot sequence.Knot Insertion Knot Insertion1P 1P P 1P 03i points(totally k-1points)36points( totally k 1 points) are replaced by the right ones(totally k points)],[43t t t ∈See demo of knot insertionB Spline Surface(B B-Spline Surface(B样条曲面)•Given knot vectors in axes(参数轴) U and V:],,,[10p m u u u U +=L B S li f f d i d fi d],,,[10q n v v v V +=L •B-Spline surface of order p ×q is defined as:m n∑∑===i j q j p i ij v N u N P v u P 00,,)()(),(B Spline Surface B-Spline Surface•are the control points of B-Splineij P Surface, which are usually referred to as thecontrol net ).(控制网格、特征网格)•and are B-Spline basis)(,u N p i )(,v N q j functions of order p and q , one for each direction (and ),which could also be direction (U and V ), which could also be computed by de Boor-Cox formula.B Spline Surface B-Spline Surface03P 23P33P02P 22P 12P32P01P 11P 21P 31P P 10P 20P 0030PNURBS Curve and SurfaceNURBS Curve and Surface •Disadvantage of B-Spline curve and Bezier Curve:–can’t accurately represent conic(圆锥曲线) curveexcept parabola(抛物线),NURBS (Non Uniform Rational B Spline) •NURBS(Non-Uniform Rational B-Spline) (非均匀有理B样条)–In order to find a mathematical method that couldrepresent conic and conicoid(二次曲面) accurately. yNURBS•NURBS is too complex•Les Piegl s The NURBS Book,Les Piegl’s The NURBS Book–“NURBS from Projective Geometry to Practical Use”–Les Piegl，Graduated from Budapest University ofi l d d f d i i fHungary, many years in SDRC company for geometricmodeler designd l d iNURBSSome years ago a few researchers joked about NURBS,saying that the acronym really stands for NOBODYUnderstands Rational B-Splines, write the authors in their foreword; they formulate the aim of changing NURBS to EURBS, that is, Everybody.…There is no doubt that they have achieved this goal....I highly recommend the book to anyone who is interestedp y p in a detailed description of NURBS. It is extremely helpful for students, teachers and designers of geometric modeling ysystems. ——Helmut PottmannNURBS•Advantages of NURBS–It provide a general and accurate representation forrepresenting and designing free curves or surfaces(自由曲线曲面)–They offer one common mathematical form for bothstandard analytical shapes (e.g., conics) and free-formshapes (parametric form).–can be evaluated reasonably fast by numerically stableand accurate algorithms;NURBS•Advantages of NURBS–They are invariant under affine as well as perspectivetransformations.–the control points and weights can be modified, whichgives great flexibility for designing curves/surfaces.–non-rational B-Spline, non-rational and rational Beziercould be viewed as special cases of NURBS.NURBS•Some difficult problems in using NURBS –Require more storage than traditionalcurve/spline methods. (such as circle representation) p–If the weights are set inappropriately, the curvewill be abnormal(畸变).will be abnormal()–It is very complex to deal with situations likecurve overlap(曲线重叠).NURBS •Before discussing about NURBS, let’s first review the definition of B-Spline:n∑==i k i i t N P t P 0,)()()()()(1,111,1,t N t t t t t N t t t t t N k i i k i k i k i i k i i k i −++++−−+−−+−−=k n k n n n k k t t t t t t t t +−++−,,,,,,,,,,11110L LLNURBS•Definition of NURBS curve.–NURBS Curves are defined by piecewiserational B-Spline polynomial basis functionp p y(分段有理B样条多项式基函数):∑== =nnikiiitNP,)(ω∑∑==ikiinikiitRPtNtP,0,)( )()(ω=nki ik itNtR, ,)()(ω∑=jkjjt N,)(ωDefinition of NURBS Definition of NURBS•NURBS basis R i,k (t) retains all properties of B-Spline Basis.–Local support: Ri,k(t)=0，t ∉[ti, ti+k]–Partition of Unity:∑n Partition of Unity:–Differentiability(可微性): If is not a knot is infinitely differentiable()==i k i u R 0,1)(•If t is not a knot, P(t)is infinitely differentiable(无限次可微) in the knot interval. If t is a knot, P(t) is only C-(k-r) continuous.continuous. –If ωi =0, then R i,k (t)=0;If +th R (t)1–If ωi =+∞, then R i,k (t)=1;Definition of NURBSDefinition of NURBS•NURBS curve has similar geometric properties as the B Spline C r e:the B-Spline Curve:–Local support (局部支持性).–Variation Diminishing Property(变差缩减性)–Strong Convex hull(凸包性)–Affine invariability(仿射不变性)–Differentiability(y(可微性)–If the weight of a control point is 0, then correspondingcontrol point doesn t affect the curve.control point doesn’t affect the curve.Definition of NURBS Definition of NURBS–If , and , then N i l/i l B i d ∞→i ω],[k i i t t t +∈i P t P =)(–Non-rational/rational Bezier curves and non-rational B-Spline curves are special cases ofNURBS curve.。
