NineBlocksPerlReview


In Press Version

This article is in press. The most recent version of the code is at NineBlocksPerlReviewCode. Please visit PickyQuilters for discussion of the article.

Quilt Patterns

I've been having fun playing with GD.pm and quilting patterns. The idea comes from Jared Tarbell, an artist and programmer who has made amazing art with Flash and Java. When I saw the quilt patterns he made on his site (http://www.complexification.net/gallery/machines/nineblock/ ), I decided they would make a perfect Christmas present for a quilter.

The author has open-sourced his code, but I do not have access to the Macromedia tools to read it, so I re-implemented it from the description on his site, with changes to print the squares in color. Since then, my local Perl Mongers group, in particular Eric Maki, have made further improvements.

Problem Description

"Nine blocks" have 9 squares in a 3x3 grid. Each square is limited to 16 basic patterns, which can be rotated in 90 degree increments.

A nine block can be specified by a corner square and its rotation, an edge and its rotation, and a center, which must be radially symetric (patterns numbered 1,5,9, and 16 above). The corner and edge are then repeated four times around the center.

Here's a sample showing each possible center, edge, and corner. The first block has corner 1, edge 2, the second has corner 3 and edge 4, and so on.

These blocks are easily drawn using the GD library by Thomas Boutell and GD.pm by Lincoln Stein. Because the programmer can build up GD::Image objects from primitives into complex composites, GD makes rapid development easy. Objects can be losslessly rescaled, rotated, copied, and recolored with little effort.

How I Began

I started by mapping out the points for each pattern, on graph paper. The second step was figuring out how to draw them. The Perl Graphics Programming book, by Shawn Wallace, published by O'Reilly, was helpful. The first code I wrote looked a bit like this, and plots a few of the basic patterns:

#!/usr/bin/perl -w
use strict;
use GD;

# See further example for easier
# to understand format.
# in-order list of end points for each square
my @squares = (
   "0,0; 1,0; 1,1; 0,1",
   "0,1; 1,1; 1,0",
   "0,0; 0.5,1; 1,0",
   # continued for squares 4-16
   );

my $sqSize = 100; 

sub square {
   my ($points) = @_;

   my $image = new GD::Image($sqSize,$sqSize);
   $image->colorAllocate(255,255,255);
   my $black = $image->colorAllocate(0,0,0);

   my $poly = new GD::Polygon;

   for my $pair (split /\s/, $points) {
      $pair =~ /([\d.]+),([\d.]+)/;
      $poly->addPt($1 * $sqSize, $2 * $sqSize);
   }

   $image->filledPolygon($poly, $black);
   return $image;
} 

sub display {
   my ($image) = @_;
   open OUTFILE, ">temp.png" or 
      die "couldn't open temp.png";
   print OUTFILE $image->png;
   close OUTFILE;
}

# main code: copy squares onto new background
my $image = new GD::Image($sqSize * @sqares, 
                          $sqSize);
my $xpos = 0;

# plot all patterns horizontally
for (@squares) {
   my $square = &square($_);
   $image->copy($square, $xpos, 0, 
                0, 0, $sqSize, $sqSize);
   $xpos += 100;
}
&display($image);


Drawing a Nine Block

The next step was drawing a block of nine squares. I did this by calling the &square() routine three times: once each for a corner, edge, and center. The corner and edge are then rotated a random number of times. To generate the centers, I just defined them in the same way as the @squares array. Lastly, the corner and edge piece are duplicated onto a new image, four times (with rotation and translation to the appropriate locations).

sub nineblock {
   my ($edgeRot, $cornerRot, $edgeShape, 
      $cornerShape, $centerShape) = @_;
        
   my ($edge, $corner, $center) = 
       (&square($squares[$edgeShape]),
        &square($squares[$cornerShape]),
        &square($centers[$centerShape]));
   
   $edge = $edge->copyRotate90   
      for (1 .. $edgeRot);
   $corner = $corner->copyRotate90 
      for (1 .. $cornerRot);
   
   my @etc = (0, 0, $sqSize, $sqSize);
   my $image = new GD::Image(3 * $sqSize,
                             3 * $sqSize);

   $image->copy($center, $sqSize, $sqSize,
                @etc);
   
   # duplicate corner/edge x 4
   # need relative positions of corner/edge
   my $xOfBlock = 0;
   
   for my $square ($edge, $corner) {
      my $max = (2*$sqSize - $xOfBlock);

      $image->copy($square, 
                $xOfBlock, 0, @etc);
      $image->copy($square->copyRotate90, 
                2*$sqSize, $xOfBlock, @etc);
      $image->copy($square->copyRotate180, 
                $max, 2*$sqSize, @etc);
      $image->copy($square->copyRotate270, 
                0, $max, @etc);
      $xOfBlock += $sqSize;
   }
   return $image;
} 

To finish this program, use all of the above subroutines with the following:

my @centers = (
   "",
   ".25,.25 .25,.75 .75,.75 .75,.25",
   "0,.5 .5,1 1,.5 .5,0",
   "0,0 1,0 1,1 0,1"
   );

my $image = &nineblock(
   int rand 4, int rand 4, # rotations
   int rand 3, int rand 3, # shapes
   int rand 3              # center shape
   );

&display($image);

Revisions and Improvements

It was easy to build a large GD image containing many quilt blocks. I just created a background and copied each nine block onto it. Conveniently, the GD objects each have their own coordinate scheme, colors, and contents. Once I have constructed the larger structures, the details take care of themselves. See the URL at the bottom of the article for the current code.

The next revision was to add color. I modified square() to use a random color for the corner, edge, and center:

my $black = $image->colorAllocate(
                           int rand 255,
                           int rand 255,
                           int rand 255);

Next, I set the color to fade from black to red along one axis and black to blue along the other, with random amounts of yellow. I printed off a large sheet of tiny blocks on photo paper, and made a Christmas present out of it.

The story could end here, with a pretty picture. However, in mid-December I mentioned the code to my local Perl Mongers group, and asked for a critique. It became obvious that there was much room for improvement. The astute reader may notice that I rebuild the primitives with every single square. That was easy to factor into an initialization routine which instead built an array of hashes for each primitive, along with a more expressive description of the primitives in a _DATA_ section.

sub square_init
{
   my @squares;
   LINE: while (<DATA>)
   {
      # allow for comments and whitespace
      next LINE if m/^\s*#/ || m/^\s+$/;
      # join continued lines
      if ( s/\\\s*$// ) { $_ .= <DATA>; }  
      
      my ($id, $points) =
         m/^(\d+): \s+(?: \(cent(?:re|er)\))
         ? \s+ (.*)$/ix;
      my %data;
      $data{'points'} = $points;
      $data{'center'} = 
         (m/\(cent(?:re|er)\)/ix )? 1 : 0;

      # create polygon object:
      my $poly = new GD::Polygon;
      
      for my $pair (split /\s*;\s*/, $points)
      {
         my ($x, $y) = split /\s*,\s*/, $pair;
         $poly->addPt($x*$sqSize, $y*$sqSize);
      }

      $data{'poly'} = $poly;
      push @squares, \%data;
   }
   
   # create center array from squares
   my @centers = grep {$_->{'center'}} @squares;

   return \@squares, \@centers;
} 

__DATA__

# id: center  points (relative to 1x1 unit sq.)
#     center  indicates squares that are 
#             rotationally symmetrical
# ---------------------------------------------
1:  (center) 0,0; 1,0; 1,1; 0,1
2:           0,1; 1,1; 1,0
3:           0,0; 0.5,1; 1,0
4:  (center) 0,0.5; 0.5,1; 1,0.5; 0.5,0
5:           0.5,0; 0.5,1; 1,1; 1,0
6:           0,0; 0,0.5; 1,1; 0.5,0
7:           0.25,0.5; 0.5,0; 0,0; 0.5,0.99;  \
             1,0; 0.5,0; 0.75,0.5; 0.25,0.5
8:           0,0.5; 1,1; 0.5,0
9:  (centre) 0.25,0.25; 0.25,0.75; 0.75,0.75; \
             0.75,0.25
10:          0,1; 0.5,1; 0.5,0.5; 1,0.5; 1,0
11:          0.5,0.5; 0.5,1; 1,1; 1,0.5
12:          0,0.5; 1,0.5; 0.5,0
13:          0,0; 0.5,0.5; 1,0
14:          0.5,0.5; 0.5 ,1; 1,0.5
15:          0.5,1; 1,1; 1,0.5
16: (center)


The square objects can then be accessed like this:

my ($squares, $centers) = &square_init;
$squares->[ 0 ]->{'center'} # returns true
$squares->[ 0 ]->{'poly'}   # GD::Polygon object

Further Improvements

The script should also eliminate any duplicate blocks on a single printout. The first solution was a hash indexed with a text version of the nineblock() parameters. This was improved by disallowing rotations on the four rotationally symmetric shapes. While there are 16384 choices of edge, edge rotation, corner, corner rotation, and center, there are 10816 unique patterns. Another improvement is to generate all 52 possible rotated shapes as polygon objects, which will also make the code faster.

The random colors I used were nice, but there could be more options for interesting color combinations using HSV color gradation instead of RGB. The module Graphics::ColorObject can do this with its HSVtoRGB subroutine.

It is not clear whether this code should become a module within the GD namespace. Doing so with OO code would make it easier to write code for the more fun ideas we came up with, such as treating each block as a pixel whose colors and shapes are chosen to recreate a larger image. It would also be fun to find additional primitives which look good in these patterns; there is no reason to limit ourselves to the traditional 16 primitives used by quilters.

The latest version of the code is available at http://kw.pm.org/local/nineblocks/

--

Daniel Allen (da@kw.pm.org) works for the Computer Science Department at the University of Waterloo. He would like to thank kw.pm, especially Eric Maki for egging him on and writing all the good code, and also dan brown, his Addition Consultant.