Exercise 5

Number of Points	100
Due Date	Tuesday, November 29, 2005, before class (Problem 1) Tuesday, November 29, 2005

Please do the following problems:

(20 points)
Given the following four rows and four columns control points:
```
Row 0:    (-2,0,-4), (-2,2,-4), (2,2,-4), (2,0,-4)     on plane z = -4
Row 1:    (-4,0,-2), (-4,3,-2), (4,3,-2), (4,0,-2)     on plane z = -2
Row 2:    (-4,0, 1), (-4,3, 1), (4,3, 1), (4,0, 1)     on plane z =  1
Row 3:    (-2,0, 2), (-2,2, 2), (2,2, 2), (2,0, 2)     on plane z =  2
```
Compute the corresponding point of (0.2, 0.5) on the Bézier surface defined by the above 4×4 control points using de Casteljau's algorithm. To receive full credits, show all detailed calculations. Only providing an answer receives no credit.
(30 points)
The following is the parametric equation of Bour's minimal surface:

where the range of r and the range of t are defined as follows:

Choose a value of r and the number of subdivisions so that you will obtain a good looking surface. Use n = 4 for this exercise.
Write a program to subdivide the domain into triangles and generate a POV-Ray smooth triangle file. Then, use this smooth triangle file to raytrace this surface. Note that to render smooth triangles, you need to compute normal vectors at the vertices of each triangle. Click here for a discussion of the use of smooth triangles under POV-Ray. Put this file in Bour.inc and include it into your POV-Ray file. Turn in a scene file Bour.pov and its traced JPEG image Bour.jpg annotated with your name and e-mail address. What does it look like?
In doing triangulation of the domain, keep in mind that too many triangles will slow down the tracing speed drastically; however, the result looks great. On the other hand, if too few smooth triangles are used, the surface would look like a polyhedron which is not very convincing. So, start your work with a coarse tessellation. Then, make it finer when you are comfortable with its shape. You should start with just a few subdivisions to make sure the camera position and orientation are the good, and move to a finer subdivision. Also, clipping might be necessary.
Grading Policy: You will receive max. 30 points if the displayed surface is correct. An max. extra 10 bonus points will be given to those creative designs using this interesting surface.

(50 points)
Design and implement a program that can show all intermediate polylines of de Boor's algorithm for B-spline surfaces using knot insertion as shown in the surface program.

You do not have to write all functions. As in the previous exercise, you only need to modify two functions for reading in data and displaying the curve. Click here to download a package for this problem. 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 B-spline surface of degree (5,3) with 8 rows each of which has 9 control points (i.e., 8 rows and 9 columns). The control net is also shown. Instead of a disk, a small sphere (in red) is shown to indicate a point on the surface. This sphere does not move in this sample program. You can click on Exit to close this window, use the left and right arrow keys to decrease and increase the value of u, and use the up and down arrow keys to decrease and increase the value of v. The current values of u and v are shown on the bottom of this window.

System Notes

To unzip and untar, move Exer-5.tar.gz to your working directory and issue the following commands:

               gzip -d Exer-5.tar.gz
               tar xvf Exer-5.tar

You will see four makefiles, each of which is designed to generate an executable under a particular system.

Makefile.SunMesa compiles the system without using OpenGL hardware. Makefile.SunOpenGL compiles the system using Sun's OpenGL library. The generated executable runs much faster on any machine in the Language Lab. 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

As in the previous exercise, you need to modify cs390_init() to read in a data file whose name is supplied to you with **argv. The file has the following format:

m  n  p  q      <--- max row index, max column index, u degree and v degree
x00 y00 z00     <--- first control point on row 0
x01 y01 z01
...........
x0n y0n z0n     <--- last control point on row 0
x10 y10 z10     <--- first control point on row 1
x11 y11 z11
...........
x1n y1n z1n     <--- last control point on row 1
...........
xm0 ym0 zm0     <--- first control point on row m
xm1 ym1 zm1
...........
xmn ymn zmn     <--- last control point on row m
u0 u1 u2 u3 ....  <-- knots in U direction
v0 v1 v2 v3 ....  <-- knots in V direction

The first line gives the max row index, the max column index, the degree in the u (i.e., column) direction and the degree in the v (i.e., row) direction. These four values are integers. All subsequent values are real numbers.

The next (m+1)×(n+1) lines contain the coordinate values of each control point in row order. That is, the control points are organized row by row. The last two lines contain the knot vectors in the u- and v- directions.

If you have followed the previous exercises closely, you will find that the most important part is in draw_bspline_surface(). This function takes all input values, including control points and knot vectors, and displays a B-spline surface and its control net. The first for displays all control points as points on the screen. Notice the way of calculating the index of each point. The second and the third for use GL_LINE_STRIP to display all line segments between two adjacent control points. The next if checks to see if the B-spline surface specification is a correct one by verifying the two fundamental identities. Then, the heart of this function is the call to gluNurbsSurface().

This function requires 11 arguments as follows:

theNurbs:
This is a drawing object declared elsewhere. Just use it as is.
mU and knot_u:
The number of u knots, mU, and the knot vector in the u-direction, knot_u. Note that the u-direction actually generates curves in the column direction.
mV and knot_v:
The number of v knots, mV, and the knot vector in the v-direction, knot_v. Note that the v direction actually generates curves in the row direction.
Columns * 3:
Here Columns is the number of columns. This argument is called the u_stride, which means the number of floating numbers between two rows of control points. Since each row has Columns control points and each control point contains three floating numbers, the total number of floating numbers is Columns * 3.
3:
This is the v_stride. For B-spline surfaces, it is always 3 since between two adjacent control points there are three floating numbers, one for each coordinate.
points_v:
This is the two dimensional array of control points in row order.
p + 1:
p is the degree of the B-spline curve in the u-direction.
q + 1:
q is the degree of the B-spline curve in the v-direction.
GL_MAP2_VERTEX_3:
Always use this parameter here.

Here comes your job:

Modify draw.c so that it can display the computation and intermediate results of de Boor's algorithm. Since you have done the curve case, extending it to surfaces would not be a difficult job. Here are some more details:

Pick one direction, say the u-direction, and apply de Boor's algorithm to some columns at u whose value is provided to you from a global variable. For each column, display all intermediate polylines. This generates a set of new points.
Apply de Boor's algorithm to this set of points at v and display all intermediate polylines. This generates a single point, the point on the surface. The value of v is also available from a global variable. Refer to Tracing the Surface - de Casteljau's and de Boor's Algorithms of DesignMentor to see the actual effect of the de Boor's algorithm.
Display the point on the surface with a sphere.
Color the involved control points and the portion of control net with a different color. Without doing this part, you will lose 10 points.
Note that, in both directions, de Boor's algorithm does not use all control points as you have learned from the curve case. You will receive maximum 25 points if you use all control points in de Boor's algorithm.

With a correct implementation, you can drag to rotate the generated B-spline surface and use the left-, right-, up- and down-arrow keys to increase and decrease the value of u and v. Then, the computation of de Boor's algorithm will be shown vividly on screen.

Here are important notes for this exercise.

Submit the first problem on paper. This part is due on November 20 in class. Keep the following in mind; otherwise, you will risk lower grade.
1. Write clearly and to the point.
2. Present all computation details and intermediate steps. Writing down only the answers is not acceptable.
Submit the last two problems with the following materials:
1. A README file in which your effort and the logic of your scene design (Problem 2) and your program should be presented in detail. Make sure your name and e-mail address appear in the very beginning of this file. SSN is not required.
2. File Exer-5.tar.gz. Do not change the structure of the files. Just modify draw.c would suffice. Do not change the makefiles as I will use my SGI machine for grading. Do not tar a directory in previous exercises. Instead, cd to your working directory and only tar the files. Do not submit *.o files and file render.
3. The following is a sample input file. It defines a B-spline surface by 8 rows and 9 columns of control points. In the u- (i.e., row) direction, the degree is 5 and hence has 14 knots. In the v- (i.e., column) direction, the degree is 3 and has 13 knots. Click here to download a copy of this file input-0.dat. Note that this file is also part of the Exer-5.tar.gz distribution.
```
8  9  5  3
-48.0  -69.0  17.0
-32.0  -55.0  23.0
-19.0  -46.0  27.0
-8.0  -40.0  29.0
9.0  -34.0  29.0
28.0  -35.0  23.0
38.0  -37.0  18.0
51.0  -43.0  10.0
68.0  -52.0  0.0
-43.0  -48.0  18.0
-29.0  -36.0  22.0
-17.0  -29.0  25.0
-8.0  -24.0  26.0
6.0  -19.0  26.0
21.0  -19.0  21.0
30.0  -21.0  17.0
42.0  -26.0  11.0
58.0  -34.0  1.0
-41.0  -32.0  16.0
-27.0  -21.0  20.0
-17.0  -15.0  22.0
-9.0  -11.0  23.0
4.0  -7.0  22.0
17.0  -7.0  19.0
25.0  -9.0  15.0
36.0  -13.0  9.0
51.0  -20.0  0.0
-41.0  -19.0  12.0
-28.0  -10.0  16.0
-18.0  -5.0  19.0
-10.0  -2.0  19.0
2.0  1.0  18.0
14.0  1.0  15.0
21.0  0.0  12.0
31.0  -2.0  6.0
46.0  -8.0  -3.0
-45.0  -1.0  0.0
-31.0  4.0  6.0
-21.0  8.0  9.0
-13.0  10.0  10.0
0.0  12.0  10.0
10.0  13.0  7.0
18.0  13.0  3.0
27.0  12.0  -4.0
42.0  9.0  -16.0
-51.0  6.0  -10.0
-36.0  11.0  -3.0
-25.0  14.0  1.0
-16.0  16.0  3.0
-2.0  18.0  3.0
10.0  20.0  0.0
18.0  20.0  -5.0
28.0  20.0  -13.0
41.0  18.0  -27.0
-59.0  13.0  -26.0
-43.0  17.0  -15.0
-30.0  20.0  -9.0
-20.0  22.0  -6.0
-4.0  25.0  -5.0
11.0  27.0  -11.0
20.0  27.0  -17.0
30.0  28.0  -27.0
42.0  28.0  -43.0
-71.0  20.0  -46.0
-52.0  23.0  -32.0
-37.0  26.0  -24.0
-26.0  28.0  -19.0
-6.0  31.0  -17.0
14.0  33.0  -25.0
24.0  35.0  -33.0
35.0  36.0  -46.0
45.0  37.0  -64.0
0.0 0.0 0.0 0.0 0.0 0.0 0.5 0.5 1.0 1.0 1.0 1.0 1.0 1.0
0.0 0.0 0.0 0.0 0.2 0.4 0.5 0.6 0.8 1.0 1.0 1.0 1.0
```
  In your Exer-5.tar.gz, in addition to the above sample input, add two or more input files named input-1.dat, input-2.dat and so on for me to test your program. Each of your test file should contain more than 6×6 control points with degree in each direction at least 3. Your testing surfaces must be clamped. That is, if the u-direction has a degree p, then the first p+1 and the last p+1 knots should be identical. I will also use my own files for testing with the following command:
```
render  input-file-name
```
  If you need a working program and other files for your testing, click here to learn more. Note that these files are for your reference only, you should not submit them as your work. Otherwise, you will receive no credit for this problem. You can also use DesignMentor to verify your work.
If you have any question, please drop in or e-mail me.