Долгая М.В. Конспект лекций по дисциплине Основы компьютерной графики

Подождите немного. Документ загружается.

перспективы» обратно пропорционален расстоянию между глазом и объектом. Опишем

координаты центра проектирования в сферических координатах.

ϕρ

θϕρ

cos

sinsin

cossin

Мировая система координат правосторонняя, а видовая система координат, т.е. система

координат, центром которой является центр проектирования или точка наблюдения –

левосторонняя.

Рисунок 3.4 – Определение расстояния до картинной плоскости

Расстояние d определяется из пропорции

картины размеробъекта размер

А, следовательно, расстояние от наблюдателя до картинной плоскости

объекта размер

картины размер

=d .

Объект

КАРТИННАЯ

Лекция 4. АЛГОРИТМЫ РАСТРОВОЙ ГРАФИКИ

4.1 АЛГОРИ

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

Поскольку экран растрового дисплея с электронно-лучевой трубкой можно рассматривать как

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

непосредственно провести отрезок из одной точки в другую. Процесс определения пикселей,

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

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

бражения он известен как преобразование

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

отрезков выбор растровых элементов очевиден. При любой другой ориентации выбрать нуж-

ные пикселы труднее, что показано на рис. 4.1.

Постоянная вдоль всего отрезка яркость достигается лишь при проведении

горизонтальных, вертикальных и наклоненных под углом 45° прямых. Для всех других

ори

ентации разложение в растр приведет к неравномерной яркости, как это показано на рис. 4.1.

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

соседними пикселями для отрезка под углом 45° больше, чем для вертикальных и горизонтальных

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

Обеспечение о

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

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

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

использование целой арифметики, а также реализация алгоритмов на аппаратном или

микропрограммном уровне.

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

используется по

шаговый метод. Приведем пример подобного алгоритма:

Простой пошаговый алгоритм

позиция = начало

1 if позиция — конец < точность then 4

if позиция > конец then 2

if позиция < конец then 3

2 позиция = позиция — шаг goto 1

3 позиция = позиция + шаг до to l

4 finish

Простой алгоритм разложения отрезка в растр, описанный в следующем разделе,

иллюстрирует применение пошаговых методов.

4.2 ЦИФРОВОЙ ДИФФЕРЕНЦИАЛЬНЫЙ АНАЛИЗАТОР

Один из методов разложения отрезка в растр состоит в решении дифференциального

уравнения, описывающего этот процесс. Для прямой линии имеем

Решение представляется в виде

где x

, и x

— концы разлагаемого отрезка и у

— начальное значение для

очередного шага вдоль отрезка. Фактически уравнение (2.1) представляет собой рекуррентное

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

для разложения в растр отрезков, называется цифровым дифференциальным анализатором (ЦДА).

В простом ЦДА либо Δx, либо Δу (большее из приращений) выбирается в качестве единицы

растра. Ниже приводится п

ростой алгоритм, работающий во всех квадрантах:

Процедура разложения в растр отрезка по методу цифрового

дифференциального анализатора (ЦДА)

предполагается, что концы отрезка (x

) и (x

) не совпадают

Integer — функция преобразования вещественного числа в целое. Примечание: во многих

реализациях функция Integer означает взятие целой части, т. е. lnteger(—8.5) = —9, а не —8.В

алгоритме используется именно такая функция. Sign — функция, возвращающая —1, 0, 1 для

отрицательного, нулевого и положительного аргумента соответственно

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

if abs(x

– x

) >= abs(y

– y

) then

Длина = abs(x

– x

) else

Длина = abs(y

– y

)

end if

полагаем большее из приращений

x или

y равным единице раст-

ра

Δх = (x

– x

)/Длина

Δу = (y

– y

)/Длина

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

делает алгоритм пригодным для всех квадрантов

х = x

+ 0.5 * Sign(Δx)

у = y

+0.5 *Sign(Δy)

начало основного цикла

i = 1

while (i <= Длина)

Plot (lnteger(x), lnteger(y))

x = x +

у = у +

i = i +1 end while finish

4.2 АЛГОРИТМ БРЕЗЕНХЕМА

Хотя алгоритм Брезенхема был первоначально разработан для цифровых графопостроителей,

однако он в равной степени подходит и для использования растровыми устройствами с ЭЛТ.

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

работы одна из координат — либо X

, либо У (в зависимости от углового коэффициента) —

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

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

Такое расстояние мы назовем ошибкой.

Алгоритм построен так, что требуется проверять лишь знак этой ошибки. На рис. 4.2 это

иллюстрируется для отрезка в первом окт

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

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

коэффициент отрезка из точки (0, 0) больше чем 1/2, то его пересечение с прямой X = 1 будет

расположено ближе к прямой Y = 1, чем к прямой Y = 0. Следовательно, точка растра (1,1) лучше

ап

проксимирует ход отрезка, чем точка (1, 0). Если угловой коэффициент меньше 1/2, то верно

обратное

Рисунок 4.2

Основная идея алгор

итма Брезенхема

Инициировать ошибку значением 1/2

Для углового коэффициента, равного 1/2, нет какого-либо предпочтительного выбора. В

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

Подобная ситуация иллюстрируется рис. 4.3, где отрезок с тангенсом угла наклона 3/8 сначала

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

(0,1)

(1,0)(1,0)

(1,1)

ошибкаошибка

)0(

)0(1/

<<ΔΔ≤

≥≤ΔΔ≤

ошибкаxy

Рисунок 4.3 – График ошибки в алгоритме Брезенхема

Также иллюстрируется вычисление ошибки при представлении отрезка дискретными

пикселями. Так как желательно проверять только знак ошибки, то она первоначально устанав-

ливается равной — 1/2. Таким образом, если угловой коэффициент отрезка больше или равен

1/2, то величина ошибки в следующей точке растра с ко

ординатами (1, 0) может быть

вычислена как

где m — угловой коэффициент. В нашем случае при начальном значении ошибки —1/2

Так как е отрицательно, отрезок пройдет ниже середины пикселя. Следовательно, пиксель на том

же самом горизонтальном уровне лучше аппроксимирует положение отрезка, поэтому Y не увели-

чивается. Аналогично вычисляем ошибку

в следующей точке растра (2, 0). Теперь е положительно, а значит, отрезок пройдет выше средней

точки. Растровый элемент (2, 1) со следующей по величине координатой Y лучше аппроксимирует

положение отрезка. Следовательно, Y увеличивается на единицу. Прежде чем рассматривать

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

Заметим, что пересечение вертикальной прямой х = 2 с заданным отрезком лежит на 1/4 ниже

прямой У = 1. Если же перенести отрезок 1/2 вниз, мы получим как раз величину —3/4. Продол-

жение вычислений для следующего пикселя дает

Так как е отрицательно, то у не увеличивается. Из всего сказанного следует, что ошибка — это

интервал, отсекаемый по оси У рассматриваемым отрезком в каждом растровом элементе (относи-

тельно — 1/2).

Приведем алгоритм Брезенхема для первого октанта, т. е. для случая 0 <= Δу <= Δ

У.

1 0 2 3

0.5

3.1. Ал

горитм Брезенхема разложения в растр отрезка для первого октанта

предполагается, что концы отрезка (x

) и (x

) не совпадают

Integer — функция преобразования в целое

х, у, Δх, Δу — целые

е — вещественное

инициализация переменных

х = х

у =

Δх = x

– x

У = y

– y

инициализация е с поправкой на половину пиксела

е = Δу/Δх - 1/2

начало основного цикла

for i = 1 to Δх Plot (х, у)

while (е >= 0)

у = у + 1

е = е — 1

end while

X = X + 1

е = е + Δу/Δх

next i

finish

ЛЕКЦИЯ 5. РАЗЛОЖЕНИЕ ОКРУЖНОСТИ В РАСТР

ПО АЛГОРИТМУ БРЕЗЕНХЕМА

Hii

mxx

(1)

Hi i

mx yR=++−

Dii

mxx

=−

222

(1)(1)

Di i

mx y R=++−−

Vii

mxx

=−

Рисунок 5.1 В растр раскладывается

первый октант, а потом различным

образом отображается

Рисунок 5.2 При построении

окружности возможен выбор трех

направлений – горизонтального,

вертикального и диагонального

mH,

mV, mD

((1)

Vii

mxy R=+−−

Рисунок 5.3 – Возможные варианты пересечения окружностью точек растра

222

(1)(1)

0(12.)

ix y R

адиус большедиагональной точки ый и ой вар

Δ= + + − −

Δ< −

=−

<→

≥→

{

}

22 2 22

222 22

222

(1) (1)( 1)

(2 1) 2( 1) 2( 1) 2 2 1

221

ii i i

iii i

xyRx y R

yxyRy

=++−−++ −−=

=++−+++ −−=

=± + = + + − − + −=

=Δ+ −

так для 1го случая

221

Δ+ −

=−

<→

= - для второго случая

0(34.)i

адиус большедиагональной точки ий и ый варΔ> −

dVD

mmm

<=−

<→

≥→

3ий случай

22 2 22

(1) (1)( 1)

ii i i

yRx y R

=+−−−++ −−

22 2 22

(1) (1)(1)

'2( )1

ii i i

yRx yR

=− − − + − + + − −

=Δ− −

4ый случай

<→

5ый случай

imΔ= →

Рекуррентное отношение для

Hii

mxx

iii

Δ=Δ+ +

Dii

mxx

=−

111

222

iii i

+++

Δ=Δ+ − +

Vii

mxx

=−

iii

Δ=Δ− +

Лекция 6. ПРОБЛЕМЫ УДАЛЕНИЯ НЕВИДИМЫХ ПОВЕРХНОСТЕЙ

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

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

этапом совершенствования изображения является удаление невидимых поверхностей. Задача эта

непроста и существует множество различных способов ее реализации. Для упрощения в

рассмотрение вносятся выпуклые тела, ограниченные плоскими гранями.

Задача удаления невидимых по

верхностей состоит в нахождении преобразования

отображающего множество объекта во множество видимых частей в двухмерном пространстве.

Объект определяется, как множество координат плюс множество отношений,

специфицирующих его топологию.

В формализованном виде алгоритмы удаления невидимых поверхностей (АУНП)

можно представить следующим образом:

АУНП = ( O, S, I, ϕ, σ ) ,

где O - множество объектов в трехмерном пространстве;

- множество видимых отрезков в двухмерном пространстве;

I - множество промежуточных представлений;

ϕ - множество функций перехода;

σ - функция стратегии.

ϕ = (PM, IS, CT, DT, VT),

где PM – преобразования проецирования (область определения – трехмерное пространство,

область значений - двухмерное;

IS - функции, позволяющие определить точки пересечения (области определения и

значений совпадают);

CT – тест принадлежности, позволяющий определить, принадлежит ли точка поверхности

(область определения и значений – дву

хмерное пространство); результат работы теста - истина

или ложь;

DT – тест глубины, сравнивающий две точки и определяющий, какая из них находится на

большей глубине, то есть дальше от наблюдателя;

VT – тест видимости или самозаслонения, определяющий невидимые грани объекта;

результат работы теста – истина или ложь.

Функция стратегии определяет порядок применения функций и тестов из мн

ожества ϕ.

6.1 Функции перехода

6.1.1 Перспективные преобразования (PM)

Перспективные преобразования применяются в АУНП либо до удаления невидимых

поверхностей либо после. Критерием является пространство, в котором работает сам

алгоритм. Если идея алгоритма такова, что определение невидимых поверхностей выполняется

в трехмерном пространстве, то проектирование выполняется после работы АУНП. Если

алг

оритм работает на плоскости с проекциями объектов, то естественно, что проецирование их

должно быть реализовано первым, а затем начинает работать АУНП.

6.1.2 Функции пересечений (IS)

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

следующие элементы, для которых определяется пересечение:

- две прямые;

- два отрезка;

- прямая и пл

оскость.

Ниже приведены цели определения точек пересечения в АУНП: