Final Project - Real-time Ray Tracer
Objective
Implement Key-frame (hopefully skeletal/bone) animation in our real-time raytracer.

Project Progress
Saturday, April 14 2007
On the programming front we are presently cleaning up our engine to remove support for some of the features that we don't require while building a realtime ray tracer.  These features basically include support for path-tracing and all the constructs that enable it.  On the other end we're aggregating things from our submissions from the past e.g. support for instancing and texturing.  Some newer things that we're working on right now are:
  1. Including support for matrix stacks to easily transform objects using transformation hierarchies.
  2. Implementation of KD-Trees (not much has gone into it yet).
  3. Including support for several multi-texture operations (we want our images to look cool!)
On a more theoretical front we keep coming up with ideas to accelerate global-illumination on our animated entities in a scene:
  1. Per-voxel lighting
    • We came up with this idea to pre-compute illumination at each point in 3D space within our scene, and store these illumination values in a 3D texture.  Each voxel in this 3D texture defines how and how much light reaches that particular voxel.  While rendering our animated entity, we might not need to compute illumination on each pixel of this animated entity.  And the animation could be done on a GPU at very high frame rates.  After pondering a bit over this approach, we realized there were certain very basic problems with it:
      • Effects of entities on global illumination.
      • Self-shadowing.
      • Shadow of one animated entity on another one.
      • Coming up with sizes of discrete intervals at which we sample illumination in our 3D scene (Interpolation can help here).
  2. Propogational Model of Lighting
    • While discussing solutions to our above mentioned problems we came up with another model to represent lighting in our scene. Each voxel in this 3D space is a function of voxels around it. When the scene is pre-computed the dependence of one voxel over its neighboring voxels is computed.  The dependence function determines how the illumination on its surrounding voxels affects the illumination on this current voxel. Each of the neighboring voxels are then assigned weights.  When we render our animated entity within this scene, it distorts this 3D space: it turns illumniation off on certain voxels which result in result being propagate through its neighboring voxels, and eventually giving out effects as shadows.  We are still thinking about this approach, and we believe there  are certain fundamental flaws with it:
      • Computationally expensive
      • Coming up with this dependence function is not going to be easy.
      • How can we harness our knowledge about photon-mapping, BRDFs and other illumination models to answer our questions.

We are also presently studying fuzzy KD-trees [1] to reduce overhead with computing spatial information at each animation frame. 
Tuesday, April 17 2007
We have been discussing possibilities of extending our ray-tracer from being a program that only use our CPU to a more specialized ray-tracer that uses both CPU and GPU.  We investigated into this a bit and found that quite a bit of research is going on in this field.  Studies show that GPUs can outperform CPUs with ray-triangle intersections [2], we got interested in figuring out whether we can use GPUs to perform fast ray-triangle intersections on dynamic geometry and incorporate streaming architecture into our current ray-tracer.  

[3] discusses a specialized KD-Tree traversal that harnesses the power of GPUs.  Should be an interesting read.

Another set of papers to go through.
Thursday, April 26, 2007
We started studying Cal3D library for loading animations.  Seems like the industry standard library to load and use animations.  Skimming through it gave us an impression that things shouldn't be too complicated.  But it doesn't seem like the kind of library where you pass in the filename and it gets you all triangles or whatever you're interested in, in an easy and convenient manner.  Lets see where we go with it.

On a sidenote we might use some of our code from previous projects to load animations from MD3 or MD5 models.
Monday, April 30, 2007
Well, we arrived on a decision with our existing code for loading MD3 or MD5 mesh and animation files.  We cannot really reuse this code since its very tightly integrated with our other projects that load and display these models.  So we'd stick with Cal3D library.  

The Cal3D lib does a lot of things in a counter intuitve way.  We feel that this library is designed for APIs like OpenGL and DirectX where you get a bunch of transformed data in one shot and you render the geometry using batch rendering calls.  Another serious problem with Cal3D is its use of materials.  We do not completely understand the "material threads" used by this library.  Still working on it.
Friday, May 4, 2007
Finally, after hours of struggling with Cal3D's material system, we figured that the counter intuitve way it handles materials is a well known issue among the Cal3D user base.  One of the posts by one of the authors of this library makes it clear that we need to perform certain operations in order without worrying about what they do internally.  Authors of Cal3D believe that this can be improved upon.  So for now, we are just performing a few steps without completely understanding what they do.

The problem boils down to the order of loading materials and associating them with the core model.  The materials need to be loaded in the same order as they are specified in the model's configuration file.  

As a part of enhancements to our scene file parser, we plan to provide users with a way to specify this configuration file in the scene file, along with a few other parameters like location of data files (anim files, mesh files, textures and skeleton files).
Sunday, May 6, 2007
We have been able to load Cal3D models with full animation, texture and material support.  The model can now be inctanced and placed anywhere in the scene.  For animation we're using precomputed BVHs and switch between them as we progress through the animation.  At load time, we sample animation every nth interval, which is based on a substitutive variable that defines the number of frames we intend to use for a particular animation and the animation framerate we intend to achieve.  These BVHs are then stored with the model.

We plan to use a deformable BVH approach and work on it a little bit, but seems like we're running out of time here and finals week coming up :((((.
Thursday, May 10, 2007
Arrrrrrrrrgh! We just noticed that our webpage at school is not getting updated because of some flaw in Uday's sync script :((((((.  

We couldn't really find enough time to implement a working model of deformable BVHs, and would be presenting our demo with precomputed BVHs.


 References:
[1] Gunther J., Friedrich H., Wald I., Seidel H., Slusallek P.:  Ray Tracing Animated Scenes using Motion Decomposition.  EUROGRAPHICS 2006.
[2] CARR N. A., HALL J. D., HART J. C.: The Ray Engine. Tech. Rep. UIUCDCS-R-2002-2269, Department of Computer Science, University of Illinois, 2002.
[3] FOLEY T., SUGERMAN J.: KD-tree Acceleration Structures for a GPU Raytracer.  In  HWWS '05 Proceedings (2005), ACM Press, pp. 15-22.
[4] GUNTHER J., FRIEDRICH H., SEIDEL HP., SLUSALLEK P.: Interactive Ray Tracing of Skinned Animations. In Proceedings of Pacific Graphics, The Visual Computer 2006.

Spring 2007.  Thomas E Hansen & Uday K Verma.  Department of Computer Science.  The University of Iowa.