Homework 5: NURBS Editor

In this problem, you will create an interactive, two-dimensional B-Spline editor with OpenGL/glut. Your program should allow the user to insert and manipulate control points for a nonuniform B-Spline of order 4 (degree 3 or cubic). Read the handout on uniform and nonuniform B-splines (***See TA's helpful hints below if you're beating your head against the wall after reading the paper***). Also, this webpage on B-spline basis functions and this one on Nonuniform B-splines might be useful(and there's always wikipedia!). Both of them have little interactive spline applets. Also, Mark Meyers' lecture slides on higher order surfaces and splines are great for understanding splines mathematically and conceptually.

IT IS REQUIRED that you compute x-y values with your own implementation of the Cox de-Boor algorithm; you SHOULD NOT USE OPENGL or GLU functions to do the math or splining for you. Get the points yourself and then have OpenGL draw line segments for you.

(You can then add NURBS drawn using GLU for extra credit, of course.) Also, so you know, the next assignment uses GLU to do 3D NURBS.

TA's Helpful Hints:

u is the parameterization value over the ENTIRE curve. For example, if you have a curve with 10,000 control points and you want to calculate the point in the middle of the curve, u = 0.5.
There are two spaces you're working this. Normal 2D space with x and y, and 1D parameterization space where values range from 0 to 1. u and the knots live in parameterization space. p (referring to control points in the paper) is a vector that lives in 2D space. Don't get the two confused.
The point is to calculate a (x,y) value for a certain u value on the curve. This (x,y) value is a linear combination of control points. The term N_i,k (u) on page 3 of the paper will give you the coefficients in that linear combination. Knots are important because you need them to calculate the coefficients. (Knots are kind of like control points for the curve in parameterization space)

Homework 5 is due on Tuesday Nov. 9 at 11:59 pm

Display Spline and Control Polyline

The editor should show both the spline curve and the control poly-line. The editor should start out with a predefined spline of 4 points in a U shape and a knot vector of < 0, 0, 0, 0, 1, 1, 1, 1 > :

A NURBS curve with 4 control points, U shapes

The repeat knots ensure that the curve goes from the first control point to the last one (and touches both of them).

To display the spline, you should break the continuous function (the one that only lives in the World of Mathematics) into many discrete segments via the Cox de Boor algorithm (in the handout) for blending functions, at an appropriately fine resolution (see the extra credit on adaptive parameterization).

Editing

Move Control Points -- Left-click

The editor should also allow a user to alter the control poly-line (and therefore the spline curve) after it has been created. In this editing mode, left-clicking and dragging a control point should move the point and update the spline accordingly. (For extra credit you can optimize the performance of your editor by noticing that each control point only affects a certain section of the curve-- cache the x-y values in a buffer and update the appropriate interval, etc.)

Insert Knots -- Right-click

The editor should allow a user to insert knots. When the user right-clicks, you convert the x-y point to a t value, which is basically a number between 0% and 100% (or 0.0 and 1.0) on the curve. To know where to insert this new knot value, ignore everthing about the control points and just stick it in the sequence of non-decreasing knot values at the first position available (after you caluculate the new control points from the old knot vector. see Helpful Pointer below). For example, after the program loads up, the user right-clicks 66% of the way along the curve from the first point to the last point. This knot value of .66 gets stuck between the zero and one to give the new knot vector < 0 0 0 0 .66 1 1 1 1 > Now the algorithm for knot insertion is run and the set of control points is update appropriately.

Note that this scheme won't insert points before or after the ends of the orignal U; you just move the U around and insert and move points to make the curve look the way you want. The shape of the curve is preserved and a new control point appears in the region of the curve where the user clicked. The purpose of doing this with NURBS instead of some other spline is that the curve stays the same when you use the knot insertion algorithm. For other types of splines (especially uniform ones where you don't track the knot values because they're all at the same intervals), it might make sense to insert control points without affecting other points, but for now (for the assignment and for the sake of simplicity) it is easiest to think of it as inserting a knot and then automatically changing the control points, instead of thinking of it as inserting control points.

Helpful pointer: When inserting a new knot and re-calculating control points, (1) Create a new empty control point list, (2) Insert the new knot into the knot vector, (3) Fill in the new control point list so that the control point values are affected only by old control point values (but NEW knot values).

What your program should do

Name your program editSpline. It should take no arguments, except maybe width and height (or a filename if you do the Load/Save extra credit).

    editSpline [ <xRes> <yRes> [ <spline-file> ] ]

The xRes and yRes would specify the window dimensions.

Include a README file with your code, saying what you did, how to compile and run it, and anything else you think we need to know.

Extra credit

Feel free to implement a few additional features for your editor. Points will be awarded based on the difficulty of implementation, how much you can learn from adding those features, and how much more useful your program will be. You may want to talk to a TA before implementing any additions.

Some things to consider adding:

Adaptive Δt value parameterization. Start with a default Δt value, like 1.0 divided by the number of pixels of distance the polyline covers. To choose the next value to step by, plug in the new t value (t_n = t_n-1 + Δt) and calculate the new position on the curve that this change will generate. Check if this x-y distance (where we were to where we will go to with the current Δt) is more than a certain amount (you could use the original Δt divided by two or something similar). If so, try half that value for Δt. Step forward and keep doing the same thing. If you do this right then even as the curve gets more complicated and more twists are added, the sharp poylgonal lines will no long appear and it won't slow down too much.

Smoothing (Antialiasing). Use OpenGL smoothing. These might be handy to know about (I didn't give you all the constants because you should read the documentation and find those out yourself.):

    glutInitDisplayMode( // make sure you have r,g,b and alpha channel
                         // as well as double buffering
    glShadeModel( // turn on the appropriate shade model (or else
                  // it will use the fast, ugly default mode)
    glEnable(     // enable blending, of course
    
    // If this exists. It doesn't exist in PyOpenGL...
    glBlendEquation( // turn on additive blending

    glBlendFunc(  // do math with the source and destination
                  // colors and source alpha value: DEST <= α_s SRC + (1-α_s) DEST
    glEnable(     // make points smooth (if you use a point size
                  // of 8 it looks nice and round and is easy
                  // to grab with the mouse)
    glEnable(     // enable line smoothing, of course
    glLineWidth(  // make the line a little fatter so there are
                  // pixels to smooth out

This is what the points and curve will look like up close: Closeup of a NURBS curve with anti-aliasing

Deleting points. Note that no algorithm exists that will preserve the curve perfectly upon deletion. You can always store a list of changes and then allow the user to remove the point by removing the curve from this history list and recalculating the entire curve from the beginning using the history list.
Load/Save. Saving the control points and knot vector to a file format of your choice (probably some kind of text file) and then allowing the user to load it and change the curve more. An easy way to do this is to take a filename as a commandline parameter. If the file doesn't exist, just create a new spline and then save the file on exit. If the file exists, then load it, allow the user to edit the spine, and automatically save over the old one on exit.
W value (Rational/Homogeneous). Adding a W value that can be changed so that the curve is actually a NURBS and not a NUBS (the R means rational-- that you are actually dividing something). You should represent the homogenizing value for each control-point visually with appropriate colors or shapes (I used a circle of different radius, and square of different size to display negative values). Make sure values like negative, zero and infinity are handled carefully. Also make sure to start the W value off at 1.0.
Toggle the control poly-line (make sure no editing is possible when the line is off):