Friday, March 18, 2011

Iteration on the GPU

I took a class on programmable shaders and GPUs this quarter. This special topics graphics class was easily the class with the 'freshest' material that I've taken thus far in grad school. And I have been yearning to learn about shaders ever since I heard the graphics class the year after me in undergrad got to learn about them!

Final Project: Iteration on the GPU
The final project was to use the CPU and GPU to make pretty pictures. I chose to GPU-ify Iteration, the generative art program you may have seen in such forms as iphone app ( and java applet ( The result of my work (including the epic battle with DirectX) is an interactive generative art composer. Previous iterations of Iteration involve repeated clicking and hoping for the next random design to be more awesome than the last, and then waiting a bit for the design to fill in.    While this certainly tickles the intermittent-variable-reward part of folks' brains, it gets old because there's nothing for the user to actually control or interact with. The GPU version of Iteration, however, allows for real-time exploring and previewing of possible designs, and then controlled compositing of different designs together.

User moves the mouse to preview different design shapes and then clicks to burn/composite the current design into the background.

User Interaction
If I had sweet video-taking capabilities (should I take a video with my phone??) I would show you what it looks like to actually interact with this program. It is pretty mesmerizng. Moving the mouse around changes the shape of the curves, sometimes bringing attractive spirals into focus or smearing out the design into a burst of rainbow colors. There are keys to change colors, to pick new random parameters, to change which two parameters of the function the mouse position controls, and to save the image as a jpeg. Using the mouse, the user can burn the current design into the background, translate the current previewed design to a more optimal position, or dim the background to give new designs a subtle backdrop to stand out against. Here are some example compositions!

So what's going on here that a) generates the pretty pictures and b) makes this a good problem for the GPU to solve? Iteration at heart is an iterated function system ( There is a function mapping 2D points to 2D points that is made out of sines, cosines and whatever other crazy junk we want. We start with a whole bunch of random 2D points, stick it through this function 1, 2, ... n times, and accumulate the points on screen after every iteration. To make these pictures nice and smooth (rather than noisy and grainy), we need LOTS of sample points and to draw each point with a very low alpha. In the case of the final GPU-Iteration, there are ONE MILLION POINTS getting iterated TWENTY TIMES... PER FRAME. That means that TWENTY MILLION POINTS are getting plotted each frame. And it's still real time. (As long as I don't try to recalculate a new 1 million random numbers.)

The great thing about this problem is that each point is iterated independently of every other point. And shaders are great at moving and drawing tons of points in parallel. I just use a vertex shader to apply the function to each point, and then a pixel shader to draw that point to the screen. The complicated bits are that I have a doubly-nested loop to make sure each point is drawn after every iteration instead of only after the final iteration (although I could have figured out how to use geometry shaders instead) and that I accumulate the color values into a buffer with one 16-bit float per color channel so I can add up very small alphas.

I'll throw my ugly DirectX code online and maybe sometime in the future use my shader knowledge to make a new version for android or flash (molehill!) or webgl.

Background: Right around the time I was working on this, some undergrads at my school (from the games lab, even!) won the UW Yahoo Hack U! contest with their katamari-for-the-web-browser game So... Katamari Damacy music is rolling gently around the back of my head. Then, I'm trying to make two windows (with different buffers, textures, contexts, devices, etc.) so I can have distinct explorer and composition windows. (This is before I combined them into a single window.) I'm feeling pretty lazy so I try to make my directx contexts/devices share certain resources, like the vertex buffer and the vertex buffer layout description. When I click Run, I am suddenly staring into the cosmos...

Cosmos Iteration!

...and I wind up wasting several hours generating one pretty speckly sparkly picture after the other until I finally try to figure out why they're like that. I swear I was going somewhere with that cosmos<-->katamari connection... Anyway, I replace the fancy iterated function with the identity function and get this fancy-shmancy plot of my computer's memory! So THAT's what's making the iterations come out as a glamorous, colorful star field, this semi-regular, non-random, non-uniform pattern.

Mmmm, memory.

That surprise was probably my favorite part of this assignment.