Computer Aided Design Outline Interpolation and polynomial approximation  Interpolation  Lagrange  Cubic Splines  Approximation Bézier curves  B-Splines  1 Computer Aided Design Some vocabulary (again ;)  Control point : Geometric point that serves as  support to the curve Knot : a specific value of the parameter u  corresponding to a joint between pieces of a curve Knot sequence : the set of knots values (in an  increasing order). W o l f r a m r e s e a r c h 2 Computer Aided Design Interpolation  The curve passes through the control points  Approximation  The curve doesn't necessary passes through the  control points But these have an influence ...  Statistic approaches ?  Least squares  « Kriging »  Not very adapted to geometric modelling  3 Computer Aided Design Interpolation 4 Computer Aided Design Interpolation Interpolation We want draw a regular and smooth parametric  curve through a certain number n of points P i Several families of base functions are available  Most obvious are polynomials  There are others -  Trigonometric functions (by mean of a Fourier decomposition for  instance) Power functions  etc...  5 Computer Aided Design Interpolation We must choose the parametrization (nodal  sequence) Uniform u =2  2 u =1 1 u =0 0 u =n-1 n-1 6 Computer Aided Design Interpolation Or non-uniform u =7  2 u =2.5 1 u =0 0 u =15 n-1 7 Computer Aided Design Interpolation Can we choose u as a curvilinear abscissa ?  In principle no since we don't know the final shape  of the curve beforehand (with the exception of interpolation points) We will see later that it is often impossible that u  corresponds with s exactly along the whole curve using analytical functions. But nothing forbids to get close to that –  numerically... 8 Computer Aided Design Interpolation Parametrization as an approximate arc length  u =d +d 2 1 2 d 2 u =d 1 1 d u =0 1 0 d n-1 u =d +...+d n-1 1 n-1 9 Computer Aided Design Interpolation In all cases, we want to have :  { xu =x P u =P ≡ i i i i y u = y i i We are going to interpolate the functions x(u) and  y(u) with ONE polynomial with n parameters This one must be of order p=n-1 :  n−1 2 n−1 ∑ j x u=a a ua u ⋯a u = a u 0 1 2 n−1 j j=0 We set the linear system and solve...  { x u =x 1 1 ⋮ x u =x 10 n−1 n−1