View Full Version : spline questions

 mjs103 March 2005, 02:44 AMI've been reading about B-splines and had some questions. B-splines are splines controlled by control points laid down by the user (through which the spline does not interpolate), a knot vector (which the user does not control except for multiplicity), and the B-spline basis functions. If the user places control points, he never actually places a point through which the curve interpolates (disregarding the end points using the standard knot vector). Maya lets you create a spline curve by placing either control points or knot (edit) points, but the end result spline appears to be the same in construction either way (meaning that either way you go the spline has both control points and knot points). If the user places just knot points how are control points determined from that? Also, on an unrelated note, I was wondering if someone could clear up why you can only approximate the conic sections with non-rational B-splines, and why you can get EXACT conic sections using rational B-splines. The book I have touts this, but doesn't explain why. Thanks!
03 March 2005, 06:31 AM
If the user places just knot points how are control points determined from that?

I'd guess (without knowing for sure) that Maya internally solves an iterative optimization problem. It essentially guesses where the CVs should be in order to produce a curve that interpolates your EPs. Then it measures how far off it is, at curve points near the EPs, and pushes the CVs in the direction that makes the curve come closer to the EPs. Repeat a few times and you'll have a purdydurndgood approximation.

I was wondering if someone could clear up why you can only approximate the conic sections with non-rational B-splines, and why you can get EXACT conic sections using rational B-splines.

Hmmm... this isn't someone's homework problem is it?
The answer to this question is only a quick google search away...I checked.

mjs1
03 March 2005, 05:32 PM
Thanks, shadowMaster! I did read about a way to do this so I think I understand what's going on.

As far as the homework thing goes, I've been a digital artist in the industry for a while now and in the past year have taken on learning computer graphics programming as a hobby, to see how it all works. So I suppose it could be considered homework, but it's not being graded... :)

craigd
03 March 2005, 07:37 PM
If the user places just knot points how are control points determined from that?

I'm not sure exactly what Maya does, but one way of doing this that seems to work (for cubic splines at least) is to find the tangents of a natural-cubic-spline through your edit points, then do a basis conversion to b-spline.

#include <ImathVec.h>
#include <vector>

// solve a tridiagonal linear system
// A - lower diagonal (n-1 elements)
// B - main diagonal (n elements)
// C - upper diagonal (n-1 elements)
// R - right hand side vector (n elements)
// U - result (n elements)
template <class T>
bool tridiag(T a[], T b[], T c[], T r[], T u[], const int n) {
int j;
T bet;
T *gam = new T[n];
if (b[0] == 0.0)
return false;
u[0]=r[0]/(bet=b[0]);
for (j=1;j<n;j++) {
gam[j]=c[j-1]/bet;
bet=b[j]-a[j-1]*gam[j];
if (bet == 0.0)
return false;
u[j]=(r[j]-a[j-1]*u[j-1])/bet;
}
for (j=(n-2);j>=0;j--)
u[j] -= gam[j+1]*u[j+1];
delete [] gam;
return true;
}

void interpolatePoints(
std::vector<Imath::V3d> &cvs,
std::vector<double> &knots,
const std::vector<Imath::V3d > &ep) {

const int N = ep.size();
if (N < 2)
return;

const int deg = 3;
int numCVs = N+2;
int numKnots = numCVs+deg+1;
cvs.resize(numCVs);
knots.resize(numKnots);

if (N == 2) { // straight line
for (int i=0; i<deg+1; i++) {
knots[i] = 0;
knots[i+deg+1] = 1;
}
cvs[0] = ep[0];
cvs[1] = (ep[0]*2 + ep[1])/3;
cvs[2] = (ep[0] + ep[1]*2)/3;
cvs[3] = ep[1];
return;
}

// knot vector
for (int i=0; i<deg+1; i++)
knots[i] = 0;
for (int i=deg+1; i<numCVs; i++)
knots[i] = i-deg;
for (int i=numCVs; i<numKnots; i++)
knots[i] = numCVs-deg;

double *data = new double[4*N-1];
double *a=data, *r=a+N, *x=r+N, *b=x+N;
a[0] = a[N-1] = 2;
for (int i=1; i<N-1; i++)
a[i] = 4;
for (int i=0; i<N-1; i++)
b[i] = 1;
const double conv[4][4] = { // 6 * inverse of bspline basis matrix
{0, 2.0/3, -1, 1},
{0, -1.0/3, 0, 1},
{0, 2.0/3, 1 ,1},
{6, 11.0/3, 2 ,1}
};

for (int dim=0; dim<3; dim++) {

// find tangents for natural cubic spline
r[0] = 3*(ep[1][dim]-ep[0][dim]);
r[N-1] = 3*(ep[N-1][dim]-ep[N-2][dim]);
for (int i=1; i<N-1; i++)
r[i] = 3*(ep[i+1][dim]-ep[i-1][dim]);

if (!tridiag(b, a, b, r, x, N)) {
cerr << "can't find CVs\n";
} else {
// convert NCB to B-Spline
double a, b, c, d;
int i;
int nseg = N-1;
for (i=1; i<nseg; i++) {
a = x[i+1]+x[i]-2*(ep[i+1][dim]-ep[i][dim]);
b = 3*(ep[i+1][dim]-ep[i][dim])-2*x[i]-x[i+1];
c = x[i];
d = ep[i][dim];
cvs[i+1][dim] = conv[1][0]*a + conv[1][1]*b + conv[1][2]*c + conv[1][3]*d;
}
cvs[i+1][dim] = conv[2][0]*a + conv[2][1]*b + conv[2][2]*c + conv[2][3]*d;
cvs[0][dim] = ep[0][dim];
cvs[numCVs-1][dim] = ep[N-1][dim];
cvs[1][dim] = (cvs[2][dim]-cvs[0][dim])/3+cvs[0][dim];
cvs[numCVs-2][dim] = cvs[numCVs-1][dim]+(cvs[numCVs-3][dim]-cvs[numCVs-1][dim])/3;
}
}
delete [] data;
}

mbaas
03 March 2005, 02:27 PM
I'd guess (without knowing for sure) that Maya internally solves an iterative optimization problem. It essentially guesses where the CVs should be in order to produce a curve that interpolates your EPs.

While the principle idea is correct (i.e. you set the CVs so that the curve interpolates the given input points), I really doubt that Maya solves this iteratively. You can do that analytically which is faster and gives accurate results.

The first thing you have to do is to compute a knot vector t. This is either done by spacing them uniformly (t[0]=0, t[1]=1, t[2]=2, ...) or by chord length. The latter means the distance of the input points determines the spacing. By the way, you can see those two options in the EP Curve Tool options dialog in Maya. Chord length spacing usually results in smoother curves.

Now you set up a system of equations c(t[i]) = p[i] where c is the spline, t is the knot vector and p are the input points you want to interpolate. The unknowns are the actual control points of the spline. This system of equation results in a tridiagonal system which can be solved rather efficiently. Once you've solved it you have the control points and together with the knot vector you have determined the curve that interpolates your points.

I don't know what book the original poster has, but I would assume that any book about splines will mention this topic (look for the keyword "interpolation"). And any numerics book will tell you about solving tridiagonal systems of equations, see for example section 2.4 in the classic Numerical Recipes (http://www.library.cornell.edu/nr/cbookcpdf.html).

- Matthias -

daniel_arz
03 March 2005, 09:39 PM
Maya lets you create a spline curve by placing either control points or knot (edit) points, but the end result spline appears to be the same in construction either way (meaning that either way you go the spline has both control points and knot points). If the user places just knot points how are control points determined from that?

because the shape of the curve determines the position of the edit points and not the other way around, Maya "reverse engineers" the resulting curve and its CV points. This is one reason why tweaking a curve via edit points is not adequate for major curvature changes.

Daniel

mjs1
03 March 2005, 07:51 AM
Thanks everyone!

After reading the replies I did some more research. It looks like finding control points by way of solving for the tridiagonal matrix is the most efficient way to go. In it I'll be setting up a system of equations, based on the maximum contribution of the various control points can have at integer values of t (either 2/3 or 1/6 for a cubic B-spline) which combine together to give me the points I input.

CGTalk Moderation
03 March 2005, 07:51 AM
This thread has been automatically closed as it remained inactive for 12 months. If you wish to continue the discussion, please create a new thread in the appropriate forum.

1