[Bf-committers] Google Summer of Code 2008 Proposal: Lightcuts

[Davide Vercelli]

Hi guys,

  I would like to submit a Google SoC proposal concerning the
implementation of the Lightcuts algorithm [1].

  The Lightcuts algorithm is a way to handle large number of lights
(thousands) by selecting a different representative subset per pixel
(hundreds), according to perceptual error metrics. Handling large
number of lights is very useful as it can be used to unify lighting
from various sources (textured area lights, volume lights, environment
maps) by conservatively converting them into a large number of point
lights.

  Users would benefit from significant speedups in scenes with complex
lighting; additionally, very fast preview renderings can be generated
by raising the error threshold.

  The original Lightcuts algorithm is not only effective but very
practical, and my opinion is that it should fit into blender's
existing ray tracing engine without major disruptions (to existing
code, workflow, etc.).

  The algorithm per se is relatively simple, but implementing it
properly and efficiently is tricky [4] and integrating it into
blender's rendering code, which is notoriously not for the
faint-hearted, could prove a good project alone. My fear though is
that it could be deemed too easy to implement as a SoC project. Here
are some possible extensions:

  a) adding an instant radiosity-like scheme [2], that is: primary
lights generate a large number of secondary lights acting as indirect
light sources; this way, blender internal would gain indirect
lighting, albeit approximated

  b) implementing reconstruction cuts [1], a screen space
interpolation scheme to cut rendering times even more, though I'm
afraid that this could be difficult to integrate in the current
rendering code

  c) implementing Multidimensional Lightcuts [3], which is an
extension to the original algorithm handling depth of field, motion
blur, participating media, antialiasing and other effects; this seems
to be way more difficult to implement and, again, I'm not sure how
well it would play with the existing rendering pipeline

  So, before submitting the actual proposal, I would like to hear if
it would be a good idea to include one of these extensions to the
original algorithm and which one. (I favour option "a" both as a coder
and as a user).

  Any other comments or suggestions would be highly appreciated.

  Finally a couple of notes about me: I am an Italian post-graduate
student and rendering is among my research interests. I am an active
member of the Italian Blender community since 2005. I have no problems
with C, C++ and Python, and I do know blender internals a bit (I have
also submitted a number of patches to the tracker, even though mostly
small UI tweaks). I do need a lot of mentoring on rendering code,
though... ;)

  Cheers,

Davide Vercelli / UncleZeiv

References:
[1] B. Walter et al, "Lightcuts: a scalable approach to illumination"
(Siggraph 2005)
    http://www.cs.cornell.edu/~kb/projects/lightcuts/
[2] A. Keller, "Instant Radiosity" (Siggraph 1997)
    http://citeseer.ist.psu.edu/keller97instant.html
    This is just the original seminal paper, the literature on this
subject is broad.
[3] B. Walter et al, "Multidimensional Lightcuts" (Siggraph 2006)
    http://www.cs.cornell.edu/~kb/projects/mdlc/index.htm
[4] M. Miksik, "Implementing Lightcuts" (CESCG 2007)
    http://www.cescg.org/CESCG-2007/papers/Prague-Miksik-Miroslav/Lightcuts_MiksikMiroslav.pdf