《Computational Geometry》lecnotes 8 N.M. Patrikalakis

13472J/1.128J/2158J/16940J COMPUTATIONAL GEOMETRY Lecture 8 N.M. Patrikalakis Massachusetts Institute of Technology Cambridge MA 02139-4307 USA Copyright 2003 Massachusetts Institute of Technology Contents 8 Fitting, Fairing and Generalized Cylinders 8. 1 Least Squares Method of Curve Fitting 8.2 Fairing of Curves and Surfaces 8.2.1 Properties and Definition 8.2.2 Curve Interrogation 224455 8.2.3 Fairing Methods 8.2.4 Surface Fairin 8.3 Generalized Cylinders: Motivation and Definitions 12 8.3.1 Applications 8.3.2 Definition 8.4 Degeneracies of Generalized Cylinders 8.5 Properties of Generalized Cylinders 8.6 Discrete Generalized Cylinders Bibliography 22 Reading in the Textbook Chapter 11, pp. 353-365

13.472J/1.128J/2.158J/16.940J COMPUTATIONAL GEOMETRY Lecture 8 N. M. Patrikalakis Massachusetts Institute of Technology Cambridge, MA 02139-4307, USA Copyright ≥c 2003 Massachusetts Institute of Technology Contents 8 Fitting, Fairing and Generalized Cylinders 2 8.1 Least Squares Method of Curve Fitting . . . . . . . . . . . . . . . . . . . . . . 2 8.2 Fairing of Curves and Surfaces . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 8.2.1 Properties and Definition . . . . . . . . . . . . . . . . . . . . . . . . . . 4 8.2.2 Curve Interrogation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 8.2.3 Fairing Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 8.2.4 Surface Fairing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 8.3 Generalized Cylinders: Motivation and Definitions . . . . . . . . . . . . . . . . 12 8.3.1 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 8.3.2 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 8.4 Degeneracies of Generalized Cylinders . . . . . . . . . . . . . . . . . . . . . . . 16 8.5 Properties of Generalized Cylinders . . . . . . . . . . . . . . . . . . . . . . . . 20 8.6 Discrete Generalized Cylinders . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 Bibliography 22 Reading in the Textbook • Chapter 11, pp. 353 - 365 1

Lecture 8 Fitting, Fairing and generalized Cylinders 8.1 Least Squares Method of Curve Fitting Given N points Pi, i= 1, 2,.,N(N> 4), construct an approximating cubic Bezier curve that interpolates PI and PN(end points Solution 1. Parametrization by chord-length method Let (8.1) where di+1=Pi+1-Pil is the chord length between two consecutive points. The overall chord length is d d (8.2) The parametric value associated with point Pi which is normalized as u; E[0, 1] with u=0 uN 2.L is defined Q(u)=∑QB13(u),0≤u≤1 where Bi3(u) are the cubic Bernstein polynomials

� � Lecture 8 Fitting, Fairing and Generalized Cylinders 8.1 Least Squares Method of Curve Fitting Example problem Given N points Pi, i = 1, 2, ..., N (N � 4), construct an approximating cubic B´ezier curve that interpolates P1 and PN (end points). Solution 1. Parametrization by chord-length method Let uˆ1 = 0; uˆ ˆ i+1 = ui + di+1, i = 1, 2, ..., N − 1 (8.1) where di+1 = |Pi+1 − Pi| is the chord length between two consecutive points. The overall chord length is N d = di (8.2) i=2 The parametric value associated with point Pi ui = uˆi/d (8.3) which is normalized as ui � [0, 1] with u1 = 0 and uN = 1. 2. Linear equations A cubic B´ezier curve is defined as 3 Q(u) = QiBi,3(u), 0 � u � 1 (8.4) i=0 where Bi,3(u) are the cubic Bernstein polynomials. 2

Obviously, the boundary conditions require Qo= P1, Q3= PN. The problem is then represented as a linear system with N-2 equations and 2 unknowns Q: Bi,3(ui)=P,-P1Bo,(ui)-PNB3,3(u i=1 2,3,…N-1 (8.5) or in matrix form B(N-2)×2·q2x1=1(x-2)×1 (8.6) 3. Least Squares Method Define the mean square error as (8.7) then E 1)(B·q-1) BB Bl (8.8) is a function of q and is minimized if we set B Bq-Bl=0 (8.9) *B Bq=B 1(normal equations) (8.10 + q=(BB)-B 1(formal solution) (8.11) The extension to fitting with B-splines is similarly formulated. 1. The choice of internal knots in the B-spline basis should reflect any knowledge of deriva tive discontinuity in the data, as shown in Figure 8.1 2. Greater density of knots is needed in rapidly changing parts of the shape 3. NAG routines for approximate fitting of cubic B-splines [9 (a)Curves: E02BAF (b)Surfaces: E02DAF E02ZAF 4. NAG routines on least square problems provide more flexibility

� Obviously, the boundary conditions require Q0 = P1, Q3 = PN . The problem is then represented as a linear system with N − 2 equations and 2 unknowns: 2 QiBi,3(uj) = Pj − P1B0,3(uj) − PN B3,3(uj) i=1 = Lj , j = 2, 3, ..., N − 1 (8.5) B or in matrix form (N−2)×2 · q2×1 = l(N−2)×1 (8.6) 3. Least Squares Method Define the mean square error as E2 = |B · q − l| 2 (8.7) then E2 = (B · q − l) T (B · q − l) = qT BT Bq − 2qT BT l + l T l (8.8) is a function of q and is minimized if we set θE2 = 0 ≤ BT Bq − BT l = 0 (8.9) θq ≤ BT Bq = BT l (normal equations) (8.10) ≤ q = (BTB) −1 BT l (formal solution) (8.11) The extension to fitting with B-splines is similarly formulated. Notes: 1. The choice of internal knots in the B-spline basis should reflect any knowledge of deriva￾tive discontinuity in the data, as shown in Figure 8.1. 2. Greater density of knots is needed in rapidly changing parts of the shape. 3. NAG routines for approximate fitting of cubic B-splines [9] (a) Curves: E02BAF (b) Surfaces: E02DAF & E02ZAF 4. NAG routines on least square problems provide more flexibility. 3

Double knot for cubics Figure 8.1: Set of data reflecting a possible discontinuity of tangent vector 8.2 Fairing of Curves and Surfaces 8.2.1 Properties and Definition Motivation 1. Spline curves resulting from (a)interpolation of points (b) manipulation of polygon, usually need fairing 2. Screen plots( small resolution )are misleading concerning curve quality 3. Full scale plots 4. Curvature plots are useful as they allow isolation of problem areas on raster devices Properties of fair curves: [3, 4 1. Curvature continuity( C2) 2. Curvature is almost piecewise linear with as few spans as possible For cubics with simple knots, property(1)is automatically satisfied. If R(t)is reasonably parametrized, IR'(t)I is constant, and the curvature k(s)=R()×R"(l R'(t)3 CR(t) Property(2)thus requires that R (t)I be almost piecewise linear. That means that R"(t)needs to be constant, which leads to the following definition of fairness Definition: Q, R are two C cubic splines in t E a, b. Q is fairer than R if for r E a, Q"(r+)-Q(r-)2≤[R If r is a knot at which interpolation of data occurs, the above expression means that reducing "shear"forces from supports increases the fairness of splines, if we consider geometric splines as approximations of physical splines

Double knot for cubics Figure 8.1: Set of data reflecting a possible discontinuity of tangent vector. 8.2 Fairing of Curves and Surfaces 8.2.1 Properties and Definition Motivation: 1. Spline curves resulting from (a) interpolation of points; (b) manipulation of polygon, usually need fairing. 2. Screen plots ( small resolution ) are misleading concerning curve quality. 3. Full scale plots. 4. Curvature plots are useful as they allow isolation of problem areas on raster devices. Properties of fair curves: [3, 4] 1. Curvature continuity ( C2 ). 2. Curvature is almost piecewise linear with as few spans as possible. For cubics with simple knots, property (1) is automatically satisfied. If R(t) is reasonably parametrized, |R� (t)| is constant, and the curvature ρ(s) = |R� (t) × R��(t)| |R� (t)|3 ∈ |R��(t)| (8.12) Property (2) thus requires that |R��(t)| be almost piecewise linear. That means that R���(t) needs to be constant, which leads to the following definition of fairness. Q Definition: Q, R are two C2 cubic splines in t � [a, b]. Q is fairer than R if for r � [a, b], ��� +) − Q��� +) − R��� [ (r (r−)]2 � [R���(r (r−)]2 (8.13) If r is a knot at which interpolation of data occurs, the above expression means that reducing “shear” forces from supports increases the fairness of splines, if we consider geometric splines as approximations of physical splines. 4

8.2.2 Curve Interrogation We interrogate the fairness of a spline curve by looking into the planar projection of their curvature. The signed curvature is defined as (x2+y2) and it is easy to point out the changes of sign( inflections). The curve is fair if a plot of r(u), hich is made up of a few monotone segments, is continuous. The aim of the fairing process is to locate the places of maximum discontinuity of n'(u)and fair those places(see figure(8.2)) k(u) Fair here Figure 8.2: Plot of curvature k(a) along curve as a function of u 8.2.3 Fairing Methods Assume that we have a spline curve obtained by interpolation of measured data. The curve generally has unwanted behavior. Curve fairing eliminates imperfections by changing data within a measurement tolerance 1. Kjellander's Method 7 P (a) Obtain data points F/(t),1≤j≤N (b) Fit the points with a spline R(t) (c)Find the knot where macR"(t#)-R"(t )l occurs and attempt fairing at P,where j=J corresponds to the worst jump (d) Using Hermite or Bezier, construct cubic interpolation Q(t), which interpolates R(t1-1)=P R P J+ (8.16) R'(t1-1),R(t+1) (8.17)

� �� 8.2.2 Curve Interrogation We interrogate the fairness of a spline curve by looking into the planar projection of their curvature. The signed curvature is defined as x��y� − x y ρ(u) = (8.14) 3 (x�2 + y�2) 2 and it is easy to point out the changes of sign ( inflections ). The curve is fair if a plot of ρ(u), which is made up of a few monotone segments, is continuous. The aim of the fairing process is to locate the places of maximum discontinuity of ρ� (u) and fair those places (see figure (8.2)). κ(u) u Fair here Figure 8.2: Plot of curvature ρ(u) along curve as a function of u. 8.2.3 Fairing Methods Assume that we have a spline curve obtained by interpolation of measured data. The curve generally has unwanted behavior. Curve fairing eliminates imperfections by changing data within a measurement tolerance. 1. Kjellander’s Method [7] Procedure (a) Obtain data points Pj(tj ), 1 � j � N. (b) Fit the points with a spline R(t). + j )−R���(t − (c) Find the knot where max|R���(t j )| occurs and attempt fairing at PJ where j = J corresponds to the worst jump. (d) Using Hermite or B´ezier, construct cubic interpolation Q(t), which interpolates R(tJ−1) = PJ−1 (8.15) R(tJ+1) = PJ+1 (8.16) R� (tJ−1) , R� (tJ+1) (8.17) 5