Exercise 4

Number of Points	100
Due Date	Tuesday, November 8, 2005, before class (Problems 1, 2 and 3) Tuesday, November 8, 2005, 11pm

Please note the change of due date/time

Please do the following problems:

(10 points)
Suppose the knot vector is U = { 0.0, 0.2, 0.5, 0.5, 0.8, 1 }. Compute the basis function N_2,2(u) and sketch its graph. Please also indicate the non-zero domain of this basis function.
(10 points)
Suppose a clamped B-spline curve of degree 3 is defined by control points (-2,0), (-2,2), (-1,2), (-1,1), (0,0), (1,1), (1,2), (2,2) and (2,0) and knots 0 (multiplicity 4), 1/6, 1/3, 1/2, 2/3, 5/6 and 1 (multiplicity 4). Insert a new knot at 0.4 twice. You should show all detailed computation of both insertions, including all computations, diagrams, all existing and new control points, and the way that corners are cut.
(10 points)
Suppose a clamped B-spline curve of degree 3 is defined by (-2,0), (-2,2), (2,2) and (2,0) and knots 0 (multiplicity 4) and 1 (multiplicity 4). Provide the computation, in triangular form, with all the detailed steps using de Boor's algorithm and show that the result is exactly the same as that of de Casteljau's algorithm. You will receive no credit if you do not show the details.

(30 points)
There are five non-degenerate quadric surfaces as follows:

*Surface Name*	*Surface Equation*
Ellipsoid	ax² + by² + cz² = 1
Hyperboloid of one sheet	ax² + by² - cz² = 1
Hyperboloid of two sheets	ax² - by² - cz² = 1
Elliptic paraboloid	ax² + by² = 2cz
Hyperbolic paraboloid	ax² - by² = 2cz

where a, b and c are all positive numbers. These surfaces were discussed in a previous page. To specify an algebraic surface such as a quadric surface, see Algebraic Surfaces. Design a scene that contains all five surface types. Name this scene file quadrics.pov and its JPEG image quadrics.jpg annotated with your name and e-mail address. This scene will be graded based on your creativity and technical skill.

Note that clipping may be required to trim a quadric surface. See Clipping for the details.

(40 points)
Design and implement a program that can show all intermediate polylines of de Boor's algorithm with knot insertion as shown in the curve 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 curve of degree 3 defined by seven control points shown as orange squares and 11 knots (not shown). As in Exercise 3, a yellow disk is provided for you to trace the B-spline curve. This yellow disk does not move and is used as an example. You can click on Exit to close this window and use the left arrow and right arrow keys to change the value of u shown on the bottom part of this window. The range of u is 0 and 1. Press the left-arrow (resp., right-arrow) key to decrease (resp., increase) the value of u.

System Notes

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

               gzip -d Exer-4.tar.gz
               tar xvf Exer-4.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  p     <----- # of knots and degree
x0 y0 z0 <----- 0-th control point
x1 y1 z1 <----- 1st control point
x2 y2 z2 <----- 2nd control point
 ......
xn yn zn <----- n-th control point
u0 u1 u2 u3 ..... um <--- knot vector

Note that n, the highest index of control points, can be computed as m - p - 1. Note also that the knot vector may contain multiple knots which should be used with care when determining the knot span that contains u. The coordinate values should be in the range of -50 and 50. When preparing your input control points, do not use small values as the control points may be jammed together.

Extremely Important
In OpenGL, the values of m and n are the number of knots and the number of control points. In our course notes and software manuals, these values are the highest indices of the knots and control points.

To draw a B-spline curve, we need to know more about OpenGL. In draw_bspline_curve(), the first for loop puts the control points on screen:

glColor3f(CS390_POINTS_COLOR);     /* select a color             */
glPointSize(8);                    /* select the size of a point */
glBegin(GL_POINTS);                /* ask OpenGL to show 3d Pts  */
    for(i = 0; i < n; i++) {       /* for each point ....        */
        glVertex3fv(&points_v[i][0]);   /* display it            */
    }
glEnd();                           /* end of point display       */

Note that the control points are of type GLfloat and the vertex drawing function is changed to glVertex3fv() rather than glVertex3dv() which was used in Exercise 3 where type GLdouble was used.

Next we draw a B-spline curve with a single OpenGL function call: gluNurbsCurve(). Note that the prefix of this function is glu rather than gl, which means OpenGL Utility library. This is a small library of a few drawing functions. NURBS curves and surfaces drawing is one of its major features.

As in the Bézier curve case, we first select a shading model, followed by enabling evaluator mapping. The next function is gluBeginCurve() with an argument theNurbs, which is a NURBS drawing object defined in header file externs.h. The actual drawing is carried out by gluNurbsCurve() that takes the following arguments:

theNurbs is the NURBS drawing object.
m is the number of knots.
A pointer to the knot vector.
The next one is u_stride, which specifies the offset (i.e., number of single-precision floating-point values) between successive curve control points. You can just use 3 as the sample program does, because each control point has three floating values, one for each of its coordinates.
The next argument is the array of control points.
The next is an integer, the order of the curve. The order of a curve is defined to be the degree of the curve plus 1.
Finally, the last argument is GL_MAP1_VERTEX_3.

After drawing a B-spline curve, one should call gluEndCurve() to close this drawing. The only parameter must be the one used in the opening call gluBeginCurve().

The following is what is used in the sample program:

glColor3f(CS390_CURVE_COLOR);      /* select a drawing color     */
glLineWidth(2);                    /* select a line width        */
if(n >= 2) {                       /* draw curve only if n >= 2  */
    glShadeModel(GL_FLAT);         /* select a shading model     */
    glEnable(GL_MAP1_VERTEX_3);    /* activate mapping and do it */
    gluBeginCurve(theNurbs);       /* start NURBS curve drawing  */
    gluNurbsCurve(theNurbs,        /* draw a NURBS curve         */
                  m,               /* # of knots                 */
                  &knot_v[0],      /* knot vector                */
                  3,               /* u stride                   */
                  &points_v[0][0], /* control points array       */
                  p + 1,           /* order = degree + 1         */
                  GL_MAP1_VERTEX_3);    /* do it as here         */
    gluEndCurve(theNurbs);         /* end of NURBS curve drawing */
}

You need to do two things. First, you need to read all control points into the point array point_v[][] and the knot vector into knot_v[].

If you look at draw.c carefully, you will see a global double variable u. Each time cs390_draw() is called, a value of u is passed to you with this global variable. The value of u comes from pressing the left- and right-arrow keys.

Here comes your job:

Modify draw.c so that it can display the following:

Draw a disk at the point on curve that corresponds to the current value of u. Function draw_disk() takes the coordinates of a point and the size of a disk, and puts a disk at the desired point. Please do not modify this function if it is possible.
Draw the control polygon of the input control points.
Given the value of u, draw all intermediate polylines obtained by applying de Boor's algorithm at u.

To draw a polyline, use the above GL_LINE_STRIP feature:

glBegin(GL_LINE_STRIP);
    /* generate a vertex on the polyline */
    glVertex3fv(address of this vertex);
    /* some other activities */
glEnd();

For a discussion of glVertex3dv(), please see Exercise 2.

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

An Important Note

Feel free to modify the colors of the objects. However, keep in mind that the color selections must be able to distinguish different objects. Do not use similar colors for near-by objects. You can also use different colors for different polylines of the computed de Boor net.

Here are important notes for this exercise.

Submit the first three problems on paper. This part is due on November 12 in class. Please 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 3) and your program should be presented in detail. Make sure your name and e-mail address appear in the very beginning of this file as shown below:
```
NAME:      your name
E-MAIL:    your e-mail address
EXERCISE:  3
FILES:     README, and other files submitted along with README
```
  SSN is not required. No README or a poor README will cost you 10 to 20 points.
2. File Exer-4.tar.gz. Do not change the structure of the files. Just modifying draw.c would suffice. Do not change the makefiles as I will use my SGI machine for grading. Some of you tar a directory in the previous exercise. Please don't do that. Please 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 will generate a B-spline curve of degree 4. Click here to download a copy of this file input-0.dat. Note that this file is also part of the Exer-4.tar.gz distribution.
```
13 4
-40  -40  -40
-40   40  -40
-40   40   40
-40  -40   40
 40  -40   40
 40   40   40
 40   40  -40
 40  -40  -40
0. 0. 0. 0. 0.  .2  .4  .8   1.  1.  1.  1.  1.
```
  In your version Exer-4.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 files should contain at least ten control points. Interesting curve design will receive up to 5 bonus points. I will also use my own files for testing with the following command:
```
render  input-file-name
```
  Refer to Sample Solution to Exercise 3 for some interesting Bézer curves. 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 questions, please stop by or e-mail me.