Installation

DoMosaic has been tested on linux and a mac using homebrew. It should work on other unix systems too. Please let me know (domino at rubels.net) if you get it going.


To run DoMosaic you'll need to install the following prerequisites:

  1. Ruby
  2. ImageMagick
  3. glpk (GNU Linear Programming Kit)
  4. A way to turn ps into pdf ala ps2pdf from ghostscript or the ps2pdf website
  5. rmagick (gem install rmagick)

Once you have the prerequisites installed its time to generate the plans. Here's one example.


Imagine you want to make a portrait of Jamie Hyneman. He's a good example as he has a number of distinct facial features. First we'll need an image. I find that wikipedia is a good source of images that are freely available. Going there we find the picture to the right.


People are quite good at making out faces, even terribly pixilated ones. Since we don't have many pixels (each domino half can be through of as one pixel) we want to leverage the pixels we do have to the fullest. To maximize the impact per domino we'll crop the image to be just the face. You can use the selection tool in gimp to copy the desired region. Then open up a new image and paste the selection and auto-crop the image. Here's our picture after cropping:

Now we're ready for the real fun, generating the model that we'll solve and use as input to create the plans:

$ ./fill.rb  -s 12 hyneman-crop.jpg 
Model generated to hyneman-crop.12.mod
$
The above step may take 10 seconds or so. You then want to check the aspect ratio. 

$ head hyneman-crop.12.mod 
/* Optimal aspect ratio: 85.0/120.0 => 0.708333333333333 */
/* Actual aspect ratio:  30/44 => 0.681818181818182 */
/* to run: glpsol --intopt --tmlim 40000 -m hyneman-crop.12.mod \ 
                  -o hyneman-crop.12.sol */
/* Options: Sets:12 Spots:9 Optimizing to use all dominos. 
            Mixed orientations */
/* Image will be 30x44 squares (a domino contains 2 squares) */
$

Note that our actual and optimal aspect ratio are pretty close. This ensures that the final result won't look stretched. (It took me two tried to crop the image just right.)

Now we need to solve the model. We just use the command line noted above. (Note that glpsol on 64-bit systems doesn't support the --intopt argument so you may need to remove it. I'm on 32 so I'll leave it in. If you're unsure, just try, you'll get a message if intopt isn't supported.) This step may take a while, particularly if you choose more than 12 sets. Let it run overnight. You can set a maximum running time in seconds with --tmlim. 

 
$ glpsol --intopt -m hyneman-crop.12.mod  -o  hyneman-crop.12.sol
GLPSOL: GLPK LP/MIP Solver 4.39
Reading model section from hyneman-crop.12.mod...
Reading data section from hyneman-crop.12.mod...
18679 lines were read
...
|7421400: obj =   6.694000000e+03  infeas =  8.723e-11 (884)
|7421419: obj =   6.694000000e+03  infeas =  1.011e-10 (884)
+7421419: >>>>>   6.694000000e+03 >=   6.694000000e+03 < 0.1% (414; 329)
+7421419: mip =   6.694000000e+03 >=     tree is empty   0.0% (0; 1157)
INTEGER OPTIMAL SOLUTION FOUND
Time used:   227899.7 secs
Memory used: 422.9 Mb (443423212 bytes)
Writing MIP solution to `hyneman-crop.12.sol'...

Phew, that took a while. Now lets generate a postscript file.

$ ./to_dom.rb hyneman-crop.12.sol > hyneman-crop.12.ps

And to now a pdf, which prints better. 

$ ps2pdf hyneman-crop.12.ps

Voila. Your plans are ready to be opened up in acrobat reader or your favorite pdf viewer and you're ready to order dominoes. The most inexpensive source of dominoes I've found is eNasco.

Aside: How to make a jpg from a png:

$convert hyneman-crop.12.pdf hyneman.jpg

If you do use this program to make a mosaic please send me a picture: domino at rubels.net