Re: Sampling lights back

(L) [2011/12/21] [tby ingenious] [Re: Sampling lights] Wayback!

That's clear. Picking a light source from a discrete distribution that tries to match the importance of each light makes a lot of sense. I'm asking about the incentive to making the size of this distribution different than the number of light sources.

(L) [2011/12/27] [tby jbikker] [Re: Sampling lights] Wayback!

>> ingenious wrote:That's clear. Picking a light source from a discrete distribution that tries to match the importance of each light makes a lot of sense. I'm asking about the incentive to making the size of this distribution different than the number of light sources.
Sorry for not answering this quicker. The reason for using an array with a size larger than the number of light sources is O(1) access. A single look-up based on a uniform random variable yields a light source, selected with a probability proportional to the pdf. If we would store lights in an array that has as many elements as there are lights, or in a linked list, access time would be O(N).

(L) [2011/12/27] [tby spectral] [Re: Sampling lights] Wayback!

And how can you sample N lights with an array of N elements if you want to sample proportional to the PDF ?

(L) [2011/12/27] [tby jbarcz1] [Re: Sampling lights] Wayback!

>> spectral wrote:And how can you sample N lights with an array of N elements if you want to sample proportional to the PDF ?
Perhaps by allocating N*M spots, adding p*M copies of each light, then indexing with rand() % M ?
Neat trick, assuming I've guessed correctly [SMILEY :)]

(L) [2011/12/27] [tby jbikker] [Re: Sampling lights] Wayback!

[SMILEY :)] No, we simply allocate an array that is sufficiently large. We build games using path tracing, so it's OK to tweak this for a specific game. We use 1024 in most cases, but more if we have lots of lights.

(L) [2011/12/28] [tby spectral] [Re: Sampling lights] Wayback!

Thanks,
And how do you compute the PDF of each light and how do you distribute each light in the array ?

(L) [2011/12/28] [tby ingenious] [Re: Sampling lights] Wayback!

>> spectral wrote:Thanks,
And how do you compute the PDF of each light and how do you distribute each light in the array ?
0 0 0 0 1 2 2 2 2 2
if the array looks like this, then uniformly sampling it will result in 0.4 probability for picking light 0, and so on. You can have a separate array that stores the probabilities for each light index:
0.4 0.1 0.5
And this is unbiased. Though might be sub-optimal due to the quantization, i.e. if a light has a 1000 times higher chance of being selected than all other lights, then you need to enlarge the array. That's why a 1D discrete CDF is generally a better approach. Also, its sampling complexity is O(logN), not O(N).

(L) [2011/12/28] [tby spectral] [Re: Sampling lights] Wayback!

It is what 'jbarcz1' proposed but Jacco tell that No ! [SMILEY :-P]
But it is the approach that I've expected too [SMILEY :-)]
Thx

(L) [2011/12/28] [tby ingenious] [Re: Sampling lights] Wayback!

>> spectral wrote:It is what 'jbarcz1' proposed but Jacco tell that No !
Hm, looks similar indeed. Though I cannot understand Jacco's reply.

(L) [2011/12/28] [tby voidcycles] [Re: Sampling lights] Wayback!

What if you have more light sources than you can fit in memory?  Would you still use a discrete sample table?

(L) [2011/12/28] [tby jbikker] [Re: Sampling lights] Wayback!

>> ingenious wrote:Hm, looks similar indeed. Though I cannot understand Jacco's reply.
Hm, indeed, it's the same thing. Sorry for the confusion.
 >> voidcycles wrote:What if you have more light sources than you can fit in memory? Would you still use a discrete sample table?
That would be an interesting scene. [SMILEY :)] I target interactive rendering, so everything will definitely be in-core.

(L) [2011/12/29] [tby spectral] [Re: Sampling lights] Wayback!

How a scene cannot fit all the light sources in memory ?
You can play with 2 arrays :
1 - A array for the lights source, N lights mean an array of size N
2 - An array of indices that point to the first array
This way you can have a lot of lights...
Of course, it is still possible to do some out-of-core rendering if you really have a hughe scene !

(L) [2011/12/29] [tby franz] [Re: Sampling lights] Wayback!

Here's an article of interest about efficiently sampling discrete distributions: [LINK http://www.keithschwarz.com/darts-dice-coins/].  Of particular interest is the Alias method which can sample in O(1) with O(n) memory.  If I'm not mistaking, Jacco's technique is described in "Simulating a Loaded Die with a Fair Die".
Cheers,
Franz