Sunday, October 11, 2015

Generating a large number of pseudo-random numbers in WebGL/OpenGL

I needed to make a large number of random numbers, but OpenGL doesn't really give a function that does this. I found a few quick and dirty tricks on the internet to get random like textures, but I really wasn't satisfied with the results. So I went a different path to try to get good results and performance.

Here is a demo of the generator: http://kcdodd.github.io/random-webgl/

My current implementation starts with a large random texture being pre-computed and loaded to the gpu, call it S. Each pixel is a random rgba value with uniform distribution between 0 and 1. This texture is constant and serves as a source of entropy for random values.

My random texture is also initialized with it's own random values, call it texture H, which is smaller than S. H.b, and H.a (blue and alpha channels) represent a texture position in S. At each iteration, H is updated by computing a new position, and looking up new values in S. S.b and S.a are mixed into H.b and H.a in a non-linear way to provide addition entropy to the position from which S itself is being sampled. However, this causes H.b, and H.a to not have a uniformly random value in the way I have done it, and is why I don't simply use that method directly for random values.

S.r, and S.g are sampled to preserve the uniform distribution of H.r and H.g (red and green), which are the values I will actually use as random numbers, ignoring the blue and alpha. They are simply added together, then mod 1 to stay on the interval [0.1].

To step the position in S, I am using the logistic map function with r = 4.

\[x^{i+1} = 4 x^i (1 - x^i) \]

I have tried to use this before as a random number generator, since it is chaotic by itself, but I have never been able to get a very desirable distribution from it. However, I don't really care about the distribution of positions, since it is the distribution of values it looks up that matters. As long as the two are independent of one another, I should get a uniform distribution, with a long non-repeating sequences due to the logistic map.

The random texture (red and green channels) can be thought of a random permutation of a random subset of S, both of which change in a chaotic way.

Just to mix the position a little further, I mix a small amount of S into x as well at each step (currently 0.1% worth). This means that the next value it generates is a function of the entire history of that pixel.

Here is the fragment shader for stepping H (which is called u_rand). S is u_entropy.


No comments:

Post a Comment