CODEWITHSUNDEEP
c#recursionbeziercurvespline
Footch
Footch

Reputation: 129

Uniform B-Spline using deBoor's algorithm issue

I have a very simple case in which I need to draw a single uniform B-spline segment of degree 2 (4 control points) and I'm trying to implement deBoor's algorithm in C#(https://en.wikipedia.org/wiki/De_Boor%27s_algorithm) but I'm running into an issue and no amount of reading and researching has helped me find out what is going on.

In my case I only have 4 control points (p1, p2, p3 and p4) defined in a Point[] array. So I only need the curve segment between points p2 and p3. Because of that, I have constructed a uniform knots array without leading and trailing knots [0, 1, 2, 3] - basically I can just use i in this case but I do it for the sake of sticking to the formula. I built an implementation of the recursive formula from Wikipedia:

enter image description here enter image description here

Which looks like this:

    Point deBoor(int i, int k, float t, int[] knots)
    {
        //i - knot span index
        //k - degree
        // t - time [0-knots.Length-1]
        //knots - the knots array
        if (k == 0) return points[knots[i]]/3f;
        return ((t - knots[i]) / (knots[i + k] - knots[i])) * deBoor(i, k - 1, t, knots) + ((knots[i + k + 1] - t) / (knots[i + k + 1] - knots[i + 1])) * deBoor(i + 1, k - 1, t, knots);
    }

I try to get the point form the deBoor method like this:

float t = time * (points.Length - 1); //time ranges from 0 to 1
int[] knots = new int[] { 0, 1, 2, 3 };
point = deBoor(0, 2, t, knots);

Unfortunately, the result I get is not correct. This image shows what my control points look like, what I'm expecting to get and what I'm actually getting: enter image description here

I looked at other implementations, like this one: https://gist.github.com/soraphis/61ee9185416ee23d0d40 and they all seem to do the same, just coded differently. I tried to copy their solutions but I got even worse results. All this makes me think that I'm missing something painfully obvious.

Upvotes: 1

Views: 1076

Answers (1)

Dominik Mokriš
Dominik Mokriš

Reputation: 1169

You seem to be confusing knots and control points. There are several things that we need to improve in your solution in order to make it work.

Degree zero functions

As already noted by @fang, your solution for k==0 is strange. I suggest replacing

if (k == 0) return points[knots[i]]/3f;

by something closer to the original formula, such as

if (k==0)
{
  if (t <= knots[i] && t < knots[i+1])
    return 1;
  else
    return 0;
}

Knot vector

As also noted by @fang, for a quadratic spline with four control points you need seven knots. You mentioned that you want uniform knots and based on your expected picture I would recommend

int[] knots = new float[] {0, 1/6, 2/6, 3/6, 4/6, 5/6, 1};

Note that the knots are now between 0 and 1; this means that t and time will be the same, i.e., 

float t = time; //time ranges from 0 to 1 and so does t

If you insist on your knots being ints (which, IMHO, contributed to your confusion) use

int[] knots = new int[] { 0, 1, 2, 3, 4, 5, 6 };
float t = time * 6; //time ranges from 0 to 1 and t from 0 to 6

Note the swapped order: t has to be time scaled to cover the whole range of knots.

Evaluation

De Boor's algorithm evaluates one B-spline, i.e., one of the basis functions (some people use a conflicting nomenclature and use the word B-spline for the whole spline function and not just one of the basis functions; this sometimes leads to confusion).

Informally speaking, for a given t, your deBoor function gives you the coefficient of the i-th control point, which is a scalar. Therefore, the return value of deBoor has to be a float or double or something similar and certainly not a point.

For each t you need to sum the control points scaled by these coefficients. So your final result will be something like

point value = deBoor(0, 2, t, knots) * points[0]
  + deBoor(1, 2, t, knots) * points[1]
  + deBoor(2, 2, t, knots) * points[2]
  + deBoor(3, 2, t, knots) * points[3];

Note that * denotes a multiplication of a float and a point (you might need to overload such an operator) and + denotes a sum of two points (again, operator overloading might be required). I'm not very versed in C#, so there might be a more elegant way of writing it down; for instance, I invite you to use a for loop.

If you are still confused, I recommend first getting acquainted with Bézier curves and then proceed to B-splines. Relatively concise introduction can be found for instance here. The pictures are a bit 90s-style but the ideas are still valid and presented in an understandable and concise way.

Upvotes: 3

Related Questions