G22.3033-002: Topics in Computer Graphics: Lecture #2Geometric ModelingNew York UniversityBezier Curves and B-splines, BlossomingLecture #2: 16 September 2002Lecturer: Prof. Denis ZorinScribe: Kranthi K GadeIn this lecture, we discuss polynomial parametric curves, which is the most commonly usedtype of curves in geometric modeling. We consider two ways of representing such curves whichare useful for computational purposes viz., Bezier and B-spline curves. We also discuss someproperties of Bezier and B-spline curves.Representation of CurvesFor computational purposes, we need to represent curves in some form. The most commonlyused representation is the parametric representation. As we have seen in the previous lecture,parametric method is to represent the curve in the form of a function of one parametery(t):R → Rn,n=2, 3,...It would be good if the function y(t) is simple because using arbitrary functions which canbe obtained say by composition of commonly used elementary functions is computationallyexpensive. So we look for class of functions which is as simple as possible and yet diverseenough to represent a wide variety of curves. Polynomial functions to large extent satisfy thisrequirement. A general polynomial function is represented in the following way:y(t)=ni=0aitiwhere n is the degree of the polynomial.The variety of curves that you can obtain using polynomials depends on the maximum al-lowed degree. The higher the degree, the greater variety of shapes one can represent. Forexample, to define a curve with n wiggles, we need a polynomial of degree n +1. But higherdegrees result in some problems. The computational complexity of maintaining the curve in-creases with increasing degree. The higher the degree of a curve, the less controllable it is,in a sense that small changes in coefficients are likely to result in large changes in the shapeof the curve. Furthermore, the curves of high degree are more likely to develop “bumps” inunpredictable when the shape of the curve is changed.Let us try to figure out what is the minimal degree we can get away with. For simplicity, letus consider the functional case only. Degree 1 polynomials can only be used to represent straightlines; degree 2 curves are parabolas in non-degenerate cases. The problem with parabola is thatit does not have a point of inflection, where the curve turns from being concave to convex orvice-versa, and hence a curve with point of inflection cannot be represented using a degree 2polynomial; we can stitch several degree 2 polynomials together, but at inflection points the2G22.3033-002: Lecture #2curvature is likely to be discontinuous unless it is zero. Cubics on the other hand may havepoints of inflection with curvature changing continuously.To represent arbitrarily complex curves one usually uses piecewise polynomials, stitchingtogether many polynomial pieces.The next question we need to address is how to specify polynomial curves. The moststraightforward approach is to define a curve using the polynomial coefficients. For example, atwo-dimensional curve can be represented using polynomials in the following way:y(t)=a0+ a1t + a2t2+ a3t3where ai’s are two-dimensional points. One can see that y(t) is the weighted average ofa0,a1,a2,a3but it is not intuitively clear though how y(t) is traversed as t changes, and how aiinfluence the shape of y(t).Bezier CurvesOne can make the coefficients describing a polynomial more intuitive by changing the basisfunctions. Instead of using the standard monomial basis [1,t,t2,t3], we use the Bernstein basis:[(1 − t)3, 3t(1 − t)2, 3t2(1 − t),t3]. One way to derive this set of basis function is to look at theexpansion of 13:1=(1− t + t)3=(1− t)3+3t(1 − t)2+3t2(1 − t)+t3(1)Why this basis? We shall see that Bezier curves have a number of nice properties. Bernsteinbasis is defined for any n.Forn =1, the Bernstein basis is [(1 − t),t] and for n =2it is[(1 − t)2, 2t(1 − t),t2]. The Bernstein basis for n =3are shown in Figure 1.Any polynomial can be written as a combination of the four polynomials of the Bernsteinbasis. If p0,p1,p2,p3are four points in space, then the cubic polynomial curvep3(t)=3i=0piB3,i(t) (2)where B3,iis the ith Bernstein polynomial is called acubic Bezier curve with control points p0,...p3.Properties of cubic Bezier curves1. Interpolation. One can easily see that p3(0) = p0and p3(1) = p3, i.e. the Bezier curvep3(t) interpolates the points p0,and p32. Affine Invariance. This property can be easily verified by considering an affine mapΦ(x)=Ax + v where A is a 3 × 3 matrix and v is in R3.Now3i=0Φ(pi)B3,i(t)=3i=0(Api+ v)B3,i)(t)=A3i=0piB3,i(t)+v =Φ(3i=0piB3,i(t))The last transformation uses the fact that Bernstein basis functions sum up to one (1).G22.3033-002: Lecture #23011B3,0B3,1B3,2B3,3Figure 1: Bernstein basis functions for n =3Figure 2: Bezier Interpolation3. Tangent to the curve at point p0is the vector ¯p0p1and tangent to the curve at p3is ¯p2p3.This can be easily verified by differentiating (2) and substituting appropriate parametervalues: t =0for p0and t =1for p3. This property can be used to test whether twoBezier curves are joined smoothly: use this property to find the tangents at the commonpoint and then see whether they are parallel.4. Convex Hull. It is clear that B3,i(t) ≥ 0 for t ∈ [0, 1]. This and (1) means that all pointson the Bezier curve lie inside the convex hull of points p0...p3.Polar forms and blossomingPolar form of a polynomial of P (t):R → R of degree n is a multiaffine symmetric functionP (t1,t2,...,tn):Rn→ R such thatP (t,t,...,t  n)=P (t) (3)We focus on the case n =3. The two properties of polar forms are defined as follows:4G22.3033-002: Lecture #2Figure 3: Blossoming for Bezier curves.• A function f (t1,...,tn) is symmetric if the value of the function is the same for anypermutation of the arguments t1,...tn.• A function f (t1,...,tn) is multiaffine if for any arguments t1,...t0j,t1j,...tnand any af(t1,...,at0j+(1−a)t1j,...tn)=af(t1,...t0j,tj+1,...tn)+(1−a)f(t1,...,t1j,...,tn)For any polynomial, there exists a unique symmetric and multiaffine polar form. We donot give a formal proof for it but an intuition behind it for the case n =3will make it clear.Because the polar form is multiaffine it is linear in each argument; therefore it is a polynomialin t1, t2, t3, of total power 3 as it follows from (3). Therefore the polar form can be expressedas b0+ b11t2+