Goals

Please take a minute to give us feedback on the first segment of the course.

  • Create graphics.

  • Learn about recursion.

  • Learn about the PostScript programming language (a stack-based language).

  • Part 1:   H-tree pattern   (6 points)

  • Your program should read in a single integer d from standard input.

  • Here are two good warmups programs which can be done independently:

  • Write a (nonrecursive) function void showH(void) that prints the moveto and rlineto (or lineto) commands needed to draw only one large H. Write your main function so that it prints out the PostScript header information, then calls showH, then prints out the final showpage command. This will give you confidence that your program is producing valid PostScript.

    As a second step, expand your showH function so that it now takes three arguments x, y, and size of type float. Write your function so that it draws an H, centered at PostScript coordinate (x,y), and with each of the 3 line segments having length size. You will probably want to use exactly this showH function in your final program.

  • Write a recursive function recurse that takes one input integer n, prints the value n, and then calls itself four times with the value n-1. The recursion should stop when n becomes negative. To test this function out, write your main function so that it reads one integer D from stdin and calls this recursive function with that value. You should get the following results. Make sure you understand how this function works, and why itp prints the numbers in the order it does.

    As second step, modify your recurse function so that instead of printing n, it prints the size of the H to be plotted. The first call to recurse (from main) will plot the big H; each line segment of the big H has length 256.0, so print 256.0. Each succesive level of recursion will halve the length. So, make your function produce the following results.

  • Once you feel a little confort with recursion and PostScript, try to figure out how to print the recursive H pattern. Start by drawing H's with pencil and paper. Do some calculations to figure out the geometry of where the smaller H's should go. Part of the challenge will be figuring out what information you need to pass to the recursive function. At the very least, it will need to know where to plot the H, and how big it should be.

  • Do not be alarmed if your PostScript output does not exactly match the PostScript output given in the course packet: it will depend on the order in which you make the recursive calls. However, you should get exactly the same picture. Also, feel free to use the lineto command instead of rlineto if you are more comfortable with a fixed coordinate system.

  • You may want to compute a^b for integers a and b. It is good practice to try to write your own power function using recursion. You can also use the math library function pow, but remember to #include<math.h>, and compile with the "-lm" flag.

  • After you compile your program, redirect the output to a file with the command:
    echo 3 | a.out > htree3.ps
    
    This is equivalent to running a.out, and then entering the value "3". You can then view the PostScript program with:
    gs htree3.ps
    
    If you get an error when trying to view, then your probably made a mistake with the PostScript syntax. Input a small value for D to help find the error.

  • Part 2:   your artistic creation   (3 points)

  • You should choose a self-referential pattern as a target output. Here are some possibilities: Sierpinski triange, Sierpinski curve, Hilbert curve, Koch snowflake, Dragon curve, Gosper island, Then try to figure out a recursive scheme that will generate it. Some pictures may be overly difficult to generate; consult a preceptor for advice if you're unsure. Remember, the goal here is not to simply randomly insert recursive calls until you get a cool picture.

    We'll deduct 1 point if you're picture is overly boring and too similar to htree.c. Most students have fun with this part, but if you have already spent too much of your time on this assignment, keep in mind that 1 point is only 1 point.

  • We will compile your program with "gcc -lm art.c". If you include an input file "input.txt", we'll run your program with "a.out < input.txt"; otherwise we'll run with "a.out". You may include whatever input parameters you like in input.txt; for example, you may wish to include the recursive depth parameter D.

    Feel free to use the color.map file from the Mandelbrot assignment for brilliant colors. In this case, your input.txt file will be (or contain) a copy of the color.map file.

  • Check out the the PostScript section of the COS 126 FAQ List for more information on PostScript.

  • Submission and readme   (1 point)
  • Use the following submit command:
    /u/cs126/bin/submit 4 readme htree.c art.c input.txt
    
    Do not use different file names or capitalization, even for your artistic creation. Note, that you will not submit any .ps files. We will generate these from your C programs. Be sure that your htree.c reads in the single integer D from stdin. Also, we will run your art.c program with the command "a.out" or "a.out < input.txt" if you submit the file input.txt.

  • Your PostScript output must:

  • view and print properly (with gs and lpr). If it doesn't, name your C programs htree-almost.c or art-almost.c so that we do not waste paper and time trying to print them.

  • stay within the 512 x 512 box.

  • be less than 3MB long.
  • Submissions deviating from these guidelines are subject to severe penalties.

  • The readme file should contain:

  • Name, precept number, high level description of code, any problems encountered, and whatever help (if any) your received.

  • Description of your artistic creation and how you went about creating it.

  • Do not include any PostScript in readme file.

  • Extra credit   (1 point)

    The extra credit is intended to challenge the more advanced students, and is strongly recommended for students aiming for an A+ in the course. If you are still struggling with the basics of recursion, you will probably benefit more by understanding the recursion examples in the lecture notes than by attempting the extra credit.

  • Combine the two main concepts you have been using and write a recursive PostScript program (not for the squeemish)! Name your PostScript program extra.ps.

  • Or "un-recursify" your program. Name your program extra.c.



  • Kevin Wayne