Implementing De Boors algorithm for finding points on a B-spline

Question

I've been working on this for several weeks but have been unable to get my algorithm working properly and i'm at my wits end. Here's an illustration of what i have achieved:

If everything was working i would expect a perfect circle/oval at the end.

My sample points (in white) are recalculated every time a new control point (in yellow) is added. At 4 control points everything looks perfect, again as i add a 5th on top of the 1st things look alright, but then on the 6th it starts to go off too the side and on the 7th it jumps up to the origin!

Below I'll post my code, where calculateWeightForPointI contains the actual algorithm. And for reference- here is the information i'm trying to follow. I'd be so greatful if someone could take a look for me.

void updateCurve(const std::vector<glm::vec3>& controls, std::vector<glm::vec3>& samples)
{
    int subCurveOrder = 4; // = k = I want to break my curve into to cubics

    // De boor 1st attempt
    if(controls.size() >= subCurveOrder)
    {
        createKnotVector(subCurveOrder, controls.size()); 
        samples.clear(); 

        for(int steps=0; steps<=20; steps++)
        {
            // use steps to get a 0-1 range value for progression along the curve
                    // then get that value into the range [k-1, n+1]
            // k-1 = subCurveOrder-1
            // n+1 = always the number of total control points

            float t = ( steps / 20.0f ) * ( controls.size() - (subCurveOrder-1) ) + subCurveOrder-1;

            glm::vec3 newPoint(0,0,0);
            for(int i=1; i <= controls.size(); i++)
            {
                float weightForControl = calculateWeightForPointI(i, subCurveOrder, controls.size(), t);
                newPoint += weightForControl * controls.at(i-1);
            }
            samples.push_back(newPoint);
        }
    }

}

    //i = the weight we're looking for, i should go from 1 to n+1, where n+1 is equal to the total number of control points.
    //k = curve order = power/degree +1. eg, to break whole curve into cubics use a curve order of 4
    //cps = number of total control points 
    //t = current step/interp value
float calculateWeightForPointI( int i, int k, int cps, float t )
    {
        //test if we've reached the bottom of the recursive call
        if( k == 1 )
        {
            if( t >= knot(i) && t < knot(i+1) )
                return 1;
            else
                return 0;
        } 

        float numeratorA = ( t - knot(i) );
        float denominatorA = ( knot(i + k-1) - knot(i) );
        float numeratorB = ( knot(i + k) - t );
        float denominatorB = ( knot(i + k) - knot(i + 1) );

        float subweightA = 0;
        float subweightB = 0;

        if( denominatorA != 0 )
            subweightA = numeratorA / denominatorA * calculateWeightForPointI(i, k-1, cps, t);
        if( denominatorB != 0 )
            subweightB = numeratorB / denominatorB * calculateWeightForPointI(i+1, k-1, cps, t);

        return subweightA + subweightB;

    }

    //returns the knot value at the passed in index 
    //if i = 1 and we want Xi then we have to remember to index with i-1
float knot(int indexForKnot)
    {
         // When getting the index for the knot function i remember to subtract 1 from i because of the difference caused by us counting from i=1 to n+1 and indexing a vector from 0
         return knotVector.at(indexForKnot-1);
    }
    //calculate the whole knot vector
void createKnotVector(int curveOrderK, int numControlPoints)
    {
        int knotSize = curveOrderK + numControlPoints;
        for(int count = 0; count < knotSize; count++)
        {
            knotVector.push_back(count);
        }
    } 

Answer 1

Your algorithm seems to work for any inputs I tried it on. Your problem might be a that a control point is not where it is supposed to be, or that they haven't been initialized properly. It looks like there are two control-points, half the height below the bottom left corner.