Planet SoC

This week I’ve been busy with something rather unexciting: speeding up the light tree creation time. You might remember that, initially, I just implemented a O(n²) method in order to have a working prototype quickly; now I lowered that to O(nlogn) following advice from Miroslav Mikšík.
It is now possible to have several tens of thousands point lights without incurring in terrible tree creation times. This is particularly important when indirect lighting is added to the mix.
A simple way to add indirect illumination to renderers is to place several small lights on surfaces hit by direct lighting. This principle is used by a family of algorithms called instant radiosity, originally developed by Alexander Keller. A lot of research has gone into reducing the number of resulting lights, in optimizing their placement in the scene (so that, for instance, lights not influencing the final rendering get trimmed), and in overcoming some of the shortcomings of the algorithm, since it tends to suffer in some corner cases.
The final part of my Summer of Code project is indeed about creating a toy implementation of instant radiosity, in order to show a potential “killer application” for Lightcuts in Blender. I think it’s also important to have it in order to have a clearer idea on how to integrate Lightcuts from a UI point of view.
Ideally it would be nice to have just a button to press, without having to rework all the lighting differently, but I’m afraid that the user must have some awareness of the strengths and weaknesses of the algorithm in order to take full advantage of it. More on this in a later post.
Here are some very preliminary results from my initial experiments with virtual point light placement.
Textured area light with indirect lighting - Tree creation time: 00:00.54 - Number of (point) lights: 5966 (0l + 0s + 5966o) - Average cut size: 155.22 - Shadow rays: 153.77 (2.58%)
Textured area light with direct lighting alone (despite the stamp) - Tree creation time: 00:00.26 - Number of (point) lights: 3102 (0l + 0s + 3102o) - Average cut size: 134.83 - Shadow rays: 132.35 (4.27%)
Test scene - with indirect lighting - Tree creation time: 00:02.00 - Number of (point) lights: 18091 (0l + 0s + 18091o) (4900d + 13191i) - Requested error rate: 0.018 - Average cut size: 587.30 - Shadow rays: 582.20 (3.22%)
Test scene - direct only - Tree creation time: 00:00.43 - Number of (point) lights: 4900 (0l + 0s + 4900o) - Requested error rate: 0.020 - Average cut size: 567.16 - Shadow rays: 562.23 (11.47%)
(Yes, I am aware of the banding problems; it’s one of the issues I have to address next week before the Gsoc is over.)