SuperHack/SuperHack CD.bin/CODING/GRAPHICS/PHONG.ZIP/PHONG.TXT

Text File | 1996-04-26 | 24.7 KB | 933 lines

        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 -

        [e-mail]


        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

        <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.



GREETS


        Siri                    - you are the love of my life

        OTM                     - I...have...nothing...to...say

        Phred/OTM               - good vector conversation

        Rich Beerman            - our game will rule

        Darkshade               - for always being helpful

        THEFAKER/S!P            - infinite humility :)

        Sami Nopanen            - cacheman...

        Tran and Daredevil      - PMODE/W, gotta love it

        VLA                     - for not releasing any more 3d docs :)


        all my #coders buddies

        bri_acid

        MainFrame

        StarScream

        ae-

        fysx

        phoebus

        doom

        Moomin

        Simm

        LiveFire

        MArtist

        Zed-

        Omni

        ior

        Kodiak_

        Saeger

        anixter

        Hasty


        and everyone else I forgot...