c# - XNA CatmullRom 曲线

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

您可以进行各种优化来加快速度，例如存储路径中每个点的路径距离，以便在步行操作期间更容易查找。随着您的路径变得越来越复杂，这一点变得更加重要，但对于只有几段的路径来说可能有点矫枉过正。

编辑: Here's an example前段时间我在 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 类，它有很多内置的功能——点算术、插值等。我可能在翻译过程中添加了一些错误，但希望当您使用它时，它们很容易被发现。

让我知道进展如何。如果您遇到任何特别的困难，我会尽力帮助您。