О том, как можно вывести кривую Безье

Изменено: . Разместил: FadeDemon | Меню
Количество просмотров3`013 / FD1302-6-0

Началась эта история, вообще говоря довольно давно, ещё задолго до случайного обнаружения формулы интерполяции по косинусам, меня тогда заинтересовали методы решения одной довольно простой, на первый взгляд, задачи. Заключалась задача в следующем: нужно было получить некоторую функцию, позволяющую проводить кривые линии на плоскости по заданным точкам, таким образом, чтобы в точках они вели себя естественно, а если сказать точнее, то их нормали в этих точках должны вести себя примерно как векторные суммы нормалей прямых, проведенных к соседним точкам. Изначально это задумывалось как расширение физического движка одной моей игры, я хотел добавить возможность создавать модели физических объектов не только из прямых линий, но и из плавных кривых, так чтобы можно было бы, например, безболезненно сделать модель в форме эллипса. Но на самом деле меня больше интересовали сами алгоритмы построения подобных кривых.


Формула косинусной интерполяции не оправдала моих ожиданий, что впрочем неудивительно, если немножко вдуматься. Дело в том, что формула эта, хоть и добросовестно что-то там сглаживает, но делает это весьма специфическим образом: у функции, которую задаёт косинусная интерполяции, производные на её концах (то-есть при стремлении коэффициента к 0 или к 1) всегда обращаются в ноль, что можно фундаментально объяснить как следствие наличия во входных параметрах всего двух точек. Интерполируя всего две точки, функция как бы “не знает” как нужно себя вести на конце отрезка, у нее как бы выбора не остаётся, кроме как во всём подражать обычному косинусу. Косинус, короче, он такой косинус… Следствием всех этих сложностей является то, что при попытке провести наклонную линию через несколько точек, расположенных примерно на одной прямой, мы получим белиберду:


Cosine & Linear interpolations
Рис. №498. Cosine & Linear interpolations

Здесь у нас точки выстроены в некоторую такую поверхность, что-ли, которая, хотелось-бы чтобы была гладенькой. Красные линии как-бы подсказывают, куда должны идти наши сглаженные линии, но сами, поскольку образованы линейной интерполяцией, образуют углы, и превращают нашу гипотетическую гладкую плоскость в совокупность прямых отрезков. Но то что творит зелёный косинус… EPIC FAIL. Никаких мы гладких кривых косинусом не построим, каким бы местом его не повернём.


Желаемая форма кривой
Рис. №499. Желаемая форма кривой

Сначала мне думалось подсмотреть как устроены функции, к примеру кубической интерполяции, или чего-нибудь подобного (краем уха слышал ещё про кубические сплайны), мне казалось, что это если и не то что нужно, то вещи достаточно близкие к тому что мы хотим, и сидя на истории, я уже почти решил отложить размышления до прихода домой, но… Тут в мою голову закралась одна мысль. Сначала я нарисовал на бумажке 4 точки, A, B, C и D, расположенные как-бы зигзагом. Долго смотрел на них. Потом решил поставить ещё точку, назовём её тут B2, так, чтобы на точках AB2C построился бы некоторый треугольник, и точка B оказалась бы примерно в его центре. Затем разделив отрезок BB2 напополам, я поставил ещё одну точку, назвав её BT, и тут же поделил пополам отрезок ABT, родив тем самым ещё одну точку. Эта точка лежала в довольно интересном месте, неподалёку от отрезка AB, и не смотря на свою кажущуюся заурядность, приковывала мой взгляд… Тут в голове мелькнула ещё одна мысль: а что если отрезки поделить не пополам, а например в соотношении 2/3? И это стало искрой в бочке с порохом…


Вывод нашей кривой на бумажке
Рис. №500. Вывод нашей кривой на бумажке

Думаю, не надо быть прорицателем, чтобы понять, что при делении отрезков в разных отношениях, координаты нашей последней точки будут меняться по достаточно интересной закономерности, которая в итоге множество всех возможных точек превращает в плавные кривые, которые, кстати, мы можем заметить на иллюстрации выше, они там изображены зелёным цветом. С помощью такого приёма у нас получается что-то вроде парабол, можно даже доказать что это на самом деле кривые второго порядка (но это будет очевидно чуть дальше). Но у нас тут встаёт небольшая проблема: параболы получилось у нас две, и они между собой почти не связаны, их выпуклости вообще направлены в разные стороны, собственно это видно на картинке. А нам надо получить непрерывную, гладкую линию, без изломов там всяких… Впрочем оказалось, что тут нет ничего проще. Мы просто берём две точки на ближайших ветвях разных парабол, проводим между ними отрезок, и делим его в том же соотношении, в каком делили предыдущие отрезки чтобы получить эти две точки. И получаем третью точку. На рисунке она обозначена точкой X.


Впрочем, пока это малопонятные рассуждения, давайте запишем это как-то более строго. Для начала: а как нам собственно поделить отрезок в соотношении? Ответ сложности не представляет: это прекрасно может сделать небезызвестная уже линейная интерполяция, я даже доказал это на экзамене :). В дальнейших рассуждениях, мы только выражение (1 − k) заменим моей любимой буковкой ψ, и тогда формула линейной интерполяции примет более опрятный вид:

\[ \overline{Z}_{XY} = \overline{X}\psi + \overline{Y}k, \,\,\, \psi = (1 - k) \]
Вот так мы делим векторы


Правда прежде чем мы формулу эту будем использовать, надо вспомнить, что в самом начале мы строили какие-то там треугольники, и построить их тоже в более строгом виде. Я решил на этот счёт особенно не заморачиваться, и точки

\[ \hat{B} \]
и
\[ \hat{C} \]
найти с помощью обратных векторов медиан треугольников, построенных на имеющихся точках. А чтобы найти медиану, надо найти центр стороны, из которой она будет проведена. А как найти центр, вы в принципе уже можете догадаться… Поэтому, мы просто возьмём, и найдём:


\[ \begin{aligned} & \hat{B} = \overline{B} + \overline{B} - \left ({1 \over 2}\overline{A} + {1 \over 2}\overline{C} \right ) = 2\overline{B} - \left ({\overline{A} + \overline{C} \over 2}\right ) \\ & \hat{C} = \overline{C} + \overline{C} - \left ({1 \over 2}\overline{D} + {1 \over 2}\overline{B} \right ) = 2\overline{C} - \left ({\overline{D} + \overline{B} \over 2}\right ) \end{aligned} \]
Ищем дополнительные точки

Идейной сложности тут также нету, находим точку середины основания, находим вектор медианы, направленный к B или C, и с этими точками его складываем. Получаем точки где-то там, вверху, которые нам и нужны. Наглядно всё это видно на том рисунке выше. Это всё несомненно кажется скучным, но вот дальше становится интереснее.


Поскольку мы выбрали линейную интерполяцию для нашей задачи, то очевидно, что будущая наша функция будет работать примерно также, а именно, принимать некоторое количество точек, и коэффициент, равный чему-нибудь в промежутке от 0 до 1. Поскольку мы хотим построить линию из двух парабол, то целесообразно для наших расчётов брать только те ветви, которые друг друга перекрывают, то-есть средние на рисунке, остальные нас интересовать не будут. Думаем теперь, как будем считать первую параболу. Если идти сверху вниз, то при k = 0, BT очевидно будет равна B, как и XB, ну а для другой полу-параболы всё будет то-же самое, но только при k = 1. Переварив эти простые факты, мы получаем полное право записать что-то подобное:


\[ \begin{aligned} & \overline{B}_T = \overline{B}\psi + \hat{B}k & \overline{C}_T = \hat{C}\psi + \overline{C}k \,\,\,\, \\ & \overline{X}_B = \overline{B}_T\psi + \overline{C}k & \overline{X}_C = \overline{B}\psi + \overline{C}_T k \\ \end{aligned} \] \[ \overline{X} = \overline{X}_B \psi + \overline{X}_C k \]
Выражаем все основные точки

Здесь точка X, собственно говоря, является той самой точкой, ради которой весь балаган мы и затеяли. Кажется, мы здесь уже и получили наш алгоритм для рисования красивых кривых. Если мы достроим пятую точку E, и всё это повторим с её участием, исключив при этом точку A, то мы, очевидно, получим ещё один кусочек нашей кривой, который будет соединять уже точки C и D, то-есть, проблема рисования сколько угодно длинной и гладкой кривой по точкам полностью разрешается. Но теперь давайте-ка сорвём покровы.


Когда я получил все эти соотношения, мне как человеку близкому к математике захотелось получить какую-то более конкретную формулу, а не совокупность линейных интерполяций. Ну, сказано — сделано, берём мы точки, и подставляем:

\[ \begin{aligned} & \overline{X}_B = \left (\overline{B}\psi + \hat{B}k\right )\psi + \overline{C}k \,\,\,\,\,\,\, \overline{X}_C = \overline{B}\psi + \left (\hat{C}\psi + \overline{C}k\right )k \\ & \overline{X} = \left (\left (\overline{B}\psi + \hat{B}k\right )\psi + \overline{C}k\right )\psi + \left (\overline{B}\psi + \left (\hat{C}\psi + \overline{C}k\right )k\right )k \end{aligned} \]


Что-то скобочек получилось больно уж дохрена. Вам не кажется, что ψ и k целесообразно в эти самые скобки занести? Мне вот, именно так и показалось:

\[ \begin{aligned} & \overline{X} = \left (\left (\overline{B}\psi + \hat{B}k\right )\psi + \overline{C}k\right )\psi + \left (\overline{B}\psi + \left (\hat{C}\psi + \overline{C}k\right )k\right )k \\ & \overline{X} = \left (\overline{B}\psi + \hat{B}k\right )\psi^2 + \overline{C}k\psi + \overline{B}\psi k + \left (\hat{C}\psi + \overline{C}k\right )k^2 \\ & \overline{X} = \overline{B}\psi^3 + \hat{B}k\psi^2 + \overline{C}k\psi + \overline{B}\psi k + \hat{C}\psi k^2 + \overline{C}k^3 \end{aligned} \]


Хм. Мой задумчивый взгляд упал на последнюю формулу, и стал ещё более задумчивым. Я долго пытался вспомнить, где же я мог видеть подобные формулы… И тут всё стало ясно.


\[ \mathbf{B}(t) = (1-t)^3\mathbf{P}_0 + 3t(1-t)^2\mathbf{P}_1 + 3t^2(1-t)\mathbf{P}_2 + t^3\mathbf{P}_3, \quad t \in [0,1] \]
Кубическая кривая Безье. Спасибо Википедии.

Внезапно стало ясно, что свежевыведенная формула, оказывается, задаёт ни что иное, как кривую Безье 3-го порядка, то-есть кубическую. Правда если вглядеться повнимательнее, то формулы немного отличаются, но это и понятно, поскольку настоящие кривые Безье строятся несколько по другому, а именно, они не проходят по опорным точкам, а лишь отклоняются в их направлении. За подробностями — добро пожаловать в Википедию. Впрочем, Безье это или не Безье, нас мало интересует, нам больше хочется полученную кривую скорее уже нарисовать. Тут, кстати, самое время заметить, почему мы в самом начале обозвали составляющие нашей кривой параболами, вернее линиями второго порядка: максимальная степень во второй формуле выше очевидно не превышает 2. Обойдёмся без комментариев.


Но прежде чем перейти к рисованию, давайте ещё немножко подумаем над упрощением нашей формулы. В глаза бросается то, что, к примеру, точки B и A встречаются по 2 раза, а ещё кое-какие две точки имеют одинаковые сомножители в коэффициенте… Нехорошо, в общем. Возьмём-ка мы, и всё это упростим:

\[ \begin{aligned} & \overline{X} = \overline{B}\psi^3 + \hat{B}k\psi^2 + \overline{C}k\psi + \overline{B}\psi k + \hat{C}\psi k^2 + \overline{C}k^3 \\ & \overline{X} = \overline{B}\psi^3+ \overline{B}\psi k + \overline{C}k\psi + \overline{C}k^3 + \hat{B}k\psi^2 + \hat{C}\psi k^2 \\ & \overline{X} = \overline{B}\left (\psi^3 + \psi k\right ) + \overline{C}\left (\psi k + k^3\right ) + \psi k\left (\hat{B}\psi + \hat{C}k\right ) \end{aligned} \]


Учитывая, что уравнение у нас векторное, в такой форме считаться оно будет точно быстрее. Чтобы сразу понять, в каком порядке что здесь будет оптимальнее считать, мы сюда введём новые коэффициенты, обзовём их гамма-коэффициентами, и определим таким вот образом:

\[ \begin{aligned} & \gamma_3 = \psi k \\ & \gamma_1 = \gamma_3 + \psi^3 \\ & \gamma_2 = \gamma_3 + k^3 \end{aligned} \]


Ведь нетрудно подметить, что сладкая парочка входит в состав почти всех коэффициентов, соответственно, вычислять ее можно только один раз. Подставим теперь все эти буковки в нашу формулу, и получим довольно простое и лаконичное выражение:


\[ \begin{aligned} & \overline{X} = \gamma_1\overline{B} + \gamma_2\overline{C} + \gamma_3\left (\hat{B}\psi + \hat{C}k\right ) \end{aligned} \]
Что получилось в результате

Мы тут сейчас не будем приводить доказательства, но это я думаю очевидно, что количество операций в полученной формуле несколько меньше, чем в исходной, а чтобы понять, почему, давайте попробуем проанализировать количество арифметических операций в выражениях (a + b)c и ac + bc. То, что это тождества, думаю ясно всем, но не сразу может стать очевидным то, что в первом выражении у нас одна операция сложения, и одна умножения, а во втором — сложение одно, а умножения уже два, хотя результат абсолютно идентичен. Соответственно, чем больше мы выносим за скобки, тем быстрее наше выражение можно будет посчитать, и как раз именно для этого мы и придумали γ-коэффициенты…


Уфф… Ну ладно. На бумажке что-то нарисовали. Формулу получили. Упростили. Можно теперь и к программированию перейти. За основу возьмём мы программку, использованную для демонстрации косинусной интерполяции. Мы только её немножко обработаем напильником, и добавим туда вот такие 2 фрагмента кода:


Код: Delphi
//почти кривая Безье 3-й степени по 4 точкам
procedure bezier(const a, b, c, d:TPoint; k1:Single; out x:TFPoint);
var
  bt, ct : TFPoint;
  k2:Single;
  gamma1, gamma2, gamma3:Single;
begin

  k2 := 1 - k1;

  //сначала находим те самые треугольники
  bt.x := 2 * b.x - (c.x + a.x) / 2;
  bt.y := 2 * b.y - (c.y + a.y) / 2;

  ct.x := 2 * c.x - (b.x + d.x) / 2;
  ct.y := 2 * c.y - (b.y + d.y) / 2;

  //вычисляем точку на нашей кривой
  //считаем гамма-коэффициенты
  gamma3 := k1*k2;
  gamma1 := k2*k2*k2 + gamma3;
  gamma2 := k1*k1*k1 + gamma3;

  //считаем по третьей формуле
  x.x := b.x * gamma1 + c.x * gamma2 + (bt.x * k2 + ct.x * k1) * gamma3;
  x.y := b.y * gamma1 + c.y * gamma2 + (bt.y * k2 + ct.y * k1) * gamma3;

end;

Думаю, что такое векторные уравнения и как их раскрывать напоминать не надо, все мы это знаем, и наглядно видим в коде выше. В функцию рисования теперь добавим:


Код: Delphi
if(CheckBox3.Checked)then begin

    //рисуем почти кривую Безье
    Image1.Canvas.Pen.Color:=clOlive;
    Image1.Canvas.Font.Color:=clOlive;
    Image1.Canvas.TextOut(5, 145, '——— bezier');

    //идем по точкам
    for i:=0 to Length(interpol) - 4 do begin

      xl.X := interpol[i + 2].X - interpol[i + 1].X;
      xl.Y := interpol[i + 2].Y - interpol[i + 1].Y;

      //расстояние между двумя средними
      wzp := ceil(sqrt(xl.X*xl.X + xl.Y*xl.Y));

      Image1.Canvas.MoveTo(interpol[i + 1].X, interpol[i + 1].Y);

      for j := 1 to wzp do begin

        bezier(interpol[i], interpol[i + 1], interpol[i + 2], interpol[i + 3], j / wzp, oup);

        Image1.Canvas.LineTo(Round(oup.X), Round(oup.Y));

      end;
    end;
  end;

Вообще, в программе ещё предусмотрена возможность перетаскивания узлов, но код там весьма тривиальный и нам мало интересен. Впрочем, скоро будет возможность скачать весь код программы отдельным файликом, когда будет наконец реализована возможность их сюда загружать. После модификаций выше, программа стала уметь рисовать наши почти кривые Безье, и для примера в самом начале нарисовала нам следующее:


Linear & Bezier
Рис. №501. Linear & Bezier

Очень неплохо, на мой скромный взгляд. Прямо, то что нужно! Особенно, если сравнить это с косинусом:


Cosine VS Bezier
Рис. №502. Cosine VS Bezier

Разница, как говориться, на лицо. Правда потом обнаружилась другая особенность, а именно оказалось, что при определённых обстоятельствах, наша кривая неплохо приближает собой косинус:


Приближение косинуса
Рис. №503. Приближение косинуса

Хоть это и ничего не меняет, но появляется повод задуматься, почему так происходит… Отметить впрочем нужно другое, что я думаю заметно на картинках: дело в том, что для построения одного отрезочка кривой, нам нужно целых 4 точки, две слева и две справа, и поэтому, отрезки по краям массива точек мы строго говоря, построить не можем. Тут нужно прибегать к ухищрениям, и достраивать некие виртуальные точки, расположенные к примеру на одной прямой с двумя крайними имеющимися точками, но в программе это, естественно, не реализовано.


Заметим теперь, что полученная нами кривая даёт довольно богатые возможности по рисованию плавных линий. Попробуем, что-ли, привести несколько неуклюжих примеров:


Яйцо Безье
Рис. №504. Яйцо Безье

Спиралька
Рис. №505. Спиралька

Своеобразная восьмёрка
Рис. №506. Своеобразная восьмёрка

Мм-да, примеры действительно неуклюжие, хотя что ещё можно ожидать от программки, написанной за 30 минут… Впрочем, надо ещё заметить одну вещичку, формула кривой задаётся единственным уравнением, идентичным для x и для y составляющей входных координат, а отсюда следует, что формулу можно легко расширить к примеру на трёхмерное пространство, и с наслаждением рисовать себе кривые в объёмном мире. Также, функция скорее всего будет легко дифференцироваться по k, ибо является она функцией всего одной переменной, все точки то в ней — константы! А производная функции может дать нам такие вещи, как нормаль и касательную, которые в той же разработке физических движков могут очень пригодиться. Кстати, в трёхмерном пространстве, нормаль к нашей кривой судя по всему превратиться в плоскость, до чего на первый взгляд, нетрудно додуматься. Хотя, интереснее было бы всё-таки наглядно проверить это самим…


Напоследок ещё можно заметить, что у точек можно некоторым образом регулировать своеобразный “вес”, меняя расстояния между точками в треугольнике, то-есть умножая вектор медианы на какое-то число. Но, поскольку результатов исследований по этим пунктам у меня пока нету, это уже будет темой следующей статьи. Туда-же, кстати, войдёт исследование нашей кривой с помощью производных, и ещё одна довольно классическая задача: нахождение точки пересечения кривой и прямой, или двух кривых, примерно как мы уже где-то делали. Возможно ещё подумаем на тему приближения косинуса с помощью нашей кривой, поскольку сия мысль не покидает моей головы вот уже несколько часов. Так-же, на очереди небольшая практическая работа по нахождению корней n-ной степени методом Ньютона. Но всё это — в следующих статьях. Спасибо, что вы с нами, и до скорых встреч! :)

Ключевые слова математика, Программизм, движок, косинус, мысль, треугольник, вектор, кривые Безье, кривая, медиана, Delphi
QR-код
Интересное
Изобретаем свой киловольтметр Тема сегодняшней нашей лекции – датчик наличия высокого напряжения, работающий по принципу электрометра, такого приборчика, который на школьном курсе физике показывают.

Читать »»
Случайные фото