Sunday, November 27, 2011

Attempt to Optimize

Today I was trying to answer two questions:
  1. Is the limit real? Is there a limit on the number of operations or loops? What is the one breaking the code?
  2. Can I optimize the photon gathering code so that more photons can be used?
The answer to the first part is yes. There is indeed a limit on the number operations. Specifically, the operation that is making the shader fail is the number of array look-ups. With too many array look-ups, the shader refuses to compile. Therefore, the number of array look-ups needs to be decreased. Currently, array look-ups are used for looking up all photon positions, photon colors, and photon incident angles, as they are held as separate arrays (so far I do not know how to pass a struct array as a uniform.

So I spent the rest of the day trying to reduce the number of array look-ups. My solution was instead of using vector arrays, use a texture and do a sample. This was a very long process that took me the whole day. The first step was to figure out how I can go from an array of floats to an Image in Javascript. Turns out there isn't any image library for doing this (i.e., something like SOIL for C++), but finally I found that I could use the HTML canvas element. I can individually set pixel values of the canvas, and then I can export the canvas as an image data URL. Once, I have the data URL, I tried passing it to WebGL as a texture, (after several hours of researching) but turns out WebGL texture cannot be created from a data URL. The data URL must first be saved into a real image before it could be loaded as a GL texture. I had no other better idea (and I already spent too much time on this to give up), so I decided to save the texture out as a real file on the server using PHP, then load that file as a GL texture. After some time, I got it to work, and could correctly load a texture that was dynamically created out of an array of floats.

The data that I decided to convert to textures are the color values and the incident angles, because they are both between 1 and 0. The color values transferred nicely (as expected) but I had major issues with incident angles because values can be negative. I first tried to remap the values, such that 0-0.5 is negative, and 0.5-1.0 is positive. However, this led to much loss of data and the results did not come out correctly. Below is an image depicting this loss of data:

Next I decided to separate the magnitude and the sign into separate textures. I succeeded in passing these two textures to the shader, but I was not able to correctly convert them back or use them. I am suspecting that it is interpolation of the texture sampler that is messing it up; optimally I want discrete values, but GLSL interpolates the texture RGB values when being sampled, so it could be the source of the error.

So finally, I decided to leave incident angles out of the equation for now. With the improvements I made today, I am now able to have a total of 140 photons in the scene, almost triple the amount I had earlier. This is considered a good improvement, however, it is still nowhere near producing a good image.

Next I am planning to also convert photon positions into a texture, but this will require a much more involved conversion. But hopefully it will allow me to loop through even more photons. However, I did read that texture samples are really slow, so I am not sure about the effect on performance. Right now I am only doing one texture sample for the color per pixel, but if I were to use a texture for positions, it will be as many texture samples as there are photons.

Below is the current result, with the mentioned improvements and using the alternative photon scattering technique mentioned in the previous post.


  1. A quick question:

    If I'm understanding this properly, you are looping through every single photon in your photon map when you do lookups. This looping behavior seems like it will eventually lead to some massive inefficiencies when your photon count gets to actual production numbers (say, tens of thousands). Are you going to be using some sort of acceleration structure such as kd-trees later down the road? Admittedly constructing/rebuilding kd-trees in mass parallel isn't easy and I have no idea where one would begin doing that...

  2. So it turns out there is a one line function that loads textures from data array... That could've saved 6 hours on my part.