Find the nearest control points either side of a Catmull Rom spline segment

Question

There is a formula for evaluating a Catmull Rom spline segment at time 't' found here.

The problem with this is that it requires finding the two control points either side of the segment to evaluate.

Is there a formula for finding those two control points?

As a alternative I considered utilising some kind of algrorithm for finding the nearest values either side of a given value:

float lowerNearest = float.MaxValue;
float upperNearest = float.MinValue;

int numElements = array.Length;

for (int i = 0; i < numElements; ++i)
{
    float dif = index - array[i].Index

    if (dif > 0)
    {
                     lowerNearest = Math.Min(lowerNearest, dif)
    }
    else
    {
         upperNearest = Math.Max(upperNearest, dif);
    }
}

However I'm not sure what values I should be comparing as the control points are only vectors and felt that it was probably the incorrect way to approach this problem.

Answer 1

Are you using this as a motion path? Assuming the points are ordered in the array you can just go in this order and keep track of which point is next/previous.

If you want to start at an arbitrary point then the question is a bit confusing - how do you define this point? I guess it is not just 'a point in space.' Is it defined like t? (0<=t<=1)

If so, you can try guessing with some sort of interpolation. Check out http://en.wikipedia.org/wiki/Nearest_neighbor_search for some hints.

Depending on the shape of the spline you could try nearest neighbour distance ratio - for example if t=0.5 then you take the middle points:

int index = Math.round(array.Length*0.5);

and take three other points around this one. Then you can try checking if one of these points is not closer to your point. If it is, use its neighbours for comparison, and so on.

If you know the approximate distance between points and it is roughly even, then you can use fixed radius nearest neighbour - query points until you find those within a tolerance and take the closest from these.

If the space is very big (lots of points) then you might be best off building a tree structure for faster search.

Hope this helps

Answer 2

How you choose the two outside control points depends entirely on what you want the spline to do and what you're trying to do with it. Those points affect how it curves, so you select them based on the curving behavior you want.

What Catmull-Rom splines are designed to do is create a smooth curve defined by an array of points. It passes through each point in the array in order and has no visual discontinuities as it does so. In this case the four control points are just four contiguous points in the array. E.g. one segment would use points 0, 1, 2, 3, the next segment would use 1, 2, 3, 4, etc.

If this is not your use case, it's possible a different kind of spline would be better suited for you, e.g. Hermite or Bézier.