План:

1. Принцип линейной аппроксимации

2. Параметрическое представление функции

3. Гладкость кривых

4. NURBS - кривые

4.1. Контрольные точки

5. Базовые функции

5.1. Узлы

5.2. Характеристика семейства базовых функций

6. Рациональные кривые

7. Язык PostScript* (Для дополнительного изучения)

    Принципы векторной графики основаны на ином математическом аппарате, чем растровая графика и имеют целью построение линейных контуров, составленных из элементарных кривых, описываемых математическими уравнениями в особой параметрической форме.
    Для того чтобы линейные контуры, составленные из элементарных кривых, не создавали резких преломлений и разрывов, элементарные кривые должны быть гладкими, что обеспечивается специальным размещением управляющих линий. Общим видом таких кривых являются NURBS-кривые, а более частным — кривые Безье . Первые и вторые используются в трехмерной графике, а вторые — только в программах плоской векторной графики.
    В программах векторной графики единственный способ изменения формы — интерактивное перемещение опорных и управляющих точек. На базе кривой Безье основывается и язык описания страниц PostScript, развитие которого шло по пути интегрирования новых возможностей выводных устройств (цветной печати, систем управления цветом и шрифта).

Принцип линейной аппроксимации

В основе пиксельной графики лежит технология дискретизации (разделение плоского изображения на равные площадки — пиксели). Если применить принцип дискретизации для линейных изображений, ее характер будет другой — линейный. Пространственная дискретизация, на которой основана пиксельная графика, сменится на линейную.
Линейная дискретизация позволяет создавать произвольные векторные контуры из элементарных кривых, построенных на основе какой-либо единой формулы.

При делении произвольного векторного контура на отдельные фрагменты (сегменты) требуется:
• разбивать линии на достаточно короткие фрагменты (сплайны);
• выбрать наиболее простую формулу (функцию), представляемую в параметрической форме, для описания.
Самой простой функцией является линейная зависимость, с помощью которой описывается прямая линия. Разбивая линейный рисунок на достаточно мелкие элементы дискретизации, соединяя полученные точки дискретизации прямыми, можно с помощью конечного количества этих прямых представить любой линейный объект и любую сложную кривую. Главным достоинством такой технологии является простота: любая точка определяется ее двумя координатами. Таким образом, огромную кривую можно описать сотней пар чисел.
Однако указанная простота является причиной следующих недостатков:
• Объекты, составленные только из прямолинейных сегментов, лишаются возможности произвольного масштабирования. (Пока отрезки достаточно мелкие, они не создают впечатления угловатости, но при значительном коэффициенте увеличения углы становятся очевидными)
• Форма объекта, аппроксимированного линейными отрезками, может изменяться, например: при вращении.
• Для достоверной аппроксимации формы объекта потребуются десятки тысяч линейных сегментов .
Указанные недостатки заставляют искать другие способы описания формы объектов и использовать более сложные кривые второй, третьей и т. д. степеней.

Параметрическое представление функции

Вы знаете, что кривые можно представлять аналитически и графически. График тригонометрической функции у = sin х изображен на рис. 1.
Такой способ представления формулы и ее графика называется явным. Он позволяет легко строить график. Однако у этого способа с точки зрения графического представления имеются следующие недостатки:

Рис. 1. График функции у = sinx

• Каждому значению х соответствует только одно значение у. Это не дает возможности начинать новый фрагмент кривой в произвольном месте.
• Кривая не может быть замкнутой.
Поэтому явный способ представления не может применяться там, где требуется описание произвольных кривых, размещаемых в произвольных местах на плоскости. Альтернативным способом является определение кривой как параметрической функции.
Параметрическое представление функции — это выражение функциональной зависимости между несколькими переменными введением вспомогательных переменных, которые называют параметрами.
В общем случае такая зависимость получает вид:
q(t) = {x(t), y(t)}, где х(t) и y(t) — функции параметра t.
Задавая одинаковые значения t , функция x(t) вычисляет значения координаты х, а функция y(t) — значения координаты у.
Особенности параметрических кривых:
1. Обе координаты (x, y) являются равноправными: вычисляются как функции вспомогательного параметра;
2. Они имеют более разнообразные формы, чем это позволяют явные уравнения;
3. Такое представление важно для пространственных кривых, поскольку обеспечивает более легкий способ построения графиков;
4. Применение параметрических функций позволяет применять более сложные функции, а не только линейную аппроксимацию. (Одним из основных недостатков аппроксимации прямыми является наличие угловых изгибов, которые даже при относительно невысоком увеличении не создают впечатления гладкости)
Поэтому неизбежной заменой прямолинейным сегментам могут быть только кривые, которые способны обеспечить требуемую гладкость (Речь идет о кривых Безье и NURBS-кривых). Но сначала необходимо определить понятие гладкости.

Гладкость кривых

Одной из самых важных причин выбора в качестве средств векторной графики кривых Безье и NURBS-кривых является управляемая гладкость. Гладкость означает, что при моделировании на кривой не образуется петель и резких преломлений (тем более разрывов). Но при этом, не исключена возможность создания как гладкого сопряжения, так и изгибов, например острых углов. Примером такого сочетания гладких кривых и острых преломлений являются профили авиакрыла.
Если касательная в соседних точках не меняет резко своего направления, такую кривую считают гладкой (рис. 2).
Если на кривой имеется излом, то направление касательной в точке Q меняется мгновенно (рис. 3).

Рис. 2. Касательная на гладкой кривой

Рис. 3. Касательная на кривой с изломом

Рассмотрим основы построения гладких кривых, применяющихся в векторной компьютерной графике. NURBS-кривые являются более общим и, соответственно, более сложным случаем таких кривых.

NURBS-кривые

Термин NURBS является аббревиатурой (сокращением) от слов Non-Uniform Rational B-spline, где:
• Non-Uniform (неоднородный) означает, что область влияния контрольной точки на форму кривой может быть различной. Это очень важное свойство для моделирования иррегулярных кривых.
• Rational (рациональный) означает, что математическое выражение, описывающее форму моделируемой кривой, есть отношение двух полиномов. (Эта особенность позволяет точнее моделировать различные кривые, например, конические сечения)
• B-spline (basis spline, базовый сплайн) - способ математического описания кривой интерполяцией между тремя и более контрольными точками.

Контрольные точки

Согласно определению параметрической кривой левая часть выражения, описывающая функцию q, выглядит так: q(t) = ...,
где t — параметр значений определенного диапазона, как правило, от 0 до 1. Используя эти значения, получают последовательность пар {х, у}, по которым строится моделируемая кривая (рис. 4).

Рис. 4. Пример построения параметрической кривой.

Рис. 5. Множество контрольных точек, определяющих параметрическую кривую.

В указанном выше выражении не определена правая часть, т. е. собственно параметрическое уравнение, а точнее, параметрические уравнения.
Одной из основополагающих особенностей NURBS-кривой является то, что ее форма определяется расположением множества контрольных точек (control points). На рис.5 эти точки обозначены как Bi.
Ломаная линия, соединяющая контрольные точки, называется управляющим многоугольником (control polygon).
Эта особенность NURBS-кривой важна, поскольку позволяет локализовать изменение формы кривой перемещением отдельных контрольных точек без изменения формы всей кривой в целом (рис. 6).

Рис. 6. Изменение формы фрагмента кривой, вызванное перемещением контрольной точки

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

Базовые функции

Функция, которая определяет зависимость формы кривой от конкретной контрольной точки Bi, называется базовой функцией (basis function) этой контрольной точки.
В названии В-сплайнов буква В и означает базовые (basis). Значение базовой функции представляет собой вещественное число. Описание NURBS-кривой требует задания базовой функции для каждой контрольной точки.
Можно описать значения функции для выбранного значения параметра t, таким образом: 30% положения одной контрольной точки плюс 60% — другой и плюс 10% — третьей. Это, в частности, означает, что когда движущаяся частица удаляется от некоторой контрольной точки, она испытывает все меньшее воздействие. И, наоборот, при приближении частицы к контрольной точке ее положение все больше от нее зависит. Такой эффект повторяется всякий раз, когда движущаяся частица проходит все контрольные точки. Подобное "влияние" контрольной точки может быть не только выражено числовыми значениями, но и визуализировано на графике. Таким образом, можно построить график базовой функции как зависимость влияния на движущуюся частицу, например в процентах, от значения t (рис. 7).
Максимальный эффект (максимальное влияние) достигается в совершенно определенной точке и постепенно уменьшается по мере удаления.

Рис. 7. Типичный график базовой функции отдельной контрольной точки.

Рис. 8. Однородные базовые функции для множества контрольных точек.

Поскольку каждая контрольная точка "обязана" иметь свою базовую функцию, NURBS-кривая, построенная, например, по пяти контрольным точкам, должна иметь пять таких функций, перекрывающих некоторую область результирующей кривой (рис. 8).

Узлы

На рис. 8 все базовые функции имеют одинаковую форму и размещены на равных расстояниях друг от друга. На самом деле, желательно варьировать длины интервалов таким образом, чтобы определенные контрольные точки влияли на значительно больший сегмент кривой, а другие — на меньший. Это создает условие для неоднородности (Non-Uniform) в описании кривой.
Определение последовательности точек, на которые разбивается ось параметра t, не является легкой задачей. Ведь при изменении относительных интервалов между такими точками, возможно менять длительность воздействия контрольных точек на движущуюся вдоль кривой частицу.
Точки, разграничивающие интервалы, называются узлами (knots), а их упорядоченный список — называется узловым вектором (knot vector).
Узловой вектор базовой функции, представленный на рис. 9, имеет вид {0.0, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0}. Это пример однородного узлового вектора (uniform knot vector), где все функции определены на одинаковых временных интервалах.

Рис. 9. Пример однородного узлового вектора

Рис. 10. NURBS-кривая с однородным узловым вектором

Рис. 12. NURBS-кривая с неоднородным узловым вектором

Следующий рисунок (рис. 10) представляет пример кривой, созданной на основе такого узлового вектора.
Если изменить узловой вектор, например, следующим образом: {0.0, 1.0, 2.0, 3.75, 4.0, 4.25, 6.0, 7.0}, то получится другое множество неоднородных (non-uniform) базовых функций (рис. 11) и, соответственно, другая форма кривой (рис. 12), которая строится на тех же контрольных точках, что и на рис. 10.

Рис. 11. Неоднородные базовые функции для множества контрольных точек.

Характеристика семейства базовых функций

Для любого значения параметра t сумма всех базовых функций равна 1.
Если веса всех контрольных точек положительны, кривая лежит в области, полученной соединением крайних (внешних) контрольных точек. Такой "габаритный" контейнер получил название "выпуклой оболочки" (convex hull).

Рациональные кривые
Ключевая буква в названии NURBS — R rational (рациональный). Рациональные кривые, в сравнении с non-rational В-сплайнами, обладают двумя очень важными свойствами:
• они обеспечивают корректный результат при проекционных трансформациях (например, масштабировании), а нерациональные В-сплайны — только при аффинных трансформациях (например, перемещениях);
• их можно использовать для моделирования кривых любого вида, включая конические сечения (окружности, эллипсы, параболы и гиперболы).
Эти свойства достигаются за счет четырехмерного представления обычной трехмерной контрольной точки {х, у, z}. Это значит, что каждая контрольная точка представляется четырьмя координатами {х, у, z, w}. Последняя координата w означает вес (weight) контрольной точки. Изначально координата w равняется единице, но при увеличении этого значения для контрольной точки увеличивается степень ее воздействия на форму кривой и последняя сильнее выгибается в сторону контрольной точки (рис. 13).
Существенным является только относительное изменение весов контрольных точек. Если вдвое увеличить веса всех контрольных точек, то форма кривой не изменится.

Рис. 13. Изменение формы кривой при изменении веса контрольной точки.

Квадратичная NURBS-кривая определяется тремя контрольными точками (рис. 14). У всех трех кривых узловой вектор имеет вид {0.0, 0.0, 0.0, 1.0, 1.0, 1.0}. Веса первой и последней контрольных точек у каждой кривой равны 1. Если вес центральной вершины меньше 1, то результирующая кривая представляет собой сегмент эллипса (рис. 14, а). Если ее вес равен 1, образуется парабола (рис. 14, б). Если же ее вес гораздо больше 1, то кривая преобразуется в гиперболу (рис. 16, в).

Рис. 14. NURBS-кривые с различными весами центральной контрольной точки.

Но NURBS-кривые обладают серьезным недостатком: расширенные возможности не могли не сказаться на уровне и сложности инструментария для их построения.

Язык PostScript*

Язык описания страницы PostScript был создан в начале 80-х годов фирмой Adobe. Он был призван стать языком управления графическим устройством, например лазерным принтером, а не просто выполнять узкую задачу — позиционировать только черные точки, т. е. не только создавать битовую карту изображения с учетом разрешения выводного устройства (так работает язык PCL). Главная обязанность этого языка должна заключаться в передаче информации между прикладными программами (графическими редакторами, программами верстки) и устройствами визуализации (лазерными принтерами, фотонаборными автоматами и цифровыми офсетными машинами). Поэтому формирование полной битовой карты страницы было перенесено в обязанность принтера, что вызвало необходимость включить в его состав как вычислительный блок, так и блок памяти.
В основу языка PostScript были положены следующие условия:
• Основой векторного принципа кодирования графической информации приняты кривые третьего порядка (кривые Безье). Они использовались для описания как графики, так и шрифта, что обусловило единые алгоритмы обработки (с некоторыми небольшими отличиями).
• PostScript разрабатывался, как язык программирования высокого уровня, а не линейного управления внешним печатающим устройством. Поэтому были предусмотрены все возможности, свойственные классическим языкам программирования: циклы, ветвления, подпрограммы и т. д. Кроме того, PostScript - это язык интерпретирующего типа (программа обрабатывается по мере поступления команд). Файлы в формате PostScript сохраняются в виде обычных текстовых символов (первая половина кодовой таблицы ASCII), что позволяет "рисовать" страницы в обычном текстовом редакторе. Поэтому документ, написанный на языке PostScript или сгенерированный из какого-либо приложения, — это программа, которая подлежит выполнению, и этим "занимается" интерпретатор языка, входящий в состав принтера.
• Изображение, которое описывается с использованием языка PostScript, никаким образом не связано с разрешающей способностью конкретных устройств вывода. Процесс приспособления изображения к возможностям принтера (процессы растеризации и растрирования) происходит уже в самом принтере, тем самым добивается максимальное качество, на которое он способен. Заранее готовить изображение, приспособленное к конкретному принтеру, нет необходимости.
• С точки зрения содержания язык PostScrip — это графика, основанная на кривых Безье (линии, которым можно присвоить обводку (stroke) и заливку (fill). Возможны импортирование и обработка пиксельной графики.
Эти условия и их реализация позволили языку PostScript стать основой всей области компьютерной графики и полиграфии. Последующее развитие языка не изменило своей основы, шло по пути интегрирования новых возможностей выводных устройств (цветная печать, систем управления цветом и т. д.).
Резюме
► Идея векторной графики состоит в описании линейных фрагментов с помощью единственной формулы.
► Разбиение произвольных кривых на отдельные фрагменты (сегменты) разумно выполнять, учитывая следующие условия: фрагменты должны быть достаточно короткими, а формула должна обеспечивать достаточно близкую аппроксимацию кривых.
► Линейная зависимость обладает важным достоинством — простотой, но при этом не лишена серьезных недостатков (объекты, составленные только из прямолинейных сегментов, лишаются возможности произвольного масштабирования, для достоверной аппроксимации формы объекта потребуются десятки тысяч линейных сегментов).
► Неизбежной заменой прямолинейным сегментам могут быть только кривые, которые способны обеспечить требуемую гладкость (кривые Безье и NURBS).
► Явный способ представления функции не может применяться там, где требуется описание произвольных кривых, размещаемых в произвольных местах на плоскости.
► Альтернативным способом описания кривой является определение кривой как параметрической сплайновой функции.
► Одной из основополагающих особенностей NURBS-кривой является то, что ее форма определяется расположением множества контрольных точек (control points). Она позволяет локализовать изменение формы кривой перемещением отдельных контрольных точек без изменения формы кривой в целом.
► Рациональные кривые обладают двумя дополнительными свойствами (они обеспечивают корректный результат при проекционных трансформациях (например, масштабировании), их можно использовать для моделирования кривых любого вида, включая конические сечения).
► NURBS-кривые все же обладают существенным недостатком: расширенные возможности не могли не сказаться на сложности и на уровне инструментария для их построения.
► Язык описания страницы PostScript, созданный как язык управления графическими устройствами, решает задачи передачи информации между прикладными программами (графическими редакторами, программами верстки) и устройствами визуализации (лазерными принтерами, фотонаборными автоматами и цифровыми офсетными машинами).
► Последующее развитие языка PostScript не изменило своей основы и продолжает идти по пути интегрирования новых возможностей выводных устройств (цветная печать, системы управления цветом и т. д.).