Long story short: I made this thing:
Or to be technical, I made a thing that makes things like that thing. (If your device doesn’t render it, it looks like this.)
Backstory: a month and a half ago I left my job to make an indie game. One of the many things on my to-do list was “Learn shader programming”, and around that time I ran across this blog post by Roger Alsing about using genetic algorithms to create images. So I tried the same idea in 3D to experiment with GLSL.
Basically I run a pseudo-genetic algorithm on triangles in 3D space while comparing their 2D projection to a target image. The result is a chaotic bunch of polygons that happen to look like the target, but only when viewed from just the right angle.
Comparisons run on the GPU so it’s reasonably fast - 1M generations takes about 10 minutes for me, but it varies by target image and polygon count.
Open the example client and uncheck “Paused”. To change the target image just drag a local file onto the page. (Note: might not work on older video cards.)
Conceptually, the algorithm is extremely simple:
- Generate random data to serve as vertex positions and colors.
- Render the data as triangles.
- Compare the result to a reference image and generate a score for how closely they match.
- Randomly perturb the data, generate a score for the result, and keep the new data if the score has gone up.
- Repeat step 4 until the output is interesting enough to write a blog post about.
That’s it, nothing fancy. What’s (possibly) interesting is that all the heavy work is done on the GPU, including the step of comparing the candidate image to the reference. I wanted to keep things fast and I wanted to try out GPGPU, so I wrote shaders to do the comparison on hardware.
One wrinkle with all this is that apparently WebGL does not support reading floats from the GPU, only integers (which are clipped to the range 0-255). Some have cleverly worked around this by encoding floats on the GPU, but to keep things simple (too late!) I treated the RGB channels like a three digit decimal in base 256, which seemed to be plenty of resolution to detect even small changes in image similarity.
When I started this I expected that finagling with the implementation might greatly affect the performance. However, profiling showed that the time spent waiting to read data off the GPU (even a single pixel) dominates everything else by a factor of 5-10. So I feel reasonably confident that the only way to significantly speed up generations would be to run several at once, reading back several results at a time. With that said, improving the “genetic” part of the algorithm could probably make it converge to better results in fewer generations. (I haven’t tried this - I’m learning GLSL here dammit, not GP!)
GLSL-Projectron on github. Issues and pull requests welcome. The core library that does all the solving is a requirable module, and the
docs folder has a sample client app that provides the UI.