Постоянная скорость по кривой Безье

Question

Проблема, которую я пытаюсь решить, заключается в том, что я не могу перемещать 2D-точку вдоль кубической кривой Безье с постоянной скоростью.

Я следовал этому руководству: http://catlikecoding.com/unity/tutorials/curves-and-splines/ чтобы изначально реализовать кривую, и это сработало замечательно. Но при попытке приблизить точку с постоянной скоростью, это далеко, далеко.

Из того, что я прочитал до сих пор, вы должны выполнять итерацию по кривой, вычисляя длину дуги и интервальные расстояния на каждом шаге. Затем сравните эти расстояния с целевым расстоянием (длина дуги * время), чтобы найти ближайшее расстояние. При достаточно высоком разрешении это должно иметь небольшую ошибку и быть достаточно точным для моих нужд.

Вот код, который у меня есть до сих пор:

Расчет очков:

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

Грустная попытка расчета точки в постоянное время:

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

В приведенном выше коде я передаю время (u) между 0 и 1, чтобы вернуть время, которое можно использовать для оценки точки на кубической кривой Безье, которая представляет движение оси x с постоянной скоростью.

Результатом является следующее: Cubic Bezier Image

Красная точка представляет нормальную точку, которая возвращается, просто оценивая исходное время по формуле Безье. Желтая точка представляет "постоянную" позицию скорости после прохождения аппроксимированного времени. Это кажется довольно точным, пока я не начну изменять касательные, чтобы быть довольно преувеличенным. Я также пытался увеличить интервалы, и это ничего не помогает.

В любом случае, любая помощь была бы замечательной. Я пока не очень хорош в чтении формул (уверен, откуда проблема), поэтому было бы здорово получить некоторую помощь, используя примеры кода, пожалуйста.:>

Спасибо!

Answer 1

Хорошо, я, кажется, нашел ответ сам.

TLDR; Для 2D-кривой не используйте длину дуги для расчета целевого расстояния. Используйте только горизонтальную (ось X) длину.

БЫСТРОЕ ПРИМЕЧАНИЕ: Это решение, вероятно, не будет работать для вас, если ваши кривые могут идти назад вдоль оси х. Мой нет.

Чтобы уточнить, целевое расстояние, значение, используемое для аппроксимации того, где на моей кривой я должен смотреть, было произведением времени и длины дуги. Длина дуги была неточной, поскольку она учитывала расстояние по оси Y. Я забочусь только о горизонтальном перемещении, поэтому расстояние по оси у было ненужным.

Вот мой обновленный код:

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

Обратите внимание, что здесь есть два существенных изменения:

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

а также

int resolution = 25 * SelectedSpline.CurveCount;

Это второе изменение должно гарантировать, что разрешение не уменьшается при добавлении кривых. В противном случае вы можете заметить ошибку в точности возвращаемого времени. Я обнаружил, что интервал 25 на кривую был очень точным и очень быстрым. Тем не менее, есть несколько четких оптимизаций, которые нужно сделать в этом коде, но, если вы также не можете понять это, он должен работать для вас.

Вот скриншот результата. Желтая точка - это точка, которую я оцениваю, используя новое время. Зеленые точки представляют мои высокие и низкие точки.

ИЗОБРАЖЕНИЕ - Результирующий график - Постоянное время по кубической кривой Безье

Answer 2

Я не вижу явных ошибок в подходе, поэтому может помочь увеличение разрешения до 1000 или 10000.

Это не то, что вы просили, но, однако, чтобы сделать его более эффективным, в случае, если это часть высокопроизводительной игры с тонной графикой и жесткими требованиями к производительности.

a) Сохраните значения в таблице за один шаг, а затем получите доступ к ним на отдельном шаге, так что для этой кривой вам не нужно каждый раз пересчитывать 100(0(0)) точек

б) Вместо пошагового выбора значений используйте бинарный поиск или линейную оценку следующего предположения для правильного интервала

Также вы хотели бы написать это на C вместо Python, но ясно, что речь идет о Python.