Controlling the knots for non-uniform spline interpolation

[tomwhoiscontrary]

I would like to use a one-dimensional spline to approximate a function, by interpolation. However, i would like to pick specific x values for the knots, creating a non-uniform spline.

It looks to me like ts_bspline_interpolate_cubic always spaces the knots evenly. Is there any way to interpolate values using a non-uniform spline with specific knots?

[msteinbeck]

Hi @tomwhoiscontrary,

Is there any way to interpolate values using a non-uniform spline with specific knots?

ts_bspline_interpolate_cubic creates a sequence of connected Bezier curves using the natural spline interpolation approach. For instance, if you want to interpolate four points P0, P1, P2, and P3, ts_bspline_interpolate_cubic creates a B-Splines consisting of four connected Bezier curves B0, B1, B2, and B3 where:

• B1 moves from P0 to P1
• B1 moves from P1 to P2
• B2 moves from P2 to P3
• B3 moves from P3 to P4

The knot vector is scaled to the default domain of [0, 1] where each internal knot describes the bounds of the Bezier curve B_n. For instance, the knot vector of a spline which has been interpolated of four points looks like this:

[0, 0, 0, 0, 0.25, 0.25, 0.25, 0.25, 0.5, 0.5, 0.5, 0.5, 0.75, 0.75, 0.75, 0.75, 1, 1, 1, 1]

where:

• 0 -- 0.25 is the bound of B0
• 0.25 -- 0.5 is the bound of B1
• 0.5 -- 0.75 is the bound of B2
• 0.75 -- 1 is the bound of B3

Arranging the knot vector like this makes perfectly sense since s(u) == order (with s being the multiplicity of a knot value) for all internal knots ensures that each Bezier curve 'hits' its start/end point (unlike B-Spline, Bezier curves, by design, pass through their start/end point). As the interpolated spline is cubic, its order is 4 requiring s(u) == 4 for each internal knot value.

To be honest, I never heard or read about an interpolation algorithm which allows one to specify the points to interpolate as well as the knot vector to create. Maybe you have a reference for such an algorithm? However, what you can do is to insert particular knots values using ts_bspline_insert_knot which preserves the shape of a spline. For instance, you could modify the knot vector above by inserting the knot value 0.3 two times:

[0, 0, 0, 0, 0.25, 0.25, 0.25, 0.25, 0.3, 0.3, 0.5, 0.5, 0.5, 0.5, 0.75, 0.75, 0.75, 0.75, 1, 1, 1, 1]

Unfortunately, TinySpline does not provide a function to remove a particular knot value from a spline. This operation is specified for splines but not easy to implement though, see #11. If you find some code which allows you to remove a knot value from a spline you could use ts_bspline_insert_knot and this function in combination to form the knot vector of your choice without modifying the shape of your interpolated spline.

[tomwhoiscontrary]

One of the things i find stimulating about splines is that everyone who writes or codes about them seems to use slightly different terminology. For example, you see a cubic B-spline as being a series of Bézier curves, which i hadn't come across before. I originally learned cubic splines as being a series of cubics, but without the idea that those cubics were Béziers. Meanwhile, most of the more mathematical treatments of B-splines i see are all about the basis functions.

Some genius at the University of Edinburgh has an interactive demonstration of non-uniform B-splines, where the knots can be dragged around the axis of the parametric coordinate:

http://www.inf.ed.ac.uk/teaching/courses/cg/d3/nonbspline.html

Einspline has an implementation:

http://einspline.sourceforge.net/NUBinterface.shtml

I can't imagine anyone wanting to use them for graphics. However, they are quite useful for interpolating functions, where you don't necessarily have samples of the function at evenly-spaced points.

[msteinbeck]

I originally learned cubic splines as being a series of cubics, but without the idea that those cubics were Béziers.

A series of cubics and a series of cubic Bezier curves, actually, are the same since cubic Bezier curves can be written as cubic functions, see https://wikimedia.org/api/rest_v1/media/math/render/svg/504c44ca5c5f1da2b6cb1702ad9d1afa27cc1ee0.

I do not see B-Splines as sequences of Bezier curves in general. Only ts_bspline_interpolate_cubic produces this kind of splines :). However, every B-Spline can be transformed into such a sequence by increasing the multiplicity of every internal knot to the order of a spline.

Einspline has an implementation

Hmm, I can't find any function which allows you to interpolate a spline with given points and given knot vector. Maybe I misunderstood your question. It looks like you just want to interpolate NURBS. TinySplines handles NURBS as well and, of course, supports to interpolate cubic NURBS by using homogeneous coordinates.

Some genius at the University of Edinburgh has an interactive demonstration of non-uniform B-splines, where the knots can be dragged around the axis of the parametric coordinate

As shown by your example, the shape of a B-Spline changes if its knot vector gets modified. You can of course set the knot vector of a spline using ts_bspline_set_knots, but it will change your spline's shape as well.

[tomwhoiscontrary]

Hmm, I can't find any function which allows you to interpolate a spline with given points and given knot vector.

You firstly call create_general_grid with the x values for the knots, then create_NUBspline_1d_d with a pointer to the resulting grid and the y values for the knots. For some reason, Einspline calls knot vectors grids, and models them as separate objects.

As shown by your example, the shape of a B-Spline changes if its knot vector gets modified.

What the example shows is that a B-spline can be interpolated through a set of data points regardless of what its knot vector is. It is indeed true that the fit changes as the knot vector is changed.

In any case, i don't want to modify the knot vector of an existing spline, i want to fit a spline using a specified knot vector. The example was meant to show that a B-spline with a non-uniform knot vector is possible.

It's quite likely i've phrased my question wrongly, and quite possible that i've misunderstood some terms. I'll step back a bit and try to explain what i'm trying to achieve.

I have some samples of a function which i believe to be continuous and smooth:

x	y
10	23.8998
11	5.34121
12	2.46852
14	0.843357
16	-0.449818
19	-1.01867
20	4.40684

I would like to interpolate values between those samples.

If i pass the y values alone to ts_bspline_interpolate_cubic, i get a one-dimensional spline, but one where the x values range from 0 to 1, rather than from 10 to 20, and where the points where the spline reproduces the y value of a sample are evenly spaced, rather than unevenly, as in the data.

if i pass both the x and y values to ts_bspline_interpolate_cubic, i get a two-dimensional spline where the points where the spline reproduces the y value of a sample have the correct x values. However, this is really a two-dimensional spline, not an interpolation of a one-dimensional function, which means it could potentially do things that a function can't, like loop round on itself. Also, i'm not sure if there's an easy way to actually find the y value for a known x value.

Is there any way to do this using TinySpline?

[msteinbeck]

Now I see what you are trying to do and it looks like you are mixing up how einspline and TinySpline define the term dimension. For TinySpline, an n-dimensional spline is a spline with n-dimensional points. For instance, a two-dimensional spline is a spline consisting of points with components x and y, a three-dimensional spline is a spline consisting of points with components x, y, and z... and so forth. On the other hand, einspline seems to use this term to differ splines, surfaces, and whatever you call a surface in 3D. It does not describe your actual data points.

That being said, in terms of TinySpline you want to interpolate a two-dimensional spline because your data points consist of two components, x and y respectively.

However, this is really a two-dimensional spline, not an interpolation of a one-dimensional function

TinySpline, unlike einspline, supports only splines, not surfaces and... seriously, how do you call a surface in 3D? Anyhow, splines are exactly what you need because you want to interpolate a cubic function like this:

$$f(x) = ax³ + bx² + cx + d$$

As explained above, ts_bspline_interpolate_cubic generates a sequence of these functions interpolating your data set.

Now, let's have a look at the knot vector thing. You want to extrapolate data using the knot vector, for instance, like this:

tsBSpline spline;
ts_bspline_interpolate_cubic(points, n, // <-- your data
    2, // <-- we need a two-dimenstional spline
    &spline);

tsDeBoorNet net;
ts_bspline_evaluate(&spline,
    10, // <-- this is your lowest x-value
    &net);

but this is not how the knot vector is working, regardless of how you set its values up. The knot vector describes the domain of a spline, for instance [0, 1]. That is, you can extract a point laying on a spline by evaluating it at a given knot value u with 0 <= u <= 1. If you iterate through the domain of a spline, for instance, like this:

for (int u = 0; u <= 1.0; u += 0.0001)
{
    ts_bspline_evaluate(&spline, u, &net);
}

you could draw the spline point by point. The smaller the incrementation of u is, the smoother your drawn spline gets.

Now, how do we extract a certain y-value for a given x-value? What we need is called the bisection method which, basically, is binary search in continuous space (which our domain is). To put it in an algorithm, you need something like this:

Input: x

u = 0.5 // <-- we start at the center of the domain
Point p;

do {
    p = evaluate(spline, u);
    if (p.x == x) break; // <-- '==' means close enough
    if (p.x < x) u = (0 + u)/2;
    if (p.x > x) u = (1+ u)/2;
} while (...) // we should set a fixed number of iterations

return p.y;

The idea is to interactively find the knot value u such that spline(u) (this is a shortcut for evaluation) returns the point p with p.x == x (x is the value you put into your function) and to return its corresponding y value.

Why is this working? Your input data is strictly monotonically increasing in x which means the interpolated spline must be a function like spline. That is, spline(u).x < spline(v).x with u < v. Thus, the algorithm described above must find our requested u in a finite number of steps.

not an interpolation of a one-dimensional function, which means it could potentially do things that a function can't, like loop round on itself.

If you sort your input values according to x and pass it to ts_bspline_interpolate_cubic, the interpolated spline will not have any loops or other things a regular function can't.

Unfortunately, TinySplien does not provide a ready to use function for the bisection method. However, a PR would be welcome :). I already thought about implementing this function but other things are more important yet.

I hope I could clear some things up.

[msteinbeck]

@tomwhoiscontrary, could I help you with your issue?

[msteinbeck]

I close this issue for now. Don't hesitate to reopen.

[tomwhoiscontrary]

Apologies for not replying sooner. I'm certainly happy for this to be closed!

I think the answer to my original question of "is there any way to interpolate values using a non-uniform spline with specific knots?" is "no", and the follow-up to that is the suggestion to treat one-dimensional functions as two-dimensional curves, which will work in practice.

Oh, and i think the generic name for a line/surface/etc is a "manifold", but i'm not a mathematician!