Early Investigation, Formulation and Use of NURBS at Boeing
n5321 | 2025年7月28日 21:58
Solid Modeling Solutions
Boeing Commercial Airplanes
Geometry that defines the shape of physical products has challenged mathematicians and computer scientists since the dawn of the digital age. Such geometry has strict requirements for accuracy and must be able to be understood as documentation for products that have a multi-year life expectancy. In the commercial airplane business, product life expectancy is measured in decades.
Geometry data represents points and curves in two dimensions and points, curves, surfaces and solids in three dimensions. A large number of descriptive forms are now used that range from precise canonical definitions (e.g., circle, sphere, cone) to general parametric forms (e.g. B~zier, non-uniform rational B-spline (NURBS), multi-resolution).
Solids add a level of complexity when bounded with general surfaces because of the need for reliable and efficient surface/surface intersection algorithms.
Core geometry algorithms are compute intensive and rely on floating point arithmetic. The mathematical theory of computational geometry is well documented and relies on infinity and absolute zero, a continuing problem for digital computers.
Some of the computational problems can be avoided when a closed form solution is available that does not require convergence to compute a result. As the shapes people modeled expanded beyond canonical forms, more general representations (with the associated computational problems) became necessary.
This article describes how Boeing initiated and supported a concerted effort to formulate a more computationally useful geometry representation.
Boeing Motivation and Experience
Engineering drawings were the dominant output of computer-aided design (CAD) systems in the 1970s and 1980s. The primary examples were a set of turnkey systems built from minicomputers and Tektronix direct view storage tube displays. The standalone systems produced large amounts of paper engineering drawings and gave users the famous 'green flash effect' from the Tektronix terminals.
The majority of the systems used two-dimensional geometry entities (mostly canonical forms) and integer arithmetic to provide acceptable performance. Work done at General Motors was turned into a software-only product called AD-2000 and into a number of turnkey (computer hardware and CAD software) offerings from Computervision, Autotrol, Gerber, Intergraph and McDonnell-Douglas Automation. Applicon developed its own system but the result was architecturally and computationally similar.
The other major player was Lockheed. Lockheed developed CADAM, which ran on an IBM mainframe and IBM refresh graphics terminals, to create the computer analog of a drafting table. Performance was key. The team built a program that regularly achieved sub-quarter response for a large number of users. Dassault noted the success of CADAM and built CATIA to not only generate engineering drawings but improve computer-aided manufacturing functions. CATIA also started on IBM mainframes and refresh graphics terminals like the IBM 2250 and 3250.
Other production tools were built inside large aerospace and automotive companies. These systems were based on three-dimensional entities and addressed early stages of design. In aerospace, the batch TX-90 and TX-95 programs at Boeing and the interactive, IBM-based CADD system at McDonnell-Douglas generated complex aerodynamically friendly lofted surfaces. The automotive industry followed a different path because they most often worked with grids of points obtained from digitizing full-scale clay models of new designs. Surface fitting was essential. Gordon surfaces were the primary form used in General Motors, Overhauser surfaces and Coons patches at Ford, and B~zier surfaces at Renault.
The third rail of geometry, solid modeling, started to receive a significant amount of research attention in the late 1970s. Larry Roberts started using solids as a basis in his Ph.D. thesis, Machine Recognition of 3D Solids, at MIT in the late 1960s. The Mathematical Applications Group (MAGI) developed Synthavision, a constructive solid geometry (CSG) approach to modeling scenes for nuclear penetration analysis in the early 1970s. The University of Rochester PADL system, the General Motors GMSOLID program and others started making more significant impact in the later 1970s.
Boeing and CAD
With all this variation in approach, how did Boeing get involved in the NURBS business? There were three distinct drivers:
Airplane surface design and definition
Experience with turnkey drafting systems
Convergence of the right people
Of Ships and Airplanes
Early commercial airplane design was derived from ship design. Both the terminology (airplanes have waterlines; they roll, pitch, and yaw; directions include fore, aft, port and starboard) and the fundamental design of surfaces (lofting to make airplanes fly smoothly in the fluid material called air) are still in use today.
The lofting process is based on sets of cross sections that are skinned to form an aerodynamic surface. The fundamental way surface lofters used to derive the curves was via conic sections. Most of the early techniques for generating families specified a circular or elliptic nose followed by some sort of elaborate spline representation. The splines could then be scaled to give the desired thickness within a specified shape. Once generated, a conformal mapping routine produced the classic Joukowski family of sections.
As Boeing computerized manual processes in the 1950s and 1960s, one of the earliest was lofting. Programs like TX-90, which evolved into TX-95, implemented the math equivalent of conic-based cross sections. These programs accepted batch card input and used listings, plots or a simple viewing program using a graphics terminal to review results. The lofts became the master dimensions and defined the exterior shape of an airplane.
All Boeing evaluations of geometry representation techniques placed a high premium on the ability of the form to represent conic sections exactly because of their importance in lofting.
The Drafting World
The advent of two new airplane programs (757 and 767) in the late 1970s placed a significant burden on the company. Because drawings were the lingua franca of both engineering and manufacturing, a concerted effort was started to improve the drafting process, and an explicit decision was made to buy commercial CAD products.
The two programs, located on different campuses in the Puget Sound region, chose different vendors to act as their primary CAD supplier. The 757 program chose Computervision (CV) CADDS, and the 767 chose Gerber IDS.
As the design and engineering job moved forward, staff members wanted to exchange information for parts that were similar between the two designs. The central CAD support staff, responsible for both systems, quickly discovered that translating geometry between CV and Gerber caused subtle problems. As a result, a design was put in place to translate all CV and Gerber entities into a neutral format. Translators were then built for CV to Neutral and Gerber to Neutral.
The design for the Geometry Data Base System (GDBMS) was therefore quite extensible, and translators were built to other turnkey systems. The GDBMS concept was ultimately adopted as the model for the Initial Geometry Exchange Standard (IGES), a format still in use.
The implementation of CAD caused two significant geometry problems. First, translation between systems, even with the neutral format, was fraught with problems. Geometry that was fine in CV could not be understood by Gerber and vice versa. The workaround to the problem required that users incorporate only 'translatable' entities on their drawings, which reduced the use of sophisticated, time saving features. Second, the overall set of entities was essentially two-dimensional. Boeing realized early on that the airplane design, engineering and manufacturing business required three-dimensional surfaces and solids.
Key People
Perhaps the biggest contributor to the Boeing geometry work was the willingness of managers, mathematicians and computer scientists to push the envelope. The team put together an environment that enabled the geometry development group to discover and refine the NURBS form. After validation of the computational stability and usefulness of the NURBS form, this new representation was accepted as the mathematical foundation of a next-generation CAD/CAM/CAE system better suited to Boeing.
The head of the central CAD organization, William Beeby, became convinced early on of the shortcomings of turnkey systems. He put a team of Robert Barnes, a McDonnell-Douglas veteran who understood the importance of CADD, and Ed Edwards, who brought experience of complex systems development from Ford and Battelle, in charge of the project.
Early experimentation focused on the display of complex surfaces. Jeff Lane and Loren Carpenter investigated the problem of direct rendering B-spline surfaces. Their work was important both academically through published papers [3] and from a sales perspective because potential users could see the results clearly.
Other early work focused on evaluation of then state-of-the-art solid modeling tools like Synthavision and PADL. Kalman Brauner, Lori Kelso, Bob Magedson and Henry Ramsey were involved in this work.
As the evaluations changed into a formal project, computing experts were added to the team in:
System architecture/user interface software (Dave Kasik)
3D graphics (Loren Carpenter, Curt Geertgens, Jeremy Jaech)
Database management systems (Steve Mershon, Darryl Olson)
Software development for portability (Fred Diggs, Michelle Haffner, William Hubbard, Randy Houser, Robin Lindner)
The team pushed the envelope in all of these areas to improve Boeing's ability to develop CAD/CAM applications that were as machine, operating system, graphics and database independent as possible. New work resulted in Vol Libre, the first fractal animated film [1], user interface management systems [2] and software that ran on mainframes, minicomputers, workstations and PCs.
The rest of this article focuses on the key NURBS geometry algorithms and concepts that comprised the geometry portion of the overall framework (called TIGER - The Integrated Graphics Engineering Resource). Robert Blomgren led the efforts of Richard Fuhr, Peter Kochevar, Eugene Lee, Miriam Lucian, Richard Rice and William Shannon. The team investigated this new form and developed the robust algorithms that would move NURBS geometry from theory to a production implementation to support CAD/CAM applications. Other Boeing mathematicians (David Ferguson, Alan Jones, Tom Grandine) worked in different organizations and introduced NURBS in other areas.
Investigation into NURBS
As its name implies, the Boeing geometry development group was the portion of the TIGER project responsible for defining, developing and testing the geometric forms and algorithms. The functional specifications listed some 10 different types of curves (from lines to splines) and an extensive list of surfaces.
There was no requirement for upward compatibility with older design systems. The most difficult requirement was that no approximation could be used for a circle.
Early research pointed to the importance and difficulty of the curve/curve, curve/surface and surface/surface intersection algorithms. As it turned out, the development of robust intersections was critical to the Boeing formulation of the NURBS form.
Curve/Curve Intersection
An excellent and meticulous mathematician, Eugene Lee, was assigned the task of developing the curve/curve intersection algorithm. The representations needed for each of the required curve forms had already been defined. The initial approach, special purpose intersection routines from each form to the other, would have resulted in far too many special cases to maintain easily.
Lee realized that each segment could be represented as a rational Bzier segment at the lowest segment level. In short, doing one intersection would solve them all. It was a great step forward, but few people knew anything about rational Bzier segments. The primary references consisted of Faux and Pratt's geometry book, deBoor's Guide to Splines, and Lane and Riesenfeld's B~zier subdivision paper. No reference contained significant discussion of rational splines.
The Lane and Riesenfeld subdivision paper was used as the basis for Lee's first curve/curve intersection algorithm. The process relied on the fact that a Bzier curve could be very easily and quickly split into two Bzier curves. Since the min-max box is also split in two, box/box overlap was used to isolate the points of intersection between two curves. This algorithm gave reasonably good results.
Rational B~zier
Since Lee needed to convert circles and other conics to rational Bzier curves to allow use of the general curve/curve intersector, he became the Bzier conics expert. His work eventually led to an internal memo of February '81, A Treatment of Conics in Parametric Rational B~zier Form. At that time, Lee felt this memo was "too trivial" and "nothing new," and it was several years before he incorporated it into later publications. The content of the memo was foundational because it contained all the formulas for converting back and forth between conics defined by the classical methods in the plane and the new 3D definition of the rational Bezier conic containing three weighted points.
B~zier to NURBS
The transition from uniform to non-uniform B-splines was rather straightforward, since the mathematical foundation had been available in the literature for many years. It just had not yet become a part of standard CAD/CAM applied mathematics.
The next step was to combine rational Bzier and non-uniform splines. Up to this point, the form P(t) = Σi wiPi bi(t) / Σi wi bi(t) (1) was used for nothing more complex than a conic Bzier segment.
As the searching for a single form continued, knowledge about knots and multiple knots led to the observation that B~zier segments, especially for conics, could be nicely embedded into a B-spline curve with multiple knots. This now seems simple because it is easy to verify that equation (1) for P(t) is valid for B-spline basis functions as well as Bernstein basis functions. By the end of 1980, the complete representation of all required curves by a single form was complete, and the form is now known as the NURBS.
We quickly realized the importance of this new geometry form. The form could provide a concise and stable geometric definition to accurately communicate design data to and from subcontractors. It would no longer be necessary to send a subcontractor 5,000 points to well define a curve segment; the few NURBS coefficients could be used instead. Therefore, Boeing proposed NURBS as an addition to IGES in 1981.
Properties
This brief overview lists many properties of the NURBS form. These properties further were observed early in the Boeing work on the form and drove NURBS to become the de facto standard representation for CAD/CAM geometry.
The NURBS form is extremely well suited for use on a computer since the coefficients, the Pi given in equation (1) above, are actually points in three dimensions. Connecting the coefficients together to form a simple polygon yields first approximation to the curve. The first and last points of the polygon are usually the actual start and end point of the curve.
Mathematically, a NURBS curve is guaranteed to be inside the convex hull of the polygon. Therefore, knowing where the polygon is means that the location of the curve is also known, and useful decisions can be made quickly. For example, the polygon may be used to determine a min-max box for each curve. The check for box/box overlap is very fast. So the curve/curve intersection process can trivially reject many cases because the bounding boxes do not overlap.
Another property of the polygon is that the curve cannot have more "wiggles" than the polygon does. Hence, if the polygon does not have an inflection, neither does the curve. When the curve is planar, this means that any line cannot intersect the curve more times than it intersects the polygon.
Simple linear transformations (translate and rotate) can be made only to the polygon, a simple operation.
As splines, a NURBS curve may consist of many segments (spans) that are connected together with full continuity. For example, a cubic curve may have C2 continuity between each span. Such curvature continuity is important in aerodynamic and automotive design.
Another NURBS advantage is that the continuity of each span is also under local control. In other words, each span of a cubic is defined by only the four neighboring coefficients of the polygon. Local control is guaranteed because only the four spans are modified if one Pi is moved.
As a continuous set of spans, a NURBS curve is defined on a set of parameter values called knots. Each knot is the parameter value at the boundary between the spans. It is often desirable to increase the number of spans. For example, this occurs when more detail is needed for a curve in one region. Adding a new knot into the existing knots is a powerful feature that increases the number of spans by one without changing the curve.
Surfaces
Given a set of basis functions like those for the NURBS form, it is a straightforward mathematical exercise to extend the curve definition to the corresponding surface definition. Such a representation is referred to as a tensor product surface, and the NURBS surface is such a surface defined over a square domain of (u,v) values. Holding one parameter yields a NURBS curve in the other parameter. Extracting and drawing the NURBS curves of the surface at each of the u and v knot values results in a satisfactory display of the surface.
The one non-trivial drawback to tensor product surfaces is that all surfaces must have four sides. One side must collapse to a point to obtain 3D, three-sided surface. This point is referred to as a pole or singularity. The partial derivatives of the surface must be calculated carefully at a pole. This is particularly important when surfaces are to be trimmed since the path of trimming in the (u,v) space must be determined correctly as the path approaches the pole.
Surface/Surface Intersection
Not all early ideas and experiments gave desirable results. Curve/curve subdivision worked well as the basis for the curve/curve intersection algorithm. However, using surface/surface subdivision as the basis for surface/surface intersection proved problematic.
Peter Kochevar developed and implemented the first Boeing NURBS surface/surface intersection algorithm using subdivision. The results quickly brought available computing resources to a halt because of computational complexity and data explosion.
Upon further analysis, it was observed that if the end result is a point, such as in curve/curve intersection, subdivision gives a good result since the segments become so small at the lowest level that line/line intersection can be used. But if the end result is a curve, which is the normal result of surface/surface intersection, the small surface segments become planes at the lowest level and the result depends on plane/plane intersection. This yields thousands of very short line segments that don't even join up. No satisfactory approach was discovered for surface/surface intersection until later.
Solids
Even in 1980, Boeing realized the importance of solid modeling. Kalman Brauner led a solids group that worked alongside the geometry development group. Their task was to design a state of the art solid modeler to develop the requirements for Boeing's aerodynamic and mechanical design processes.
The requirements were given to the geometry development group to develop and test the appropriate algorithms. This was a useful cooperative effort between groups since the requirements for doing Boolean operations on solids are very stringent. Not only do the various intersections have to give accurate results, but they also have to be extremely reliable. Everything in a Boolean fails if any one of the many intersections fails.
This work on solids was later incorporated into the Axxyz NURBS based solid modeler.
Migration from Boeing Outward
Boeing was able to demonstrate the value of NURBS to the internal design and engineering community as well as a number of CAD vendors through TIGER. A decision to launch a new airplane program (the 777) resulted in a decision to purchase a next generation CAD system from a commercial vendor rather than build one internally. Ultimately, Dassault's CATIA running on IBM mainframes was chosen as the CAD system used to design and build the 777.
To IGES
One of first adopters of NURBS was the IGES community. Dick Fuhr, of the TIGER geometry development group, was sent to the August 1981 IGES meeting where he presented the NURBS curve and surface form to the IGES community. At this meeting Boeing discovered that SDRC was also working with an equivalent spline form. The members of the IGES community immediately recognized the usefulness of the new NURBS form. In the years that have followed, NURBS has become the standard representation for not only CAD/CAM but also for other uses (e.g., animation, architecture) of computational geometric modeling.
To Axxyz
Even though Boeing chose to design commercial airplanes with CATIA, other groups expressed interest in the TIGER NURBS work for government and commercial purposes. The core NURBS implementations were given to Boeing Computer Services and a number of the technical staff built a computer independent CAD/CAM/CAE software system marketed under the name Axxyz. Axxyz debuted formally at the 1985 Autofact conference and was eventually sold to General Motors and Electronic Data Systems.
The Axxyz group did early implementations of NURBS surface bounded (B-Rep) solids as part of the first commercial product release. Topology information, based on the twin edge boundary representation, was added to enable trimmed NURBS surfaces to be used as faces that were combined into a shell structure defining a solid.
Other applications were added that associated engineering, manufacturing, and drafting data directly with the NURBS geometry. This approach added a wealth of tessellation and inquiry capabilities to the basic geometry algorithm library.
To Intergraph and Dassault
One of Boeing's goals was to improve the use of NURBS in commercial CAD packages. The algorithms that led to the software implemented in TIGER had all been documented. Both Dassault and Intergraph received copies of the algorithm books for ultimate implementation in their products.
Hard Problems
NURBS implementation pushed compute power of the late 1970s and 1980s significantly. Performance tuning was always an adventure and permeated the various algorithm implementations.
The most critical problem, intersection, has already been discussed for both curve/curve and surface/surface cases. Other issues, like display and interaction, tolerance management and translation also arose.
Display
The first interactive NURBS implementations were delivered on calligraphic, vector-only graphics devices (the Evans and Sutherland Multi-Picture System). As the technology progressed into raster graphics, other work was done to generate solid, shaded images. From an architectural perspective, Boeing treated NURBS curves, surfaces and solids as standard objects that the graphics subsystem (not the application) could draw directly. In this way, changes could be made in display resolution as zooms occurred without involving the application.
Vector rendering of NURBS curves and surfaces relied on a chord-height tolerance technique. The technique, while slower than equal subdivision, was more aesthetically pleasing because areas of high curvature were drawn with more line segments. Shading used a similar technique to tessellate surfaces into polygons that were then used as input to a standard polygon shader.
Tolerances
Like any digital form, computation of results stops before reaching an exact zero. Perhaps the most difficult values to manage were the tolerance epsilons that indicated that an answer had been found. Experimentation on the best set of tolerances was continual to balance performance and accuracy. The tolerance values were changed frequently, and no one truly understood their interrelationships.
Translation
The Boeing NURBS implementations stored all entities in that form, even if the form that the user input was simpler or used less storage. In this way, a single intersection routine would be used for curves and a second routine for surfaces. Conceptually, the design was quite clean but numerous attempts to improve performance resulted in some special cases. Even so, the special cases were embedded in the intersection routines and not in the database form of the NURBS entities.
This approach caused some interesting problems with translation to terminology the user understood and to other CAD systems that understood more primitive entities and may not have accepted rich NURBS forms. The solution to the problem was to develop a set of routines that would examine the NURBS definition to see if it was close enough to being a line or a circle to call the entity a line or a circle. This information was used dynamically to report the simplest math formulation to the user. In addition, the same technique was useful when data was being translated into forms for other systems and applications. When a NURBS curve could be identified as an arc, an arc entity was generated for IGES and a radial dimension used in the drafting package.
Conclusion
In spite of our best efforts, 3D design applications require users to become geometry experts. NURBS is no panacea. But the foundational NURBS work done at Boeing did demonstrate the utility of the approach. As a result of this pioneering work, NURBS is still the preferred form to precisely represent both complex curves and surfaces and a large number of simple curves, surfaces and solids.
