Алгоритмы компьютерной графики Пешков Анатолий Тимофеевич, БГУИР. 1 отображение просранства пользователя и машинного носителя 4

• Название: 1 отображение просранства пользователя и машинного носителя 4
• Дата: 24.09.2022
• Размер: 1.86 Mb.
• Имя файла: Алгоритмы компьютерной графики Пешков Анатолий Тимофеевич, БГУИР.doc
• Тип: Документы; #693275
• страница: 5 из 20

2.3 Кривые Безье.

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

Кривые Безье строятся на основании так называемого многочлена Безье.

Многочлен Безье задается в параметрической форме через параметр t. При этом связь параметра t с декартовыми координатами задается как:
x = P_x(t); y = P_y(t),

где параметр t изменяется в диапазоне

0<=t<=1.
Если заданы точки-ориентиры :
x₀,y₀; x₁,y₁;... x_i,y_i;.... x_m,y_m,
то многочлен Безье представляется в виде:


m

P_x(t)=C_mⁱtⁱ (1-t)^m-i x_i;

. i=0




. m

P_y(t)=C_mⁱtⁱ (1-t)^m-i y_i, . i=0


где 0 <= t <= 1;
В векторной форме многочлен Безье задается как:



Вынесем из под знака суммы слагаемые со значением i=0 и i=m, представив многочлен Безье в виде:


Если учесть, что 0=1, 0⁰=1 и С_m⁰ =С_m^m =1 ,то будем иметь:
 

Найдем значения для P при t=0 и t=1:

Подставив в полученное выражение значение t=1и t=0, получим:



Оценим поведение многочлен Безье в окрестностях точек t=0 и t=1. Для этого применим разложение функции f(x) в окрестности точки x=а в ряд Тейлора:
f(x)=f(a) + ((x-a)/(1f⁽¹⁾(a) + ((x-a)²/(2f⁽²⁾(a) + ...+
+ ((x-a)²/(2f⁽²⁾(a)+ R(x ⁿ⁺¹),

где:

• 
  f⁽ⁱ⁾(a) – i-ая производная функции f(x) в точке x=a;
  
• 
  R(x ⁿ⁺¹)- остаточный член, определяющий погрешность порядка n-ой степени x.
  

Для многочлен Безье в окрестности точки t = 0 будим иметь:
P(t=0) = P(0)+tP⁽¹⁾(0)+R(t²) P(0)+tP⁽¹⁾(0) (2.3-2)
(так как параметр t, оставаясь меньше единицы, стремится к нулю, достаточно остановиться на погрешности второго порядка).
P(t=1) = P(1)+(1-t)P⁽¹⁾(1)+R((1-t)²) P(1)+(1-t)P⁽¹⁾(1). (2.3-3)

Найдем общее выражение для производной многочлен Безье:




При t=0 имеем:



или:



При t=1 будем иметь:



или:



П олученные значения производных для значений t = 0 и t = 1 подставим в выражения (2.3-2), (2.3-3):

Из полученных выражений видно, что кривая Безье в окрестности точки t= 0 стремится к прямой P₀P₁, отличаясь от нее тем меньше, чем t ближе к 0, а в окрестности точки t =1 она стремится к прямой P_m-1P_m, отличаясь от нее тем меньше, чем t ближе к 1.

Выведем рекурсивные выражения для расчета функции, определяемой полиномом Безье.

Сначала выведем рекурсивное выражение для расчета С_mⁱ.

Покажем, что имеет место

Для этого выполним следующие преобразования правой часть доказываемого равенства:

В выражение (2.3-1) вместо С_mⁱ подставим С_m-1ⁱ +C_m-1^i-1.



Обозначим многочлен, построенный на m+1 точках

x₀,y₀; x₁,y₁;... x_i,y_i;.... x_m,y_m,
как P_0,m(t). Легко убедиться, что часть выражения (2.3-4), помеченная первой фигурной скобкой, представляет собой полином Безье P_0,m-1(t), построенный на m точках:
x₀,y₀; x₁,y₁;... x_i,y_i;.... x_m-1,y_m-1,
а часть выражения (2.3-4), помеченная второй фигурной скобкой, представляет собой полином Безье P_1,m(t), построенный на m точках:
x₁,y₁;... x_i,y_i;.... x_m,y_m,
В таком случае можно выразить многочлен Безье P_0,m(t), построенный на точках:

P₀, P₁, ….P_i,….. P_m-1, P_1,m,

через многочлен Безье P_0,m-1(t), построенный на точках

P₀, P₁, ….P_i,….. P_m-1,

и многочлен Безье P_1,m(t), построенный на точках

P₁, ….P_i,….. P_m-1, P_1,m

следующим образом:



Отсюда следует, что для определения значения полинома Безье P_0,m(t), заданного на точках-ориентирахP₀, P₁, ….P_i,….. P_m-1, P_1,m, для некоторого конкретного значения параметра t, можно использовать следующее правило:

1. 
   для заданного значения t (например, t=0.5) находится значение полинома Безье, заданного на точках-ориентирахP₀, P₁, ….P_i,….. P_m-1, P_1,m-1, и полинома Безье, заданного на точках-ориентирахP₁, ….P_i,….. P_m-1, P_1,m;
   
2. 
   определяется отрезок, соединяющий найденные точки;
   
3. 
   в качестве значения полинома Безье P_0,m(t), заданного на точках-ориентирахP₀, P₁, …P_i,….. P_m-1, P_1,mберется точка, соответствующая середине найденного отрезка.
   

В качестве итерационного алгоритма формирования значения полинома Безье для текущего значения t можно использовать следующий алгоритм.

На каждой итерации рассчитываются точки, расположенные на i-ой части отрезков, соединяющего две соседние точки-ориентиры, полученные на предыдущей итерации. Эти рассчитанные точки берутся как точки ориентиры для следующей итерации. Если после очередной итерации будет получена одна точка-ориентир, то эта точка и есть искомая точка, определяемая полиномом Безье для заданного значения t.

Граф–схема такого алгоритма приведена на .

На Error: Reference source not found приведены примеры расчета значения полинома Безье для разного количества точек-ориентиров и разных значений параметра t.

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

Содержательно многочлен Безье можно представить в виде модели, в которой используется эластичная магнитная нить, закрепленная в точках P₀ и P_n, расположенная в магнитном поле, создаваемом одинаковыми магнитами, помещенными в точках P₀, P₁,…, P_m-1.

Для того чтобы обеспечивать большее «притяжение» к какой-либо точке-ориентиру, можно использовать механизм кратных точек (удвоение, утроение и т.д.), в соответствующее количество раз увеличивающий напряженность поля, создаваемого в этой точке. Этот механизм иллюстрируется Рис. Формирование дуги окружности.-13.

На рисунке механизм кратных точек используется для точек-ориентиров P₁, P₂, которые берутся с одинаковыми координатами X, Y. Поэтому при рассмотрении полинома, определенными точками-ориентирами P₁, P₂, в качестве его значения для любой заданной величины параметра t выбирается точка, соответствующая P₁ (или, что то же самое P₂). Поэтому на приведенном рисунке промежуточная точка-ориентир совпадает с начальными точками-ориентирами P₁, P₂.


Рис. Кривые Безье.‑15




Рис. Кривые Безье.‑16


Рис. Кривые Безье.‑17