Recursive Graphics
| 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
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:
htreeimplements the algorithm described above; drawdraws an H of size w with thickness r at (x,y); and mainprints 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 easy
and
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
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.
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.