Глава I
1.4. Рациональные кривые Безье

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

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

`x(u)=a_0+a_1 u+⋯+a_n u^n`

`y(u)=b_0+b_1 u+⋯+b_n u^n`

Тогда `x^2+y^2-1=0` означает, что

`0=(a_0+a_1 u+⋯+a_n u^n)^2+(b_0+b_1 u+⋯+b_n u^n)^2-1`

`=(a_0^2+b_0^2-1)+2(a_0 a_1+b_0 b_1 )u+(a_1^2+2a_0 a_2+b_1^2+2b_0 b_2)u^2`

`+⋯+(a_{n-1}^2+2a_{n-2} a_n+b_{n-1}^2+2b_{n-2} b_n)u^{2n-2}`

`+2(a_n a_{n-1}+b_n b_{n-1})u^{2n-1}+(a_n^2+b_n^2)u^2n`

Это уравнение должно выполняться для всех `u`, откуда следует, что все коэффициенты равны нулю. Начиная с высочайших степеней и двигаясь вниз, мы показываем в `n` шагов, что все `a_i=0` и `b_i=0` для `1≤i≤n`.

Шаги

  1. `a_n^2+b_n^2=0` предполагает `a_n=b_n=0`.
  2. `a_(n-1)^2+2a_{n-2}a_n+b_{n-1}^2+2b_{n-2}b_n=0` и Шаг 1 предполагает что `a_{n-1}^2+b_{n-1}^2=0` из чего следует, что `a_{n-1}=b_{n-1}=0`.
  3. ⋮
  4. `a_1^2+2a_0 a_2+b_1^2+2b_0 b_2=0` и Шаг `n-1` предполагает что что `a_1^2+b_1^2=0` из чего следует, что `a_1=b_1=0`.

Таким образом, `x(u)=a_0` и `y(u)=b_0`, что очевидно невозможно.

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

`x(u)={X(u)}/{W(u)}` `y(u)={Y(u)}/{W(u)}`  (1.13)

Где `X(u)`, `Y(u)`, и `W(u)` – многочлены, таким образом, все координатные функции имеют одинаковый знаменатель.

Примеры

Пример1.8 Круг с радиусом 1 и центром в начале координат

`x(u)=(1-u^2)/(1+u^2)`   `y(u)=2u/(1+u^2)`
Пример1.9 Эллипс с центром в начале координат; `y`-ось это большая ось, `x`-ось это малая ось, и большой и малый радиус 2 и 1, соответственно

`x(u)=(1-u^2)/(1+u^2)`   `y(u)=4u/(1+u^2)`
Пример1.10 Гипербола с центром в `P=(0,4⁄3)`; `y`-ось это поперечная ось

`x(u)=(-1+2u)/(1+2u-2u^2)`   `y(u)=(4u(1-u))/(1+2u-2u^2)`

нижняя ветвь (с вершиной в `P=(0,2⁄3)`) прослеживается для

`u in ({1-sqrt 3}/2, {1+ sqrt 3}/2)`
Пример1.11 Парабола с вершиной в начале координат; `y`-ось ось симметрии

`x(u)=u`   `y(u)=u^2`

Обратите внимание, что парабола не требует рациональной функции. Читателю следует понять эти функции. Для уравнений окружности легко увидеть, что для любых `u`, `(x(u),y(u))` лежит на единичной окружности с центром в начале координат

`(x(u))^2+(y(u))^2=((1-u^2)/(1+u^2))^2+(2u/(1+u^2))^2`

`=(1-2u^2+u^4+4u^2)/(1+u^2)^2=(1+u^2)^2/(1+u^2)^2=1`

Определим рациональную кривую Безье `n`-ой степени

`C(u)={sum_{i=0}^nB_{i,n}(u)w_iP_i}/{sum_{i=0}^nB_{i,n}(u)w_i}`   `0≤u≤1`   (1.14)

Где `P_i=(x_i,y_i,z_i)` и `B_{i,n}(u)` как и раньше; `w_i` скаляр, называется весами. Таким образом, `W(u)=∑_{i=0}^nB_{i,n}(u)w_i` является общей функцией знаменателя. За исклю­чением явных случаев, мы предполагаем что `w_i>0` для всех `i`. Это условие обеспечи­вает `W(u)>0` для все `u in [0,1]`. Мы пишем

`C(u)=sum_{i=0}^nR_{i,n}(u)P_i`   `0≤u≤1`   (1.15)

где `R_{i,n}(u)={B_{i,n}(u)w_i}/{sum_{j=0}^nB_{j,n}(u)w_j}`

`R_{i,n}(u)` это рациональная базисная функция для этих форм кривых. Рис 1.18а показывает пример кубических базисных функций, и Рис 1.18b описывает кубическую рациональную кривую Безье.

Рисунок 1.18. Рациональные кубические (a) Базисные функции (b) Кривая Безье.

`R_{i,n}(u)` имеет свойства, которые можно легко вывести из уравнения (1.15) и описанные свойства `B_{i,n}(u)`:

Св.1.8 Не отрицательность: `R_{i,n}(u)≥0` для всех `i`,`n` и `0≤u≤1`;
Св.1.9 Разбиение единицы: `∑_{i=0}^nR_{i,n}(u)=1` для всех `0≤u≤1`;
Св.1.10 `R_{0,n}(0)=R_{n,n}(1)=1`;
Св.1.11 `R_{i,n}(u)` достигает ровно одного максимума на отрезке `[0,1]`
Св.1.12

Они дают следующие геометрические свойства рациональных кривых Безье:

Св.1.13 Свойство выпуклой оболочки: кривые содержатся в выпуклых оболочках образованных их контрольными точками.
Св.1.14 Инвариантность преобразований: повороты, перемещение и масштабирование применяемые к кривой, применяются к их контрольным точкам;
Св.1.15 Осцилляцию собственности: такое же, как для полиномиальных кривых Безье (см предыдущий раздел);
Св.1.16 Интерполяция конечной точки: `C(0)=P_0` и `C(1)=P_n`;
Св.1.17 `k`-ая производная при `u=0` зависит от первой (последней) `k+1` контрольных точек и веса; в частности, `C'(0)` и `C'(1)` параллельны `P_1-P_0` и `P_n-P_{n-1}`, соответственно;
Св.1.18 Многочленные кривые Безье частный случай рациональных кривых Безье.

Примеры

Пример1.12 Рассмотрим рациональную круговую дугу Безье.

`C(u)=(x(u),y(u))=({1-u^2}/{1+u^2},{2u}/{1+u^2})`   `0≤u≤1`

представляет один квадрант единичной окружности, как показано на рисунке 1.19a. Выведем теперь квадратичное рациональное Безье представление этой дуги. Очевидно, из Св.1.16 и Св.1.17, `P_0=(1,0)`, `P_1=(1,1)`, и `P_2=(0,0)`. Для весов мы имеем

`W(u)=1+u^2=sum_{i=0}^2B_{i,2}(u)w_i=(1-u)^2w_0+2u(1-u)w_1+u^2w_2`

Заменяя `u=0` на `w_0=1`, и `u=1` на `w_2=2`. В итоге, заменяя `u=1⁄2` на `5⁄4=1⁄4w_0+1⁄2w_1+1⁄4w_2`, и используя `w_0=1` и `w_2=2` получаем `w_1=1` (Смотри Рис 1.19b)

Рисунок 1.19. Представление единичного круга, (a) `x(u)=(1-u^2)⁄(1+u^2)` и `y(u)=(2u)⁄(1+u^2)` для одного квадранта; (б) представление Безье, соответству­ющее рисунку 1.19a (`w_0-1`, `w_1=1`, `w_2=2`).

Рациональные кривые с координатными функциями в виде уравнения. (1.13) (один общий знаменатель), имеют элегантную геометрическую интерпретацию, которая дает эффективную обработку и хранение компактный данных. Идея состоит в том, чтобы использовать однородные координаты для представления рациональной кривой в `n`-мерном пространстве как многочлен кривой в `(n-1)`-мерном. Начнем с точкой в трех­мерном Евклидовом пространстве, `P=(x,y,z)`. Тогда `P` записывается в виде `P^w=(wx,wy,wz,w)=(X,Y,Z,W)` в четырехмерном пространстве, `w≠0`. Теперь `P` получается из `P^w` делением всех координат на четвёртую координату, `W`, т. е. на отображение `P^w` из начала координат на гиперплоскость `W=1` (смотри рис 1.20 для двухмерного случая, `P=(x,y)`. Это отображение, обозначаемое `H`, является перспек­тивной картой с центром в начале координат

Рисунок 1.20. Представление евклидовых точек в однородной форме.

`P=H{P^w}=H{(X,Y,Z,W)}={((X/W,Y/W,Z/W) " если " W≠0), ("направление"(X,Y,Z) " если " W=0):}` (1.16)

Обратите внимание, что для любого `x,y,z,w_1,w_2,` где `w_1≠w_2`

`H{P^{w_1}}= H{(w_1x,w_1y,w_1z,w_1)}=(x,y,z)`

`=H{(w_2x,w_2y,w_2z,w_2)}=H{P^{w_2}}`

Теперь для данного набора контрольных точек, `{P_i}`, и весов, `{w_i}`, построим взвешенные контрольные точки, `P_i^w=(w_ix_i,w_iy_i,w_iz_i,w_i)`. Затем определим нерациональную (многочленую) кривую Безье в четырехмерном пространстве

`C^w(u)=sum_{i=0}^nB_{i,n}(u)P_i^w`   (1.17)

Тогда, применяя перспективную карту, `H`, на `C^w(u)` получаем соответствующую рациональную кривую Безье уравнения (1.14) (смотри рис 1.21), то есть, выписывая координатные функции уравнения (1.17), получаем

Рисунок 1.21. Геометрическая конструкция рациональной кривой Безье.

`X(u)=sum_{i=0}^nB_{i,n}(u)w_ix_i`   `Y(u)=sum_{i=0}^nB_{i,n}(u)w_iy_i`

`Z(u)=sum_{i=0}^nB_{i,n}(u)w_iz_i`   `W(u)=sum_{i=0}^nB_{i,n}(u)w_i`

Расположение кривой в трёхмерном пространстве даёт

`x(u)={X(u)}/{W(u)}={sum_{i=0}^nB_{i,n}(u)w_ix_i}/{sum_{i=0}^nB_{i,n}(u)w_i}`

`y(u)={Y(u)}/{W(u)}={sum_{i=0}^nB_{i,n}(u)w_iy_i}/{sum_{i=0}^nB_{i,n}(u)w_i}`

`z(u)={Z(u)}/{W(u)}={sum_{i=0}^nB_{i,n}(u)w_iz_i}/{sum_{i=0}^nB_{i,n}(u)w_i}`

Используя векторную запись, мы получим

`C(u)=(x(u),y(u),z(u))={sum_{i=0}^nB_{i,n}(u)w_i(x_i,y_i,z_i)}/{sum_{i=0}^nB_{i,n}(u)w_i}`

`={sum_{i=0}^nB_{i,n}(u)w_iP_i}/{sum_{i=0}^nB_{i,n}(u)w_i}`   (1.18)

Для алгоритмов в этой книге мы, в основном, используют форму, определяемую уравнением (1.17), и аналогичную форму рациональных кривых B-сплайнов. Таким образом, нерациональные формы обрабатываются в четырехмерном пространстве, и результаты находятся в трехмерном пространстве с помощью карты `H`. Мы имеем в виду попеременно либо `C^w(u)` или `C(u)` в качестве рациональных кривых Безье (или B-сплайнов), хотя, строго говоря, `C^w(u)` не рациональная кривая.

Примеры

Пример1.13 Давайте вернёмся к круговой дуге на рис. 1.19б. Мы имеем `P_0=(1,0)`, `P_1=(1,1)`, `P_2=(0,1)`, и `w_0=1`, `w_1=1`, `w_2=2`. Следовательно, для уравнения (1.17) трехмерные контрольные точки `P_0^w=(1,0,1)`, `P_1^w=(1,1,1)`, и `P_2^w=(0,2,2)`. Тогда `C^w(u)=(1-u)^2P_0^w+``2u(1-u)P_1^w+u^2P_2^w` это параболическая дуга (нерациональная), которая проецируется на круговую дугу на плоскости `W=1` (смотри рис 1.22).

Рисунок 1.22. Однородное представление дуги окружности.

Пусть `u_0` фиксированный. Пусть `C^w(u)` многочлен кривой Безье, мы используем алгоритм де Кастельжо для вычисления `C^w(u_0)`; впоследствии, `C(u_0)=H{C^w(u_0)}`. Таким образом, мы применяем формулу (1.12) для `P_i^w`

`P_{k,i}^w(u_0)=(1-u_0)P_{k-1,i}^w+u_0P_{k-1,i+1}^w`

для `{(k=1",...,"n),(i=0",...,"n-k):}`(1.19)

Пример1.14 Давайте применим формулу (1.19) для вычисления точки `u=1⁄2` на рациональной круговой дуге Безье примера 1.13. Дуга задается `C^w(u)=(1-u)^2P_0^w+2u(1-u)P_1^w+u^2P_2^w`, тогда `P_0^w=(1,0,1)`, `P_1^w=(1,1,1)`, и `P_2^w=(0,2,2)`. Треугольное множество полученных точек показаны в таблице 1.4. Тогда `C(1⁄2)=H{C^w(1⁄2)}=H{(3⁄4,1,5⁄4)}=(3⁄5,4⁄5)`.

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

`C(u)=({(1-u^2)}/{(1+u^2)},{(2u)}/{(1+u^2)})`

Тогда

`C(1/2)=({1-(1/2)^2}/{1+(1/2)^2},{2(1/2)}/{1+(1/2)^2})=(3/5,4/5)`

Используя выражение (1.17)

`C^w(1/2)=sum_{i=0}^2B_{i,2}(1/2)P_i^w=`

`=(1-(1/2))^2(1,0,1)+2(1/2)(1-(1/2))(1,1,1)+(1/2)^2(0,2,2)`

`=1/4(1,0,1)+1/2(1,1,1)+1/4(0,2,2)=(3/4,1,5/4)`

Проекция `(3/5,4/5)`. Уравнения (1.18) и (1.15) дают одинаковый результат.

Наконец, отметим, что `C(1⁄2)=(3⁄5,4⁄5)` не середина круговой дуги в первом квадранте; т.е. параметризация не является равномерным (см раздел 1.1). Точка `(3⁄5,4⁄5)` больше, чем половина длины дуги от начальной точки. Это интуитивно правильно, так как при дифференцировании `C(u)` можно видеть, что стартовая скорость в два раза больше конечной скорости.