Sign in to follow this  

B-Spline calculation

This topic is 4302 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi! I am currently trying to write a b spline drawing program and i would like to confirm with others whether what i have is correct for i am not getting the right results. //Here is how i do it. //interpolate the t parameter (0f to 1f) for(float t = 0f; t <= 1f; t+=fStepSize) { //Sum for x and y fX = 0f; fY = 0f; //Loop through all points for(int i = Points.Count-1; i >= 0; i--) { fBasisValue = BSplineBasis(t, i, intDegree); //Get value from basis function fX += fBasisValue*arrPoints[i].X; fY += fBasisValue*arrPoints[i].Y; } AddPoint(fX, fY); } BSplineBasis is a recursive function public float BSplineBasis(float t, int i, int p) { if(p == 0f) { if(knot[i] <= t && knot[i+1] > t) return 1f; return 0f; } return (t-knot[i])/(knot[i+p]-knot[i]) * BSplineBasis(t,i,p-1) + (knot[i+p+1]-t)/(knot[i+p+1]-knot[i+1])*BSplineBasis(t,i+1,p-1); } There problem i encounter is when knot[i+p] - knot[i] = 0. I will get a NaN because of division by 0. How should i handle the division by 0 thingy? Cause the mathematical formula i see does not say anything bout it. http://mathworld.wolfram.com/B-Spline.html Or is there anything else cause problem? Thanks in advance

Share this post


Link to post
Share on other sites
A proper knot vector should contain strictly increasing values, which is why it's never the case you get a division by zero (or by a negative value either). This document is a good B-Spline reference that should help you out. It also includes a section on making the B-Spline natural, which means you constrain the second derivative at the end-points to zero. This makes the curve behave more like a straight peice of malleable metal, in that you can bend it in different ways however it tries to remain straight in the areas where it isn't constrained by the "knots."

Finally, keep in mind that for an interpolating B-Spline construction is a two-step process. First you have to set up the system of equations that finds the control points, and then you have use those control points with the basis function to generate the curve. This means you'll need at the very least a general NxN matrix class that implements inversion to solve the system. The article I posted covers how to generate the system, but solving it is up to you. For a non-interpolating B-Spline you can just use the input points as the control points.

Share this post


Link to post
Share on other sites
Hi! I'm back with some questions to ask.

If i have knot vectors that have same values, then i will still get a division by 0 error. As far as i know, it is legal to have knot vector of same value as long as it is non decreasing

Share this post


Link to post
Share on other sites
It doesn't make sense to have two equal values in the knot vector, since that implies that the curve can take on two different values given the same input parameter, which is impossible. In all honesty, the values in the knot vector are of no major importance if you're just drawing the curve as a whole. Only once it starts describing some type of motion do you need to worry about the values. I've personally just used consecutive integers in the past as knot values.

Share this post


Link to post
Share on other sites
How about nonperiodic B-spline?

What i've read so far says

p = order of the curve, First p knot value = 0, Last p knot value = 1

This is what giving me the division by zero problem. Any thoughts on this?
This whole spline thingy is quite confusing sometimes. Looking forward for further replies.

Share this post


Link to post
Share on other sites
A non-periodic B-Spline is one that interpolates the first and last control points. However it requires you to divide by zero. This isn't so much of a problem when you're dealing with the mathematical definition of a B-Spline, since it turns out that when you encounter a zero denominator you'll also encounter a zero numerator that "cancels" everything, but if you try and implement it in code you'll run into problems. You might try replacing the denominator with a really small number instead when that happens. I did a little more searching and found this reference that covers non-periodic B-Splines.

Share this post


Link to post
Share on other sites
Aha!!! I finally realize where the problem lies!

This is how i used to do it

for(float t = 0f; t <= 1f; t+=stepSize)

My problem is due to the parameter range from 0 to 1

In the document that you linked, for a uniform knot of [0,1,2,3,4,5,6,7], the parameter range is [2,5].

This shows me that parameter range should be taken according to the knot values.
since the example given is a quadratic, with some figuring, i realize that i should take from

knot[degree] = 2;
knot[knotlength-degree-1] = 5

I plug it in my program and now it gives result that match other applets that i came across.

Anything that i get wrongly still? Hope my result is not of coincident.

Share this post


Link to post
Share on other sites
That's correct, the knot vector needs to have extra values depending on the degree of the B-Spline. For instance, a 3rd degree (cubic) B-Spline needs to have 3 extra values at either end of the vector. The parameter range is then from λn to λm+n. How you chose these values depends on what type of spline you're creating. For an interpolating spline (when you're solving for the control points) the extra values can be anything you want as long as they're non-decreasing. For a non-periodic spline, you make the first and last n+1 values equal so that the end points are interpolated. But like I mentioned before, in either case you'll need to make explicit checks for division by zero if you allow two values in the vector to be equal.

Finally, remember that the basis Njn(t) is always 0 for t < λj or t > λj+n+1. I noticed that your basis function only checks this when n = 0, however if you chose to render the curve by implementing C(t) term for term, then this check is important:


if(t < knot[i] || t > knot[i+p+1])
return 0.0f;
else if(p == 0)
return 1.0f;

Share this post


Link to post
Share on other sites

This topic is 4302 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this