CS91: Lab 5

B-Splines

B-Splines are named after basis spline. Like the Catmull-Rom spline, it is a piecewise polynomial which provides local control with smoothness guarantees are each key. This lab can be attempted for extra challenge if your group has already finished the core assignment.

To complete this assignment, you will need to extend the basecode to support the new spline type (Part 1) and then to read and implement the algorithm described in this B-Spline construction summary (Part 2).

Part 1: Extend the basecode to support a new spline type

Implementing a B-Spline with the base code requires implementing a custom interpolater and adding an option to the UI to switch to the new spline type.

In aSplineVec3.h, add a new interpolation type enum called CUBIC_BSPLINE

In aSplineVec3.h, add a new BSpline interpolator derived from ACubicInterpolatorVec3

class ABSplineInterpolatorVec3 : public ACubicInterpolatorVec3
{
public:
    ABSplineInterpolatorVec3() : ACubicInterpolatorVec3(ASplineVec3::CUBIC_BSPLINE) {}

    virtual vec3 interpolateSegment(
        const std::vector& keys,
        const std::vector& ctrlPoints,
        int segment, double u);

    virtual void computeControlPoints(
        const std::vector& keys,
        std::vector& ctrlPoints,
        vec3& startPt, vec3& endPt);

// You probably want a knots vector...
protected:
    std::vector mKnots;
};

In aSplineVec3.cpp, create stubs for the implementations of interpolateSegment and computeControlPoints

BSplineInterpolatorVec3::computeControlPoints(
    const std::vector& keys,
    std::vector& ctrlPoints,
    vec3& startPt, vec3& endPt)
{
    ctrlPoints.clear();
    if (keys.size() <= 1) return;

    std::cout << "BSpline computeControlPoints\n";
}

vec3 ABSplineInterpolatorVec3::interpolateSegment(
    const std::vector& keys,
    const std::vector& ctrlPoints,
    int segment, double t)
{
    std::cout << "BSpline interpolate\n";
    return vec3(0,0,0);
}

Extend ASplineVec3i::setInterpolationType to support BSplines

void ASplineVec3::setInterpolationType(ASplineVec3::InterpolationType type)
{
    double fps = getFramerate();

    delete mInterpolator;
    switch (type)
    {
    case LINEAR: mInterpolator = new ALinearInterpolatorVec3(); break;
    case CUBIC_BERNSTEIN: mInterpolator = new ABernsteinInterpolatorVec3(); break;
    case CUBIC_CASTELJAU: mInterpolator = new ACasteljauInterpolatorVec3(); break;
    case CUBIC_HERMITE: mInterpolator = new AHermiteInterpolatorVec3(); break;
    case CUBIC_MATRIX: mInterpolator = new AMatrixInterpolatorVec3(); break;
    case CUBIC_BSPLINE: mInterpolator = new ABSplineInterpolatorVec3(); break;
    };

    mInterpolator->setFramerate(fps);
    computeControlPoints();
    cacheCurve();
}

Download a new implementation of CurveViewer.cpp that supports BSpline types

After completing this section, you should be able to select a BSpline type in the UI and see your print statements when you click to add, delete and edit points.

Part 2: Implement B-Splines

For this assignment, let's implement a uniform B-Spline which is based on a cubic (degree 3) polynomial. A description of how this is done is in the handout. B-Splines use the concept of a knot to control the amount of influence each basis function has over each point. To compute the control points, you will need to

Calculate a knot vector for a uniform B-Spline. Knots should be evenly spaces 1 apart and the start knot should be at time 0.
Similar to your Hermite spline, compute a matrix A to create a natural B-Spline. This will correspond ot setting the 2nd derivative at t₀ and t_m to zero, where t_m is the last point knot and m is the number of segments. The matrix A will have (m+3) rows and columns.
Compute a matrix D to hold the given points we wish to interpolate. The matrix D will have size (m+3,3).
Solve our control points C = A.inverse() * D
Save our control points in C into the vector ctrlPoints. ctrlPoints will have m+3 points in it.

To interpolate using the B-Spline, you must combine control points, knots, and the fractional time u. To make your life easier, implement functions to compute N and dN in terms of the recurrence relationship.

Another tip is to hard-code the example points for the writeup and check the output of your functions against the writeup. In this way, you can improve your understanding through a concrete example.

Submission Guidelines

Don't forget to show off your excellentness by highlighting your B-Spline in the assignment README and video.

CS91 Computer Animation: Lab 5

B-Splines

Part 1: Extend the basecode to support a new spline type

Part 2: Implement B-Splines

Submission Guidelines