Monthly Archive for May, 2008

Playing with a “working” prototype

Published
by
UncleZeiv
on May 29, 2008
in Blender, Coding, GSoC 2008 and Graphics
. 0 Comments

The Google Summer Of Code has officially started on Monday. I’ve been doing a fair amount of coding  since my last post and it is now possible to see something almost meaningful on my branch.

I finally managed to have all pieces of the puzzle in place. My initial attempt to hook the lightcuts algorithm to the renderer through a “lights iterator” interface turned out to be ill conceived: what I really needed was a callback mechanism to let Blender Internal evaluate the contribution of a single light. In the end this will require more changes to the render engine, but overall this technique remains pretty non-intrusive.

Right now the technique supports omnidirectional lights (”Lamps” in Blender parlance), Lambert shading, only diffuse. Through the UI it’s possible to change the maximum allowed error and the cut size — that is, the maximum number of lights taken into account per sample.

Early tests show that the lightcuts version consistently outperforms the traditional rendering pipeline, even for fairly small amounts of lights. Results are not always correct though, especially when complex occlusions are present.

Let me clarify that although I am already receiving useful feedback from testers, there is a long list of limitations you have to be aware of before playing with my test builds. Here is a minimal and possibly incomplete checklist:

  • raytracing and shadowing must be enabled! This is not a current limitation: Lightcuts doesn’t make sense otherwise
  • all materials should be only diffuse, employing the Lambertian model (current limitation): disable specularity and/or set it to black
  • any other feature is not supported yet; in particular, ensure that the Bias toggle is turned off, or results could differ significantly
  • all lamps should be omnidirectional (”Lamp”), with Inverse Square falloff, and ray shadowing active
  • please ignore QMC settings: I am really using the old “single sample” lamps, not accessible from the UI anymore; fiddling with the settings could lead to inconsisten settings and eventually to crashes
  • it goes without saying: disable AO, SSS, whatever feature doesn’t look like a “plain” feature

I’ve also added a new render layer called “False Color“. It’s a visual debugging tool that shows per-pixel color-coded information. Right now, the red channel shows the ratio between used lights and maximum cut size: when it’s dark, it means that the algorithm took advantage of its metrics to aggressively save calculations; somewhat unintuitively, the most expensive parts to compute are the dark areas (in the actual picture, not in the false color one): having a relative error criterion means requiring a very accurate calculation precisely where the signal is weak, and that’s when the “max cut” limit is hit.

A sprouting tree

Published
by
UncleZeiv
on May 20, 2008
in Blender, Coding, GSoC 2008 and Graphics
. 0 Comments

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.

Use ack!

Published
by
UncleZeiv
on May 7, 2008
in Coding
. 1 Comment

By misspelling awk during a search, I’ve come to know a very useful utility: ack. I wholeheartedly suggest to install it and use it as a drop in replacement for grep in most circumstances.

Basically, it’s a developer-friendly grep that, by default, ignores many annoying things that tend to get in the way nowadays, such as .svn folders. Other common options, such as recursiveness and “operate on all files in this directory” are assumed without the need of explicitly typing them. The output is structured, colored and highlighted in a meaningful and useful way — but it still plays well in a pipe, where it reverts to a more sober, grep-like output. It maintains a small (but extendable) database of filetypes, so that you can ask for specific categories of files to be included or not: for instance –noshell ignores .sh, .bash, .csh, .tcsh, .ksh, and .zsh files.

It’s also actively maintained.

It’s already an indispensable tool for me. Go grab it, you won’t regret it!