Shadows
Introduction
Shadows add a lot of realism to a 3D engine. They help to impart a good deal of information about movement, lighting and shape. Shadows are your friend. Use them wisely.
Fake Shadows
Perhaps the easiest shadows to make are fake shadows. Amongst the easiest are casting them to the floor. An easy method is to project your triangle to the floor (Y = 0 in most 3D engines). Then do a simple divide by Y, so the higher an object is, the smaller the shadow. Simple, but effective. This doesn't take into account the direction of the light source. Again, this is easy to do:
s.x = p.x - (p.y / l.y)*l.x;
s.z = p.z - (p.y / l.y)*l.z;Where s is the shadows vertex, p is the point, and l is the light source. Very easy to code, and it works well. However, it doesn't really work well for much else than flat planes.
Shadow Z-Buffer
I also know another method of generating shadows. This requires the use of 2 z-buffers though. The basic idea is that you generate two z-buffers: one from the point of view of the camera, and one from the point of view of the light. When you come to render, you need to do the following:
- If point is not visible, simply move on the the next pixel
- Map co-ordinate from 'camera space' into 'light space'
- Project down to 2-D again.
- Use x' and y' to index into the shadow Z-buffer
- If z is greater than shadow zbuffer, then a surface is nearer to the point than the light - so shadow it, using a 'shadow intensity'
However, this method is pretty damn slow, as you might imagine.
Shadow Volumes
Another method of implementing shadows is by the use of a shadow volume. A shadow volume is an infinite volume of space, where light cannot be seen, because it is being blocked by a polygon. Making the volume is simple enough: Make vectors from the origin of the light, through the vertices of a polygon. Normalize them, and hey presto, a simple, infinite volume. These are now rays.
Their equation would be:
D = Direction
O = origin of light
L = light source point
Vertex = polygon vertex
D = vertex - light
O = vertex
Ray = O + D*infinity
For this to be useful, it needs to lie withing the view volume. So, clip it to the view volume. Clipping lines against planes is covered somewhere within these pages. You won't be able to classify the two endpoints against the plane however: you'll have to find the intersection of the line and plane, and find out whether that is a valid part of the volume. I.E. the volume cannot be in the portion of space between the polygon and the light source, can it? Once the volume is clipped, you'll end up with a set of polygons, which will define the shadow volume.
When it comes to rendering, it becomes more interesting. Consider the interaction of the shadow volumes, with a ray shooting from the viewers position, for a given pixel. If a point on that ray is withing a shadow volume, then the point is clearly in shadow. But what if the point is between two shadow volumes? Then it is not in shadow! So, you will need some kind of flag. The flag will start at FALSE (point not in shadow). When it enters a shadow volume, it will become TRUE, and when it leaves, it will become FALSE again.
Still, for a complex scene, this system will also be quite slow. The number of shadow polygons increases sharply as the number of polygons and light sources increases. Perhaps such issues are why realtime systems still only use fake shadows ...
"Shadow Slabs"
This is a little idea I've been brewing in my mind... it works similar to the shadow volumes above, but you can have a model half in shadow, half out of shadow.
The idea is that we perform an extensive pre-process, and generate "slabs", which define where an area comes into shadow/goes out of shadow. This would be an extensive pre-process, calculating for all of the lights and polygons in the scene. However, when it is complete, you would have a list of polygons ("Shadow Slabs"), which define the borders of the shadow. Very similar to shadow volumes.
Then, when rendering, you would clip against these slabs, in 3D. Then, the one half of the object will be considered as "illuminated", so its just rendered as normal. The other half will be considered as "shadowed", and this is where you can choose what to do next. If there shadowed area has zero lighting, then you can just discard the polygons -- a crafty piece of culling. However, if the area is lit, then you can just darken the polygon, say divide the colours at the triangle vertices by 2, 4, 8 whatever, for gouraud shading. The advantage of this is that you can have models emerge/submerge into shadowed volumes, with little extra processor power. With a well designed engine structure, I think it could most definitely be done real time. Any thoughts? Has this already been done? It wouldn't surprise me if it had. I'd be interested if anyone implemented such a system though.
Realtime volumetric lighting
Heres a quick and easy way of doing volumetric lighting in realtime. For those who don't know, volumetric lighting works along the lines of calculating the volume of space that is illuminated by a given light. So, when an objects falls into that volume, it is illuminated by the light, and when it comes out, it is not.
The algorithm is very simple. We just invert shadow z-buffers. What we do is for each directional light source, we render a z-buffer from its point of view. The frustum for this view will define the volume of light, and the z-buffer will carry the depth information needed to correctly identify whether or not a vertex is lit. Then, when we come to light a vertex, we simple transform it into the camera space for the light (light-space), perspective project it, if it lies within the lights frustum. Then, we simply do a z-test against the buffer. If the vertex Z is less than the corresponding entry in the z-buffer, then we can light it. If it is not, then the vertex is not visible, so we must not light it. The z-buffer for the light needn't be rendered at too high a resolution, say maybe 64x64. In addition, this trick can be modified to run in realtime, for dynamic lights. Additionally, if you rasterise the polygon onto the z-buffer for the light, you can also work out good shadows casting onto walls and floors. If the polygon over-writes light z-buffer pixel i, then you can transform a polygon corresponding to that pixel, into world space, and draw it, using the z information. So, we'd take the pixel z, and its neighbours z. We also take the 2d co-ords of those points in light z-buffer space. We can now project back into 3d co-ords, then back into world co-ords via the camera matrix for the light. We could then use these 4 points to define a shadow polygon, and fill it as normal. The quality may not be that high, because the shadows will be staircased, but it should work.
Tom Hammersley, tomh@globalnet.co.uk
References: 3D Computer Graphics 2e, Computer Graphics: Principles & Practice
