| t I l I I. . \I .\I. v w l. I. J; ,.I\...:. A.... 4 I(.v‘1 . .I I. .» .v c ‘ 4 . II . . D ‘ l -' I 0" '- l , Io |Iv._‘u. ,.P V‘# I "?&n "m .. Z } I ~ I ! A '7! « I- 'I u! h'lllln III-I .Wo. ilt . y [bill I, .. 1|." I I WWW!WWI!IIWHIWW THESis 310753 9234 . _-.. .- L” “‘7’ 3'3; ‘2? E§:£.;;,.4.,i~3. 3:3 “Stet: Um: 33;: tyJ mismcertifythathe dissertationenfifled SURFACE ASSESSMENT USING COLOR GRAPHE cs pmted by Martin John Vander'ploeg hasbeenacceptedmsfinfinmmt “mem‘luilunemsfor PhLDL in W Engineering “M 3m M‘ijl'ofcsul’ MUM/92> / / "Sui-Wm- 01mm ‘ _ _ 0‘27“ MSU RETURNING MATERIALS: P1ace in book drop to LJBRARJES remove this checkout from ” your record. FINES W111 be charged if book is returned after the date stam ed be1ow. 2:\ p 23 K328 ‘F-‘x’j’x A"; . ‘M‘ L'Q’.’ 5‘9 Lgfi‘ 2&0 n’5{l “flag. "QM , L1,) ’11". 7 3’7 ; i ?7}3 SURFACE ASSESSMENT USING COLOR.GRAPHICS By martin John Vanderploeg A DISSERTATION Smeitted to Michigan State University in partial fulfilJment of the requirements for the degree of DOCTOR OF PHILOSOPHY Department of Mechanical Engineering 1982 5 (”c-"3* A L“) 91‘ - ® l ABSTRACT SURFACE ASSESSMENT USING COLOR GRAPHICS By Martin John Vanderploeg Modern techniques for the design and production of smooth skins , such as car bodies and aircraft wings and fuselage, depend upon the development of a database which accurately represents the surface. Before the database can be' used for production, it must be checked for possible errors. Such errors may result fran bad raw data, as from errors introduced in a digitizing process, or fran designer errors. Typically these databases are very large, maldng the checking process tedious and expensive. Current checking methods include inspection of flow lines or sections, and any include building prototypes . This dissertation develops a method for surface checking using shading and raster graphics. This method uses a scan line method which is based on improved numerical techniques and takes advantage of the rapidly decreasing cost of computer memory. These developments have resulted in a fast and accurate check procedure. The dissertation illustrates the ability of the algoritrm to detect specific surface flaws using a small test database. The ability of the algorithn to "assemble" objects on the screen is also demonstrated using a large database for an airplane fuselage and canopy. ACIQJCMIEDGEMENI’S I would like to extend special thanks to the people at General Dynamics for funding this work. Specifically, I thank Mr Bernard Breen and Mr. Larry Tucker for their technical assistance and support. I also wish to thank the other members of my cannittee Drs. Erik Goodmn and Ronald Rosenberg for their guidance and technical support . A Special thanks go to my parents, Nbrvin and Joann Vanderploeg for their loving support throughout an; graduate work. Finally, I would like to extend sincere thanks to my major profes- sor and good friend Dr. James Bernard, for his guidance, constant encouragement, and especially for his extreme patience. 11 TABLE OF CONTENPS HSTOFTM 0.0....OOOOOOOOOOOOOOOO.............OOOOOOOOOOOOOOV HSTOFMGMo 000000 0.00.000000000000000...OOOOOOOOOOOOOOOOOOOVj. Chapter I II INIRODUCIION .....OOOOOOOOOOOOOOO0....0.00.00.00.000000000001 CURVE AND SURFACE DEFINITIONS .......... .................... 2 2.0 Generalized Curve and Surface Definitions .... ..... ....2 2.1 Parametric Curves and Surfaces ............. ........... 5 2.2 BiCUbic Pmtric SWfaceS 00.0.0000...00.0.00000000006 (I) DATABASE ERRORS AND METHODS OF DETECTION ........ ........ ... 3.0 Database Structure ....................................8 3.1 Surface Checking ......................................8 3.2 Types of Database Errors ..............................9 3.3 Surface Checking Using Shading ........................11 INTRODUCTION TO SURFACE SHADING AND DISPLAY ........ . ....... 1n 0 Design.Environment Requirements .......................1A 1 Raster Graphics .......................................1A 2 mmaDEMwof&me.NHHHHNHHHHHHHJS 3 Previous work in Surface Shading and Display ..........17 4.3.1 Display Techniques for Polygon Surfaces ........17 I4.3.2 Display Methods for Parametric Surfaces ........22 ASURFACE SHADING ALGORITHM FOR DESIGN ......................29 Introduction ...... ..... ...............................29 The Patch Preprocessor ................................29 The Y Scan ............................................33 The X Scan ............................................33 The Hidden Line Problem ............ ...... .............3A Solutions of Nonlinear Equations ......................39 Approximate Methods ...................................A2 :innmmny ......... .................................. ....AA 0 «lounzwml-lo U'IU'IU1U'IU'IU'IUlm iii VI Algoritm Evaluation ....................................... 145 6.0 Introduction .......................................... A5 6.1 Error Detection ....................................... A5 6.2 Image Generation for a New Light Source ............... A8 6.3 Compute Times ......................................... A9 6.4 Object Assembly ....................................... 50 6.5 Surface Checking Scheme ............................ 2. . .52 VII CONCLUSIONS ............................................. ...55 APPENDICES ...................................................... 56 REFERENCES ...................................................... 86 iv LIST OF TABLES l. Canpute Times ....... ........50 \O (I) N 0\ U1 .1? LA) N H O O O 5.: O 11. 12. 13. 1A. 15. 16. 17. 18. 19. 20. LIST OF FIGURES Flow Line Display ofBump ............................... 10 Gross Error inBump 10 Missing Data inBump 12 Slope Discontinuity ianp 12 Magnified End View, Slope Discontinuity in Bump ......... 13 Viewing Screen and Screen Coordinates l6 Polygon Apprexirration of Bicubic Patch l8 Scan PlaneandIntersection Curve ..... . ..... ........19 Number of Intersection Curves onaPatch 21! Effect of Silhouette Edge on the Number of Intmection mes O0.00.00.......OOOOOOOOOOOOI0.0...00.00.26 Typical Intersection Curve Endpoints 31 Illustration of Active Curve Updating ..... . ...... .3...6 Interior Intersection of 'IVwo Patches ..... 38 Division of Intersection Curves for Interior Intersectims I................OOOOOOOOOOOOOOO......OIOOOOOIHO smed amp ......OOOOOOO00.00.00.000.........OOOOOOOOOO....“6 Shaded Bump with Slope Discontirmity 147 Shaded Bump with Slope Discontirmity, Appmxjmte mthOd O......OOOOOOOOOOOOOOOOO0.00.00.00.000000u7 Shaded Bump with Slope Discontinuity, Different LigIt Source ......OOOOOOOOOOOOOOOO..OOOOOOOOOOOOOL‘B Alrcraf‘tWing... ...... ..... ....... . .......... . ..... .. ...... 51 SMdamcmWi—Ig, lower OO......OOOOOCOOOOCO0.000000000051 Vi 21. 22. 23. A1. B1. B2. BB. BA. B5. B6. B7. B8. Cl. D1. D2 0 Shaded Aircraft Wing, Lower plus Half of Upper .............52 Shaded Aircraft Wing, Entire Surface ..53 Shaded Aircraft ................ ..... . ........ ......... 53 Definition of Patch.Boundaries .............................57 Calculation.of Boundary Endpoints ..........................63 @nmdemsmaSflmwmemg.unnnnuuuunnfi Method of Calculating Silhouette Endpoints ............ ..... 67 Simple Pairing Cases ............. ....... ....... ........ ....68 Pairing with One Silhouette Endpoint .......................69 Single Boundary Ehdpoint ...................................71 Determination of Leading or'I‘railing Status ................72 Pairing Example ............................ ................ 7A A Comparison of Newton's Direction and the secarlt DireCtion OOOOOOOOOOOOOOOOO0.00000000000IOOOOO0.00.0076 The Ratio ds/dt Along the Intersection Curve u .............83 Relationship of the u and x Directions .....................8A CHAPTER I Introduction Modern techniques for the design and production of smooth skins , such as car bodies and aircraft wings and fuselage, depend upon the de- velopment of an accurate mathematical representation of the surface . Before the surface definition can be used for analysis or production, it must be checked for possible errors. Such errors nay result from bad raw data, as from errors introduced in a digitizing process, or fran de- signer errors. Typically, the checking process is tedious and expen— sive. This thesis develops a method for surface checking using surface shading and raster graphics that can reduce both cost and time required to check a surface. The next chapter discusses the mathematical repre- sentation of surfaces. Chapter 3 presents several categories of sur- face errors and current methods of surface checking. Chapter A reviews current methods of surface shading and display, and Chapter 5 presents an algorithn developed in this thesis especially for the purpose of sur- face checldng. Chapter 6 then presents sane examples, and Chapter 7 presents conclusions. CHAPTERH Curve and Surface Definitions 2.0 Generalized Curve and Surface Definitions One way to define a curve in space consists of two transendental equations of the form: Fl(x,y,z) = 0 (2.0.1) F2(x,y,z) = 0 where x, y, and z are three independent spacial coordinates. The curve consists of the locus of points which simultaneously solve these two algebraic equations. Curves can also be defined parametrically. The curve becomes the locus of points whose coordinates are functions of a single independent parameter. The parametric form of a curve is: x = fl(s) y = f2(s) (2.0.2) 2 = f3(s) The two forms may be illustrated using a straight line. The alge- braic form consists of the equations for two planes, which form a line where they intersect. The algebraic form of the line is: ll 0 Fl(x,y,z) Alx + le + Clz + D1 (2.0.3) II 0 F2(x,y,z) A2x + B2y + C22 + D 2 The parametric form of the line is: (2.0.1!) For simple curves it is possible to transform fran one form to the other. As the equations became more complicated it is difficult or impossible to make this transformation. Analogous forms also may be written to define surfaces. The alge- braic form consists of one algebraic equation. G(x,y,z) = 0 (2.0.5) The surface is defined by the locus of points that solve this equation. The parametric form defines the surface as the locus of points whose coordinates are functions of two independent parameters, 5 and t . X = 81(S,t) y = g2(s,t) (2.0.6) 2 = g3(s,t) A plane may be used to illustrate the two different equation forms of a surface. The algebraic form is: G(x,y,z) = Ax + By + Cz + D = 0 (2.0.7) The parametric form is: E15 + Glt + H1 M II ‘< ll E23 + G2t + H2 (2.0.8) = + + 2 E38 G3t H3 Again, transformations between the two forms are possible only for sim- ple surfaces . The next section discusses the advantages of the para- metric form, which will define surfaces throughout this thesis . 2 . l Parametric Curves and Surfaces When producing shaded images from mathematical surface definitions , it is convenient to use the parametric form (1,2,3). One favorable pro- perty of the parametric form is the one—to-one mapping of spatial coor- dinates x, y, and z to the parametric coordinates s and t. A second advantage is the existence of well-behaved partial derivatives every- where on the curve or surface. The importance of well-behaved partial derivatives will become evident as surface shading algorithms are dis- cussed. Throughout this thesis, the vector normal to the surface will be used for shading purposes. The normal vector of a parametric surface at a point is carputed by taking the cross product of two vectors tan- gent to the surface at that point. A convenient pair of tangent vec- tors are: -T a: 3x " By " 82 " -T a 3x " By " az " _ —'I' N-VS xvi (2.1.3) Complex curves are typically broken up into several segments to facilitate fitting the curve with a series of low order polynomials . In a similar way, complex surfaces are often broken up into several , patches to facilitate fitting the surface with low order polynomials . The boundaries of a patch are usually determined by limits on the parametric values s and t. A cannon convention allows these parameters to vary from zero to one. 2. 2 Bicubic Parametric Surfaces A popular surface representation is the bicubic polynamial (A). Although the ideas and analysis which are tre basis of this thesis require only that the surface is parametrically defined, the bicubic surface is used throughout for illustrative purposes. Equations for bicubic surfaces appear in many different forms. A general form of the equation is: 3 3 x(s,t) = 2 2 X13 51 tJ (2.2.1) i=0 J-o where XiJ are constants. There are similar equations for y and 2. Each patch is then delineated by A8 constants. Equation 2.2.1 is often written in matrix form. The constants are contained in three A-by-A matrices, one for each equation. The matrix form is: x(s,t) = [1 t t2 t3][x] 1‘ (2.2.2) where the matrix [X] contains the constants XZU . Bicubic parametric surfaces:may also be represented in an alter- native form which have been derived so that the constants defining the patch have geometric meaning. This form is A A x(s,t) = 1:1 3:1 “Fi(s)*F3(t) (2.2.3) where Fi(s), so—called blending functions, are cubic polynomials. In this case the constants Xij are geometric properties of the surface patch, such as spatial values or tangent vectors at various points on the patch. Similar equations are written for y and 2. One specific bicubic surface is the Coons surface. Coons surfaces are presented in detail in (A) and (5). Figures 1 and 2 are examples of surfaces defined by Coons patches. CHAPTER III Database Errors and Methods of Detection 3.0 Database Structure A typical surface description is comprised of multiple surface patches. The database defining the surface consists of the constants which define the patches. For example, the bicubic patch is defined by A8 constants. The surface database for a bicubic surface then contains N blocks of A8 constants, wrere N is the number of patches ccnprising the surface . When generating a database, errors may be introduced by the designer, or by the hardware. For example, mating parts may be de- signed by different people , introducing interference problems and slope mismatches along boundaries. Hardware related problems such as round off and hardware conversions may also create errors. In addi- tion, design changes may create unexpected flaws. Detecting these errors , or so called, surface checking is an important design problem. 3.1 Surface Checking There are three basic surface checking techniques which are commonly used. One method is manual inspection of the constants defining the sur- face. This requires knowledge of the surface being modeled, and an understanding of how much each constant affects the shape of the patch. 8 This:method is time consuming and inefficient for surfaces with a large number of patches, and considered impractical for production environments. The second method of surface checking uses sections and flow lines to visually inspect the surface. Flow lines are constant s and t lines drawn at given intervals over a.patch. They are easily computed and displayed. A viewpoint is chosen and the spatial coordinates of the constant 5 and t lines are projected onto a plane and displayed on a plotter or a graphics terminal. Figures 1 and 2 illustrate surfaces displayed using flow lines. Section cuts may also be displayed. Sec— tions, which.are:more tedious to compute than flow lines, are useful for detecting surface flaws since they can be cut in any desired direction. Hewever, it is usually not practical to make enough section cuts to properly check the surface. A third method, which is often used serially with visual inspec- tion via flow lines or sections, produces a three dimensional repre- sentation of the surface. This method uses the mathematical surface representation to drive a numerically controlled milling machine which produces a model of the surface. The model can then.be inspected for flaws. This method is effective, but far more expensive than other techniques. 3.2 Types of Database Errors When comparing the usefulness of different surface checking techniques, it is helpful to classify different types of errors that can exist in a database. The "bump" database, displayed in Figure 1, will be used to illustrate the different types of errors. The bump 10 Figure 1. Flow Line Display of Bump Figure 2. Gross Error in Burrp 11 is made up of four patches which are based on 192 separate data entries in the database. The first class of database errors contains gess errors. These errors are easily detected using flow lines. Figure 2 presents a gross error in the "bump", caused by one incorrect entry in the database. The second error classification is missing data. Again, these errors are easily detected using flow lines. An example of missing data is presented in Figure 3, where one of the patches has been left out. More difficult errors to detect are small slope discontinuities between patches. Figure A is an example of a surface containing an unwanted slope discontinuity. From this view it is impossible to visually detect the problem. With prior knowledge of the discontinuity ‘ location it is possible to choose a view looking down the patch bound- ary wrere the lepe discontinuity exists. After magdfication, this view is displayed in Figure 5, which is a closeup view of the patch centerline area as seen from the direction of arrow A in Figure A. Tine slope discontinuity is now apparent, but finding the proper view depended on knowing the location of the slope discontinuity. For surfaces with many patcres , the location of slope discontinuities are generally unknown. This makes identifying them with flow lines difficult, thus detection of this kind of error is often delayed until a model or prototype is constructed. 3.3 Surface Checking Using Shading To avoid delays and costly proofing runs on numerical controlled machines, it is very desirable to facilitate detection of errors in l2 Figure 3. Missing Data in.Bump \\\ ‘K 1 Figure A. Slope Discontinuity in Bump Figure 5. Nagnified End View, Slope Discontinuity in Bump the database using computer graphics. One pranising’ technique is surface shading. By displaying the shaded surface on a variable intensity raster terminal, it is possible to locate subtle errors. The idea origirates from the ability of the human eye to detect small deviations on smooth reflective surfaces . As an example, surface-re- lated flaws on a car body are easily detected by the human eye, yet they are very difficult to find using only engineering drawings of sections or flow lines. If the surface can be represented visually by a carputer as a reflective surface, these subtle errors can be detected. The next section will introduce terminology and concepts concern- ing computer-generated pictures . Previous work done on surface shading will then be discussed. CHAPTER IV Introduction to Surface Shading and Display A . 0 Design Environment Requirements When computer surface shading techniques are used for surface checking, the visual display must represent the surface properties accurately so that flaws may be identified. Shading algorithms often use approximations which make shading calculations easier, but these approximations may hide subtle flaws on the original surface . Ch the other hand, accurate processing of the details of the surface may require tedious calculations. Since interactive programs are ideal for a design environment , fast shading algorithms are desirable so that a designer is not required to wait long periods of time for each image. The question of whether high accuracy or rapid calculation should have higher priority will be addressed in later chapters. The next section describes how images are produced on a raster device . Basic concepts of surface display will then be presented, followed by a discussion of previous work done in the area of surface shading. A.l Raster Graphics The raster screen is an increasingly popular method of displaying computer generated images. A common example of a raster device is the 1A 15 television. Raster screens are made up of many small units called raster units or pixels. For a gray scale device, the user has control over the intensity of each pixel ranging from white to black. For color raster (devices, the color and intensity of each pixel can be controlled. The resolution of a raster device refers to the number of pixels on the screen. A screen with a large number of pixels is said to have good resolution, meaning each individual pixel is hard to discern, and the edges of objects being displayed appear smooth. A.2 Raster Display of Surfaces To aid in the discussion of surface display techniques, it is con- venient to define a set of screen coordinates. Figure 6 illustrates the orientation of screen coordinates used in this discussion and throughout this thesis. To display the color of surface on a raster screen requires that the intensity and color of each pixel be canputed. This requires proj ecting a three dimensional surface to the viewing screen. Each pixel is then mapped to a point on the surface. The properties of the surface at that point are then used to canpute tre intensity of the pixel. Typically, the mapping of a pixel to a point on the surface requires the construction of a sightline frem tre viewpoint through the pixel being mapped. All patcl'es intersected by the sightline are determined. These patches are compared to determine which patch is visible along the sightline. l6 Scan Line Figure 6. Viewing Screen and Screen Coordinates 17 Methods used to compute the sightline-patch intersection and normal vector at trat intersection point depend on the type of surface patch. Existing algorithms for solving these problems will be dis- cussed in the next section. A . 3 Previous Work in Surface Shading and Display Literature in the area of computer-generated surface shading started appearing in the late 60's and early 70's. Since then the tOpic has been well represented in the literature. A good review of current literature in surface shading is presented in Reference 6 . Early shadirng techniques were based on surfaces consisting of flat patches (polygons) . A.3.1 Display Techniques for Polygon Surfaces Curved surfaces may be approximated using many small polygons. For example, Figure 7 illustrates an approximation of a bi-cubic patch using polygons . Surface representations consisting of polygons are called polygon-type surfaces . The advantages and disadvantages of three well known polygon type surface display methods will be presented here . The War-nook method (7) uses a depth priority algorithm to display surfaces constructed of polygons. This algorithm uses windows , or areas of the screen, which are successively subdivided into four smaller wirndows until the window is canpletely covered by a visible polygon. The window is then displayed. The subdivisions can continue until the windows are the size of one pixel. The major drawback of this method is trat the pixels are not assiged in an orderly fashion, an inconvenient procedure for a raster device. 18 W Figure 7. Polygon Approximation of Bicubic Patch The method develOped by Newell, Newell, and Sancha (8) determines 2 priority of all polygons in a scene by comparing the z coordirate at the centroid of each polygon. Of the polygons which are potentially visible at a given pixel, the polygon with the highest priority is assumed visible. This method works well for surfaces comprised of many small polygons . Problems arise when polygons penetrate each other, arnd when cyclic overlaps of polygons occur. Cyclic overlap involves polygons that are both in front arnd behind of another polygon. An extended algorithm was developed to handle these problems (8) . Watldns developed a scan line method for polygon display. This is the most widely used of the three methods and is available in commer- cial software (9,10) . A general overview of the algorithm is presented below. Additional detail is presented in (.11) and (12) . 19 To aid in the diScussion of scan line techniques, it is convenient to define several associated terms. A scan line is a constant y line representing a row of pixels (see Figure 6 and 8). The screen is com- prised of many scanlines. The associated scan plane is defined by the viewpoint and the scan line. The scan plare cuts constant y sections through objects in the scene to determine what is potentially visible on the scan line, as shown in Figure 8. A sightline, passing through the viewpoint arnd the pixel, is defined for each pixel along the scan line. Intersections between he sightline and objects in the scene determine what is potentially visible at that pixel. The scan line algorithm developed by Watkins (11) efficiently determines polygon sightline intersections by orderly processing of the sightlines. This makes possible tre use of irnformatien about Sightline Intersection Curve Viewing (Screen Viewpoint Figure 8. Scan Plane and Intersection Curve 2O intersections fren the previous sightline when calculating intersec- tions for the present sightline. This orderly processing, or scanning of sightlines, is the basis of scan line methods. Scan line methods use two nested scans, the x scan arnd the y scan. The x scan, which is the inner loop, starts at the end of a scan line and steps along the scan line computing sightline polygon intersections for each sightline along the scan line. The y scan, starting at the tOp of the screen, steps through each scan line on the screen calling the x scan at each step. When ccnputing sightline polygon intersections , many calculations can be saved by knowing which polygons are intersected by the sight- line. It is in the determination of the intersected polygons that the scan line methods derive treir efficiency. This is done using a list of active polygons associated with each scan line, and a list of active line segnents associated with each sightline. The active polygon list contains all polygons intersected by a scan plane, therefore this list is updated for each scan line, or at each step of the y scan. The active polygon list is updated by using a list. of maximum and minimum y values of polygons in the scene. The list of maxima are ordered such that they are decreasing in magnitude. A pointer is used to indicate the maximum or minimum of the next poly- gon to be encountered and added on the list, for a maximum, or dropped off the list for a minimum. Thus, as the y scan progresses, the y value of the scan line, Escan, is compared to the next maximum or minimum. When Yscan is less than the current maxirmmn or minimum, the associated polygon is added or deleted from the active polygon list, and the pointer is advanced to the next maximum or minimum. At this 21 point the active polygon list is updated for the scan line at Yscan, and the x scan can be initiated. Once the active polygon list is established for a scan plane, the x scan for that scan line can begin. For each x scan, the intersection of tre scan plane with the active polygons create straight line seg- ments which are defined by their endpoints. An active line segment list contains the subset of these line segrents which are intersected by a given sightline. The active line segrent list is updated for each sightline using a list of line segment endpoints. The list is sorted starting with the endpoint with the smallest x coordinate. A pointer is used to indicate the next line segment endpoint to be encountered, or so-called current endpoint. When tre x value of the sightline, Xscan, is increnented for the next sightline, it is compared to the current endpoint. If Xscan is geater than the current endpoint , the active line segment list is updated. The z coordinates of the intersections between the sightline and the active line segments are compared to determine which polygon is visible. The normal vector associated with the visible polygon is then used to ccnpute the intensity of the pixel defining the sightline. Scan line methods applied to polygons have proven very time- effective in producing shaded images. But if these methods are to be applied to contoured surfaces, the surfaces must be approximated by polygons before shading begins . For applications where flat surface approximations are unacceptable , direct shading of contoured surfaces may be required. The next section will examine methods of directly shading parametric surfaces . 22 14.3.2 Display Methods for Parametric Surfaces Parametric surfaces were first displayed using polygon techniques . A curved parametric surface can be approximated by many small polygons as shown in Figure 7. The polygons may then be displayed usirng techni- ques discussed in the previous section. This method is effective for visualizing gross surface characteristics, but detailed slope and curvature information is lost in the image. To maintain exact slope and curvature information at each pixel, a direct method of shading parametric surfaces is required. Three methods of direct parametric surface display will be discussed here. In 197A , Catmull developed one of the first algorithms for the direct display of parametric curved surfaces (13) . This algorithm subdivides each patch until each subdivision covers only one pixel. The large number of subdivisions required can be time consuming. Catmull developed an efficient method to subdivide one specific surface type, the parametric bi—cubic patch. The subdivisions are made along flow lines. To test if the subdivided patches are the size of one pixel, an approximating polynomial is constructed using the four vertices of the patch. This method effectively randles patches with little curvature, but problems may be encountered with highly curved patches or patches with poor orientation. These problems arise from tlre fact that the polygon constructed may not totally contain the patch subdivision. Lane and Carpenter (12) modified this method into a scan line type method. As patches are subdivided, pieces which do not fall on ‘ the scan line are placed in an inactive patch list. Subdivision 23 continues until the patch is within a set tolerance of being a four-sided planar polygon. The active patches along the scan line may then be processed usirng the x scan from the polygon scanline method. Sweeping in this fashion is convenient for raster display. In 1978, Blinn developed a scan line method (11) for displaying curved parametric surfaces. The scan line algorithm used is similar to the one developed by Watkins (11) discussed earlier in this chapter, but the complexity of the algorithm is increased when polygons are replaced by curved parametric patches. The algorithm contains the y scan and x scan typical of scan line methods, with the addition of a patch preprocessor. The preprocessor finds and orders local y maxima/minima for each patch. Unlike polygons, for which maximum and minimum values occur at the corners , maxima and minima for contoured surfaces can occur m the boundary or on the interior of the patch. The local maxima and minima of contoured surfaces contain the corners and solutions to the following equations: 3%(s,t) = O (A.3.l) 3%(s,t) = 0 Obtaining the solutions of these nonlinear equations requires an itera- tive technique. Blinn uses Newton' s method for equations of this type. Curved parametric patches create additional carplications during the y scan. Intersections of the scan plane, defined by the scan line 2A and.viewpoint, with a parametric patch results in.a curve rather than the straight line which must result from polygons. We will refer to these curves as intersection curves. Another complication results from the fact that the scan plane may intersect the patch in.more than.one place, as shown in Figure 9. Therefore more tran one intersection curve may come from a single patch. The number of intersection curves on each patch can be determined as afimction of localminimaandmaxima. Whenamaximlmmorminimnmm of a patch is encountered during the y scan, the number of intersection curves associated with the patch is increased or decreased. This method is illustrated in Figure 9. Tina ith scan line ms zero inter- section curves associated with the patch. Moving from he ith scan line to the ith+l scan line a global maximum is encountered at the point A, therefore the number of intersection curves on the patch ith A / A ith-l-l __ ith-+2 ith+3 Figure 9. Number of Intersection Curves on a Patch 25 increases to one. Moving to the ith+2 scan line a second local maximum is encountered at point B increasing the number of intersection curves to two. The next scan line passes the local minimum at C, reducing the number of intersection curves to one. Another problem.associated with curved patches is the so—called silhouette edge. Silhouette edges are defined as curves on the surface where the 2 component of the normal vector is zero (see Figure 10). An intersection curve that intersects a silhouette edge is not single- valued in z. This problem may be handled by dividing the intersection curve at the silhouette edge into two intersection curves. Thus as the y scan progresses, the end of the silhouette edge implies a change in the number of intersection curves associated with the patch. This idea is illustrated in Figure 10. As the y scan moves from the ith scanline to the ith+1 scan line, the beginning end of a silhouette edge is encountered at A, therefore the number of intersection curves increase from one to two. To facilitate the x scan, the endpoints of each intersection curve must also be computed. Endpoints can occur at the patch bound- aries or at silhouette edges. If endpoints occur at patch boundaries, they may be found from one of these four equations. 1) y(0,s) Yscan 2) y(l,s) Yscan (A.3.2) 3) y(t,0) = Yscan A) y(t,l) = Yscan 26 A \, ith A back curve ith+l ~———front curve \ ‘ silhouette edge Figure 10. Effect of Silhouette Edge on the NUmber of Intersection Curves 27 Endpoints at silhouette edges are obtained by simultaneously solving: y(s,t) = Yscan (A.3.3) Nz(s,t) = 0 where N2 is the z component of the normal vector. These endpoints are then used during the x scan to update the active curve list. During the x scan, the visible intersection curve is determined by comparing the z coordinates of intersections between the sightline and the active intersection curves. Intersections of each sightline with the intersection curves are found by simultaneously solving: x(s,t) = Xscan (A.3.A) y(s,t) = Yscan Typically, equation A.3.A is solved using Newton's method, but Blirnn notes that singularities or cusps in the patch may occur, and that for these cases Newton' s iteration is not appropriate . Blinn also notes trat, although the technique is accurate and avoids polygon approximations, the x scan portion of tre algorithm is slow, and he developed an alternative algorithm. Along the visible intersection curve, Blinn computes sightline intersections only at so—called key visual points and uses linear interpolation to compute the normal vectors between then. This reduces the number of times equation A.3.A is solved, thus improving canputation time. A 28 description of key visual points and how the algorithm works can be found in Reference 1A. Another method of directly displaying curved surfaces was deve10ped in 1980 by Whitted (15). This algorithm, which was deve10ped specifically for the bi-cubic surface, is a scan line algorithm similar to Blinn's, with modifications to handle silhouette edges. Silhouette edges, which are usually of a higher order than cubics, are approximated by one or more cubics. A patch containirng a silhouette edge is then divided along the silhouette edge into two patches having boundaries which are cubics in one variable. The preprocessed patches, whose edges are cubics in one variable, are displayed using a scan line technique similar to Blinn' s algorithm without having to compute sil- houette edges at every scan line. Each of the surface shading algorithms discussed has its advan- tages, eitrer in accuracy or speed. But the demands of the designer required both speed and accuracy. The next chapter presents an algori- thm developed to apply color graphics to surface crecking and explains tre steps taken to retain both speed arnd accurary. CHAPIER V A Surface Shading Algorithm for Design 5 . 0 Introduction Since surface checking as defined here has the purpose of finding subtle flaws in the data base, it is clear that approximations to the surface must be scrutinized carefully. If the surface approximation washes out the sought-after flaws, all hope for successful surface checking is lost. 0n the other hand, exact methods lead to an in— creased computirng burden, perhaps rendering the creek process so time consuming as to rule out the kind of interactivity so desirable to the designer. To attain the desired accuracy, the algorithm developed in this thesis builds on ideas developed by Blimn (1A) . This type of algorithm is referred to as an exact algorithm because tre normal vectors are corputed at each pixel. The algorithm is basically a scan line method with several modifications to help fulfill tl'e dual needs of the design environment, namely, rapid calculation and accuracy. The three major conponents of this algorithm, the patch preprocessor, the y scan, arnd the x scan, are presented in the following sections. 5 . l The Patch Preprocessor A maj or difference between the algorithm deve10ped rere and the algorithm developed by Blirnn is that many of the calculations done by Blinn during the y scan are replaced by careful patch preprocessirng. 29 30 The first calculation done by the patch preprocessor is finding global maxima and minima in x, y, and z for each patch. Conservative approximations are used, meaning that the patch is always contained by the approximate extrera. The algorithm developed to approximate these extrema is much faster than solving for the exact extrera, arnd errors are small for most patches. Appendix A presents a detailed description of this algorithm. The x and y extrema are used to determine which patches are on the screen. These patches are then placed in an active patch list, allevi- ating any search involving patches not on the viewing screen. As an example, consider an instance when small areas of an object are magni- fied arnd displayed, leaving the majority of tie patches outside of the viewing screen. The preprocessing saves work with patches that are not on the screen. From this point on, calculations discussed are for active patches only. The z extrema for these patcres are stored to be used later during the x scan. The secornd calculation done during patch preprocessing is the calculation of all scan plane intersections with patch edges, includirng both patch boundaries and. silhouette edges. These intersection points are the endpoints of intersection curves. The algorithm developed to compute these endpoints uses Newton' 8 method to solve equations A.3.2 and A.3.3 presented by Blirnn. But unlike Blinn's algorithm which con- putes all the endpoints on one scanline, this algorithm computes all of the intersection curve endpoints for each patch. Appendix B presents a detailed discussion of this algorithm. The endpoints conputed for a typical patch are illustrated in Figure 11. 31 Figure 11. Typical Intersection Curve Endpoints 32 After all endpoints are corputed for each patch, endpoints of the same intersection curve are paired. Pairing methods are also discussed in Appendix B. As the patches are processed, endpoint pairs are sorted by their y values and placed in vectors associated with each scan line. After all active patches are processed, the endpoints are then ordered in x in preparation for the x scan. At this point, any effects of the approximation used to calculate global patch maxima and mninima have been corrected. No "search" beyond exact patch boundaries has been done. A disadvantage of this method is the large amount of memory re- quired to store the endpoints of the entire screen, as opposed to Blinn's method which requires memory for only one scan line at a time. But corputing intersection curve endpoints a patch as a time eliminates the need for the exact local minima and maxima which are required by Blinn to compute intersection curve endpoints a scan line at a time, a calculation similar to cutting constant y sections for each y value in turn. Another advantage of storing all endpoints arises from the desire of the designer to "assemble" an object on the screen. Display- ing objects a piece at a time may enable the designer to detect how well pieces are mating and possible interference. In such applications, patches already displayed need not be processed again by the prepro- cessor, and the scans need only cover areas where rew patches have been added. Also, single patches may be corrected or altered and the entire scene can be displayed by only preprocessing the altered patch, deleting the original patch, and scanning in the neighborhood of the altered patch. In both of these instances there are large computational savings . 33 Since memory cost has been rapidly decreasing to current rather nominal levels, the time saving from this technique more than offsets the large memory requirements. In the case of a corputer with virtual memory, there is, in fact, no trade-off at all since paging delays for memory access are very much smaller than the time saved by this prepro- cessing. The next section will discuss the y scan. Subsequent sections give a detailed explanation of the x scan. 5.2 The Y Scan Recall that the patch preprocessor has corputed the endpoints of intersection curves for the entire scene. The endpoints are stored in vectors representing each scan line. The endpoints in each vector are stored in order of increasing x. The y scan steps through all scan lines on the screen. At each scan line, the y scan calls the x scan and supplies the associated endpoints. The x scan computes the visible intersection curve and the point where the sightline intersects it for each pixel on tre scan line. The y scan then moves on to the next scan line until all scan lines are displayed. 5. 3 The X Scan The x scan must determine, for each sightline along the scan line, which intersection curve is visible at the pixel. This problem is usually called the hidden line problem. After the visible curve has been identified, the intersection point between the sightline and the visible curve is corputed. Because the intersection curves are not 3A linear, an iterative method such as Newton's method is required to solve for the intersection point. Solving nonlinear equations in the context of this task will be examined in a later section. The next section will discuss the hidden line problem. 5.A The Hidden Line Problem The hidden line problem refers to the identification of visible intersection curves or portions of intersection curves. This is done at each pixel as the x scan sweeps across a scan line. The first step in determirning which curve is visible is to find all intersection curves intersected by the sightline. (For the re- mainder of this chapter, the word curve will refer to an intersection curve.) This is acconplisl‘ed using an active curve list which contains curves intersected by the sightline. The active curve list is updated for each pixel as the x scan moves across tl'e scan line. The npdating is done using a pointer and the ordered list of curve endpoints supplied for each scan line by he y scan and the patch preprocessor. [The pointer is used to indicate the next endpoint to be encountered durirng the x scan. This endpoint will be called the current endpoint. As the x scan progresses, the x value of the pixel, Xscan, is compared with the x value of the current endpoint. If Xscan is greater than the x value of the endpoint, a curve is added or deleted from the active curve list , depending on whether the expoint encountered is a leadirng or trailing endpoint of the curve. The pointer is then advanced to the next endpoint in the list, which is again corpared to Xscan, and the process continues. 35 An example is presented in Figure 12. The example contains two. patches A and B. Patch B contains one silhouette edge. The scan line has three associated intersection curves, 5, b, and 3. Curve 5 lies in patch A, arnd curves 5 and 'c' lie in patch B. The ordered list contain- ing the x values of the curve endpoints is given beside the figure, and lines joining endpoints indicate a pair of endpoints on tre same curve. The first endpoint of a pair appearing in the list is the leading endpoint of the curve and the second endpoint is the trailing endpoint. The x scan starts at the left end of the scan line. At this point no patches are intersected by the sightline. Therefore there are no active curves when the x scan begins. The pointer starts at the top of the endpoint list, pointing at X1. As the x scan progresses arnd the value of Xscan is incremented, it is corpared to the endpoint pointed at by the pointer, or the so-called current endpoint. Note that XL is a leading endpoint, therefore when Xscan becores geater than Xl, curve 'a' is intersected by the sightline, and therefore is placed in the active curve list. The pointer is then advanced to the rext endpoint, X2, and Xscan is corpared to X2. Because Xscan is less than X2, no additional changes are made to the active curve list. The x scan continues until Xscan becomes greater than X2, at which point curve ‘6 is added to the active curve list. The pointer is advanced to X3, but X3 is still greater than Xscan, so no additional changes are made to the active curve list, which now contains curves 5 and ‘6. Because X3 is a trailing endpoint, when Xscan becores larger than X3, curve 5 is removed from the active curve list. The pointer is then advanced to XA, which is also less than Xscan, and therefore curve '6' is added to 36 Patch B \V 00 M 0‘ math I 7 1 I Patch A Figure 12. Illustration of Active Curve Updating 37 the active curve list. The pointer then advances to X5, which is greater than Xscan, and therefore, at this point the active curve list contains B'and.EI As the x scan.continues, it then passes endpoint values X5 and X6, both trailing, leaving the active curve list empty. After determining all curves intersected by a given sightline, it must be determined which curve is first intersected by the sightline, or, in other words, which curve is visible at the sightline. The algorithm which determines the visible curve uses two steps. The first is a global depth conparison of patches from which the active curves originate. This step may determnine if sore curves cannot be visible. The second step determines which of the renainirng curves is visible. The global depth comparion of'patches will first be discussed. Recall that global z extrema were computed for each.patch.during patch.preprocessing. The 2 limits of patches containing active curves are compared to determine if any are gldbally behind others. This is typical for most objects being modelled, for example, solid Objects generally have two disjoint sides. Active curves lying on patches gldbally behind others must be behind curves lying on the other patches. Such curves are immediately eliminated when determining the visible curve. NOte that the global patch check is required only when there is a change in the active curve list. From this point, determnination of which active curve is visible is broken into two classifications, depending on whether or not patches intersect each other on their interiors. For example, Figure 13 illustrates two patches which intersect on their interiors. The more general case, where intersecting patches:may be present, requires a depth check at each pixel. The z coordinate of 38 Line of Intersection Figure 13. Interior Intersection of Two Patches intersections between the sightline and the active curves are conputed to determine which curve is visible at the pixel. Corputing the 2 value of the intersection point requires solving the nonlinear equations A.3.A for parametric values 3 and t, given x and y of the pixel. (This solution is discussed in detail in the next section). The values of s and t are then used to corpute 2. Doing this calculation for all active curves is compute intensive, thus savings from the global 2 check, which reduces the number of active curves, is evident. The more restrictive case, where patches are assumed not to inter- sect each other, requires a depth check only when the active curve list is changed. This is due to the fact that once a curve is determined to be in front of another, it retains in front. In fact, when a new curve is added to the active curve list it need only be compared to the 39 current visible curve to determine which curve is visible, and only when the visible curve is deleted from the active curve list is the depth corparison required. It is also possible to convert cases with intersecting patches into those without . This is done by dividing the intersected patch into two patches by computing the intersection of the two patches, and dividing the associated intersection curves into two curves. This idea is illustrated in Figure 1A. In this case, two intersection curves are divided into four curves which only intersect at their ends, thus the faster algorithm can be used to display these patches. Clearly, if it can be assumed that patches do not rave interior intersections, calculations are significantly reduced. Of course, such assumption precludes the detection of unwanted interference. The next section will discuss solution methods for finding intersections of a sightline and an intersection curve. 5. 5 Solutions of Nonlinear Equations Up to this point, the algorithm has determined which curve is visible for a given sightline. The curve is identified by which patch it is in and its endpoints. The next step is to conpute normal vectors for the associated pixels along the visible curve. The s and t values of each siglntline intersection point are needed to conpute the normal vectors . Therefore, an iterative technique is required to solve equa- tion A.3.A for s and t. Blinn suggested bivariate Newton's method (16,17) for solving the equations. Newton's method requires the s and t values of a starting point for the iteration. Faster convergence is achieved when no \\ b 21 ‘\ 3 I" ‘\ ‘\ \ ' l 3 L} l 5 [2 3 b )4 5 \3au35:6 U 5 .\ - 7] a 2 \ c 7 8 8 a \ a \.. Newly Formed Intersection Curves Figure IA. Division of Intersection Curves for Interior Intersections Al the starting point is near the solution. Good initial starting points are available from the x scan. Interior to a visible curve, the s arnd t values from the previous pixel are used as a starting point for the present pixel. When the visible curve changes, a starting point is required on the new curve. In this case, the s and t values of the endpoint of the new visible curve closest to the x value of the sight- line is used as the starting point. It is also important to note a singularity that may prevent con- vergence of Newton' 3 method. Consider a situation. wherein s arnd t for a pixel on a visible curve are known, and the ds arnd dt to arrive at the next pixel are sought. The following equation is solved for ds arnd dt .. .. .. .. -..1 3x 3x F d8 “5's- 51E OX a (5.5.1) El 31 f“. ..as M .dyl where dx is the known x distance to the next pixel arnd dy is the known y distance to the next pixel. Solutions exist only when the matrix of partial derivatives is nonsingular, i.e. , when the determinant is non-zero. The determinant of this particular matrix is proportional to the 2 component of the normal vector at the point. T‘terefore, Newton's iteration will fail on areas of the patch where the z conponent of the normal vector is near zero. This corresponds to normal vectors lyirng in the plane of the screen, i.e. , to silhouette edges. Therefore, Newton's method must be modified in these areas. A2 In the neighborhood of a silhouette edge, an absolute maximum on As and At is imposed so tl'at the iteration stays in the region of the patch where it started. Convergence can be obtained for most pixels near silhouette edges by heavily damping Newton' 8 method, but still retaining the As/At ratio. As the number of iterations increases, the step size is increasingly reduced. In the event that the iteration does not converge after a limited number of iterations, the pixel is assigned the same normal vector as the neighboring pixel. Another class of methods, the generalized secant methods, can be used to solve this type of nonlinear equations. The advantage of these methods is that the partial derivatives used in equation 5.5.1 of Newton's method are not used after the first step of the iteration. Obtaining these derivatives requires numerous calculations . Although the convergence rate for secant methods is slower than Newton' s method, extra iterations using secant methods are offset by the savings incurred from not having to corpute partial derivatives at every iteration step. One particular generalized secant method, Broyden' s method (16) , which is used in this thesis, is discussed in detail in Appendix C. 5 . 6 Approximate Methods A method was developed for approximating the normal vectors along a visible curve between its endpoints similar to the method of key visual points developed by Blirnn. At key visual points, Blinn conputes the exact normal vector. For points on the visible curve between key visual points, be linearly interpolates between the normals at the key visual points . One method used by Blinn to determine the location of key visual points is to compute a key visual point every time the normal “3 vector rotates a given number of degrees in the scarplane. This procedure was apparently derived to avoid the burden of calculating the s and t values to go with each pixel. The approximating algorithm developed in this thesis also conputes exact normals only in a few prescribed planes along the visible curve. But instead of linearly interpolating, a third order interpolation, or so-called blend, is used between the points. (This method preserves the lepe at the endpoints of the curve, which is necessary if slope discontinuities between patches are to be visible.) The following equation is used to blend the normal vector: = ‘N * ‘N ‘I’ N N0 Fl(x) + N1 F2(x) + Nxo F3(x) + le rue) (5.6.1) where NO is the normal vector at the leading endpoint of the curve and N1 0arrilearetl'e partial derivatives of the normal vector with respect to x at the is the normal at the trailing endpoint. Also Nx leading and trailing endpoints, and Fl(x) through Fu(x) are third order blendirng functions (5) . These blending functions guarantee that the normal and the derivative of the normal with respect to x is maintained at the ends. Since the normal vector is a conplicated function of s arnd t, conputing the derivative with respect to x is not straightforward. Appendix D presents the derivation for Nx . It is usually sufficient to blend between the endpoints of the visible curve, thus no interior points need be corputed. But for sharply curved patches it may be necessary to break the curve into shorter segments. It is also important to note that Nx is undefined AA along silhouette edges. For this case, the blend is started a slight distance’in from the silhouette edge, arnd points near the silhouette edge are corputed exactly. This approximating technique has been shown to be much more accurate than linear interpolation, with only a slight increase in corputation time. When corpared to exact techniques, a large time savings is realized. 5. 7 31111111311)! A tradeoff of time versus accuracy is evident for all of the methods discussed. The most accurate technique, the exact method, requires calculation times which may be prohibitive for extensive use in an interactive environment. However, it is possible, through a combination of exact and approximate methods developed in this thesis, to create a practical design tool. The next section will present results. Accuracy and calculation time will be corpared for several algorithms. The effectiveness of each technique for detecting surface flaws will also be discussed. Finally, a possible surface checking scheme will be outlined. CHAPTER VI Algorithm Evaluation 6 . 0 Introduction In the following section, comparisons are made between the exact and the approximate methods presented in this thesis. First the ability of the algorithm to detect surface flaws is examined. The calculation time is then compared for each algorithm. Finally, a large data base with many patches is used to illustrate the overall effec-' tiveness of the modified y scan developed in this thesis. 6.1 Error Detection An evaluation of the algorithm' 8 ability to detect surface flaws makes use of the bump presented in Chapter 2. The bump with no slope discontinuities is shown in Figure 1. Figures ’4 and 5 show the bump after a slope discontirmity was introduced. ' The following examples compute the intensity for each pixel based on the absolute value of the dot product of the normal vector and the light vector. Taking the absolute value implies the light vector is in both directions, therefore all surfaces are illuminated. Although this is not realistic , it is effective when looking for surface irregularities . The exact algorithm is used to shade the bump with and without the slope discontinuity. Figure 15 presents the bump without the lepe 145 A6 Figure 15. Shaded Bump discontinuity. The color discontinuity in Figure 16 clearly indicates the slope discontinuity along the patch boundary. This could easily be detected by a designer who could then correct the error. The approximate method can also be used to identify the slope discontinuity. The image of the bump computed by the approximate method is shown in Figure 17. Again, a color discontinuity is apparent along the patch boundary containing the slope discontinuity. It should be noted that since the interpolation scheme is accurate at patch boundaries, flaws on the interior of the patch may not be as accurately represented by the approximate method as those near the patch boundary. It is of interest to note that not all views of the bump, or all light sources will highlight the slope discontinuity. For example, Figure 18 presents the same view of the bump as displayed in Figure 16, N7 Figure 16. Shaded Bump with Slope Discontinuity Figure 17. Shaded Bump with Slope Discontinuity, Approximate Method 148 Figure 18. Shaded Bump with Slope Discontinuity, Different Light Source but the light source has been moved. The slope discontinuity is not apparent in Figure 18. This is due to the fact that the change in the normal vector across the discontinuity is in the plane normal to the light vector. Thus the angle between the light vector and the normal does not change, and no color discontinuity is generated. Therefore, when checking a given view of a surface, it is necessary to observe images produced from several different light sources. The next section will discuss an efficient method of recomputing the image for each light source. 6.2 Image Generation for a New Light Source Computing an image for a new light source without changing the viewpoint is a straightforward calculation. Surface normal vectors “9 corputed for a given view remain the same for any light source. Therefore, moving the light source requires only the computing of the pixel intensity using the known normal vector and new light vector. This is a simple calculation, orders of magnitude less burdensore than corputing the normal vectors themselves. In this thesis, pixel intensity is computed by taking the dot product of the normal vector and the light vector. Therefore, moving the light source requires calculation of one dot product for each pixel. Such a calculation is potentially simple enough to be inter- active. It is concievable that with the help of an array processor, the light source could be hard wired to a Joy stick, and new light source locations could be viewed almost continuously. In contrast, changing the vievpoint necessitates recalculation of the normal vectors, with attendant silhouette and hidden surface problems. The next section will benchmark several of the images presented above . 6.3 Compute Times Calculation times for the bump are indicated in Table 1. Note trat two different numerical techniques are listed for the exact method . These indicate that Broyden' s method results in a significant time savings compared to Newton's method. As expected, the table also indicates that the approximate method requires less time than either of the exact methods. Finally, the time required to corpute Figure 18 using normal vectors corputed for Figure l6, which amounts to moving the light source, is listed to illustrate the simplicity of this procedure . 5O TABLEl Compute Times Exact method (Newton's) 112 sec Exact method (Broyden’s) 37 sec Approximate method 19 sec Light source charge 5 see All routines used in these corparisons are in Fortran and are being run ona Prime 750. 6.1-I Object Assembly The following example is used to demonstrate how objects can be assembled on the screen without reshading the entire scene. Data representing an aircraft wing are used for the example. A flow line representation of the wing is shown in Figure 19. The following is a possible scenario for a desiger checking the wing. Assume portions of the wing were designed by two different designers. Thus, the designer may first choose to inspect the lower half of the wing. The resulting image is shown in Figure 20. At this point many different light sources would be used to inspect the 51 Figure 19. Aircraft Wing Figure 20. Shaded Aircraft Wing, Lower 52 surface. Upon completion of this check, the desiger may want to add a portion of the wing as shown in Figure 21. Again, many different light sources are used to inspect the newly added portion and to check how it fits with the lower half. At this point he may choose to corplete the assembly as shown in Figure 22 and continue the checking. Later, while checking the fuselage, the wing could be added to insure a proper fit. The total aircraft is shown in Figure 23. 6.5 Surface Checking Scheme A possible surface checking scheme could entail the following steps. A designer may start the surface check by displaying the surface using flow lines. This would be used to check for missing data or gross errors in the database. During this procedure, the Figure 21. Sladed Aircraft Wing, Lower plus Half of Upper 53 Figure 22. Shaded Aircraft Wing, Entire Surface Figure 23. Shaded Aircraft 514 designer would note which.views clearly display areas of interest. At this point he may choose to examine a view more carefully. This view would then be shaded using either the approximate method or the exact method. Mom a time standpoint, it is advantageous to use the approxi— mate:method.whenever possible, but which algorithm.should be used ‘would depend'on several other consideratidns. For example, the type of surface flaws which are to be identified would affect the choice of the algorithm. If the slopes along patch boundaries are being checked, the approximate:method.would be very effective. On the other hand, if flaws involving curvature inflections on patch interiors are suspected, the exact method would better identify these errors. The designer may also have prior lcnowledge of possible problem areas on the surface, or’may have located possible problem areas using the approximate method. In this case, these problem areas could be 'magnified and viewed using the exact method. Regardless of which algorithm is used, each view is then inspected using many different light sources. A.comhination of these procedures and the assembly procedure would be used repeatedly until the designer is satisfied that the surface is correct. 55 CHAPIERVII Conclusions Surface display methods developed prior to this work were primarily aimed at producing aesthetically pleasing images. The goals of this thesis, to develop a display algorithm to be used for surface checking, required a different approach to tl'e problem. The algorithm deve10ped in this thesis ras proven to be effective at locating surface flaws, and has been shown to be time effective from a designer's standpoint, facilitating a much more efficient check procedure than using various views from line drawings. Future work should include speedup of the exact method through the use of better hardware. For example, many of the shading calculations can be done in parallel, lending themselves to array processing. Also, improvements in the accuracy of tl'e approximate method may be possible through the use of higher order interpolation scheres. Other shading techniques could also be investigated, such as shading by curvature, which could highlight different types of surface flaws. APPENDICES APPENDIX A Calculation of Approximate Patch Extrema Patch extrema are approximated by expanding the matrix expressions for the spatial coordinates, arnd summing maxima of terms. T're expres- sions for the z extrera will be derived in the following discussion. Identical expressions exist for x and y. Figure Al illustrates a typical patch. Parametric variables s and t run from zero to one. The patch boundaries, which are curves of one parametric variable, are numbered from one to four as shown in the figure. For example, L1(s) is the boundary curve at t = 0. The following discussion specifically deals with Coons surface definitions, but similar techniques can.be applied to other parametric surface definitions. The matrix equation for 2 as a function of s arnd t on the surface is: z = (F (Sm (Sm (Sm—r Fz z 93:00 3—201 - r (t; l 2 3 A 00 01 at at 1 82 32 3500 9301 —o"‘2Z o —-o322 1 F (t) (A l) as as asat asat 3 ° 2 2 32 82 a z a z 9:10 all ratio rate my where Fl through F“ are cubic blending functions, and data subscript appearing in the matrix related to the patch corners, i.e. , Z01 is the 56 57 Figure Al. Definition of Patch Boundaries 58 2 value at the corner s=O, t=l. Partially expanding equation A.l yields: L1(S)Fl(t) + L2 +-g-,§00*F3(t)Fl(s) + a201*‘fi‘u('c)1'+‘l(s) (A.2) 82 32 + filmF3(t)F2(S) + ‘a'fll*Fu(t)F2(s) where Ll(s) and L2(s) give the z coordinates on the boundaries 1 arnd 2 respectively. If Gl(t) and G2(t) are defired as the following: —-00*F G (t) = g (t) + g—zorruo) (A.3) 1: 3 a a 92m - 3%1w3m + 5%11‘Fu“) Then equation A.2 becomes: Ll(S)Fl(t) + L2(S)F2(t) (A.A) + Gl(t)Fl(s) + G2(t)F2(s) The first two terms are associated with t blending of the s varying boundaries, while the last two terms represent 8 blending of additional surface contours due to partial derivatives with respect to t (see Figure Al). Using the fact that max(a+b) s max(a) + max(b), equation A. 5 becores: 59 max(Z) <_max(L1(S)Fl(t) + L2(S)F2(t)) (A5) + max(Gl(t)Fl(s) .... G2) Also note that since Fl + F2 1 the max(aF:L + bF2) = max (a, b), i.e., the larger of the two values a and b. Therefore the approximate maximum of 2 can be written as: max(Z) imax(Ll(S), L2(S)) + max(Gl(t), G2(t)) (A.6) Equation A.6 is easily solved. The expressions L1, L2, G and 1, G2 are cubics of one variable, therefore locations of local extrema can easily be found by differentiation and solving of the resultant quadratics. Local extrera located between 0 and l are then corpared to end values to obtain global extrema over the range of 0 to l. A similar derivation can be done to determine a lower bound for the minimumz. APPENDIX B Calculation and Pairing of Intersection Curve Endpoints B.O Calculation of Intersection Curve Endpoints All intersection curve endpoints of a patch are conputed at one time. Endpoints can occur on patch boundaries or on silhouette edges. Calculation of endpoints on patch boundaries will be discussed first. 8.0.1 Patch Boundaries Patch boundaries are functions of one parametric variable . End— points are corputed using Newton' s method to solve the following equation: Y(s) = Yscan (8.1) i where Y(s) is the expression for the y value of the patch boundary, and Yscan 1 lines may cross a patch boundary, therefore this calculation must be is the y value of the ith scan line. Any number of scan performed for all intersections. There may also be more than one intersection of a patch boundary with a given scan line. Both of these difficulties are handled using the following algorithm. The algorithm starts at the end of the patch boundary representing the lower limit of the parametric value. For this discussion the 60 61 parametric value will be s and therefore the search starts at s=0. Both y and dy/ds are conputed at the starting point. The value of Yscan is then increrented in the direction of dy/ds, starting next to the y value of the starting point, until the upper limit of the para- metric value is encountered. Each solution of equation B.1 uses the solution of the previous Yscan as a first guess for Newton' 5 method. If anytime during the Newton iteration the sign of dy/ds changes, the iteration is stopped and Yscan is incremented in the new direction, and Newton's iteration is continued. These ideas can be illustrated in the example presented in Figure B1. Due to the positive derivative at s = O, the first Yscan value greater than YO, Yscani, is used in equation B.1 to solve for endpoint l. The derivative at point 1 is also positive, therefore Yscan is increnented to Yscani +1 to compute endpoint 2. Yscan is again incre- mented to Yscan1+2, but the first step of Newton iteration moves 8 past Smax and a derivative sign change is detected. Therefore Yscan is decrerented to Yscan1 +1, and Newton's method is resumed, using as a starting point the last s value corputed during the aborted iteration. Because s was already incremented past s max’ Newton' s iteration converges to endpoint 3. This process is continued until s I l is encountered. This operation is performed for all four sides of the patch. B.0.2 Silhouette Edges The algorithm used to corpute intersection curve endpoints along a silhouette edge is based upon two assumptions: 1) all silhouette edges come in contact with a patch boundary in at least one point, and 63 / \ Figure Bl. Calculation of Boundary Endpoints 6A 2) each silhouette edge has no:more than one sign change in dy/dx, or so-called inflection point, along the silhouette edge. Figure B2 illustrates both of these conditions. The algorithm first locates intersections between silhouette edges and patch boundaries. A silhouette edge is defined as the locus of points on a patch whose 2 component of the-normal vector is zero. Therefore points on the boundaries whose 2 component of the normal vector is zero can.be thought of as silhouette edge starting points. The 2 component of the normal vector on a patch boundary can be expressen in terms of one parametric value, therefore zeros can be found using one—dimensional Newton's method. These points are stored for the next step of the algorithm. Using a silhouette edge starting point, the algorithm increrents Yscan and computes the intersection points. USing partial derivatives at the starting point, the direction to increrent Yscan is determined. For example, on a constant t edge, t=0, if dy/dt is positive, Yscan would be incremented in a positive direction. The initial Yscan is determined by the y value of tie starting point and the increment direction. Intersection points are fOund using bi-variate Newton's method to solve the following sinmiltaneous equations: Nz(s,t) = O (13.2) Y(s,t) = Yscani where N2 is the 2 component of the normal vector. Good initial values for Newton' s iteration are supplied by tre solution at the previous Yscan. 65 Inflection Point on {Silhouette Edge Silhouette Edge / Starting Point Figure B2. Critical Points on a Silhouette Edge 66 Yscan is increrented until one of two termination criteria is met: 1) Newton's iteration does not converge. This condition occurs when a silhouette edge has ended, or an inflection point has been passed. ' Endpoints that exist past the inflection point are corputed when the opposite silhouette edge starting point is used. This idea is illus- trated in Figure B3. Starting at point A, endpoints l and 2 are computed and termination occurs when Newton' 8 iteration does not con- verge for Yscan“? Similiarly, endpoints 3 and A are computed wren starting from point B. 2) A limit on s or t is exceeded, meaning the silhouette edge reaches a patch bourndary. When this criterion is met, the starting point associated with the termination point is removed from the starting point list to avoid duplicate calculations. B.1 Pairing of Intersection Curve Endpoints After all intersection curve endpoints are corputed for a patch, endpoints of the same intersection curve are paired. Endpoints are sorted by scan line and pairing is done for each scan line. Tre logic used to pair the endpoints depends on tre mmmber and type of endpoints for the given scan line, i.e. , whetlrer the scan line originates from a patch boundary, or from a silhouette edge. The majority of pairing results from several simple cases discussed below. Two common cases, two or four boundary endpoints, are illustrated in Figure BA. In these cases the pairing is straightforward. Another common case, two boundary endpoints and one silhouette endpoint , is presented in Figure B5. Note that the silhouette endpoint actually plays the role of two endpoints. Pairing is again straightforward. Figure B3. 67 Method of Calculating Silhouette Endpoints 68 \ \u / \ Figure BA. Simple Pairing Cases 69 Yscan1 Pairing 1-2 1-3 Figure B5 . Pairirng with One Silhouette Endpoint 70 When only one boundary endpoint exists on a scanline, it is assumed to be at a patch maximum or minimum, as shown in Figure B6, and the endpoint is deleted. Because these cases make up the majority of pairing, the time required for pairing is small. More corplicated cases are paired by determining if each endpoint is a leading or trailing endpoint. The algorithm which defines the leading or trailing status uses the idea that once tre status of the patch boundary is defined, it retains that status until: 1) a sil- houette edge starting point is passed, or 2) a change in the sign of dy/ds occurs along the boundary. These ideas are illustrated in Figure B7. At s=0, the boundary is a leading edge, but after the first critical point, i.e. , the silhouette edge is passed, the patch bound- ary becores a trailing edge. Note that the silhouette edge takes on the status the patch boundary had before it crossed the silhouette edge, thus the silhouette edge in Figure B7 is leading. When the second critical point, i.e. , the sign change in dy/ds, is passed the patch boundary becores a leadirng edge. Therefore the status of endpoints is defined leading or trailing and they are stored as they are being computed. The algorithm starts by conputing tre status of the four patch boundaries at their begin- nings. Next the silhouette edge starting points are corputed. As endpoints of the patch boundary are corputed, their status remains the same as the beginning until an 1) inflection point is passed, which corresponds to a change in the Yscan increment direction, or 2) a silhouette edge starting point is passed. In the second case, the silhouette edge starting point is assigned the same status as the 71 End point 1 Deleted Figure B6 . Single Boundary End point 72 Patch Boundary Leading \ 5‘0 fl Yscani +1 Silhouette Edge Starting Point Yscani Patch Boundary Trailing/ atch Boundary M leading Silhouette Edge Leading Inflection / Figure B7. Determination of Leading or Trailing Status 73 boundary it started from. Silhouette edge endpoints then have the same status as their starting points. Pairing endpoints is done by pairing leading endpoints in the order they occur from left to right with the closest trailing end- points, until all endpoints are used. As endpoints are used they are deleted from the list so they will not be paired twice. Silhouette endpoints are paired twice. Figure B8 illustrates this process. Unpaired endpoints are displayed in the figure after each pairing. Beginning Endpoint List; L—leading, T-trailing 1L, 2L, 2L, 3T, 31', AT First Pairing lip-3T 2L, 2L, 31‘, AT Second Pairing 2L-3T' 2L, AT Third Pairing 2L,-AT Figure B8. Pairing Example APPENDIX C The Generalized Secant Method for Solving Nonlinear Equations Newton's method, which is a popular technique for solving non- linear equations, is addressed in detail in (16) and (17). In general, for the one—dimensional case, a solution t s , is sought for the nonlinear equation: x(t) = o (0.1) Given a starting value t t is increrented each iteration according to O 3 the equation: axon) -1 } * X(tn) (0.2) 1: =1: n+1 n '{ (it An example of Newton's method is graphically illustrated in Figure Cl. The iterations are continued until x(tn) is less than some prescribed error, and then tn is assumed to be a solution. The secant method, which is similar to Newton's method, uses one iteration of Newton' 8 method to start the sequence, arnd then increments t using the following equation: - tn-l t __ n 1:n+1 - tn -[7((tn) - X(t 17] * X(tn) (0'3) 75 76 f(t) f (0.8) converges to a solution vector ts . By definition of the secant direction, Bn must also solve the equation: BnA = xn (0.9) where Atn = tn - tn-l and AXr1 = x(tn) - x(tn—l)‘ There are new an which solve equation 0.9, but the assumption is made that Bn is close to the previous én- and the difference between them is 6n- 1’ 1‘ Bn=B +C M n-l (0.10) Generalized secant methods are classified by the rank of the updating matrix, On. The discussion that follows deals with rank 1 79 updating methods, in particular Broyden's method (17) . The derivation is as follows. Substituting equation 0.10 into equation 0.9 yields: (En-l + 0n_l) AEn = A791 (0.11) _ J _. Choosing a vector W, such that WAt n is not equal to zero, multiplying both sides of equation C.ll by W, and rearranging yields: 6M = < 1_) * (Al-(n - én-lAE-n) * WT (0.12) W Atn A common choice for W is: W = A? ((3.13) This choice of W minimizes tre change in Bn. Another choice for W, which minimizes the change in Bgl, is: _. ”T ._ W.Bn-1Axn (C.lA) The effect of W on the convergence rate depends on the application. It is useful to conpare Newton's method and Broyden's method in the context of the x scan. The nonlinear system of equations being solved at each pixel is: x(s,t) = Xscani (0.15) Y(s,t) = Yscan,L 80 The starting point used for each iteration is the solution at the previous pixel. The first step of Newton's method, which is required by both solution methods, is readily available from the known partial derivatives corputed when finding the normal vector at the previous pixel. Therefore, comparisons of the two methods will begin after the first step. The majority of the calculations required for solving equation 0.15 using Newton's method arise from solving for x, y, and the J acobian matrix at each step of the iteration. The J acobian matrix consists of the four partial derivatives, dx/ds, dy/ds, dx/dt, and dy/dt. Computing each of these six values requires multiplication of three matrices, a le containing blending functions in s, times a AxA containing patch data, times a Axl containing blending functions in t. This product can be thought of as five vector dot products of length four, but the calculation of x arnd y has common intermediate products with two of the partial derivatives, therefore after corputing x and y, only two addition dot products are required to obtain two partial derivatives . The retaining two partial derivatives cost five dot pro- ducts each, therefore the approximate cost of Newton' 3 method for one step is 22 dot products. On the other hand, Broyden's method only requires calculation of x and y at each iteration, along with calcula— tions for the matrix updating approximately equal to two of the dot products discussed earlier. Thus the approximate cost for one step of Broyden' s method is 12 dot products. A direct corparison of the two methods for a given problem then depends on the average number of iterations required for each solution . Several test cases rave indicated that for each pixel Newton' s method 81 uses an average of . 8 additional steps after the initial step, while Broyden' s method required an average of one additional step . This indicates an approximate savings of 30 percent for solving equation 0.15 during the x scan. APPENDIX D Calculation of 2% The normal vector is a function of the parametric values s and t, therefore derivatives with respect to s and t are easily obtaired. (see eq. 2.1.3) Computing derivatives of the normal vector with respect to x is not straightforward. The first step in corputing aN/ax is to corpute the derivative of the normal vector along the intersection curve cut by the scan plane. The intersection curve is a constant y curve, therefore the following equation is true along the curve: a .31 § 21 * = dy 38 ds 4- at dt 0 (D.l) This equation gives the ratio of ds to dt to move along the curve, as illustrated in Figure D1. The derivative of the normal along the curve can be found using the following equation: aN . a a AN. 22 5'6 as au at au 03'” where u is the arch length along the curve. But the u direction contairns corponents of x and 2 as shown in Fig- ure D2. From Figure D2, dx and du are related by the followirng expres- sion: 82 83 ds Intersection ! Curveu Figure D1. The Ratio ds/dt Along the Intersection Curve u 8A Intersection Curve u Figure D2. Relationship of the u and x Directions dx: where e: where (”'02 N N II and Thus, equation D.3 yields: du * cos(6) az arctan.(5§9 a a 811 Bu iii§+2£ii as an at an 3233 32 at +__ T5 au at an flag} 1 3X 311 COS! 65 85 (D.3) (v.14) (D.5) (D.6) (13.7) LIST OF REFERENCES 10. ll. 12. LIST OF REFERENCES Struik, D.J . , "Differential Geometry", Addison-Wesley, Cambridge, 1950. Weatherburn, C.E. , "Differential Georetry", University Press, Cam- bridge, 1927. Osserman, R. , "A Survey of Minimal Surfaces", Van Nostrand Reinhold, 1969. Forrest, A.R. , "Qn Coons and Other Methods for the Representation of Curved Surfaces", Corputer Graphics and Image Processing, 1972, Rogers, D.F. and Adams, J .A., "Mathematical Elements for Corputer Graphics", McGraw-Hill, 1976. Coviak, R.A., "Color Graphics in Engineering Design", Pasters Thesis, Dept. of Mechanical Engineering, Michigan State Urniversity, E. Lansing, ML, 1981. Warnock, J . E. , "A Hidden Surface Algorithm for Conputer Half-Tone Generated Pictures", Corputer Science Dept. , University of Utah, TRA-15, June 1969. Newell, M.E., Newell, R.G., and Sancha, T.L., "A Solution to the Hidden Surface", 1972. "Graphics Utah Style - 80", Manual, University of Utah, Salt Lake City, Utah, 1980. Sutherland, I.E., Sproull, R.F., and Schumacher, R.A., "A Charac- terization of Ten Hidden Surface Algorithms", Conputing Surveys, Vol. 6, No. 1, March 197A, pp. 1-55. Watkins , G.S. , "A Real-Time Visible Surface Algorithm", Corputer Science Dept., UI‘ECH-CSC—‘IO—lOl, June 1970. Lane, J.M., Carpenter, L.C., Whitted, T., and Blirnn, J.F., "Scan Line Methods for Displaying Parametrically Defined Surfaces", Communications of the A.C.M., Vol. 23, No. 1, Jan. 1980, pp. 23-3A. 86 13. 1A. 15. l6. 17. 87 Catmnull, E. , "A Subdivision Algorithm for Corputer Display of Curved Surfaces", UIEL—CSC-7A-l33, 197A. Blinn, J .F., "Corputer Display of Curved Snm'faces", Ph.D. Diss., Conputer Science Dept. , Urniversity of Utah, Salt Lake City, Utah, 1978. Whitted, T. , "An Improved Illumination Nbdel for Shaded Display", Communications of the A.C.M., Vol. 23, No. 6, June 1980, pp. 3A3- 3‘49- Ortega, J .M. and Rheirnbolt, W.C. , "Iterative Solutions of Non- linear Equations in Several Variables", Academic Press, London and New York, 1971. Conte, S.D. arnd deBoor, 0., "Elementary Numerical Aralysis", McGraw-Hill, New York, 1980. nrcwran STnTE UNIV. LIBRQRIES mWWII?"I"MlWIHIWIIWMINIMUM“ 31293107539284