Lighting, shadow casting

Lighting

This is computed thanks to the normal vectors of each vertex of a face. Roothly speaking, the more the normal vector points to the light, the lighter is the pixel (dot product).
3D cards does this work for us.
In the case of Goureau shading, the lighting is computed in each vertex of the faces, then it is interpolated for each pixel of the face.
In the case of Phong shading, the normal vector is interpolated for each pixel, then the lighting is computed. This lighting computation can be pre-computed in a phong-map.

EDIT: see the documentation about per pixel lighting and bump mapping

Shadow casting

Three methods exist, but none is fully usable. This problem is today's main work in 3D rendering.

Shadow Buffer (Shadow map method 1)

We render in a Z-Buffer the scene from the light point of view

Then when rendering from the camera point of view, for each pixel we compute his position (x',y',z') in the previous Z-Buffer. If the Z value in the Z-Buffer is less than z', this pixel is in shadow. Otherwise z'=Z and the pixel is lighted.

Id-Buffer (Shadow map method 2)

A nice speed up of the Shadow-Buffer.
Instead of computing two Z-Buffers, we will use identifiants : each object (or face) gets a unique number. From the light point of view we render an Id-Buffer, telling for each pixel which object (or face) is located here. Then from the camera point of view we compare the object's (or face's) id with the one located in the Id-Buffer at the place the screen pixel would be.

This seems to be the best shadow casting algorithm for software 3D engines, but is not adapted to 3d hardware acceleration: the 3d card use float values, where an id can be stored inaccurately.

Shadow Volumes

We need an hardware Stencil Buffer. This buffer make it possible to switch on/off the rendering of every pixel of the screen.

Here is what we want to render. the triangle will cast a shadow on the ball. We first render a Z-Buffer of this.
The ZBuffer is set so as to enable Z comparison but to disable Z writing.
We compute the triangle's silhouette.
In the Stencil Buffer, we put 1 for each pixel in the blue polygons (projection of the edges from the light, displayed only if ccw oriented), which are made by projecting one segment of the silhouette at a very far distance from the light, where Z from our plane <= Z from the Z-buffer..
We put 0 for each pixels in the green polygons (cw oriented), where Z from our green plane < Z from the Z-Buffer.
Then each pixel marked as 1 in the Stencil-Buffer is rendered as in shadow, each pixel "0" is rendered as highlighted.

Note that in the special case where the camera is inside the shadow volume, this technic will not work as the ccw and cw faces does not intersect on the screen.

Inverted/Reversed Shadow Volumes (alias John Carmack's trick)

This is very similar to the shadow volumes, but this manages the special case where the camera is inside the shadow volume.

Here is what we want to render. the triangle will cast a shadow on the ball. We first render a Z-Buffer of this.
We compute the triangle's silhouette.
The ZBuffer is set so as to enable Z comparison but to disable Z writing.
In the Stencil Buffer, we put 1 for each pixels in the green polygons (projection of the edges from the light, displayed only if cw oriented), where Z from our green plane > Z from the Z-Buffer.
We put 0 for each pixel in the blue polygons (projection of the edges from the light, displayed only if ccw), which are made by projecting one segment of the silhouette at a very far distance from the light, where Z from our plane >= Z from the Z-buffer..
Then each pixel marked as 1 in the Stencil-Buffer is rendered as in shadow, each pixel "0" is rendered as highlighted.

If we render the side polygons, and the caps (the original triangles and their projected clones), we render a closed volume instead of a silhouette, and in this case such shadowing method is useable in every cases.

Pros and Cons of each method

Shadow buffers can even operate on slow computer. They can support Alpha transparency - like the "holes" in a simple tree texture. Soft shadows can be made with shadow mapping. But they are quite pixelized.

Shadow Volumes are very accurate. They are the more realistic tool at the moment. But they can not use Alpha transparency, and they need a powerful 3d acceleration for complex scenes. Slow soft shadows for the moment.

In the case of the shadow maps, we first hilight everything, then we darken shadow areas. This is physically incorrect, resulting in wrong result. Using shadow volumes, we can hilight only what can be reached by light, which is the way to go.

Improving from the simple shadow casting to the full shadowing system

Ok we can now cast simple shadows for a single simple object, but we still need to include this properly in our engine. We could just mark in the Stencil-Buffer every areas where there are shadows, and render them with a dark rectangle. But this would result in unrealistical artifact, as area that are in one light's shadow would not receive light from other lights.
The difficulty is also to shadow a non-concave object:

Some parts of the object will be self-shadowed
Some parts of the decor will be "shadowed many times", for example the shadows casted by a human body and one of its arms can intersect. As a result we cannot use the inverse Stencil operator.

A solution of the second issue is to project the object to a plane, using a parallel projection matrix. New issue: the object cannot shadow itself. And still, two object can generate shadows that will intersect.
Here is my solution:

Render the whole scene without any light (only ambient lighting)
For each light:
- Clear the stencil buffer
- For each object
  - Compute the position of the light in the object space
  - Compute the shadow volume of the object
- Render the scene with this light switched on, only where the stencil buffer is equal to zero, while adding the resulting rendering to the previous one in order to add lighting from different lights (Blend using the GL_CONSTANT_COLOR to do so:
  glBlendColor( lightcolor );
  glBlendFunc( GL_CONSTANT_COLOR, GL_ONE );).

On a GeForce 2, this gives you for each light :

2 passes to compute the shadow volume (front pass and back pass)
1 passe for diffuse lighting: TU0 = DOT3 to compute lighting, TU1 = MODULATE to multiply lighting and color texture
1 passe for specular lighting: TU0 = DOT3 to compute lighting, TU1 = MODULATE to multiply lighting and color texture

Bottleneck: every single bits of the Stencil Buffer might be necessary. They will not be usable for anything else (like mirrors).