XNA CatmullRom Curves

Question

我需要澄清我正在尝试的一种技术。我试图将一个实体从A点移动到B点，但我不希望实体沿直线移动。

例如，如果实体位于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。缺点是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类，它内置了很多功能-点算术、插值等。我可能在翻译过程中添加了一些错误，但希望当你玩它时，它们会很容易发现。

让我知道进展如何。如果你遇到任何特别的困难，我会看看我能做些什么来帮助你。