Hello.
As discussed with mattn on IRC yesterday I'd like to tackle dynamic shadows for entities in UFO:AI. After some thinking and digging through the source-code - and realizing that this is a somewhat more difficult task than I first thought :-). Still I think it would add a lot of atmosphere to the game... so - here are the thoughs I've come up with so far.
Oh, and I should probably add a disclaimer - I'm not really a graphics programmer. I went through the Peroxide trainers when I was a child - and a few years later I eventually understood them. I played around with the Q1 engine a bit a couple of years ago, did a few OpenGL when I needed it (did a 2D vector render library 2 years ago) but I'm rather new to most of this, so bear with me. This will probably read more like a tutorial at some points. :-)
I'll first summarize the different kinds of shadows one could consider:
- Static lightsource, obstructed by static objects, casting a shadow on static objects. (SSS)
This one we already have - and for compatibility with older hardware, the performance benefits and technical reasons you can probably think of we should stick to them as is.
- Static lightsource, obstructed by dynamic objects, casting a shadow on static objects. (SDS)
This is the one I want and the issue which got me into this.
- Static lightsource, obstructed by dynamic objects, casting a shadow on dynamic objects. (SDD)
This would also be very nice to have, and wanting it ruled out projected shadows for me (shadow receiver ordering issues).
- Dynamic lightsource, obstructed by static/dynamic objects, casting a shadow on static/dynamic objects. (DXX)
Well, this would be nice to have, and when the former is done this should be easy to add, but it's not what I'm focussing on right now.
- Static lightsource, obstructed by static objects, casting a shadow on dynamic objects. (SSD)
Yes... this also would be nice to have. Unfortunatly, right now I'm not sure what the best way to realize it would be. Shouldn't be too hard (I believe), but it's not related to all this because it needs shadowing from the static lightmap.
Alright. After playing around with projected shadows a bit I realized that I don't like computing the shadow receiver order (and that it brings other problems with it too).
That leaves shadow maps and shadow volumes. As the latter requires computing the object's silhouette on the CPU all the time, comes with this certain problem I now don't speak about (because in the case UFO:AI ends up using it it's better to pretend not to know about it, right?) and it's generally falling out of favor anyway - this leaves shadow maps.
Assuming that a 24bit depth buffer is available (and for what I have in mind it must be) precision shouldn't be an issue.
So let's talk about implementing shadow maps to let entities cast shadows.
As there can be rather many static light sources (which, assuming a point-light, casts in 6 directions) which won't cast shadows on objects on most grids on the map (each room usually contains a light-source, and more than half of the directions will simply cast light on just the wall/floor/ceiling) one must do occlusion testing for them.
Actually performing a true occlusion test for each object which might throw a shadow would be too CPU intensive, but one can simply precalculate this for each static lightsource to each grid on the map, by simply performing an occlusion test on the quad "vertically dividing a grid into triangular prisms". I hope you understand what I mean by that (and do you have a term for that plane? :-).
This could maybe optimized even more, by raycasting to each of the edges of the rectangle and checking whether the crossed tris form a wall quad (this will yield some false-negatives, but all four rays hitting something while still leaving the object only partially obscured (i.e. a window) should be rare enough to not be a problem precluding a full-blown occlusion test at that point).
I hope this will be fast enough to become part of the loading process, if not it must be put into the preprocessing step (not a big issue, I just fear that .bsp maybe can't extended without breaking compatibility).
Now we know what light sources will (possibly - we only checking it on grid level) cast shadows for all dynamic objects on the map (I'll call them illuminated objects) and we have to build up the shadow maps.
As the cast light might be partially obscured by the map (imagine a light from within a room shining through a window, partially illuminating a soldier outside) I need some stencil - and as D:S only comes in 24:8 these days I have my 24-bit depth guaranteed.
And now...
- Disable virtually anything, as the color buffer won't be needed
- Clear depth and stencil buffer
- Render illuminated objects(s), build up depth buffer
- Enable stencil, mark anything that passes the following depth tests
- Render all grids between the light and the object(s) (Is this possible at all, or is there just the BSP? If not... see my occlusion idea below, we'll just render a few tris in orthogonal mode here)
- Clear depth buffer
- Switch stencil function, let only non-marked fragments pass
- Render illuminated objects(s)
... we have our shadow map for this light-source. Note that we only render a small part of the map here, only the entities which are illuminated by the light-source, and only for those light-sources which are likely to be casting shadows anyway. And that we don't actually render any fragments. The performance should be okay.
If one accepts that the "standstill" animation won't have updating shadows, regeneration of the shadow map could be skipped in these cases.
I also thought about caching whether or not a stencil will be needed at all for this particular light-source / face, but this would only benefit those purely in-door lights, which will usually only have to render a single (two?) map tiles anyway. Maybe I'm wrong here and saving some overhead would yield benefits, but that stuff needs to be profiled.
Caching the stencil would be very cool - as an alternative one could build up a 2d "occlusion map" (not the one you think) by converting (during preprocessing) the respective grid tris to the projected ones to be rendered in orthogonal mode, to speed up stencil generation (I think it's a fair bet that part will be the bottleneck). This would obviously need extension of the .bsp format.
We could also skip shadows of objects not visible to the player, but I'd rather not do that - at the very least not for models. The implications of providing them are just too cool.
Anyway. After that one just needs the vertex shader to transform the shadow map back to eyespace, and a fragment shader doing the actual shadowing - the usual.
So far. Feedback is appreciated.
Felix
P.S.: Again I note - I have no idea what I'm talking about.
