UncleZeiv’s Corner

One of my favourite pictures from the original Lightcuts paper is an office scene lit exclusively by a tv screen. You can do that with textured area lights.

In Blender you can already link a texture to a light, but the outcome is a sort of texture projection, which is useful if you want to fake effects like light passing through a tree without actually computing the visibility: that comes of course very handy for cutting rendering time, to have artistic control on shadowing, etc.

What I mean here with textured area lights, on the other hand, is actually modulating the color and intensity of the light throughout its area. This way you can obtain the effect of lighting coming from tv screens, large windows with varying lighting conditions, and even area lights with custom shapes. Here are some examples.

In the lightcuts paper you had also the added contribution of indirect light. In this case I added some additional lighting using a faint environment map. The interesting point to note is that putting additional lighting has a negligible impact on rendering time, if not a beneficial effect! This is because completely occluded areas evaluate far more lights than bright areas, as a consequence of using a proportional error metric; thus, having those parts brighter allows for less evaluations.

Here’s a false colour rendering where the green areas show where the environment lighting is more influential and the bluish areas show where the area light is more influential. The red channel counts the number of lights used with respect to the maximum, so the image is white where it’s most occluded, as expected.

These days I’ve been working on adding support for oriented lights. It’s mostly there, even though there are a couple of missing details and the current code is obviously slower than it could be.

Still, like in my previous post, I can’t resist posting another revisited preliminary test, now rendered with actual lightcuts code.

And the corresponding false colour image:

The original test took almost an hour to render, at 400×300 OSA5. This one took ten minutes at 800×600. True, the images don’t look exactly the same, but that’s because I changed the falloff type of the virtual point lights to a more realistic inverse squared. Still, the speed improvement looks pretty good already!

Yes, I am perfectly aware that the shadow from the sun suffers from aliasing problems. This issue will be addressed somehow, so don’t worry about that.

Please note that the virtual point lights have been placed by a custom (and pretty hackish) Python script; generating them automatically is something that I definitely want to do in the future, but is not strictly speaking part of the current GSoC.

My plan in the near future is to complete the basic feature set in time for midterm evaluation — that is, adding support for specularity and for the other diffuse shaders available in Blender. This is holding back some other things I would like to do as soon as possible, such as releasing a couple of Blender scripts to render from environment maps and to do basic indirect lighting, and squashing the bug that is causing this video to flicker like crazy.

Focus on lowering algorithmic complexity and don’t perform other optimizations until their usefulness is demonstrated by thorough profiling: since I completely agree with this maxim, I feel obliged to explain why my latest lightcuts update seems to contradict it.

First of all, let’s recap: in order to select an optimal subset of the available lights per sample, a lightcuts implementation needs to maintain them organized into a binary tree. The leaves of this tree are the actual lights, while intermediate nodes represent clusters of lights. A cluster of lights is a sort of imaginary light whose position, intensity and orientation is somehow representative of all its children.

The original paper spends only a paragraph on tree building and related issues. The point is that building the light tree is trivial, but building it efficiently is far less trivial. Miroslav Mikšík, in his paper dealing with implementation issues regarding lightcuts, notes that a naive algorithm may have a O(n³) complexity; he devised a technique to reduce such complexity to O(nlogn).

Keep in mind that a robust implementation should be able to deal at least with several thousands of lights, and should allow venturing into the millions! This is one of those cases where complexity does matter.

Right now, though, I’ve implemented a simple O(n²) scheme, taking advantage of the nice heap mini-library available in Blender. I’ve spent some time, on the other hand, ensuring that a single memory allocation is required for the entire tree, instead of one for each node. This is possible because the number of nodes in the tree is predictable in advance. This reduces fragmentation, is cache friendly and, since it’s possible to use offsets instead of pointers, its memory footprint is the same on 64 bits machines instead of increasing because of the doubled pointer size.

Next, I want to move on to the other parts of the algorithm, in order to have a working prototype fairly soon. It probably won’t support a large number of lights, nor oriented lights (spot) which are probably going to be added later on, as they require special treatment. But at least it will be possible to validate the overall architecture of the project, and people will be able to start playing with it.

For this purpose, the current algorithm has both acceptable performance (I’m not going to debug with large number of lights at the beginning, anyway) and is easier to debug.