# Exercise 2

 Number of Points 100 Due Date Friday, October 7, 2005

Do the following problems:

• (20 points)
List the numbers of vertices, edges, faces, loops, shells and holes of the following polyhedron and verify the Euler-Poincaré formula. In your README file, state clearly the way you used to obtain these numbers. You will receive no credit if you only provide a set of values.

• (40 points)
Use Boolean operators (i.e., union, intersection and difference) to modify a cube (or an object you wish to use) so that its shadows on three perpendicular walls are the letters M, T and U. Note that the orientation of the shadows is important. Look at the orientation of S (in DES), E (in CSE), A (in USA) and U (in MTU).

If the shadow of U in MTU is not vertical in your image, you risk lower grade.

You do not have to start from scratch. Check here to get more information and an initial copy of a POV-Ray file.

A more elegant design (i.e., color, texture, simplicity, good-looking objects and so on) will receive a higher grade. Up to 10 bonus points will be given to a creative design. Also make sure that your modified object is clearly shown in the ray-traced image.

• (40 points)
Design a program that reads in an input file that describes a polyhedra with the winged-edge data structure and displays it on screen.

You do not have to write all functions. In fact, I have provided you with all necessary tools except for reading and displaying. Click here to download this package (Exer-2.tar.gz). After unzip and untar (see below), you can make it with one of the four makefiles. The executable will be named as render. Run it and you will see the following on screen:

It displays a wireframed torus, a cube and two triangles. You can drag using the left-mouse button to change the orientation of these objects. Click the Exit button to quit this program.

### System Notes

To unzip and untar, move Exer-2.tar.gz to your working directory and issue the following commands:
```               gzip -d Exer-2.tar.gz
tar xvf Exer-2.tar
```
You will see four makefiles, each of which is designed to generate an executable under a particular platform.

Makefile.SunMesa compiles the program without using OpenGL hardware. Makefile.SunOpenGL compiles the system using Sun's OpenGL library. The generated executable runs much faster. Makefile.Linux is for you to compile your program under Linux with Mesa. Finally, Makefile.SGI is for me to grade your program.

To make this system, say using Makefile.SunMesa, issue the following command:

```               make -f Makefile.SunMesa
```

You only need to modify two functions of this package. Both of them are in file draw.c. The first function is cs390_init(), which is called only once when this program is executed and takes two arguments: argc and argv. See the template below:

```void cs390_init(int argc, char **argv)
{
}
```
In this function, you should read in the input data file whose name is passed to this function via argv. For example, if this program is started with the following line:
```     render  tetrahedron.dat
```
then it should read in the winged-edge data structure from file tetrahedron.dat.

The second function is cs390_draw(). In this function, you should draw the polyhedron read in by function cs390_init(). Obviously, the winged-edge data structure must be global in some way for both functions to have access to it.

While cs390_draw() uses several OpenGL function calls, you only need to know the following:

1. glColor4f():
It takes four arguments that specify the color to be used. The fourth argument is always 1.0. The first three arguments are floating numbers in the range of 0.0 and 1.0, giving the intensity of a RGB color. In function cs390_draw(), the first call to glColor4f() uses a red color to draw two triangles; the second uses a yellow color (R+G) to draw the wireframed torus; and the third uses a green color to draw the cube.
2. glVertex3dv():
This function sends an array of three double values to OpenGL for further processing. For example, suppose we want to send a point (10.0, 5.0, 20.0) to OpenGL for further processing, you should do the following:
```     GLdouble  point[3] = { 10.0, 5.0, 20.0 };
.........
glVertex3dv(point);
```
Note that glVertex3dv() requires its only argument to be a pointer to a array of type GLdouble.
3. glBegin() and glEnd():
Since your program will display the input polyhedron face by face, you need the following structure in cs390_draw():
```     for (i = 0; i < No_of_Faces; i++) {
glBegin(GL_POLYGON);
for (each vertex of this face) {
}
glEnd();
}
```
For each face in the winged-edge data structure, your program should locate all of its vertices in some (i.e., clockwise or counterclockwise) order. Then, for each vertex, use glVertex3dv() to send this vertex to OpenGL for further processing.

glBegin(GL_POLYGON) tells OpenGL that a polygon is about to be constructed and glEnd() tells OpenGL that the polygon construction is completed. Between glBegin() and glEnd(), you should supply the vertices in order. Note that these vertices should form a simple (i.e., no self-intersection), planar and convex polygon. Otherwise, the result is unpredictable.

Function glPolygonMode() can be used to draw the edges. For example, the above code can be modified to draw all edges of a face:

```     for (i = 0; i < No_of_Faces; i++) {
glBegin(GL_POLYGON);
for (each vertex of this face) {
}
glEnd();
}
```
The added line instructs OpenGL to draw an outlined polygon. More precisely, only the edges are drawn. You have two more choices: GL_POINT only draws the vertices of a polygon, and GL_FILL draws the polygon filled with a previous specified color.

In cs390_draw(), you should specify a color for your drawing, followed by a loop for displaying the vertices of each face. You should also display all edges of the given polyhedron in a color different from that of the polygons.

### Important Notes

• When listing the vertices of a face, you should use an efficient algorithm as we discussed in class. A brute-force or naive algorithm risks very low grade.
• You should present your algorithm clearly with a detailed elaboration in your README file. I do not accept a copy of your statements as an elaboration.
• Feel free to modify the colors of the objects. However, keep in mind that the color selections must be able to distinguish vertices (if any), edges, faces, and the background. Do not use similar colors for the edges and faces.
Here are some further important notes.
• For all problems, you should show the details of your reasoning and computations in a README file.
• Submit a single file ups.pov for your scene and a 640×480 image in JPEG format (i.e., file name extension .jpg). You should annotate this image with your name and e-mail address. Name this image ups.jpg. I don't accept any other image format.
• Since I will use my SGI machine for testing and grading your OpenGL programs. You should do the following:
1. Only modify file draw.c and do not add any other files so that all makefiles do not have to be changed. However, if you want to change the program structure, you should change all make files. I do not modify any makefile to make your program work. As a result, if I cannot make your program with Makefile.SGI, I will consider your program incorrect.
2. When you submit your program for Problem 3, use tar followed by gzip, and submit your version of Exer-2.tar.gz rather than individual program files. To tar and gzip, goto your working directory and issue the following commands:
```tar cvf Exer-2.tar file-1 file-2 file-3 ......
gzip Exer-2.tar
```
The result is a file with name Exer-2.tar.gz. Only tar the files. Moreover, remove all .o files and render. If you tar a directory and/or include the .o and render files, you risk lower grade.
• The input data for Problem 3 will be in the following format:
```#V      <-------------- number of vertices
x  y  z <-------------- coordinates of the first vertex
x  y  z <-------------- coordinates of the second vertex
.......
x  y  z <-------------- coordinates of the last vertex
e       <-------------- vertex table: 1st vertex on edge e
f       <--------------               2nd vertex on edge f
.......
k       <--------------               last vertex on edge k
#F      <-------------- number of faces
e       <-------------- face table  : first face has edge e
f       <--------------               second face has edge f
.......
t       <--------------               last face has edge t
#E      <-------------- number of edges
X  Y  Fl  Fr  Left-Pred Left-Succ Right-Pred Right-Succ
.......
```
It starts with the number of vertices followed by that number of lines, each of which contains the coordinates of a vertex. The next section is a vertex table. Each entry of a vertex table contains an incident edge. A vertex table is followed by a face table. Each entry of a face table contains an incident edge. Finally, it is an edge table. Each entry contains a start and end vertices, left and right faces, the predecessor and successor in a left traverse and the predecessor and successor in a right traverse. The coordinate values of vertices are all in the range of -50 and 50.

The following is an example which is a translation of the tetrahedron discussed in the winged-edge data structure:

```4                      // four vertices
50.0    0.0   5.0     // vertex 1 = A
-50.0   50.0  -50.0    // vertex 2 = B
-50.0  -50.0  -50.0    // vertex 3 = C
0.0    0.0   50.0    // vertex 4 = D
1                      // vertex 1 has edge 1
2                      // vertex 2 has edge 2
4                      // vertex 3 has edge 4
5                      // vertex 4 has edge 5
4                      // number of faces
1                      // face 1 has edge 1
3                      // face 2 has edge 3
1                      // face 3 has edge 1
2                      // face 4 has edge 2
6                      // number of edges
1  4  3  1  5  6  2  3 // edge 1 starts @ v1 & ends @ v4 ...
1  2  1  4  3  1  6  4 // edge 2
2  4  1  2  1  2  4  5 // edge 3
2  3  2  4  5  3  2  6 // edge 4
3  4  2  3  3  4  6  1 // edge 5
1  3  4  3  4  2  1  5 // edge 6
```
This file is available in Exer-2.tar.gz with name test-0.dat.

• The following must be found in your submission:
2. ups.pov and ups.jpg
3. Exer-2.tar.gz
4. At least three test files with name test-0 (i.e., the above test file), test-1.dat (e.g., a cube), test-2.dat (e.g., any other polyhedron) and so on. You will receive a bonus up to 5 points for designing a complex and interesting test polyhedron in test-2.dat .
```NAME:      your name