Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

A study of B-splines and their applications to surface design and manufacture Bedi, Sanjeev 1983

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

Download

Media
831-UBC_1984_A7 B43.pdf [ 3.92MB ]
Metadata
JSON: 831-1.0080806.json
JSON-LD: 831-1.0080806-ld.json
RDF/XML (Pretty): 831-1.0080806-rdf.xml
RDF/JSON: 831-1.0080806-rdf.json
Turtle: 831-1.0080806-turtle.txt
N-Triples: 831-1.0080806-rdf-ntriples.txt
Original Record: 831-1.0080806-source.json
Full Text
831-1.0080806-fulltext.txt
Citation
831-1.0080806.ris

Full Text

A STUDY OF B-SPLINES AND THEIR APPLICATIONS TO SURFACE DESIGN AND MANUFACTURE by SANJEEV BEDI Bachelor of Technology-Indian Institute of Technology Kanpur, India 1982 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF APPLIED SCIENCE in THE FACULTY OF GRADUATE STUDIES Department of Mechanical Engineering We accept this thesis as conforming to the required standard THE UNIVERSITY OF BRITISH COLUMBIA MARCH, 1984 © Sanjeev Bedi, 1984 In presenting this thesis in partial fulfillment of the requirements for an advanced degree at the University of British Columbia, I agree that the Library shall make i t freely available for reference and study. I further agree that permission for extensive copying of this thesis for scholarly purposes may be granted by the Head of my Department or by his or her representatives. It is understood that copying or publication of this thesis for financial gain shall not be allowed without my written permission. Department of Mechanical Engineering The University of British Columbia 2075 Wesbrook Place Vancouver Canada V6T 1W5 Date: March 7, 1984. ABSTRACT Compound curved s u r f a c e s are f r e q u e n t l y encountered i n engineering applications, such as marine pr o p e l l e r s , turbines, ship h u l l s , aeroplane fuselages and automobile bodies. In the manufacture of such items the surface d e f i n i t i o n i s required i n a smoothly changing form without surface o s c i l l a t i o n s and i r r e g u l a r i t i e s . Frequently, however, the surfaces are defined by measured prototype data, which may be sparse i n nature and have attendant measurement er r o r s . In such instances the data has to be approximated and possibly smoothed by a series of curves of some known form. There are a number of types of curves a v a i l a b l e for curve f i t t i n g i n CAD/CAM work. In this work the basis and properties of B-spline curve f i t t i n g are established and evaluated i n r e l a t i o n to other curve f i t t i n g techniques. A series of t r i a l shapes, or bench marks, were devised which showed that B-splines generated the smoothest curves and are very suitable for computer-aided-design a p p l i c a t i o n s . B-splines, with other types of spline curves, form the basis of a new computer-aided-machining program c a l l e d G-SURF. The surface i s defined within G-SURF as a g r i d of orthogonal space curves and i s machined using an end m i l l i n g cutter i n c l i n e d at a predetermined angle to the surface normals. The end m i l l thus cuts on the leading or t r a i l i n g edge (as appropriate) and i s able to remove material very e f f i c i e n t l y at a f u l l and preselected material cutting speed. Within t h i s work G-SURF has been used to design and produce a series of t r i a l objects, including a 3 f t . ship h u l l and a chain-saw guide bar. They have served to prove and test the G-SURF program. - i i i -. ^  TABLE OF CONTENTS Page ABSTRACT • i l LIST OF FIGURES \iy ACKNOWLEDGEMENTS •..• Ti?-CHAPTER 1 — INTRODUCTION TO CURVE-FITTING AND G-SURF 1.1 1.1 Introduction 1.1 1.2 G-SURF 1.2 1.3 Curve Fitting 1.3 1.3.1 Least-mean-square curve f i t t i n g 1.3 1.3.2 n t h order polynomial f i t 1.3 1.3.3 Conic 6pline curve f i t t i n g . . . . 1.4 1.3.4 Cubic spline curve f i t t i n g 1.5 1.3.5 B-spline curve f i t t i n g 1.5 1.4 Objectives ••• 1.6 CHAPTER 2 — B-SPLINE THEORY AND EXAMPLES 2.1 2.1 Knots 2.1 2.2 Basis Function 2.2 2.3 Nodes 2.4 2.4 Geometric Interpretation of B-Splines 2.5 CHAPTER 3 — CURVE FITTING COMPARISONS 3.1 3.1 Test Curves and Curve Fitting Methods 3.1 3.2 Comparison of Curve Fitting Methods 3.2 3.2.1 The S-curve 3.2 3.2.2 The two-level curve 3.3 3.2.2 The off-set point 3.3 3.3 Other Evaluation Factors 3.4 CHAPTER 4 — B-SPLINE AND G-SURF APPLICATIONS 4.1 4.1 Introduction 4.1 4.2 Twisted Surface 4.1 4.3 Sine Curve 4.2 4.4 Chain Saw Guide Bar 4.3 4.5 Ship Hull 4.3 CHAPTER 5 — CONCLUSIONS 5.1 APPENDIX I A worked example of conic spline f i t t i n g AI.l APPENDIX II A worked example of cubic spline f i t t i n g AII.l APPENDIX III A worked example of B-spline f i t t i n g AIII.l REFERENCES R.l LIST OF FIGURES Figure Page 1.1 Surface approximated by a set of curves 1.7 1.2 G-SURF machining technique 1.8 1.3 A schematic of a 5-axis C.N.C. machine 1.9 1.5 Curve f i t t i n g using 9th order polynomial 1.10 1.4 Curve f i t t i n g using Least-mean-squares 1.10 1.6 Curve f i t t i n g using Conic splines 1.12 1.7 Curve f i t t i n g using Cubic splines 1.13 2.1 A E-spline f i t to a given set of data points 2.7 2.2 Basis function for a set of equally spaced knots 2.8 2.3 Basis function between two equally spaced knot points. 2.9 2.4 Knot coalescence 2.10 2.5 Basis function of order one 2.11 2.6 Basis function of order two 2.12 2.7 Basis function of order three 2.13 2.8 Basis function of order four 2.14 2.9 Geometric interpretation of B-splines 2.15 3.1 Data points for the S-curve 3.7 3.2 Data points for the two level curve 3.8 3.3 Data points for the off-set point 3.9 3.4 A B-spline (BSAPP) f i t to the S-curve 3.10 3.5 A B-spline (BSPIN) f i t to the S-curve 3.11 3.6 A Cubic spline (CUB.SPL) f i t to the S-curve 3.12 3.7 A Conic spline (CON.SPL) f i t to the S-Curve 3.13 3.8 A least-mean-square (LMS) f i t to the S-curve 3.14 3.9 A 9th order polynomial (9thP0LY) f i t the S-curve 3.15 3.10 UNIGRAPHIC f i t to the S-curve 3.16 3.11 A B-spline (BSAPP) f i t to the two level curve 3.17 3.12 A B-spline (BSPIN) f i t to the two level curve 3.18 3.13 A Cubic spline (CUB.SPL) f i t to the two level curve .. 3.19 3.14 A Conic spline (CON.SPL) f i t to the two level curve .. 3.20 3.15 UNIGRAPHIC f i t to the two level curve 3.21 3.16 A B-spline (BSAPP) f i t to the off-set point 3.22 3.17 A B-spline (BSPIN) f i t to the off-set point 3.23 3.18 A Cubic spline (CUB.SPL) f i t to the off-set point .... 3.24 3.19 A Conic spline (CON.SPL) f i t to the off-set point 3.25 3.20 UNIGRAPHIC conic f i t to the off-set point , 3.26 3.21 UNIGRAPHIC spline f i t to the off-set point 3.27 Figure Page 4.1 The twisted plane 4.5 4.2 Photograph of the twisted plane 4.6 4.3 G-SURF's mode of changing cutting edge 4.7 4.4 The sine curve surface 4.8 4.5 Photograph of the sine curve surface 4.9 4.6 Effect of misalignment i n X-axis 4.10 4.7 Data points for chain saw blade 4.11 4.8 Cubic spline f i t to chain saw blade 4.12 4.9 B-spline (BSAPP) f i t to a chain saw blade 4.13 4.10 B-spline (BSAPP) f i t to chain saw blade, 2nd i t e r a t i o n 4.14 4.11 F i r s t derivative plot of cubic spline (CUB.SPL) f i t to chain saw blade 4.15 4.12 F i r s t derivative plot of B-spline (BSAPP) f i t to chain saw blade 4.16 4.13 F i r s t derivative plot of B-spline (BSAPP) f i t to chain saw blade, 2nd i t e r a t i o n 4.17 4.14 Station lines for East-wood h u l l 4.18 4.15 Tool path for East-wood h u l l 4.19 4.16 Photograph of the ship h u l l 4.20 A I . l Conic spline (CON.SPL) f i t when end slope greater than slope between points AI.4 AI.2 Conic spline (CON.SPL) f i t when end slope equals slope between points .° AI.5 AI.3 UNIGRAPHIC conic f i t to end slope greater than slope between points AI.6 AI.4 UNIGRAPHIC f i t to end slope less than slope between points AI.7 AI.5 Conic spline f i t to i n f l e c t i o n point slope less than slope between points AI.8 AI.6 Conic spline f i t when i n f l e c t i o n point slope i s between the slope between points AI.9 A3.1 Basis functions add up to form curve AIII.7 A3.2 Basis function after being multiplied by these coef f i c i e n t s AIII.8 - v i -ACKNOWLEDGEMENTS The author wishes to thank Dr. G.W. Vickers for his unending words of encouragement and for the guidance given throughout this work. He i s also thankful to his colleagues for t h e i r valuable suggestions and c r i t i c i s m . F i n a l l y , to his parents and s i s t e r , the author owes h i s deep gratitude for t h e i r u n f a i l i n g encouragement throughout the work. The i n v e s t i g a t i o n reported herein was supported by the Natural Sciences and Engineering Research Council of Canada. - 1.1 -CHAPTER 1 INTRODUCTION TO B-SPLINE CURVE FITTING AND G-SURF 1.1 Introduction i Compound curved surfaces are frequently encountered i n engin-1 2 eerlng applications , . The performance and appearance of ship h u l l s , aeroplane fuselages , marine propellors, and automobile bodies, etc. depend l a r g e l y on the smoothness of the s u r f a c e 3 . In most of the cases, a prototype i s f i r s t made and tested and the surface i s subsequently measured from the prototype. In the case of marine propellors the surface i s stored as a e r o f o i l sections at d i f f e r e n t radius r a t i o s , while ship h u l l s are defined at various sec-tions c a l l e d water-lines, s t a t i o n - l i n e s and b u t t o c k - l i n e s 3 . The surface data, however generated, i s i n essence a f i n i t e series of points. The points do not define the complete surface, they may be sparse i n nature and frequently have measurement errors. Surface o s c i l l a t i o n s or i r r e g u l a r i t i e s are usually not acceptable as they become apparent i n the finis h e d product. A hood or fender of an automobile should "look" smooth when i t i s complete -. Doubly curved surfaces present a challenge i n manufacturing as they cannot be e a s i l y machined by plane or c y l i n d r i c a l generators. However, i f they can be defined as a series of curves smoothly trans-l a t i n g through or among the given data points, the surface can be re-produced on a CNC machine. 1.2 G-SURF G-SURF is a CAD-CAM package designed and developed at UBC for designing and manufacturing doubly curved surfaces of essentially low to moderate curvature**. G-SURF approximates a surface as a series of orthogonal space curves. The number and spacing of the curves deter-mines the adequacy of the surface definition. The orthogonal space curves used to define the surface may be B-spline or other types of spline curves. The orientation of the local or component coordinate reference frame across the surface is given in Figure 1.1. The tangent of the spline curve determines the local Y-axis while the tangent to the orthogonal spline curve determines the local X-axis. As shown in Figures 1.2 and 1.3 the surface is machined with an end milling cutter inclined at a predetermined angle to the surface normal in the oscullating plane (i.e. the tangential plane to the curve along which the tool is travelling). The end mill thus cuts on the trai l i n g or leading edge and operates at f u l l cutting speed at a l l times during the machining operation. The greater the inclination of the end mill to the surface normal the smaller is the effective radius of cutting and the less likely is the cutter to remove essential surface material. Curvature and interference checks can be made within the program and cutter inclination adjusted accordingly. G-SURF is designed for use on a mini-computer and is thus suitable for small CNC manufacturers with modest computing f a c i l i t i e s . The output is applicable to 2-1/2, 3, 4 or 5 axis CNC machines. The 4 and 5 axis CNC machines are more flexible and enable a wider range of work to be completed. - 1.3 -1.3 Curve Fitting A number of curve f i t t i n g methods can be used within G-SURF to define the orthogonal surface grids. The two basic choices when f i t t i n g a curve to discrete data points are interpolation or approxima-tion. The former passes a curve through a l l the data points, however much in error they may be, while the latter passes a curve among the points. Approximation generally gives a smoother curve for CAD/CAM applications but where no adjustment can be made to the position of the specified data interpolation becomes a necessity 5. The common types of curve f i t t i n g with their attendant charac-teristics are given below: 1.3.1 Least-mean-square curve f i t t i n g The least-mean-square method of curve f i t t i n g minimizes the mean-square deviations of a polynomial function 6. This f i t is approp-riate when the error in the data points have a normal distribution. Even one "wild" point can distort a least-mean-square f i t to the extent that i t is unacceptable. Least-mean-square f i t s frequently generate oscillations in the curve as shown in Figure 1.4. Wild points, sharp slopes or a scarcity of points at the end of the curve can start fluc-tuations, which make this f i t unsuitable for CAD/CAM purposes. th 1.3.2 n order polynomial f i t A polynomial can be made to pass through a given set of data points. The d i f f i c u l t y is that the order of the polynomial is deter-mined by the number of points. Higher order polynomials frequently generate oscillations as shown in Figure 1.5 and are not suited for surface design in CAD/CAM applications 2. 1.3.3 Conic splines* Splines are piecewise combinations of particular curve types which can be made to match in position and slope at the junction of 7 each section . They are the mathematical equivalent of the mechanical splines, or flexible elastic strips, used by draftsmen to smooth o curves . The general equation of a conic is given as: 2 2 ax + bxy + cy +dx + ey + j = 0 This represents a l l two-dimensional sections through a right circular cone (i.e., line, circle, ellipse, parabola, hyperbola — a l l single curvature curves). With conic splines this equation can be used to f i t the f i r s t three data points and then to f i t the next three data points with position and slope continuity at each junction. Conic splines do not give curvature continuity at junctions. Changing any data point changes a l l the fitted equations. A worked example of a conic spline is given in Appendix I and summarised in Figure 1.6. The conic equations are applied to advantage in CURVFIT- to span a set of closely spaced digitised points with widely spaced 'control points' at which position and slope are chosen and specified. Inflexion points are identified as additional control points. The method is capable of producing either approximation or inter-polation f i t s . - 1 . 5 -1.3.4 Cubic spline curve f i t t i n g These are a set of cubic polynomial equations of the form: 2 3 2 ax + bx + cx + d = y This equation i s more f l e x i b l e than the conic equation i n that i t generates double curvature. In th i s case the equation can be used to f i t the f i r s t four data points and then to f i t each a d d i t i o n a l data point with p o s i t i o n , slope and curvature continuity at each junction. A worked example of the cubic spline curve f i t t i n g i s given i n Appendix II and the res u l t s shown i n Figure 1.7. While any degree of polynomial curves can be used the cubic i s most widely accepted i n CAD/CAM ap p l i c a t i o n s . It i s of s u f f i c i e n t l y high order to give curvature continuity and yet low enough to prevent unnecessary o s c i l l a t i o n s . As with conic splines a l l equations f o r a p a r t i c u l a r curve are altered i f any data i s changed. Also large v e r t i c a l slopes create computational d i f f i c u l t i e s . 1.3.5 B-Splines curve f i t t i n g B-splines are l i n e a r combinations of basis functions formed ik from p a r t of the power s e r i e s g i v e n by y = ( x - e j where x i s the independent variable, y the dependent variable , e i s any constant and k the degree of the polynomial. B-splines have the property of generating the least curvature ( i . e . smoothest) of a l l curves, produce no o s c i l l a t i o n s and, are v a r i a t i o n a l l y diminishing ( i . e . degenerate to the least power required to f i t the data — a straight l i n e i s f i t by an equation of a straight l i n e ) 5 , 1 0 , 1 1 . B-splines may be of any order although cubic B-splines are used within G-SURF. These span four i n t e r v a l s and a l t e r a t i o n of any data points e f f e c t s only the neighbouring four spans. The d e f i n i t i o n and formulation of B-splines are given in Chapter 2 of this work. 1.4 Objectives The object of the present work i s to examine the basis of B-spl i n e curve f i t t i n g and to evaluate i t i n r e l a t i o n to other curve f i t t i n g techniques. A series of t r i a l shapes, or bench marks, were devised for making these comparisons. In addition, i t i s required that the c a p a b i l i t i e s of G-SURF be investigated and developed by machining a series of test surfaces of increasing complexity. The a p p l i c a b i l i t y of the approach to l o c a l i n d u s t r i a l problems i s i l l u s t r a t e d by two recent projects. One i s the generation of smooth data and CNC tapes required i n the manufacture of chain saw guide bars. The other i s i n l o f t i n g and machining a three-foot model ship h u l l . Y m Machine Coordinates X m Surface approximated by a set of curves. -1.8-FIG. 1.2 G-SURF machining technique. Rotary tables were designed by Dr.Shi-Gang Wang & Dr.J.P.Duncan. FIG. 1.3 A schematic of a 5 - a x i s C.N.C. machine. -1.10-j FIG.l.4 Curve f i t t ing using Least-mean-squares. -1.11-FIG. 1.5 Curve f i t t i n g using 9th order polynomial. - 1 . 1 2 -B. 0 A •1 • 4 . 0 2. 0 0. 0 — - 2 . 0 0. i 1 . 1 . 1 , i • , 1 ! , 1 1 1 0 1 .0 2 . 0 3 . 0 4. 0 5 . 0 6 . 0 7 . 0 e . a. 0 FIG. 1.6a Curve f i t t i n g using Conic splines.with i n f l e c t i o n point at Y = 3.0. E q u a t i o n s o f c u r v e s I n d i f f e r e n t r e g i o n s a r e : -R e g i o n A : x 2 + 2 . 2 2 0 * X * Y - 1 . 5 8 * Y 2 - 1 .333*X + 3 . 1 7 * Y + 2 . 4 7 = 0 . 0 R e g i o n B : x 2 - 1 .420*X*Y - 0 . 5 7 * Y 2 - 2 . 2 9 *X + 1 .31*Y + 1 .59 - 0 . 0 R e g i o n C : x 2 + 2 5 . 5 0 0 * X * Y - 1 2 . 2 5 * Y 2 - 1 2 4 . 7 5 * X - 4 . 1 3 * Y + 2 5 4 . 5 = 0 . 0 Reg ion D : x 2 + 0 . 5 7 0 * X * Y + 0 . 1 3 * Y 2 - 1 2 . 6 0 * X - 3 .56*Y + 3 8 . 4 5 = 0 . 0 -1.12b-X FIG. 1.6b Curve f i t t i n g using Conic splines with inflection point at Y = 3.2. FIG. 1.7 Curve f i t using Cubic s p l i n e s . Equations of curve i n d i f f e r e n t regions are :-Region A : Region B  Region C  Region D  Region E  Region F 2.6 - 1.33*X + 0.15*X2 + 0.08*X3 29.6 - 23.33*X + 9.15*X2 - 0.91-X3 2 3 - 124.2 + 87.02*X - 19.69*X + 1.49*X 740.7 - 431.93*X + 84.10*X2 - 5.43*X3 - 356.51 + 72.67*X + 3.66*X2 - 0.96*X3 -11353.3 + 4785.59*X - 669.6*X2 + 31.1*X3 = Y = Y = Y = Y = Y = Y CHAPTER 2 B-SPLINE THEORY AND EXAMPLES B-splines are d e f i n e d 5 as l i n e a r combinations of basis func-t i o n s formed from the truncated power series y = (x-e) where x i s the independent variable, y the dependent variable, e i s any constant and k the degree of the p o l y n o m i a l . The k'*1 order b a s i s f u n c t i o n s are a p p r o p r i a t e l y s c a l e d k*"*1 d i v i d e d d i f f e r e n c e s of the truncated power s e r i e s . Given a knot sequence [ t^» t n] a B-spline approximation to a set of data points i s given by: n F(x) = S o B ( x) (1) i = l 1 1 , J where F(x) i s the function value of the curve at x, t Vi ct^  i s the c o e f f i c i e n t of the i basis function, B. . i s the value of the i ' * 1 basis function or order j . An example of a B-spline f i t and basis function i s given i n Figures 2.1 and 2.2. 2.1 Knots For the, cubic B-spline used i n G-SURF the basis function con-s i s t s of four cubic polynomial arcs stretching across f i v e knots. Each i s normalised and non-zero over four i n t e r v a l s and zero everywhere 1 3 else . At most, four basis functions of order four are non-zero at any point on a curve as shown i n Figure 2.3 for the i n t e r v a l 3 to 4. The point at which a basis function s t a r t s i s c a l l e d the knot point. These points are usually coincident with the data points. To incorporate end-slope c o n t r o l , a d d i t i o n a l knots are added at the end points of the curve 5. The number of ad d i t i o n a l knots required at each end i s (k-1) where k i s the order of the B-spline. A knot sequence may contain i d e n t i c a l knots up to a m u l t i p l i c -i t y k. The ef f e c t of a knot occuring with a m u l t i p l i c i t y n, i . e . t = t = • • • = t (2) i i+1 i+k-1 v ' to decrease the degree of d i f f e r e n t i a b i l i t y of the basis function B k 1) » at x to n ^ t i . e . , i f any two knots coincide the curve loses i t s d i f f e r e n t i a b i l i t y by 1 at that point. The formation of a double knot may be viewed as being a coalescence of two adjacent knots as shown i n Figure 2.4. 2.2 Basis Functions Given a knot sequence X = [ t ^ ,  m",t 1 the basis function of i i n order k (degree k-1) may be d e f i n e d 5 , 1 2 as x - t t - x B i k ( x ) = t H- B i k - l ( x ) + B i + l k - l ( x ) ( 3 ) ' i+k-1 i ' i+k i+1 ' where the i n i t i a l conditions are defined as 1 i f t <x< t \ x ( x ) - 1 • 1 + 1 . (4) ' 0 otherwise In order to get a better understanding of the basis function the following table i s derived, using Equations (3) and (4), for a knot sequence x = [ t j , * # , , t ] i n the region t^ < x < t ^ . - 2.3 -k = 1 k = 2 k = 3 k = 4 B i , r 0 B l , 2 = 0 B 2 , i - 0 B2,2 " ° B l , 3 . - 0 (1-x) 3 B 3 , l = 0 B3,2= ^ B 2 j 3= (1-x) 2 B2,4= x(2-x) 2 { < ! - * > + ^ 1 V = 1 B5,l= ° B4,2 = x  B5,2= ° B 3 3 = x(l-x) x(2-x) 2 2 B4,3 " 2 B3,4 B4,4 - 4»<i-3 X 6 ? 2 - « ) + ( ^ ) H - ( 3 - x ) ^ B 6 , l = ° B6,2 = 0 B5,3 = ° B 7 , l = ° Each column in the above table represents the basis functions of different orders. 1 2 ( i ) The f i r s t column contains equations of basis functions of order one. The basis function is given in Figure 2.5. If Bj ^  is used to f i t a set of data points the resulting f i t wi i l be a histogram. - 2.4 -( i i ) The second column gives equations of polynomial pieces representing the basis function of order two between t(4) & t(5). The basis function is given in Figure 2.6. If a curve is f i t using 2» t n e output w i l l be a linear interpolation with only point continuity. ( i i i ) The third column contains the equation of polynomial pieces forming basis function of order three in the interval t(4) to t(5). The basis polynomials are shown in Figure 2.7. Curve f i t t e d using B^ ^ is continuous in point and slope. ' (iv) The fourth column contains equations of polynomial pieces of order four in the range t(4) to t(5). The basis poly-nomials are given in Figure 2.8. The curve obtained • using B^ ^ is continuous in point, slope and curvature. This is the order of B-splines used in the G-SURF program. A worked example of B-spline curve f i t t i n g i s given in Appendix III. For computational purposes a recurrence algorithm developed by Carl de Boor 5 is used to evaluate the basis function. 2.3 Nodes Once the basis functions have been defined, the B-spline approximation of order k to any arbitrary function 1 0, or set of data, may be stated as: F(x) where G i 's are called the nodes and the value of the function at the nodes gives us the coefficient of B-spline basis functions. This is shown in detail in Appendix III. In B-spline interpolation, however, the procedure to determine ct^'s i s s l i g h t l y different. In matrix form B-splines basis function may be defined as: I a(V B i , k ( x ) (4) Tk=iy t 'i+i + fci+2 + *••+ W i ) • (5) - 2.5 -{ F } = [B] {«} or (6) w = ur 1 { F } . Knowing both the matrices on the right hand side, the matrix {a} can be easily determined. There are other features about [B ] and {F } which make the calculation of [otj's very easy. [B ] i s a banded matrix and can be inverted without pivoting by Gauss's method5. This approach is used within ( B S P I N ) for B-spline interpolation. 2.4 Geometric Interpretation of B-Spline Approximation B-spline approximation (BSAPP) can be fitted to a set of data points without calculating the basis function. Carl de Boor has proved that F (for k = 0) F^ k(x) =* (7) X F I > K _ 1 + d - A ^ . ^ (for k > 0) x - X ' ^ ti-k+M" t i where M is order of B-spline, k = M-1, F^ i s the value of the i th data point, F ,(x) is the value of B-spline f i t of degree k at the point i,k x. Consider a knot sequence T = [ t Q .... t ^ ] = [111123456789999]. The value of the B-spline i s to be found for x = 7.6. Since t 9<7.6<t 1 0, i = 9. Using the recursive relation, given in equation 7, we get F 9 3(7.6) = X F 9 2(7.6) + (1-X) F G 2(7.6) \ - (7.6 - 7)'_ x oT^~0'6 - 2.6 -F 9 2(7.6) = X F 9 x(7.6) + (1-X) F g ^7.6) X (4=2) " °* 3 F g 2(7.6) = X Fg ^7.6) + (1-X) F ? ^7.6) \ - < 7' 6 - 6.6)  X (4=2) ~ 0 , 3 F 9 x(7.6) = X F 9 + (1-X) F g '\ - (7-6 - 7.0) _ A " (4-1) " °' 2 Fg L(7.6) = X Fg + (1-X) F ?  A (4-1) 0 , 5 3 F ? L(7.6) = X F 7 + (1-X) F 6 ' _ (7.6 - 5.0) _ X ~ (4-1) _ °' 8 7 The value of the data points F^, F^, Fg, Fg can be put into the above relations and the value of B-spline determined. This is shown as a graphical solution in Figure 2.9. A geometerical f i t to the S-curve at the point x = 5.5 is shown in Figure 2.10. FIG. 2.1 A B-Spline f i t to a given set of data points. FIG. 2.2 Basis function'for a set of equally spaced knots. -2.9-Y F I G . 2.3 B a s i s f u n c t i o n between two e q u a l l y s p a c e d k n o t p o i n t s . -2.10-l ' ' 1 ' I I FIG.2.4 Knot c o a l e s c e n c e . - 2 . 1 1 -F I G . 2.5 B a s i s f u n c t i o n o f o r d e r one. - 2 . 1 2 -F I G . 2.6 B a s i s f u n c t i o n of order two. - 2 . 1 3 -FIG. 2.7 B a s i s f u n c t i o n of order three. -2.14-FIG.2.8 B a s i s f u n c t i o n of o r d e r f o u r . F I G . 2.9 G e o m e t e r i c e x p l a n a t i o n o f B - S p l i n e s . FIG. 2.10 B-Spline (BSAPP) geometeric construction. - 3.1 -CHAPTER 3 CURVE FITTING COMPARISONS 3.1 Test Curves and Curve Fitting Methods To evaluate B-spline curves in relation to other curve f i t t i n g methods a series of t r i a l shapes, or bench marks were devised. The three chosen standard data sets are given in Figures 3.1 to 3.3 and comprise of: 1. The S-curve: used to evaluate the smoothing capabilities of each method. Figure 3.1. 2. The two-level curve: used to evaluate the treatment of h i g h slopes. Figure 3.2. 3. The off-set point: used to evaluate the capability of each method to deal with an off-set point and thereafter follow a straight lin e . Figure 3.3. The curve f i t t i n g methods implemented on the PDP 11/34 and used for comparison with B-splines are as follows: 1. BSAPP — B-spline approximation. 2. BSPIN — B-spline interpolation. 3. CON.SPL — conic polynomial spline. 4. CUB.SPL — cubic polynomial spline. 5. LMS — least-mean-squares approximation. 6. 9TH POLY — 9th order polynomial curve. 7. UNIGRAPHIC — general f i t t i n g routine from ] graphics package (installed locally at National Research Council). 3.2 Comparison of Curve Fitting Methods 3.2.1 The S-Curve The resulting curves for BSAPP, BSPIN, CUB.SPL, CON.SPL, LMS, 9TH POLY and UNIGRAPHIC are given in Figures 3.4 to 3.10 respectively. This set of data points were fitted well by most of the methods but some differences are evident. BSAPP generated the smoothest curve, although as discussed previously, this did not pass through a l l the data points. However, the fitted curve always lies within the convex hull of the enclosing polygon as shown in Figure 3.4. BSPIN and CUB.SPL fitted the data points with a smooth c u r v e which passed through a l l the points as shown in Figures 3.5 and 3.6. CON.SPL fitted the data points with a f a i r l y smooth curve. However, i t was not as smooth as BSPIN and CUB.SPL. Further, CON.SPL required the most manual intervention and some prior knowledge of the curve. The user is required to define a l l inflection points and slopes as well as end point slopes. Manipulation of the inflection point slopes can be used to improve the curve but this depends on user's s k i l l and the result is not unique. Results from LMS given in Figure 3.8 show unwanted o s c i l l a -tions. It was found that suitable results were obtained only when a large number of data points were used. Even then there is no assurance that oscillations w i l l not occur. The 9TH POLY given in Figure 3.9 also shows some oscillations. With less smooth data sets these oscillations can become very s i g n i f i -cant . Results from UNIGRAPHIC curve f i t t i n g are given in Figure 3.10 The results are not unlike those of CUB.SPL shown in Figure 3.6. - 3.3 -3.2.2 The two-level curve This set of data highlights the capabilities of a method to deal with relatively sudden changes of slopes without overshoot. The resulting curves for BSAPP, BSPIN, CUB.SPL, CON.SPL and UNIGRAPHIC are given in Figures 3.11 to 3.15 respectively. BSAPP fitted by far the smoothest curve, and had no overshoots as shown in Figure 3.11. BSPIN, CUB.SPL and CON.SPL a l l generated serious oscillations in the fitted curve as shown in Figures 3.12 to 3.14. BSPIN and CUB.SPL gave similar results. The results for CON.SPL were better than BSPIN and CUB.SPL. However, the operator time required for CON.SPL was significant and probably unacceptable in practice. The spline f i t t i n g routine on UNIGRAPHIC also gave o s c i l l a -tions as shown in Figure 3.15. 3.2.3 The off-set point This set of data highlights the capabilities of a method to deal with off-set points. The resulting curves for BSAPP, BSPIN, CUB.SPL, CON.SPL and UNIGRAPHIC are given in Figures 3.16 to 3.21 re-spectively. BSAPP smoothed the data to a remarkable extent, s t i l l keeping within the convex hull of the enclosing polygon. The straight line portion was exactly reproduced as shown in Figure 3.16. BSPIN and CUB.SPL fitted a highly oscillating curve to the given set of data points as shown in Figures 3.17 and 3.18. Oscillations created in the offset curve were carried down into the straight line portion of the curve. CON.SPL had great d i f f i c u l t y i n f i t t i n g this set of data points. Additional inflection points, data points and slopes were tried but even so the most acceptable curve is shown in Figure 3.19. The conic spline and spline general from UNIGRAPHIC give identical and unsatisfactory results shown in Figures 3.20 and 3.21. In the case of the conic spline the curve turns on i t s e l f , while in spline general oscillations are encountered. 3.3 Other Evaluation Factors While the technical suitability of a curve f i t t i n g method to a particular application is of prime concern, other factors such as: 1. the ease of use; 2. computational size and application to mini-computers; and 3. speed of computation need to be exercised. A general assessment of these factors is given in Table 3.1. From the standpoint of ease of use BSAPP and CUB.SPL were rated 'good' while CON.SPL was rated 'poor' as i t required the most manual intervention and some prior knowledge of the curve shape. The task image size, which is the memory size required to store and run the object code for the compiled .version is given in Table 3.1. It can be seen that BSPIN and CUB.SPL require approximately the same memory sixe (32kB). BSAPP requires a somewhat larger memory,(50kB), although i t gives a graphic terminal display. If this feature were removed i t would be approximately the same size as BSPIN and CUB.SPL. CON.SPL requires approximately twice the amount of memory as the other methods. The overall assessment is that BSAPP, BSPIN and CUB.SPL are a l l easy to use and require similar computer memory space. BSAPP gives by - 3.5 -far the smoothest curves and i s the only method to suitably handle a l l the bench mark curves. BSPIN and CUB.SPL both give good i n t e r p o l a t i o n r e s u l t s . CON.SPL requires the most memory capacity and the most user input, but i s s t i l l s uitable for some ap p l i c a t i o n s . The other methods LMS and n*"*1 order polynomial are not considered suitable for CAD/CAM ap p l i c a t i o n s . TABLE 3.1 PROPERTY BSAPP BSPIN CON.SPL CUB.SPL 1. Task image size 25088 Words 16192 Words 30528 Words 17248 Words 50 K Byte 32 K Byte 61 K Byte 34 K Byte 2. Graphic's a b i l i t y Graphic display, Paper plot Paper plot Paper plot Paper plot 3. System dependence IGL, PLOT10 PLOT10 PLOT10 PLOT10 -3 . 7-6. a r— 4. 0 2. 0 — * k Y 0. 0 — -2. 0 1 1 1 1 , 1 1 1 | I 0. 0 1. 0 2. 0 3. 0 4. 0 5. 0 X 6. 0 7. 0 8.""0 9. 0 FIG. 3.1 Data points fot the S-curve. -3 . 8-6 . 0 X • 4 . 0 0 . a t « « - 2 . 0 a. 1 T 1 . 1 1 1 . I 1 1 0 i . a 2 . 0 3 . 0 4 . 0 X 5 . 0 6 . 0 7 . 0 8 . 0 0 . 0 FIG. 3.2 Data points for the two level curve. -3 . 9-6. 0 — -A. 0 • 2. 0 Y » s « . X 0. 0 -2. 01 i 1 1 1 1 . 1 1 1 I | 0. 0 1. 0 2. 0 3. 0 4. 0 5. 0 X 6. 0 7. 0 8. 0 9. 0 FIG. 3.3 Data points f o r the o f f - s e t p o i n t . - 3 . 1 0 -FIG. 3.4 A B-Spline (BSAPP) f i t to the S-Curve. -3.11-FIG. 3.5 A B-Spline (BSPIN) f i t to the S-Curve. -3.12-FIG. 3.6 A cubic spline (CUB.SPL) f i t to the S-Curve. -3.13-.3.7 A conic spline (CON.SPL) f i t to the S-Curve. - 3 . 1 4 -6. B -4 . Z » \ Y 1 z. z • z. z — - 2 . B Z | 1 1 , 1 1 1 --1 _.. 1 . ,1 Z 1. Z 2. 2 3. 0 A. Z 5. a X 6. 0 7. 0 s. 2 « . a FIG. 3.8 A l e a s t - m e a n - s q u a r e s (LMS) f i t t o the S-Curve. -3.15-FIG. 3.10 UNIGRAPHIC'S f i t to the S-Curve. -3.17-FIG. 3.11 A B-Spline(BSAPP) f i t to the two level curve. -3.18-FIG. 3.12 A B-Spline(BSPINT) f i t to the two level curve. -3.19-FIG. 3.13 A Cubic spline(CUB.SPL) f i t to the two level curve. - 3 . 2 0 -e. 0 4 . 0 2 . 0 Y 0 . 0 - 2 . 0 1 I . I . I 1 1 1 0 . 0 1 . 0 2 . 0 3 . 0 4 . 0 X 5 . 0 6 . 0 7 . 0 e . 0 O. 0 FIG. 3.14 A Conic spline(CON.SPL) f i t to the two level curve. 8.0 9.0 10.0 11.0 FIG. 3.15 UNIGRAPHICS f i t to the two level curve. - 3 . 2 2 -6. 0 — 4. 0 2. 0 -A • Y 1 0. 0 -2. 0 . 1 . 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 0. 0 1.0 2. 0 3. 0 4. 0 5. 0 6. 0 7. 0 B. 0 9. 0 A FIG. 3.16 A B-Spline(BSAPP) f i t to the off-set point . - 3 . 2 3 -6 . 0 — A. 0 — Y 2 . 0 0. 0 - 2 . 0 . 1 . 1 , 1 , 1 , 1 • 1 i 1 • ! . 1 0 . 0 1 . 0 2 . 0 3. 0 A. 0 X 5 . 0 6 . 0 7 . 0 B . 0 3. 0 FIG. 3.17 A B-Spline(.BSPINT) f i t to the off-set point. - 3 . 2 4 -6. 0 — A. 0 — Y 2. 0 i 0. 0 -2. 0 -i 1 • 1 « 1 - 1 . 1 , 1 • | , ! , | 0. 0 1.0 2. 0 3. 0 A. 0 X 5. 0 6. 0 7. 0 B. 0 0. 0 FIG. 3.18 A cubic spline(CUB.SPL) f i t to the off-set point . -3.25-e. 0 4 . 0 — 2 . 0 Y ' 0 . 0 -2. 0 1 1 1 1 , 1 1 ! 1 1 0 . 0 J. 0 2 . 0 3 . 0 4 . 0 X 5 . 0 6. 0 7. 0 e. 0 B. 0 FIG. 3.19 A conic spline(CON.SPL) f i t to the o f f - s e t p o i n t . 6.0 -4.0 -Y 1 2.0 -t i J > • • 4 • rc 0.0 zr. xc i 1 i i i 1 i i i X 0. 0 1.0 2.0 3.0 4.0 5.0 6.0 7.0 8.0 9.0 FIG. 3.20 UNIGRAPHICS conic f i t to a off-set point. • 6 . 0 U 4.0 Y * - • 1 0.0AjL_ XC u l I I i I 1 I L _ 1 1 X 0.0 1.0 2.0 3.0 4.0 5.0 6.0 7.0 8.0 9.0 FIG. 3.21 UNIGRAPHICS spline f i t to a off-set point. - 4.1 -CHAPTER 4 B-SPLINE AND G-SURF APPLICATIONS 4.1 Introduction B-spline and G-SURF have been discussed in the preceding chap-ters. G-SURF is a Fortran computer program which utilizes B-splines, and other spline curves, to define and machine surfaces. G-SURF exploits the smoothing property of B-splines to generate smooth surface shapes. Two test objects and two industrial components were machined using this approach and are discussed below. The process of machining these objects served to prove the versatility of the approach and at the same time highlighted some interesting features. The objects that were machined are: 1. Twisted Surface, 2. Sine curve, 3. Chain-saw guide bar, and 4. Ship hull. 4.2 Twisted Surface This doubly curved surface can be obtained by twisting the opposite edges of a square flat plate. The surface was generated by G-SURF from a set of equi-spaced points lying on equi-spaced lines as shown in Figure 4.1. B-splines fitted straight lines to this set of points and a predetermined number of machine data points and data surface normals were generated. The object was machined on a 5-axis machine in time share mode from a 2-1/2 axis controller. The cyl i n d r i -cal end milling cutter is programmed through G-SURF to move along the generating lines in such a way that i t has a constant inclination (10 degrees) to the surface normal in the local tangent plane, as shown in Figure 1.2. A photograph of the fi n a l machined component is given in Figure 4.2 and shows that each of the cuts is straight although each had been generated with a f u l l range of 5-axis movements. As the cutter axis was inclined at a small angle to the local surface normal the resulting blend of adjacent cuts gave an excellent surface finish. It was noted during machining that material removal was accomplished very effectively using the f u l l cutting speed of the end m i l l . 4.3 Sine Curve A series of sine curves were selected to generate a surface with both convex and concave sections. To give the best possible access to these shapes the G-SURF program was adapted to cut on either the leading or trai l i n g edges as shown in Figure 4.3. Thus, deeper concave surfaces can be accessed without the spindle or the tool inter-fering with the object. Figure 4.3 shows G-SURF's mode of changing i t s cutting edge at every change in curvature. The computer plot of the surface is shown in Figure 4.4 and photograph of the machined component in Figure 4.5. During the course of machining i t became apparent that alignment of a l l the five axes was very important. The f i r s t few attempts to machine the sine curve produced a step at the highest and lowest point. This step was even-tually explained by misalignment in the y-z plane. A computer simula-tion of a misalignment in this plane is given in Figure 4.6 for an error of 2 mm in the y-axis. - 4.3 -4.4 Chain Saw Guide Bar For the CNC machining of a chain saw guide bar a set of digit-ized data points was supplied from an existing bar as shown in Figure 4.7. A major requirement was that the final guide bar should be smooth and have a minimum negative curvature. A cubic spline curve was i n i t i a l l y fitted to this set of data on the UNIGRAPHIC system with an instantaneous slope curve, as shown in Figures 4.8 and 4.11 respectively. Subsequently, a B-spline was fitted to the same set of data points as shown in Figure 4.9. The results clearly show that B-splines give a much smoother f i t although by no means perfect. An iterative procedure was adopted in which the original set of data was replaced by points from the last B-spline f i t . The result of the 2nc* i t e r a t i o n gives a smoother curve, as is shown in Figures 4.9 and 4.10, and the derivative plots are given in Figures 4.12 and 4.13. 4.5 Ship Hull A model of a ship hull was made to be used for stability tests in the B.C. research ship testing f a c i l i t y . The data for station lines was obtained for the Eastwood hull as shown in Figure 4.14. On the f u l l size ship the station lines were 10 feet apart and the whole length of the ship was 106 feet. The selected model length was 30 inches. The ship hull surface was developed with B-splines and the fin a l shape of the hull is given in Figure 4.15. A photograph of the completed oak model is shown in Figure 4.16. The ship hull was machined using only the 3-axis capabilities of the CNC machine. - if. 3a -LEAF k.k MISSED IN NUMBERING. -4.5-F I G . 4 . 2 P h o t o g r a p h o f t h e t w i s t e d p l a n e . ft C u t t i n g w i t h t r a i l i n g FIG. 4 .3 G-SURF's mode of changing cutt i n g edge FIG. 4.4 The sine curve surface. - 4 . 9 -FIG. 4 .5 Photograph o f t h e s i n e c u r v e s u r f a c e . -4 .10-2. 000,— 1. 0 0 0 Y 0 . 0 0 0 0J.*000 ' 2. 0 0 0 ' 4. 0 0 0 6. 0 0 0 B. 0 0 0 10. 0 0 0 1 2 . 0 0 0 1 4 . 0 0 0 1 6 . 0 0 0 _L 1 1 1 FIG. 4 . 7 Data p o i n t s f o r c h a i n saw b l a d e . 2. 000,— FIG. 4.8 Cubic spline f i t to chain saw blade. F I G . 4.9 B - S p l i n e f i t t o c h a i n saw b l a d e . 2. 000,— FIG. 4.10 B-Spline f i t to chian saw blade, 2 i t e r a t i o n . FIG.4.11 F i r s t derivative p l o t of cubic spline f i t to chain saw FIG. 4.12 F i r s t derivative plot of B-Spline f i t to chain saw blade. 0. 3 0 0 0. 100 -0. 100 -0. 3 0 0 . 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 0 . 0 0 0 2 . 0 0 0 4 . 0 0 0 6.000 G. 0 0 0 10. 0 0 0 1 2 . 0 0 0 1 4 . 0 0 0 1 6 . 0 0 0 FIG. 4.13 1 derivative plot of B-spline f i t (2 i t e r a t i o n ) to chain saw blade. -4.18-T I C M R R K S P A C I N G : 1 f t FIG. 4.14 Station l i n e s f o r East-wood-hull. -4.19-FIG.4.15 Tool path f or East-Wood h u l l . - 4 . 2 0 -F I G . 4.16 P h o t o g r a p h o f t h e s h i p h u l l . CHAPTER 5 CONCLUSIONS The basis of B-spline curve f i t t i n g has been examined and evaluated i n r e l a t i o n to other curve f i t t i n g techniques. It i s found that: (a) B-spline approximation (BSAPP) f i t s , to a given set of data points, the smoothest, curve which l i e s within the convex h u l l of the enclosing polygon. (b) B-spline approximation (BSAPP) i s v a r i a t i o n a l l y diminishing, i . e . i t f i t s a straight l i n e with a l i n e a r equation. (c) B-spline i n t e r p o l a t i o n (BSPIN) gives r e s u l t s very s i m i l a r to cubic splines (CUB.SPL). (d) B-spline i n t e r p o l a t i o n (BSPIN) and cubic splines can f a i l when faced with high slopes or o f f - s e t points but otherwise they give good a l l purpose i n t e r p o l a t i o n r e s u l t s . (e) Conic spline (CON.SPL) requires the most manual intervention and i n that sense Is not very user f r i e n d l y . t i l ( f ) Least-mean-square (LMS) and n order polynomial (9TH POLY) are not generally suitable for CAD/CAM ap p l i c a t i o n s . The c a p a b i l i t i e s of G-SURF as demonstrated during the design and manufacture of the machined models are: (a) Cutting with an end m i l l i n g cutter i s a very e f f i c i e n t means of material removal and gives good surface f i n i s h . - 5.2 -(b) I n c l i n a t i o n of the end m i l l i n g cutter to the surface normal enables the cutter to be positioned to minimize surface interference, c) Positioning the end m i l l so that i t cuts on either the leading or t r a i l i n g edge increases the a c c e s s i b i l i t y of the tool to deep conca v i t i e s . (d) Alignment of a l l the f i v e axes on a CNC machine i s c r i t i c a l . (e) The computer CPU task f i l e size required for G-SURF i s approximately 55 kB which w i l l f i t on to any Fortran based mini computer. 5.1 Proposed Future Work (a) The next phase of this work should include the study of B-spline surfaces and their comparison with other common surfaces, such as Coon's Patch, UNISURF, Ferguson's Patch, etc. (b) Graphic relationships between d i f f e r e n t machining parameters to increase the e f f i c i e n c y of G-SURF. APPENDIX I A WORKED EXAMPLE OF CONIC SPLINE CURVE FITTING The curve f i t t i n g routine called 'CON.SPL' f i t s a given set of data with piecewise conies of the general form 2 2 ax + bxy + c y + d x + ey + f = 0 . AI.l The curve can be guided by specifying slope at the end points or at inflection points. In the present example the data points for the S-curve are as follows: x O 1 2 3 4 5 * 6 7 8 y 2.6 1.5 1.2 2.2 4.0 4.5 3.3 1.2 2.0 The slope at the end points was specified by additional points as: (-1.0, 4.0) for the starting slope (8.5, -4.0) for the end slope. The inflection point was chosen to be at (3.5, 3.0) and the slope point as (-1.8, 8.0). To f i t the f i r s t part of the spline curve the f i r s t three data points are used together with the starting slope at x = 0 and the weighted mean slope at x = 2. At the f i r s t data point, x = 0, the slope is given as dy _ 4.0 - 2.6 dx -1.0 - 0.0 ~ - 1 , 4 A I * 2 At the third point the weighted mean slope is - AI.2 -Sw = t S2 ( x4 " V + S3 ( X3 " X 2 } ^ / ( X4 " X 2 ) A I * 3 where y3" y2 S = - = - 0.3 3 X2 y4" y3 S, - = 1 3 x.-x_ 4 3 dv so that at x = 2.0 , = 0.35 dx The resulting equations for the f i r s t part of the spline curve are 0 + 0 + 6.76c + 0 + 2.6e + f = 0 0 + 2.66b - 7.28c + d - 1.4e + 0 = 0 1 + 1.5b + 2.25c + d + 1.5e + f = 0 AI.4 4 + 2.4b + 1.44c + 2d + 1.2e + f = 0 4 + 1.9b + .84c + d + 0.35e + 0 = 0 . The solution of this set of simultaneous equations is x 2 - 2.22xy - 1.59y2 - 1.33x + 3.17y + 2.48 = 0 . AI.5 Similarly the equations for the other parts of the spline curve taking position and slope continuity at each junction are: between x = 2 and x = 3.5 x 2 - 1.42xy + 0.58y2 - 2.29x + 1.31y + 1.59 = 0 . AI.6 between x = 3.5 and x = 5.0 x 2 + 25.5xy - 12.25y2 - 124.75x + 4.12y + 254.5 - 0 AI.7 between x = 5.0 and x = 8.0 x 2 + 0.58xy + 0.13y2 - 12.603yx - 3.56y + 38.45 = 0 . AI.8 - AI.3 -The plot of the conic spline curve is shown in Figure 1.6. In the last interval 4 points are fitted instead of three because a f i t to the 1st, 3rd and 4th points in that interval, l i e s within the acceptable error limit at the 2nd point. Hence, for computational purposes the 2nd point is ignored. In f i t t i n g curves with CON.SPL, i t was found that the definition of the endpoint slope c r i t i c a l l y affected the curve f i t t i n g . If for example the end point slope was defined as being greater than or equal to the slope between the f i r s t two data points then a curve was not generated in this region as shown in Figure AI.l and AI.2. However, i f the end point slope is less than the slope between the f i r s t two points a suitable f i t is obtained as shown in Figure 1.6. UNIGRAPHIC conic f i t has similar d i f f i c u l t i e s as shown in Figure AI.3, where the curve tends to curl back on i t s e l f in spite of the slope being less than the slope between the f i r s t two points. In figure AI.4 a UNIGRAPHIC conic f i t to an end slope larger than the slope between the f i r s t two points is shown. The f i t is poor. In f i t t i n g curves with CON.SPL, inflection points and slope at the inflection point play a c r i t i c a l role. If the inflection point slope is less than slopes between the two sets of points, then a curve is not f i t to the two adjacent segments of the curve as shown in Figure AI.5. If however the inflection point slope is in between the slopes of the two sets of points only one segment is fitted with a curve as shown in Figure AI.6. For an acceptable f i t the inflection point slope is greater than the slopes between the two sets of points, as shown in Figure 1.6. 6 . 0 ^ _ \ 4. 0 Slope between points End point slope End p o i n t s l o p e 0. 0 S,.lope between f i r s t two d a t a p o i n t ! - 2 . 01 I 1 i I 0 - 0 1 - 0 ' 2! a ' 3 . ' 0 ' 4 J 0 ' s!a ' el a ' 7 J 0 1 8 ^ 0 1 o . ' 0 FIG. A I . l Conic spline f i t when end slope greater than slope between points. FIG. AI. 2 Conic spline f i t when end slope equals slope between points. 6.0 > M as I FIG.AI „ 3 UNIGRAPHICS Conic f i t to end slope greater than slope between points. J 1 1 1 L 0.0 1.0 2.0 3.0 4.0 5.0 6.0 7.0 8.0 9.0 FIG.AI.4 UNIGRAPHIC Conic f i t to end slope less than slope between points. I n f l e c t i o n p o i n t s l o p e . FIG. AI. 5 Conic spline f i t to i n f l e c t i o n point slope l e s s than slope between points. 6 . 0 4 . 0 2 . 0 a. a • 2 . 0 S l o p e between d a t a p t s . I n f l e c t i o n p o i n t s l o p e — Slope between points End point slope J i > I 0 . 0 1 . 0 2 . 0 3 . 0 4 . 0 5 . 0 6 . 0 7 . 0 8 . 0 O . 0 F I G . AI.6 C o n i c s p l i n e f i t f o r i n f l e c t i o n p o i n t s l o p e between s l o p e of d a t a p o i n t s . - AII.l -APPENDIX II A WORKED EXAMPLE OF CUBIC SPLINE CURVE FITTING The curve fi t t i n g routine called 'CUB.SPL' f i t s a given set of of data with piecewise cubics of the general form g(x) = a i + b^x-x^ + C i ( x - X i ) 2 + d ±(x-x i) 3 AII.l where x ± < x < x i + 1 . Given a set of ordinates x^ < x^ ••• < x n a cubic spline can be f i t over the region [x^x^] in small cubic parabolas which have the above general equation and at junctions x^ have point, slope and curvature continuity. 2 3 g(x) = a i + b 1(x-x i) + c i(x-x i) + d i(x-x 1) g'(x) = b ± + 2c i(x-x ±) + 3d i(x-x ±) 2 All.2 g"(x) = 2c ± + 6d.(x- X i) . Let us take the following set of data points for the S-curve. x O l 2 3 4 5 6 7 8 y 2.6 1.5 1.2 2.2 4.0 4.5 3.3 1.2 -2 Since the slope and curvature are not specified at the ends, we f i t a cubic polynomial to the f i r s t three intervals (four data points) and thereafter we f i t cubic polynomials in each subsequent interval ensuring point, slope and curvature continuity. To f i t a curve between x, and x, 1 4 2 3 g(x) = a2 + b- jX + c^x + d^x - All.2 -1 0 0 0 a l 2.6 1 1 1 1 b, 1.5 X 1 — 1 2 4 8 C l 1.2 _1 3 9 27 d l 2.2 2.6 -1.3333 .15 .083. A l l . 3 To f i t a curve between x. and x,.. 4 5 g(x 4) = g(3) = 2.2 g'(x 4) = b±+ 2c xx + 3dxx = 1.816 g"(x 4) = 2c Lx + 6djX = 1.8 g(x 5) = 4.0 Using these four conditions the following equations are obtained and can be solved to give the four coefficients a^, b^, c^ and d^ • 1 0 0 _1 a2 =  b2 * C2 " d„ = 3 1 0 4 29.5984 -28.3316 9.1494 -0.9166. 9 27 a2 2.2 6 27 X b2 = 1.8166 2 18. C2 1.8 16 64_ - d 2 - _4.0 _ All.4 - All.3 -The cubic equation for the curve between x^ and x,. is given as g(x) = 29.5984 - 28.3316 x + 9.1494 x 2 - 0.9166 x 3 . All.5 Similarly the equations for regions x, to x Q can be fitted as: region 5 6 g(x) = -124.206 + 87.0247 x - 19.6897 x 2 + 1.4866 x 3 All.6 region 6 7 g(x) = 740.724 - 431.9298 x + 84.1005 x 2 - 5.4327 x 3 All.7 region region X7 " X8 g(x) = -356.5129 + 72.6732 x +3.66795 x 2 -0.96422 x 3 All.8 X8 " X9 g(x) - -11353.3236 + 4785.5914 x - 669.6061 x 2 + 31.0964 x 3 All.9 A plot of these cubic spline curves is shown in Figure 1.7. - A I I I . l -APPENDIX I I I A WORKED EXAMPLE OF B-SPLINE CURVE FITTING The curve f i t t i n g routines called 'BSAPP' and 'BSPIN' f i t a given set of data with piecewise polynomials as defined in the text. The data points for the S-curve are as follows: x 0 1 2 - 3 4 5 6 7' 8 y 2.6 1.5 1.2 2.2 4 4.5 3.3 1.2 -2.0 Both B-spline curve f i t t i n g methods go through the following sequence: (a) Generate a knot sequence There are 9_ data points. Hence, there are JL5_ knots. The knot sequence t ^ to t ^ i s 0. 0, 0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 8, 8, 8 (b) Generate the basis functions Once the knot sequence has been generated the basis functions can be obtained from equations 3 and 4. The divided difference recurrence r e l a t i o n s h i p i s given i n the t e x t . However, f o r computational ease and computing ef f i c i e n c y , Carl de Boor's algorithm i s used w i t h i n G-SURF^. This algorithm goes through the following steps to produce the equations of the basis function i n each i n t e r v a l . Given a knot sequence [ t ± t j and k, the order of the B-spline to be generated, the basis functions can be obtained by the following steps: 1. b l := 1 2. for j = 1, ••• k-1 do. - AIII.2 -2.2 6L. := x - t , , . . 3 ±+1-3 2.3 Saved := 0 . 2.4 for r = 1, j , do. 2.4.1 Term := b / ( 6 R + 6 ^ , ) . r r j + l - r ' 2.4.2 b := Saved + 6R * Term. r r 2.4.3 Saved := * Term. J+l-r 2.5 b.,. := Saved. J+l The basis functions can be generated using the de Boor algorithm. Let 0 < x < 1 then i = 4 , because t^ < x < t b l =. 1 j = 1 6 R = (1-x) 6 1 = x r = 1 Term = — = 1 1-n+n b 1 = (1-x) Saved = x b 2 - x j = 2 6 R = (2-x) EL - A I I I . 3 -r = Saved Term = 1 * = (1-x) 1-x+n b 1 = (1-x) 2 Saved = x(l-x) r = 2 Term b 2 = x(l-x) + (2-x) j 2 X x_ (2-x)+x = 2 x x_ 2 2 x B 3 = 2 3 6 3 = (3-n) = X 2 Term = . / ^ l = (l-x ) : (1-x) + n b1 = (1-x) 3 2 Saved = x(l-x) Term x(l-x) + f (2-x) (2-x) + x b 2 = x(l-x 2 + (2-x)(l-x) |+ (2-x) 2 J 2 4 6 Saved = f - (1-x) + - f - (2-x) + ( 3-x) r Term - AIII.4 -2 2 2 b3 = J~ ( 1 ~ x ) + IT <2_x> + <3_x> f~ _ b4 ~ 6~ So the equations of the basis functions in the region 0 < x < 1 are B 2 > 4 = x( l - x ) 2 + (2-x)(l-x) f + (2-x) 2 | 2 2 2 B3,4 = f ~ ( 1 " X ) + f " ( 2 " X ) + ( 3 ~ x ) f " 3 B4,4 " 6^ * Similarly solving for B-spline basis function equations in the region 1 < x < 2 we obtain: _ (2-x) 3  B2,4 " ~~4 _ x 2 (3-x)(2-x)x (3-x) 2(x-l) B3,4 " 4 U x ) + 6 + 6 2 2 B4,4 = f~ ( 2 " x ) + f (3-x)(x-l) + (4-x) ^f-•o _ ( X - 1 ) 3 B5,4 " ~~~6 For region 2 < x < 3 we obtain: n - (3-x) 3 3,4 " ~~6 _ x 2 (4-x)(x-l)(3-x) (4-x) 2(x-2) B4,4 " 6 ( 3 ~ x ) + ~ 6 + 6 _ (x-l) 2(x-3) (x-l)(4-x)(x-2) (x-2) 2(5-x)  B5,4 " ~ + 2 + 6 _ (x-2) 3  B6,4 " ~ For region 3 < x < 4 we obtain: _ (4-x) 3  B4,4 " ~ - AIII.5 -B5,4 = i [(x-DC 4^) 2 + (5-n)(x-2)(4-x) + (5-x)2(x-3) ] B6,4 = 1 t(x-2)2(4-x) + (x-2)(5-n)(x-3) + (6-n)(x-3) 2] •a _ ( X - 3 ) 3 B7,4 " ~ 6 * Similarly the basis function in the intervals 4 < x can be found. (c) Generating the Two Extra B-Spline Coefficients The B-spline approximation to any function g(x) is given by n g(x) = S a B . i=l 1 1 , J We know B. . but we need to find a. . i . J • i There are two methods which can be used to find : 1. As there are (m+2) basis functions, we need (m+2) conditions to find a l l the a^'s. There are m data points, so we need two more conditions. These two conditions are obtained by making a linear interpolation in the f i r s t and last interval at the 0.333 and 0.666 of interval length respectively. In this example the two generated data points are: for the f i r s t interval (0.333, 2.6 + ( 1 , ^ Q ' 6 ) *3333 ) = (0.333, 2.234 ) (7.666, 1-2 + ( ~ 2 - ° ~ 1 , 2 ) * T ) and for the last interval 2. 8-7 = (7.666, - 1.0666) . - AIII.6 -Thus can be evaluated quite easily. Carl de Boor has proved that the a^'s are equal to the value of the data points"*. Thus, the may be given as: a l 2.6 a2 = 2.234 a3 = 1.5 a4 = 1.2 a5 = 2.2 a6 = 4.0 a7 = 4.5 a8 = 1.2 a9 = -1.0666 a i o = -2.0 . To illustrate how the B-spline basis functions add up to form the desired f i t the expanded region 3 < x < 4 is shown in Figure AIII.l with the basis functions drawn in there normalized form. In Figure AIII.2 basis functions are shown after they have been multiplied by their respective coefficients. This method is used in B-spline approximation (BSAPP). 2. a±'s c a n a^- s o be found by solving the matrix equality (6) green in the text. This method is used in B-spline interpolation (BSPIN). AIII.7 F I G . A3.1 B a s i s f u n c t i o n add up to form c u r v e . A I I I . 8 F I G . A 3 . 2 B a s i s f u n c t i o n a f t e r b e i n g t h e r e c o e f f i c e n t s . m u l t i p l i e d by - R . l REFERENCES 1. Faux, I.D. and Pratt, M.J., "Computational Geometry for Design and Manufacturing," E l l i s Horwood, Chichester, England, July 1968. 2. Duncan, J.P. and Mair, S., "Sculptured Surfaces i n Engineering and Medicine," Cambridge University Press, Cambridge, 1983. 3. Vickers, G.W., "Computer-Aided Manufacture of Marine Propellors," Computer Aided Design, Vol.9, No.4, pp.267-274, October, 1977. 4. Haw, R., G.W. Vickers and S. Bedi, "Documentation of G-SURF," 1983. 5. de Boor, C a r l , "A Guide to Splines," Applied Mathematical Sciences Vol. 27, Springer-Verlag(1978) 6. Moore, C a r o l y n , '"UBC Curve,' Curve F i t t i n g R o u t i n e s , " Computing Centre, U n i v e r s i t y of B r i t i s h Columbia, Vancouver, Canada, 1981. 7. Comstock, J.P., " P r i n c i p l e s of Naval Architecture", The Society of Naval Architects and Marine Engineers, N.Y., U.S.A., 1967. 8. Bezier, P., "Numerical Control Mathematics and Applications," John Wiley and Sons, 1972. 9. Divinsky, N., "Linear Algebra," Page F i c k l i n Publications, C a l i f o r n i a , U.S.A., 1975. 10. Gordon, W.J., "B-Spline Curves and Surfaces," CAGD Academic Press, G.M. Research Laboratory, ed. R.F. Riesenfeld University of Utah, 1974. 11. Schoenberg, I.J., "On Spline Functions," Mathematics Resarch Centre, U.S. Army, University of Wisconsin, Madison, Wisconsin 12. de Boor, C a r l , "On Calculating with B-Spline," J . Approx. Theoty,, Vol.6(1972) pp. 50-62. 13. Coons, S.A., "Surface Patches and B-Spline Curves," Syracuse University, N.Y., U.S.A. 

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0080806/manifest

Comment

Related Items