PDA

View Full Version : Leverage fragment shader for efficient "cellular automata type" programs



abaababb
05-09-2017, 06:07 AM
I have a use case where I want to have grids of pixels interacting according to rules. If you are familiar with Conway's game of life, it isn't much different than this. One example might be, some red pixels are placed at some coordinate/location, and every frame the pixels near the red pixel's also turn red if 3 in the immediate proximity are already red, or some rule set like this.. So I've done this on the CPU by using a 2d array and a timer.. however these kinds of algorithms are not fast. I might have to loop over every pixel in this byte array and have an inner loop to process the neighborhood of each pixel so it becomes O(NPixels*NeighborhoodChecks) time complexity which is not always tractable to run on the CPU 30 or 60 times per second.

My question is how can I use the fragment shader to achieve greater efficiency?

GClements
05-10-2017, 12:28 AM
There are two main approaches:

1. Fragment shader with render-to-texture. You need two textures, for even and odd generations. Each step binds one texture (the source) to a texture image unit, and the other texture (the destination) to a framebuffer object (FBO). Set the viewport to the texture dimensions and render a pair of triangles to completely cover the destination. The fragment shader can determine the appropriate source texture coordinates as glFragCoord.xy*2-1 (i.e. transforming glFragCoord.xy from [-1,1] to [0,1]). After each step, the odd and even textures are swapped.

2. Compute shader with image load/store. This can be used with an even/odd pair, or a single texture can be updated in place. But there are no guarantees as to the order in which invocations occur, so you need to use explicit synchronisation (e.g. atomics) if you need to ensure that specific values are calculated before they are used.