OllieBrown

To round out my previous post concerning GSoC I thought I should list out the changes I have made and how the milestones are lining up.

Changes:

• Reimplemented the photon map data structure from the ground up.
• Lots of changes to the photon emission code to make it physically accurate.
• Code to emit from spotlights in place but untested.
• Re-factoring of the indirect light and direct light classes into independent raytracer and photonmapper engines
• A new structure (LightCalculator) that will loop through the sector elements and add up the components from each engine (raytracer and photon mapper).
• Many new command line options for tweaking the photon mapper and calibrating it with the raytracer.
• Filtering in the photon map to help eliminate artifacts and smooth out noise (still needs work).
• A new final gather implementation (still needs work).
• The beginnings of an irradiance cache to speed up final gather.
• Updates to the texinfo documentation for lighter2 (still needs work).
• A new version of the Cornell box model (with more lights and fixed colors).
• a brand new model of 'Construction in Wood' (another example of color bleed).

Results:

• Photon mapper is working and, although noisy and not artifact-free, giving usable results.
• Photon mapper is an order of magnitude faster.
• New rendering engines can be implemented easier in the future using the LightCalculator/LightComponent classes.
• Work has already begun to further eliminate noise (final gather), speed up even more (irradiance cache) and remove artifacts (gaussian filter).

Despite the noise and artifacts still present I think it's safe to say Milestone 1 is complete (or nearly so). Here's a list of things still to finish/implement.

Immediate priorities (considered unfinished Google Summer of Code obligations):

• Debug gaussian filter.
• Test spotlight emission and ensure it is correct.
• Add support for directional light sources.
• Retrieve and use surface albedo from object material (texture, color, etc). Consider accounting for normal/bump maps.
• Complete irradiance cache and then debug final gather.

Future changes (for fun and profit!):

• Add support for filtering materials (translucent w/o refraction).
• Add support for reflective/refractive materials and caustics.
• Add support for static linear/area/polygon light sources. This would require changes to:
  
  1. photon mapper - sampling over area as well as hemisphere.
  
  
  2. raytracer - ability to distribute rays from area source as needed.
  
  
  3. raytracer - ability to detect collision with the geometry of an area source (not infinitely small like point source/spotlight)
  
  
  4. libcrystalspace - support to parse and represent area sources within a world (but static ones only).
  
  
  5. libcrystalspace - support to render the geometry of an area source (no longer infinitely small).
  
  

It seems appropriate to send thanks out to Res and Scott at this point as they have both been quite helpful this summer and I'm sure will continue to be.

And now, we carry on ...

A New Plan
Thanks to all who offered feedback for my previous post. With the discovery of the GSoC '08 branch for lighter2 with photon mapping plans need to change. I've been examining Greg Hoffman's changes to lighter2 to determine what work could be done and I think there's a good chunk here to constitute a project. Here's my assessment of what the branch contains:

• There's a basic Photon Map data structure and code to emit and gather photons in a single sector.
• This code does seem to do something but I don't think it's correct in all cases (or at least robust) yet
• There are things missing (proper handling of materials, diffuse to diffuse light paths)
• It's missing some options to fine tune the convergence (no max error, max recursion depth, no control over number of photons emitted)
• Right now it's slow and has room for optimization

So, it seems given the original content of my proposal and this discovery from last summer that the new course of action should be to work on the photon mapping implementation. So, here's a basic outline of what I could do again welcoming comments:

Milestone 1: Repair

1. Ensure the PM calculation is correct and fix where needed (such as handling LD+SE paths)


2. Add the missing settings for controlling convergence


3. Ensure it scales well from small test cases (like the Cornell Box) to large game levels

Milestone 2: Improve Quality

1. Handle light traveling across portals


2. Handle all materials properly (materials are ignored right now)

Milestone 3: Improve Speed/Features

1. Add importance sampling to avoid redundant photon emission


2. Move calculations to GPU (BIG speedup)


3. Optional: Add support for 'dielectrics' (refracting materials) and caustics (via reflection and refraction)

Concerning the optional task under Milestone 2, Photon Mapping just handles caustics well (it's famous for it) and as such it would be easy to render this if the information about refraction is available in the material structure (namely index of refraction). It could make for some interesting but very specialized effects.

Time-line
I'm planning about two weeks for each milestone with an extra week for the first one just for getting out of the starting gate. Here's a rough time-line to completion of these milestones:

• Milestone 1 (already in progress): Now - July 21st
• Milestone 2: July 22nd - Aug 4th
• Milestone 3: Aug 5th - Aug 18th

I want to make sure that the amount of work I'm doing is worthy of a full SoC project regardless of the time frame. I'm definitely slow getting started here and I want to ensure all involved that I will make that up as we go either by putting in extra time now or beyond the scheduled GSoC end. Therefore, I think it is best to make sure I get a project defined that is of a scope appropriate for SoC so that no one feels short changed.

We are underway and I am long overdue in posting an entry here so there is much to discuss.

What have I been doing:
Planning! I have been getting very familiar with lighter2 and determining where change would be most appreciated. This has been a slow task as much of lighter2 is un-commented (or at least, the comments are not very detailed). Also, I have had to learn much about the CS app framework, the instance tracking classes used in CS and the i* classes used throughout lighter2. Conceptually, I reached a good place to actually propose some changes to Scott my mentor last week and we met to discuss just that.

What is the current status:
At present, we have identified the following concerns or features that need attention in lighter2 and would pertain to my proposal and my areas of expertise -

1. lighter2 is an external dependency for any CS app. For redistribution purposes, it would be better if it was internal (either built into the library or as a plugin).


2. lighter2 uses the 'direct lighting' approach for its central calculation. This works well and is efficient but is below the standard of other game engines which use Radiosity. For example, see this page under the heading 'Dynamic Lighting and Shadows' (http://developer.valvesoftware.com/wiki/Source_Engine_Features).


3. While lighter2 is a single run, non-interactive component efficiency is still quite important. This is because during development of a game, static lighting needs to be recalculated every time the world is changed. This can be tedious if it takes more than a minute or two to give a result(and seconds would be even better).



4. Conceptually, any light-mapping application can be thought of as a bootstrap. The rendering system will use the light maps to render the world but the light-mapping application needs a rendering system (or at least part of one) to construct the light maps. Therefore, lighter2 naturally depends on some components of the CS library (mostly viewing and projection calculations and geometry loading components).

   Some of the conceptual components of lighter2 (like the 'scene' and 'segment' classes) should be part of the CS library. I have not examined the library itself too deeply to see if it provides these components but Scott suggested that they are in fact copies of classes from the library. This is conceptually undesirable but there may be reasons for it. More discussion of this is in order.



5. At the heart of the 'direct lighting' approach is a BRDF approximation used to calculate how much ambient/diffuse illumination each surface gives off for each light source. I have not yet identified where this calculation takes place but I'm operating on the assumption that this calculation is being done somewhere and is using a very simple BRDF model like the Blinn-Phong model.

What conclusions can be drawn:
From all of this I've identified some requirements for this project -

1. New code should be easy to integrate (or already be integrated) into the CS library.


2. The current 'lighter2' work flow (which will probably be more efficient than any new work flow) should be retained as a fallback for when quick calculations are important. This includes both the 'direct lighting' algorithm and the current BRDF model.


3. We should consider re-writing lighter as a plugin. This is secondary to the main proposal objectives but if we are making enough changes to lighter this may happen anyways as a side-effect or as an add on at the end if there is extra time.

So what are the plans:
I'm going to start moving forward with changes now. Here's the initial proposal of work in the order it will be undertaken (this may change in a typical design-build fasion) -

1. The direct lighting BRDF model will be upgraded to the Oren-Nayer model. This should be very easy and will satisfy part of the original proposal. If nothing else gets completed on this project at least this will be in place. It will also serve as a way to finish examining the details of lighter2 that will be more productive than just reading the source. Note that we may need to convert the Blinn-Phong parameters to Oren-Nayer parameters so that material properties do not need to be redesigned for every existing world to take advantage of this improved model.


2. The Radiosity algorithm will be implemented as a CS plugin. I have implemented Radiosity before and believe this can be done relatively quickly given the tools that CS already has built-in. Implementing it as a plugin will make it available for use in lighter2 or even as its own internal step in the standard CS rendering pipeline. Here's a breakdown of how this will be undertaken -
   
   
   
   1. The most efficient approach to Radiosity that I know of is the hemi-cube method. This fits well in any scanline rendering system that can render-to-texture. We will start by developing a CS app that renders the scene from the point of view of the light sources to a texture map. This will then be integrated into a bigger radiosity plugin.
   
   
   2. In the radiosity algorithm all surface patches can be light sources. To avoid the need to supply seperate lights just for the radiosity system, existing light sources will have to be approximated with proxy geometry and special work may be required to support spot-lights and other non-area light sources. Point light source will need to be approximated with very small area light sources.
   
   
   3. The hemi-cube textures are used to compute form factors and fill in a large matrix that describes which surfaces can see what parts of which other surfaces. This is a straight-forward calculation.
   
   
   4. With the form factors calculated we need a large linear system solver that computes the equilibrium achieved by this world. This will initially be a standard Gauss-Seidel solver and can be upgraded to something fine-tuned to the radiosity problem at a later time.
   
   
   5. The solved system must be written back to the geometry by placing the computed colors into the mesh vertices which normally requires some type of interpolation. From here, we could further propagate this data out into textures which would then become the light maps for the scene.
   
   

At this point we will reevaluate and decide what is to be done next. Additional project tasks may include:

• Improving radiosity with things like: a better linear system solver, automatic geometry or light map subdivision at high-frequency artifacts and support for more types of light sources.
• Re-working of lighter2 as an internal dependency (see above)
• Other changes to lighter2 to bring it up to speed with the CS library and make it more maintainable into the future.

Conclusions:
What's described here will constitute the bulk of this project and work will begin immediately. I intend to reevaluate progress as I go and learn more about CS and lighter2. All comments are welcome and encouraged as there are a plethora of assumptions underlying these ideas and any number of them could prove to be wrong. The collective knowledge of the CS community can do far better to identify these problems than I can digging through the mountains of code and documentation. My time is better served now making changes rather than fact-checking!

Thanks to all for reading this! I will post more as I go.

Seth