13472J/1.128J/2158J/16940J COMPUTATIONAL GEOMETRY Lectures 4 and 5 N. M. Patrikalakis Massachusetts Institute of Technology Cambridge MA 02139-4307. USA Copyright 2003 Massachusetts Institute of Technology Contents 4 Introduction to Spline Curves 4.1 Introduction to parametric spline curves 4.2 Elastic deformation of a beam in bending 4.3 Parametric polynomial curves 4.3.1 Ferguson representation 4.3.2 Hermite- Coons curves 4.3.3 Matrix forms and change of basis 13. 4 bezier curves 4.3.5 Bezier surfaces 4.4 Composite curves 4.4.1 Motivation 2224457778889 4.4.3 Continuity conditions 4.4.4 Bezier composite curves(splines) 4.4.5 Uniform Cubic B-splines Bibliography Reading in the Textbook Chapter 1, pp
13.472J/1.128J/2.158J/16.940J COMPUTATIONAL GEOMETRY Lectures 4 and 5 N. M. Patrikalakis Massachusetts Institute of Technology Cambridge, MA 02139-4307, USA Copyright c 2003 Massachusetts Institute of Technology Contents 4 Introduction to Spline Curves 2 4.1 Introduction to parametric spline curves . . . . . . . . . . . . . . . . . . . . . . 2 4.2 Elastic deformation of a beam in bending . . . . . . . . . . . . . . . . . . . . . 2 4.3 Parametric polynomial curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 4.3.1 Ferguson representation . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 4.3.2 Hermite-Coons curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 4.3.3 Matrix forms and change of basis . . . . . . . . . . . . . . . . . . . . . . 7 4.3.4 B´ezier curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 4.3.5 B´ezier surfaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 4.4 Composite curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 4.4.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 4.4.2 Lagrange basis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 4.4.3 Continuity conditions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 4.4.4 B´ezier composite curves (splines) . . . . . . . . . . . . . . . . . . . . . . 20 4.4.5 Uniform Cubic B-splines . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 Bibliography 28 Reading in the Textbook • Chapter 1, pp.6 - pp.33 1
Lecture 4 Introduction to Spline Curves 4.1 Introduction to parametric spline curves Parametric formulation =r(u),y=y(u), z=2(u) or R=R(u)(vector notation) Usually applications need a finite range for u(e.g. 0<u<1) For free-form shape creation, representation, and manipulation the parametric representa tion is preferrable, see Table 1.2 in textbook. Furthermore, we will use polynomials for the following reasons Cubic polynomials are good approximations of physical splines. (Historical note: Shape of a long flexible beam constrained to pass through a set of points- Draftsman's Splines) Parametric polynomial cubic spline curves are the" smoothest"curves passing through a set of points; (i.e. they minimize the bending strain energy of the beam x Jo xds) 4.2 Elastic deformation of a beam in bending Within the Euler beam theory Center of curvature dA Length ds a中 Fiber igure 4.1: Differential segment of an Euler beam
Lecture 4 Introduction to Spline Curves 4.1 Introduction to parametric spline curves Parametric formulation x = x(u), y = y(u), z = z(u) or R = R(u) (vector notation) Usually applications need a finite range for u (e.g. 0 ≤ u ≤ 1). For free-form shape creation, representation, and manipulation the parametric representation is preferrable, see Table 1.2 in textbook. Furthermore, we will use polynomials for the following reasons: • Cubic polynomials are good approximations of physical splines. (Historical note: Shape of a long flexible beam constrained to pass through a set of points → Draftsman’s Splines). • Parametric polynomial cubic spline curves are the “smoothest” curves passing through a set of points; (i.e. they minimize the bending strain energy of the beam ∝ R L 0 κ 2ds). 4.2 Elastic deformation of a beam in bending Within the Euler beam theory: R y dA dA N.A. y Fiber Length ds d Center of curvature ✁✁✁ ✁✁✁ ✂✁✂✁✂✁✂ ✂✁✂✁✂✁✂ Figure 4.1: Differential segment of an Euler beam. 2
Plane sections of the beam normal to the neutral axis(N A remain plane and normal to the neutral axis after deformation Elongation strain of a fiber at distance y above the NA (y+ r)do-rdo y The radius of curvature can be related to the differential angle and arc length Bdb=ds→k=1=2 The stress experienced by a fiber at distance y from the N. A can be found from Hooke's law relating stress and strain g= E y The bending moment about the N.A. can be calculated by integrating the stress due to bending times the moment arm over the surface of the cross-section Loya=R/dA=-EL ds =-EI For small deflections, the displacement Y= Y() of the N.A., the following approxima tions can be made d 2 ds ds dr2 e Therefore M (4.1) Consider a beam with simple supports and no distributed loads, as shown in Figure 4.2. Figure 4.2: Simply supported beam Looking at a section of the beam between two supports(Figure 4.3), the bending moment can be expressed as a linear equation M=Ao+Ala where Ao and Al are the bending moment and shearing force at a =0 in Figure 4.3
• Plane sections of the beam normal to the neutral axis (N.A.) remain plane and normal to the neutral axis after deformation. • Elongation strain of a fiber at distance y above the N.A.: = (−y + R)dφ − Rdφ Rdφ = − y R • The radius of curvature can be related to the differential angle and arc length: Rdφ = ds ⇒ κ = 1 R = dφ ds • The stress experienced by a fiber at distance y from the N.A. can be found from Hooke’s law relating stress and strain. σ = E = −E y R • The bending moment about the N.A. can be calculated by integrating the stress due to bending times the moment arm over the surface of the cross-section: M = Z A σydA = − E R Z A y 2 dA = −EI 1 R = −EI dφ ds = −EIκ. • For small deflections, the displacement Y = Y (x) of the N.A., the following approximations can be made: φ ≈ dY dx , ds ≈ dx, dφ ds ≈ d 2Y dx2 • Therefore, − M EI ≈ d 2Y dx2 (4.1) • Consider a beam with simple supports and no distributed loads, as shown in Figure 4.2. Figure 4.2: Simply supported beam. Looking at a section of the beam between two supports (Figure 4.3), the bending moment can be expressed as a linear equation: M = A0 + A1x (4.2) where A0 and A1 are the bending moment and shearing force at x = 0 in Figure 4.3. 3
Figure 4.3: Section of simply supported beam between pins. The shear force and bending moment at the ends of the section are illustrated Upon substituting Equation 4.2 into Equation 4.1 and integrating, we get dy AoI+A Y()Co+C1C+C2:c-+C3c(cubic) Therefore, in order to replicate the shape of physical splines, the CAd community developed shape representation methods based on cubic polynomials Generically, polynomials have the following additional advantages easy to store as sequences of coefficients efficient to compute and trace efficiently easy to differentiate, integrate, and adapt to matrix and vector algebra; and easy to piece together to construct composite curves with a certain order of continuity, a feature important in increasing complexity of a curve or surface 4.3 Parametric polynomial curves 4.3.1 Ferguson representation In 1963, Ferguson at boeing developed a polynomial representation of space curves R(u)=a+a1+a22+a3n3 where< us l by convention. Note there are 12 coefficients, ai, defining the curve r(u) This representation is also known as the power basis or monomial forn The coefficients, ai, are difficult to interpret geometrically, so we can express ai in terms of R(O, R(1), R(O, and R(I)(where R denotes derivative with respect to u R(1) a0+a1+a2+a3 R(O) R(1
x A0 A1 A1 M(x) Figure 4.3: Section of simply supported beam between pins. The shear force and bending moment at the ends of the section are illustrated. • Upon substituting Equation 4.2 into Equation 4.1 and integrating, we get: φ ∼= dY dx ∼= − 1 EI [A0x + A1 x 2 2 ] + A2 Y (x) ∼= C0 + C1x + C2x 2 + C3x 3 (cubic) Therefore, in order to replicate the shape of physical splines, the CAD community developed shape representation methods based on cubic polynomials. Generically, polynomials have the following additional advantages: • easy to store as sequences of coefficients; • efficient to compute and trace efficiently; • easy to differentiate, integrate, and adapt to matrix and vector algebra; and • easy to piece together to construct composite curves with a certain order of continuity, a feature important in increasing complexity of a curve or surface. 4.3 Parametric polynomial curves 4.3.1 Ferguson representation In 1963, Ferguson at Boeing developed a polynomial representation of space curves: R(u) = a0 + a1u + a2u 2 + a3u 3 (4.3) where 0 ≤ u ≤ 1 by convention. Note there are 12 coefficients, ai , defining the curve R(u). This representation is also known as the power basis or monomial form. The coefficients, ai , are difficult to interpret geometrically, so we can express ai in terms of R(0), R(1), R˙ (0), and R˙ (1) (where R˙ denotes derivative with respect to u): R(0) = a0 R(1) = a0 + a1 + a2 + a3 R˙ (0) = a1 R˙ (1) = a1 + 2a2 + 3a3 4
Solving the above equations yields expression for the coefficients, ais, in terms of the geometric end conditions of the curve. a0= R(O R(0 3R(1)-R(O)]-2R(0)-R(1) a3=2R(0)-R(1)+R(0)+R(1) 4.3.2 Hermite-Coons curves By substituting the coefficients into the Ferguson representation, we can rewrite Equation 4.3 R(u)=R(0)(t)+R(1)mn(u)+R(0)m2(u)+R(1)(u) (4.4) 0( n(a)=3x2-23 m(u)=u-2n2+u3 The new basis functions, ni(u), are known as Hermite polynomials or blending functions see Fi igure 4 ere first used for 3D curve representation in a computer environ the 60,s by the late Steven Coons, an MIT professor, participant in the famous ARPa project MAC 1.0 7 0.0 72 0.0 Figure 4. 4 Plot of hermite basis functions Note that these basis functions, ni(u), satisfy the following boundary conditions, see Fig- 7()=1,m(1)=m0(0)=m6(1)=0; mn(1)=1,m(0)=mh(0)=m1(1)=0; n2(0)=1,m2(0)=n(1)=m2(1)=0; n3(1)=1,m3(O)=n(0)=3(1)=0. These boundary conditions also allow the computation of the cubic Hermite polynomials, ni(u), by setting up and solving a system of 16 linear equations in the coefficients of these
Solving the above equations yields expression for the coefficients, ai ’s, in terms of the geometric end conditions of the curve. a0 = R(0) a1 = R˙ (0) a2 = 3[R(1) − R(0)] − 2R˙ (0) − R˙ (1) a3 = 2[R(0) − R(1)] + R˙ (0) + R˙ (1) 4.3.2 Hermite-Coons curves By substituting the coefficients into the Ferguson representation, we can rewrite Equation 4.3 as: R(u) = R(0)η0(u) + R(1)η1(u) + R˙ (0)η2(u) + R˙ (1)η3(u) (4.4) where η0(u) = 1 − 3u 2 + 2u 3 η1(u) = 3u 2 − 2u 3 η2(u) = u − 2u 2 + u 3 η3(u) = u 3 − u 2 The new basis functions, ηi(u), are known as Hermite polynomials or blending functions, see Figure 4.4. They were first used for 3D curve representation in a computer environment in the 60’s by the late Steven Coons, an MIT professor, participant in the famous ARPA project MAC. 0.0 1.0 0.0 1.0 0 1 2 3 Figure 4.4: Plot of Hermite basis functions. Note that these basis functions, ηi(u), satisfy the following boundary conditions, see Figure 4.4: η0(0) = 1, η0(1) = η 0 0 (0) = η 0 0 (1) = 0; η1(1) = 1, η1(0) = η 0 1 (0) = η 0 1 (1) = 0; η 0 2 (0) = 1, η2(0) = η 0 2 (1) = η 0 2 (1) = 0; η 0 3 (1) = 1, η3(0) = η 0 3 (0) = η 0 3 (1) = 0. These boundary conditions also allow the computation of the cubic Hermite polynomials, ηi(u), by setting up and solving a system of 16 linear equations in the coefficients of these polynomials. 5
Geometric Interpretation of Hermite-Coons curves If we make the following substitutions R O R(1)=a1t(1) where t(a) is the unit tangent of the curve, the following observations can be made from Figure 4.5, relating the coefficients ao and an to the shape of the curve const= bias towards t(O) ·a1↑,ao= const→ bias towards t(1) a0,a1↑→ increase fullness ao, a1 both LARGE cusp forms(R(u)=0) or self-intersection occurs ao Increasing t(1) R(0) R(1) a0, a1 Increasing simultaneously R(1) R(0) t(1) Figure 4.5: Fullness of a Hermite-Coons curve Due to the importance of choosing ao and an appropriately, the Hermite-Coons represen- tation can be difficult for designers to use efficiently, but is much easier to understand than the Ferguson or monomial forn
Geometric Interpretation of Hermite-Coons curves. If we make the following substitutions: R˙ (0) = α0t(0) R˙ (1) = α1t(1) where t(u) is the unit tangent of the curve, the following observations can be made from Figure 4.5, relating the coefficients α0 and α1 to the shape of the curve: • α0 ↑, α1 = const ⇒ bias towards t(0) • α1 ↑, α0 = const ⇒ bias towards t(1) • α0, α1 ↑ ⇒ increase fullness • α0, α1 both LARGE ⇒ cusp forms (R˙ (u ∗ ) = 0) or self-intersection occurs R(1) t(0) R(0) t(1) simultaneously α0, α1 increasing α1 constant α0 increasing t(1) t(0) R(0) R(1) Figure 4.5: Fullness of a Hermite-Coons curve. Due to the importance of choosing α0 and α1 appropriately, the Hermite-Coons representation can be difficult for designers to use efficiently, but is much easier to understand than the Ferguson or monomial form. 6
4.3.3 Matrix forms and change of basis Monomial or Power or Ferguson form R() =U·F M 33-2-1R() 0010 R(0) 1000 R(1) Conversion between the two representations is simply a matter of matrix manipulation U·F U·MH·FH F MH·F FH Ma·F 4.3, 4 Bezier curves Bezier developed a reformulation of Ferguson curves in terms of Bernstein polynomials for the UNISURF System at Renault in France in 1970. This formulation is expressed mathematically as follows R(u)=∑RBn()0≤u≤1 Ri and Bi, n(u) represent polygon vertices and the Bernstein polynomial basis functions respec tively. The definition of a Bernstein polynomial is Bi n(u) u2(1-u)-i=0,1,2, il(n-i) The polygon joining Ro, R1,..., Rn is called the control polygon Examples of Bezier curve n=2: Quadratic Bezier Curves(Parabola), see Figures 4.6 and Figure 4.7 R(u)=Ro(1-)2+R12u(1-)+R2 220R 00R2
4.3.3 Matrix forms and change of basis • Monomial or Power or Ferguson form R(u) = h u 3 u 2 u 1 i a3 a2 a1 a0 = U · FM • Hermite-Coons R(u) = h u 3 u 2 u 1 i 2 −2 1 1 −3 3 −2 −1 0 0 1 0 1 0 0 0 R(0) R(1) R˙ (0) R˙ (1) = U · MH · FH Conversion between the two representations is simply a matter of matrix manipulation: U · FM = U · MH · FH Hence, FM = MH · FH FH = M−1 H · FM 4.3.4 B´ezier curves B´ezier developed a reformulation of Ferguson curves in terms of Bernstein polynomials for the UNISURF System at Renault in France in 1970. This formulation is expressed mathematically as follows: R(u) = Xn i=0 RiBi,n(u) 0 ≤ u ≤ 1 Ri and Bi,n(u) represent polygon vertices and the Bernstein polynomial basis functions respectively. The definition of a Bernstein polynomial is: Bi,n(u) = n i ! u i (1 − u) n−i i = 0, 1, 2, ...n where n i ! = n! i!(n − i)! The polygon joining R0, R1, ..., Rn is called the control polygon. Examples of B´ezier curves: • n=2: Quadratic B´ezier Curves (Parabola), see Figures 4.6 and Figure 4.7 R(u) = R0 (1 − u) 2 + R1 2u(1 − u) + R2 u 2 = h u 2 u 1 i 1 −2 1 −2 2 0 1 0 0 R0 R1 R2 7
B 0.0 0.0 1.0 Figure 4.6: Plot of the quadratic Bernstein basis functions. R Figure 4.7: Illustration of end conditions for a quadrati er curve n=3: Cubic Bezier Curves, see Figures 4.8 and 4.9 R(u)=R(1-x)3+R13(1-)2+R23x2(1-)+R3 3 300 R 0R oR Interpolation of Ro, Rn and tangency of curve with polygon at u=0, 1 The Bezier curve approximates and smooths control polygon Properties of Bernstein polynomials 1. Positivity B;n(u)≥0in0≤a≤1
0.0 0.0 1.0 1.0 i=0 u Bi,2(u) i=2 i=1 Figure 4.6: Plot of the quadratic Bernstein basis functions. u = 1 u = 0 R2 R1 R0 Figure 4.7: Illustration of end conditions for a quadratic B´ezier curve. • n=3: Cubic B´ezier Curves, see Figures 4.8 and 4.9 R(u) = R0 (1 − u) 3 + R1 3u(1 − u) 2 + R2 3u 2 (1 − u) + R3 u 3 = h u 3 u 2 u 1 i −1 3 −3 1 3 −6 3 0 −3 3 0 0 1 0 0 0 R0 R1 R2 R3 • Interpolation of R0, Rn and tangency of curve with polygon at u = 0, 1: • The B´ezier curve approximates and smooths control polygon. Properties of Bernstein polynomials 1. Positivity Bi,n(u) ≥ 0 in 0 ≤ u ≤ 1 8
B3() 2 0.0 0.0 1.0 Figure 4.8: Plot of the cubic bernstein basis functions 2. Partition of unity Eio Bi n(u)=[1-u+un=l(by the binomial theorem) Bi n(u) (1-u)B1,n-1()+uB2-1,n-1() ith Bi n(u)=0 for i<0. and Boo(u)=1 4. Linear Precision Property ∑=B,n(u) onversion of explicit curves to parametric Bezier curves Parametrization of straight lines y(a) 5. Degree elevation: The basis functions of degree n can be expressed in terms of those degree n+1 as +1 B1+1m+1(x),i=0,1 +1 6. Symmetry Bi, n(u)= Bn-i,n(1-u 7. Derivative B(u) =n[Bi-In-1(u)-Bin-Iu) where B-1n-1(u)=B,, n-1(u)=0 8. Basis conversion (for each of the y, a, coordinates Ferguson or monomial form f 2 u 1- a f1 f
0.0 0.0 1.0 1.0 u i=3 i=2 i=1 i=0 Bi,3(u) Figure 4.8: Plot of the cubic Bernstein basis functions. 2. Partition of unity Pn i=0 Bi,n(u) = [1 − u + u] n = 1 (by the binomial theorem) 3. Recursion Bi,n(u) = (1 − u)Bi,n−1(u) + uBi−1,n−1(u) with Bi,n(u) = 0 for i n and B0,0(u) = 1 4. Linear Precision Property u = Xn i=0 i n Bi,n(u) • Conversion of explicit curves to parametric B´ezier curves. • Parametrization of straight lines y = y(x) → x = u; y = y(u) 5. Degree elevation: The basis functions of degree n can be expressed in terms of those of degree n + 1 as: Bi,n(u) = 1 − i n + 1 Bi,n+1(u) + i + 1 n + 1 Bi+1,n+1(u), i = 0, 1, · · · , n 6. Symmetry Bi,n(u) = Bn−i,n(1 − u) 7. Derivative B0 i,n(u) = n[Bi−1,n−1(u) − Bi,n−1(u)] where B−1,n−1(u) = Bn,n−1(u) = 0 8. Basis conversion (for each of the x, y, z, coordinates) • Ferguson or monomial form: f(u) = X 3 i=0 fiu i = h u 3 u 2 u 1 i f3 f2 f1 f0 = U · FM 9
RI/ R R R R R Figure 4.9: Examples of cubic Bezier curves approximating their control polygons . Hermite form f(u)= U·M·F f(0) . bezier form Fo f(u)=x32u1 F1 MB:F2 =U·Mp·F F3 Conversion between form U·FM=U.MH·FH=U·MB·FB →F FH=MB·F or→FH=Mn1FM=Mn·MB·FB
R0 X R3 R2 R1 R0 R1 R3 R2 R1 R0 R3 R2 R3 R2 R1 R0 X Figure 4.9: Examples of cubic B´ezier curves approximating their control polygons. • Hermite form: f(u) = h u 3 u 2 u 1 i · MH · f(0) f(1) ˙f(0) ˙f(1) = U · MH · FH • B´ezier form: f(u) = h u 3 u 2 u 1 i · MB · F0 F1 F2 F3 = U · MB · FB • Conversion between forms: U · FM = U · MH · FH = U · MB · FB ⇒ FM = MH · FH = MB · FB or ⇒ FH = M−1 H · FM = M−1 H · MB · FB etc. 10
