Лекции (Алещенко) (774781), страница 6

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 6)

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

Алгоритмы компьютерной графики

РАСТРОВЫЕ АЛГОРИТМЫ

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

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

Для инициализации библиотеки служит функция

v
oid far initgraph(int_far*driver, int_far*mode, char_far*path)

где *driver – задает тип адаптера,

*mode – определяет режим, например,

*path – имя каталога, где находится драйвер адаптера (файл типа BGI – Borland Graphics Interface).

Функция graphresult возвращает код завершения предыдущей графической операции

int far graphresult (void)

Любая графическая библиотека (в том числе и рассматриваемая) содержит модули для реализации основных графических объектов:

• линейные изображения (отрезки прямых, дуги окружностей, дуги эллипсов),

• сплошные объекты, т.е. растровые образы двумерных областей (круг, прямоугольник, эллипс),

• шрифты,

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

Эти объекты называются также графическими примитивами.

Библиотека Borland C++ содержится в файле graphics.h. Примеры функций графики из этой библиотеки приведены в табл.6.

Общий вид вызова функции:

{имя} ( {параметры} )

Таблица 6

Рассмотрим функцию выбора шрифта

void far settextstyle (int Font, int Direction, int Size);

где Font – задает идентификатор одного из шрифтов и соответствует обращению к набору символов (матриц 8х8 пикселей), изображающих

каждый символ; может принимать значения

Direction – определяет ориертацию текста (горизонтальная или вертикальная):

Size – указывает, во сколько раз нужно увеличить шрифт перед выводом на экран. Например, для шрифта DEFAULT_FONT возможны значения:

1 - матрица 8х8 пикселей,

2 - матрица 16х16 пикселей,

. . .

10 – матрица 80х80 пикселей.

Приведем типовую форму файла с использованием графики и вывода текста на экран.

# include

# include

# include

# include

int main (void)

{

int driver = DETECT, gmode, errorcode;

int x,y;

initgraph(&gdriver,&gmode);

errorcode = graphresult();

if (errorcode != OK)

{

printf(“Graph. error:%s\n”,grapherrormsg(errorcode));

printf(“Press any key to halt:”);

getch();

exit(1);

}

printf(“Graph.error:%S\n”,grapherrormsg(errorcode));

x=getmaxx()/2;

y=getmaxy()/2;

settextstyle(GOTHIC_FONT, GORIZ_DIR,8);

outtextxy(x,y, ”Press any key to close a gr.sys:”);

getch();

closegraph();

printf(“We are now back in text mode.\n”);

printf(“Press any key to halt:”);

getch();

return0;

}

АЛГОРИТМЫ ВЫЧЕРЧИВАНИЯ ЛИНИЙ

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

Важным понятием растровой графики является связность, т.е. возможность соединения двух пикселей растровой линией (последовательным набором пикселей). Линия состоит из соседних одинаково закрашенных пикселей.

И
спользуется два понятия связности для точек a₁(x1,y1) и a₂(x2,y2) (см. рис.46).

Понятие 4-хсвязности более строгое, чем 8-связность (т.е. является частным случаем).

В качестве линии на растровой сетке выступает набор пикселей p₁,p₂,…,p_n , где два пикселя p_i, p_i+1 являются соседними; линия может быть определена в смысле 4-хсвязной или 8-связной.

Одним из подходов к вычерчиванию линии является использование соотношения между смещением по координатам х и у.

Для простоты считаем, что

0  y2-y1  x2-x1

о
трезок описывается уравнением

или y = k x + b.

П
усть требуется провести линию от a₁(0,0) и a₂(10,5). Тогда смещения

y = 5 и y = 10, а соотношение

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

Этот метод используется довольно редко.

Наиболее популярный метод изображения линий основан на алгоритме Брезенхейма (Bresenhame), предложенный в 1965 г. для растрового построения отрезка.

Алгоритм Брезенхейма отличается тем, что не требуется выполнять деление или умножение чисел с плавающей точкой. Вместо этого отношение между значениями координат x и y представляется косвенно через серии сложений и вычитаний. Основная идея алгоритма Брезенхейма – это регистрация средних значений погрешностей между идеальным положением каждой точки и той позицией на экране дисплея, в которой она реально отображается.

В принципе, алгоритм применим для любой формы линии. Его суть – итерационный процесс поиска соседних точек, начиная с точки a₁(x1,y1).

Алгоритм Брезенхейма:

а) в каждой итерации цикла вычерчивания линии вычисляются 2 погрешности по осям x и y, которые увеличиваются с изменением координат x и y соответственно;

б) если значение погрешности достигает определенной величины, оно вновь устанавливается в 0, а соответствующая координата увеличивается на 1;

в) этот процесс продолжается, пока вся линия не будет построена полностью и мы не попадем в точку конца.

П ри построении отрезка прямой всегда выбирается ближайший по вертикали пиксель (см. рис.47).

П ри этом из двух точек А и В A

выбирается та, которая ближе к a{

исходной прямой, т.е. точка А, т.к. }b

a < b . B

Для этого вводится число, равное

d = (x2-x1)(b-a) Рис. 47.

Если d>0, то значение y от предыдущей точки увеличивается на 1, а d – на 2(y -x), в противном случае значение y не изменяется, а d = 2 y.

Тогда простейший алгоритм для того же примера

0  y2-y1  x2-x1

имеет вид:

void line ( int x1, int y1, int x2, int y2, int Color )

{

int dx = x2-x1;

int dy = y2-y1;

int d = (dy<<1)- dx;

int d1 = dy<<1;

int d2 = (dy-dx)<<1;

putpixel(x1,y1,Color);

for (int x = x1+1; y = y1; x<=x2; x++)

{

if (d>0) { d+ = d2; y+ = 1;

}

else d+ = d1;

putpixel(x,y,Color);

}

}

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

ВЫЧЕРЧИВАНИЕ ОТРЕЗКОВ

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

Алгоритм Сазерленда-Кохена

Пусть область отсечения ограничена прямоугольником (см. рис. 48а). Четыре линии, образующие прямоугольник, делят плоскость на 9 областей, которые могут быть закодированы тетрадой Code (см. рис. 48б).

Каждый бит тетрады имеет смысл:

0 – точка левее прямоугольника,

1 – точка выше прямоугольника,

2 – точка правее прямоугольника,

3 – точка ниже прямоугольника.

Тогда для произвольной точки M(x,y) на прямой L можно определить тетраду (полубайт) принадлежности внутренности прямоугольника, исходя из условия, что если Code = 0000B, точка находится внутри прямоугольника, иначе – точка вне прямоугольника.

ОПРЕДЕЛЕНИЕ ПРИНАДЛЕЖНОСТИ ТОЧКИ

ВНУТРЕННОСТИ МНОГОУГОЛЬНИКА

В общем случае многоугольник ограничивается ломанной p₁, p₂,…, p_n (см. рис. 49). Для некоторой точки M(x,y) задача принадлежности может быть решена путем построения произвольного луча из точки М и определения числа пересечений этого луча с границей многоугольника.

Удобно использовать горизонтальные или вертикальные лучи, тогда:

1. если луч не проходит через вершину (рис.49а), то условие принадлежности точки внутренности многоугольника – нечетное число пересечений луча со сторонами многоугольника, если число пересечений четное, то точка лежит вне многоугольника;

2. если луч проходит через вершину, то возможны следующие 4 варианта

• (рис. 49 б) М₁ и М₂ – простые случаи, ребра, выходящие из вершины лежат либо по одну сторону от луча, либо по разные стороны. Это – экстремальные случаи, и четность числа пересечений инвертируется для М₁ и сохраняется для М_2;

• (рис. 49 в) для точек М₃ и М₄ такой подход непосредственно не годится.

В общем случае получаем алгоритм:

• все отрезки ломанной, кроме горизонтальных, проверяются на пересечение с горизонтальным лучом, выходящим из точки М,

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

ЗАКРАСКА ОБЛАСТИ, ЗАДАННОЙ ЦВЕТОМ ГРАНИЦЫ

Рассмотрим область, ограниченную набором пикселей заданного цвета, и точку M(x,y), лежащую в этой области (см. рис. 50).

Задача заполнения заданным цветом,

е сли область не является выпуклой, может

о казаться сложной.

Существуют несколько алгоритмов закраски.

Алгоритм “растекания цвета”:

1. о рганизавать цикл закраски пикселей

до достижения границы области,

2) закрасить пиксель M(x,y) заданным цветом,

1. закрасить соседние пиксели в смысле 4-х

или 8-связности. Рис. 50

Этот алгоритм не эффективен, т.к. для уже закрашенного пикселя функция закраски выполняется еще три раза.

Алгоритм «штриховка»:

1. для заданной точки M(x,y) определить и закрасить максимальный горизонтальный отрезок внутри области,

2. проверить отрезки выше и ниже в поисках незакрашенных пикселей,

3. если такие пиксели найдены, то повторяется п.1.

Алгоритм работает эффективно для областей любой формы.

УДАЛЕНИЕ НЕЛИЦЕВЫХ ГРАНЕЙ

Р ассмотрим многогранник ( рис. 51) и решим задачу

в идимости граней аналогично задаче освещенности,

рассмотренной выше. n₁ n₂

Е сли вектор нормали какой-либо

г рани n составляет с вектором L, задающим n₃

н аправление проецирования, тупой угол,

т о эта грань не видна и называется n₄

н елицевой. L

Когда соответствующий угол является

острым, грань называется лицевой. Рис. 51

В случае параллельного проецирования имеем для лицевой грани

(n,L)  0

При центральном проецировании с центром в точке C вектор проецирования для произвольной точки P будет равен

L = C – P

Условие видимости для любой точки P грани то же

(n,L)  0

Знак скалярного произведения не зависит от выбора тоски p, а определяется тем, в каком полупространстве относительно плоскости, содержащей данную грань, лежит центр проецирования.

Для выпуклого многогранника удаление нелицевых граней решает задачу удаления невидимых ребер.

Рассмотрим подробнее алгоритмы.

УДАЛЕНИЕ НЕВИДИМЫХ ЛИНИЙ

1. Алгоритм Робертса предназначен для фигур, у которых каждая грань – выпуклый многоугольник:

1. отбрасываются все ребра, обе образующие грани которых являются нелицевыми;

2. проверяется каждое из оставшихся ребер со всеми гранями многогранника на закрывание. При этом возможны три случая (см. рис.52):

а ) б) в)

Рис. 52

а) грань не закрывает ребро (рис.52а);

б) грань полностью закрывает ребро, тогда ребро удаляется из списка видимых (рис.52а);

в) грань частично закрывает ребро, тогда оно разбивается на несколько частей, из которых видимые части включаются в список ребер на место удаленного ребра (рис.52а).

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

1. Алгоритм Аппеля применим для произвольного многогранника.

Введем понятие количественной невидимости точки – это количество лицевых граней, закрывающих ее.

Точка является видимой только в случае, если ее количественная невидимость равна нулю. A B

К онтурная линия – это ломанная,

состоящая из ребер, для которых одна D C

и з граней является лицевой, а другая – нелицевой.

Например, линия ABCC’D’DEE’A’A (см. рис.53). E

Количественная невидимость точек ребра A’ B’

и зменяется на единицу при прохождении ребра

позади контурной линии. D’ C’

E’

Рис. 53

Алгоритм определения видимости ребер произвольного многогранника:

а) берется какая-либо его вершина и определяется ее количественная невидимость;

б) просматривается изменение количественной невидимости вдоль каждого из ребер, выходящих из данной вершины, причем ребра проверяются на прохождение позади контурной линии, и в соответствующих точках количественная невидимость изменяется. Части отрезка, для которых количественная невидимость равна нулю, изображаются;

в) выполняется переход к следующей вершине и возврат к п.а);

г) если ребро выходит из вершины, принадлежащей контурной линии, проверяется, не закрывается ли это ребро одной из граней (например, линия DD’).

Так как у реальных многогранников количество ребер, входящих в контурную линию, намного меньше общего числа ребер, то алгоритм Аппеля более эффективен, чем алгоритм Робертса.

Удаление невидимых граней

Метод z-буфера (буфера глубины)

Каждому пикселю p(x,y) картинной плоскости, кроме цвета, хранящегося в видеопамяти, сопоставляется расстояние его от картинной плоскости вдоль направления проецирования z (его глубина). Вначале массив глубин инициализируется со значением +.

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

АЛГОРИТМЫ УПОРЯДОЧЕНИЯ

Введем понятие сцены как комплекса изображений пространственных фигур на экране дисплея (или в кадре), т.е. на картинной плоскости.

Понятие сцены включает в себя в общем случае:

1. предметы (пространственные объекты),

2. освещение (цвет, число источников света и их характеристики),

3. фон, т.е. плоские объекты, заполняющие пространство экрана, не заполненное предметами.

Для корректного заполнения сцены требуется упорядочить грани изображаемых объектов, чтобы более дальние грани выводились раньше, чем более близкие. Но бывают случаи, когда заданные грани нельзя упорядочить (см. рис. 54), тогда производится разбиение одной

и ли нескольких граней на фрагменты, которые

м ожно упорядочить.

Рис.54

1. Метод сортировки по глубине.

Наиболее простой – сортировка по минимальному расстоянию до картинной плоскости вдоль направления проецирования с последующим выводом их в порядке приближения.

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

Рассмотрим алгоритм проверки для случая параллельного проецирования вдоль оси Оz.

Перед выводом грани P следует убедиться, что никакая другая грань Q, проекция которой на ось Оz пересекается с проекцией грани Р, не будет закрываться гранью Р.

Алгоритм состоит из проверок:

а) пересекаются ли проекции этих граней на ось Ox?

б) пересекаются ли их проекции на ось Oy?

в) находится ли грань P по другую сторону от плоскости, проходящей через грань Q, чем начало координат (наблюдатель)?

г) находится ли грань Q по ту же сторону от плоскости, проходящей через грань P, что и начало координат (наблюдатель)?

д) пересекаются ли проекции этих граней на картинную плоскость?

Если хотя бы на один из этих вопросов получен отрицательный ответ, то считаем, что эти грани P и Q упорядочены верно, и сравниваем P со следующей гранью; в противном случае считаем, что эти грани нужно поменять местами, для чего дополнительно проверяются тесты:

е) находится ли грань Q по другую сторону от плоскости, проходящей через грань P, чем начало координат?

ж) находится ли грань P по ту же сторону от плоскости. проходящей через грань Q, что и начало координат?

Если ни один из тестов не позволяет с уверенностью решить, какую из двух граней нужно выводить раньше, то одна из них разбивается на две части плоскостью, проходящей через другую грань. Вопрос об упорядочении оставшейся грани и частей разбитой грани решается легко.

2.Метод двоичного разбиения пространства.

Рассмотрим некоторую плоскость в объектном пространстве. Она разбивает множество всех изображаемых граней на два непересекающихся подмножества (кластера) в зависимости от того, в каком полупространстве относительно плоскости лежат эти грани. Будем считать, что плоскость не пересекает ни одну из этих граней.

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

Многократно применяя ту же технику для упорядочения граней внутри каждого кластера (см. рис.55 – плоскости П, Ш, IV), добиваемся того, что в каждом кластере оказывается не более одной грани.

В качестве разбивающей плоскости часто используют плоскость, проходящую через одну из граней. При этом множество всех граней разбивается на 4 класса (лежащих на плоскости, пересекающих ее, лежащих в положительном полупространстве и лежащих в отрицательном полупространстве). Затем строится дерево разбиения пространства. Когда дерево построено, осуществляется построение изображения в зависимости от используемого проецирования (параллельного или центрального).

3. Метод построчного сканирования.

Все изображение на картинной плоскости представляется как ряд горизонтальных (или вертикальных) линий пикселей (см. рис.56). Рассматривается сечение сцены плоскостью, проходящей через линию пикселей и центр проецирования. Пересечением этой плоскости с объектами сцены будет множество непересекающихся отрезков, которые необходимо спроецировать.

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

1. Алгоритм Варнака.

Этот алгоритм основан на разбиении картинной плоскости на части, для каждой из которых задача видимости решается достаточно просто (см. рис.57).

В идимая часть картинной плоскости

д елится на 4 части. Далее:

1. е сли часть полностью закрыта проекцией

б лижайшей грани или не содержит изображе-

н ие ни одной грани, то решение очевидно;

1. и наче часть делится на 4 более мелких

части и переходим к п.1;

1. процесс разбиения продолжается с

точностью до пикселя. Рис.57

ГЕОМЕТРИЧЕСКИЕ СПЛАЙНЫ

Теория сплайнов разработана в трудах Шенберга с 1946 года. Это методы криволинейной аппроксимации описания поверхности по заданным точкам.

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

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

Рассмотрим наиболее простые и наиболее часто используемые сплайны, в построении которых используются кубические (в случае одномерных сплайнов – сплайновых кривых) и бикубические (в случае двумерных сплайнов – сплайновых поверхностей) многочлены.

Общая формулировка задачи: по заданному массиву точек на плоскости (2D) или в пространстве (3D) построить кривую, либо проходящую через все точки (задача интерполяции), либо проходящую вблизи от этих точек (задача сглаживания).

Задача интерполяции

Пусть задан набор точек на плоскости (x_i,y_i), i = 0,1,…,m, таких, что x_1<x_2<…<x_m-1<x_m, т.е. пронумерованы в порядке возрастания абсцисс (см. рис.58).

Известно, что существует интерполяционный

п

(x₀,y₀) (x_m,y_m)

 

 



 

олином Лагранжа

г
де

г
рафик которого проходит через

все точки (x_i,y_i). Рис.58

Полином однозначно описывается своими коэффициентами, легко программируется, но у его использования есть недостатки:

• степень полинома на 1 меньше числа заданных точек, и чем больше точек, тем выше степень полинома;

• изменение координат одной точки требует полного перерасчета коэффициентов полинома.

Компромиссом является кусочная интерполяция. Простейший случай – кусочно-линейная, затем – кусочно-квадратичная (по трем точкам) и кусочно-кубическая (по четырем точкам).

Замечено, что если соединить точки стальной полосой, то получится плавная линия, достаточно корректно описываемая кусочно-кубической функцией, которая называется сплайн-функцией y = S(x) или сплайном.

Сплайн обладает следующими свойствами:

1. график функции проходит через каждую точку заданного массива

S(x_i) = y_i, i = 0,1,…,m;

1. на каждом из отрезков

[x_i, x_i+1], i = 0,1,…,m-1

функция является многочленом третьей степени

1. на всем отрезке задания [x₀,x_m] функция S(x) имеет непрерывную производную.

Так как на каждом из отрезков [x_i,x_i+1] сплайн описывается четырьмя коэффициентами, то для его полного построения на всем отрезке задания необходимо найти 4m чисел. Эти коэффициенты вычисляются, исходя из условий непрерывности сплайна во всех внутренних узлах x_i, i = 1,…,m-1, а также непрерывности первой и второй производных в этих узлах.

Д
ля пространственной задачи аналогично получаем бикубический интерполяционный сплайн

В этом случае имеется тот же недостаток – изменение одной точки требует перерасчета всех коэффициентов.

ЗАДАЧА СГЛАЖИВАНИЯ

Первое преимущество – расширение класса функций, второе преимущество – отказ от однозначности проецирования искомой кривой на координатную ось или поверхности – на координатную плоскость.

Рассмотрим пространственную задачу. Используем параметрическое описание кривой, которую назовем -кривой

x = x(t), y = y(t), z = z(t)

a  t  b,

где x(t), y(t), z(t) – функции, непрерывные на отрезке [a,b].

Е
сли считать a = 0, b = 1, что достигается заменой

и
ли в векторной форме r = r(t), 0  t  1,

Параметр t задает ориентацию параметризованной -кривой, т.е. порядок прохождения точек при монотонном увеличении t;

-кривая называется регулярной кривой, если r’(t)  0 в каждой ее точке, т.е. существует касательная и эта касательная меняется непрерывно вслед за перемещением точки вдоль кривой (см. рис.59).

Е
диничный вектор касательной к -кривой описывается выражением



(x,y,z)



T

Если потребовать наличие второй

производной, то можно определить вектор

кривизны -кривой

модуль которого характеризует степень

ее отклонения от прямой. В частности,

если  - отрезок прямой, то k = 0. Рис.59

Рассмотрим виды сглаживающих кривых.

Пусть в пространстве задан упорядоченный набор точек, определяемых векторами V₀,V₁,…,V_m (см.рис.60) Ломанная, проходящая через эти точки, называется контрольной ломанной, порождаемой множеством

V

V₀ V₁

V₃

V_m

Рис.60

= {V₀,V₁,…,V_m}

1. Кривая Безье – это кривая,

о пределяемая
уравнением

0  t  1,

г
де

Кривая Безье обладает следующими свойствами:

• является гладкой,

• начинается в точке V₀ и заканчивается в точке V_m, касаясь при этом отрезков ломанной;

• ф
  ункциональные коэффициенты

п
ри вершинах V_i, i = 0,1,…,m суть универсальные многочлены (многочлены Бренштейна); они неотрицательны и их сумма равна 1.

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

П
ри m = 3 получаем элементарную кубическую кривую Безье, определяемую четверкой точек V₀,V₁,V₂,V₃ и описываемую параметрическим уравнением

0  t  1,

или в матричной записи

r(t) = V M  T

0  t  1,

г
де

Матрица M называется базисной матрицей Безье.

П
орядок точек в заданном наборе существенно влияет на вид элементарной кривой Безье (см. рис.61).

Основные недостатки кривых Безье:

• степень функциональных коэффициентов напрямую связана с количеством точек в заданном наборе m;

• при добавлении хотя бы одной точки в заданный набор необходимо провести полный перерасчет функциональных коэффициентов в параметрическом уравнении кривой;

• изменение хотя бы одной точки приводит к заметному изменению вида всей кривой.

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

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

Составная кривая называется:

• G¹-геометрически непрерывной, если вдоль этой кривой единичный вектор ее касательной изменяется непрерывно;

• G²-геометрически непрерывной, если вдоль этой кривой изменяется непрерывно еще и единичный вектор кривизны.

Таким образом составная кубическая кривая Безье представляет собой объединение элементарных кубических кривых Безье r₁,…,r_m таких, что

r_i(1) = r_i+1(0) , i = 0, …,m-1,

где r = r_i(t), 0  t  1, - параметрические уравнения кривой.

Возможны варианты вида составной кривой Безье, определяемой набором вершин V₀,V₁,…,V_m:

1. G¹-геометрически непрерывная, у которой каждые три точки

V_3i-1,V_3i,V_3i+1 лежат на одной прямой;

1. замкнутая G¹-геометрически непрерывная, у которой совпадают первая и последняя точки V₀ = V_m и три точки V_m-1,V₀=V_m,V₁ лежат на одной прямой;

2. G²-геометрически непрерывная, у которой каждые 5 точек

V_3i-2,V_3i-1,V_3i,V_3i+1,V_3i+2 лежат в одной плоскости.

1. В-сплайновая кривая отличается от кривой Безье коэффициентами.

Рассмотрим на примере кубических многочленов. По набору точек V₀,V₁,V₂,V₃ определяем элементарную кубическую кривую при помощи параметрического векторного уравнения

0  t  1

или в матричной форме

r(t) = V M T

г
де

Функциональные коэффициенты в уравнении r(t) неотрицательны, в сумме составляют 1 и универсальны (не зависят от точек).

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

Составная кубическая В-сплайновая кривая, задаваемая параметрическим уравнением

r = r_i(t), 0  t  m-2,

и определяемая набором точек V₀,V₁,…,V_m-1, m  3, представляет собой набор (m-2) элементарных кубических B-сплайновых кривых ₃,…,_m, описываемых уравнениями вида

О
бласть изменения параметра t и расположение на ней точек, соответствующих стыковочным узлам, может быть произвольным. Простейший случай – это равномерная параметризация с равноотстоящими целочисленными узлами.

Такая составная кубическая В-сплайновая кривая является G²-геометрически непрерывной и лежит в объединении (m-2) выпуклых оболочек, порожденных последовательными четверками точек заданного набора.

Можно добавлять к заданному набору точки, тогда получим новую составную В-сплайновую кривую.

СПЛАЙНОВЫЕ ПОВЕРХНОСТИ

Регулярной поверхностью называется множество точек M(x,y,z) пространства, координаты которых определяются из параметрических уравнений

x = x(u,v), y = y(u,v), z = z(u,v), (u,v)  D,

где x(u,v), y(u,v), z(u,v) – гладкие функции своих аргументов,

D – некоторая область на плоскости параметров u и v,

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

Такая поверхность описывается векторным уравнением

r(u,v) = (x(u,v), y(u,v), z(u,v))

(u,v)  D,

Пусть заданы точки в пространстве V_ij , i = 0,1,…,m, j = 0,1,…,n.

Соединяя соответствующие вершины прямолинейными отрезками, получим контрольный многогранник (точнее, опорный граф) множества V.

Сглаживающая поверхность описывается параметрическими уравнениями вида

т

.е. тензорным произведением, или в виде

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

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

Построение сглаживающей поверхности производится на базе построения элементарных фрагментов. Рассмотрим бикубические сплайновые поверхности как наиболее часто используемые, у которых функциональные коэффициенты a_i(u) и b_j(v) – суть многочлены третьей степени относительно соответствующих переменных (кубические многочлены).

Требуется задать набор 16-ти точек

V_ij , i = 0,1,2,3, j = 0,1,2,3,

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

1. Элементарная бикубическая поверхность Безье

v

1

1. u

Рис.62

т.е. область изменения параметров и представляет собой единичный квадрат (см. рис.62 ), или в матричной форме

Э
лементарная бикубическая поверхность Безье наследует многие свойства кубической кривой Безье:

• лежит в выпуклой оболочке порождающих точек;

• является гладкой поверхностью;

• упирается в точки V₀₀, V₃₀, V₀₃, V₃₃, касается исходящих из них отрезков контрольного графа заданного набора точек.

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

1. Элементарная B-сплайновая поверхность

ф
ункциональные коэффициенты определяются аналогично В-сплайновым кривым, т.е.

и
ли в матричной форме, аналогично поверхности Безье

r(u,v) = U^T M^T W M V,

где М – базисная матрица кубического В-сплайна.

Основные свойства, наследуемые от элементарной В-сплайновой кривой:

• является гладкой поверхностью;

• лежит в выпуклой оболочке, порождающих ее 16-ти вершин;

• “повторяет” контрольную многогранную поверхность.

Более сложные поверхности сглаживаются с помощью построения составных бикубических В-сплайновых поверхностей, которые наиболее эффективны при использовании равномерных узлов i, j на прямоугольнике

[0,m][0,n], i = 0,1,…m-1; j = 0,1,…,n-1.

ЛИТЕРАТУРА

1. Аммерал Л. Машинная графика на языке Си. в 4-х книгах.- М.: Сол Систем, 1992.

2. Боресков А.В. и др. Компьютерная графика: первое знакомство./ Под ред. Е.В.Шикина. – М.: Финансы и статистика, 1996. – 176 с.

3. Борзенко А.Е. IBM PC: устройство, ремонт, модернизация М.: ТОО «Компьютер Пресс»,1997.-344с.

4. Гилой В. Интерактивная машинная графика М.: Мир, 1982.- 380 с.

5. Иванов В.П., Батраков А.С. Трехмерная компьютерная графика./ Под ред. Г.М. Полищука М.: Радио и связь, 1995.-224 с.

6. Ласло М. Вычислительная геометрия и компьютерная графика на С++.- М.: «Изд. БИНОМ», 1997.- 304 с.

7. Ньюмен У., Спрулл Р. Основы интерактивной графики. - М.: Мир, 1985.- 573 с.

8. Смирнов С.А. Проективная геометрия. - М.: Недра, 1976.- 224 с.

9. Томпсон Н. Секреты программирования трехмерной графики для Windows95. - СПб.: Питер, 1997.

10. Шикин А.В., Боресков А.В. Компьютерная графика. Динамика, реалистические изображения. - М.: Диалог-МИФИ, 1996.- 288 с.

11. Шлихт Г.Ю. Цифровая обработка цветных изображений. - М.: изд. ЭКОМ, 1997.-336с.

84

Характеристики

Список файлов лекций