Compute world position by walking N units along spline?

Question

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?

Answer 1

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));
 }

Answer 2

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++)
        Advance(_distance / 10.0);