COS 126: Spring 1997
Recursive Graphics
Due: Wed. 3/26/97, 11:59pm

In this assignment, you'll use recursion to write a program that generates a program as output. Specifically, you'll write, in htree.c, a program that emits Postscript code to draw an "H-tree" pattern.

The H-tree is an example of a self-similar, or fractal, pattern that is defined using recursion. An H-tree with parameter r is defined by drawing an "H", and then recursively drawing four more H-trees with parameter r/2 at each of the four corners of the first H. The parameter r defines the thickness of the lines in the H. H-trees are of practical interest in designing microprocessor chips, because they're a good pattern to use for running the wires that connect circuit components when a tree of interconnections is needed.

htree.c should use a recursive function to draw an H-tree of size w with parameter r at (x,y), where w is the length of each of the three lines in an H and r is the thickness of each line. Here's pseudocode for the recursive algorithm:

if r > 0 then
put an H-tree with w = w/2 and r = r/2 at the upper left corner
put an H-tree with w = w/2 and r = r/2 at the upper right corner
put an H-tree with w = w/2 and r = r/2 at the left left corner
put an H-tree with w = w/2 and r = r/2 at the lower right corner
draw an H of size w at (x,y)

The basis case occurs when r = 0, at which point the recursive function does nothing. Although the H-tree pattern looks complex, the H-tree algorithm is very similar to the fractal star algorithm described on pp. 59 in Algorithms in C. Another, simpler, example is the recursive function for drawing a ruler described on pp. 54-57; code for this example is available in /u/cs126/examples/ruler.c.

You should write three functions:

htree implements the algorithm described above;
draw draws an H of size w with thickness r at (x,y); and
main prints the header, calls htree, and prints the trailer

Your program will draw a pattern by emitting code in the Postscript page-description language. Writing programs that emit programs is a very powerful technique that has many applications. Most programs that produce graphical output emit Postscript, because Postcript is the language used to drive virtually all laser printers. It is a powerful, high-level, stack-based language designed specifically for rendering two-dimensional graphics and text. See the COS 111 Postscript "cheatsheet" for a quick introduction to Postscript. For more details than you'll probably ever need, see A First Guide to PostScript; this guide includes a concise summary of the Postscript operators. (Graphics freaks will want to buy a copy of the Postscript Language Reference Manual.)

Postscript coordinates are in units of "points" and the origin, (0,0), is at the bottom left of the page. There are 72 points per inch. For htree.c, we'll translate the origin to (50,50) and draw all output in a 512×512 integer coordinate system. To start, generate Postscript for drawing an H-tree centered at (256,256) with w = 256 and r = 2; your program should print the following Postscript.

%!
50 50 translate 0.30 setgray
1 setlinewidth
  64 384 moveto 128   0 rlineto stroke
  64 320 moveto   0 128 rlineto stroke
 192 320 moveto   0 128 rlineto stroke
1 setlinewidth
 320 384 moveto 128   0 rlineto stroke
 320 320 moveto   0 128 rlineto stroke
 448 320 moveto   0 128 rlineto stroke
1 setlinewidth
  64 128 moveto 128   0 rlineto stroke
  64  64 moveto   0 128 rlineto stroke
 192  64 moveto   0 128 rlineto stroke
1 setlinewidth
 320 128 moveto 128   0 rlineto stroke
 320  64 moveto   0 128 rlineto stroke
 448  64 moveto   0 128 rlineto stroke
2 setlinewidth
 128 256 moveto 256   0 rlineto stroke
 128 128 moveto   0 256 rlineto stroke
 384 128 moveto   0 256 rlineto stroke
showpage

The first two lines are the header, and the last line is the trailer; use printf in your main function to emit these lines exactly as shown.

Each of the 4-line chunks that start with setlinewidth draw one H. The first four chunks draw 128-unit Hs with r = 1 at (128,384), (384,384), (128,128) and (384,128), and the fifth chunk draws a 256-unit H with r = 2 at (256,256). Use setlinewidth to set the thickness of the lines to r.

You can display the image specified in a Postscript file by sending it to a printer with the lpr command:

% lcc htree.c
% a.out | lpr

Make sure your output starts with the header shown above; if the first line of the output is not "%!", you'll get just the Postscript code instead of the image. And if you forget the "showpage" trailer, you'll get a blank page.You can also use gs, the Ghostscript previewer, to view Postscript. Redirect your Postscript output to a file, then run gs on the file:

% a.out >foo.ps
% gs foo.ps

Once you can draw the r = 2 pattern, revise your program to draw the r = 32 pattern shown here, and turn in this version of htree.c. (It's easyand convenientto have your program accept an optional argument that specifies r, so that, for example, the command "a.out 2" draws the r = 2 pattern. This feature is not required, however.)

Turn in your code and your documentation with the command

/u/cs126/bin/submit 6 readme htree.c

Extra Credit

Postscript is a complete programming language with variables, procedures, control structures, and so on. Write the H-tree program completely in Postscript and submit it as H-tree.ps. Use this file name to avoid confusing your Postscript program with the output from htree.c.

More Extra Credit!

Do another, different, recursive design. Experiment with implementing a different draw function or a different htree function. For example, on page 59 of Algorithms in C, star calls box, which uses fill to fill the boxes with white. Calling draw or box at different points with respect to the recursive calls will produce different and interesting effects. Try Xs or Ss instead of Hs, or use recursive triangles, or whatever. You might try introducing some randomness. For example, change the pattern between recursive calls. If there's sufficient interest, we'll hold a class vote for the best design from 5 "finalists" and plaster it on the back of the COS 126 T-shirts.

If you do the extra credit, submit your design as graphic.c.

References
R. Sedgewick, Algorithms in C, 2nd ed., Addison-Wesley, 1990, pp. 51-59.
Adobe Systems, Postscript Language Reference Manual, 2nd ed., Addison-Welsey, 1990.


Copyright © 1996 David R. Hanson / drh@cs.princeton.edu
$Revision: 1.3 $ $Date: 1997/3/11 14:42:26 $