Jump to content
  • Advertisement
  • Remove ads and support GameDev.net for only $3. Learn more: The New GDNet+: No Ads!

  • 07/16/99 05:58 PM
    Sign in to follow this  

    Fast Phong Shading (OTMPHONG.DOC)

    Graphics and GPU Programming

    Myopic Rhino
    <%Topic="Fast 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 T), where T is the smallest angle
            between the two vectors.
    
            u = pixel normal vector
            v = light vector
    
            u dot v = cos T * |u| * |v|
    
                     u dot v
            cos T = ---------
                    |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 T (*)
            |
            |
            |*    *
            |          *
            |             *
            |                *
            |                   *
            |                     *
            |                       *
            |                         *
          y |                          *
            |                           *
            |                            *
            |                             *
            |                              *
            |                               *
            |                                *
            |                                 *
            |                                  *
            |                                   *
            +------------------------------------------
                                T
    
                    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 T (*)
            |      flat shading approximations of light intensity shown as (X)
            |
            |*XXXX*XX               dT  (angle between normal vectors)
            |          *       -------------
            |        XXXXX*XXXX            |
            |                *             | dI  (change in intensity)
            |                   *          |
            |                  XXX*XXXXXX  |
            |                       *
          I |                         *
            |                          *
            |                           *XXXXXX
            |                            *
            |                             *
            |                              *
            |                               *
            |                                *
            |                                 *XXXXX
            |                                  *
            |                                   *
            +------------------------------------------
                                 T
    
                    This graph tells us something that we already know by
            practical experience, that flat shading is very inaccurate for large
            values of dT, and much more accurate for small values of dT.  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 T (*)
            |        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 dT
            |             XXX   *              |
            |                XXXXX*  --------------+
            ||____________________|X*              |
          I |        dT              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*  |
            +------------------------------------------
                               T
    
                    This graph tells us that gouraud shading is very accurate
            as T->90.  However, if T is small and dT is large, gouraud shading
            will look like an obvious linear approximation.  This can be avoided
            by using smaller values of dT (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 T (*)
            |            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
            +------------------------------------------
                                 T
    
                    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 T.
    
    
    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 T 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(T) 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(T), and if this other value changed in a linear
            fashion, it would be possible to create a lookup table that related
            cos(T) to this other value.  After a bit of deep thinking, I realized
            that I was staring right at such a value, T!  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
             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. T.  You will find that for a small dT, gouraud shading
            looks very much like phong shading.  However, phong shading can
            achieve this result with a much larger dT, 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...
    
    


      Report Article
    Sign in to follow this  


    User Feedback


    There are no comments to display.



    Create an account or sign in to comment

    You need to be a member in order to leave a comment

    Create an account

    Sign up for a new account in our community. It's easy!

    Register a new account

    Sign in

    Already have an account? Sign in here.

    Sign In Now

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!