# Compute world position by walking N units along spline?

My goal is to move ahead along a spline 'x' world units, unfortunately there is no way to map spline points to world points.

What I do is I iterate along the spline by a small alpha amount (say 0.001), get the new spline point vs the old one and add the difference to a total up until it equals or is slightly greater than the distance I wanted to move in world space.

This works fine but there is a huge bottleneck with the sqrt, basically to calculate the distance between two vector points you need to do a square root calculation.

I feel it should be possible to just get the squared value and just use that, unfortunately I can't get the code working, here is what I have:

Where _distance is the amount to move, Distance is the alpha value along the spline.

        float distanceMoved = 0;

float oldDistance = Distance;

while (distanceMoved < (_distance))
{
Vector3 before = Position;
float oldAlpha = Alpha;
float oldDist = Distance;
Distance += _iteration;

distanceMoved += (before - Position).magnitude;
}


Notice the line with (before - Position).magnitude, the .magnitude property performs a square root.

I've tried changing it to .sqarMagnitude and say distanceMoved < distance * distance but it has accelerated the rate of movement forwards.

Any ideas what is going wrong or how I can get rid of the square rooting or do this differently entirely?

• You know that 10 + 10 + 10 != Sqrt(10*10 + 10*10 + 10*10) ? – Kromster Mar 25 '14 at 4:28
• Yes, that is the problem I'm having? – meds Mar 25 '14 at 4:47
• This just explains why your "optimization" does not work as expected. – Kromster Mar 25 '14 at 5:11
• You should fix your variable names. If Distance is the alpha value, why not call it Alpha? And… what is Alpha, then? – sam hocevar Mar 27 '14 at 7:46

You shouldn't do a linear search!!! You should opt for a binary search in the first place. Secondly, you should have multiplied the desired distance by itself i.e. desired_distance_to_move * desired_distance_to_move than do a binary or (in case you care not of performance) a linear search for a point with a distance * distance > desired_distance^2 (and < [desired_distance^2 + 1]) if you are doing binary search).

How to do binary search in a situation like this:

a is the estimated step size.

t is the current position on the spline.

distance_2() is a function that returns the square distance without using root obviously

spline() gets you a position on the spline

old_pos = spline(t);
curr_dist_2 = distance_2(old_pos, spline(t + a));
step_size = a;

while (curr_dist_2 < desired_dist_2)
{
a += step_size;
step_size *= 2;
curr_dist_2 = distance_2(old_pos, spline(t + a));
}

while (curr_dist_2 > desired_dist_2 + 1 || curr_dist_2 < desired_dist_2)
{
step_size /= 2;
if (curr_dist_2 > desired_dist_2 + 1)
{
a -= step_size;
}
else
{
a += step_size;
}
curr_dist_2 = distance_2(old_pos, spline(t + a));
}


If the curvature of your spline is small enough, there is a method that will speed up things while remaining accurate. The idea is the same as developed in my answer to this question: if iterating by alpha makes you advance by distance, then iterating by K * alpha will make you advance by approximately K * distance as long as K is not too large.

Given your desired distance _distance, the function becomes as ridiculously short as this:

    float const d = 0.001;

Vector3 oldPosition = Position;

Distance += d;
Distance += d * (_distance / (oldPosition - Position).magnitude - 1.0);


Now of course if _distance becomes too large, the approximation no longer works well. You can fix this by doing a small, reasonable number of iterations instead:

    for (int i = 0; i < 10; i++)