Кривые XNA CatmullRom

Question

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

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

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

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

Редактировать:

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

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

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

Изменить: Вот пример, который я сделал с этим методом в JavaScript некоторое время назад. Это подтверждение концепции, так что не смотрите слишком критично на код:P

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

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

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