Постоянная скорость над кубической кривой Безье

Question

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

Я следовал этому руководству: 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, чтобы вернуть время, которое может быть использовано для оценки точки на кривой кубического безье, которая представляет движение оси х с постоянной скоростью.

В результате этого: Cubic Bezier Image

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

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

Спасибо!

Answer 1

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

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

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

Чтобы уточнить расстояние до цели, значение, используемое для приближения, где на моей кривой я должен смотреть, было продуктом времени и длины дуги. Длина дуги была неточной, поскольку она учитывалась на расстоянии по оси Y. Я только забочусь о горизонтальном движении, поэтому расстояние 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 на кривую был очень точным и очень быстрым. Тем не менее, в этом коде есть четкая оптимизация, но если вы также не можете понять это, это должно сработать для вас.

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

IMAGE - Resulting Graph - Constant Time Over Cubic Bezier Curve

Answer 2

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

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

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

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

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