Creating continuous splines / Making a smooth transition between splines

Question

I'm working on a project that involves creating a spline from a defined set of points (tens of thousands of points).

I first create a spline for the first 1000 points and simulate "driving" on that path with an arrow (it is drawn using the tangent and the current point on spline). When I'm approaching the end of the path I take the next 1000 points and create a new spline and continue my "driving".

The problem that I have is the fact that the splines (previous spline and current spline) don't match at the end. By not matching I mean they don't have the same tangent (first derivative doesn't match) and there is a difference between the last point of the previous spline and first point on the new spline (this is because I'm not using an interpolating spline but a smooth spline - see NOTE1 below). This makes my arrow "jump" at the end of spline, when switching to the newly created spline.

NOTE1: I'm NOT using interpolating splines. I'm using smooth splines. See here and here for more details. This means that the set of points given as input may not be on the resulting spline (In my case they are quite close to the spline - but usually NOT on the spline).

NOTE2: Using an interpolating spline is out of the question because I have a lot of noise in the data used for computing spline.

NOTE3: Computing a spline for the entire set of points takes a lot of time (more than 30 seconds) on a 3Ghz PC with 2 GB RAM (our target platform for the application); so doing this is also out of the question.

I'd be interested to overcome that unwanted "jump" when switching splines.

So my questions are:

• Are there some ways/algorithms for doing a smooth "jump"/transition to the new spline?
• Can I do something with a special type of spline to overcome this? (This is what I tried so far without a considerable improvement).

Thank you for any ideas,

Iulian

Answer 1

This is a pretty unsophisticated suggestion, admittedly, but one obvious hack would be to fit overlapping rather than distinct subsets of points and then interpolate between the resulting splines in the overlapping region.

Eg, generate a smooth spline for points 1-1000. While you're animating from 1-900, generate the next spline from 901-1900. For the region between 901 and 1000, use a weighted combination of the corresponding positions in both splines, where the weighting is 1:0 at 901 and 0:1 at 1000. The same for 1801-1900 and so on.

I'd guess that a simple linear interpolation would suffice and the margins probably wouldn't need to be huge, but you could determine that empirically.