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

The Assignment:

Purposes:

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 www.cs.colorado.edu/~main/chapter9/fractal.cxx. 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 www.cs.colorado.edu/~main/ds/grading.html.

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:

• For the base case (when the width drops below epsilon) you should create a new Polygon object that has its coordinates at the points that are specified by the parameters. The code will look something like this: Polygon *p = new Polygon; ...followed by four calls to p->AddVertexXYZ(...); Once the Polygon is created, you don't need to worry about it any more.
• For the recursive case, you must make four recursive calls, which are somewhat illustrated by this drawing:

                            E
                   A-----------------B
                    |       |       |
                    |       |       |
                    |       |       |
                    |       |       |
                   H|-------+-------|F
                    |      I|       |
                    |       |       |
                    |       |       |
                    |       |       |
                   D-----------------C
                            G
  

  In this drawing, the original four points given as parameters to the random_fractal function are A, B, C and D. You will have to calculate the coordinates of the five other points (E, F, G, H and I). Use a straight-line interpolation to calculate these points. For example, the z-coordinate of point E should be calculated as halfway between the z-coordinate of A and the z-coordinate of B. Once you have calculated the coordinates of the five extra points, you should then move point I up or down a random amount before making any recursive calls.

  Notice that there will be four recursive calls in all. For example, one of the four recursive calls will deal with the upper-left sub-square A-E-I-H.

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

• Include "threed.h"
• Ask the user for an integer x to seed the random number generator. Then call srand(x).
• Call PutIntoGraphicsMode( );
• Call your random_fractal function, using an initial big flat square with all corners at z=0. Try having the square go from -5 to +5 on both the x and y axes, and use 1 for the epsilon (so that when the length of an edge in the square drops below 1, there is no further recursion). If my calculations are right, this should give four levels of recursion, resulting in 256 total squares in your final picture. (Note: The threed.h class is currently limited to no more than 1000 polygons.)
• Call RefreshScreen( ). This will display all the polygons that you created.
• Have a loop that then reads a character from the keyboard and changes the viewpoint based on that key. You should have keys to allow the user to quit (call ShutDownGraphics and then leave the loop), to zoom in or out (use the ZoomView function from threed.h, and to rotate the view around the origin using SpinView, RollView or TiltView from threed.h. Each time that you change the screen, call RefreshScreen to redraw everything.

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 http://csel.cs.colorado.edu/udp/machines.html. 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:

• fractal3.o
• Xturbo.o
• threed.o
• useful.o