# Ray Tracing concers: Efficient Data Structure and Photon Mapping

I'm trying to build a simple ray tracer for specific target scenes. An example of such scene can be seen below.

I'm concerned as to what accelerating data structure would be most efficient in this case since all objects are touching but on the other hand, the scene is uniform.

The objects in my ray tracer are stored as a collection of triangles, thus I also have access to individual triangles.

Also, when trying to find the bounding box of the scene, how should infinite planes be handled? Should one instead use the viewing frustum to calculate the bounding box?

A few other questions I have are about photon mapping. I've read the original paper by Jensen and many more material. In the compact data structure for the photon they introduce, they store photon power as 4 chars, which from my understanding is 3 chars for color and 1 for flux. But I don't understand how 1 char is enough to store a flux of the order of 1/n, where n is the number of photons (I'm also a bit confused about flux vs power).

The other question about photon mapping is, if it would be more efficient in my case to store photons per object (or even per Object's triangle) instead of using a balanced kd-tree.

Also, same question about bounding box of the scene but for photon mapping. How should one find a bounding box from the pov of the light when infinite planes are involved?

EDIT: I would like to add one more question. I've seen in some source codes, that are using russian roulette, scaling the photon's power by the material's diffusivity and dividing by the average color. Is this correct? I thought that the point of the russian roulette was to not have to do this and end up with photons with varying and small powers.

-

If your camera is always in the same position and orientation, using the view frustum and clipping the infinite planes to those dimensions would certainly be a viable idea. You would no longer have infinite planes. If your camera position/orientation is not fixed then you would have to rebuild your structures with the newly clipped planes every time the camera changes, or you must handle infinite planes differently.

With an infinite plane, the only way a line will not intersect will be if it is parallel to the plane. With a ray, it also won't intersect if the direction of the ray is pointing away from the plane. In both cases, you can handle them separately from your other geometry. I doubt you would have very many infinite planes, so checking them without an acceleration structure is probably fine.

I believe the four chars is actually storing just RGB values as floating point numbers with the same exponent (ie 3 chars for the mantissa of the channels then 1 char for the shared exponent) as outlined in the cited reference from the SIGGRAPH course

The KD-tree is used for efficient nearest neighbour lookups. I don't think storing the photons per object will get you faster lookups so it would not be more efficient.

For the russian roulette, I would say that the sources you have looked at don't seem to be following the algorithm as originally specified. Without seeing them myself, I can't really comment much farther. Perhaps the authors found the results more appealing this way.

-
Thank you very much for your answer. What structure do you believe would be fastest for my situation? Also, sorry for adding one more question, but do you know in the original paper how the power changes after each bounce? I tried multiplying by the object's color but the photons end up with very small power and that's without scaling them by 1/n. – Grieverheart Nov 15 '12 at 16:42
I think a KD tree is going to be hard to beat. The benefit of knowing the scene before hand is that you can heavily preprocess it for your ray intersection tests (remove unseen geometry, etc), but the photon mapping is a stochastic process so you probably won't be finding any good improvements to the algorithm in the photon gathering phase. For the bounces, you are calculating the indirect light. This may very well be a small contribution. You add this to the direct contribution to get the final colour. – Chewy Gumball Nov 16 '12 at 18:19