## Sampling lights

Practical and theoretical implementation discussion.
ingenious
Posts: 282
Joined: Mon Nov 28, 2011 11:11 pm
Location: London, UK
Contact:

### Re: Sampling lights

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.

jbikker
Posts: 224
Joined: Mon Nov 28, 2011 8:18 am
Contact:

### Re: Sampling lights

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).

spectral
Posts: 382
Joined: Wed Nov 30, 2011 2:27 pm
Contact:

### Re: Sampling lights

And how can you sample N lights with an array of N elements if you want to sample proportional to the PDF ?
Spectral
OMPF 2 global moderator

jbarcz1
Posts: 6
Joined: Sun Dec 11, 2011 11:47 pm

### Re: Sampling lights

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

jbikker
Posts: 224
Joined: Mon Nov 28, 2011 8:18 am
Contact:

### Re: Sampling lights

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.

spectral
Posts: 382
Joined: Wed Nov 30, 2011 2:27 pm
Contact:

### Re: Sampling lights

Thanks,

And how do you compute the PDF of each light and how do you distribute each light in the array ?
Spectral
OMPF 2 global moderator

ingenious
Posts: 282
Joined: Mon Nov 28, 2011 11:11 pm
Location: London, UK
Contact:

### Re: Sampling lights

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).

spectral
Posts: 382
Joined: Wed Nov 30, 2011 2:27 pm
Contact:

### Re: Sampling lights

It is what 'jbarcz1' proposed but Jacco tell that No !
But it is the approach that I've expected too

Thx
Spectral
OMPF 2 global moderator

ingenious
Posts: 282
Joined: Mon Nov 28, 2011 11:11 pm
Location: London, UK
Contact:

### Re: Sampling lights

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