Создание кубических и / или квадратичных кривых Безье для соответствия пути

Question

Я работаю над 2D-игрой в Lua. У меня есть путь, который состоит из нескольких точек, например, точек от А до L:

Я хочу плавно перемещать объект по этому пути. Чтобы достичь этого, я хотел создать квадратные или кубические кривые Безье на основе точек и интерполировать эти кривые. Тем не менее, как мне правильно подобрать кривые, чтобы путь не нарушался, если, например. кривая останавливается, а другая начинается в точке F?

Answer 1

Подгонка кривой объясняется в этом вопросе: Как я могу подогнать кривую Безье к набору данных?

Тем не менее, существует обязательный способ интерполировать точки. Это идет по этому пути:

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

Answer 2

Вам не нужно знать математику, чтобы сделать это.

Соедините каждую точку со следующей точкой с помощью отдельной кривой Безье.

Кривые Безье имеют "ручки", прикрепленные к их конечным точкам. Эти маркеры касаются кривой (в конечных точках). Чтобы сделать "гладкий" путь, все, что вам нужно сделать, это сделать так, чтобы маркеры каждых двух смежных кривых Безье "сидели" на одной линии.

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

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

Наконец, что касается перемещения точки (вашего "объекта") вдоль кривой с, казалось бы, постоянной скоростью: вы можете использовать адаптацию такого метода, как этот.