Incremental Shading Techniques

Most images currently generated in computer graphics apply the Phong reflection model to polygon mesh models. Polygon mesh models are distinguished by the fact that the geometric information is only available at the vertices of a polygon.  Incremental or interpolative shading techniques apply simple reflection models to polygons, calculating intensities at the vertices, and then interpolating values for interior points.  Interior points are evaluated in scan line order and the schemes are easily integrated into a Z-buffer or a scan line hidden-surface removal algorithm.

The term 'shading' is loosely used to signify the application of a 'point' reflection model over the entire surface of an object.  The term 'rendering' appears to be used to mean the complete process of going from an object database to the final shaded object on a screen.  This section deals only with the problem of applying simple reflection models to polygon mesh objects.  The next section looks at how these methods are integrated with scan conversion and hidden surface removal to form a complete rendering system.

Two incremental shading techniques are common; Gouraud interpolation (1971) and Phong interpolation (1975).  Phong  interpolation gives more accurate highlights and is generally the preferred model.  The Gouraud method tends to be confined to applications where the diffuse component is sufficient, or to preview images prior to final rendering.

Phong shading is more expensive than Gouraud shading and obeys the first law of computer graphics, which appears to be that the required processing time grows exponentially with perceived image quality. However, Gouraud shading has become almost standard in recent graphics hardware and Phong shading is also available.

These notes deal with both these methods .  Doing shading calculations efficiently is a neglected topic in computer graphics.  Phong calculations can greatly exceed more than 50% of the total rendering time and addressing the problem of shading using an efficient method should be considered to be just as important as the quality of the reflection model.  It is mandatory in areas such as three-dimensional animation where large numbers of frames have to be generated.

Another problem that must be addressed by interpolative shading techniques is final polygon visibility.  Polygon boundaries should be invisible in the final shaded version and some impression of the original surface that the polygon mesh approximates restored.  We can thus identify two functions of a shading scheme for polygon meshes:

   (1)    to use some interpolative method for interior points, and
   (2)    to diminish the visibility of the polygon mesh approximation.

The first shading schemes to be used in computer graphics were developed by Bouknight (1970) and Wylie et al. (1967).  Wylie et al.'s method calculated an intensity at the vertices of triangular facets on the basis of distance from the viewpoint and then used linear interpolation to assign an intensity to interior points.  In Bouknight's work the emphasis was on hidden surface removal and the polygons were 'constant' shaded.  That is, a single intensity was calculated for each polygon and used over its entire area.  This method, although it certainly imparts an impression of three dimensionality, leaves the polygon mesh structure glaringly obvious.

Gouraud shading

The generally acknowledged first scheme that overcame the disadvantages of constant shading of polygons uses bilinear intensity interpolation. This is known as Gouraud shading (1971).  It is a simple and economic scheme that does not entirely eliminate the visibility of polygons.  It suffers from Mach banding - where piecewise linear intensity changes across a polygon boundary trigger the human visual system into perceiving the boundary as a bright band.  The standard explanation for this is that the human visual system is sensitive to the second derivative of intensity because of our need to detect and enhance edges.

The Gouraud scheme is normally restricted to the diffuse component of the reflection model developed in Chapter 2. This is because the shape of the specular highlights, using this scheme, depends strongly on the underlying polygon mesh.  An obvious highlight example that Gouraud shading misses altogether is the case of a highlight in the middle of a polygon.  If there is no highlight component at any vertex then there is no way that the highlight will be recovered by the interpolation. The diffuse component as we have seen previously is expressed as:

        I_i k_d (L . N) / (r + k)

If we assume the light source is at infinity then L . N is constant over the surface of the polygon.  The only variable is r, the distance of the view point.  If we ignore the fact that the variation of r over the polygon is non-linear (or even ignore r altogether), then we can calculate intensities at the vertices and use bilinear interpolation to calculate all other intensities.

The technique first calculates the intensity at each vertex of the polygon. The normal N used in this calculation is the so-called vertex normal and this is calculated as the average of the normals of the polygons that share the vertex (see the figure below).  This is an important feature of the method and the vertex normal is an approximation to the true normal of the surface (which the polygon mesh represents) at that point.

A pass through the data structure storing the object will calculate an intensity I_v for each vertex.  The interpolation process that calculates the intensity over a polygonal surface can then be integrated with a scan conversion algorithm that evaluates the screen position of the edges of a polygon from the vertices in the data structure.

The vertex normal NA is the average of the normals Nl, N2, N3 and N4,
the normals of the polygons that meet at the vertex.

The intensities at the edge of each scan line are calculated from the vertex intensities and the intensities along a scan line from these (see figure below). The interpolation equations are as follows:

For computational efficiency these equations are implemented as incremental calculations.  This is particularly important in the case of the third equation, which is evaluated for every pixel.  If we define Ax to be the incremental distance along a scan line then AI, the change in intensity, from one pixel to the next is

Apart from Mach banding, two well-known errors that can be introduced in Gouraud shading are:
 

  1) Anomalies can appear in animated sequences because the intensity interpolation is carried out in screen coordinates from vertex normals calculated in world coordinates.  This is not invariant with respect to transformations such as rotation and in animated sequences frame-to-frame disturbances can be caused by this.

  2) The process of averaging surface normals to provide vertex normals for the intensity calculation can cause errors which result in, for example, corrugations being smoothed out.  The figure below shows three normals all pointing in the same direction.  This would result in a visually flat surface.  Although this can be a problem, it should not occur providing a sufficiently dense polygonal surface has been used in the model.

A regularly corrugated surface producing identical vertex
normals from non-identical surface normals.

Phong interpolation

A method due to Bui-Tuong Phong (1975) overcomes some of the disadvantages of Gouraud shading and specular reflection can be successfully incorporated in the scheme.  In particular we can now have a specular highlight in the middle of a polygon despite the fact that each of the vertex normal angles would not produce a highlight.  The features of the method are:

 1) Bilinear interpolation is still used so that points interior to polygons can be calculated incrementally.
 2) The attributes interpolated are the vertex normals, rather than vertex intensities.  These are calculated,  as before, by averaging the normal vectors of the surfaces that share the vertex.
 3) A separate intensity is evaluated for each pixel from the interpolated normals.

 4) Again we need to assume that both the light source and the viewpoint are at infinity so that the intensity at a point is a function only of the interpolated normal.

The first stage in the process is the same as for the Gouraud method - for any polygon we evaluate the vertex normals.  For each scan line in the polygon we evaluate by linear interpolation the normal vectors at the end of each line (see the figure above). These two vectors Na and Nb are then used to interpolate Ns.  We thus derive a normal vector for each point or pixel on the polygon that is an approximation to the real normal on the curved surface approximated by the polygon.  This feature accounts for the quality of Phong shading.  Ns, the interpolated normal vector, is then used in the intensity calculation.  This idea is represented in the figure below, which shows that vector interpolation tends to restore the curvature of the original surface that has been approximated by a polygon mesh.  Referring to the notation used above we have:

Vector interpolation tends to 'restore'curvature

These are vector equations that would each be implemented as a set of three equations, one for each of the components of the vectors in world space.  This makes the interpolation phase three times as expensive as Gouraud shading.  In addition there is an application of the Phong model intensity equation at every pixel.  Incremental computations can be employed as with intensity interpolation, and for example, would be implemented as:

where Nsx, Nsy and Nsz are the components of a general scanline normal vector Ns and

Comparison of Gouraud and Phong shading

Gouraud shading is effective for shading surfaces which reflect light diffusely.  Specular reflections can be modelled using Gouraud shading, but the shape of the specular highlight produced is dependent on the relative positions of the underlying polygons.  The advantage of Gouraud shading is that it is computationally the less expensive of the two models, only requiring the evaluation of the intensity equation at the polygon vertices, and then bilinear interpolation of these values for each pixel.

Phong shading produces highlights which are much less dependent on the underlying polygons.  However, more calculations are required, involving the interpolation of the surface normal and the evaluation of the intensity function for each pixel.
 
 

The Rendering Process

This section brings together material in  previous notes, integrating it into the rendering process. Rendering is a general term that describes the overall process of going from a data representation of a three-dimensional object to a shaded two-dimensional projection on a view surface.  It involves a number of separate processes:

 (1)  setting up a data structure for polygon models that will contain all
       the information which is subsequently required in the shading
       process;
 (2)  applying linear transformations to the polygon mesh model, for
       example transformations to position objects within a scene, and
       viewing transformations;
 (3)  culling back-facing polygons;
 (4)  scan converting or rasterizing polygons, that is converting the vertex-
       based model into a set of pixel coordinates;
 (5)  applying a hidden surface removal algorithm;
 (6)  shading the individual pixels using an interpolative or incremental
       shading scheme.

In practice, operations (4), (5) and (6) are carried out simultaneously. However, computer graphics textbooks normally fragment the rendering process.  They usually contain a chapter comparing hidden surface removal algorithms without regard to how these algorithms are integrated with the other processes.  In this section we present  an integrated approach to the entire latter half of the rendering process.  So rather than dealing with them as unconnected processes, we shall wherever possible, try to show how they work together.

It would appear that most rendering systems have settled for some variation of the Z-buffer approach, and indeed graphics workstations are now available with hardware Z-buffers.  Other hidden surface removal algorithms find applications in special contexts.

Rasterizatlon

First, it is necessary to discuss rasterization, or scan conversion.  This is the process of finding which pixels an individual polygon covers or, at a more basic level, which pixels an edge of a polygon lies on.  This second aspect will be dealt with first.

Rasterizing edges

There are two different ways of rasterizing an edge, based on whether line drawing or solid area filling is being used.  Line drawing is not covered in these notes, since we are interested in solid objects.  However, the main feature of line-drawing algorithms (for example, Bresenham's algorithm (1965)) is that they must generate a linear sequence of pixels with no gaps (figure (a) below).  For solid area filling, a less rigorous approach suffices.  We can fill a polygon using horizontal line segments; these can be thought of as the intersection of the polygon with a particular scan line.  Thus, for any given scan line, what is required are the left- and right-hand limits of the segment, that is the intersections of the scan line with the left- and right-hand polygon edges.  This means that, for each edge, we need to generate a sequence of pixels corresponding to the edge's intersections with the scan lines (figure (b) below). This sequence may have gaps, when interpreted as a line, as shown by the right-hand edge in the diagram.

The conventional way of calculating these pixel coordinates is by use of what is grandly referred to as a 'digital differential analyser' or DDA.  All this really consists of is finding how much the x coordinate increases per scan line, and then repeatedly adding this increment.

 Pixel sequences requiredfor (a) line drawing and (b) polygon filling.

Let (xs, ys), (xe, ye) be the start and end points of the edge (we assume that ye > ys).  The simplest algorithm for rasterizing, sufficient for polygon edges is:

      x = xs
       m = (xe - xs)l(ye - ys)
       for y  = ys to ye do
          output (round (x), y)
          x =  x+m

The main drawback of this approach is that m and x need to be represented as floating-point values, with a floating-point addition and real-to-integer conversion each time around the loop.  A method due to Swanson and Thayer (1986) provides an integer-only version of this algorithm.  It can be derived from the above in two logical stages.  First we separate out x and m into integer and fractional parts.  Then, each time round the loop, we separately add the two parts, adding a carry to the integer part should the fractional part overflow.  Also, we initially set the fractional part of x to -0.5 to make rounding easy, as well as simplifying the overflow condition.  In pseudo-code:

      xi = xs
       xf = -0.5
       mi = (xe - xs) div (ye - ys)
       mf = (xe - xs)l(ye - ys) - mi

       for y  = ys to ye do
          output (xi, y)
          xi = xi + mi
          xf = xf + mf
          if xf > 0.0 then  {xi = xi + 1; xf = xf - 1. 0}

Because the fractional part is now independent of the integer part, it is possible to scale it throughout by 2*(ye - ys), with the effect of converting everything to integer arithmetic:

      xi = Xs
       xf = -(ye - ys)
       mi = (xe - xs) div (ye - ys)
       mf = 2*[(xe-xs) mod (ye-ys)]

       for y  = ys to ye do
         output (xi, y)
         xi = xi + mi
         xf = xf + mf
         if xf > 0 then {xi = xi + 1; xf = xf - 2*(ye - ys)}

Although this appears now to involve two divisions rather than one, they are both integer rather than floating point.  Also, given suitable hardware, they can both be evaluated from the same division, since the second (mod) is simply the remainder from the first (div).  Finally it only remains to point out that the 2*(ye - ys) within the loop is constant and would in practice be evaluated just once outside it.

Rasterizing polygons

Now that we know how to find pixels along the polygon edges, it is necessary to turn our attention to filling the polygons themselves.  Since we are concerned with shading, 'filling a polygon' means finding the pixel coordinates of interior points and assigning to these a value calculated using one of the incremental shading schemes described in the previous chapter.  We need to generate pairs of segment end points and to fill in horizontally between them.  This is usually achieved by constructing an 'edge list' for each polygon.  In principle this is done using an array of linked lists, with an element for each scan line.  Initially all the elements are set to null.  Then each edge of the polygon is rasterized in turn, and the x coordinate of each pixel (x, y) thus generated is inserted into the linked list corresponding to that value of y. Each of the linked lists is then sorted in order of increasing x. The result is something like that shown in the figure below. Filling in of the polygon is then achieved by, for each scan line, taking successive pairs of x values and filling in between them (because a polygon has to be closed, there will always be an even number of elements in the linked list).  Note that this method is powerful enough to cope with concave polygons with holes.

In practice, the sorting of the linked lists is achieved by inserting values in the appropriate place in the first place, rather than performing a big sort at the end.  Also, as well as calculating the x value and storing it for each pixel on an edge, the appropriate shading values would be calculated and stored at the   same time (for example, intensity value for Gouraud shading; x, y and z components of the interpolated normal vector for Phong shading).

 An example of a linked list maintained in polygon rasterization.

If the object contains only convex polygons then the linked x lists will only ever contain two x coordinates; the data structure of the edge list is simplified and there is no sort required.  It is not a great restriction in practical computer graphics to constrain an object representation to convex polygons.

One thing that has been slightly glossed over so far is the consideration of exactly where the borders of a polygon lie.  This can manifest itself in adjacent polygons either by gaps appearing between them or by their overlapping.  For example, in the figure below the width of the polygon is 3 units, so it should have an area of 9 units, whereas it has been rendered with an area of 16 units.  The traditional solution to this problem, and the one usually advocated in textbooks, is to consider the sample point of the pixel to lie in its center, that is at (x + 0.5, y + 0.5). (A pixel can be considered to be a rectangle of finite area with dimensions 1.0 x 1.0, and its sample point is the point within the pixel area where the scene is sampled in order to determine the value of the pixel.) So for example the intersection of an edge with a scan line is calculated for y + 0.5, rather than for Y, as we assumed above.  This is messy, and excludes the possibility of using integer-only arithmetic.  A simpler solution is to assume that the sample point lies at one of the four corners of the pixel; we have chosen the top right-hand corner of the pixel.
 
 

This has the consequence that the entire image is displaced half a pixel to the left and down, which in practice is insignificant.  The upshot of this is that it provides the following simple rasterization rules:

 (1)   horizontal edges are simply discarded;
 (2)   an edge which goes from scan line Ybotton to Ytop should generate x
        values for scan lines Ybottom through to Ytop - 1 (that is, missing the
        top scan line);
 (3)   similarly, horizontal segments should be filled from Xleft to Xright
        (with no pixels generated if Xleft = Xright).

Incidentally, in rules (2) and (3), whether the first or last element is ignored is arbitrary, and the choice is based around programming convenience.  The four possible permutations of these two rules define the sample point as one of the four corners of the pixel.  The effect of these rules can be demonstrated in the figure below. Here we have three adjacent polygons A, B and C, with edges a, b, c and d. The rounded x values produced by these edges for the scan shown are 2, 4, 4 and 7 respectively. Rule (3) then gives pixels 2 and 3 for polygon A, none for polygon B, and 4-6 for polygon C. Thus, overall, there are no gaps, and there is no overlapping.  Horizontal edges are discarded because the adjacent edges will have already contributed the x values to make up the segment.  Note also that, for the sake of simplicity, the scan conversion of this polygon was not performed strictly in accordance with the rasterization rules mentioned above).

Order of rendering

There are two basic ways of ordering the rendering of a scene.  These are: on a polygon-by-polygon basis, where each polygon is rendered in turn, in isolation from all the rest; and in scan-line order, where the segments of all polygons in that scene which cross a given scan line are rendered, before moving on to the next scan line.  In standard textbooks, this classification has the habit of becoming hopelessly confused with the classification of hidden surface removal algorithms.  In fact the order of rendering a scene places restrictions on which hidden surface algorithms can be used, but it is of itself independent of the method employed for hidden surface removal.  There are the common hidden surface removal algorithms that are compatible with the two methods:

  1) by polygon: Z-buffer
  2) by scan line: Z-buffer; scan line Z-buffer; spanning scan line algorithm

By-polygon rendering has a number of advantages.  It is simple to implement, and it requires little data active at any one time.  Because of this, it places no upper limit on scene complexity, unlike scan line rendering, which needs to hold simultaneously in memory, rasterization, shading, and perhaps texture information for all polygons which cross a particular scan line.  The main drawback of simple by-polygon rendering is that it does not make use of possible efficiency measures such as sharing of information between polygons (for example, most edges in a scene are shared between two polygons).  The method can only be used with the Z-buffer hidden surface algorithm which, as we shall see, is rather expensive in terms of memory usage.  Also, scan line based algorithms possess the property that the completed image is generated in scan line order, which has advantages for hardware implementation and anti-aliasing operations.

An important difference between the two rendering methods is in the construction of the edge list.  This has been described in terms of rendering on a polygon-by-polygon basis.  If, however, rendering is performed in scan line order, two problems arise.  One is that rasterizing all edges of all polygons in advance would consume a vast quantity of memory, setting an even lower bound on the maximum complexity of a scene.  Instead, it is usual to maintain a list of 'active edges'.  When a new scan line is started, all edges which start on that scan line are added to the list, while those which end on it are removed.  For each edge in the active list, current values for x, shading information and so on, are stored, together with the increments for these values.  Each time a new edge is added, these values are initialized; then the increments are added for each new scan line.

The other problem is in determining segments, since there are now multiple polygons active on a given scan line.  In general, some extra information will need to be stored with each edge in the active edge list, indicating which polygon it belongs to.  The exact details of this depend very much on the hidden surface removal algorithm in use.  Usually an active polygon list is maintained that indicates the polygons intersected by the current scan line, and those therefore that can generate active edges. This list is updated on every scan line, new polygons being added and inactive ones deleted. The outline of a polygon-by-polygon renderer is thus:

for {each polygon} do
   {construct an edge list from the polygon edges}
   for y  = ymin to ymax do
     for {each pair (xi, xi+1) in EdgeList [y] } do
        {shade the horizontal segment (xi, y) to (xi+1, y)}

while that of a scan line renderer is:

       clear active edge list
       for {each scan line} do
          for {each edge starting on that scan line} do
            {add edge to active edge list;
            initialize its shading and rasterization values
              and their increments}
          {remove edges which end on that scan line,
          parse active edge list to obtain and render segments;
          add the increments to all active edges}

Finally, it is worth pointing out that it is possible to achieve a hybrid of these two methods.  Often it is possible to split a scene up into a number of unconnected objects.  If the scene is rendered on an object-by-object basis, using scan line ordering within each object, then theadvantage of shared information is realized within each object, and there is no upper limit on scene complexity, only on the complexity of each individual object.