GameDev.netFast Phong Shading (OTMPHONG.DOC)

OTMPHONG.DOC - A new approximation technique for the Phong shading model based on linear interpolation of angles 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: 1) determine a normal vector at each vertex of a polygon, the same normal vector used in gouraud shading. 2) interpolate normal vectors along the edges of the polygon. 3) interpolate normal vectors across each scanline, so you have one normal vector for each pixel in the polygon. 3) 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
© 1999-2011 Gamedev.net. All rights reserved. |