algorithm - 创建三次和/或二次贝塞尔曲线以适应路径

Question

我正在用 Lua 开发一款 2D 游戏。我有一条由多个点组成的路径，例如，点 A 到 L:

我想沿着这条路径平滑地移动一个物体。为此，我想根据这些点创建二次或三次贝塞尔曲线，并对这些曲线进行插值。但是，我如何正确地拟合曲线，这样路径就不会被破坏，例如。一条曲线在 F 点停止，另一条曲线从点 F 开始？

Answer 1

曲线拟合在这个问题中有解释:How can I fit a Bézier curve to a set of data?

但是，必须有一种更简单的方法来插值点。它是这样的:

1. 优化:在每条边的中间放置一个点。
2. 对偶:在每条边的中间放置一个点并移除旧点。
3. 重复双重步骤几次。
4. 从第一步开始重复，直到曲线足够平滑。

您可以很容易地看出它在纸上是可行的。生成的曲线开始近似于一系列贝塞尔样条曲线。

在这个 PDF 文件(第 3 部分)中有更正式的描述:http://www.cc.gatech.edu/~jarek/courses/handouts/curves.pdf

这里有一些 Javascript 代码可以做到这一点:

function bspline_smooth(points, order) {

    // insert a point in the middle of each edge.
    function _refine(points) {
      var i, index, len, point, refined;
      points = [points[0]].concat(points).concat(points[points.length-1]);
      refined = [];
      index = 0;
      for (i = 0, len = points.length; i < len; i++) {
        point = points[i];
        refined[index * 2] = point;
        if (points[index + 1]) {
          refined[index * 2 + 1] = _mid(point, points[index + 1]);
        }
        index += 1;
      }
      return refined;
    }

    // insert point in the middle of each edge and remove the old points.
    function _dual(points) {
      var dualed, i, index, len, point;
      dualed = [];
      index = 0;
      for (i = 0, len = points.length; i < len; i++) {
        point = points[i];
        if (points[index + 1]) {
          dualed[index] = _mid(point, points[index + 1]);
        }
        index += 1;
      }
      return dualed;
    }

    function _mid(a, b) {
      return new Point(
        a.x + ((b.x - a.x) / 2),
        a.y + ((b.y - a.y) / 2) );
    }

    if (!order) {
       return points;
    }
    return bspline_smooth(_dual(_dual(_refine(points))), order - 1);
}