Efficient sampling of many lights

[cessen]

No matter how long what runs? The algorithm, as presented in the paper, always runs a finite amount of time for a fixed number of initial virtual point lights.

In the paper they put it in the context of a ray tracer that is still shooting eye rays. So I was imagining that e.g. antialiasing and DoF would still be computed with monte carlo ray tracing. But you're right, that's not actually part of the algorithm itself. So more simply, it just won't converge.

Every unbiased method has been originally described as a single-pass finite-sample algorithm. Progressive rendering with an "outer loop" came much later, so in that regard Lightcuts is on the same "level" as path tracing.

Yeah. Although I think there is a difference in presenting an algorithm as one-pass, and presenting an algorithm as arbitrarily many passes. Both are finite, but the latter typically implies some kind of limit solution.

EDIT: Err... mixing up my terminology. The above should have read:
"Yeah. Although I think there is a difference in presenting an algorithm as single-sample, and presenting an algorithm as arbitrarily many samples. Both are finite, but the latter typically implies some kind of limit solution."

Or something along those lines, anyway.

[phkahler]

I tried something a bit similar several years ago. My goal then was to use photon mapping for indirect lighting and rays for direct lighting. I put all light sources into an octtree. The lights would be inserted in the tree using a bounding box based on brightness. You could use more arbitrary shapes if you had a way to determine a relevant bounding volume. Then for illumination at a point, you'd just drill down the octtree nodes containing that point and use the lights at each level. My trees allow object (in this case lights) at all levels, not just leaf nodes. I had a maze with a light at each "corner" position running 1280x1024 at 5-10fps with over 200 lights (no photon map).

I've always considered a city like you show - with thousands of lights in a polygon soup, and lots of people walking around - to be a goal.

[cessen]

Never got around to writing a paper on the technique in the OP, but it looks like someone else did!

http://jcgt.org/published/0005/01/02/

The second half of the paper describes a technique essentially the same as my OP, but in more formal terms. Really cool! Hopefully this approach will get more visibility now, and perhaps further research.

EDIT:
It seems I maybe got a little over-excited. I read the paper again more thoroughly, and the technique they present isn't quite the same. To converge to a consistent result, their approach requires multi-pass progressive rendering, whereas the approach in my OP works quite happily within a single pass. Nevertheless, the concepts are very similar! Variations on the same theme.