This is a recent experiment I did which had two main inspirations. The first was an experiment by Roger Alsing: he wrote a simple program that took the Mona Lisa as input and had an algorithm optimize a set of polygons to approximate that image as closely as possible. The results are quite remarkable. However, this experiment varied the number of vertices per polygon and thus was able to alter the final geometric complexity that was being used.

The second inspiration came from a blog post by Simon Trümpler which explained how Homeworld 2 was rendering its background art back in the day. I find the idea to use a triangle mesh with vertex color interpolation instead of an environment map very creative.

I started to combine these ideas in my head: how far can you get when you want to approximate a given image with a soup of triangles with interpolated colors? The first approach was to take a fixed number of triangles and randomly vary their vertex positions and colors and see if the new triangle soup does a better job at approximating the target image. Unfortunately, this approach turns out to be far too naive. It gets cought up in local minima with groups of triangles representing image features just well enough that breaking them up is impossible. But at the same time, they don’t represent the final image well enough to be acceptable. The result is a terribly slow convergence which stops before it actually resembles the input.

Thus, I decided to constrain the search space a lot. Instead of random triangles with blending, my next attempt used a regular mesh of triangles. The vertices of this mesh are still free to move as long as the whole image area stays covered by the mesh. The mesh also may not self-intersect. And and the image colors at the current vertex positions are taken as hints for the vertex colors being used. If you give this algorithm time, it starts to converge to acceptable results. However, it will still show considerable deviations from the input image in some regions, which may not be what you want.