User:UncleZeiv/SummerOfCode2008/Proposal

From BlenderWiki

Updated for the Blender Conference 2008 --UncleZeiv 09:00, 21 October 2008 (UTC)

Other information about this project here

Abstract

This project is about implementing the Lightcuts algorithm in Blender. The Lightcuts algorithm, introduced at Siggraph 2005, is a way to handle a large number of point lights (thousands) by selecting a different representative subset (hundreds) per pixel, according to perceptual error metrics. This way, rendering times become sublinear with respect to the number of lights, without perceptible loss of quality.

Having thousands of point lights in a scene may seem unrealistic, but they are not meant to be hand placed by artists; instead, they can be the result of a conservative, “brute force” discretization of various sources such as textured area lights, environment maps, and even volume lights. Lightcuts is indeed a way to unify in a single strategy the handling of lights coming from different sources.

Artists are thus encouraged to make extensive use of area lights and environment lighting. Moreover, by raising the error threshold, faster preview renderings can be generated in order to adjust lighting.

Finally, it is noteworthy that “Instant Radiosity”-like algorithms [2] are a particularly interesting source of point lights, placing a large number of them in the scene in order to simulate indirect lighting. A simple IR scheme has been implemented.

Benefits to the Blender Community

• rendering times scale sublinearly with light complexity, thus encouraging artists to make extensive use of area lights and environment lighting
• by raising the error threshold, fast preview renderings can be generated in order to streamline trial-and-error lighting adjustments
• an “Instant Radiosity”-like scheme enables Blender Internal to support also indirect lighting (albeit approximated); the current implementation is pretty simple, but already useful in most scenes, particularly for architectural visualization.

Deliverables

Blender's ray tracing engine is being extended to support the Lightcuts algorithm.

Proper UI integration has not been provided yet; anyway it is envisioned to be fairly simple. Currently, an entire panel among the scene buttons is devoted to Lightcuts; this is used for testing and development purposes and is not meant as a basis for the final UI. See the User Manual. See also this page on integration issues.

I am committed to keep the code clean and well documented, and to maintain as compact an API as possible.

Additionally, a proof-of-concept implementation of an “Instant Radiosity”-like has been provided; this is not production ready nor user ready within the scope of the Summer of Code, but is meant to be a starting base to build upon in the future.

Project Details

The project can be viewed as the sum of three fairly separated parts.

1. code to transform current Blender lights in a collection of point lights (of course this is particularly relevant for area lights and environment maps from the “World”); this code does not have to be particularly smart, as the true savings are performed by the Lightcuts algorithm.

   I may use or at least have a look at Matt Ebb's code on importance sampled environment maps.

2. code to build the hierarchical tree from the point lights collected in the previous step; naïve building algorithms have O(n³) complexity, obviously dominating rendering times; many techniques exist to speed up tree building

   Currently, this has been implemented for omnidirectional ("Lamp") lights in O(n*log(n)), and works acceptably well for thousands of lights

3. the core of the algorithm, that is: traverse the tree starting from the root and replacing each of the currently selected nodes with its children if we calculate that its error metric is going to exceed the threshold required by the user. Please see [1] for details on how to calculate those metrics. Of course, tree traversal and error metrics calculations have to be particularly efficient since this code is called per pixel (or better per sample)

   This has been implemented for all light types, diffuse shading and phong specular; more to come.

My aim is to keep code changes to the ray tracing engine at a minimum. My original idea was to issue a preprocessing call at the beginning, and, per sample, to cycle not all lights but only the subset provided by the Lightcuts code; this, though, doesn't work because, in order to select the subset, the Lightcuts algorithm has to evaluate the lights as well. I am now using a custom version of shade_lamp_loop, and will soon propose to merge it with the actual one. The non-lightcuts code path should be fairly unaffected by this change.

Node materials may require specific experimentation since computing the accurate metrics required by the algorithm may be difficult for them. Further interactions with the render pipeline, render layers, etc. have to be carefully investigated. In general, not all current features from the internal rendering engine can be supported; we must find a way to notify the user if some of the settings are incompatible.

[3] is a useful source of implementation hints.

This code should not interact significantly with Blender's UI, so shouldn't clash with Blender 2.50 plans as far as I understand. My aim is to merge this branch in time for 2.50.

Project log

See also the midterm report.

• may
  • tree data structure in place (currently only for directional lights)
  • "core" algorithm in place for directional lights and lambertian diffuse shading (even for large numbers of lights)
• june
  • support all light types (also directional and oriented)
  • support also specularity
  • automatic light creation from environment maps and area lights
• july
  • support all diffuse shading models and phong shading
  • more efficient tree creation using kd-trees
  • automatic light creation from textured area lights
• august
  • proof-of-concept “Instant Radiosity” calculation

TODO

See User:UncleZeiv/SummerOfCode2008/Status.

Project FAQ

Moved here.

Bio

I am a 27 years old PhD student at Sant'Anna School of Advanced Studies in Pisa, Italy. My research topics include virtual environments and rendering. I previously received my Masters degree (2005) and my BA degree (2002) in Computer Engineering from University of Pisa.

I started using Blender in 2005 and I have been a part of the community ever since. I attended the Blender Conference both in 2006 and 2007, also giving a talk in 2006 [4] (on the integration between Blender and my lab's virtual reality system). In 2007 I gave a talk on Blender together with Riccardo Covino in a prestigious venue [5]. My artistic output is limited but you can see a couple of works from last year in [6].

I am a Blender fan, so having the possibility to both work on Blender and deal with topics useful to my research, is a fantastic way to spend the summer. I would also be very proud to provide Blender with a new useful feature.

Project updates

I blog about my progress in this project at my technical blog.

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]

M. Miksik, "Implementing Lightcuts" (CESCG 2007)

http://www.cescg.org/CESCG-2007/papers/Prague-Miksik-Miroslav/Lightcuts_MiksikMiroslav.pdf

[4]

http://www.blender.org/community/blender-conference/blender-conference-2006/proceedings/davide-vercelli/

[5]

http://www.blendernation.com/2007/10/27/oct-28th-blender-presentation-in-florence-italy/

[6]

http://profile.imageshack.us/user/unclezeiv/images