CPSC 645/VIZA 675

Homework 2 due 3/12/09

This assignment has both a written portion and a programming portion.

Written portion:

1. Given the polynomial

a. [3 points] Blossom this polynomial in four variables.

b. [3 points] Use the blossom in part a to write down the control points for a quartic Bezier curve over the parameter interval [0,1] that represents this function.

c. [3 points] Blossom this polynomial in three variables.

d. [3 points] Use the blossom in part c to write down the control points of a cubic B-spline curve using the knots -1, 0, .1, .4, .6, 1, 2, 2.

2. Given a cubic B-spline curve with the knots -1, 0, .1, .5, .6, 1, 1.5, 2 and associated control points

(0,0)

(1,0)

(1,1)

(0,1)

(0,2)

(2,2)

a. [4 points] Use the deBoor (pyramid) algorithm to evaluate the curve at 0.6.

b. [4 points] Calculate the direction of the derivative at 0.6.

c. [4 points] Use Boehm’s algorithm to insert the knots 0.7, 0.7 and give the modified control points.

d. [4 points] With the original control points, use the Oslo algorithm to insert the knots 0.7, 0.8 and give the modified control points.

3. Assume you are observing a car driving over some course, and have observed its position at several points in time. For ease of description/computation, all the times are scaled to the [0,1] range. The times and positions you measure are:

t = 0 (0, 0)

t = 0.1 (1, 1)

t = 0.2 (3, 2)

t = 0.3 (5, 3)

t = 0.5 (8, 3)

t = 0.7 (8, 0)

t = 1.0 (4, -1)

a. [6 points] You want to fit a cubic Bezier curve to the data. Using a least-squares computation, find the best-fit cubic Bezier curve to the data.

b. [6 points] Assume you still want to fit a cubic Bezier curve to the data, but you know you want to make the first and last points match the measured data exactly. Again, using a least-squares computation with Lagrange multipliers, find the best-fit cubic Bezier curve to the data, assuming you are interpolating the first and last points. Be sure to show your work!

Programming portion:

Create a program that will allow users to read in, manipulate, and display a NURBS curve (note that this curve is rational). Skeleton code can be found here that allows you to draw points and lines, though you are encouraged to write your own display code if you feel comfortable doing so. Generally, little partial credit will be given – i.e. if the code doesn’t work, I won’t hunt through all your source code to try to determine whether the error is “large” or “small”. I may still give partial credit if it seems to work in “most but not all” cases, or has smaller visible errors and such.

You should submit a written set of instructions for how to use/control your program.

a. [25 points]. Read in a knot vector and a set of control points, and display the curve. You should display both the starting and ending point, along with a set of lines connecting several points that lie on the curve. Basically, you should just evaluate the curve at several parameter values and then connect those points together.

b. [5 points] Evaluate the points where the individual piecewise segments (i.e. the individual Bezier curves that make up the B-spline) meet. Draw these points in a separate color, to highlight the places where the piecewise curves meet with continuity.

c. [30 points] Draw the Frenet frame at several points along the curve. The Frenet frame will show the tangent, normal, and binormal to the curve. You should draw 3 different vectors (for the 3 axes) in different but consistent colors (i.e. one color for the tangents, one for the normals, one for the binormals). You should allow the option of either scaling these to a fixed length, or letting the length reflect the actual magnitude.

For partial credit, you can do this first ignoring the weight values (i.e. treat as a non-rational curve).

Sample input files can be found here and here. The file contains the degree of the curve on the first line, the number of knots "n" on the second line followed by a line containing the "n" knot values. The line of knot values is then followed by a number of control points "m" and then "m" lines containing the "m" control points. Each control point is of the form (x, y, z, w) and should be interpreted in homogeneous form as (wx, wy, wz, w). Therefore the point with xyz coordinates (1,2,3) with weight 2 should be interpreted as (2,4,6,2).