Constant Speed Over Cubic Bezier Curve

Question

The problem that I'm trying to solve is that I can't seem to move a 2D point along a cubic bezier curve at a constant speed.

I followed this tutorial: http://catlikecoding.com/unity/tutorials/curves-and-splines/ to implement the curve initially and that has worked wonderfully. But when trying to approximate the point at a constant speed it's way, way off.

From what I've read so far, you're supposed to iterate over the curve, calculating the arc length and interval distances at each step time. Then, compare those distances to a target distance (arc length * time) to find the closest distance. With a high enough resolution, this should have little error and be accurate enough for my needs.

Here is the code that I have so far:

Point calculation:

public static Vector3 GetPoint (Vector3 p0, Vector3 p1, Vector3 p2, Vector3 p3, float t) 
{
    t = Mathf.Clamp01(t);
    float oneMinusT = 1f - t;
    return
        oneMinusT * oneMinusT * oneMinusT * p0 +
            3f * oneMinusT * oneMinusT * t * p1 +
            3f * oneMinusT * t * t * p2 +
            t * t * t * p3;
}

Sad attempt at calculating the point at a constant time:

private float GetApproximatedTime(float u)
{
    int resolution = 100;
    float ratio = 1.0f / resolution;
    float arcLength = 0.0f;
    Vector3 p0 = SelectedSpline.Evaluate(0.0f);
    List<MultiCurveUtility.ArcTimeLength> arcTimeLengthMap = new List<MultiCurveUtility.ArcTimeLength>();
    arcTimeLengthMap.Add(new MultiCurveUtility.ArcTimeLength(0.0f, 0.0f));

    for (int i = 1; i <= resolution; i++)
    {
        float t = ((float)i) * ratio;
        Vector3 p1 = SelectedSpline.Evaluate(t);
        arcLength += Vector3.Distance(p0, p1);
        arcTimeLengthMap.Add(new MultiCurveUtility.ArcTimeLength(t, arcLength));
        p0 = p1;
    }

    float target = u * arcLength;
    int low = 0;
    int high = 1;
    float min = 0.0f;
    float max = 0.0f;

    for (int i = 1; i < arcTimeLengthMap.Count; i++)
    {
        max = arcTimeLengthMap[i].ArcLength;
        if (target > min && target < max) 
        {
            high = i;
            low = i - 1;
            break; 
        }

        min = max;
    }

    float p = (target - min) / (max - min);
    float lowTime = arcTimeLengthMap[low].ArcTime;
    float highTime = arcTimeLengthMap[high].ArcTime;
    float lowHighDelta = highTime - lowTime;
    return arcTimeLengthMap[low].ArcTime + (lowHighDelta * p);
}

In the above code I'm passing in the time(u) between 0 and 1 in order to return a time that can be used to evaluate a point on the cubic bezier curve which represents x-axis movement at a constant rate.

The result is this: Cubic Bezier Image

The red dot represents the normal point that is returned by just evaluating the original time with the bezier formula. The yellow dot represents the 'constant' speed position after passing in time that has been approximated. It seems pretty accurate until I start changing the tangents to be fairly exaggerated. I've also tried increasing the intervals and that doesn't help anything.

Anyway, any help would be wonderful. I'm not terribly great at reading formulas yet (I'm sure where the issue is coming from), so it would be great to get some help using code examples please. :>

Thanks!

Answer 1

I don't see any glaring errors in the approach so increasing resolution to 1000 or 10000 can help.

This isn't what you asked, but however to make it more efficient, in case this is part of some high performance game with a ton of graphics in it and tough performance requirements

a) Store the values in a table in one step, then access them in a separate step so for that curve so you don't have to recompute 100(0(0)) points each time

b) Instead of stepping through the values, use a binary search or linearly estimate the next guess for the correct interval

Also you'd want to write it in C instead of Python but clearly this is about Python.

Answer 2

Alright, I seem to have found the answer myself.

TLDR; For a 2D curve, don't use arc length to calculate target distance. Only use horizontal (x-axis) length.

QUICK NOTE: This solution probably won't work for you if your curves can go backwards along the x-axis. Mine do not.

To elaborate, target distance, the value used to approximate where on my curve I should be looking, was a product of time and arc length. Arc length was inaccurate because it factored in the y-axis distance. I only care about horizontal movement, so the y distance was unnecessary.

Here is my updated code:

private float GetApproximatedTime(float u)
{
int resolution = 25 * SelectedSpline.CurveCount; // Factor in additional curves.
float ratio = 1.0f / resolution;
float arcLength = 0.0f;
Vector3 p0 = SelectedSpline.Evaluate(0.0f);
List<MultiCurveUtility.ArcTimeLength> arcTimeLengthMap = new List<MultiCurveUtility.ArcTimeLength>();
arcTimeLengthMap.Add(new MultiCurveUtility.ArcTimeLength(0.0f, 0.0f));

for (int i = 1; i <= resolution; i++)
{
    float t = ((float)i) * ratio;
    Vector3 p1 = SelectedSpline.Evaluate(t);
    arcLength += Mathf.Abs(p1.x - p0.x); // Only use the x-axis delta.
    arcTimeLengthMap.Add(new MultiCurveUtility.ArcTimeLength(t, arcLength));
    p0 = p1;
}

float target = u * arcLength;
int low = 0;
int high = 1;
float min = 0.0f;
float max = 0.0f;

for (int i = 1; i < arcTimeLengthMap.Count; i++)
{
    max = arcTimeLengthMap[i].ArcLength;
    if (target > min && target < max) 
    {
        high = i;
        low = i - 1;
        break; 
    }

    min = max;
}

float p = (target - min) / (max - min);
float lowTime = arcTimeLengthMap[low].ArcTime;
float highTime = arcTimeLengthMap[high].ArcTime;
float lowHighDelta = highTime - lowTime;
return arcTimeLengthMap[low].ArcTime + (lowHighDelta * p);
}

Notice that there are two significant changes here:

arcLength += Mathf.Abs(p1.x - p0.x);

and

int resolution = 25 * SelectedSpline.CurveCount;

That second change is to ensure that the resolution doesn't diminish when curves are added. Otherwise, you may notice error in the accuracy of the returned time. I found that an interval of 25 per curve was very accurate and very fast. That said, there are some clear optimizations to made in this code but, if you also couldn't figure this out, it should work for you.

Here is a screenshot of the result. The yellow dot is the point I evaluate using the new time. The green dots represent my high and low points.

IMAGE - Resulting Graph - Constant Time Over Cubic Bezier Curve