1. The animation algorithm shown below performs key frame based animation. It assumes that the key frames are described by a series of m linked lists in a data structure named K. Each node in the linked list contains three fields: frame (giving the frame number of the key frame), value (giving the value of attribute a at this frame), and next (giving a pointer to the next node in the linked list). The variable K.head_a gives a pointer to the head of linked list a. The pointer variables p_a and n_a are used to point to the previous key frame and the next key frame, respectively.

Animation Algorithm 3

00a m = ||A||

00b for a = 0, 1, 2, ..., m - 1 // for all attributes

00c p_a = K.head_a

00d n_a = K.head_a

00e end for

01 for f = 0, 1, ..., F // for all frames

02 for a = 0, 1, 2, ..., m - 1 // for all attributes

03 while f > n_a -> frame

04a p_a = n_a

04b n_a = n_a -> next

04c end while

05 u = (f p_a -> frame) / (n_a -> frame p_a -> frame)

06 A_a = (1 u) * (p_a -> value) + u * (n_a -> value)

07 end for

08 draw object with values A₀, A₁, A₂, ..., A_m-1

09 end for

The above algorithm assumes that time is represented as a nonnegative integer value named a frame number. Give a revised version of the algorithm suited to real-time animation. If you number the lines, you need only provide the changed/added/deleted lines.

Suppose that the overall length of the animation is T time units. Assume that after drawing the object, the function getElapsedTime (in some imaginary graphics library) is available to yield the amount of time that has elapsed since the previous time the object was drawn (or since the beginning of the algorithm in the case of the first frame). If you want to program this method, the OpenGL function is glutGet(GLUT_ELAPSED_TIME).

Hint: the human user should store something different from frame values in the linked list.

2. In this question, you will write a 3D graphics program to display a curve, a sphere moving along a curve, and a sphere moving along the curve with sinusoidal and parabolic ease-in and ease-out.

(a) Uniform Cubic B-Spline

Using a 3D graphics package, such as OpenGL, draw a blue uniform cubic B-spline using the following control points (also draw the control points in black):

( 0.0, 0.0, 0.0),

( 1.0, 3.5, 0.0),

( 4.8, 1.8, 0.0),

( 6.5, 7.0, 0.0),

( 9.0, 3.5, 0.0),

(32.5, 4.8, 0.0),

(33.2, 2.6, 0.0),

(36.8, 7.0, 0.0),

(37.8, 5.0, 0.0),

(41.2, 20.5, 0.0),

(41.5, 21.5, 0.0),

Hint to get started: Start with code for drawing the control points in black. Then draw a straight blue line made up of many dots from the first point to the last point. Position the camera on the positive Z axis. Then replace the code for drawing a straight line with code for drawing a curve. An algorithm for drawing a curve is given in the online notes at the end of Uniform B-Spline Derivation section of the Interpolation notes.

Hint for OpenGL: The DrawPoint(Qx, Qy, Qz) function in the notes corresponds to the following OpenGL commands:

glBegin(GL_POINTS);

glVertex3d(Qx, Qy, Qz);

glEnd();

(b) Motion Control

Using a 3D graphics package, such as OpenGL, animate a yellow ball moving along the blue curved path defined in part (a) above. The ball should take 5 seconds to traverse the whole path and then begin again. Motion control should be used to ensure that the ball goes at a constant rate along the curve.

Hint for drawing the sphere in the right place: Leave your code for part (a) unchanged because we still want to be able to see the curved path. You can add a DrawSphere function that is similar to the DrawCurve function, but it will need to depend on the time or the fraction of the arc length. To determine where to translate the sphere for drawing, calculate Qx, Qy, and Qz in the same manner as for part(a).

Hint: for implementing motion control: Construct a table similar to that shown in class. Call the function for constructing the table once from the init function. In your table, add an extra column for the segment number (which was variable i in the Uniform B-Spline notes). When drawing in segment 0, use points 0, 1, 2, and 3; when drawing in segment 1, use points 1, 2, 3, and 4; etc. To initialize the table, fill in say 20 evenly spaced u values between 0 and 1 for segment 0, then repeat for each of the other segments. A GetParameters function for the table can be provided that, given an arc length, returns the estimated values for the segment number i and the fraction u.

Alternate hint: instead of having a separate integer segment number i and floating point u value, combine them into a single floating point number. Put this number in the table instead of a uvalue. For example, let a value of 3.72 represent segment 3 and u = 0.72. Using this idea, no extra column is needed in the table, interpolation code is simplified, and the GetParametersfunction only needs to return a single value. However, you will need to break the value back into i and u components.

(c) Sinusoidal Ease-in / Ease-out:

A variant on the program described for part (b) should also demonstrate ease-in and ease-out, where a sinusoidal (i.e., sine-based) distance-time function is used for easing in and easing out. You can either have two separate programs or you can change your program to have two modes. In the default mode or when b is entered as input, it uses the method for part (b). When c is entered as input, the program switches to using the sinusoidal ease-in/ease-out function.

(d) Parabolic Ease-in / Ease-out:

A variant on the program described for part (b) should also demonstrate ease-in and ease-out, using a parabolic ease-in and ease-out as described in the class notes. For ease-in, have the speed increase for the first 1/6 of the curve (i.e., t₁ = 1/6) and for ease-out, have the speed decrease for the last 1/6 of the curve (i.e., t₂ = 5/6). Thus, the speed of the sphere should increase while travelling along the first 1/6 of the path, then go at a constant rate until 5/6 of the path, and then decrease along the last 1/6 of the path. Again, this could be a separate program or invoked when d is entered as input. The method for calculating v₀ is given in the on-line notes (or it is 1.2 for this question.)