Методы построения кривых Безье

Министерство образования и  науки Российской Федерации

 

 

Допускаю к защите

Руководитель_________

____________________

Курсовая работа

по дисциплине Компьютерная геометрия и графика на тему «Методы  построения кривых Безье»

 

Выполнил студент:

 

Преподаватель:

 

 

^группа

 

 

^{подпись}

 

^{подпись}

 

 

^Ф.И.О.

 

^Ф.И.О.

Курсовой проект защищен

с оценкой______________

Иркутск, 2011

 

Оглавление

 

Введение

Кривые Безье были разработаны  независимо друг от друга двумя разными  французскими учеными: Пьером Безье и Полем де Кастелье в 60-х годах прошлого века. Оба ученых производили исследования в этом направлении в целях нахождения способа компьютерного проектирования автомобильных кузовов, так как оба на момент открытия работали в разных автомобильных компаниях (Пьер – в «Рено», Поль – в «Ситроен»).  При этом открытие Де Кастелье было сделано раньше (1959 г.), однако компания «Ситроен» долго это скрывала, в качестве производственной тайны. Поэтому, впервые представив, Кривые Безье в 1962 году, Пьер стал обладателем патента и увековечил свое имя в их названии [1].

 

Принцип построения кривых Безье

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

Кривая Безье строится с помощью, так называемых, контрольных точек. Из всех контрольных точек кривая, обычно, проходит лишь через две  – опорные или узловые точки. Остальные контрольные точки  не лежат на самой кривой, но их положение  определяет ее кривизну – кривая как бы «стремиться» пересечься с ними, но, выгибаясь дугой, так и не «дотягивается». Эти точки называются управляющими. Таким образом, кривая непрерывно заполняет отрезок между опорными точками, изгибаясь в направлении управляющих точек, поэтому изменение положения любой из контрольных точек меняет изгиб кривой.

Такой принцип построения позволяет интуитивно определять внешний вид кривой по положению контрольных точек, что позволяет реализовать интерактивность и наглядность при подборе кривой нужной формы, а это, в свою очередь, позволяет наиболее быстро, просто и относительно точно реализовать представляемую кривую. Кроме того, представление кривой в виде контрольных точек позволяет, при ее трансформации (изменения формы, масштаба или пересчета в другой системе координат), не преобразовывать кривую полностью, а лишь преобразовать контрольные точки, а затем построить по ним новую кривую. Это существенно уменьшает количество необходимых расчетов. Именно поэтому кривые Безье нашли широкое применение в системах автоматизированного проектирования, графических редакторах и других представлениях двумерной и трехмерной графики на компьютере, например, при представлении шрифтов формата TrueType [1][2].

Математически, построение кривой Безье  сводится к поиску таких функций для опорных точек , не зависящих от , и имеющих вид полиномов по , что кривая обладает основными свойствами кривой Безье, а именно:

1. Кривая проходит через две контрольные точки, которые являются ее началом и концом, т. е. .
2. Масштабирование и изменение пропорций кривой не нарушает ее стабильности, т. е. кривая не зависит от выбора декартовой системы координат в или, другими словами, она инвариантна относительно движений пространства («аффинно-инвариантна»).
3. Если все контрольные точки лежат в одной плоскости, то кривая плоская и всегда располагается внутри фигуры, образованной линиями, соединяющими эти точки.

Что равносильно следующему:

1. , для любой точки
2. , для любого
3. , для любого и , для любого

Нахождение таких функций и  реализуется в различных методах  построения [3].

Основные методы построения Кривых Безье

Существует несколько основных методов построения кривых  Безье. Каждый из них имеет свои преимущества и недостатки, а также удобен и  рационален при различных требованиях  к точности и сложности кривой. Но, кроме методов построения, существуют и разные виды кривых Безье (я не имею ввиду подразделение по степени полинома), для которых существуют свои способы построения. Так по информации, необходимой для построения, различают два вида кривых: «Обычные» - нерациональные и рациональные кривые Безье.

Методы построения нерациональных кривых Безье

    С использованием полиномов Бернштейна

Этот метод реализован в виде частного случая многочленов или полинома Бернштейна, при котором его коэффициенты – векторные. Упомянутый полином, был описан задолго до открытия самих кривых (в 1912 году) Российским ученым Сергеем Натановичем Бернштейном, при доказательстве аппроксимационной теоремы Вейерштрасса [4][5].

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

Задаются коэффициенты при равными коэффициентам бинома Ньютона . А из этого следует, что . Так как функции Бернштейна удовлетворяют рекуррентному соотношению , с его помощью можно вычислить соответствующие функции, например , , . Тогда, если дана контрольная точка , то кривая Безье, определяемая этими точками : . Степень полинома также называют степенью кривой Безье [3][5].

Преимущества построения кривой Безье  с использованием полиномов Бернштейна:

1. Кривая является полиномиальной, а следовательно, бесконечно гладкой по всей своей длине.
2. Построение не требует сложных вычислений. Полиномы Бернштейна зависят лишь от числа опорных точек, но не от их координат, поэтому кривая легко пересчитывается при любом изменении опорных точек.

Алгоритм Де Кастелье

Этот алгоритм построения кривых Безье был разработан их «первооткрывателем» Полем Де Кастелье, который, как я уже упоминал, придумал его в 1959 году, с целью применения в проектировании кузовов машин компании «Ситроен», в которой он тогда работал. В этом алгоритме, тоже используется базис Бернштейна, а также, выведенная в предыдущем методе, рекуррентная формула[6][5].

Подставим в базис Бернштейна рекуррентную формулу , выделив крайние точки и учитывая, что и , получим

 

где  , . Продолжив этот процесс разложения и , придем к равенствам . Обозначив через , а через , получим рекуррентное соотношение . Эта формула позволяет вычислить любую точку кривой Безье, следовательно саму кривую Безье можно определить, как линию, точки которой определяются этим уравнением. Вычисления по этому уравнению производятся по характеристическим точкам и не требуют подсчета функций Бернштейна. Величины и t единственным образом задают точку на кривой [5].

Стоит заметить, что с геометрической точки зрения, при реализации алгоритма Де Кастелье происходит разбиение отрезков ломаной линии, которую образуют контрольные точки, в заданном соотношении. Причем, полученные в результате разбиения точки, образуют новую ломаную, которая снова разбивается. Процесс повторяется до тех пор, пока ломаная не превратится в линию, тогда, разбив эту линию мы получим точку кривой Безье. Таким образом, меняя параметр , влияющий на соотношение разбиения отрезков ломаной, представленного как , мы можем получить все точки кривой [6].

Преимущества построения кривой Безье  по алгоритму Де Кастелье:

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

Построение рациональных кривых Безье

Рассмотренные выше способы построения кривой Безье, позволяют управлять  ее формой с помощью изменения  положения опорных точек, причем, чем больше этих точек, тем в большей степени мы можем управлять кривой. Но имея в качестве средств управления только опорные точки, иногда очень сложно построить кривые заданной формы. Поэтому был введено еще одно средство управления формой кривой – вес опорной точки. Влияние веса точки на форму кривой отличается от аналогичного влияния положения опорной точки. Так при смещении опорной точки все точки кривой передвигаются на разные величины в направлении смещения. При изменении веса опорной точки, точки кривой смещаются по направлению к этой точке, если вес увеличился или в противоположную сторону, если вес уменьшился [7].

Кривые Безье, в которых каждой опорной точке присвоен дополнительный параметр – ее вес, получили название рациональных. Способ построения рациональных кривых Безье основан на алгоритме Де Кастелье, но прежде, необходимо представить сам алгоритм в так называемой операторной форме или операторных обозначениях.

Для опорных точек  и параметра определим оператор правого сдвига , действующий на кривые вида , где - гладкие функции от . Тогда можно найти по формуле: . Аналогично, для кривых вида , определим оператор левого сдвига  по формуле: .

Тогда на множестве кривых, для  которых определен оператор или , имеем и . Тогда их степени и , где число повторений и .

Тогда, кривая Безье с опорными точками  , может быть задана в виде а также в виде .

В итоге, в операторных обозначениях, можем записать алгоритм Де Кастелье как , поскольку , т. е. если расписать:

Теперь для опорных точек  зададим веса , тогда , где а . Оператор действует одновременно и на сами точки и на их веса .

Согласно биному Ньютона рациональную кривую Безье можно представить в виде . В случае равных весов точек , знаменатель становится постоянным, а кривая превращается из рациональной в нерациональную кривую Безье [7].

Преимущества построения рациональной кривой Безье:

1. Рациональная кривая Безье способна точно (а не приблизительно) представлять собой дуги кривых второго порядка. Это бывает важно при проектировании деталей, в которых требуется, чтобы та или иная кривая в точности являлась дугой, например, эллипса, параболы или гиперболы (поскольку от этого зависят физические свойства той детали, в описании которой участвует данная кривая).
2. Как я уже упоминал, дополнительный параметр опорной точки – вес, позволяет добиться совершенно новых форм кривых, невозможных при использовании нерациональных кривых Безье с любым количеством опорных точек.

 

Построение рациональной и нерациональной кривых Безье в системе компьютерной алгебры Wolfram Mathematica 8.0

Чтобы наглядно убедиться в большей «гибкости» рациональных кривых Безье, по сравнению с нерациональными, я решил реализовать на практике программу по построению этих кривых в одной системе координат. При этом обеспечить возможность изменения положения опорных точек и изменения величины веса опорных точек рациональной кривой, посредством взаимодействия с графиком и интуитивно-понятными элементами интерфейса. Для большей наглядности, опорные точки у двух кривых будут общие.

В качестве средства реализации программы  я выбрал систему компьютерной алгебры Wolfram Mathematica 8.0, так как я уже ознакомился с седьмой версией этой системы во время занятий компьютерной геометрией и графикой в этом семестре и знаю, что в ней есть все необходимые функции для создания интерактивных графиков.

Несмотря на то, что координаты опорных точек будут меняться непосредственным взаимодействием  с графиком, считаю целесообразным задать некое их значение сразу, которое они примут при запуске программы. Это предотвратит появление всех точек в начале координат, а следовательно, сделает более наглядным влияние их положения на форму кривой уже при запуске программы.

Количество опорных точек, я  думаю, лучше будет установить достаточно, но не слишком, большим, например, равным восьми. Это предоставит возможность разнообразно изменять форму кривой, сделает ее боле гладкой, а также одновременно продемонстрирует, что, несмотря на большое количество опорных точек, «гибкость» нерациональной кривой значительно уступает таковой у рациональной кривой.

  Координаты восьми опорных точек задам с помощью массива «optochki0» :

optochki0={{-2,-5},{-7,15},{1,19},{24,-12},{-15,1},{-12,-3},{13,13},{3,-5}};

Так как я планирую создать именно интерактивный график, в котором  параметры координат опорных  точек и их веса будут меняться в реальном времени, всю программу я считаю нужным включить во встроенную функцию Dynamic[], которая будет обновлять график при малейшем изменении координат опорных точек или их веса.

Чтобы оставить возможность добавления контрольных точек в дальнейшем, я не задаю явно их количество, а определяю как количество элементов массива «optochki0», с помощью функции Length[]:

Dynamic[

n=Length[optochki0];

Функция Dynamic[], хоть и позволяет обновлять график при изменении параметров координат опорных точек или их веса, само это изменение не обеспечивает, поэтому, с этой целью, подключаем дополнительную функцию Manipulate[], которая позволяет интерактивно менять различные параметры, добавляя для этого специальные элементы контроля. Сразу включим в эту функцию параметры, которые мы будем менять – веса точек, в виде вектора текстовых названий  этого параметра для каждой точки: