Weighted Random Pick of RGBA

[mikegi]

In a pixel shader I calculate the probability of 4 items in RGBA (R+G+B+A = 1.0). Now I want to randomly pick one weighted by its probability. For example, lets say that R=0.6 and A = 0.4 and G,B = 0. That means that 60% of the time I want to pick R and 40% of the time I want to pick A. An easy but lengthy way to do this would be to make X = R, Y = R+G, Z = R+G+B, choose a random number between 0 and 1.0, then test the random number against XYZ:

float4 sum;
float random;

sum.X = prob.R;
sum.Y = prob.R + prob.G;
sum.Z = prob.R + prob.G + prob.B;

random = MyRandomFunction();

if( random < sum.X )
  pick R
 else if( random < sum.Y )
  pick G
 else if( random < sum.Z )
  pick B
 else
  pick A

Is there an easier way based on some HLSL PS instruction?

Thanks

 

[armchair_architect]

You could probably use a table lookup (using 1D texture, or in DX10 maybe a constant buffer). Say you create a 100x1 RGBA texture, fill the first 60 pixels with (1.0,0,0,0), the next 40 with (0,0,0,1.0). Since your random function gives you a number in [0..1] you can use that as the 's' coordinate in your texture lookup. Do a dp4 of the texture value with your RGBA value, and it'll pick out the right component.

If your random function is itself a texture fetch, you could bake both textures together so you only need a single texture lookup.

 

[Davros]

generate random number between 1 and 100 if less than 61 choose r else choose a

 

[sebbbi]

How about this version without any dynamic branching and some vectorized (3d/4d) operations thrown in. Should be much faster than your version:

psInput.RGBA = input data
psInput.prob = input data propabilities

float random = MyRandomFunction();
float4 sum = psInput.prob.r;
sum.gba += psInput.prob.g;
sum.ba += psInput.prob.b;
sum.a += psInput.prob.a;
sum = ceil(saturate(sum - random));
sum.gba -= sum.rgb;
return dot(saturate(sum), psInput.RGBA);

Should be correct, unless I (most likely) made a typo or two in my calculations

 

[mikegi]

sebbbi is on the right track. Here's a modification of his approach:

float random = MyRandomFunction();
float4 sum;

sum.rgba = prob.r;
sum.gba += prob.g;
sum.ba  += prob.b;
sum.a   += prob.a;  // resulting sum.a always = 1.0

sum = step( random, sum );  // all sums > random = 1.0 afterwards

sum.gba -= sum.rgb; // shift and subtract leaves only first 1.0 in rgba

// I use the result to select one of four rows in a data-to-color LUT

tex.y = dot( sum, float4( 0.125, 0.375, 0.625, 0.875 ) );
tex.x = data_value;

I believe this will work assuming that the random function ALWAYS returns a number less than 1.0.

 

[sebbbi]

Yes, you are correct. step() function does basically the same as the saturate and ceil in my approach. Also there is one extra saturate() at the return statement in my code. I quickly calculated the algorithm on my scratch pad, and that saturate was left from my earlier solution (that was not as optimal as this one). Otherwise our solutions look the same.

 

[nAo]

If you need a cheap pseudo random number generator that doesn't involve sampling a texture or a constants buffer:

unit32 rand(uint32 seed)
{
    uint32 mod = seed & 0x1f;
    return 0x7UL + ((seed >> mod) || (seed << (0x20 - mod)));
}

This was just 2 instructions back in the 680x0 days but shader model 4 doesn't support bitwise rotations AFAIK.

 

[mikegi]

Yes, an inexpensive random number generator will be necessary. I still haven't tackled that one. It'll need to be compatible with SM2. To get one that varies over the screen I'll need to get the screen coordinates and use them to look into a 2D random texture.

There will be two display modes: the first will simply find the maximum probability and use that row in the data-to-color LUT, the second will be the one that does the random weighted look up. I have both in C++ for my noninteractive app. Now I need them in my interactive app and they need to be pretty zippy since it'll cover the entire window most of the time.

Most users prefer the look of the randomized technique and it matches well will the physical reality. My several-orders-of-magnitude larger competitors don't know how to do it (even in software)!

 

[mikegi]

Wanted add that I finally got around to implementing this weighted random picker and it works perfectly. The most difficult part was creating a decent random number generator.