This is to certify that the thesis entitled A COMPARISON OF SHADING ALGORITHMS FOR REAL-TIME RASTER GRAPHICS SYSTEMS presented by KATHLEEN A . CIESLAK has been accepted towards fulfillment of the requirements for MASTER .OLSCIENCEl—degree in W ENGINEERING Date October 17, 1985 0-7639 MS U is an Affirmative Action/Equal Opportunity Institution _ __ fi- ‘—__—_ —h____—_ _ MSU LIBRARIES a— ‘- RETURNING MATERIALS: Place in book drop to remove this checkout from your record. FINES wiI] be charged if book is returned after the date stamped below. A COIPARISON 0F SHADING ALGORITHMS FOR REAL-TIIB EASTER GRAPHICS SYSTEIS By Kathleen A. Cieelak A THESIS Submitted to lichigan State University in partial fulfillment of the requireaenta for the degree of MASTER OF SCIENCE Department of Electrical Engineering and Systems Science 1985 ABSTRACT A OOIPAHISON OF SHADING ALGORITHIS FOR HEAL-TIME EASTER GRAPHICS SYSTEIS By Kathleen A. Cieslak Shading is an important part of computer graphics. It transforms flat. confusing line drawings to solid images that appear three-dimensional. Shaded images of real-time raster graphics systems must conform to strict timing constraints or the images degrade. Shading is enhanced by improving the shading algorithm as well as the object model and the method of processing the data during the hidden-surface removal algorithm. This report presents eight algorithms from the current literature. They are transformed into functional-block architecture specifications then compared primarily on the basis of speed of execution. However, the fastest algorithm is not necessarily the most suitable. The quality of the images generated is an important criterion for judging the algorithms. If there are no limitations on hardware. the best solution is a combination of algorithms since some are more suitable than others for simulating certain effects. such as specular reflections and transparency. To my Parents and Grandparents ii ACINUILEDGIENTS I wish to express my sincere appreciation to Dr. P. D. Fisher for his constant guidance and encouragement. valuable suggestions. and interminable patience throughout this study. Also. I wish to thank my committee members. Dr. I. Shanblatt and Dr. C. 'ey. for their helpful suggestions concerning this research. Above all. I especially wish to thank Richard Daids for his endless encouragement, patience and understanding throughout the course of this study. This research was supported in part by Lear Siegler. Inc. / Instrument Division. iii Chapter I. mmalon O O O O O O O O O O O O O O I O O O O 0 II. mmnwm O O O O O O O O O O O O O O O O O O O O O 2.1 Graphics Terminology and the Raster System . . 2.2 Problems of High-performance Graphics . . . . . 2 .3 Th. Sh‘din‘ PtOble- O O O O I O O I O O O O O C III. PRESENTATION OF SHADING ALGORITHHS . . . . . . . . . 3.1 Gouraud Intensity Interpolation Shading . . . . 3.2 Phong Normal-vector Interpolation Shading . . . 3.3 Blinn Normal-vector Interpolation Shading . . . 3.4 Newell-Sancha Half-tone Shading . . . . . . . . 3.5 Ihitted Rey-tracing Shading . . . . . . . . . . 3.6 Can-ull Bivariate Surface-patch Shading . . . . 3.7 Cook-Torrance Reflective Iodel for Shading . . 3.8 Fournier-Fussell-Carpenter Fractal-surface Shading IV. COMPARISON OF THE ALGORITHMS . . . . . . . . . . . . 4.1 Basic Routines and Processor Model as Standards for Comparison . . . . . . . . . . . . . . . 4.2 Functional-block Level Transformations of 4.2.1 Gouraud Transformation . . . . . . . . . 4.2.2 Phong Transformation . . . . . . . . . . 4.2.3 Blinn Transformation . . . . . . . . . . 4.2.4 waell-Sancha Transformation . . . . . . 4.2.5 Ihitted Transformation . . . . . . . . . 4.2.6 Catmull Transformation . . . . . . . . . 4.2.7 Cook-Torrance Transformation . . . . . . 4.2.8 Fournier-Fussel1-Carpenter Transformation 4.3 Comparisons . . . . . . . . . . . . . . . . . . V. CONQUSION O O O O O O O O O O O O O O O I O O O I 0 TABLE OF CONTENTS 5 .1 sm‘q O O O O O O O O O O O O O O O O I O O O 5.2 Further Research . . . . . . . . . . . . . . . BEL 1mm 0 O O O O O O O O O O O O O C O O O I 0 iv Algorithms 17 28 33 34 41 50 61 64 71 77 85 89 93 103 105 115 122 132 136 143 148 153 155 159 159 160 163 Table 2.1 4.1 4.2 LIST OF TABLES Page Required memory bandwidths for a 60-Hx display versus pix.l ti-O' [28] O O O O O I O I O O O O O O O O I O O O O O O 22 Summary of execution times for basic procedures . . . . . . . . 100 Summary of execution times and additional hardware . . . . . . . 157 Figure 1.1 3.1 3.2 3.3 3.4 3.5 3.6a 3.6b 3.6c 3.7 3.8 3.9 3.10 3.11 3.12 3.13 4.1 4.2 LIST OF FIGURES I-chart of algorithm transformations . . . . . . . . . . . . Geometry of reflection model for Gouraud's algorithm . . . . Projection of one polygon intersected by the scan line [18] Geonetry of reflection model for Phong's algorithm . . . . . Determination of the reflected light [26] . . . . . . . . . Projections of the reflected light [26] . . . . . . . . . . Positions of light source and viewer with no intarf°r°n°° [3] O O 0 O O O O O O O O O O O O O O O O O 0 Positions of light source and viewer where some of the reflected light is intercepted [3] . . . . . . . . . . . . Positions of light source and viewer where some of the incident light is masked off [3] . . . . . . . . . . . . . Proportion of facet contributing to the reflected light 1. 1 - (-lk) [3] O O O O O O O O O 0 O O O O O O O C O O 0 Geometry of reflection model for Ihitted's algorithm [35] . Paths of reflected light that reach the viewer [35] . . . . Tree formed from components of light reaching the viewer from point P of Figure 3.9 [35] . . . . . . . . . . . . . Patch subdivided so that no subpatch covers more than on‘ ‘upl’ paint [7] O I O O O O O O O O O O O O O O 0 O 0 Geometry of reflection model for Cook and Torrance's .l‘orith [10] I O 0 O I O O O O O O O O O O O O O O 0 O O Subdivision of a triangle [30] . . . . . . . . . . . . . . . Addition array to sum four addends most expediently . . . . Image to be shaded with raster of pixels . . . . . . . . . . vi Page 36 37 44 47 48 56 57 58 59 66 67 68 73 79 87 98 106 Figure Page 4.3 Functional-block diagram of Gouraud's shading model . . . . . . 108 4.4 Functional-block diagram for calculating the shading "'10P." O O O O O O O O O O O O O 0 O O O O O O O O O O 0 O O 109 4.5 Functional-block diagram for calculating the interpolation coefficient . . . . . . . . . . . . . . . . . . 110 4.6 Functional-block diagram of the interpolation calculation . . . . . . . . . . . . . . . . . . . . . . . . . 111 4.7 Functional-block diagram of the entire shading calculation . . . . . . . . . . . . . . . . . . . . . . . . . 114 4.8 Functional-block diagram of the normal vector 'pptoxintion O O O O O O O C O O O O O O O O O O O O O O O O 111 4.9 Functional-block diagram for calculating cos 0 . . . . . . . . . 119 4.10 Functional-block diagram for estimating cos 6 . . . . . . . . . 120 4.11 Functional-block diagram for Phong's shading model . . . . . . . 121 4.12 Functional-block diagram for calculating the direction of the peak specular reflection . . . . . . . . . . . . . . . 123 4.13 Functional-block diagram for calculating c, . . . . . . . . . . 125 4.14 Functional-block diagram for calculating k1 .nd k: 0 O I O O O O O I O O O O O I O O O O O O O O O O O I O 1 26 4.15 Functional-block diagram for calculating the distribution of the facets' orientations . . . . . . . . . . . 127 4.16 Functional-block diagram for calculating g and j . . . . . . . . 128 4.17 Functional-block diagram for calculating the Fresnel function . . . . . . . . . . . . . . . . . . . . . . . 129 4.18 Functional-block diagram for calculating G and the (N.V) to“. O O O O O O O O I O O O O O O O O O O O O O O O O 130 4.19 Functional-block diagram for Blinn's shading model . . . . . . . 131 4.20 Functional-block diagram for Nowell et al.'s ‘h‘dins ladol O O I O O O O O I O O O O I O O O O O O O I O O 134 4.21 Functional-block diagram for calculating shading values for tr.n'p‘r.nt Obj .ct‘ O O O C O O O O I O O O O O O O O O O 135 vii Figure 4.22 4.23 4.26 4.27 4.28 4.29 4.30 4.31 4.32 5.1 Functional-block diagram for calculating 7' . . . . . . . Functional-block diagram for calculating the direction at t°f10ction O O O O O O O O O O O O O O O O O O O O O Functional-block diagram for calculating kf . . . . . . . Functional-block diagram for calculating the direction Of tr.n-1tt°d li‘ht O O O O I O O I O O O O O O O O O O Functional-block diagram for Ihitted's shading model . . . Functional-block diagram for summand generation . . . . . Functional-block diagram for approximating one normal component for a bicubic patch . . . . . . . . . . . . . Functional-block diagram for calculating the distribution of the facets' orientations . . . . . . . . . . . . . . Functional-block diagram for calculating the spectral component of reflection . . . . . . . . . . . . . . . . Functional-block diagram for the Cook and Torrance 'h.din‘ ‘0‘. 1 O O O O O O O O O O O O O O O O I O O O O Functional-block diagram for fractalixation calculations . The relationships between the three processes and the ‘1 ‘orith' O O O O O O O O O 0 O O O O O O I O O O O O 0 viii Page . 138 . 139 . 140 . 141 . 142 . 145 . 147 . 150 . 151 . 152 . 154 . 161 CHAPTER I INTRODUCTION Since the introduction of the cathode-ray tube. (CRT). as a display device for computers. one goal has been to achieve realistic. dynamic images. As opposed to printers and other such display devices. CRTs allow real-time graphical interaction with the computer. Images are drawn on the screen before the user's eyes almost immediately after the commands are entered. Thus. no more waiting for printouts to see results. The next logical step is to improve the images themselves. For real-time dynamic applications. the image must be updated and displayed on the screen at fast rates according to strict timing constraints to create the illusion of movement. Several graphics systems were developed evolving to raster graphics which seems the most promising. Raster graphics systems are capable of creating solid. colored. realistic. dynamic images. Realism is achieved through various techniques. one of which is shading. Shading enhances realism by providing depth cues for a three-dimensional appearance. The effect is similar to a drawing of a circle. which appears as a flat disk until the artist shades it creating the illusion of a sphere. Shading provides for surface properties adding to the realism of the image. If the object being displayed has a smooth surface it will reflect light differently than another with a rough surface. By utilizing properties of reflection from various surfaces according to different types of available lighting shading can convey textures of objects. Patterns may 1 also be imposed onto objects through the use of shading. However. shading has proven a formidable task for designers since it is dependent on many factors. The type of lighting present creates different properties of reflection. The location of the lighting may affect the reflections and form shadows from the object. And as mentioned. the object's surface properties also affect reflections of the light. In addition the manner in which the human visual system operates comes into play as does the location of the viewer. This research presents and investigates several shading algorithms as well as a new reflective model and an object modeling technique. which can be applied to the algorithms to enhance realism. All of these are available in the current literature. This investigation compares the attributes of each algorithm and determines the time complexity using functional-block transformations. Subsequent chapters explain these concepts in more detail. Chapter II provides background information by defining general graphics terminology and explaining how a raster graphics system operates. It presents some of the problems of high performance graphics systems and explains the problem of shading more explicitly. Chapter III presents shading algorithms available in the current literature. These encompass two general methods for representing solid objects. For the polygon-mesh method. several implementations for shading are presented since this is a popular technique for modeling solids. The fourth chapter compares the algorithms presented mainly on the basis of execution time. There are different criteria which may be used to evaluate shading algorithms. depending upon a system's requirements and applications. For example. realism or cost may be important considerations. But for three-dimensional. real-time graphics systems the most important criterion is execution time so that the image update performance is not degraded. Chapter IV presents a processor model to use as a standard for comparison. The algorithms are transformed into functional-block diagrams then are compared for speed of execution using various architectures to efficiently implement the diagrams. By changing the algorithms to a functional-block representation. they are transformed from an behavioral representation to an architectural representation. This can be depicted in what are known as I‘charts [l3]. Y-charts are three-dimensional characterizations of a transformational system. This three-dimensionality can be depicted as a '1'. Each axis is associated with a different representation of the system with different levels of the particular representation located along the length of its axis. One axis is for architectural representations meaning various hardware models of a system. The second axis is for behavioral representations which are different forms in which the behavior of an algorithm may be represented. The third axis is for physical representations or the different stages of the actual implementation. In such a system transformations may occur along the same axis at the same or different levels. or between axes. Arcs are drawn on the I-chart to show these transformations. In this investigation. transformations occur from the Algorithmic level of behavioral representations to the functional-block architectural representations enabling an accurate assessment of the time required for each algorithm's execution. The Y-chart for these transformations is shown in Figure 1.1. ARCHITECTURAL REPRESENTATION PROCESSOR, MEMORY SWITCH LEVEL FUNCTIONAL BLOCK LEVEL REGISTER TRANSFER LEVEL LOGIC LEVEL PRIMITIVE ELEMENT LEVEL (transistors, resistors, etc.) v PHYSICAL BEHAVIORAL REPRESENTATION SYSTEM LEVEL ALGORITHMIC LEVEL BINARY LEVEL 1 - MASK LEVEL 1 - CELL LEVEL - MASTER-LAYOUT LEVEL 1 REPRESENTATION Figure 1.1: Y-chart depicting algorithm transformations The fifth and final chapter summarises the advantages and drawbacks as well as any conclusions derived from the comparison [of the shading algorithms. Possible extensions of this work for future research are also included. CHAPTER II BACKGROUND This chapter provides background information to aid in the understanding of the problem of shading computer-generated images. Some general graphics terminology is presented leading into the specific definitions associated with raster graphics systems. The second section of this chapter discusses some of the problems of graphics systems. specifically those of high-performance graphics. The chapter ends with a more detailed explanation of the shading problem. 2.1 Graphics Terminology and the Raster System The field of computer graphics has been defined as the "creation. storage and manipulation of models of objects and their pictures via computer" [12]. It is concerned with the synthesis of pictures of objects. either real or imaginary. Computer graphics takes the three-dimensional objects and attempts to portray them on a two-dimensional viewing display. For this reason it encompasses many of the basic concepts and techniques of geometry and drafting in addition to phenomena of the real. three-dimensional world. Essentially. all computer graphics systems are comprised of the same types of components. Each system has a host processor. a display controller and a display device. The host processor typically performs other functions as well as graphics processing. The display controller executes 6 instructions to display the images and may have some capability to manipulate them. The distribution of the processing between these components and the implementation of the display procedure are dependent on the type of graphics system. defining the technologies it employs and its complexity. Hovever. all systems perform two basic functions. The first is the construction and manipulation of the object's image. while the second is displaying that image. This division of labor led to the concept of two coordinate systems. The first is the world coordinate system. or object coordinate system as it is sometimes called. This refers to the three-dimensional space. where the object to be modeled normally resides. The second is the device coordinate system. which is the planar space of the display. Here. models of the object are manipulated then projected onto the viewplaneof the screen. It is necessary to use the world coordinates during most manipulations of the object's orientation with respect to the viewer. The object is then transformed to device coordinates for displaying its image. Simple geometric definitions of points and lines are applied during the modeling and manipulations of objects. including the notions of slope and intersections. However. even simple calculations of intersections may become time consuming when working with curved surfaces and solids. There are generally two methods for representing curved surfaces. The first is to divide the object into planar polygons and form a skeletal polygon-mesh. Tho types of polygons arise during such a representation: convex and concave. Convex polygons are those satisfying the condition that for any two points contained by the polygon. all points on the line segment connecting them are also contained by the polygon. Concave polygons are 8 those which are not convex. The polygons are easily represented by listing their vertex coordinates. Because the polygons are planar. second-order equations may be used to describe the surface. but this method tends to produce noticeable contour edges during solid modeling; more so than the next method. The second method for representing curved objects is to define the coordinates of points on the surfaces by three-dimensional equations. Thus patches. which are not necessarily planar. are defined by three parameterixed equations; one equation for each of the cartesean coordinate axes. These equations provide exact information at any point for the surface. Although this may be an advantage. the calculations can become extensive. Though the patches are typically larger than the polygons of the first method. meaning there are fewer patches to calculate. their equations are generally more complex and difficult to handle during manipulations of the object. Therefore. the class of surfaces that may be modeled is limited due to large execution times. but also because curved patches do not provide enough degrees of freedom to satisfy lepe continuity between patches so they are not suitable to model arbitrary forms. Both polygon-mesh and curved-patch representations are often called wire-frame pictures or three-dimensional drawings because their appearance is like a collection of lines and arcs. Once a model of the object has been generated a particular view must be bounded since the display screen has a limited area and/or a picture of the entire object may not be desirable. The rectangular space in the world coordinate system that frames this view is called a window. The window and its contents are then mapped to device coordinates. A viewport is a 9 rectangular portion of the display screen in device coordinates where the window's contents are mapped and thus displayed. A viewport may include all or part of the screen. (Sometimes a viewport is also called a window by some systems. but this ambiguity can be confusing.) This mapping procedure must be repeated whenever the viewpoint of the object is changed. Tb map the object enclosed by the window to the viewport. the object is projected to the plane of the screen. There are two classes of planar projections. The first is parallel projections which assume that the center of projection. (the point through which all projection rays pass). is infinitely distant from the projection plane. which in this case is the viewplane of the screen. Because the projection point is so far away. the projection rays appear parallel. Parallel lines are extended from each vertex of the object to the viewplane. The points of intersection of these lines with the viewplane are the projections of the object's vertices. These vertex projections are then connected according to lines corresponding to edges of the object. Different types of parallel projections exist depending on the number of faces and edges of the object parallel to the projection plane. In general. however. this class of projections is not very realistic because it lacks perspective foreshortening. Perspective foreshortening. performed naturally by the human visual system. is where the size of objects. or their projections. vary inversely with the distance from the center of projection. An advantage of parallel projections is that they scale measurements accurately; therefore. this method is usually used for drafting. The second class is perspective projections which have the effect of perspective foreshortening. The center of projection is explicitly 10 specified and is thus a finite distance from the object. Projection rays. which converge at this point and consequently are not parallel. are extended to the vertices of the object and on through to the viewplane. Again. the intersections of the lines with the viewplane define the projected image. For both classes of projections. angles are preserved only when the object's face containing the angle is parallel to the viewplane. The above projections describe monographic images. where only one image is formed. The human visual system actually produces two images. one from each eye since the eyes are separated by a small distance. The brain fuses the two images into one forming a stereographic image. This provides a powerful depth one known as stereopsis. For this to be effective each eye must see only one of the images formed. Some systems have been designed to take advantage of this effect [8.9]. It should also be noted that most computer displays are based on a left-handed. three-dimensional. cartesean coordinate system where the x-axis points into the screen. Using a three-dimensional projection format along with these reference axes. transformations can be performed on the images to give the impression of motion. Basically. there are two kinds of image dynamics. Update dynamics is when a change occurs in the shape. color or other physical properties of the image being viewed. lotion dynamics is when the object appears to move with respect to a stationary viewer; conversely. it could also be when the objects appear stationary and the observer appears to move. as is the case with flight simulators. This second type of dynamics is possible through transformations. Transformations may change the actual view of the object to make other sides visible or just change the present view's orientation to the observer. 11 The basic types of transformations include translations. rotations and scaling. These may be implemented using matrix multiplications. They create effects such as panning. roaming and dragging. Panning uses translations to move the viewpoint parallel to the viewplane causing the entire scene to move as if the viewers turned their heads. Dragging. which also uses translations. moves one or more objects within the scene being viewed. This is often used in CAD systems while trying to find the optimal placement of objects in a scene. Zooming uses scaling to make the image larger or smaller giving the illusion of the viewer moving closer to or further from the image. The method used to display the images on the screen is one of the main criteria used to catagorixe graphics systems. There are three basic systems: vector-scan graphics also known as calligraphic-scan systems. direct-view storage tubes (DVST). and raster-scan graphics systems. Vector-scan graphics systems were the first type of system to be developed. They are called random-stroke display systems. Pictures are drawn using plotting instructions specifying to draw a line from point A to point B. This is why they are called random-stroke systems; the starting and ending points for their instructions may be anywhere on the display screen. These instructions are stored in a display file where they are accessed by the display controller which executes them on the display device. a CRT. The inside of a CRT screen is coated with a phosphorous material which emits light when excited by an electron beam. The electron beam draws the image by moving across the surface of the screen. but the emitted light fades shortly after the beam moves away. Hence. the image must be retraced 30 times or more each second for the image to remain stable 12 on the screen. requiring a display file to store the instructions so they can be re-executed during the refresh cycle. This refresh rate creates high bandwidth requirements of both the memory and the processor to meet the necessary timing. If the image is not refreshed soon enough it fades then again becomes bright after it is finally retraced. This noticeable flashing of the image is known as flicker and can be annoying to the systsm's users. In order to be able to retrace the entire image within the allotted time. vector graphics' images had to be fairly simple. The use of a structured display file helped solve this problem. It is an extension of the regular display file because it stores hierarchies which compose the image. These hierarchies are like subroutines to a software program and can be executed faster. A structured display file allows for transformations by merely specifying parameters for the size. location and orientation of the image thereby improving dynamics. vector systems use less memory than raster systems. but the deflection circuitry used for the electron beam is complex since it must accommodate random strokes. The DVSTs operate on a random-stroke basis but the display screen is different. Inside the screen is a dielectric mesh which retains the image until it is deliberately erased. This eliminates the need for the display file which was a significant advantage before VLSI reduced the cost of memory chips. Unfortunately the image cannot be selectively erased; the entire image must be wiped out all at once. To erase the screen a charge is applied to the dielectric mesh which appears as a flash. This can be annoying to the user. However. it is possible to reduce the energy of the electron beam while drawing the image so that the image will not be volatile. but then a display file is needed to refresh it. The advantage of 13 this is the capability of displaying a frame composed of both volatile and non-volatile images. This would decrease the demands of each refresh cycle to only retrace some of the image; the parts anticipated to move. This is similar to the technique used in animated cartoons. But neither of these systems can display solid. dynamic images. Raster-scan graphics systems were developed using television monitors giving them this capability as well as taking advantage of the established assembly lines of the monitors. The monitor screen is broken into an array of picture elements called pixels. The electron beam scans the pixels row by row from top to bottom in a fixed pattern known as a raster. This eliminates the need for the complicated deflection mechanism of the random-stroke display systems. Actually. there are two types of rasters. The first is a non-interlaced pattern where the electron beam traces each horizontal line. called a raster line or scan line. in sequence from top to bottom of the display. The second is an interlaced display which alternates the lines dividing them into an even field. the even-numbered lines. and an odd field. the odd-numbered ones. To display a complete image or frame. both fields are required so two passes through the raster lines are necessary. In both rasters. as the electron beam moves along a scan line it is called active because it is displaying data. Retraces are when the beam reaches the right edge of the line and returns to the left edge of the next raster line. (horizontal retraces); or similarily. when the beam returns from the bottom right corner to the top left corner. (vertical retraces). During these retraces. (not to be confused with redrawing an image though the terms are identical). the electron beam is blanked or turned off. A variation of either raster is called horizontal underscanning. By 14 decreasing the horizontal deflection of the electron beam the raster pattern is altered to change the shape of the pixels. usually making them square. Ihelan [34] presents what he calls a subclass of raster-scan systems. The pixels of his display are rectangular areas which are larger than typical pixels enabling his system to be faster than general raster systems while still retaining all of their attributes. though he loses some spatial resolution of the display. The time required to completely scan the raster is called the refresh rate. The reciprocal of the refresh rate is the frame time which measures the duration of each frame before the next refresh. These two rates help determine the level of interactivity of a raster display. or how fast a new image can be generated in response to a user's input. This is usually the most critical performance measurement of a raster graphics system. Typically. raster systems are slower than random-stroke systems because they indirectly draw lines and arcs by scanning the entire screen activating only. the pixels composing the lines and arcs. whereas random-stroke systems only pass over the points of the lines and area. But. with faster processors and shorter memory access times. raster systems are approaching the speed of the random-stroke systems. One disadvantage of raster systems is that they require large memories. The number of distinguishable pixels in the raster determines the display's resolution. Some of the highest resolutions may be larger than an array of 4096 x 4096. The image memory; also known as the frame buffer. display or bit-map memory; has one or more bits of memory that correspond to the pixels of the display. A bit plane is an array of memory of one bit per pixel. The pixel depth of a system is its number of bit planes. This determines 15 the number of gray-scale intensities available for shading on an achromatic display. (a monochromatic display has one bit plane and thus displays only black and white). or the number of colors available for color displays. called color resolution. An image plane is a set of bit planes. usually eight. For full color. three image planes are needed; one each for red. green and blue which are the additive primary colors necessary to combine and produce most other colors. (They are called additive primaries because individual contributions of each are added to form other colors.) Consequently. the number of bits in the image memory must be one or more times the number of pixels of the display screen. Because of such large memories raster systems need an extremely high bandwidth for both the processor and memory to satisfy image update and display timing constraints. But this pixel-by-pixel addressing capability is the key which allows different kinds of images on a single screen; such as alphanumeric characters combined with photographic images. Baldauf [1] made an important observation concerning bit-mapped memories and raster-scan displays; namely. to increase the quality of the display does not necessitate increasing the number of pixels of the display. Using a system with four megabits of memory. Baldauf compares the configuration of four million pixels with one bit of memory per pixel to that of one million pixels with four bits per pixel thus providing sixteen gray scales. The quality of both is very similar and the cost advantages favor the latter. Concerning display devices in general. achromatic monitors are superior to color monitors in terms of brightness. resolution and size. Color displays are more complex and impose significantly higher bandwidth 16 requirements on the memory and processor. Therefore. color monitors cannot easily match the quality of their achromatic counterparts. However. color adds another dimension to the information displayed. It also adds considerably to the price of the system. In 1979 they were considered too costly for widespread use [15]. But in 1984 according to lachover and Meyers [22]. sales of color raster displays were growing at a rate of two to three times faster than the rate of growth of DVSTs and vector-scan displays. meaning color displays are gaining popularity. A variation of achromatic displays which is also gaining popularity. particularly among users who enter data from printed papers. is the positive image display. Positive images are black characters on a white background. This is a bit different to implement because instead of turning pixels on to show an image. the background is always on and the pixels making up the hmage are turned off. But this is less tedious for the user since the screen has the same sort of contrast as printed material. The hardware required by a raster system consists of the components of a basic graphics system mentioned earlier: a host processor. display controller. and display device. The display device's operation is as already discussed. Sometimes. in smaller systems. the host processor is called the display processor. graphics processor. video display processor or display generator. Often. there is still another processor which acts as a host performing other functions but which has the capability to manipulate the image memory. too. The display processor manipulates the data in the image memory by writing new data to update the image for the next frame. It also has the ability to read the memory to determine previous pixel values so as to establish new values. Display processors once were merely buffers. 17 but graphics functions were eventually moved there to relieve the host processor's burden so it could perform other duties. The raster system equivalent of the display controller. the final component of a basic graphics system. is called the video refresh controller. refresh controller. display controller or frame buffer controller. It reads from the image memory and feeds data to the output portion of the system. It does not have the ability to alter pixel data; in other words it can only read from the image memory. not write to it as well. The display controller's main function is to obtain the pixel data in parallel form to utilize higher bandwidths then convert it to a serial bit stream to store in the video buffer. frame buffer. or refresh buffer. The video output hardware converts the data to intensity levels or colors helping the display controller create the serial data. The video buffer stores the pixels' intensities or colors for the display. In summary. there are vector-scan displays. which are random-stroke. refresh systems; raster-scan displays. which are non-random-stroke. refresh systems; and direct view storage tubes. which are random-stroke. refresh and/or nonvolatile-image systems. 0! these three. raster graphics is the only one able to display solid. dynamic images but it is not entirely free of problems. These problems and some of general graphics systems are presented in the next section. 2.2 Problems of High-performance Graphics This section begins with some general problems common to all graphics systems. One is that CRTs are analog devices and computers and processors 18 are digital devices. A digital-to-snalog converter. (DAC). is essential to graphically display information. Since the DAC converts the digital signals from the display controller to analog voltages meaningful to the CRT. the DAC's resolution directly determines either the number of gray scales or colors resolvable in the monitor. A color monitor needs three DACs. one each for red. blue and green. Castleberry [4.5] discusses this problem and presents a video DAC that meets the high-performance requirements of a graphics system. yet is low cost. Another problem. which may be apparent from the redundant terminology. is a need for standardization. Each unique graphics configuration developed requires a new software system to support it. According to lachover and Myers [22]. "the principal idea underlying the quest for standards was that the main body of software should be device independent. It should interface to any input device through a device handler. which would. of course. be device independent. Similarily. it should interface to any type of display through a display driver". One advantage to software which is adaptable to any hardware system is that once programmers have learned to use it they become portable. too. and can move about freely among systems. Several graphics standards exist now with some moving towards national or international acceptance. In 1977 the Core Graphics System standard was develOped by an AC! Siggraph Committee. It is a three-dimensional standard defining the boundary between applications and the graphics support package as well as specifying the content of that package. Although it was not officially accepted by the International Standards Organization. (ISO). it has been influential in the development of other standards. particularly the Graphical Kernel System. (GKS). GKS has been officially accepted by ISO. 19 It has been called a ”Small Core” because it. too. defines the boundary between the applications and the graphics support package. However. it does not specify the content of the graphics support package. and it is a two-dimensional standard although three-dimensional extensions have been discussed. Iachover and lyers [22] list five other standards and their status toward national or international approval. They are as follows: 1) Initial Graphics Exchange Specification. IGES. It provides for the exchange of graphics databases among CAD/CAI systems. 2) North American Presentation Level Protocol Syntax. NAPLPS. It uses sequences of bytes of ASCII code and code extensions to describe graphics and text in separate frames. As the name suggests. it functions at the sixth level of the ISO's Open Systems Interconnection model and can transmit graphics and text over a low-capacity data communication link. 3) Programmer's Hierarchical Interface to Graphics Standard. PHIGS. It is an updated. expanded. dynamic. three-dimensional version of Core. 4) Virtual Device letafile. VDI. It is a two-dimensional. device-independent standard conceived to satisfy both the Core concept and GKS for metafiles. It functions at the level just above device drivers and is concerned with the transfer of picture information between different graphics devices. 5) Virtual Device Interface. VDI. It also operates at the level just 20 above device drivers but is a two-way communications protocol. It interfaces between device-independent software and device-dependent code. Among the problems peculiar to raster systems. the memory contention problem has received significant exposure in the literature. To avoid flicker in the displayed image. the display controller must refresh the display 30 or more times per second. For the illusion of motion the display must be refreshed even more often to avoid jerky movements. so the display controller must access the image memory for the display data frequently. leanwhile. the display processor is calculating the data for the next frame to be displayed and must update the image memory before the display controller needs the new data. As a result both have high demands for accessing the memory creating a memory contention problem. Adding to this matter. many of the problems to be discussed later. (including shading). increase the processing time to generate the new image thus affecting the display processor's attempts to meet its timing constraints. Iith most systems a stable display is the foremost requirement so the needs of the display controller are met first then tradeoffs are made to accommodate the display processor. Some specific timings that are critical to the Operation of the display controller are the refresh rate. retrace times. total line time. active line time. total frame time and pixel time. All of these pertain to the display and though most build on each other. they are particularly dependent on the refresh rate. As previously stated. the refresh rate is the number of times the entire screen must be scanned per second. The retrace times are the amount of time needed by the electron beam to reposition itself after displaying a raster line. Since the beam is 21 blanked. the display controller may not need data from the memory. depending on whether it has enough for the next active session. Often the display processor will access the memory during these retrace times. The total line time is the average time required by the electron beam to scan a visible raster line including the horizontal retrace time. Active line time does not include the retrace time since the beam is blanked. The total frame time is the total line time multiplied by the number of visible lines in the frame plus the vertical retrace time; its reciprocal is the refresh rate. Pixel time is the average time necessary for the beam to scan a single pixel; it is the active line time divided by the number of pixels per line. Essentially. it is the rate that new pixel data must be supplied to the video output hardware to support display refresh. In other words. if data for only one pixel is obtained during each memory cycle. pixel time determines the rate in which the memory must be accessed by the display controller; therefore. the pixel time determines the necessary bandwidth of the memory and processors. According to Righter [28]. the required. instantaneous. memory bandwidth is equal to the reciprocal of the pixel time. He presents a table of required memory bandwidths for a 60—Hz display versus pixel times for different display dimensions. shown in Table 2.1. To achieve such high bandwidths. many solutions have been presented. One device designed to allow better access to the image memory is dual-ported memory chips. These devices provide two access paths with the actual memory time-shared between these ports; it does not imply that the same memory location can be accessed simultaneously from both ports but this method does provide some time savings [19.27]. Some of these chips include extra logic to help decrease access times. On-board shift registers 22 Table 2.1: Required memory bandwidths for a 60-Hz display as inverse of pixel time [28] was: 34.39.1122 mm 512 x 384 66.5 ns 15 le 640 x 512 38.3 ns 26.1 le 1024 x 768 14.4 ns 69.4 le 1024 x 1024 10.0 us 100 le 1280 x 1024 8.0 ns 125 MHz 23 transform a large block of parallel data to a serial bit stream leaving the device free for the next access [38]. Drumm. Harris and Ebertin [11] include on their device logic to handle memory contention so it is possible to access the same location simultaneously from both ports. Iilliams [37] compares the different types of general purpose memory chips available. such as SRAIs. DRANs. EPROIs and EEPROIS. Other solutions to the problem of memory contention include architectures for the memory itself to increase its bandwidth. Depending on the arrangement of the memory chips. different access modes can be implemented to access rows. columns. pages or nibbles. Ihitton [36] summarizes the different access modes as she thoroughly discusses the memory contention problem. She claims that displays of moving. smooth-shaded solids and vector objects almost always require a technique known as double buffering. Double buffering is when two complete images are stored in the video buffer. 'hile the display controller is accessing one copy to update the display. the display processor is writing the next frame's data into the second copy. At the end of their cycles the two processors switch copies. Double buffering nearly eliminates the memory contention problem but is costly to implement. Overall. Ihitton concludes that bigger memory devices do not necessarily mean better access and stresses using different architectures to achieve higher bandwidths. Though the display controller needs the image memory to supply data to the display. high-performance graphics dictates that a large number of pixels be written into the memory every frame time. For this reason van Dan [39] claims graphics cannot be done remotely; both the display processor and the display controller need to access the image memory. This is especially 24 true of high-performance graphics systems because they need a front-end mini- or mainframe computer for the data manipulations. In general. as interactivity decreases. frustration increases contributing to premature user fatigue. So the display processor must be able to quickly process the new image and store it into memory for the display controller to display. As designers strive for realism. images are becoming more complex requiring excessive time to generate updated images corresponding to new viewpoints derived from user inputs. Again. architectures can be implemented to speed up processing. such as pipeline and/or parallel processing. and petri nets which are data-driven systems. Hany papers exist discussing multiprocessing techniques both for their own merit and as applied to specific graphics systems. Such architectures provide increased throughput and. if modularly designed with well-defined interfaces between the processors. they may provide modification flexibility. In addition specialized hardware to perform some image generation functions greatly decreases processing time though at an increase in cost. lost of the other problems of highrperformance graphics systems affect the image-processing time. The first step to producing an image is to model the object. Tho methods for modeling objects have already been discussed; polygon-mesh and curved-patch equations. Generally. objects do not follow surface models very well. Particularly with natural phenomena such as clouds or smoke. these models become extremely complex trying to imitate these objects. Also the diversity of a design within a given framework is limited. A model may be able to produce an image of a tree but it may not be able to distinguish a poplar from a maple tree. Then again. such fine detail may not be necessary. depending on the application. The model must 25 also provide a three-dimensional projection format. This not only keeps track of faces and edges seen in the chosen view but those not seen. too. as well as the depth or z-coordinate of each. This type of format allows for hidden surfaces to be appropriately shown when the view changes and aids in most of the processes to be discussed such as clipping. hidden surface removal. shading and shadow generation. Actually. all four of the processes mentioned are related to each other and are especially dependent on how the object was modeled. Clipping is a technique for not showing portions of the object outside of the window. It is executed before hidden surfaces are removed because it determines the depth coordinates of each of the surfaces of the image. It also decreases the number of surfaces so these are removed before any more calculations are performed on them to avoid wasting time. Hidden-surface removal is the next process performed on the image because it. too. removed surfaces from the image so they are eliminated before they are processed any further. Also known as the visibility problem. hidden-surface removal is used on both solid models and wireframe drawings alike. It removes any surface or line that is obscured by surfaces that are closer to the viewer. thus generating a realistic. solid picture or a less confusing wireframe drawing. Unfortunately. the identification and removal of hidden surfaces is very time consuming. so many different algorithms have been developed to solve this problem. One notable contribution.was from Sutherland. Spoull and Schumacker [31]. They compared ten such algorithms trying to find some fundamental insights into the problem itself. They concluded that all of the algorithms performed some sorting of the surfaces to determine which were visible; if the sorting 26 process could be made more efficient the execution time would decrease. They presented two methods of sorting different from those used by the algorithms that they compared. A second conclusion was the detection of a principle called coherence; that objects have a local constancy about theme "Scan-line coherence" is the fact that a scan line changes very little between successive frames. "Frame coherence” is that an entire picture is nearly the same from one frame to the next. In fact the world model of an object changes less frequently than the viewing position. These principles may be used to reduce the amount of computations necessary for generating successive frames. Other features which enhance realism are filling adjoining surfaces with contrasting shades to show intersections. adding highlights and textures. shading surfaces to show form and three-dimensional qualities. and simulating transparent surfaces. These will all be treated in the next section which explains the shading problem more completely. The final process covered in this section is shadow generation. Shadows enhance realism by providing depth cues reinforcing the three-dimensional effect. They are not dependent on the viewpoint but on the type of light sources available and their locations. If. however. the light source is behind or at the viewpoint no shadows will be visible; they will be cast behind the object. hidden from view. This is often the approach taken to avoid the extra calculations to generate shadows. The same algorithms used for hidden-surface removal can be used to create shadows except the light source's location is used as the viewpoint. Instead of removing the surfaces hidden by other objects. their intensity or color is changed to produce the shadow. Since the processing is so similar. 27 it is possible to compute hidden surfaces for removal and shadows simultaneously. Nevertheless. even after all of the above processes have been performed on the image there are still problems merely drawing it onto the display. A line or are cannot simply be drawn from point A to point B on a raster display because of the scan pattern; it must be transformed or mapped to a pixel representation which is a process called scan conversion. This is usually performed by the raster display itself so the user does not need to be concerned about it. Once the lines are drawn. they must be smoothed. Any nonvertical or nonhorixontal line may appear as a staircase because of the arrangement of the pixels in a matrix which form the line. There are two approaches to this problem. known as aliasing. The first approach is to increase the resolution of the display. By increasing the pixel density the jaggedness of the edges and lines will be smaller and less perceptable but there will be more points to compute overall. The second approach is to use multiple bits of memory to represent each pixel's intensity or color. Varying the intensity along jagged edges will create the impression of straight lines because the edges will be turned. or faded into the background. Once the lines have been smoothed. intersections of surfaces must be computed particularly for objects modeled by equations. Phillips and Odell [25] discuss this problem and present an algorithm to attempt to solve it. They stress that it is often more difficult to find intersections than to just display them. Fortunately. for many applications this is sufficient. The next section provides more detail concerning the shading problem and many of its related processes mentioned above. 28 2.3 The Shading Problem Essentially. the problem of shading is to generate solid images by filling the polygons or patches formed during the modeling stage in such a way as to enhance realism. Shading is affected not only by the method of modeling the object but also by the hidden-surface removal algorithm used; the order in which the hidden-surface removal algorithm computes visible information influences the shading algorithm. The best attribute a hidden-surface removal algorithm can possess. with respect to shading. is to generate information by scan line rather than arbitrarily ordered patches or polygons. Because these two algorithms are so closely related they are often treated together in published studies. Shading algorithms vary in complexity ranging from those that arbitrarily fill the surfaces of an image to those that record minute details of surface properties. texture and patterns. All but the simplest involve the behavior of the human visual system and principles of optics. Peculiarities of the behavior of the human visual system often force algorithms to compensate. or even deviate from. otherwise uniform shading rules. The effects will be discussed as they pertain to the method or problem being presented. Briefly. the optics principles involve the angles of incident light to the surfaces being shaded. The resulting reflection. absorption or transmission from the surface is dependent on many factors. One such factor is the surface properties of the object being modeled; a smooth. glossy surface will reflect more light than a dull. matte surface. Another factor is the light source itself including both the type of light and its location. The type of light as well as its luminance. or intensity. is 29 influencial in determining how an object will be lit up. Diffuse background light. or ambient light. produces constant illumination of objects regardless of their orientation to the light. This uniform brightness makes objects appear flat and does not usually produce realistic images when used alone. Point sources of light can produce specular reflections. or highlights. which are dependent not only on the object's orientation to the light but also the viewer's orientation to the object with respect to the light's location. This creates much more interesting images. The absorption of light determines the object's color or intensity. The transmission of light through objects is related to absorption by the object's degree of transparency. It is similar to the shadow—generation and hidden-surface removal processes because objects behind transparent objects must be identified. The illumination of these ”hidden" objects is altered according to the amount of light actually allowed through the object in the foreground and whether or not that light is refracted. loreover. transparent objects often yield specular reflections. which sometimes help reinforce the presence of clear objects. One method effectively used to generate transparent objects. in addition to opaque objects which have a zero percentage of transparency. is called ray-tracing. Using the principles of optics. light rays are followed from the viewer to the first surface where the ray will branch into its components of reflected and refracted light. Each of these components is followed forming a tree that can be used to determine the shading intensities of the surfaces viewed. One such algorithm is presented in the next chapter. Surface detail can be conveyed through shading; textures and patterns enhance realism and can be exhibited through proper shading. One method is 30 to map a digitized photo or model of the pattern or texture to the surface of the image. This mapping determines the pixels' intensities or colors and is probably the best way to generate patterns. Tbxtures can be shown in this manner or they can be modeled. One approach is not to actually model the texture but to perturb the surface normal to indicate the texture. The surface normal is critical to measuring angles of incidence. reflection and refraction from the surface while computing intensity values. So. by altering the nermal's true direction a smooth surface will appear as a rough surface. but the overall effect is not very realistic. Another approach is to model the texture using fractal mathematics which were developed by Benoit landelbrot. This method uses stochastic processes to model the randomness of natural phenomena. This method. too. will be discussed further in Chapter III. Another method for generating shaded images is known as half-tones; this is the method used in most printed matter such as newspapers. books and magazines. The human visual system performs spatial integration where a small area. when viewed from a distance. appears as a single intensity despite the fact that a close-up examination reveals fine detail of varying intensities. This effect is used when producing half-tone images. The screen is divided into small resolution units. usually a small. square matrix of pixels. Each resolution unit is imprinted with a black dot whose area is proportional to the amount of blackness of the corresponding area of the object being displayed. (Blackness equals one minus the intensity.) This method provides more intensity levels without increasing the number of bit planes but spatial resolution of the display is sacrificed. Color is another type of surface detail. Achromatic color includes 31 black. white and shades of gray with its only attribute being the intensity of the colors. Chromatic displays have many attributes. Hues distinguish between different colors. Saturation. also called chroma. refers to the purity of a color or the amount of dilution by white light. ('hite light is 0% saturated.) Brightness. or value. is similar to intensity for achromatic color. A tint is the result of adding white light to a color thereby decreasing its saturation. Shades result when black is added to a pure color. decreasing its brightness. Tones are the result of the addition of both black and white light to a color. Several theories have been developed concerning the eye's reaction to color. One of specific interest for raster systems is called the tri-stimulus theory. This theory states that there are three different types of cones on the retina of the eye. each having peak sensitivities to light of either red. blue or green hues. This is aligned with the concept of using these same hues in combinations to produce most colors on color television or raster-scan monitors. A comprehensive discussion of color which covers topics like different color models for monitors and printers. and objective descriptions of colors using electromagnetic energy densities and standard chromaticity diagrams is beyond the scope of this paper but is included in Foley and van Dan's book [12]. One color model of pertinence to raster graphics is the RGB color model. Using a right-handed cartesean coordinate system. a unit cube is formed with black located at the origin. white at the point (1.1.1). and red. blue and green are located on the axes where z-1. y-l and x-l. respectively. The main diagonal connecting black and white contains equal amounts of each primary and represents the gray levels. However. this model is hardware-oriented so it is not easily 32 controlled by the user because it does not directly relate to intuitive notions of hue. saturation and brightness. Nevertheless. to implement color on a raster display three sets of equations are necessary. one for each primary hue. This is why color systems generally require higher bandwidths of the memory and processors and are more difficult to implement. Overall. the procedure for computing shades or IGB values for a particular pixel involves determining which polygons or patches are mapped there. finding details about the surfaces assigned color or intensity. calculating the pixel's angle and distance from.the light source and from the viewer. then computing the shading value for the pixel in question. Details about the surface include taking into consideration most of the processes already discussed to create a realistic image. After everything is considered. shading is a complicated process and many algorithms have been developed to provide a solution. Several of these algorithms are presented in the next chapter. CHAPTER III PRESENTATION OF SHADING ALGORITHMS Some of the first shading procedures are known as constant-shading algorithms. These are usually applied to objects modeled using the polygon-mesh technique where each planar. polygonal facet is filled with a single intensity value or color. One problem with this method is that adjacent polygons may exhibit an obvious difference in intensity; in reality. objects are composed of continuous curves and their intensities vary continuously. By shading images with this method the polygons used to model the object are apparent to the viewer.[22] This couspicous transition from one intensity to the next is called contouring and contributes to the unrealistic appearance caused by this method. Another problem with this method is known as the Inch-band effect. which is caused by the human visual system. If the light-intensity curve from illuminated surfaces has a discontinuity in magnitude or slope. the eye accentuates the change. Thus. the difference in shading of adjacent polygons is exaggerated. lore complex algorithms have been developed to overcome these problems to provide continuous shading of curved surfaces as well as simulate texture. transparency and other attributes discussed in the previous chapter. Four of the next five sections present one such algorithm. The third and seventh sections present new shading models which could be applied to some of the other algorithms. The sixth and eighth sections introduce different methods for enhancing the object models. The sixth section uses the curved-patch modeling technique discussed in Chapter II. The eighth and 33 34 final section presents a new method based on fractal geometry to alter models of terrains and other natural phenuena. Both may be applied along with any of the other shading models to generate realistic pictures. Included in this text are many equations and figures that are modified versions of those that appeared in the papers which originally presented the algorithms. Some adjustments were necessary to unify the notation used throughout this text as well as to eliminate or add portions of figures to better represent the discussions contained here. 3.1 Gouraud Intensity Interpolation Shading This algorithm [18]. published in 1971. is applied to a curved-patch object-modeling technique called rational Coons patches but could easily be modified for the polygon-mesh technique. In 1964 S. A. Coons introduced a modeling technique to extend the class of objects that may be modeled; this technique allows for the definition and representation of curved surfaces. An extension was develOped by T. I. P. Lee in 1969 called the rational Coons patch. One of its properties is that patches can be reparameterized without modifying their geometric shapes. Gouraud's algorithm is based on a hidden-surface removal algorithm developed by G. S. Iatkins which accepts nonplsnar polygons; so. Gouraud extended it to rational Coons patches. Intkins' algorithm computes information about the image scan line by scan line. which facilitates the shading process. The actual shading rule implemented utilizes basic principles of optics which take into consideration the object's orientation and its distance from the viewer. The light source is assumed to be at the same location as the observer to 35 avoid the need to generate shadows. The object's orientation is measured as the cosine of the angle. 0. between the surface normal. N. and the direction of the light. ‘L; or as in this case. the viewer. V; shown in Figure 3.1. The distance from the viewer is introduced to distinguish between overlapping. parallel planes which would otherwise be shaded with the same intensity since both have the same orientation. This also simulates the manner in which the eye perceives illuminated objects from a distance; because light energy decreases as the inverse square of the distance. parallel faces at different distances from the viewer would appear to be different intensities in reality. According to Gouraud. the method used to compute the distance is not important as long as the relative ordering of the faces is preserved. Using the perspective transformation. the (x.y.z) coordinates of a point become the projection coordinates (x/z. ylz. lls) if the observer is located at the origin of the coordinate system and is facing in the positive a direction. Using the 1/1 coordinate as an approximation of the distance. the shading equation becomes 1 3 S - ; cos 0 (1) Since the distance values. 1/z. are only known at the vertices of the polygons. it is necessary to perform a linear interpolation for points between the vertices to obtain the distance values. After the distance values have been computed. the shading for point P located on the scan line between points E and F shown in Figure 3.2 is approximated using the equation .1. . .1. . SP = (1 - u) 2E cos 0 + o 1F cos 0 (2) 36 Figure 3.1: Geometry of reflection model for Gouraud's algorithm 37 Scan Line Figure 3.2: Projection of one polygon intersected by the scan line [18] 38 The coefficient u ranges as O S u S 1 and denotes the position of the point P on the scan line between the end points E and F: if P is located at E. then u - 0; if P is at point F. then u - 1. Gouraud claims there is no noticeable degradation in the shading from using this approximate equation. To smoothly shade curved surfaces Gouraud modifies the shading computation of each patch so that continuity exists across each boundary. Since each vertex of the patch will be oriented differently. thus requiring different shading. interior points have to be shaded as a continuous function of the vertex shading. Generally. these modifications attempt to alleviate the effects of contouring and the Mach-band effect. To help achieve this shading continuity a normal for each vertex is computed by either averaging all of the patch vertex-normals associated with the vertex or using an analytical description of the surface to compute the exact normal. Two successive linear interpolations are performed to compute the shading of interior points for each patch. Referring again to Figure 3.2. the surface normals are assumed to be known at the vertices A. B. C and D. The scan line intersects edge AB at point E and edge CD at point F. The point P is any point inside the patch ABCD that is on the scan line. The shading at points E and F is interpolated using the shading values calculated at the vertices. The shading at point E is calculated using the shading values from point A. 8A' and from point B. 83' in the equation where “E is defined similarily to u in equation (2). Likewise. SF and SP can be calculated using the equations 39 SF-(l-uF)SD+uFSc (osapsn (4) sP-u-ap)sg+aps,. (osapsi) (5) Using these equations. it can be verified that if P ' A. then SP 3 8A P l B. then SP 3 SB P . Cs than SP 3 Sc P 3 D. then SP‘a SD Since latkins' technique for computing hidden surfaces efficiently calculates and tabulates data for the image. this was extended to include the shading calculations to help minimize the computation of a new shade for each point. Watkins scans the picture from top to bottom by scan line. computing the following information for each polygon edge: 1) The number of the first scan line that intersects the edge. 2) The total number of scan lines that intersect the edge. 3) The x and z coordinates of the highest point of the edge. 4) The slope in x and z for the edge. The necessary shading information is easily added to this list: 5) The shading. S. of the surface at the highest point of the edge. 6) The "slope" of the shading along the edge. The shading "slope" is calculated as S - S AS =_’___L (6) n 40 where S: and S, are the shading of the two endpoints of the edge and n is the total number of scan lines that intersect the edge. 'ith the above information the shading may be computed for a given scan line. An edge will become "active" when its first point is reached by a scan line which is being used in the shading computation. The xyz coordinates are known for this point along with the value of the shading. A segment is created when an edge becomes active by pairing edges which belong to the same patch; the segment is the portion of the scan line between the paired edges and contains information about the coordinates of the endpoints. the values of the shading at the endpoints. and both the coordinate slope and shading "slope" necessary to update shading information from scan line to scan line. From the present scan line the slopes are added to the coordinate information of the point on the edge and to the point's shading value to find the coordinates and shading of the next point where the next scan line intersects the same edge. After the hidden-lines computation is perfonmed. many of the segments are totally or partially visible. The shading is calculated for each visible point of a segment along a scan line by computing a coefficient as KP - IE xr’xr where the K's represent the displacement along the scan line. Using this (7) value for the coefficient a. the shading can be calculated for the point P of Figure 3.2 using equation (5). According to Gouraud. this linear interpolation for the shading intensities produces shading across patch boundaries which is continuous in value but not in derivative. This eliminates most of the contouring effects 41 but some Inch-band effects may be seen in the vicinity of silhouette curves and where the surface curves sharply. He stresses that this algorithm may be implemented in hardware since it is only a linear interpolation being performed. and he compares the execution times required for Iatkins' algorithm and the extended algorithm proposed by Gouraud. If Gouraud's algorithm is totally implemented in hardware. no extra time will be required for execution though extra demands will be made of the memory. If the algorithm is implemented in software. the total time required by Iatkins' algorithm would be multiplied by less than 1.2 for Gouraud's algorithm's execution time. Two systems which have implemented Gouraud's algorithm are described in papers published by Fujimoto. et al. [17]. and Fuchs. et a1. [16]. The next section presents an algorithm which tried to improve upon Gouraud's by reducing the Itch-band effect. 3.2 Phong Normal-vector Interpolation Shading This algorithm [26]. published in 1975. was developed by Bui Thong Phong. It expands upon Gouraud's algorithm because instead of linearly interpolating the intensity value of the shading. Phong's algorithm interpolates the surface normal and then calculates the new shading values using these normal vectors. Phong also uses a more complex shading equation which allows the viewer to be in a different location than the light source in addition to taking into account reflectivity of the object and specular reflections. Phong presents the more complex shading rule with his algorithm as an attempt to achieve more realistic shading. Another 42 difference between the two algorithms is that Phong's algorithm is presented for objects modeled using the polygon-mesh technique. Phong's shading equation is based on the physical principles of optics with a few empirical adjustments. The direction of the incident light is always measured as an angle with respect to the surface normal. 0. The angle of incidence equals the angle of reflection. so the direction of the reflected light is also measured as G with respect to the normal. Different types of lighting affect the object's illumination in different ways as do different types of surfaces. Rough or dull surfaces scatter the reflected light in all directions equally. an effect called diffuse reflection. This type of reflection follows Lambert's cosine law which relates the amount of light reflected and the direction of the light source to the surface as shown in the equation sP.d " 91» c“ 9 (s) where CP is the coefficient of reflectivity of the surface; CP is a ratio of the light reflected from the surface to the total amount of incoming light at the point P. This type of reflection is not dependent on the viewer's location because the object appears a constant intensity from all directions. Diffuse background light. or ambient light. produces constant illumination of objects regardless of the object's orientation; reflection is dependent only on the object's coefficient of reflectivity and the intensity or brightness of the light. for which Phong uses an environmental diffuse reflection coefficient. Cd. Normally. an object subjected to only ambient light would be illuminated according to the equation 43 SP.‘ . CP Cd (9) but Phong combines the equations (8) and (9) as sP.(d + ‘) ' CP (CO8 0 (1 ' Cd) + Ca). (10) Diffuse reflection from colored surfaces requires three equations. one for each primary color. lost of the light is absorbed but the color of the light reflected is the perceived color of the object. Specular reflections depend on the location of the viewer because the light is reflected unequally in different directions. Such highlights are emitted from shiny surfaces and appear white. or the color of the incident light because most of the light is reflected. For a perfect mirror. light is reflected only in the direction of perfect reflection; that is when the angle of incidence equals the angle of reflection. This is the reason for the concentration of reflected light in the highlight. For nonperfect reflectors the reflected light is not quite as concentrated but falls off rapidly as the direction moves from that of perfect reflection. Therefore. the viewer's location is critical; as the viewer moves from the direction of reflection. less light is available to be seen as a highlight. The direction of the line of sight is measured as the angle a from the reflection vector. R. as shown in Figure 3.3. Phong approximates the specular reflection as the cosine of a raised to the power c1. where c1 usually ranges from one to ten. Then the surface is a perfect reflector. c1 is large so the value will rapidly go to zero as o deviates from O. This cosine term is multiplied by a function '(O). which is a function of the ratio of the specularly reflected light and the incident light as a function of the incident angle; l(0) ranges between 10 and 80 percent. Both c1 and 44 t” 2H “4 Figure 3.4: Determination of the reflected light [26] 48 3>1< >i< X‘E Figure 3.5: Projections of the reflected light [26] 49 where ir' In. It. and Ti are components of R5 and 'NP in the x and y directions. respectively. Using assumptions (1) and (2). the component 7‘ of N? is Eh - cos 0. (16) meaning 0 S'En S 1. The following relations are obtained from trigonometric identities i-zz'-1 (17) and i; + if" - 1 - cos: 20. (18) Using equations (15) and (18). we obtain it - 221. in (19) and Y: - 22n in (20) Thus. the three components 0f if are obtained from NP and are known in the light source coordinate system. The projection of if onto the x-axis of the viewer coordinate system requires finding the dot product of ‘Rf with this z-axis. The component of if on an axis parallel to the viewing direction is then evaluated as the cosine of a. which is used to simulate specular reflections. Phong states that interpolating RP. as is done for the normal vectors. would be a more time-consuming process. calculating these vectors directly requires less storage space as well. By calculating the shading values from interpolated normals. a better approximation of the curvature of the surface 50 is obtained and highlights are more accurately simulated. Unfortunately. the Nachrband effect is not completely eliminated because a continuous derivative of the shading function across polygon edges is not guaranteed; subjective brightness along abrupt changes in orientation of adjacent polygons will be visible. This is inevitable because. according to the Inch-band effect. it will be visible at abrupt changes in the slope of the intensity distribution curve regardless of whether or not the first derivative of the curve is continuous. Phong tried using higher-degree interpolation schemes and the effect was still visible. Furthermore. the images produced differed very little from those produced by the method presented here so the latter was determined a better technique because it uses less time and may be implemented in harduare. However. this method did produce a marked improvement over Gouraud's algorithm for simulating smooth shading. although it requires more than three times the hardware to implement and a slight increase in execution time; but Phong feels the improved quality is worth it. The next shading algorithm improves on Phong's method by not using any empirical adjustments in the shading model. 3.3 Blinn Normal-vector Interpolation Shading In this algorithm [3]. published in 1977. James F. Blinn uses a theoretical shading model derived by K. E. Torrance and E. I. Sparrow. Blinn does not actually present an algorithm to implement the shading model but applies his model to existing algorithms then compares his images generated to those from Phong's algorithm. Blinn's experimental results generally match those from Phong's algorithm but some differences arise. 51 Blinn's shading model simulates highlights more accuractely because it uses a theoretical model whereas Phong's shading model includes some empirical adjustments. One of the two main differences is that the amount of specular reflection varies with the direction of the light source. The second main difference is that the direction of the peak specular reflection does not always coincide with the direction of reflection. R. where the angle of the reflected light with the surface normal equals the angle of the incident light. Blinn's algorithm assumes that the surface is composed of a collection of mirror-like microfacets that are oriented in random directions. The specular component of the reflected light is assumed to come from facets that are oriented in the direction of maximum highlights. E. If the surface was a perfect mirror. light would only reach the viewer if the surface normal bisected the angle between the directions of the viewer and of the light source. This required direction of the normal is'H and can be defined + + idl‘fl | (21) l“ I F5 rd The diffuse component of reflected light results from multiple reflections between the facets. and from internal scattering. The Torrance-Sparrow shading model implemented combines four factors to generate the shading intensity: nor (Ni?) s a (22) where D is the distribution function of the facets' orientations. G is the amount by which the facets shadow and mask each other. F is the Fresnel 52 reflection law. and (NiV) is the cosine of the angle between the surface normal and the viewer. All vectors are assumed normalized. Each of these terms will be discussed more fully in turn. Light will be specularly reflected only by facets posessing a local normal vector which points in the direction of ‘H. The distribution function. D. evaluates the number of facets pointing in this direction. Several different distribution functions have been proposed. Phong uses a cosine function raised to a power as presented previously except instead of measuring the angle between the directions of the viewer and the reflected light. the angle 8 is measured between the average surface normal and 'H of each facet to conform to Blinn's representation of the surface using microfacets. This angle may be defined as B - cos-1 (N‘H). (23) Blinn's version of Phong's distribution function becomes 01 - cosc‘ p (24) The distribution function used in the Torrance-Sparrow model is a standard Gaussian distribution: -( )’ D3 3 ° 3 cs (25) where D: is the proportionate number of facets whose local normals form an angle 8 from the average surface normal. The factor ca is the standard deviation for the distribution which is a property of the particular surface being modeled; c, is large for dull surfaces and small for shiny surfaces. A third distribution function has been proposed by T. S. Trowbridge and 53 K. P. Reitz which generates a very general class of surface properties by modeling the facets as ellipsoids of revolution: D, s (26) cos' B (c,' - l) + 1 where c, is the eccentricity of the ellipsoids. c, is O for very shiny surfaces and 1 for very diffuse surfaces. Each of these distribution functions peaks when the value of the cosine term is 1. which is when facets point along the average surface normal so that 8 is 0. As 8 increases or decreases the values of the functions decrease at rates that are controlled by the values of c1. c, and c,. Blinn used a uniform angle. u. at which the distribution falls to one half to compare the functions. In terms of u the three controls become l 2 c1 :- - __n__ (27) ln cos a (ln 2)"‘ ca s —— , (28) e cosa u - l 0.8 (29) c a . ’ cos' n - (2)°-‘ Although similar plots are obtained of the functions for equal values of o. Blinn uses D; for his shading model because it has experimental as well as theoretical justifications. and it is the easiest to compute. If a does not change within a frame. D, can be calculated using intermediate values calculated once per frame: 11 - 1 / (c,’ - 1) (30) k, - k1 + 1 (31) 54 Using equations (30) and (31). D, becomes D, - ’ (32) 8 cos 8 + k1 This speeds up the computation of the distribution function. Tb simulate surfaces of varying shininess. c, changes from place to place on the surface and D, must be normalized. In equation (26) D, is normalized so that D,(0) . 1. If e, varies across the surface. a constant normalizing factor must be used that is based on the minimum value of c. over the surface: c, - c.1n + (1 - c.1n) t(u.v) (33) where t(u.v) is the texture value. The texture-modulated distribution function is: °min °3 D, a (34) cos' 8 (c, - 1) + 1 The second factor in the specular reflection model measures the degree to which the facets shadow each other and is called the "geometric attenuation factor". G. G ranges in value from O to 1 and represents the proportion of light from the source that reaches the viewer after the shadowing takes place. An assumption is made that the microfacets are V-shaped grooves with the sides at equal but opposite angles from the average surface normal. Only grooves where one of the sides has a local normal in the direction of‘H contribute to the highlight. Three cases may arise for different positions of the light source and viewer; these are illustrated in Figure 3.6. Note that L and V'do not necessarily lie in the 55 ' plane of the figure which contains H and N. For case (a) of Figure 3.6. G is 1 since the light rays are not blocked by other surface facets. To compute G for cases (b) and (c) the proportion of the facet contributing to the reflection must be calculated. This is the ratio 1 - (m/k) as shown in Figure 3.7. By projecting the vector V or the vector ‘L onto the plane containing 'N and H. the problem is reduced to two dimensions. Applying the law of sines and several trigonometric identities. the ratio is determined for cases (b) and (c) in terms of the vectors N. H. V. and E: c = 1 - lk .. - _ 35 b " (v-n) ( ) 2(fioi) (fi-T.) 2(fi-i) (N-I.) G6 = 1 - m/k I . (36) (Li) ('V-i) The value of G will be the minimum of 6‘. Oh and Ge' The next factor in the shading model is the Fresnel reflection. F. which determines the actual amount of incident light reflected from a facet as opposed to being absorbed. F is a function of the index of refraction. r. of the substance and the angle of incidence. O. which is defined in this case as O = cos.1 (L-H) = cos"1 (V'H). (37) Thus the Fresnel function is given by sin3 (0 - 1) + tan3 (0 - 1) sin’ (9 + 7) tan’ (6 + 1) F = 0.5 (38) where sin sin 0 8 7 . 56 and viewer with no Figure 3.6a: Positions of light source interference [3] 57 —> 2| El fil Figure 3.6b: Positions of light source and viewer where some of the reflected light is intercepted [3] 58 9 2H 3| <| 4 Figure 3.6c: Positions of light source and viewer where some of the incident light is masked off [3] 59 Figure 3.7: Proportion of facet contributing to the reflected light is 1 - (m/k) [31 60 For metallic substances r will be large in value and F(O.r) is nearly constant at 1; for nonmetallic substances r is small and F has an exponential appearance beginning at 0 for O - O. and reaching 1 at O - 90'. If the light source and the viewer are assumed infinitely far away. the light rays reaching the viewer will be parallel and L and V will be constant vectors. This means that the calculations of the directions of L.‘V and H and of (75H) need to be performed only once per change in light source direction. Using some trigonometric identities. F. too. only needs to be calculated once using the equation (39) F _ (g - j)‘ 1 + (j (g + j) - 1)‘ (g + i)’ (j (g - j) + 1)‘ where j. (V'i) and ' II (t: + 1’ - 1).... This helps reduce the computation time. The final factor in the shading model is the division by (N‘V). Since the viewer sees more of the surface when it is tilted. more facets with local normals in the H direction will contribute to the intensity of the specular reflection. The increase in area seen is proportional to the cosine of the angle between the average surface normal and the line of sight. thus explaining the presence of this term. Combining this term with the computation of G. it is possible to avoid a division by zero by making some comparisons to find the minimum of G.. 6b and Gc before doing the divisions: If (N°V) ( (N-L) then If 2(fi-V) ('fi-i) < (TI-i) then 61 G:- 203-?!) I (TI-i) else G:- 1 I (N-V) else 11 2(‘fi-i) (fi-i) < (V-i) then G:- 2(N-H) (N-L) /(V°H) (NW) else G:- 1 / (TV-V.) This also helps speed up the computation of the highlight function. Comparing this highlight function to the one Phong used. Blinn notes that for small angles of incidence. the two are very similar. However. the intensity of the highlight and its direction differ for large 0. thus the differences are most noticeable for edge-lit objects. Also. Phong's model does not simulate nonmetallic objects as well as Blinn's does. Because D, is easier to compute than D,. the savings in computation time offsets the extra time required to generate G and F so Blinn claims there is no overall increase in computation time yet the degree of realism is increased. The next section presents an algorithm which uses the method of half-tones described in Chapter II to generate shaded images. 3.4 Newell-Sancha Half-tone Shading Although the authors claim this is a half-tone algorithm [23.24]. I. E. Newell. R. G. Newell and T. L. Sancha do not disclose the specifics on how the half-tones are implemented. However. the algorithm. published in 1972. is significant because it is one of the early attempts at simulating transparent objects. The algorithm also uses a different method to generate the information about the objects being modeled; images are created by 62 calculating the shading values per polygon in order of decreasing distance from the viewer instead of on a scan line basis as with the previous three algorithms. The basic idea behind the Newell-Sancha hidden-surface algorithm is to order the polygons or patches in order of decreasing distance from the viewplane then to paint the object face by face. overlapping any existing faces thereby covering hidden surfaces. If conflicts arise where the faces cannot be properly placed in order. perhaps due to cyclical obscurings or intersections of faces. faces are split to attempt to resolve the problems. thereby increasing the total number of faces composing the object. The faces are painted into the image memory. which they call a screen map. then the information is processed again according to scan lines before being displayed. The shading function is performed during the painting of the faces to the image memory. The model used has a diffuse. an ambient and a specular component. The diffuse component is the cosine of the incident angle. 0. raised to the power s and multiplied by a coefficient. Cd. which is the intensity range. s is an arbitrary power; when s - 1. the function simulates diffuse reflection. As a increases. the object appears darker except for a few faces which appear at the brightest intensity; this gives the effect of a shiny black surface. The ambient component. 8 is a ,. constant representing the ambient level of lighting. The specular component is used in particular to simulate longitudinal reflection patterns of bottles or other objects of revolution and has the form of the sine of the incident angle raised to a high power. i. and multiplied by the specular intensity range. C Thus. the shading equation becomes 63 S = Cd cos‘ 0 + S, + C, sin1 0. (40) Transparent materials can be simulated by slightly altering the painting routine. 'hen the new surface being painted is transparent. instead of simply replacing the previous shading value of the old face covered by this new surface with the new face's value. the shading value stored is a combination of both the old. So. and new. Sn. shading values. A comparison is made between the old and new values and depending on the outcome. the resulting shading value is a weighted sum of these two as follows: If Sn ( So; 8 - w Sn + (l - w) 80 (41) If s, > so; 3 .. s (42) where w is a weighting factor. Newell. et al. claim that these functions are not an attempt to simulate the real world but can considerably enhance the appearance of the images produced. Although the effects of' transparency are simulated. no provision is made for the effects of refraction which are apparent through many transparent objects. Also. they feel that "the time taken to produce an image precludes the possibility of using shaded pictures in a truly interactive way". Their second paper. [23]. presents ten figures of images produced with their algorithm. They compare the complexity of each figure and the time required to produce the image. The entire algorithm is broken into four parts with the third being the writing of the fragments to the image memory. which includes the performance of the shading function. They list times for this part ranging from 1.4 to 33.4 seconds. However. it is 64 not known exactly how much of these times was spent on the shading alone. Regardless. pictures of images generated using this method which were included with the paper greatly exhibited contouring effects. The next section presents an algorithm to generate images using the method of ray tracing described in the last chapter. It simulates the effects of both transparency and refraction as well as shadows and light reflected from object to object within a scene. 3.5 'hitted Ray-tracing Shading In this algorithm [35]. published in 1980. Ihitted incorporates a technique known as ray tracing. The algorithm is based on a hidden-surface algorithm that produces ”trees" of global information for each pixel of the display. The trees are formed by tracing light rays from the viewer to the first surface encountered. then tracing the components of reflection and refraction from the first surface to the next until reaching a light source. Shading is then performed by traversing the tree to determine the light intensity received by the viewer. The hidden-surface algorithm does not perform the usual functions of clipping and removal of faces hidden to the viewer; these may be visible as reflections on other objects within view of the observer. Rays are traced from the viewer to the first surface to the next surface and onto the last surface before reaching the light source; therefore. objects not included in the view may affect the lighting of visible objects. The ray tracing is performed by calculating the intersection of an incident ray of light with a reflecting surface. Since the rays are traced 65 from the viewer. the direction of the incident ray. L. coincides with the direction of the viewer. ‘V. for_the first surface. The incident ray is broken into two components: the reflected light in the direction of 'R and the light transmitted through the surface in the direction of T. The R direction follows the rule that the angle of incidence equals the angle of reflection as established in previous sections. The direction of the transmitted light. T. obeys Snell's law of refraction. Thus. R and T‘ are functions of N and V given by _ v V' - ‘27 (43) lv-Nl ii - ‘v" + 274' (44) T-k,(‘fi+v')—'fi (45) where 1,. - (t; I‘v'l’ - IV' +fil‘)"-‘ and kn - the index of refraction. These equations assume that (ViN) is less than zero so‘N must point to the side of the surface that from which the ray is incident. Likewise. kn must be adjusted to account for the change. If the denominator of k, is imaginary. T is assumed to be zero because of total internal reflection. The intersection process is performed recursively until all branches of the tree are terminated. These relationships are pictured in Figure 3.8. Figure 3.9 shows how the rays are traced from surface to surface with Figure 3.10 showing the tree formed from the components of light reaching the viewer from point P in Figure 3.9. The shading model used by Ihitted is dependent on the vectors generated by the hidden-surface removal algorithm. namely. N.‘R and T. It includes a 66 EA? E E V Reflecting Surface ..-Ai kf(N+V') Figure 3.8: Geometry of reflection model for Whitted's algorithm [35] 67 I __ Surface 2 S2 N2 S1 N1 V Surface 1 P If Figure 3.9: Paths of reflected light that reach the viewer [35] 68 V Figure 3.10: Tree formed from components of light reaching the viewer from point P of Figure 3.9 [35] 69 constant representing the ambient reflection. 8,. and terms for the diffuse and specular reflections and the transmitted intensity. The diffuse component ideally would include contributions reflected from nearby objects as well as light from all of the sources. These contributions would simply add together to form the total diffuse reflection. However. the computation required to sum components from other objects in the scene would be too extensive so a diffuse componhnt similar to that used by Phong is implemented which only accounts for the sources. Assuming that N and L are normalized. the diffuse component becomes their dot product multiplied by the diffuse reflection coefficient. Cd. The complete equation for the shading model is S - S, + Cd (N‘L) + C, R + Ct T (46) where C, and Ct are the specular reflection and transmission coefficients. respectively. R is the intensity of light incident from the R direction and T is the intensity of light from the T direction. Although the coefficients C, and Ct were held constant to generate the pictures included in 'hitted's paper. more accuracy is obtained by making them functions incorporating the Fresnel reflection law; the coefficients would then vary as a function of the incident angle in a manner depending on the properties of the surface being displayed. Instead. they must be chosen to correspond to physically reasonable values to generate realistic pictures. As the tree from the hidden-surface algorithm is traversed. shading intensities are calculated at each node using this model. The intensities are then linearly attenuated as a function of the distance between the nodes. The linear function is used because it provides a good approximation of the effects of distance; for 7O non-planar surfaces the square-law approximation does not apply. lhen modeling surface properties. if the value of C. 1. decreased and that of Cd increased. the surface will appear less glossy but the highlight will not spread out realisticly as it did for Phong's model whenever the specular exponent was reduced to simulate less smooth surfaces. To improve the highlights generated. a random perturbation is added to the surface normal to simulate the randomly oriented microfacets of a rough surface. thereby assuming a surface modeled in the manner described by Blinn in section 3.3. If the surface is smooth and shiny. the perturbation has a small variance; rough surfaces necessitate using larger variances. This method will also give transparent objects a frosted appearance by using larger variances. But because this method requires a great amount of extra computation. it is avoided whenever possible. One such case is when specular reflections are caused directly by a point light source. where Phong's model of specular reflections can effectively be used at the point of reflection. Shadows may be simulated using this algorithm by extending the trees from the hidden-surface algorithm to include rays associated with light sources at each node. If one of these rays intersects a surface before it reaches the source. the point of intersection represented by the node lies in shadow with respect to that light source. This source will not contribute to that point's diffuse reflection. thus creating a shadow. The pictures included in Vhitted's paper were created using a VAX-ll/780 and are probably the best generated by any of the algorithms thus far. However. they required between 44 and 122 minutes to be processed. For simple pictures 12 percent of the processing time is attributed to just 71 the shading with the majority of the time needed to compute the intersections in the hidden-surface removal algorithm. Some shortcomings of the algorithm is that it does not provide for diffuse reflections from distributed light sources. nor do specular reflections degrade gracefully as surfaces get less glossy. Ihile this algorithm was able to shade objects modeled by both polygon-mesh and curved-patch representations. the next section presents an algorithm designed specifically for curved patches. particularily a class known as the bicubic patch. 3.6 Catmull Bivariate Surface-patch Shading This algorithm [6.7] was developed in 1974 by Edwin Catmull. The method was primarily developed for objects modeled using a class of curved patches called bicubic patches but is not limited to them alone and can be applied to other kinds of surfaces as well. The algorithm is based upon a subdivision procedure which divides the patches into subpatches. After the subdivisions are accomplished. hidden-surface removal and shading functions are performed. Four different methods to determine the shading values are discussed. Catmull feels that bicubic patches are better for modeling objects to be displayed. The polygon-mesh technique produces unrealistic effects such as a faceted appearance caused by contouring and jagged silhouettes formed by straight-line segments. Also. quadric curved patches do not provide enough degrees of freedom and are therefore unsuitable for modeling many objects. Bicubic patches are easily joined with slope continuity across the 72 boundaries so they produce continuous shading and smooth silhouettes. And as mentioned. the basis of Catmull's algorithm is the subdivision algorithm and this process can be performed quickly using bicubic patches. The subdivision algorithm divides all patches into subpatches until each subpatch's projection represents only a single pixel on the raster display. This is done by joining the midpoints of opposite sides of the patch. thus dividing it into four subpatches. Eventually the patch will appear as in Figure 3.11. Subpatches which do not cover any pixels are associated with the nearest subpatch covering a pixel or sample point. Clipping is performed during this process to determine if a subpatch will be on the screen before dividing it any further. Overall. the number of subdivisions required is slightly greater than one third of the number of pixels covered by the original complete patch. According to Catmull. the subdivision of each bicubic component requires thirty additions with values passing through four adders; it is best to have a subdivider for each of the three bicubic comoponents to work simultaneously and reduce the total execution time required. When the subdivisions are completed. hidden surfaces are removed then a shading value is assigned to each pixel and accordingly. to each subpatch. Cannull sites four methods to determine the shading value for each pixel. The first shading method can be any of those mentioned in this text which uses the surface normal to calculate the shading intensity. However. since the equation of the normal to a bicubic patch is a fifth degree polynomial. it is difficult to find. A fifth degree subdivision equation could be used to solve the normal equation but this is impractical so Catmull used the following method to generate the pictures in his paper. 73 Figure 3.11: Patch subdivided so that no subpatch covers more than one sample point [7] 74 The normal equation is approximated with a cubic equation. Its components are then subdivided along with the components of the patch equation to obtain approximate normal equations for the subpatches. The patch and normal equations are functions of two variables. u and v. The notation for the x-component is x(n.v)=U llx V (47) where U and V are matrices defined as u - [n' u' u 1] (43) V I [v3 v3 v 1]T (49) and I: is a four-by-four matrix of coefficients defined as b q ‘11 ‘11 ‘11 '14 ‘11 'ss ‘21 ‘14 x a,, a,, a,, a,, (50) ‘41 ‘42 ‘41 ‘44 L - The derivative of the xrcomponent in the urdirection is given by xu - 0' III V (51) and the derivative in the v-direction is defined as xv - U I! V' . (52) The normal vector. [xn yn an]. is found by forming the cross product of the tangent to the surface in the urdirection. [xn yn zn]. and the tangent in the v-direction. [xv yv ‘vl' Thus. the normal components are defined as xn(u.v) yn(u.v) and xn(u.v) To find the approximate components of the normal 75 3 U' I, V U I: V' - U Iy V' U' I, V . - 0' II V u I, v' - u I, v' 0' I1‘ v 0' I1 v u I, v' - a II v' u' Iy v . requires (53) (54) (55) a similar matrix multiplication for each component as shown for only the x-component: x - c Px cT where C is the Coons matrix defined as and where -3 3 -2 -1 O 0 1 0 l O 0 OJ — I 2 -2 1 1‘ xn(0.0) xn(l.0) dxn(0.0) du dx (1.0) dun xn(0.1) xn(1.1) d (0.1) 4:“ dx (1.1) dun dxn(0.0) dv dxn(1.0) dv d ‘(0.0) diav d ’(1.0) d:3v d (0.1) i 4:“ d (1.1) .3“ a: ’(0.1) dvav dx ‘(1.1) dvav J (56) (57) (58) 76 dxn(u.v)/du 3 U" I, V U I, V' + U” I, V U' N, V' - u' I, v' u' I, v - u I, v' u" I, v (59) dxn(u.v)/dv = U' I, V' U I, V' + U' I, V U I, V" - u I, V" n: I, v - u I, v' u' I, v' (60) d'xn(u.v)ldudv - u" I, v' u I, v' + u" I, v u I, v" + 0' I, v' u' I, v' + u' I, v u' I, v" - u' I, v" u' I, v - u: I, v' u: I, v' - u I, v" u" I, V'- n I, v' u" I, v'. (61) The equations for the y- and z-components are similar and can be found by comparing equation (52) with equations (53) and (54) to derive similar equations as (55) and (57) through (60) for the other components of the approximated normal vector. A second method to find the shading values is to use an intensity function. This associates numbers with the pixels as derived by a function. The function could be based on anything such as pressure. strain. height. density. artistic whim. etc. Some checks must be used to stay within the bounds of the display as described in [7]. The third method is to map a picture to the surface. This is done by forming a one-to-one correspondence between either the pixels covered by the patches and the intensities of the picture or between areas of the picture and entire patches. The intensity of the picture could be a function of u and v as is the patch. The function or area is divided as the patch is to maintain the correspondences. One problem that may occur is a sampling problem. If the the picture contains more intensity values than the patch 77 has pixels. all of the information in the picture will not be displayed on the patch. In the area-mapping method the sampling problem is less noticable because the average intensity of the area is mapped to the subpatch. however. the problem is not eliminated. The forth and final method to calculate the shading values is to modify the intensity for effects such as shadows or transparency. Another method must be used to find the initial intensities then this method adjusts the values. A method similar to that of Newell. et al. is used for displaying transparent objects. Shadows are created by using "shadow-patches" formed from the silhouette of an object from the point of view of the light. After determining which portions of the object are behind these patches. the shading values of the shadowed portions are attenuated. One problem is that this method merely diminishes highlights rather than eliminating them. Several pictures generated by this method were included in both of Catmull's papers. Times to produce the pictures ranged from 115 seconds to 15 minutes. It was not disclosed exactly what portion of the time was required to generate only the shading values. Despite the complexity of many of the pictures. they were very realistic. The next section presents a shading model that utilizes the different characteristics of various materials to display how they reflect light more accurately to achieve more realistic images. 3.7 Cook-Torrance Reflective Nodel for Shading This model [10]. published by Robert L. Cook and Kenneth E. Torrance in 1981. is a reflectance model for shading computer images with emphasis on 78 generating color images. It is based on geometrical optics like most of the previous algorithms but is applicable to a broader range of materials. surfaces and lighting situations. Here. the intensity of the reflected light is determined by the intensity and size of the source. and by the object's reflecting ability and surface properties. The spectral highlights are determined by the spectral composition of the source and the wavelength-selective reflection property of the surface. Like the previous algorithms. this shading model uses the vectors N. V. ‘L. and ‘H. where all are normalized and defined as in previous sections and shown again in Figure 3.12. Note that the angles between 'H and the two vectors 4V and 'L are defined as g. and that these three vectors lie in the same plane; N is not necessarily contained in that same plane. This model also derives its specular component in a similar manner as Blinn's model and depends on the description of a surface as being composed of randomly oriented microfacets. Unlike any previous algorithm. this model determines the energy of the incident light as expressed as energy per unit time and per unit area of the surface. lost non-mirror surfaces reflect the incident been over a wide range of angles. thus. the reflected intensity in any given direction depends on the incident energy and the incident intensity. The intensity of the incident light is expressed in a similar manner to the energy but is per unit projected area and per unit solid angle. The energy of an incident beam of light. Bi' is given by E, - I, (fi-E) u, (62) where Ii is the average intensity of the incident beam and ”i is the solid 79 Figure 3.12: Geometry of reflection model for Cook and Torrance's algorithm [10] 80 angle of the beam. Unless the surface is a perfect mirror. the incident light will be reflected over a wide range of angles. Each light source is associated with e bidirectional reflectance. 2b. which is the ratio of the reflected intensity in a specified direction to the incident energy from another direction both within a small solid angle. Rb is given as s _ _ 63) '1. E, ‘ where S is the reflected intensity or shading value that the viewer sees from each light source and is given by s - I, a, - I, 1, (Ni) 6, (64) Rb is a linear combination of two components. The diffuse component. Rd. is from either internal scattering where the incident light penetrates the surface or from multiple surface reflections such as from a rough surface. The specular component. R is from light that is reflected at the surface '0 of the object. If the object being modeled is not composed of a homogeneous material. these two components may have different colors. If d is the fraction of reflectance that is diffuse. (l - d) is the fraction of reflectance that is specular and Rh is given by Rb I d Rd + (l - d) R,. (65) The light reflected toward the viewer from ambient light. when integrated over the entire hemisphere of illuminating angles. can be defined by a hemispherical-directional reflectance. R,. which is an integral of Rb and. therefore. is a linear combination of Rd and R,. R, is assumed 81 independent of the direction of‘V and the ambient light is assumed uniformly incident. The reflected intensity due only to the ambient light. 8 is given by .9 sa ' Ra Ii.a f (66) where 11', is the intensity of the incident ambient light and f is the fraction of the illuminating hemisphere that is not blocked by other objects. given by r 11611:) (67) 8— O 0 n i where the integration is performed over the unblocked portion of the illuminating hemisphere. Hence. the total intensity of the light observed is the sum of the reflected intensities from all of the light sources plus any reflected intensity from the ambient light. 'ith f I l. the shading model is defined ‘8 s - I,” n, + 21 11.) (ii-f.) “1.1 (d n, + (1 - d) 3,). (68) This equation takes into account light sources with different intensities and projected areas. For instance. if two incident beams have the same intensity and incident angle but one has twice the solid angle as the other. the first will make the surface appear twice as bright as the second will. Similarily. if an incident beam has twice the intensity but the same incident angle and solid angle as a second beam. the first will make the surface appear twice as bright. However. the model depends on several variables. For example. the intensities depend on the wavelength of the 82 light. d depends on the material composing the object and the reflectances depend on these variables in addition to the reflection geometry and the surface roughness. Directional dependence only affects the specular component. R,. since it relies on the location of the viewer. Similar to Blinn's model. this component can be defined as F D G R,I _._ _- . (69) n (N-L) (N-V) The terms G. D and F have the same meaning as they did in Blinn's model but their equations are defined differently. G is the geometrical attenuation factor which accounts for the shadowing and masking among the microfacets. It is defined as { 263-3) (ii-Tn 2(i-i) (74.1)} G I min 1. (70) (v-i) ' (‘v-i) D represents the the fraction of facets that are oriented in the direction of ‘H. Cook and Torrance consider the Gaussian model proposed by Blinn in equation (24). but also a model developed by Petr Beckmann and Andre Spizzichino for rough surfaces 1 -[tan‘ 8 / ma 1 n=-—,————,——. . (71) n cos B where m is the root-mean-squsre slope of the facets. which controls the spread of the specular component. If m is small. the surface will appear smooth and the distribution of the specular component from the facets will be highly directional around the vector E. If m is large. rough surfaces are simulated and the specular component will be more spread out. Comparing this model to Blinn's of equation (24). the differences are very slight. 83 The advantage of this function is that it gives the absolute magnitude of the reflection without introducing any arbitrary constants; however. it requires more computation. Ihen objects have two or more different surfaces of different roughness. the distributive functions will have different slapes m. The overall D can be expressed as a weighted sum of the respective distribution functions: 1) - E v, D(mj) (72) J , where v, is the weight of the 1“ distribution function. The IIII of .11 the weights must equal 1. F is the Fresnel term which describes how light is reflected from each microfacet. It is a function of the incident angle. t. and the wavelength of the light. A. F. as well as the other reflectances Rd and 3,, may be obtained from the reflectance spectra for the material. This information has been measured for many materials. usually for illumination at normal incidence. and tabulated. The measurements were made for only a few wavelengths so the values may need to be interpolated. By multiplying the reflectance spectra for the surface by the spectral energy distribution of the incident light. the spectral energy distribution of the reflected light is obtained. Since F and Rd also vary with the geometry of the reflection. Rd is taken to be the bidirectional reflectance for illumination in the direction nonmal to the reflecting surface. whereas F's directional dependence leads to a color shift when the directions of incident and reflected light are near grazing. The Fresnel equation expresses the reflection in terms of the index of 84 refraction. r. and the extinction coefficient of the surface. Co. and the angle of illumination of the microfacets. {. If r and C, are known. the Fresnel equation is used to find the spectral and angular dependence of F. If not. r is estimated by setting Co I 0 using an equation similar to Blinn's equation (39) except here is has an additional factor of 1/2: 1 ( - )’ ( ( + ) - 1)’ F - ' J [1 + J ' J J (73) 2 (t + i)’ (i (t - 1) + 1)“ where 1" (v.°i) and g 8 (1'3 +1, _ 1,9.5. This dependence of reflectance on wavelength and incident angle implies that the color of the reflected light changes with the angle t. The computation of this color shift is excessive so it is approximated from the spectral energy distribution. thereby approximating the RGB values for the color. Since all of the other algorithms have only dealt with intensities for achromatic displays. the procedure for calculating these values is not discussed. However. some important conclusions were drawn concerning the realism of computer-generated images. One conclusion is that nonhomogeneous materials may have specular and diffuse components of different colors. Plastics are one such material. The color of the specular component. which is reflected from the surface. is only slightly altered by the color of the incident light. depending upon the reflectance of the surface material. The diffuse component is of the color of the plastic alone. This is not the case with metallic objects. Reflections from metals occur almost completely at the surface. The specular component is still only slightly altered by the color of the light 85 source but if the surface is smooth. there may be barely any diffuse reflection. According to Cook and Torrance. most of the other algorithms create images of objects that appear to be made of plastic. Their model increases the realism of the images by simulating other materials. The next section presents a new method for modeling objects. particularily those that occur in nature such as mountain ranges. continent outlines and other objects with random surfaces. 3.8 Fournier-Fussell-Carpenter Fractal-surface Shading In 1982 Alain Fournier. Don Fussell and Loren Carpenter published a detailed discussion [14] of a new method to model objects. particularly for those that occur naturally due to the randomness of their surfaces. The method was derived from fractal mathematics techniques which were largely developed by Benoit Iandelbrot in the late 1960's. One of the methods presented by Fournier. et al. was implemented by Stephen L. Stepoway. David L. Iells and Gerald R. Kane in a multiprocessor architecture in a paper published in 1984 [30]. Fractal mathematics techniques are very useful to model non-deterministic phenomena such as terrains. smoke and clouds. Traditional methods for modeling such objects; i.e.. polygonrmesh or curved-patch techniques. do not generate realistic images of these types of objects. Even so. extremely large numbers of polygons or patches are necessary to reproduce the natural features. The use of texture-mapping. a technique which was discussed in both Chapter II and Section 3.6. is more effective for these types of objects but even this tends to have a repetitive 86 regularity not characteristic of the real objects. Thxture-mapping also has limitations to the detail that can be conveyed as the viewer is brought closer to the surface. Conversely. fractal mathematics can create the resolution required of a particular scene by continuing the texturing process to the extent necessary. The nature of the process is random enough to effectively model smoke. trees. rocks and other such objects yet can be controlled enough to follow a basic outline. such as the coast of a continent. The algorithm is similar to that presented by Catmull in Section 3.6. Both relied on a subdivision process to break the model into pieces which covered only a single pixel on the raster display then calculated surface normals to be used in the shading computation. In this algorithm the object is modeled at the start using a polygonrmesh technique where the polygons are all triangles. The description is coarse requiring just a few dozen triangles to give a general outline of the overall shape of the object; the algorithm provides the texture definition. The more triangles used at this phase. the more specific and controlled will be the object's definition. As stated the subdivision algorithm breaks the triangles into smaller triangles continuously until each triangle corresponds to only one pixel. The new triangles are somewhat noncoplanar. The midpoints of the edges forming a triangle under consideration hre moved a random distance from the edges in a direction related to the normal of the triangle. These new midpoints are joined to form a new triangle. Each edge of the new triangle is connected to a corresponding vertex of the original triangle to form three more triangles. In this manner each triangle is divided into four smaller triangles as illustrated in Figure 3.13. Some problems may arise if 87 B -——q Figure 3.13: Subdivision of a triangle [30] 88 adjacent triangles are processed simultaneously. If their shared midpoint is not moved to the same position. the surfaces will not meet at the common edge. This can be corrected by sharing information between the processors about the midpoint's new position so both will use the same placement. Another solution is to move the midpoint in the direction of the average normal of the two triangles sharing the edge; still the processors must share information about the midpoint's exact displacement along the average normal. Once the subdivision process is completed the shading values are determined from the shade of the original triangle and the orientation of the normals of the new triangles. The shading values may be obtained using any of the shading models mentioned in this chapter which uses the surface normal to calculate the value. Several pictures were included in the paper of Fournier. et al.. mostly depicting terrains. The effect was very realistic. No execution times were provided for the time required to generate the images; however. Stepoway. et al.. claim that fractal surfaces cannot be used in real-time applications because of the complexity of generating images. Nevertheless. the realism is impressive and fractal techniques have been used in movies such as ”Star Trek II". "VOl Libre” by Carpenter and ”Peak” by Mark Snilily. Overall. this chapter has presented a wide range of shading models and techniques to achieve realistic. computer-generated images. The next chapter will examine the time-space complexity of the algorithms and discuss the advantages and disadvantages of each. CHAPTER IV COMPARISON OF THE ALGORITHMS There are different criteria by which to judge the shading algorithms presented in Chapter III. One such standard is the realism of the images generated by the algorithm. Many of the algorithms build upon previous work in an attempt to enhance the realism of the final images. The shading process is closely related to the modeling technique and the hidden-surface removal algorithm implemented. The modeling technique provides the basic data about the surfaces of the object. The manner in which the hidden-surface removal algorithm processes this information determines how it will be aviilable for the shading algorithm and its reflectance model; most shading algorithms prefer a hidden-surface removal algorithm that processes the information scan-line by scanrline. Increased realism of the shaded images results from improvements in any of these three processes. It should be noted that because the images are produced from a numerical description of the objects. only approximate images of the subject matter will be attained. There are many factors which affect the realism of the images generated by the computer; such as the resolution of the screen. the number of intensity levels obtainable. the processing power available. and the lack of a visual feedback system. to name a few. Therefore. precise duplicates of the objects are not possible and a degree of desired realism must be defined. Generally. the algorithms presented in Chapter III are based on two modeling techniques. each with a modified version as well. and various 89 9O reflectance models. Gouraud's algorithm was presented for the polygon-mesh technique and relies on the data being processed in scan-line order. The polygon-mesh technique uses low-order equations which are easy to solve. and it does not restrict the class of objects that can be modeled. Though Gouraud's algorithm improves upon the constant shading algorithm by reducing contouring. it still exhibits Mach band effects. According to Catmull [7]. Gouraud's algorithm is difficult to use to generate highlights and the shading is affected by the orientation of the polygons in the picture. This last problem is due to the viewer and light source being at the same location and causes frame discontinuities for motion pictures. Despite these problems. Gouraud's images are acceptable and the algorithm has been implemented in systems as mentioned in Chapter III. Phong improved upon Gouraud's algorithm by maintaining shading continuity across the boundaries of the polygons. It still exhibits Inch band effects though not as noticably. However. Phong's reflectance model was based on some empirical adjusnments so Blinn applied a theoretical model which portrays highlights more accurately. Though Blinn's algorithm was applied to Phong's algorithm. it is a reflectance model so it alone is not dependent on the polygonrmesh modeling technique or scan-line ordering of processing data as is Phong's algorithm. Both of these algorithms produce images of better quality than Gouraud's. The Newell-Sancha algorithm. also uses the polygon-mesh modeling technique but it requires the data to be processed by area rather than scan-line because it shades entire polygons at the same time. Since no effort was made to shade continuously across the polygons' edges. this algorithm exhibits considerable contouring and the Hach band effect; and 91 thus. the images are not as realistic as those from the previous algorithms. Although this algorithm was an early attempt to display transparent objects. no effects of refraction are modeled. lhitted's algorithm could be applied to either polygon-mesh or curved-patch modeling techniques. It requires that the information about the objects be processed in the form of ray-tracing trees. The algorithm accounts for light sources within the scene being displayed and reflections between objects. neither of which were modeled in the previous algorithms. The images are very realistic but require large amounts of computations. and do not account for diffuse reflections from distributed sources; also highlights do not degrade gracefully as surfaces become less glossy. Catmull's algorithm created realistic images using a specific class of curved patches called bicubic patches. He claims polygons create silhouettes that are not smooth and quadric patches cannot model any arbitrary object. The algorithm divides the patches into subpatches no larger than the size of one pixel before performing the shading or hidden-surface removal processes; thus. the information is processed by pixels. Overall. the bicubics are high-order equations and are difficult to deal with. The subdivisions require large amounts of computations. 'orking at the pixel level creates aliasing problems not easily solved but eliminates the Mach band effect. Cook and Torrance presented a reflectance model independent of both the modeling technique and the manner in which the information is processed during the hidden-surface removal procedure. It relates the brightness of the object. as well as what it is composed of. to the intensity and size of each light source. Cook and Torrance feel that all of the previous 92 algorithms display all objects as if they were made of plastic. They use the information about the object's composition to determine exactly how light will be reflected to display more realistic images true to the material that composes the objects. They claim to do all this without increasing the overall execution time. The final algorithm presented in Chapter III explains a new modeling technique based on fractal mathematics. It is specifically developed for natural objects because of their non-deterministic nature. Using the previous modeling techniques on objects such as smoke. clouds or mountains. which do not have regular features or simple macroscopic structures. requires excessively large numbers of primitives. either polygons or patches. Fractals provide random texture and structure to objects modeled coarsely with planar triangles. Texture-mapping attempts this effect but is too regular because it repeats the pattern and therefore. appears unnatural. Another advantage is that fractals are not defined at a predetermined level of resolution so distant and very close scenes are still quite realistic. Also. the computational effort is proportional to the complexity of the images. Fractals can model deterministic objects. too. but the computations are more demanding than any of the previous algorithms. This concludes the comparison of the algorithms presented in Chapter III based on realism and other problems. such as implementation. Unfortunately. despite its importance. realism is a very subjective criterion. The most important criterion is the speed of execution so that the images are able to respond to inputs on a real-time basis. If the time required to generate successive images is too long. the image update rate will degrade causing flicker. The time complexity of the algorithms will be 93 analyzed in this chapter. The first section presents routines for standard functions. such as addition and multiplication. then analyzes them for their speed of execution. The hardware requirements of the processor model of the system are discussed based on these functions. These routines serve as subroutines for encoding the algorithms into functional-block representations in the second section and different architectures are applied to make the algorithms run more efficiently. The final section compares the algorithms based on the criterion of speed of execution. 4.1 Basic Routines and Processor Model as Standards for Comparison The purpose of this chapter is to analyze the execution times required for the shading algorithms. Some assumptions have been made about the processor model to isolate the amount of time required for the shading algorithms. First. the size of the memory is as large as necessary. Since the mapping of the memory is beyond the scope of this paper. no contention problems exist so the time required to access memory locations is assumed to be negligible. Also. the time to actually display the image on the screen is not considered. Lastly. there is no limit to the hardware available to implement the system. If four multiplications are performed simultaneously. four multipliers are available. This increases the cost of the system but reduces the speed of execution. Of course. other methods besides simply adding hardware are investigated. This is particularily true when computing an undetermined number of values; since the total hardware requirements are unknown. other architectures must be utilized to minimize the execution time. 94 The processor model contains the necessary hardware as described in the procedures that will follow. Nevertheless. some information is vital to the shading computations and the time necessary to calculate this information is discussed. Examples of such information include the determination of normal vectors for polygons and patches. extra processing of object models. and correlating data within the scene as with ray-tracing and some hidden-surface removal algorithms. The processor model is discussed in this section after the analysis of execution times for addition; subtraction; multiplication; division; square roots; exponentials; cosines; sines; inverse cosines; tangents; exponentiation; dot products; matrix products; vector addition. magnitudes and normalization; and summations as well as the determination of normals and midpoints. All numbers are assumed to be signed. two's-complement. fixed-point numbers that are scaled to values less than one. Although the system is a 32-bit machine. most of the values are only 16-bit with the higher precision provided for multiplication. Here n will be considered 16 and the system will be a 2nrbit system. Therefore. two successive multiplications may be performed before an overflow is likely to occur and truncation becomes necessary. As stated. the execution times of several functions and processes are analyzed in this section. These times will be used in the next section when the shading algorithms are transformed into functional-block representations. Many of the execution times for the procedures were calculated using the material from Hwang [20] and Shanblatt [29]. Most of these times are measured in increments known as A, which is the delay of a single NAND. NOR or INVERTER gate. This helps to keep the comparison independent of the technology used to implement the system. 95 The first procedure is addition. An n-bit. (up to 64 bits). Carry-Look-Ahead Adder. CLA. is used which produces an (n + 1)-bit sun. It is a two-level design based on 4-bit Block CLAs. The execution time reguired. AT. is 12 A,. For subtraction the subtrahend is complemented then is added to the minuend to form the desired difference. Complementstion requires 3 A, so the total time needed for subtraction is 15 A,. A Baugh-Iooley array multiplier is used to implement multiplication [2]. An nrbit multiplicand and multiplier will produce a 2n-bit product. The execution time required is based on the number of bits; AT' (4n + 3) A,. The next eight procedures are implemented with the OORDIC algorithm first developed by Vblder in 1959 [32] then later discussed by 'alther [33] and Lawitzke [21]; Walther provides a comprehensive discussion of how to implement the OORDIC algorithm for circular. linear and hyperbolic functions using either the rotation or vectoring modes which he calls a unified algorithm. The unit of OORDIC delay. Ac. is the result of n shifts and adds requiring 2n clock cycles where n is the number of bits in the result and each clock cycle is at least as long as AT for addition. Based on the CLA's execution time. Ac is appromimately 24n A One function implemented is '0 division. Generally. the dividend is at least n bits but no more than 2n bits in length and the divisor and quotient have n bits. Division is a linear function and is implemented using the vectoring mode. It requires one Ac or 24n A where n refers to the number of bits in the quotient. Most I of the seven remaining functions implemented with the OORDIC algorithm require feeding back the outputs and dividing out a constant term. The square root function is a hyperbolic function using the vectoring mode and 96 requires Ac and one division process or 48n A,. Exponentials are also hyperbolic functions but use the rotation mode. Two OORDIC delays are again needed so the delay is 48n A The cosine function is circular and uses the ‘- rotation mode. It also requires 2AC so that AT is 48n A,. The sine function is similar to the cosine function and requires the same delay. The inverse cosine is first evaluated by finding the inverse sine then using a trigonometric relation for the final result. The inverse sine is defined as si -1 I t nV’ --JL-- n 7 ‘ [(1—1‘)] (74) This function requires a multiplication. subtraction. square root and one division then the inverse tangent is evaluated using the OORDIC algorithm which uses one Ac. Then the arc cosine is evaluated using - fl _ cos ‘ 7 I 5-- sin 1 1 (75) which has a total time delay of (lOOn + 33) A The tangent function is ‘0 implemented by simultaneously calculating the sine and cosine functions and then dividing them. during which the constant terms cancel. The tangent Exponentiation is the last Cordic function and is b. requires 2Ac or 48n A,. evaluated using the identity for c I a (b ln s) e c I (76) Natural logarithms can be implemented with the OORDIC algorithm using 2 AC. Thus. the total delay will be (4 AC + 131) A, or 3203 A, when n is 32. Since the images are three-dimensional each vector has three components. Thus. to form dot products requires three separate multiplications which may be performed in parallel and two additions so the 97 delay is that of multiplication plus 24 A,. On the other hand. because of the bicubic patches discussed in Cbtmull's algorithm. some matrices are as large as 4 x 4. If matrix A is defined as m x c and matrix B is c x p. then as each row of A is multiplied by each column of B. c multiplications and (c - 1) additions are necessary. However. the multiplications can be completed simultaneously. If c I 4. the number of addition delays can be reduced to two by finding the sums in parallel according to the recurrence computation array. also called tree reduction. shown in Figure 4.1. For all matrix multiplications performed in this paper c I 4 so the number of additions needed is two. But overall these operations are required mp times for the completion of the entire matrix multiplication procedure when performed separately. By using m processing elements. PEs. entire columns of the product can be calculated by each PE simultaneously. This reduces the total delay time to p (4n + 27) A, but substantially increases the hardware because each PE must have c multipliers and at least (c/2) adders with a maximum of c adders. Vector addition uses three parallel adders to sum the vector components separately and simultaneously. It requires the same delay as scalar addition. Determining the magnitude of vectors requires taking the square root of the sum of the squared vector components. The vector normalization process then divides this number into each component of the original vector. The former requires three simultaneous multiplications. two additions. and one square root while the latter additionally requires three simultaneous divisions. Thus the total delay to calculate the magnitude is (52m + 27) A and to normalize the vector is (76n + 27) A,. Summations are generated using recurrence computations as depicted in 98 ADDEND ADOEND ”Wm \/ \/. Figure 4.1: Addition array to sum four addends most expediently 99 Figure 4.1. This reduces the computation from (a - 1) addition delays. where a is the number of addends. to log, n. Thus. the total delay is 12 log, a A The minimum number of adders needed to accomplish this is ,. half the number of addends where each can send its sum directly to any other adder to expediently transfer data. The maximum would be equal to a with the adders arranged in an array with predefined data paths similar to that shown in Figure 4.1. Finding the normal vector of a planar polygon is done by calculating the cross product of any two adjacent sides. Since the equations for the sides of the polygons are not known. vectors in the same direction can be calculated by subtracting corresponding components of the endpoints; this requires three simultaneous subtractions for each vector or 15 A, overall. Then six simultaneous multiplications and three simultaneous subtractions are necessary to perform the cross product. The total delay. including finding the vectors. is (4n + 33) A,. The final procedure is to find the midpoint of linear line segments. The corresponding components of the endpoints are added needing three simultaneous additions and then each sum is split in half using three simultaneous divisions. The total delay is (24n + 12) A,. All of the execution times discussed above are tabulated in Table 4.1 for both the general case and when n is 32. They will be used in the next section while transforming the algorithms into functional-block representations. The hardware requirements now presented for this system are subject to change after the shading algorithms have been transformed. These requirements are based on the parallel operations performed to calculate the 100 Table 4.1: Summary of execution times for basic procedures Procedure Execution Time. AT AT‘Ihen nI32 3 Addition 12 A, 12 A, Subtraction 15 A, 15 A, Multiplication (4n + 3) A, 131 A, Division 24n A, 768 A, Square Root 48n A, 1536 A, Exponential 48n A, 1536 A, Cosine , 48n A, 1536 A, Sine 48m A, 1536 A, Arc Cosine (lOOn + 33) A, 3233 A, Tangent 48n A, 1536 A, Exponentiation 120n A, 3203 A, Dot Product (4n + 27) A, 155 A, Matrix Multiplication p (4n + 27) a, ‘ 155 p A, Vector Addition 12 A, 12 A, Vector Magnitude (52n + 27) A, 1691 A, Normalization (76n + 27) A, 2459 A, Summation 12 log, a A, ' 12 log, a A, Normals (4n + 33) A, 161 A, Midpoints (24n + 12) A, 780 A, 1- n is the number of bits in the numbers. 3- Matrix A is m x c. B is c x p. Function performed is A ' B. 3- a is the number of addends to be summed. 101 procedures discussed above. The majority of the hardware is necessary because of the vector computations that are performed. particularily the matrix multiplication. First. the consequences of using a 32-bit machine are discussed. As stated. the majority of the numbers are limited to only 16 bits but the system is capable of 32 to accommodate the larger products from multiplication. Adhering to these limitations means there are initially 16 bits to form values but the number of bits in the shading values is likely to increase since most of the shading algorithms require at least one multiplication. Thus. the number of bits used to calculate shading intensities provides a maximum of 2'3 intensity levels. Even though the values of x. y and z are limited to 16 bits. this limitation provides more than adequate screen resolution. Besides. the relationship between the screen resolution and the number of intensity levels available was discussed in Chapter II with the greater number of intensities favored over the higher resolution. For this reason even if these limitations did not allow for such high resolutions or vastly numerous intensity levels. they would not adversly affect the images generated. The most demanding procedure. in terms of hardware. is matrix multiplication. The recurrence computation was used for this procedure as well as to generate summations. Using the recurrence computation array to reduce the delay caused by the additions means needing from two to four adders per processing element because there are two possible ways to implement the recurrence array. The first is to use two adders which are capable of sending their sums to each other and themselves directly to avoid delays from transferring data. These sums are used as inputs for the next 102 addition. If there are four addends. as is the case with matrix multiplication. each adder receives two addends and forms a sum. Then one of the adders adds the two sums just produced to form the final sum. The second method of implementation is to use four adders in an array as denoted by the plus signs in Figure 4.1. The adders of the first row compute their sums then send them to the adders in the next row as designated by the lines marking the data flow pattern. The direction of the data flow is predetermined and is static so this hardware is dedicated whereas the data flow pattern of the previous method is programmable so a single addition can easily be performed. The advantage of this second method is that if the number of addends used as inputs to the summation is greater than four. this method lends itself readily to pipelining; four addends could be applied to the first row of adders after one addition cycle while the final sum of the previous four is being calculated by the second row. However. the matrix multiplication procedure requires four of the recurrence arrays so large numbers of addends can be efficiently summed using all four arrays. Thus. using the first method requires less hardware and the advantages of the second method are still retained. Overall. the matrix multiplication procedure needs eight adders. two for each processing element. It also needs 16 multipliers. four for each processing element. The quadruplicate hardware demands cut the execution time to one quarter of that without the extra hardware. Vector normalization and cross products require three simultaneous divisions and hence. three dividers. The process of determining vectors from polygon vertices to use for the cross products requires six simultaneous subtractions. Since there are already at least six adders 103 because of matrix.multiplication. only six complementor circuits need to be added to the hardware list. And lastly. the OORDIC algorithm requires a shift register. Since three dividers are needed. the OORDIC circuitry is tripled. This concludes the hardware requirements of the basic routines discussed above. Besides the assumptions stated at the beginning of this section. no other demands are made of the processor model at this time. Nevertheless. if some of the procedures are performed in parallel to speed the execution of the shading algorithms. more hardware may be necessary. Methods to reduce the execution times of the algorithms are investigated in the next section of this chapter. along with their impact on hardware requirements. The algorithms are transformed into functional-block representations using the processes described in this section as basic building blocks. 4.2 Functional-block Transformations of the Algorithms In this section the shading algorithms presented in Chapter III are transformed into functional-block representations using the routines analyzed in the previous section as the functional blocks. One problem with performing a time analysis on these algorithms is due to the relationship between the object-modeling technique. the hidden-surface algorithm and the shading algorithm implemented. Because the overall appearance of the shaded images can be improved by introducing changes to any of these three areas. one cannot simply analyze the shading algorithm alone. For this reason improvements to the object-modeling technique and the hidden-surface 104 algorithm are also transformed to functional-block representations when deemed that they are critical to the operation of the shading algorithm. These times must be considered along with the actual shading algorithm execution time during the time analysis. Another problem with comparing the algorithms is that each makes different assumptions. For example. most of the algorithms assume that the normal vector to the polygon is known before performing the shading but Catmull carries out an extensive approximation of the normals. Gouraud and Newell. et al.. claim to know the incident angle and calculate its cosine directly whereas Blinn. Ihitted and Cook. et al.. know the vectors for the viewer and light source's directions and use dot products to determine the cosines of their angles with the normals. On the other hand. Phong approximates the cosine of the angle for the specular component directly from the normal but still uses a dot product for the cosine of the incident angle. Blinn approximates the direction of specular reflection and its angle with the normal but Cook. et al.. assume they are known while the other algorithms do not utilize them at all. Catmull and Fournier. et al.. do not implement their own shading algorithm so they make the same assumptions of the shading algorithm used. Cook. et al.. and Ihitted are the only algorithms that demonstrate the additive property of different light sources. Yet. the impact of these assumptions is not always noticeable. To calculate the normal for planar polygons requires much less time than to carry out the approximations of normals for bicubic patches. Therefore. the planar-polygon normal calculation is nearly negligible in comparison. The additive property associated with multiple light sources is applicable 105 across the board so it is ignored. For Phong to approximate the cosine is only one gate delay greater than using a dot product. However. for Newell. et al.. and Gouraud to directly calculate the cosine takes almost ten times longer than performing the dot product so some advantages are gained here that will be considered during the final analysis. After each algorithm has been transformed. it is applied to the simple image of Figure 4.2. The figure depicts a raster of pixels with an object modeled having six surfaces. Three of the surfaces are hidden from the viewer and are drawn with dashed lines. Note that point G is located behind point A and each raster point is represented by its corresponding visible and hidden surfaces. The algorithms are applied to this object while assuming only one light source as a standard for the time analysis. The last section of this chapter summarizes the time studies of the next eight subsections. 4.2.1 Gouraud Transformation This algorithm is presented in Section 3.1. The shading value is interpolated across patches or polygons to give the appearance of smooth. curved surfaces. Although Gouraud presented his algorithm for objects modeled using Coons patches. it is analyzed as applied to polygons. Gouraud assumes that the viewer and light source are at the same location and thus. both make the same angle. 0. with the normal to the surface. The shading value is calculated at the highest and lowest points of the edges of the polygons. (the vertices of the polygons). during the hidden-surface removal algorithm 106 Figure 4.2: Image to be shaded with raster of pixels 107 using equation (1). The functional-block diagram for this equation consists of a cosine operation and two successive multiplications as shown in Figure 4.3. The total time needed for this calculation is 2798 A,. The number of scan lines intersecting each edge is determined during the hidden-surface algorithm as well. Using this and the two endpoints' shading values. a shading "slaps" is calculated using equation (6). This slope is also calculated during the hidden-surface algorithm. The functional-block diagram for the ”lepe" is shown in Figure 4.4. Not including the time to calculate the endpoints' shading values. the ”slope" requires 783 A,. Starting from the highest endpoint of a polygon edge. this "slope” is added to the shading value of the present edge-pixel to obtain the shade of the point of intersection of the next scan line with the same edge. Since the endpoint shades and edge s10pes have all been calculated during the hidden-surface algorithm. this procedure requires only an addition for each interior point on the polygon edges. Using these values. the interior points of the polygon.. (those not on edges). are interpolated using equations (7) and (5) as depicted in Figures 4.5 and 4.6. The complete interpolation requires 941 A,. The hardware required for each of these procedures is within the limits of the existing processor model. This is really the only algorithm that provides a method for its implementation. It uses the shading "slape" to speed the calculation of the shading values for the polygon edges and interpolates all interior points as discussed more fully in Section 3.1. It is possible to process segments of the scan lines in parallel after the segment endpoints' shades have been calculated. The image in Figure 4.2 has a total of 13 visible segments 108 l////, Gouraud Shade Calculation 1////7 Cosine cos 9 Multiplication cos 9 * cos 9 Multiplication '1 cos2 9 z / SE / Figure 4.3: Functional-block diagram of Gouraud's shading model 109 ,///// Shading "Slope" Calculation ;’ Subtraction Division / / Figure 4.4: Functional-block diagram for calculating the shading "slope" 110 z//// Interpolation Coefficient Calculation ///// Subtraction Subtraction xP-XE XF’XE Division XP'XE Kris / “ / Figure 4.5: Functional-block diagram for calculating the interpolation coefficient 111 ,//// Interpolation Calculation ////7 Interpolation Coefficient Calc “P Subtraction 1 - 4;, Multiplication Multiplication * (1- up) SF. (IP SF Addition (1- up) SE+ (1,, SF / .1, / Figure 4.6: Functional-block diagram of the interpolation calculation 112 which could easily be done in parallel by adding enough hardware. However. the number of segments composing images is neither constant nor predetermined. Also. since the length of each segment is not the same. some segments require more total time than others. A better method is to calculate shades for pixels in parallel. As long as the endpoint shades can be coordinated with each segments' interior points. each interior pixel's interpolation can be performed in parallel. By making each pixel's interpolation independent. the timing is more uniform and lends itself better to pipeline and parallel processing than segments do. Each interpolation requires three subtractors. two multipliers. one adder and one divider. The entire interpolation is used as a pipeline. there are several parallel pipelines to calculate data for several pixels at once. Using two parallel adders to calculate each segment's endpoints' shading values. the information can be available every 12 A,. After this delay. one or more of the pipelines could begin calculating pixel shading values. If there are fewer pixels in the first segment than parallel pipelines. each remaining pipeline may have to wait one or more additional delays. The delay of each stage of the pipeline must be 783 A, plus some latch delay because the division process is the most time-consuming. After the first stage is completed. several pairs of endpoints' values will be available so the pipelines can continue processing the entire picture. The pipelines will have six stages so the delay for each is (N’+ 5) 768 A,. where N is the number of values processed. This delay includes filling and emptying the pipeline. Since the pipelines are Operated in parallel. the total delay is this plus at least one addition delay: (N + 17) 768 A,. 113 The hardware necessary for this architecture primarily depends on the number of parallel pipelines used. Assuming there are three. the system would need nine subtractors. six multipliers. three adders and three dividers plus two more adders to calculate the edge shades and a buffer to store the edge shades until a pipeline is ready to use them as well as latches between the pipeline stages. So besides the latches and buffers. six adders and three complementors must be added to the system. A general block diagram of the architecture is presented in Figure 4.7. lhen applying this algorithm to the image in Figure 4.2. there are two parts to consider. The first is the extra processing that must be done during the hidden-surface removal algorithm to find data specifically for the shading portion. The second part is the shading portion itself. During the hidden-surface algorithm. shades are calculated for the vertices of the polygons and "slopes" are determined for each edge. The widget in Figure 4.2 has six polygons. eight vertices and 12 edges. Assuming that the shading information is only calculated for visible portions of the image. seven vertex shading values and nine ”slopes" must be calculated. This requires a total of 26.633 A,. This time is greatly dependent on the implementation of the hidden-surface algorithm and could possibly be reduced. However. as it stands. it does not impose any new requirements on the hardware of the system. Overall. the image has 15 interior edge points whose shading values must be calculated. In total there are 13 segments and 19 interior polygon points. Starting from point C of edge CD. the first segment has two pixels so after 12 A, two pipelines will be started. Normally. after another 12 A, the third pipeline is started but in this case the endpoints of the next 114 / Shading Calculation / Edge Shade Calculations Buffer Three Parallel Interpolation Pipelines / SP / Figure 4.7: Functional-block diagram of the entire shading calculation 115 segment are vertices of polygons meaning their shading values are already known so no addition is necessary. Since there are 19 pixels. each pipeline calculates shading values for six. The last pixel's value is found by one of the first two pipelines since they finish before the third. (This last pipeline delay would have absorbed the extra addition delay in the beginning.) Thus. the total delay for Gouraud's algorithm when applied to the standard image for N’I 7 is the pipeline delay and one addition; thus. A,. is 9228 A,. 4.2.2 Phong Transformation Phong's algorithm is presented in Section 3.2. It assumes that the light source and viewer are infinitely far away. This means that the rays of light will be parallel and that distances do not affect the shading values. The algorithm assumes normal vectors are known at vertices them instead of interpolating shading values across the polygons. normals are interpolated for each pixel. The most time-consuming portion of this process is that the normals must be normalized after they have been approximated. Although Phong assumes to know the directions of the viewer and light source. the cosine of the angle of the viewer is approximated directly from the normal vector. Phong claims that finding cos c in this manner is faster than interpolating it. but the difference between this method and calculating the cosine using a dot product is actually one extra A,. In this algorithm the calculation of normals can be considered part of the information processing during the hidden-surface algorithm. Normals are 116 approximated for each pixel of the image using the same interpolation scheme of Figures 4.5 and 4.6 that was used to approximate shading values. The functional-block diagram uses the previous figures as its blocks and is shown in Figure 4.8. The total delay is 4183 A,. Because of the large number of pixels in an image. the normal approximations would greatly benefit from a similar architecture used for the shading interpolations for Gouraud's algorithm. One difference is that the circuitry to calculate the segments' endpoints' shading values is not needed. The other is the need for normalization circuitry. The best architecture is to break up the normalization process into its five steps: three simultaneous multiplications. two sequential additions. a square root and three simultaneous divisions. These are added at the end of the interpolation pipeline making it an 11-stage pipeline. Now the stage delay must be equal to the square rooter's delay: 1536 A,. Since the total delay of any two consecutive steps does not exceed the square rooter's delay. pairs of consecutive stages are joined as one stage making a six-stage pipeline with better hardware utilization. This also decreases the total pipeline delay which is now (N + 5) 1536 A,. As with all pipelines. the greatest time savings are obtained when large numbers of the calculations are performed. The hardware requirements of this pipeline are those specified for the normalization process mentioned above and for the interpolation pipeline in the last section. The total requirements are five multipliers. four adders. three subtractors. four dividers and a shift register. If three of these are placed in parallel. the extra hardware units required by the system are 13 adders. three complementors and nine dividers. 117 4////, Approximation of Normal Vector /////7 Interpolation Coefficient Calc Interpolation Calculation Z Normalization NP Ifipl 2H / / Figure 4.8: Functional-block diagram of the normal vector approximation 118 The remaining calculations are part of the shading portion of the algorithm. to calculate the cosine of the incident angle requires a dot product as shown in Figure 4.9 which uses 155 A,. Once cos 0 is known. estimating cos c as in equation (17) requires 156 A,; this calculation is pictured in Figure 4.10. Lastly. Phong's shading calculation is equation (11). Using the cosine values. a shading value is computed according to the functional-block diagram of Figure 4.11. The entire calculation. including evaluations of the cosines. uses 4284 A,. The biggest time-user is the exponentiation of the cosine value for the specular reflection. With the OORDIC implementation of this function. unless c, is greater than 30. it is faster to perform the function using consecutive multiplications. However. since c,'s value is not known. exponentiation is used here. Nevertheless. this function can be broken into three steps. The first and last require 1536 A, so this is the stage delay of a pipeline implementation. Both cosine operations can be combined as one stage and the operations parallel to the exponentiation form four stages parallel to those of the exponentiation. All in all. there are six stages in the pipeline that contribute to the total delay of (N‘+ 5) 1536 A,. Using three of these in parallel. the hardware must have 27 multipliers. 18 adders. six subtractors and six shift registers. Therefore. in addition to the hardware added for the normal interpolations. 11 multipliers. six adders and three shift registers must also be added to to the system. Applying this algorithm to the image in Figure 4.2 increases the execution time of the hidden-surface algorithm. There are 34 visible points that need to have normal vectors. Splitting these in three. each pipeline calculates at least 11 normals with one doing an extra. The delay for this. 119 1///, Calculation of cos 9 ////7 Dot Product L'NP / e / Figure 4.9: Functional-block diagram for calculating cos 0 120 / Estimate of cos a / Calculation of cos 9 cos 9 III n Multiplication Addition Subtraction 222-1 11 / / Figure 4.10: Functional-block diagram for estimating cos c ‘121 4//// Phong Shade Calculation / T I Subtraction Calculation of cos 9 1 - Cd cos 9 I Estimate of cos 6 cos (I I I Multiplication Exponentiation c1 cos 9 (1 - Cd) I p1 cos c Addition Multiplication c1 2 C * W 9 ' P1 + Cd sum]: COS ( ) P3 Multiplication *C 3 sum P 1 p2 I I Addition P2 + P3 / / Figure 4.11: Functional-block diagram for Phong's shading model 122 with N'I 12. is 26.112 A,. In the same manner. the shades must be calculated for the same 34 points plus the seven vertices. This means two of the shading pipelines find 14 values and the last only finds 13. The total delay for the Phong shading calculation is 29.184 A,. 4.2.3 Blinn Transformation Blinn's algorithm is presented in Section 3.3. Although the polygonrmesh modeling technique is used. the surface is presumed to be composed of microfacets oriented in random directions. Blinn claims that there is no increase in execution time over Phong's algorithm. He assumes that the directions of the viewer. light source and normal are known. However. Blinn's algorithm is an attempt to improve on Phong's algorithm. Since no attempt is made to alter the shading values across polygons to smooth the shading. it is assumed that Blinn relies on Phong's technique to interpolate the normal vectors. Thus. everything in the last section that pertains to interpolating the normals applies here as well. Another process added to the hidden-surface algorithm is the determination of the direction of the specular reflection. H. as in equation (21) which is shown in Figure 4.12. 'H needs to be calculated only once per change in light source direction so this is an addition of 2471 A, to the hidden-surface algorithm's delay and two multipliers. 12 dividers. l7 adders. three complementors and one shift register. including the hardware for the normal interpolations. Blinn uses H to calculate the angle 8 that it makes with the normal. 123 ,//// Calculation of H' ////l Vector Addition f+V Normalization I+V II+V| 3| / / Figure 4.12: Functional-block diagram for calculating the direction of the peak specular reflection 124 This is unnecessary and time-consuming. The cos B is the value needed for the shading calculations and it can be found using a dot product which uses 155 A,. The calculation of Blinn's shades is more complicated because it uses the Fresnel Reflection Law. F; a distribution function for the facets' orientations. D,; a division by (HIV) and a geometric attenuation factor. G. D, utilizes calculations described in equations (29). (30). (31) and (32) for which functional-block diagrams are shown in Figures 4.13. 4.14 and 4.15. The complete calculation of D, takes 5954 A,. This calculation needs to be performed only once per frame so it does not drastically increase the execution time of the shading equation. The Fresnel function of equation (39) is depicted in Figures 4.16 and 4.17. Despite the fact that its calculation requires 3832 A,. it has to be found only once per change in light source direction. G is only calculated once per change in illumination as well. It was presented as equations (35) and (36) but is combined with the division by (HIV) using the short program at the end of Section 3.3. The functional-block diagram is Figure 4.18 and its total delay can be one of four from the various paths possible; the maximum is 1227 A,. This software requires that a magnitude comparitor be added to the system which has a delay 0f 48 A,. These last three functions can be performed in parallel so the delay of D, is added once to the shading calculation's time. Then the shading computation of equation (22) uses an additional 262 A, for consecutive multiplications as shown in Figure 4.19. There is sufficient hardware after the hidden-surface algorithm requirements are fulfilled. Applying Blinn's algorithm to the widget in Figure 4.2. the normal and 125 1///, Calculation of c3 J///, Cosine COS I Multiplication cos m * cos n I I subtraction Subtraction cos2 n «- l I num cos2 n - 2 I denom Division num denom - quot Square Root (quot)1/2 / °3 / Figure 4.13: Functional-block diagram for calculating c, 126 ,///I Calculation of k, and k2 ‘//// Calculation of c3 Multiplication Subtraction C32 - l Division l _._ . k ‘ (C32 - l) l 7 k1 Addition 4. R, 1 / *2 / Figure 4.14: Functional-block diagram for calculating k, and k, 127 A////’ Calculation of Distribution Function J////I Dot Product I Calculation of RI and k2 NIH I cos B L k k 1’ 2 I J Multiplication cos fl * cos I Addition cos2 p + k l I denom Division k _- o denom qu t Multiplication quot * quot / / Figure 4.15: Functional-block diagram for calculating the orientations distribution of the facets' 128 /////r Calculation of g and j A///// { Dot Product I m” H j l l Multiplication I L Multiplication r * r l l J * J l I i J [ Addition I I Subtraction I r2 + 12 - 1 Square Root J / s / Figure 4.16: Functional-block diagram for calculating g and j 129 / menisci. o! If“). Mia. / I Calculation of g .4 j I I s. 1 I 7 T F . 1 Addition Subtraction s 0 3 I - 1 1 r r I T 1 mt IMO. I m‘”““‘“‘ ltalt nudes r ”tune-non J (a - J) - v “-91-" J (g¢5)1-,2 lath-p, I ‘ I f I I [ , I , I I mflufl I I «unau— ] I “an“ '1 a": an”, vim—1 g I ’ I l 1 lhltiplicstum “tumtm an! ' .1 d1 ' d‘ F’ J L Figure 4.17: Functional-block diagram for calculating the Fresnel function 130 / 'alculatlfl ol 6 u (i-') 70'- / l I 1 Dec Pres-ta cu fluent: not Pvnsnu Du Paine: De: Pres-u i-? i t a; i i 5.; l l I J 01'th L Tr? ._ mastication hutsltestlcn 4 a a 7 (i-fi (i-i) . '1 (it) (Fri) - v, Wit-t. Addition .' . 'l . 1" '1 . ’1 . 1.: assista- simian minute-tun (i-i) 0 (ii) - —1 “If“ ('1) 0 fl") - v, amu- Division :L. 2: Ni) 'b \ [3+ \ Figure 4.18: Functional-block diagram for calculating G and the (T137) terns 131 moves main-Au -.uu«—m uou noun-«v ace—niuanomacuuh "an.v ounumm O h D cowumuwaawuasz coaumoflaawuasz a _ m 25.4; 8% 2;. u no .38 cofluucam Hummonm wo .uHmo .5 532:me no .38 T \ _ 4 532238 mafia 5:; \ 132 i calculations add 28,583 A. to the hidden-surface algorithm's execution time. There is a one tine delay of 5954 A‘ to start the shading calculations. then the shading values for the 41 pixels covered by the inage. each using 262 A‘, are calculated. The total delay for the shading portion of Blinn's algorithm is 16,696 A.. Thus. Blinn's claim that his algorithm did not increase the execution time of Phong's algorithm has been verified. 4.2.4 Newell-Sancha Transformation Newell. Sancha and Nevell's algorithm. presented in Section 3.4. performs most of the hidden-surface removal and shading functions at the same time. It calculates shading information by polygon rather than scan line. Shading values must still be calculated per pixel but the values are constant throughout a polygon meaning less calculations are necessary. The hidden-surface algorithm arranges the polygons in order of increasing distance from the viewer. Shading values are calculated for polygons starting vith the furthest ones using equations (40). (41) and (42). After the polygon's shading value has been determined. the entire polygon is vritten into memory. In this manner polygons are placed in the nemory and closer ones that obscure others simply overlap them. This automatically "removes" hidden surfaces but it is possible to calculate several values for the same pixel as will be evident from the example at the end of this section. The advantage of this method is that transparent surfaces are easily simulated though refraction effects are ignored. Also. no extra processing for the shading function is required in the 133 hidden-surface algorithm since they are performed together in the shading calculation. The shading calculation assumes that the incident angle is known and so the cosine and sine functions are evaluated directly. Figure 4.20 shows the functional-block diagram for the shading calculation. The total delay is 4894 A“. If the closest object is transparent. when a shading value is recalculated for a pixel. the new shading value is a combination of the old and new values as found using equations (41) and (42) and illustrated in Figure 4.21. The transparency calculation is basically an interpolation but the weighting factor is already known and does not have to be calculated; however. a nagnitude comparator must be added to the system hardware. The total delay of this computation is 206 A‘. Overall. the equations can be arranged into a three-stage pipeline with a stage delay of 1536 AI by breaking up the exponentiation function as was done for previous algorithms. The last three Operations in Figure 4.20 plus the entire transparency calculation can be combined as the third stage of this pipeline. Thus. the pipeline delay is (N‘+ 2) 1536 A“. In this case parallel pipelines are not as necessary because fewer calculations need to be performed since the data is calculated per polygon instead of per pixel. Thus. the only extra hardware needed for the system is a shift register and a magnitude comparator. When applied to the image in Figure 4.2. this algorithm calculates a shading value for each of the six polygons comprising the object. Once the shade is determined it is assigned to each pixel covered by the polygon. Using the pipeline. the total delay is 12.288 Al' Though the delay is not too extensive, some of it is unwarranted because the algorithm is not 134 / Newell-Sancha Shade Calculation J Cosine / cos 9 Sine sin 9 Exponentiation cos 9 Exponentiation sin1 9 Multiplication 3 Cr cos 9 p1 Multiplication 1 CS sin 9 - p2 Addition + 2 PI 92 sum 1 Addition sum + S a l / shading model / Figure 4.20: Functional-block diagram for Newell et al.'s 135 z///, Transparancy Calculation /’ Subtraction 1 - w Multiplication Multiplication “*Sn (1-w)*So [ Addition w 8 + (1 - w) S n / s / Figure 4.21: Functional-block diagram for calculating shading values for transparent objects 136 efficient. Assuming the image of Figure 4.2 is opaque. each pixel will be replaced by another shading value at least once. Iorse yet. pixels on edges common to two or more polygons are replaced more frequently. Thus. at least half of the execution time could be eliminated by a hidden-surface algorithm in this example image with the object being opaque. Now assuming that the polygon AEEB is an opening rather than a surface. seven of the 41 pixels have only one shading value assigned to them but the seven are a small percentage of the total so time may be saved by using a hidden-surface algorithm. However. whether or not an actual time-savings can be realised by using a hidden-surface algorithm would depend on its implementation. 4.2.5 Ihitted Transformation This algorithm. presented in Section 3.5. can be applied to planar-polygons or curved-patches; the polygon implementation is discussed in this section. 'hitted assumes that the normal vectors and directions of the light source and viewer are known. Nevertheless. the vectors for the reflected light. i and transmitted ‘light. 'T. are calculated during the hidden-surface algorithm using the method of ray-tracing described in Section 3.5. Infonmation about the way light illuminates the object is calculated on a global basis during the ray-tracing procedure. Ray-tracing is performed by starting at a point on the surface and calculating 'i and 'T from that point. These new vectors are then followed until they reach another surface where they become the new incident rays and the procedure is repeated. Therefore. these calculations are sometimes performed several times starting 137 from a single pixel. Equation (43) calculates 7' and the functional-block diagram is shown in Figure 4.22. The total execution time is 2614 A‘. A pipeline configuration could be used but is not worthwhile as will be explained. 'V' is used to calculate'T and i. The functional block diagram for equation (44) that computes '5 is shown in Figure 4.23 and has a delay of only 24 A' after 7' is known. 'T is found using Snell's law to simulate refraction effects through transparent objects. The calculation of the coefficient kf is diagrammed in Figure 4.24. Note that the vector magnitude procedures in the second step do not include the square root step of the usual procedure so their delay is only 155 A‘. The renaining portion of the 'T calculation is shown in Figure 4.25. The total delay. not including the ‘V' calculation. is 2882 A“. It is not worthwhile to pipeline this computation because of the data dependency among the various steps; none can proceed until kf is known but the delay for k: practically causes the entire delay of the T calculation. However. a two-stage pipeline could be used where the first stage finds V' and the last stage finds‘f and T. The stage delay would be 2906 A‘ so the pipeline delay is (N + 1) 2906 A‘. The required hardware includes six multipliers. five adders. one complementor. two dividers and a shift register which are within the limits of the processor model. Using three of these pipelines in parralel. two multipliers. seven adders. three dividers and three shift registers need to be added to the system. The shading calculation of equation (45) is diagrammed in Figure 4.26. The total delay is 298 A‘. This computation can be pipelined into three stages with a stage delay of 155 A“. The first stage includes the first 138 / Calculation of V' / Dot Product V?fi Vector Magnitude lV-ii‘l 1 Division V |l _._T... / / Figure 4.22: Functional-block diagram for calculating V” 139 l///r Calculation of i. ,///7 Calculation of V" v! Vector Addition fi+fi Vector Addition V'i-zfi a” / / Figure 4.23: Functional-block diagram for calculating the direction of reflection 140 l(//( Calculation of RE 1///, l l ‘l Calculation of V" Multiplication “ a V. kn kn Vector Addition V’ + E [Vector Magnitude Squared I [7 Vector Magnitude Squared |73I2 IV“ + 8'2 - 91 Multiplication k2*IV'I2-p L 2 F Subtraction p2 ‘ p1 ' d1 Square Root I 3 Division .1. “I / k / Figure 4.24: Functional-block diagram for calculating kf "I 141 4///, Calculation of f /’ Calculation of V' r Calculation of R _J f Vector Addition +V' 3' 2| f L Multiplication Multiplication Multiplication _. — * - -l _ .— kf t (N + vo)x kf (N + v )y kt * (N + V"; Subtraction I kf (E + V') - ii I HI / / Figure 4.25: Functional-block diagram for calculating the direction of transmitted light 142 1//’/r Hhittcd Shad. Calculation J////’ Dot Product I I Multiplication Multiplication _._ c a n N-L s c s 1- t Multiplication Addition --— I + I Cd * (N I.) p1 C. R Ct T sunsl I Addition sum + S l a J Addition Sulll1 + Sa + p1 / s / Figure 4.26: Functional-block diagram for 'hitted's shading model 143 three parallel operations. The second stage has the multiplication performed parallel to two successive additions. The last stage is the last addition. The total pipeline delay is (N'+ 2) 155 A‘. Even with three parallel pipelines the procedure does not need any extra hardware. Applying the ray-tracing procedure to the image in Figure 4.2 is somewhat trivial if the object is opaque because there is only one object and. therefore. no surfaces for the I and T vectors to bounce off of. There are 82 pixels in both the visible and hidden faces but since the light rays never strike the hidden-surfaces only 41 pixels require one ray-tracing calculation each. Each pipeline computes values for 13 pixels with two doing an extra. The total delay added to the hidden-surface algorithm is 43.590 A‘. After the hidden-surface algorithm is performed. only 41 pixels are visible so the delay for 'hitted's shading procedure is 2480 AI vhen N is 14. So the ray-tracing computations are very time-consuming but the shading is very fast. If part of the object is transparent. the number of vectors to calculate is greater and the ray-tracing execution time increases but not the shading time. Assuming polygon ABFE is transparent. seven extra sets of i and T vectors must be calculated because the initial T values will strike the previously hidden faces. Thus. the ray-tracing time increases to 49.404 A'; an increase of 5814 A“. 4 .2 .6 Catmull Transformation Cannull's algorithm is presented in Section 3.6. It does not actually present a specific shading model but claims any can be used that are based on the surface normal. The algorithm can be applied to both polygons and 144 curved-patches but is presented for curved-patches called bicubics. First. surface normals are approximated for each patch. This is a very time-consuming process attributed to the hidden-surface algorithm. Next. the object model is modified using a subdivision algorithm to break the patches into pixel-sire subpatches. The approximated surface normals are divided with the patches so that each subpatch has its own normal. The normals are approximated using several matrix multiplication operations. All of the operations have at least one 4 x 4 matrix; several involve the vectors 0 and V from equations (48) and (49) since the bicubic equations are functions of u and v. It is assumed that the first and second derivatives of these vectors are known. values for (u.v) that are of particular interest are (0.0). (0.1). (1.0) and (1.1). If these values are plugged into the vectors and stored as constants for use during the matrix nultiplications. long strings of summands can be avoided because the additions can be performed in parallel with the multiplications. Otherwise. each summand as found in Figure 4.27 would have a possible 256 terms. plus the number of multiplications would increase because polynomials are being multiplied. By using the constant vectors. the number of summands that must be generated increases but there is an overall savings in time. The time analysis for the normal approximation is only discussed for one component of the bicubics. x. The other two are calculated in a similar procedure that requires the same amount of time and hardware. Referring to Figure 4.27. the summands are calculated for equations (53). (59). (60) and (61). Since matrix multiplication is associative. the rightmost pair are multiplied first to fully utilize the hardware and minimize the delay. The matrix multiplication of a m x c matrix and a c x p matrix is set up so that 145 / Summand Generation / Matrix Multiplication Matrix Multiplication k j * * V a U (Mi ) P1 I Matrix Multiplication j h a v M * V ”i 3 Matrix Multiplication f h * * = U (Mg V ) p2 Multiplication * D1 1)2 / Uk Mi vj Uf Mg vh / Figure 4.27: Functional-block diagram for summand generation 146 the delay is dependent on the value of p. For VJ the value of p is one so the delay is minimal. The product of the first step is also a 4x1 natrix so the delay of the second matrix.multiplication is also minimised. The total ‘. This can be made into an efficient. three-stage pipeline because each of the stages has nearly the same delay. delay to generate a summand is 441 A The pipeline's delay is (N’+ 2) 155 A‘. Using these summands. equations (53). (59). (60) and (61) can be evaluated using the summation and complementing processes. In equation (53) x11 has two terms so the delay is (12 + 3) A‘. The number of summands in equations (59) and (60) is four. Complementations can be performed in parallel before the summation begins. The total delay is 27 A‘. Equation (61) has eight summands and its delay is 39 A'. These summations can be performed as the summands are generated so the delays are insignificant. The extra hardware necessary for the pipeline and summations is 49 multipliers and 43 adders. The final computation for the normal is a 4 x 4 multiplication as in equation (56) and shown in Figure 4.28. The value of p is four so each stage takes 524 A.. Foaming a two-stage pipeline. the total delay is (N + 1) 524 A'. The necessary hardware is covered by the extra added for the extra hidden-surface calculations. However. all of the hardware must be tripled so that all three components can be calculated in parallel. The total additional hardware is 179 multipliers and 145 adders which is significantly more than that needed by any of the other algorithms. According to Catmull. each component requires 30 additions during each subdivision in the subdivision algorithm. The components may be calculated simultaneously. Catmull estimates that the number of subdivisions needed to 147 /////’ Approximate Normal Component Calculation j////7 Matrix Multiplication w/o Sums C * P x Matrix Multiplication w/o Sums C * P * CT x ////// String of Summands with Coefficients ,////I Figure 4.28: Functional-block diagram for approximating one normal component for a bicubic patch 148 completely divide a patch is slightly greater than one third of the number of pixels covered by the patch. The total delay added to the modeling portion of the processing is then (360 9 sub) A‘ where sub is the number of subdivisions required. Applying this algorithm to the gixmo in Figure 4.2. it requires slightly greater than 35 subdivisions when edge pixels that are common to two patches are counted twice; once for each patch. This means an increase in the modeling procedure of 12.600 A‘. Normals are approximated per patch so six are needed here. This adds 3668 A‘ to the hidden-surface algorithm's execution time. Altough the additional delays are relatively short. the extra hardware is quite extensive. 4.2.7 Cook-Torrance Transformation Cook and Torrance developed a shading model that is presented in Section 3.7. In their original paper they discussed color shaded images extensively. One of their conclusions is that objects made of certain naterials have specular reflections and diffuse reflections of different colors. Since all of the other algorithms discussed in this report do not address the issue of colored images. this part of the Cook-Torrance algorithm is largely ignored. Overall. the algorithm is very similar to Blinn's algorithm discussed in Sections 3.3 and 4.2.3 because both assume that the surface is made up of randomly oriented microfacets. Yet Cook and Torrance assume that the direction of the specular reflection. E. is known. If this is calculated during the hidden-surface algorithm as in Section 4.2.3. which is shown in 149 Figure 4.12. then the delay is 2471 A. which occurs only once per change in the light source's direction. The hardware needed for this calculation is within the limits of the systen. The shading calculation depends on the geometric attenuation factor. a division by (N;V). the Fresnel Refraction Law and a distribution function for the facets' orientations. The calculation of G and the (N‘V) division are performed exactly as shown in Figure 4.18 and discussed in Section 4.2.7. Therefore. their delay is a naximum of 1227 A'. The Fresnel function calculation is the same as Blinn's in Figures 4.16 and 4.17 except the final value is multiplied by one half in this model. However. this multiplication can be performed in parallel with the last set of simultaneous multiplications so the execution time is unchanged at 3832 A‘. The distribution function used is different from Blinn's and is presented as equation (71). Its functional-block diagram is shovn in Figure 4.29 and its total delay amounts to 4105 A These four functions are used to calculate the specular component of the reflected light. R . R ' ' is found using equation (69) and its functional-block diagram is presented in Figure 4.30. The total time needed for this calculation is 4105 A. for c. n. F end (fi-V) which are found simultaneously and only once per change in light source direction. The remaining time needed per pixel is only 262 A“. The shading model calculation is diagrammed in Figure 4.31. R‘. the hemispherical-directional reflectance. and Rb. the bidirectional reflectance. are linear combinations of the diffuse and specular components of the reflectance; Rd and R‘. so they are calculated using the interpolation calculation of Figures 4.5 and 4.6 in Section 4.2.1. If the interpolation calculation is broken into three steps. the shading 150 Calculation of D I Dot Product 1 L Multiplication Tangent (N’fi) - cos p m * Ill tan I Multiplication Multiplication cos . *coe I tan ’ * tan ’ I Multiplication Division tan2 9 - q c052 l * cos2 9 32 1 Multiplication Complement m2 cool. I -ql Division Exponential 1 _ q 1112 cos“ p 2 efil I Multiplication 'q 1 * q2 e 7 Figure 4.29: Functional-block diagram for calculating the distribution of the facets' orientations 151 .3333: no nuance-co .933... on» na.uauoo.eo now Innueao Mooueineoomuouom "on.v euon.u eoaeeo._c.._:x _ Pi e... a. . e . Icu —l‘ coaueo._e.e_or _ _ 3...: n v I IHIII . cone.>.o _ 3.1.. a n — oozes—3:3. _ m.m .w.m. a n U non—5.... no: _ — clue... 5...: one u no .300 _ — a «o cone—no.8 _ — cones-i use-sum no .38 w _ L g a \ an no so. .3338 \ 152 1////r Cook-Torrance Shade Calculation L / J Dot Product I Multiplication Calculation of Rs it .1 *Ii R Multiplication 'i Ii * (N°L) ' P1 Interpolation Calculation Interpolation Calculation R a "b Multiplication Multiplication * u I Ra p2 [ pl *Rb-p3 l J / Addition I p2+‘5 s / Torrance shading model Figure 4.31: Functional-block diagram for the Cook and 153 computation can be made into a five stage pipeline with a stage delay equal to that of division. 768 A.. Thus. the total delay is (N‘+ 4) 768 A‘ plus a one time addition of 4105 A‘. Only three multipliers and one adder need to be added to the hardware. If three of these pipelines are used in parallel. three magnitude comparators. three complementors. 2O multipliers and one adder must be added to the system. Then applied to the image in Figure 4.2. the time added to the hidden-surface algorithm is still 2471 A.. To calculate shading values for the 41 visible pixels requires 17.929 A‘ where N'- 14. 4.2.8 Fournier-Fussell-Carpenter Transfonmation This last algorithm uses a technique called fractalixation to alter the object modeling technique to make images of natural objects appear more realistic. It is presented in Section 3.8. The object to be modeled is composed of planar. triangular polygons. This algorithm divides the triangles into smaller triangles until none represent more than a single pixel in the raster. The algorithm finds the midpoints of the three sides of a triangle then uses the points to break the triangle into four smaller triangles. The process is transformed into a functional diagram as in Figure 4.32. The total delay is 780 A. per triangle that is divided. If three of these circuits are used in parallel. the extra hardware required by the process is 24 dividers and 19 adders. After the new object model has been completed. the hidden-surface algorithm has to calculate the normals to the triangles so that any of the 154 eoo.ua.oo~ao no.ueu..euoeuu uou luau-.6 moo—elnanouuouom "um.v ounmum \\\\\ moamcmwue usom (\\\\ 4 U c. m: . sowumaaoaeo ucaooowz cofiumanoamo unwoacfiz sowumasuamo usfioocaz \\\\\ :owumuwamuomum (\\\\ 155 shading models previously discussed can be applied. This process requires 161 A' per normal calculated. or per triangle. The number of triangles is likely to get very large so three normal-calculator circuits are used in parrallel. No additional hardware is necessary. Before the algorithm can be applied to the image in Figure 4.2. the polygons must be broken into triangles. Any polygon can be broken into triangles by starting at one vertex and connecting it to all of the other vertices except the two immediately beside the first. Applying this to the image in Figure 4.2. a total of 12 triangles are formed from both visible and hidden surfaces. There are a total of 81 pixels covered by all of these surfaces so there must be at least 81 triangles formed. This will require 22 fractalixations which will use 6240 A‘. The normal calculations will be performed for only the 41 visible triangles so they use 2254 A'. 4.3 Comparisons This chapter discussed the eight algorithms on the basis of their images' realism. Although realism is a subjective quality. it is important because it is often the basis of most viewers' opinions of the images. The most important criterion for raster graphics systems is the speed of execution because if successive frames take too long to generate. the quality of the image degrades to the point where flicker can be annoying. Section 4.1 described basic processes that could be used to transform the algorithms into functional-block diagrams to help analyze their execution times. The hardware requirements of these processes were assessed and formed the basic processor for the system. The functional-block diagrams 156 were applied to various architectures to attempt to minimise the execution times. This often required additional hardware to be added to the system. Sometimes the algorithms added extra time and/or hardware to the hidden-surface removal or object modeling portions of the entire display process. All of these execution times and hardware requirements are summarised in Table 4.2. Based on the time analyses performed. the Newell-Sancha algorithm requires both the shortest delays and the ninimal extra hardware. This may be the reason why the images are not as realistic as any from the other algorithms. Gouraud's images are quite good yet the delays are not too great and the extra hardware is the second minimal. Gouraud utilised the cosine function rather than a dot product during the hidden-surface algorithm to compute contributions of light from the source; most of the other algorithms used dot products. The cosine requires more time to calculate than do dot products. Newell. et al.. use the cosine function but calculate much fewer shading values overall so its extra time is not significant. Gouraud's extra time in the hidden-surface algorithm could be reduced but the cosine is not used to calculate all shading values so switching to the dot product may not generate too great of time-savings. However. Gouraud's algorithm does not simulate specular reflections very realistically. Blinn and Phong improve on Gouraud's method with Blinn's algorithm being the faster and requiring less extra hardware. Still. these do not accurately simulate effects of transparency. 'hitted's algorithm is capable of such effects and produces extremely realistic hnages. Ihitted's shading model did not reproduce specular reflections as well as Blinn's or Phong's as the surface becomes less smooth but it does 157 .cowuocsm mwnu HOw venom on xme Esufiuowam wcacmnm nocuo mceeoooz oceans u mouoenm I am: u «m: u uneconm u monoocm . mm; . monoecm u Aam>oEom communmlcovvfimv Mm: I monoecm - mm<3nm<= «maxm oszHDomm zmeHmoou< no onemom mam umsu mowanEw cesaoo maMDU mmmZIzoowdom A/\I\\\I\W Homhmo ZEHHmOUA< qua