Copy Link

Add to Bookmark

Report

Technique for the Phong shading based on linear interpolation of angles

A new approximation technique for the Phong shading model based on linear interpolation of angles

@DrWatson

Published in

atari

· 11 months ago

released 3-30-95
by Voltaire/OTM [Zach Mortensen]

email: mortens1@nersc.gov

IRC: Volt in #otm, #coders

INTRODUCTION

Realtime phong shading has always been a goal for 3d coders, however the massive amount of calculations involved has (until recently) hampered progress in this area. When I first heard the term 'realtime phong shading' mentioned about 6 months ago, I laughed to myself at what I perceived was an oxymoron. In my experience at the time (derived from reading several 3d documents), phong shading required a tremendous amount of interpolation and one square root per pixel. Even with lookup tables for the square root function, there was no way that this algorithm would be fast enough to use in realtime. Early reports from other coders attempting realtime phong shading proved this, the fastest code I heard of could draw around 1500 triangles per second.

Phong shading never really was a goal of mine. I am a pretty lazy person, I could think of a thousand ways I would rather spend my time than implementing an inherently slow algorithm in my code and trying to optimize it. Until about a week ago that is, when I received a little demo called CHEERIO by Phred/OTM. Phred and I have been good friends for quite awhile, and we both write vector code. We have helped each other improve the speed of our code dramatically by sharing our ideas, 2 heads are definitely better than 1! Anyway, there were rumors flying around that CHEERIO was phong shaded, when in reality it was really nice gouraud shading. I took a close look and...well, it looked like phong but Phred wasn't around to correct us, so I went on believing he had coded a phong fill that was as fast as my gouraud fill. Part of the reason Phred and I have made our code so fast is competition, neither of us can stand being outdone by the other. So whether I wanted to or not, I had to come up with a fast phong fill SOON if I were to save face.

The fastest method I knew of was using a Taylor series to approximate color values. This method involves a fairly fast inner loop with a lot of precalculation. It also requires a thorough knowledge of calculus. Believe me, doing Taylor series on your homework is a lot easier than trying to implement one in the real world for some strange reason. So that is where I started, I was deriving the Taylor approximation for phong shading when I stumbled upon what seemed to me an obvious shortcut that would make phong filling nearly as fast as gouraud filling. I also believe I am the first to come up with this method, since I have seen no articles about it, and I have yet to see realtime phong shading in a demo or game.

OK, now on to the fun stuff...

THE PHONG ILLUMINATION MODEL

This is not a text on phong illumination, but on phong SHADING. They are two very different things. Whether you use phong shading or not, you can use phong illumination with your lambert or gouraud shading to make your colors look more realistic. I don't want to get into how this formula is derived, so I will just give you the low down dirty goods.

color = specular + (cos x) * diffuse + (cos x)^n * specular

Make sure you set up your palette in this way. In a nutshell, the ambient component defines the color of an object when no light is directly striking it, the diffuse component defines the color of the object, and the specular component defines the color of the highlight made when light strikes the object directly. x should have a range of 0 to 90 degrees, since that is the range of angles possible when light intersects a visible plane. The power n in the specular component defines certain attributes about the material, the greater the power n, the shinier the material will appear to be (i.e. the specular highlight will be smaller and brighter as n increases).

THE PHONG SHADING MODEL

The idea behind phong shading is to find the exact color value of each pixel. In its most common form, the phong shading model is as follows:

determine a normal vector at each vertex of a polygon, the same normal vector used in gouraud shading.
interpolate normal vectors along the edges of the polygon.
interpolate normal vectors across each scanline, so you have one normal vector for each pixel in the polygon.
determine the color at each pixel using the dot product of the normal vector at that pixel and the light vector, the same method used in gouraud and lambert shading. Since the interpolated normals are not of constant length, this step requires a square root to find the length of the normal.

This shading model produces impressive results. A new color is calculated for each pixel, and the color gradient across a plane is non linear.

However it is also VERY SLOW if implemented as it is shown here. In order to linearly interpolate a vector, one must interpolate x, y, and z coordinates. This task is not nearly as time consuming as the dot product, which requires 4 multiplies, 2 adds, a divide and a square root per PIXEL. A few optimizations can be performed that eliminate one multiply and replace the square root with a table lookup, but 3 multiplies and a divide per pixel are far too slow to be used in realtime.

OPTIMIZING THE PHONG SHADING MODEL

Lets mathematically break down the phong shading model. After all is said and done, you are left with the dot product of the pixel normal vector and the light vector divided by the product of the magnitudes of these two vectors. Another way to express this value is (cos α), where α is the smallest angle between the two vectors.

 u = pixel normal vector 
 v = light vector 

 u dot v = cos α * |u| * |v| 

          u dot v 
 cos α = --------- 
         |u| * |v|

So the dot product of a normal vector and a light vector divided by the product of the magnitudes of the two vectors is equal to the cosine of the smallest angle between the two vectors. This should be nothing new, it is the same technique used to find color values in the lambert and gouraud shading techniques. Lets attempt to graphically represent what is going on with phong, gouraud and lambert shading.

                                graph of y = cos α (*) 
        | 
        | 
        |*    * 
        |          * 
        |             * 
        |                * 
        |                   * 
        |                     * 
        |                       * 
        |                         * 
      y |                          * 
        |                           * 
        |                            * 
        |                             * 
        |                              * 
        |                               * 
        |                                * 
        |                                 * 
        |                                  * 
        |                                   * 
        +------------------------------------------ 
                            α

The phong shading model states that the intensity of light at a given point is given by the dot product of the light and normal vectors divided by the product of the magnitudes of the two vectors. Flat shading is the roughest approximation of this, planes are rendered in a single color which is determined by the cosine of the angle between the plane's normal vector and the light vector. If we graph the intensity of light striking flat shaded planes, we should find that they roughly form a cosine curve, since the color values at certain points are determined by the cosine of the angle between two vectors

                          graph of Intensity = cos α (*) 
        |      flat shading approximations of light intensity shown as (X) 
        | 
        |*XXXX*XX               dα  (angle between normal vectors) 
        |          *       ------------- 
        |        XXXXX*XXXX            | 
        |                *             | dI  (change in intensity) 
        |                   *          | 
        |                  XXX*XXXXXX  | 
        |                       * 
      I |                         * 
        |                          * 
        |                           *XXXXXX 
        |                            * 
        |                             * 
        |                              * 
        |                               * 
        |                                * 
        |                                 *XXXXX 
        |                                  * 
        |                                   * 
        +------------------------------------------ 
                             α

This graph tells us something that we already know by practical experience, that flat shading is very inaccurate for large values of dα, and much more accurate for small values of dα. This means that the shading appears smoother when the angle between normals (and therefore between planes) is very small.

Now lets consider gouraud shading. Gouraud shading is a linear interpolation of color between known intensities of light. The known intensities in gouraud shading are defined at each vertex, once again by use of the dot product. In this case, the normal vector at each polygon vertex is the average of the normal vectors (the ones used in flat shading) for all planes which share that vertex. Normals of planes which are greater than 90 and less than 270 degrees from the plane containing the vertex in question are not considered in the average because the two planes are facing away from each other. If we plot interpolated intensities used in gouraud shading against the cosine curve, it is evident that gouraud shading is a much more accurate approximation than flat shading.

                        graph of Intensity = cos α (*) 
        |        interpolated light intensities shown as (X) 
        | ---------------------------------+ 
        |*X   *                            | in this region, the linear 
        |  XXXX ---*--------+              | approximation is always going to 
        |      XXX    *     | dI (error)   | be inaccurate without a very 
        |         XXXX --*--+              | small value for dα 
        |             XXX   *              | 
        |                XXXXX*  --------------+ 
        ||____________________|X*              | 
      I |        dα              X*            | 
        |                         X*           | in this region, a gouraud 
        |                          X*          | approximation is nearly 
        |                           X*         | perfect because cos x is 
        |                            X*        | nearly linear 
        |                             X*       | 
        |                              X*      | 
        |                               X*     | 
        |                                X*    | 
        |                                 X*   | 
        |                                  X*  | 
        +------------------------------------------ 
                           α

This graph tells us that gouraud shading is very accurate as α->90. However, if α is small and dα is large, gouraud shading will look like an obvious linear approximation. This can be avoided by using smaller values of dα (i.e. use more polygons to fill in the gaps in the interpolation). With enough polygons, gouraud shading can be 100% correct.

Phong shading is the most correct method of shading because it is not an approximation, distinct colors are determined for each pixel. These values follow the cosine curve exactly, because the intensity of each pixel was calculated using a dot product, which eventually yields the cosine of the angle between the plane at that pixel and the light vector. If we plot phong shading intensities with the cosine curve, we find that the values follow the function exactly.

                        graph of Intensity = cos α (*) 
        |            phong light intensities shown as (X) 
        | 
        |X    X 
        |          X 
        |             X 
        |                X 
        |                   X 
        |                     X 
        |                       X 
        |                         X 
      I |                          X 
        |                           X 
        |                            X 
        |                             X 
        |                              X 
        |                               X 
        |                                X 
        |                                 X 
        |                                  X 
        |                                   X 
        +------------------------------------------ 
                             α

Once again, shadings calculated using the phong model follow the cosine curve, because the dot product between the normal vector at each pixel and the light vector can be simplified to a function involving cos α.

TAYLOR APPROXIMATIONS

Now that we know a function which gives the intensity of light at a given pixel, we need to find a fast way to evaluate that function. Most people seem to know that Taylor series can be used for phong shading, but I have never met anyone that was able to tell me that the cosine function would be the function that is approximated. The fact that vector coders are afraid of math is disturbing to me.

The Taylor approximation for cos(x) is given by the following series:

             x^2   x^4   x^6                      x^(2n) 
 cos x = x - --- + --- - --- + ... + (-1)^(n-1) * ------ 
              2!    4!    6!                       (2n)!

Actually I think that is a Maclaurin series, which is nothing more than a Taylor series expanded about the point x = 0. In any case, you can use any number of terms in a Taylor series to approximate a function. The more terms you use, the more accurate your approximation will be...and the slower your approximation will be. The first two terms of the series for cos x are sufficient to give an accurate approximation from x = 0 to x = 90, which are the limits of α between the light and visible facets.

This is about as far as I got with the Taylor approximation method for phong shading. Once I got to this point, the proverbial light bulb clicked on inside my head, and I forgot all about Taylor series because I came up with a faster method.

LINEAR INTERPOLATION OF ANGLES

To set the scene for you, I was riding the bus to school about at about 8:00 in the morning when I thought I would do a bit of work on the phong algorithm. The bus ride is about 30 minutes and is usually devoid of any excitement, so I whipped out my trust pad of graph paper and started grinding out formulas. I got really excited when I arrived at the Taylor approximation, but I just about jumped through the roof when this thought entered my mind.

I realized that the Taylor approximation for phong shading basically interpolates values along the curve I = cos(α) just as gouraud shading linearly interpolates values, except the values for phong shading happen to fall directly ON the cosine curve. The problem is that the cosine curve is not linear, therefore phong interpolation is much more complicated than gouraud interpolation.

Then I stepped back and looked at the problem from another angle (punny). If it were possible to interpolate some other value related to cos(α), and if this other value changed in a linear fashion, it would be possible to create a lookup table that related cos(α) to this other value. After a bit of deep thinking, I realized that I was staring right at such a value, α! The angle between the light vector and the normal vector at each vertex of a plane changes in a linear fashion as you go from one vertex to the next, and from one edge of the plane to the next across each scanline.

As soon as it hit me, this idea made perfect sense. The phong shading model calls for normal vectors to be linearly interpolated from vertex to vertex and from edge to edge. When I thought about this a bit further, it seemed totally ridiculous. The actual <x,y,z> coordinates of these normals do not matter one bit, only the angle between the vector defined by these coordinates and the light vector. Why interpolate 3 coordinates per pixel when they are just an intermediate step in finding the angle between two vectors?

So angular interpolation eliminates the interpolation of a whole vector. But that's not all, it also eliminates the dot product which was previously needed to find the cosine of the angle between the normals and the light. Without the dot product or vector interpolation, there is nothing left of the traditional method of phong shading. All that needs to be done is interpolate angles across the plane, and look up the cosine of those angles in a lookup table. Once you know the cosine, the rest is easy.

Using this method, an existing gouraud fill can be converted to a phong fill very very easily. Instead of interpolating colors across the plane, interpolate angles instead. If you are smart about the way you express your angles, they can be represented in a single byte. Remember that the only possible values for the smallest angle between a normal vector and a light vector are 0 to 90 degrees.

After you have interpolated an angle and looked up its cosine, all you need to do is plot a pixel of the correct color. The color calculations for each pixel are the same as those for lambert and gouraud shading. Multiply the cosine by the number of colors in the gradated palette range and add the result to the base color of the range.

Of course, you need to determine the angle between the light and the normal vectors at each vertex. This can be accomplished by the inverse cosine function. By taking the inverse cosine of the cosine, you get the angle as a result. Try to remember your trig classes.

LIMITATIONS

Angular interpolation is correct in 99% of all possible cases. The only cases when it will not be correct is when the angles at any two or more vertices are equal. Interpolated vector phong shading will display a specular highlight inside the plane in such a case, but interpolated angle phong shading will render the plane in a solid color because the difference between the angles at the vertices is 0, there will be no change in the angle across the plane.

CRITICISM AND RESPONSE SESSION

The preliminary release of demos incorporating this technique were met with a bit of criticism, most of which was caused by ignorance. Here are a few common criticisms of this technique and my responses.

"You are interpolating something linearly, and linear interpolation is gouraud shading"

Do your homework. The phong model calls for linear interpolation of normal vectors, and it is obviously not gouraud shading.

"It looks a lot like gouraud shading"

Yes it does. Refer to the section where I plotted intensities based on various shading techniques, and take a look at the graphs of Intensity vs. α. You will find that for a small dα, gouraud shading looks very much like phong shading. However, phong shading can achieve this result with a much larger dα, which means less facets.

"I see no specular highlight"

The first version I released used a linear palette, not a palette based on the phong illumination model. Without the phong illumination model, it is very hard to make specular highlights look correct. The palette has now been corrected to conform to the phong illumination model.

"You still can't get a highlight in the center of a single polygon"

Well, I think that the speed of this method is a reasonable tradeoff. Specular highlights appear between polygons with this method, and the difference is not too noticeable.

"The specular highlights are no different than gouraud specular highlights"

Take a closer look. With gouraud shading, specular highlights are gradated in a linear manner. With phong shading, the gradation of colors is nonlinear because it follows the cosine curve.

CLOSING COMMENTS

Angular interpolated phong shading is new as far as I know. If you decide to use this technique in any of your code, please give me appropriate credit. I am not asking for a cut of your royalties, just to have my name mentioned somewhere. I have always made it a point to give credit where credit is due, and I would appreciate if you would do the same. Someone along the line actually has to put in some hard work to develop the algorithms that we all use.