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

Post by ingenious » Wed Dec 21, 2011 11:30 am

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.
Image Click here. You'll thank me later.

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

Re: Sampling lights

Post by jbikker » Tue Dec 27, 2011 3:09 pm

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

Post by spectral » Tue Dec 27, 2011 3:34 pm

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

Post by jbarcz1 » Tue Dec 27, 2011 5:35 pm

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

Post by jbikker » Tue Dec 27, 2011 8:15 pm

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

Post by spectral » Wed Dec 28, 2011 8:14 am

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

Post by ingenious » Wed Dec 28, 2011 9:34 am

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).
Image Click here. You'll thank me later.

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

Re: Sampling lights

Post by spectral » Wed Dec 28, 2011 10:24 am

It is what 'jbarcz1' proposed but Jacco tell that No ! :-P
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

Post by ingenious » Wed Dec 28, 2011 11:12 am

spectral wrote:It is what 'jbarcz1' proposed but Jacco tell that No ! :-P
Hm, looks similar indeed. Though I cannot understand Jacco's reply.
Image Click here. You'll thank me later.

voidcycles
Posts: 2
Joined: Wed Dec 28, 2011 5:00 pm

Re: Sampling lights

Post by voidcycles » Wed Dec 28, 2011 5:03 pm

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

Post Reply