CS91: Lab 4

Step 1: Get the source

The curve assignment has been added to your AnimationFramework reporitoy. To get the source, run

> git pull

Step 2: Compile and run

Same as before, you should compile all source in a build subdirectory. The compiled applications will be in /bin as with the rotation assignment. Additionally, the asisgnment includes 'solution' versions of the assignment libraries which you can use to build a 'solution' version of the demo.

> cd build
> make
> ../bin/CurveEditor
> ../bin/CurveEditor-Soln

User interface overview

The basecode includes a UI to test your curve code. A screenshot is below. With the 'Curve Controls' panel on the top left, you can create and edit curves. Blue points represent the input data which are interpolated between. Yellow points represent control points which are computed based on the input data. The input data points are also called keys.

The Type drop-down menu specifies how curve points are interpolated. You will implement linear, Bernstein, Castlejau, Hermite, and Matrix.
The Mode drop-down menu specifies how left mouse clicks are interpreted:

Add will append points to the curve when you left click with mouse;
Edit will allow you to drag curve points (blue) and control points (yellow) using the left mouse button;
Delete will remove curve points (blue) when you select one with the left mouse button.

The Ctrl pts button will toggle the display of control points (yellow).
The Clear button will remove the entire curve.

Curve implementation overview

The curves you implement in this assignment will be the foundation for animating objects, characters, and crowds for the remainder of the In your basecode, animation curves consist of keyframes, where each keyframe is time/value pair. For this assignment, all keys are 1.0s apart. Animation curves can interpolate between given points differently, depending on which AInterpolatorVec3 algorithm is active. Below is the class hierarchy of the interpolators you will implement:

AInterpolatorVec3
    ALinearInterpolatorVec3
    ACubicInterpolatorVec3
       ABernsteinInterpolatorVec3
       ACasteljauInterpolatorVec3
       AMatrixInterpolatorVec3
       AHermiteInterpolatorVec3

An interpolator needs to implement two core features

A function for computing control points based on given points, declared virtually as computeControlPoints()
A function for interpolating between points, declared virtually as interpolateSegment()

Assignment Due Feb 27

(10 points) Linear splines. Let's start by implementing linear interpolation
1. (5 points) Compute the interpolation fraction in AInterpolatorVec3::interpolate()
  Input: a list of Key where each Key is a std::pair
  . For example, to access the time and data of the first key, you would do
```
   ASplineVec3 key = keys[0];
   double time = key.first;
   vec3 data = key.second;
     
```
  Input: a list of control points
  Output: a list of interpolated points between each key
  This function computes a curve corresponding to the current keys. Your task is to compute the normalized time between keys[segment] and keys[segment-1] for the current time t. The normalized time is then passed to interpolateSegment().
2. (5 points) Implement ALinearInterpolatorVec3::interpolateSegment(). Use linear interpolation to compute the value of the curve.
  Input: a list of Key where each Key is a std::pair.
  Input: a list of ctrlPoints (not needed for linear interpolation, since the ctrl points are the same as the input points)
  Input: segment ID. The function should compute the value of the curve between keys[segment] and keys[segment+1]
  Input: u. The fraction between 0 and 1 at which to compute the value of the curve
  Return value: vec3 corresponding to the value of the curve
(50 points) Cubic splines. Now, let's implement piece-wise cubic curves. You will implement three equivalent methods. Given keyframe points of the form p_i = [x_i, y_i]^T (i = 0 to m), construct a cubic spline that interpolates the p_i data points.
1. (20 points) Compute control points. Implement ACubicInterpolatorVec3::computeControlPoints(). For each segment, compute the control points b0, b1, b2, b3 and add them to the list of control points.
  Input: a list of Key where each Key is a std::pair
  .
  Output: a list of ctrlPoints for each segment. At the start of the function, the list should be cleared. For each segment, four control points should be added.
  Input: startPoint - A helper for setting b1 for the first segment. You can set b1 of segment 0 like so
```
b1 = b0 + (keys[0].second - startPoint);
```
  Input: endPoint - A helper for setting b2 for the last segment. You can set b2 of segment n-1 like so
```
b2 = b3 - (endPoint - keys[lastIdx].second);
```
2. (10 points) Bernstein. Implement ABernsteinInterpolatorVec3::interpolateSegment(). Use a Bernstein polynomial to compute the curve value
  Input: a list of Key where each Key is a std::pair.
  Input: a list of ctrlPoints (four for each segment corresponding to b0, b1, b2, and b3)
  Input: segment ID. The function should compute the value of the curve between keys[segment] and keys[segment+1]
  Input: u. The fraction between 0 and 1 at which to compute the value of the curve
  Return value: vec3 corresponding to the value of the curve
3. (10 points) De Casteljau. Implement ACasteljauInterpolatorVec3::interpolateSegment(). Use de Casteljau's algorithm to compute the curve value
  Input: a list of Key where each Key is a std::pair.
  Input: a list of ctrlPoints (four for each segment corresponding to b0, b1, b2, and b3)
  Input: segment ID. The function should compute the value of the curve between keys[segment] and keys[segment+1]
  Input: u. The fraction between 0 and 1 at which to compute the value of the curve
  Return value: vec3 corresponding to the value of the curve
4. (10 points) Matrix. Implement AMatrixInterpolatorVec3::interpolateSegment(). Use the matrix formulation of the curve to compute the curve value
  Input: a list of Key where each Key is a std::pair
  .
  Input: a list of ctrlPoints (four for each segment corresponding to b0, b1, b2, and b3)
  Input: segment ID. The function should compute the value of the curve between keys[segment] and keys[segment+1]
  Input: u. The fraction between 0 and 1 at which to compute the value of the curve
  Return value: vec3 corresponding to the value of the curve
  To help with matrix math, we are using the Eigen library. Below are examples showing how to work with Eigen
```
Eigen::MatrixXd A(Rows, Cols);
//To initialize a matrix to zeros do
A = Eigen::MatrixXd::Zero(Rows, Cols);
//To access elements of the matrix
A(0,1) = 1.0;
// To solve a system of equations
P = A.inverse() * D;
```
(20 points) Hermite spline. Implement a Hermite spline having C² continuity which supports either clamped or natural end point conditions (your choice).
1. (10 points) Implement AHermiteInterpolatorVec3::computeControlPoints(). Formulate a matrix to solve for control points that give C² continuity. Solve for the slopes p'_i corresponding to each point p_i and store them in the list of control points.
  Input: a list of Key where each Key is a std::pair
  Output: a list of ctrlPoints for each segment. At the start of the function, the list should be cleared. For each segment, two control points should be added.
  Input: startPoint - Not needed. Optionally could be used for clamped endpoints if desired
  Input: endPoint - Not needed. Optionally could be used for clamped endpoints if desired
3. (10 points) AHermiteInterpolatorVec3::interpolateSegment(). Compute the Hermite curve using either the polynomial or matrix method.
  Input: a list of Key where each Key is a std::pair.
  Input: a list of ctrlPoints (consists of one slope for each input point)
  Input: segment ID. The function should compute the value of the curve between keys[segment] and keys[segment+1]
  Input: u. The fraction between 0 and 1 at which to compute the value of the curve
  Return value: vec3 corresponding to the value of the curve
Extra credit.
1. Implement an additional interpolation type as a subclasses of AInterpolatorVec3. For example try a step interpolator, a higher order polynomial, or a 'wiggly' interpolator.
2. Create a cool drawing with the splines.
3. Try animating the control points.
4. Try animating an object based on the current spline.
(10 points) Submission Guidelines
Submitting your assignment

Students should submit their code along with a README and videos. The README can be very brief, consisting of
- answers to questions,
- descriptions of what was completed, including extra challenges, and
- how long the assignment took you and what was the hardest part
Videos should show results, including any extra challenges. Videos will be collected together and shown during class presentations. Please submit a mp4 of length no more than 60 seconds. For example
- Capture the demo window with recordmydesktop --windowid [OpenGLViewerId] demo.ogv
- Check the recording with mplayer demo.ogv or run firefox demo.ogv
  NOTE: If you're running out of space because of big files, try using the /local drive for temporary storage.
About checkins

You will be asked to briefly checkin (less than 1 minute) about your homework assignment. This is not intended to much work. Please don't prepare slides or a voice over for your video. None of these are necessary! Some ideas of what you might like to talk about:
- Give your name (at least to start, until everyone gets to know each other)
- Say one interesting thing about your assignment; ideally something unique to your experience. Some ideas

CS91 Computer Animation: Lab 4

Step 1: Get the source

Step 2: Compile and run

User interface overview

Assignment Due Feb 27

(10 points) Submission Guidelines