A History of Curves and Surfaces in Computer Aided Geometric Design [pdf]

1 A History of Curves and Surfaces in CAGD Gerald Farin Computer Science and Engineering Arizona State University Tempe, AZ 85257-5406 This article provides a historical account of the major developments in the area of curves and surfaces as they entered the area of CAGD – Computer Aided Geometric Design – until the middle 1980s. We adopt the definition that CAGD deals with the construction and representation of free-form curves, surfaces, or volumes. 1. Introduction The term CAGD was coined by R. Barnhill and R. Riesenfeld in 1974 when they organized a conference on that topic at the University of Utah. That conference brought together researchers from the U.S. and from Europe and may be regarded as the founding event of the field. It resulted in the widely influential proceedings [8]. The first textbook, “Computational Geometry for Design and Manufacture” by I. Faux and M. Pratt [63], appeared in 1979. The journal “Computer Aided Geometric Design” was founded in 1984 by R. Barnhill and W. Boehm. Its cover is shown in Figure 1. Another early conference was one held in Paris in 1971. It focussed on automotive design and was organized by P. B´ezier, then president of the Societ´e des Ing´enieurs de l’Automobile. The proceedings were published by the journal “Ing´enieurs de l’Automobile.” A series of workshops started in 1982 at the Mathematics Research Institute at Ober- wolfach; these were organized by R. Barnhill, W. Boehm, and J. Hoschek. Ten years later, a parallel development started at the Computer Science Research Institute Schloss Dagstuhl initiated by H. Hagen. In the U.S, a conference series was organized by SIAM (Society for Industrial and Apllied Mathematics); the first one being held 1983 at Troy, N.Y., and organized by H. McLaughlin. In the U.K., the conference series “Mathematics of Surfaces” was initiated by the IMA (Institute for Mathematics and Applications). A Norwegian/French counterpart was started by L. Schumaker, T. Lyche, and P.-J. Laurent. 2. Early Developments The earliest recorded use of curves in a manufacturing environment seems to go back to early AD Roman times, for the purpose of shipbuilding. A ship’s ribs – wooden planks emanating from the keel – were produced based on templates which could be reused many times. Thus a vessel’s basic geometry could be stored and did not have to be recreated every time. These techniques were perfected by the Venetians from the 13th to the 16th century. The form of the ribs was defined in terms of tangent continuous 2 Figure 1. The cover of the journal CAGD. It shows a drawing by P. Uccello (ca. 1430). Figure 2. Splines: a mechanical spline from the 1700s. circular arcs – NURBS in modern parlance. The ship hull was obtained by varying the ribs’ shapes along the the keel, an early manifestation of today’s tensor product surface definitions. No drawings existed to define a ship hull; these became popular in England in the 1600s. The classical “spline,” a wooden beam which is used to draw smooth curves, was probably invented then. The earliest available mention of a “spline” seems to be [51] from 1752. This “shipbuilding connection,” described by H. Nowacki [103], was the earliest use of constructive geometry to define free-form shapes, see Figure 2. More modern developments linking marine and CAGD techniques may be found in [10,100,115,136]. Another key event originated in aeronautics. In 1944, R. Liming wrote a book entitled “Analytical Geometry with Application to Aircraft” [95]. Liming worked for the NAA (North American Aviation) during World War II; this company built fighter planes such as the legendary Mustang. In his book, classical drafting methods were combined with computational techniques for the first time. Conics were used in the aircraft as well as in 3 Figure 3. R. Liming: conic construction of a fighter aircraft cockpit. the shipbuilding industries before, essentially based on constructions going back to Pascal and Monge. Traditionally, these constructions found their way onto the draftsman’s draw- ing board in the form of blueprints which served as the basic product definition. Liming realized that an alternative was more efficient: store a design in terms of numbers instead of manually traced curves. Thus he translated the classical drafting constructions into numerical algorithms. The advantage: numbers can be stored in unambiguous tables and leave no room to individual interpretations of drawings. Liming’s work was very influen- tial in the 1950s when it was widely adopted by U.S. aircraft companies. Figure 3 shows one of Liming’s constructions. Another researcher was also involved in the transition of aircraft drawings to computations; this was S. Coons, see [34]. Coons later gained fame for his work at MIT. Another early influential development for CAGD was the advent of numerical control (NC) in the 1950s. Early computers were capable of generating numerical instructions which drove milling machines used for the production of dies and stamps for sheet metal parts. At MIT, the APT programming language was developed for this purpose. A problem remained: all relevant information was stored in the form of blueprints,1 and it was not clear how to communicate that information to the computer which was driving a milling machine. Digitizing points off the blueprints and fitting curves using familiar techniques such as Lagrange interpolation failed early on. New blueprint-to-computer concepts were needed. In France, de Casteljau and B´ezier went far beyond that task by enabling designers to abandon the manual blueprint process all together. In the U.S., J. Ferguson at Boeing and S. Coons at MIT provided alternative techniques. General Motors developed its first CAD/CAM system DAC-I (Design Augmented by Computer). It used the fundamental curve and surface techniques developed at GM by 1Liming’s conic constructions were an exception but were not widely available outside the aircraft indus- try. 4 researchers such as C. de Boor and W. Gordon. In the U.K., A.R. Forrest began his work on curves and surfaces after being exposed to S. Coons’ ideas. His PhD thesis (Cambridge) includes work on shape classification of cubics, rational cubics, and generalizations of Coons patches [65]. M. Sabin worked for British Aircraft Corporation and was instrumental in developing the CAD system “Numerical Master Geometry.” He developed many algorithms that were later “reinvented.” This includes work on offsets [118], geometric continuity [116], or tension splines [119]. Sabin received his PhD from the Hungarian Academy of Sciences in 1977, a seemingly odd choice which is explained by the close collaboration between researchers in Cambridge, U.K, and their counterparts in Hungary, under the leadership of J. Hatvany. All these approaches took place in the 1960s. For quite a while, they existed in isolation until the seventies started to see a confluence of different research approaches, culminating in the creation of a new discipline, CAGD. Without the advent of computers, a disciplines such as CAGD would not have emerged. The initial main use of these computers was not so much to compute complex shapes but simply to produce the information necessary to drive milling machines. That information was typically output to a punch tape by a main frame computer. That tape was then transferred to the control unit of a milling machine. The main interest of a designer was not so much the milling machine; it was rather a plotter which could quickly graph a designer’s concepts. Early plotters were the size of a billiard table or larger; this was natural as drawings for most automotive parts were produced to scale. Plotting, or drafting, was so important that almost all of CAD was aimed at producing drawings – in fact, CAD was often considered to stand for “Computer Aided Drafting” (or ”Draughting,” in British English). Before the advent of these systems, trivial-sounding tasks were extremely time consuming. For example, producing a new view of a complex wireframe object from existing views would take a draftsman a week or more; using computers, it became a matter of seconds. A milestone in display hardware was the use of CRTs, or Cathode Ray Terminals. These went back to oscillographs which were used for many scientific applications. CRTs (not in use for CAD applications any more) displayed an image by “drawing” curves on a screen. Another dimension was added to simple display technology by adding an interactive component to it. The first interactive graphics system was invented by I. Sutherland at MIT in 1963, see [134]. His thesis was part of the CAD project at MIT; S. Coons was a member of his PhD committee. See Figure 4 for an illustration of Sutherland’s prototype. 3. De Casteljau and B´ezier In 1959, the French car company Citro¨en hired a young mathematician in order to resolve some of the theoretical problems that arose from the blueprint-to-computer chal- lenge. The mathematician was Paul de Faget de Casteljau, who had just finished his PhD. He began to develop a system which primarily aimed at the ab initio design of curves and surfaces instead of focusing on the reproduction of existing blueprints. He adopted the use of Bernstein polynomials for his curve and surface definitions from the very beginning, together with what is now known as the de Casteljau algorithm. 5 Figure 4. I. Sutherland’s Sketchpad system. Figure 5 shows a part of his 1963 technical report [44]. The breakthrough insight was to use control polygons (courbes `a pˆoles), a technique that was never used before. Instead of defining a curve (or surface) through points on it, a control polygon utilizes points near it. Instead of changing the curve (surface) directly, one changes the control polygon, and the curve (surface) follows in a very intuitive way. In the area of differential geometry, concepts similar to control polygons were devised as early as 1923, see [17], but had no impact on any