Кривые XNA CatmullRom

Question

Мне нужно некоторое разъяснение по технике, которую я пытаюсь. Я пытаюсь переместить сущность из точки A в точку B, но я не хочу, чтобы сущность путешествовала по прямой.

Например, если объект помещен в x: 0, y: 0, и я хочу перейти к точке x: 50, y: 0, я хочу, чтобы объект перемещался по кривой цели, я бы представил максимальное расстояние, на котором оно было, равно x: 25 y: 25, поэтому он перемещается по X к цели, но отодвинулся от цели на y.

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

Если есть какие-либо альтернативные методы, которые могут быть проще, чем я пропустил, я был бы рад услышать их.

Edit:

Чтобы показать, как я получаю кривую:

Vector2 blah = Vector2.CatmullRom(
    StartPosition, 
    new Vector2(StartPosition.X + 5, StartPosition.Y + 5), 
    new Vector2(StartPosition.X + 10, StartPosition.Y + 5), 
    /*This is the end position*/ 
    new Vector2(StartPosition.X + 15, StartPosition.Y), 0.25f); 

Идея в конце концов, я генерировать эти точки на лету, но я просто пытаюсь работать его на момент.

Answer 1

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

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

Учитывая набор точек и общее расстояние для перемещения по пути, определяемому как линии между этими точками, следующий (более или менее псевдо) код найдет точку, которая находится на определенном расстоянии по пути:

Point2D WalkPath(Point2D[] path, double distance) 
{ 
    Point curr = path[0]; 
    for (int i = 1; i < path.Length; ++i) 
    { 
     double dist = Distance(curr, path[i]); 
     if (dist < distance) 
      return Interpolate(curr, path[i], distance/dist; 

     distance -= dist; 
     curr = path[i]; 
    } 
    return curr; 
} 

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

Редактировать:Here's an example, что я сделал с этим методом в JavaScript некоторое время назад. Это понятие доказательства правильности, так что не выглядит слишком критически код: P

Edit: больше информации о генерации сплайна
Учитывая набор «узел» указывает - являются точки, что кривая должна проходят в последовательности - наиболее очевидным подходом для алгоритма кривой является Catmull-Rom. Недостатком является то, что C-R нуждается в двух дополнительных контрольных точках, которые могут быть неудобно генерировать автоматически.

Некоторое время назад я нашел довольно полезную статью в Интернете (которую я больше не могу найти, чтобы дать правильную атрибуцию), которая рассчитала набор контрольных точек на основе местоположения наборов точек в вашем пути.Вот мой C# код для метода, который вычисляет контрольные точки:

// Calculate control points for Point 'p1' using neighbour points 
public static Point2D[] GetControlsPoints(Point2D p0, Point2D p1, Point2D p2, double tension = 0.5) 
{ 
    // get length of lines [p0-p1] and [p1-p2] 
    double d01 = Distance(p0, p1); 
    double d12 = Distance(p1, p2); 
    // calculate scaling factors as fractions of total 
    double sa = tension * d01/(d01 + d12); 
    double sb = tension * d12/(d01 + d12); 
    // left control point 
    double c1x = p1.X - sa * (p2.X - p0.X); 
    double c1y = p1.Y - sa * (p2.Y - p0.Y); 
    // right control point 
    double c2x = p1.X + sb * (p2.X - p0.X); 
    double c2y = p1.Y + sb * (p2.Y - p0.Y); 
    // return control points 
    return new Point2D[] { new Point2D(c1x, c1y), new Point2D(c2x, c2y) }; 
} 

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

Учитывая набор узлов «N» (точки на кривой), мы можем создать набор контрольных точек, которые будут использоваться для построения кривых между парами узлов:

// Generate all control points for a set of knots 
public static List<Point2D> GenerateControlPoints(List<Point2D> knots) 
{ 
    if (knots == null || knots.Count < 3) 
     return null; 
    List<Point2D> res = new List<Point2D>(); 
    // First control point is same as first knot 
    res.Add(knots.First()); 
    // generate control point pairs for each non-end knot 
    for (int i = 1; i < knots.Count - 1; ++i) 
    { 
     Point2D[] cps = GetControlsPoints(knots[i - 1], knots[i], knots[i+1]); 
     res.AddRange(cps); 
    } 
    // Last control points is same as last knot 
    res.Add(knots.Last()); 
    return res; 
} 

Итак, теперь вы имеют массив из 2*(n-1) контрольных точек, которые затем можно использовать для генерации реальных сегментов кривой между узлами.

public static Point2D LinearInterp(Point2D p0, Point2D p1, double fraction) 
{ 
    double ix = p0.X + (p1.X - p0.X) * fraction; 
    double iy = p0.Y + (p1.Y - p0.Y) * fraction; 
    return new Point2D(ix, iy); 
} 

public static Point2D BezierInterp(Point2D p0, Point2D p1, Point2D c0, Point2D c1, double fraction) 
{ 
    // calculate first-derivative, lines containing end-points for 2nd derivative 
    var t00 = LinearInterp(p0, c0, fraction); 
    var t01 = LinearInterp(c0, c1, fraction); 
    var t02 = LinearInterp(c1, p1, fraction); 
    // calculate second-derivate, line tangent to curve 
    var t10 = LinearInterp(t00, t01, fraction); 
    var t11 = LinearInterp(t01, t02, fraction); 
    // return third-derivate, point on curve 
    return LinearInterp(t10, t11, fraction); 
} 

// generate multiple points per curve segment for entire path 
public static List<Point2D> GenerateCurvePoints(List<Point2D> knots, List<Point2D> controls) 
{ 
    List<Point2D> res = new List<Point2D>(); 
    // start curve at first knot 
    res.Add(knots[0]); 
    // process each curve segment 
    for (int i = 0; i < knots.Count - 1; ++i) 
    { 
     // get knot points for this curve segment 
     Point2D p0 = knots[i]; 
     Point2D p1 = knots[i + 1]; 
     // get control points for this curve segment 
     Point2D c0 = controls[i * 2]; 
     Point2D c1 = controls[i * 2 + 1]; 
     // calculate 20 points along curve segment 
     int steps = 20; 
     for (int s = 1; s < steps; ++s) 
     { 
      double fraction = (double)s/steps; 
      res.Add(BezierInterp(p0, p1, c0, c1, fraction)); 
     } 
    } 
    return res; 
} 

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

Заголовок вашего мобильного телефона в любой точке пути (примерно) - угол между точками с обеих сторон. Для любой точки n на пути угол между p[n-1] и p[n+1] является углом заголовка.

// get angle (in Radians) from p0 to p1 
public static double AngleBetween(Point2D p0, Point2D p1) 
{ 
    return Math.Atan2(p1.X - p0.X, p1.Y - p0.Y); 
} 

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

Сообщите мне, как это. Если у вас возникнут какие-либо особые трудности, я посмотрю, что я могу сделать, чтобы помочь.