Hi all!

I am looking for an efficient way to shuffle an array in plain HLSL (i.e., create a random sequence where every index is used exactly once).

I've learned so far that Fisher–Yates shuffle (Knuth shuffle) algorithm would do the job, but I didn't find any implementations in HLSL so far. So I tried implementing the algorithm myself but the naiv approach of transforming code from a different language like C++ into HLSL produces rather slow running results.

Any ideas for a really fast way to achieve this?

It's possible that your implementation could be improved. You could try posting it here for suggestions.

You may also be able to set up your own LCG with a period matching the array length, if you know the length up front.

Hmm, I might have chosen the wrong approach anyway.

What I actually need is a deterministic function that takes an index and a range limit number as input and returns a unique "shuffled" number not larger than the specific limit.

int f (int index, int limit)        // returns a value between 0 and limit

Example: Range / upper limit of 1000 --> input and return value have to be between 0 and 1000:

f (1, 1000)   -->  724
f (2, 1000)   -->  28
f (3, 1000)   -->  301
f (4, 1000)   -->  513
f (500, 1000) -->  8
f (999, 1000) -->  148

Where each return value will occur exactly once (and within the specified range).

So basically the same as shuffling and querying an array of 1..1000, but ideally without having to define and iterate through an array.

Any ideas?

Wouldn't this be a lot simpler to calculate on the CPU and upload the result to a buffer or texture?

Wouldn't this be a lot simpler to calculate on the CPU and upload the result to a buffer or texture?

Yes it would, but in my case that's not possible. I need to do it inside a post-processing pixel shader.

How often do you need this to run? And must it be different (but still deterministic) each time?

How often do you need this to run? And must it be different (but still deterministic) each time?

Once for each pixel on the screen (per frame, of course). Can (no, must) be the same result each time.

Where each return value will occur exactly once (and within the specified range).

So basically the same as shuffling and querying an array of 1..1000, but ideally without having to define and iterate through an array.

There's no way the GPU can know if a return value has previous been used without caching every value and checking each one serially - what is exactly what GPU's are bad at.

If I understand you correctly, you're trying to create a screen sized array of unique values which never change, but re-create them each frame in the most inefficient way possible? If that's correct, just calculate it on the CPU and store it in a screen sized texture. If I'm wrong, tell us exactly what it is you're trying to achieve.

There's no way the GPU can know if a return value has previous been used without caching every value and checking each one serially

That's why I need a deterministic (mathematical) function doing it. I don't intend to calculate anything just to store/cache it, I wan't to call a function that always returns the same value for the same inputs, but that value should be nothing continuous or linear but something like "fixed noise".

If I understand you correctly, you're trying to create a screen sized array of unique values which never change, but re-create them each frame in the most inefficient way possible? If that's correct, just calculate it on the CPU and store it in a screen sized texture.

In the most efficient way, not most inefficient. And as I said, calculating anything on the CPU is out of scope here. It has to be done on the GPU, and purely in HLSL. Using any additional textures is not an option either.

If I'm wrong, tell us exactly what it is you're trying to achieve.

Ok, I'll try, although I have to simplify much to avoid writing a novel...

Imagine I wanted to have the entire screen black (ie. no pixels colored), and then highlight one pixel after another, depending on a single variable passed from the CPU to the GPU, holding a value between 0 and 1. Value 0 means all pixels are black, Value 1 means all are highlighted, any value between stands for the percentage of highlighted pixels.

The application (CPU) starts increasing from 0 to 1, so that one pixel after the other will be highlighted. This happens in a "random" or "noisy" way, but still deterministic. For example, the first value larger then 0 (say 0.001) will always highlight the pixel at screen position (0.325, 0.871) with all other pixels remaining black. The second step (e.g. value 0.002), happening for example 0.1 seconds later, will additionally highlight pixel (0.728, 0.523) where the first pixel will remain highlighted - and so on, until the whole screen has been highlighted. At no point during the process (ie. while increasing the passed value), any pixel that had been already highlighted will be black again.

So, at every time (for every value passed from CPU to GPU) it is defined which pixels have to be highlighted (whatever "highlighting" might be, pixel shader wise).

Has that become clear now?

Yes, but it still doesn't explain why you can't do this math once on the CPU, generate a texture (once), and then just bind it in your post-process shader...