What exactly is involved with updating the lighting in something like this?
Changing from pre-baked radiosity to entirely dynamic using deferred shading techniques.
Are you doing detailed work with the algorithms, or has that stuff already been written and you just need to plug new components the right way into an old game?
It's a lighting model that's well known in 3D graphics and widely employed.
I assume it has to be done in the right way so you can maintain good performance.
Basically, yes. Mostly it includes cleaning up really shitty code.
Are there new data structures that needed to be added into the game engine?
Related to above, generally yes. idTech 2 used what's called a potentially visible set (PVS) -- basically after the map geometry was compiled, a PVS compiler would run on the data sets and build a list of potentially visible geometry from every available point in the map. This took awhile but it worked (mostly). It tended to be buggy.
At the moment I've replaced it with super basic frustum culling (e.g., just not drawing geometry that's outside the view frustum) but I want to replace it with a basic oct tree. After the BSP is compiled, the general idea is to generate a 'cube' area around the entire map and its geometry then subdivide that several times (not sure if it should be preset or based on size, etc., need to play with that a bit). From there geometry is further culled -- only geometry within octtree nodes that are in the view frustum will be tested against the view frustum and ultimately culled. It's probably not the most efficient means of doing this but when modern GPU's are capable of rendering billions of triangles per second having a few hundred (or even a few thousand) isn't going to affect performance much (or at all). The real performance hog is going to be the shaders and making them run as efficiently as possible.
I've already run into a few bottle necks related to the dynamic shadows (too many lights against too many shadow casting objects kills framerate). A simple way around this is to have accent lights not cast shadows (still allows for very good lighting on surfaces) but I'm not sure I like that solution.
I've also noticed that certain methods of building maps can greatly affect performance. I suspect this is a limitation of the BSP structure itself and I have a feeling the octtree scenegraph will help with that a lot.
I think a video would illustrate the new lighting better than screenshots:
