1
\$\begingroup\$

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?

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

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));
 }
\$\endgroup\$
1
\$\begingroup\$

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);
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.