For some details on the algorithm and implementation, see below ^^
Once upon a time I saw some images generated with basic shapes that tried to approximate some given image. Because I like the style, I made something like that myself. Problem was: There aren’t many good libraries to perform drawing shapes that also handled transparency and per-pixel operations. Coding all of that myself was too much work, so I used the easiest solution: JavaScript. Problem was... JavaScript is slow. Drawing a few hundred triangles and then comparing the resulting image to another given image was a lot of work, even using multiple workers to distribute it. I got maybe 5-10 images per second that way. The algorithm I use is pretty simple but slow... so it took hours for at least some reasonable results.
A few days ago I decided to revisit this thing with the help of my trusty GPU. Basically I redid everything so it runs completely on the GPU. I now have about 600 images per second!
Here you can see some of my most liked pokemon :)
Following are some more details on how it works:
The algorithm: Take a set of triangles. Each consisting of three 2D vertices and a color with transparency. Now you draw them all. Now you compare the resulting image with the one you want to approximate. This can be done for example by comparing each pixel and adding the squared differences of each color channel (squaring makes everything positive, which is good, and also is a nice and smooth function). If the result is better than your current best, use this new one as your new best. Now you go over your triangles and with some probability change their vertices or colors. Then repeat from the drawing phase. This is a simple hill climbing algorithm. If you are more precise, this isn’t really a evolutionary/genetic algorithm, as there isn’t a population with stuff like crossover happening. But being a bit more informal here (and for the title to make sense :D) I will still call it evolutionary. Just think of it as having a single individual reproducing. Only the best will survive and live as long as it stays the best, outliving all its children. Each generation mutates slightly and has to adapt to the environment. So I would say the naming is at least a bit justified.
The implementation: If you want to do something like this, here is the general recipe. You generally want to avoid transferring data from your CPU to the GPU and back, as copying stuff needlessly is not good. My implementation uses OpenGL, but you may choose any other API, as long as it provides compute shaders and writeable buffers (you could of course emulate that with textures or other techniques, but that would require some more thinking). You put all your triangle data in a buffer. I use one vec2 buffer for the positions (length = triangles*3) and one vec4 buffer for colors (length = triangles). Those buffers are bound as a shader storage buffer object (SSBO) and can be accessed by all shader stages. One Compute shader updates the triangles. Each work item processes one triangle. The only important thing here is, that you have to implement your own pseudo-random number generator. Probably the best way is to upload some initial random seeds and then use a simple linear-congruental generator (https://en.wikipedia.org/wiki/Linear_congruential_generator). I use a more involved Tau-step generator, which is probably overkill, but I had it l lying around (used it in monte-carlo simulations, where the randomness is a bit more important).
The drawing phase can be very simple. Just bind your SSBOs as vertex buffer objects and draw with triangles mode. Or the more complicated (which I did for some reason, probably because of some other code I used elsewhere...): Draw n=triangles instanced points. Use a geometry shader to generate a triangle for each point from the buffers. Then just render normally. Will probably change that and hope to see some improvements. The result is rendered in a frame buffer object with attached color texture.
The next step is just some screen quad/triangle shader comparing each pixel of the input image with the rendered one and calculating the difference. This is again put in a frame buffer object texture.
The important part is the error calculation. If you use some kind of sum of values, which is probably reasonable, you have the problem of it being more of a sequential algorithm. Luckily there is a parallel sum algorithm (for example here https://developer.nvidia.com/gpugems/GPUGems3/gpugems3_ch39.html). If you render the drawing in a frame buffer object, you can bind the output texture as an image and use it for read/write operations. Thinking about the image being just rows (or columns) layed out sequentially, it is easy to transfer the 2D image sum problem to a 1D one corresponding to the algorithm.
A simple shader with only one dispatch item just copies the result into another SSBO, where the current maximum is also stored.
Next compute shader goes over all triangles. If old error in the SSBO is larger than the current one, this will just copy the contents of the current triangle buffer to the “best” buffer.
Only copy to CPU and back operation I do is to download the error and draw the image on the screen and for some error difference output it as a file. Then upload the buffer with the updated current best error.
And that was basically all, in short form of course. You can of course do a lot better. Much to optimize, maybe use a real evolutionary algorithm, etc... But this was more or less a short two evening project, so it’s alright for now ^^
