Introduction
While I may appear on the outside to be a cold, heartless programmer, on the inside I’m a normal person who celebrates Valentine’s day like anyone else. That is, by writing programs. (and people ask why I’m single…)
XKCD once did a version of Sierpinsky’s triangles, but using hearts: http://xkcd.com/543/. So I decided that I could write a program that could render these “triangles”, but for arbitrary shapes.
And, once I can do it for arbitrary shapes, I can “heartify” all of the letters of the comic sans alphabet, and have a webpage with a text input to let people create their own heartified strings, for their sweetheart’s name or whatever:
I’ll pick on Sally for now, since she is convenient.
Web Server
Okay, this really is just a CGI script which calls the “montage” program to stitch together the 26 precomputed letters to form a word. Then it saves the resulting image to a file, and serves the file.
Data Processing
It just now struck me that image processing has been a theme for me recently…
Regardless, the hearts are created by using an iterative loop, each time around adding another layer of hearts. Each loop has 4 major parts: sizing, maximizing, disqualifying, and rendering. People familiar with the FRC Vision 2013 architecture may notice some similarities, specifically in the maximizing/disqualifying steps mirroring the point clouds.
Sizing is, as it’s name implies, determining the sizes of hearts that can fit into the current image. This is done for every pixel which may contain a valid heart, and for every pixel it determines the largest possible heart which fits into the legal regions centered at that pixel. This part really is as inefficient as it sounds - I loop through every pixel, and then start with a size 0 heart and step up the size until the heart no longer fits.
There are a few optimizations present, e.g. circles are used as a first-pass approximation to hearts because the hearts equation is long and complex:
theta = M_PI/2.0 - theta; r = (2.0 - 2.0 * sin(theta) + sin(theta) * sqrt(fabs(cos(theta))) / (sin(theta) + 1.4)) / 4.0;
Ergo, it is best to avoid computing this function where possible. Note that I have implemented a cache to accelerate this function through the use of lookups. The distance function leaves us with an image which looks approximately like:
In the above image, the white areas correspond to “illegal” areas where hearts cannot be, and the intensity of red corresponds to the largest heart which fits at the given pixel. Brighter indicates larger hearts can fit. Below is the distance image from the second iteration:
After the distances are computed, note that there are peaks and ridges of intensity. In order to fit the largest heart we can, we want to place hearts on these peaks and ridges. However, we cannot simply place a heart at every valley and peak - we would then run the risk of overlapping hearts. This is why we have the disqualifying step. All hearts are compared against each other, and overlaps are resolved by removing the smaller heart. Again, this is optimized by providing liberal caching and approximations.
Rendering is the simplest step. Wherever a heart is located, after the disqualification step, we simply draw a heart.
Then we repeat. Note how in the second distances image, there are black areas splotched onto the image. These correspond to the hearts which were placed onto the image in the first image.
Final result after 3 iterations:
Possible Future Changes
One thing that I’ve found makes this program exponentially faster is choosing smaller images. This is why each letter was computed individually, and not from a single large image containing all of the letters. In the future it would be nice to have the program automatically subdivide the image into smaller regions to process (or, alternatively, fix the algorithm so it’s faster on large images).
On a related note, I have done work on removing the need to recompute the distance map for the entire image every iteration. The theory is that we can determine how a given heart affects the distance map near it, so we adjust the distance map at render time instead of having to recompute it every iteration. However, I couldn’t get this code to work in time for Valentines, so it is commented out.
In order to make the algorithm more useful for other holidays, I think it would be nice to allow for different shapes and colors (not just red hearts). Also, people (you know who you are) complained about my use of Comic Sans, so maybe a font selector would be good.
Source Code
This project ended up on my GitHub account:
