Practical and theoretical implementation discussion.
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).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.
Perhaps by allocating N*M spots, adding p*M copies of each light, then indexing with rand() % M ?spectral wrote:And how can you sample N lights with an array of N elements if you want to sample proportional to the PDF ?
Neat trick, assuming I've guessed correctly
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.
0 0 0 0 1 2 2 2 2 2spectral wrote:Thanks,
And how do you compute the PDF of each light and how do you distribute each light in the array ?
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).