teaching machines

How to make a 3-D present for your wife

July 13, 2012 by . Filed under algorithms, public.

In summer-fall 2009, I read Douglas Hofstadter’s Godel, Escher, and Bach. It took me that long. It was full of cleverness, but I think most of the message was lost on me. That’s okay, because I was inspired by the cover image to make my wife a keychain of her initials. Hofstadter carved what he calls the GEB triplet by hand from redwood with a band saw. I’m not so handy, but I do a lot of volume rendering and isosurface extraction. When I learned the College of Design at my university had a 3-D printer, I went to work.

Hofstadter's triplets.

Following is my algorithm for generating a triplet of your wife’s initials, though I suppose any three initials are fair game.

  1. Generate three images, one for each of your wife’s initials. Because these letters are going to be turned into a solid, choose a thick font face. I use Impact. Its lack of serifs reduces the number of sharp edges.
  2. To give each letter equal presence, autocrop all the images and rescale them to be the same size. To keep subsequent processing fairly speedy, I go with something like 128 by 128. Narrow letters like I and J will become very thick, but leaving them thin will result in a very small intersection volume. Add a 1-pixel border so that contour extraction will produce a closed surface. I accomplish this step and the previous with the help of ImageMagick’s command-line utilities: 
    #!/bin/sh

font="/usr/share/fonts/truetype/msttcorefonts/Impact.ttf"
size=126

for i in $*; do
  convert -font $font -pointsize 144 label:$i \
    -trim \
    -resize ${size}x${size}\! \
    -bordercolor white -border 1x1 \
    -threshold 99\% \
    $i.png
done
  3. Compose a 3-D array of integers. If the images are N-by-N, this array should be N-by-N-by-N.
  4. Effectively, what you need to do now is lay out each initial in the N planes of each dimension in the 3-D array. Initial 1 can be laid out along the planes in the first dimension, initial 2 in the planes of the second, and initial 3 in the planes of the third. Here, “lay out” means increment the 3-D array cell if the corresponding pixel is black. After you’ve laid out all three, you’ll find a 3 in all the cells that are black in each initial.A slightly simpler approach is to just march through each cell in the 3-D array and look to see if the corresponding pixels in all three initials are black: 
    for each voxel(x, y, z) in volume
  if pixel(x, y) of the first initial is black and
     pixel(z, y) of the second initial is black
     pixel(x, z) of the third initial is black
    voxel(x, y, z) = 1
  else
    voxel(x, y, z) = 0
  endif
endfor
  5. Extract an isosurface (using the Marching Cubes algorithm, perhaps) around contour 0.95 or similar.
  6. Depending on your array’s resolution, your model will probably be a bit coarse. Clean it up in your favorite 3-D modeling program. I use Blender. First I go into Sculpt Mode and smooth any sharp edges. Second I add a Smooth modifier to the mesh, set Factor to approximately 2.5 and Repeat to 30. The printer I use requires units to be in [0, 1] and the input to be in STL format, so I scale it down and export to STL. My result looks like:

    My initials triplet STL model.

  7. Wait for the printer to get fixed.
  8. Resubmit your job two more times until it finally gets processed.
  9. Present your gift to your wife, upon which she will swoon. The end result looks like something like this:

    My initials triplet, C-R-J.