Implementacja algorytmu De Boorsa do znajdowania punktów na B-splajnie

Question

Pracuję nad tym przez kilka tygodni, ale nie jestem w stanie sprawić, aby mój algorytm działał poprawnie i jestem na końcu rozumu. Oto ilustracja tego, co udało mi się osiągnąć:

Jeśli wszystko działa by się spodziewać A Perfect Circle/owal na końcu.

Moje punkty próbkowania (na biało) są przeliczane po każdym dodaniu nowego punktu kontrolnego (w kolorze żółtym). W 4 punktach kontrolnych wszystko wygląda idealnie, ponownie dodając piątą pozycję na pierwszym miejscu wygląda dobrze, ale potem na 6 zaczyna znikać z boku, a na 7. podskakuje do początku!

Poniżej zamieściłem mój kod, gdzie calculateWeightForPointI zawiera rzeczywisty algorytm. I dla odniesienia - here is the information i'm trying to follow. Byłbym bardzo wdzięczny, gdyby ktoś mógł mnie poszukać.

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

Twój algorytm wydaje się działać dla wszystkich wejść, na których go wypróbowałem. Twoim problemem może być to, że punkt kontrolny nie jest tam, gdzie powinien być, lub że nie został poprawnie zainicjowany. Wygląda na to, że są dwa punkty kontrolne, połowa wysokości poniżej lewego dolnego rogu.