Data Structures - Chapter 9 - Programming Assignment
Generate and Display a 3-D Fractal Surface

The Assignment:
Give you some exposure to graphics programming and strengthen your understanding of recursion.
Before Starting:
Read all of Chapter 9, especially Section 9.2.
Due Date:
Tuesday, Nov 7. If you run into hardware or software problems, you may submit on Wednesday with no penalty. You may submit on Thursday or Friday with a small penalty. No submissions will be accepted after Friday.
How to Submit Your Work:
Make sure that your program is working in the ugrad lab. Then submit your work to Dora. Also, to receive full credit you must demonstrate your work to the TA during your recitation of Nov 13/14.
File that you must write:
  1. fractal3.cxx: This should be a modified version of the fractal.cxx program which you can download from The original file displays a 2d fractal surface. Your modified version will display a 3d fractal surface as described below. The main program must display this surface and then allow the user to move the viewpoint around the surface.
Other files that you will need: (Available in ~cs2270/programs or online here.)
  1. priority.h: A priority queue class that you'll need for the three-d graphics file in this assignment.
  2. useful.cxx: and useful.h: A small collection of useful functions such as a function to generate a random real number in a specified range.
  3. threed.h and threed.c:
    Xturbo.h and Xturbo.c: These files provide the Polygon data type that you can use to display a collection of polygons in 3-d space.
  4. test3d.cxx: A small demonstration program for the stuff in threed.h. Make sure you know how to compile and run this before you do anything else.
Independent Work:
Keep in mind that you will not learn unless you do your own homework. Course guidelines are available at

Discussion of the Assignment

Start by grabbing fractal.cxx, renaming it to fractal3.cxx, and changing the include files at the top to be the old include files (assert.h, stdlib.h, and iostream.h). Delete the using namespace directive too because we're going to have to use a slightly older compiler.

Then write a new prototype for the random_fractal function that would be approprite for a three-dimensional surface rather than a simple line. The information that you pass to the new random_fractal function must include the x and y coordinates of the four points of a square on the x-y plane along with four heights (one for each of the four corners of the square). You should think a bit about how to pass all that information to the random_fractal function. For example: Do you need to pass four separate x-coordinates for the four corners of the square, or can you get by with less?

As with the original 2-D version, you will also have an epsilon parameter to indicate when the recursion stops. (My implementation stops when the width of my square drops below epsilon. I calculate the width by subtracting one x-coordinate from another rather than passing an explicit width parameter. But you could also pass it as a parameter if you prefer.)

After you have written your new prototype, add that to your fractal3.cxx file along with a comment that indicates what the new function will do.

Then, of course, you need to implement the function:

Once you have the random_fractal function in place, you should modify the main program so that it does these things:

Compiling, Linking, Running

Do all your compilation and running on one of the bird machines (just like the polycgi assignment). A list of these machines is given at the bottom of The compilation can be done from any kind of login on one of these machines. But for the actual running, you must establish an X connection. An X-connection can be established from any machine in the undergrad lab with the slogin command. For example, to connect to swallow:

    slogin swallow

When you compile, you must make and link together these files:

Also, you must use an old version of the compiler (the new version doesn't seem to find the right graphics include files), and you must also link to certain graphics libraries. It's probably easiest if you just grab a copy of my makefile from Remember to rename the file makefile and make sure that each command line begins with a tab (not with eight spaces).

Michael Main (