Далее мы изучим другую параметрическую многочеленную кривую, кривую Бе­зье. Так как они обе используют полиномы для их координатных функций, степенная базисная и Безье формы математически эквивалентны; т.е. любая кривая, которая мо­жет быть представлена в одной, также может быть представлена в другой форме. Тем не менее, метод Безье превосходит степенную базисную форму для геометри­че­ского моделирования. Наша презентация кривых Безье, будет неформальной; для более стро­го­го и полного ознакомления читатель должен ознакомится с другой литературой [Forr72; Bezi72, Bezi86; Gord74a; Chan81; Fari93; Yama88; Hosc93; Roge90].

Степенная базисная форма имеет следующие недостатки:

• это неестественно для интерактивной разработки фигуры; коэффициенты `{a_i}` сообщают очень мало геометрического представления о форме кривой. Кроме того, разработчик, как правило, хочет, задавать граничные условия на обоих концах кривой, а не только в начальной точке;
• алгоритмы вычисления степенных базисных полиномов имеют алгебраическое, а не геометрическое выражение (например, метод Горнера);
• численно, это довольно плохая функция; например, метод Гомера склонен к ошибкам округления, если коэффициенты сильно различаются по величине.

Метод Безье исправляет эти недостатки.

Кривая Безье `n`-ой степени определяется так

`C(u)=sum_(i=0)^n B_{i,n}(u)P_i`   `0<=u<=1` (1.7)

Базисная (смешивающая) функция, `{B_(i,n) (u)}`, это классический Многочлен Бернштейна n-ой степени (Bern12; Lore86) заданный так

`B_{i,n}(u)={n!}/{i!(n-1)!}u^i(1-u)^{n-1}` (1.8)

Геометрические коэффициенты этой функции, `{P_i}`, называются контрольными точками. Обратите внимание, что в определении уравнения (1.7), требуется, чтобы `u∈[0,1]`.

Примеры

В дополнение к ранее упомянутым свойствам, кривые Безье инвариантны при обычных преобразованиях, таких как поворот, перемещение и масштабирование; то есть, преобразование применяется к кривой, путём применения к управляющему полигону. Мы рассмотрим эту концепцию, более подробно в Главе III для B-сплайнов (частным случаем которых, являются кривые Безье).

В любой схеме представления кривой (или поверхности) , выбор базисных функ­ций определяет геометрические характеристики схемы. На рис 1.13а-г показаны базис­ные функции `{B_(i,n) (u)}` для `n=1,2,3,9`. Эти функции имеют следующие свойства:

Свойство 1.6 дает простые алгоритмы для вычисления значений многочленов Бернштейна при фиксированных значениях `u`. Алгоритм А1.2 вычисляет значение `B_{i,n}(u)` для фиксированного `u`. Вычисление `B_{1,3}` представлено в Таблице 1.1.

Алгоритм А1.2

Bernstein(i,n,u,B)
{ /* Вычисление значения многочлена Бернштейна */
  /* Вход: i,n,u  */
  /* Выход: B */
for (j=0; j<=n; j++) /* вычисление колонок */
   temp[j] = 0.0; /* Таблицы 1.1 */
temp[n-i] = 0.0; /* во временный массив */
u1 = 1.0 – u;
for (k=0; k<=n; k++)
   for (j=0; j>=k; j++)
      temp[j] = u1*temp[j] + u*temp[j-1];
B = temp[n];
}
  

Алгоритм А1.3 вычисляет `n-1` многочлена Бернштейна `n`ой степени с ненуле­вым фиксированным `u`. Это позволяет избежать ненужных вычислений нулевых условий. Алгоритм изображен в таблице 1.2 для кубического случая.

Алгоритм А1.3

AllBernstein(n,u,B)
{ /* Вычисление всех многочленов Бернштейна n-ой степени */
/* Вход: n,u  */
/* Выход: B (массив, B[0], …, B[n]) */
B[0] = 1.0;
u1 = 1.0 – u;
for (j=1; j<=n; j++)
   {
   saved = 0.0;
   for (k=0; k<j; k++)
      {
      Temp = B[k];
      B[k] = saved + u1* temp;
      saved = u*temp;
      }
   B[j] = saved
   }
}
    

Алгоритм А1.4 комбинирует А1.3 и уравнение (1.7) вычисляет точку на кривой Безье `n`ой степени с фиксированным значением `u`.

Алгоритм А1.4

PointOnBezierCurve(P,n,u,C)
{ /* Вычисление точку на кривой Безье */
  /* Вход: P,n,u  */
  /* Выход: C (точка) */
AllBernstein(n,u,B)  /* B локальный массив */
C = 0.0;
for (k=0; k<=n; k++)
   C = C + B[k]*P[k];
}
  

Используя свойство 1.7, легко вывести общее выражение производных кривой Безье

`C'(u)={d(sum_{i=0}^n B_{i,n}(u)P_i)}/{du}=sum_{i=0}^nB'_{i,n}(u)P_i`

`=sum_{i=0}^n n(B_{i-1,n-1}(u)-B_{i,n-1}(u))P_i`

`=nsum_{i=0}^{n-1}B_{i,n-1}(u)(P_{i+1}-P_i)` (1.9)

Из уравнения (1.9) легко получить формулы для конечных производных кривой Безье, например

`C'(0)=n(P_1-P_0)`   `C''(0)=n(n-1)(P_0-2P_1+P_2)`

`C'(1)=n(P_n-P_{n-1})`   `C''(1)=n(n-1)(P_n-2P_{n-1}+P_{n-2})` (1.10)

Обратите внимание, из уравнений (1.9) и (1.0) следует, что

• производные кривой Безье `n`ой степени является кривая Безье `(n-1)`-ой степени;
• выражения для конечных производных в `u=0` и `u=1` симметричны (из-за, конечно, симметрии базисных функций);
• `k`-ая производная в конечной точке зависит (в геометрически очень интуитив­ным способом) исключительно от `k+1` контрольных точек на том конце.

Пусть `n=2` и `C(u)=sum_{i=0}^2B_{i,2}(u)P_i`. Тогда

`C(u)=(1-u)^2 P_0+2u(1-u)P_1+u^2 P_2`

`=(1-u)"("ubrace((1-u)P_0+uP_1)_("линеный")")"+u"("ubrace((1-u)P_1+uP_2)_("линеный")")"`

Таким образом, `C(u)` получают в виде линейной интерполяции двух кривых Безье первой степени; В частности, любая точка на `C(u)` получается три линейной интерпо­ляции.

Если предположить, что `u=u_0` фиксированно и дать `P_{1,0}=(1-u_0)P_0+u_0 P_1`, `P_{1,1}=(1-u_0)P_1+u_0 P_2`, и `P_{2,0}=(1-u_0)P_{1,0}+u_0 P_{1,1}`, следует что `C(u_0)=P_{2,0}`. Ситуация показана на рис 1.16, и кубический случай показан на рис 1.17.

Обозначая общую кривую Безье `n`-ой степени как `C_n(P_0,...,P_n)`, мы имеем

`C_n(P_0,...,P_n)=(1-u)C_{n-1}(P_0,...,P_{n-1})+uC_{n-1}(P_0,...,P_n)` (1.11)

Это следует из рекурсивного определения базисных функций (смотри свойство 1.6). Фиксированное `u=u_0` и обозначая `P_i` как `P_{0,i}`, уравнение (1.11) дает рекурсив­ный алгоритм для вычисления `C(u_0)=P_{n,0}(u_0)` на кривой Безье `n`-ой степени, т.е.

`P_{k,i}(u_0)=(1-u_0)P_{k-1,i}(u_0)+u_0P_{k-1,i+1}(u_0 )`   где `{(k=(1,...,n)),(i=(0,...,n-k)):}`(1.12)

Уравнение (1.12) называются Алгоритм де Кастельжо. Это процесс отрезания углов (смотри рис 1.16 и 1.17) который даёт треугольную таблицу точек показаную в Таблице 1.3.

Алгоритм А1.5

deCasteljau1(P,n,u,C)
{ /* Вычисление точку на кривой Безье */
  /* Алгоритм де Кастельжо */
  /* Вход: P,n,u  */
  /* Выход: C (точка) */
for (i=0; i<=n; i++)  /* Используя локальный массив таким образом, мы не */
   Q[i] = P[i];       /* разрушаем контрольные точки */
for (k=0; k<=n; k++)
   for (i=0; i<=n-k; i++)
      Q[i] = (1.0 - u)*Q[i] + u*Q[i + 1];
C = Q[0];
}
    

Мы закончим этот параграф сравнением Безье и степенных базисных методов. Очевидно, что формула Безье является более геометрической из двух. Уравнение (1.10), а с выпуклой оболочкой и свойствами осцилляции делает кривые Безье более подходящими для интерактивного дизайна кривой. Контрольные точки дают разработ­чику более интуитивные ручки для формы кривой, чем коэффициенты степенных бази­сов. Кроме того, алгоритм де Кастельжо менее склонен к ошибкам округления, чем алгоритм Горнера. Это интуитивно понятно, если учесть, что алгоритм де Кастельжо просто повторяют линейную интерполяцию между точками, в каждом из которых лежат в непосредственной близости от кривой. Единственный недостаток формулы Безье является то, что оценка точки является менее эффективным (см Алгоритмы A1.1, A1.4, и A1.5, и Упражнение 1.13 позже в этой главе).