5. Shading

5.1 Flat Shading

5.1.1 Z-flat

Z-flat is a very annoying-looking shading technique which can be implemented by giving a polygon the color value depending on the z coordinate average of the polygon's vertices:

color = max_col - (vertex1.z + vertex2.z + vertex3.z) / a,

where a is some suitable number dividing by which we can get the z average to the range 0..max_col. Because we're using a coordinate system in which the z-axis points to the direction to which you probably are looking right now ;) the z value grows as it goes farther so we must substract the value we've got from the biggest possible color value max_col.

5.1.2 Lambert Flat

Lambert Flat is a remarkably better-looking technique because it has a real light source. Additionally, we finally get some use for vectors which we tried to learn so hard at the beginning of this tutorial ;) The drawback of lambert flat is the truth that is flickers annoyingly.

The idea is the following: we present the light source as a vector. For each frame we calculate the normal vector of every polygon (by creating two vectors from the polygon and by taking the cross product of them) and calculate the cosine of the angle between the normal and the light source with the help of dot product -- the smaller angle, the more light. Using suitable coefficients we can fit this value in a desired range, for example in a RGB mode to the range 0..63 by multiplying the cosine by 63. Finally we check if the color value is negative. If it is, we change it to zero and the polygon is not seen. Some pseudo code again:

- LSi, LSj, LSk are light source's coefficients
- Ni, Nj, Nk normal's coefficients
function LambertFlat
< calculate the coefficients of the polygon normal >
// a = |N| * |LS|
a = sqrt(Ni*Ni + Nj*Nj + Nz*Nz) * sqrt(LSi*LSi + LSj*LSj + LSk*LSk)
if a<>0 (we don't want to divide by zero)
color = max_col * (LSi*Ni + LSj*Nj + LSk*Nk) / a
if color<0
color = 0
else
color = 0
return color
endf
This is a quite slow way (two sqrt's, many muls and a div per polygon), so a little speedup would be nice.

If the length of both of the vectors is one, we can forget most of the muls, the div, and both of the sqrt's (how to ensure that the length of a vector is one, see 1.1.3). We can precalculate the length of the light source vector; it remains the same even though we wanted to rotate it. With the normal vectors we can do the same thing but scale the vectors by max_col so we can save one mul more. Now we can rotate the normals as if they were coordinates, and the speedup is remarkable. So, in the init part:

- calculate the normal vector,
- calculate its length,
- multiply the vector by max_col,
- divide it by its length.

Now the function substitutes to the form

function LambertFlat
color = LSi*Ni + LSj*Nj + LSk*Nk
if color<0
color = 0
return color
endf

5.2 Gouraud Shading

5.2.1 Z-Gouraud

Z-gouraud works right like z-flat. It's a bit boring-looking but far better than z-flat which sucks badly X) So we take the z coordinate of a point, divide it by a constant, and substract the result from the maximum color value; no problem.

5.2.2 "Real" Gouraud

This works like Lambert Flat, but we take the angle between the vertex (rather than polygon) normal and the light vector.

Vertex normals are normals of the object's surface (the object being actually approximated using polygons) at the point, so they are in every vertex perpendicular to the object's (the real object, not the approximated one) surface. Calculating that kind of normal isn't easy, so we take just a nice approximation of the real normal by calculating the average of the normals of the polygons hitting the vertex:

1. set all vertex normals to zero
2. for each face, calculate the face normal and add it to the vertex normal for
each vertex it is touching
3. normalize all vertex normals

Not an easy job, implementing that, so here's some pseudo code again. The pseudo uses an another possible way:

1. find the faces touching each vertex
2. add the face's normal to the vertex normal
3. divide the vertex normals by the number of faces touching it (it's the average
you know)
4. normalize the vertex normals

This is of course a slower way, but I just hadn't time to code a pseudo of the faster technique :I Anyway, it works.

function CalcNormals
< calculate the normal of one plane; this function (c) Jeroen Bouwens if I remember right >
function calcnor(X1,Y1,Z1,X2,Y2,Z2,X3,Y3,Z3,NX,NY,NZ)
int RelX1,RelY1,RelZ1,RelX2,RelY2,RelZ2
RelX1=X2-X1
RelY1=Y2-Y1
RelZ1=Z2-Z1
RelX2=X3-X1
RelY2=Y3-Y1
RelZ2=Z3-Z1
NX=RelY1*RelZ2-RelZ1*RelY2
NY=RelZ1*RelX2-RelX1*RelZ2
NZ=RelX1*RelY2-RelY1*RelX2
endf
< face = polygon table, vertex = vertex table >
int i,a,ox,oy,oz
float cx,cy,cz,len,cn
for i=0 -> num_of_vertices-1
cx=0
cy=0
cz=0
cn=0
for a=0 -> num_of_faces-1
< if the face touches the vertex i >
if ((face[a][0]=i) or (face[a][1]=i) or (face[a][2]=i))
< the function returns to (ox,oy,oz) the normal vector >
calcnor(
vertex[face[a][0]].x,vertex[face[a][0]].y, vertex[face[a][0]].z,vertex[face[a][1]].x, vertex[face[a][1]].y,vertex[face[a][1]].z, vertex[face[a][2]].x,vertex[face[a][2]].y, vertex[face[a][2]].z,ox,oy,oz
)
< (cx,cy,cz) will carry the average of the plane normals, cn is incremented because it tells how many normals have been calculated into c* >
cx=cx+ox
cy=cy+oy
cz=cz+oz
cn+=1
endif
endfor
< if some polygon touches the vertex >
if cn > 0
< calculate the length of the normal >
len=sqrt(cx*cx+cy*cy+cz*cz)
if len = 0
len=1
endif
< normalize the vectors >
normal[i].x=cx/len
normal[i].y=cy/len
normal[i].z=cz/len
endif
endfor
endf

And the code is used like in Lambert flat.

Note! This technique doesn't work right in this way: if a face is made of many triangles (as in 3DS), it is added twice to the sum of face normals and gets thus too much weight. This may look annoying. The problem can be solved  by  checking if a normal value has already been used when calculating a vertex normal.

5.3 Phong Shading

5.3.1 Phong Illumination

Phong illumination means that we can make gouraud look like phong by fixing the palette. Ok, it looks better than ordinary gouraud. The formula of phong illumination is this:

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

where ambient is the color of a polygon when it's not hit by light (minimum color that is), diffuse is the original color of the polygon, and specular the color of a polygon when it's hit by a perpendicular light (the maximum color). x is the angle between the light vector and the normal, and it's allowed to change between -90 and 90 degrees. Why not 0..360 degrees? Because when the angle is over 90 degrees, no light hits the polygon and we ought to use the minimum value ambient. So we must perform a check, and if the angle is not in the required range, we give it the value 90 degrees, and cosine gets the value zero the color getting the value ambient. n is the shininess of the polygon (some people maybe remember it from rendering programs). Try and find a suitable value for each purpose!


5.3.2 Environment mapping

Many people mix real phong and env-mapping, but they're two very different things. In env-mapping we use a bitmap (environment map) from which we get color values for pixels. Using this technique, we can create different types of patterns to shading, and surfaces begin to look for example metallic. Env-mapping works like gouraud, but instead of calling a gouraud filler we call a texture filler, and instead of using the angles like in gouraud we use the x and y coefficients of the normals as indices into a bitmap. This technique doesn't allow moving light sources but they can be used with the following little trick:
- LS is the light vector
- N[0..2] are the vertex normals of a triangle
- cx1, cy1 etc are the coords into an env-map
- env-map is a 256x256-sized bitmap
if ( LS.k <= 0 ) ; we use the technique straight
cx1 = env_crd( N[0].i - LS.i )
cy1 = env_crd( N[0].j - LS.j )
cx2 = env_crd( N[1].i - LS.i )
cy2 = env_crd( N[1].j - LS.j )
cx3 = env_crd( N[2].i - LS.i )
cy3 = env_crd( N[2].j - LS.j )
else
a = N[0].i + LS.i ; addition instead of substraction
; - LS.i is the opposite to the one above
if (a<0)
a = a + 1 ; move to the opposite side
else
a = a - 1
cx1 = env_crd( a ) ; convert
a = N[0].j + LS.j
if (a<0)
a = a + 1
else
a = a - 1
cy1 = env_crd ( a )
a = N[1].i + LS.i
if (a<0)
a = a + 1
else
a = a - 1
cx2 = env_crd( a )
a = N[1].j + LS.j
if (a<0)
a = a + 1
else
a = a - 1
cy2 = env_crd ( a )
a = N[2].i + LS.i
if (a<0)
a = a + 1
else
a = a - 1
cx3 = env_crd( a )
a = N[2].j + LS.j
if (a<0)
a = a + 1
else
a = a - 1
cy3 = env_crd ( a )
endif
texture( x1, y1, x2, y2, x3, y3, cx1, cy1, cx2, cy2, cx3, cy3 )
function env_crd ( float value )
a = value * 127 + 128
return a
endf
The function env_crd converts a normal coefficient (at the range -1..1) to a coordinate into the env-map (0..255, brightest in the center).

At the beginning we checked if the z coefficient of the light vector is positive or negative. This because positive and negative coefficients require different calculations; positive values require a bit fixing. With negative values of the coefficient we can calculate the coordinates into the env-map like this (as in the pseudo code): we substract the normal x and y coefficients from the light coefficients before transforming them into the env-map space. Where's the z coefficient? We don't need it, but because these vectors should be unit vectors, we can give it weight by decrementing the values of x and y coefficient: for example if the x and y coefficients are both 0.5, the z coefficient has the weight 0.7 (vector length: 0.5^2 + 0.5^2 + 0.7^2 = 1).

This technique doesn't work with light sources having a positive z coefficient, they require the following: the z coefficient is positive and the vector (-LS.i,-LS.j,-LS.k) is the opposite for the light vector. If we fool the routine to think the light vector to be the opposite (at the other side), we can get exactly the opposite result as we need. Why like this? This opposite light vector has of course a negative z coefficient and we can use the technique above. We can get the right result from the opposite one by moving the values at the center to the edges and vice versa -> tada: we've got the original light vector!

5.3.3 "Real" Phong

[Chem] For the One and Only Phong shading we need the following four vectors:
- light to surface
- surface normal
- camera to surface
- the reflection vector (the vector that is being computed)
In the loop, we interpolate the upper three vectors, and the brightness value can be found as follows:
The light hits the surface and reflects in a way that the angle between the light and the normal equals the angle between the reflection ray and the normal (b's in the picture). x = the angle between the reflection ray and the camera vector.

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

Note the locations of b and x. Ambient is the color value of a surface (this is the same for every pixel in the surface but may vary from object to object) when there's no light hitting the point at all. Diffuse is the texel value (bitmap pixel color) at the current point, specular is the light value reflecting from the object depending on the angle between the reflection ray and the camera, and n is the shininess of the object.

5.4 Light Source Handling

These techniques work with all shading techniques. Actually they're very straightforward. So straightforward I derived them from the beginning by myself :)

5.4.1 Freely moving lightsources

The only problem is, how to keep the light vector up-to-date. How could it be done? Ha, piece of cake! We save only the location of the light, calculate the vector from this point to the vertex to be drawn (or any other point of which the normal vector is), and normalize it. That's it! The new light vector is ready for use.

5.4.2 Spotlights

..I hear a voice whining that the technique above works only with point light sources, but not with spotlights. So I thought at first. But no problem: they can actually be implemented very easily. We just also save the original light vector and the angle of the spotlight. When we've built the new light vector, we check if the angle between it and the normal vector is greater than the angle of the spotlight. If yes, the light is round zero (or perform a nice little ratio between the angles and you get a soft-edged spotlight!), otherwise the value can be get normally from the angle between the light vector and the normal (or try your own tricks!).

Don't wonder if the edges of your spotlight look weird or it bugs in some other way when you're using gouraud or flat shading. The problem is that when we're interpolating linearly between vertices, different polygons get different-length shades, and the spotlight may look quite annoying. Any good solutions for the problem would be appreciated ("real phong" is not accepted ;) Chem suggested splitting the polygons into smaller ones when going too close to them. Could work, but I can't say anything about the speed or reliability.

5.4.3 Light attenuation

Just some more basic math: we calculate the distance between every vertex and the light source, and make the light intensity somehow dependent on the distance. Then we only calculate :)
; for each vertex in face
for a=0 -> num_of_vertices-1
; calculate the new light vector
l_vector.x = vertex[a].x_coord - light.x_coord
l_vector.y = vertex[a].y_coord - light.y_coord
l_vector.z = vertex[a].z_coord - light.z_coord
distance = sqrt((l_vector.x)^2 + (l_vector.x)^2 +
(l_vector.x)^2)
; normalize the new light vector
l_vector.x = l_vector.x / distance
l_vector.y = l_vector.y / distance
l_vector.z = l_vector.z / distance
; calculate brightness
brightness = 1 - (distance/light.fadezedo)^fogness
; calculate the light values
light_at_vertex[a] = gouraud(vertex1.normal,brightness)
endfor
function gouraud (param normal, brightness)
color = ( l_vector.x*normal.x + l_vector.y*normal.y +
l_vector.z*normal.z ) * brightness
if color<0
color = 0
else if color>255
color = 255 ; or your maximum color...
return color
endf
Ok. Light.fadezero gives us the distance the light is exactly zero. Fogness is a scene constant (Chem thinks it's not a very logical name for the variable :) which tells how the light dims. Values between 0.5 and 2 should do the job for most purposes.

This is of course not the one and only way, there sure are many others, too. I just happen to think this is the best one (yes, I have tried the 1/distance^2 method :)