home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Collection of Hack-Phreak Scene Programs
/
cleanhpvac.zip
/
cleanhpvac
/
FAQSYS18.ZIP
/
FAQS.DAT
/
OTMPHONG.DOC
< prev
next >
Wrap
Text File
|
1995-04-08
|
24KB
|
516 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 -
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
<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...
