Assignment 5
Dylan Scott (CS184-DU) and Stephanie Ren (CS184-AK)
For project 5 we decided to augment our project 4 raytracer to simulate
global illumination using the technique of photon mapping.
Photon mapping is a two-pass algorithm that augments raytracing by
adding an additional step to the algorithm before rendering: Prior
to rendering we shoot many 'photons' into the scene, beginning at light
sources, which bounce around in the scene before coming to
rest. Simulating this bouncing may be done using Russian Roulette,
where at each bounce there is some probability that a photon will
be reflected, absorbed, or transmitted. Alternatively, you can also
simulate photons where at each bounce the photon is deposited into
the map, but reflected at a lower energy until it drops below some
threshold. We chose the latter model for simplicity's sake, though
it may come at the cost of performance (since it results in a greater
number of photons in the scene).
After constructing the photon map, we render as we would normally, but
now when we find the intersection with an object, we query the
photon map for the nearest neighboring photons, and add their
contribution to the scene. As a result we get more interesting effects,
such as diffuse interreflection (color bleed).
The main performance bottleneck for photon mapping is the nearest
neighbor query on the photon map we constructed. Since we shoot so
many photons into the scene, it is very important to have an efficient
data structure on which to do this query. We went with the data
structure suggested by Henrik Wann Jensen (the pioneer of the photon
mapping technique) - kd-trees. Since kd-trees are not a trivial
data structure to efficiently implement, and since we did not want to
reinvent the wheel, we decided to use an existing kd-tree library
for Java (our raytracer is written in Java). The library we used may be
found at:
http://www.cs.wlu.edu/~levy/software/kd/
Finally: Pictures
Rendered at 1080x1080 with antialiasing, with approximately 500,000
photons in the scene.
Rendering took approximately 8 hrs on a moderately powered laptop (1.83
GHz Core 2 Duo, 2 GB RAM). Most of that time spent in the kd-tree
n-nearest neighbors method.
Click the images to see the full sized render.
A visualization of the photon map used to render the cornell box image.
Source code may be found here.