|
Читайте также: |
Устройство цветных кинескопов подобно устройству черно-белых с тем отличием, что обязательно имеется три типа люминофора для красного, зеленого и синего цветов, а также средств для формирования и управления тремя отдельными электронными лучами (в некоторых, скорее экспериментальных цветных кинескопах используется единственный электронный луч).
14. Стандарт GKS
GKS - cтандарт двумерного графического интерфейса, который использует неиерархический нередактируемый формат описания изображений. Изображения строятся путем непосредственного вызова функций графической системы. Каждому примитиву соответствует своя функция. Несколько примитивов вывода могут быть объединены в сегмент, которому присваивается уникальный идентификатор. Сегменты размещаются в общей памяти для повторного использования. Изменять содержимое сегментов не допускается. Cпециальные функции позволяют осуществлять перенос, масштабирование, поворот и другие операции над сегментами. Геометрическая информация подвергается преобразованиям, которые связывают три системы координат: мировые координаты, нормированные координаты (NDC) и координаты устройства. Стандарт поддерживает несколько классов логических устройств ввода: ввод координат (позиции), ввод последовательности позиций, выбор альтернативы, указание объекта, ввод строки и ввод числа. Каждое логическое устройство ввода может работать в режимах: запрос, опрос, событие. В качестве примера реализации можно привести библиотеку SunGKS.
Дальнейшее развитие стандарт GKS получил в стандарте GKS- 3D (ISO IS 8805 - Graphical Kernel System for tree dimensions). GKS-3D - стандарт трехмерного графического интерфейса, который использует все возможности стандарта GKS и содержит некоторые дополнительные функции для работы с трехмерной графикой. GKS-3D поддерживает трехмерные примитивы, трехмерный ввод, трехмерные сегменты и обеспечивает работу со скрытыми линиями и поверхностями. Стандарт обеспечивает трансформацию трехмерных мировых координат в координаты двумерного устройства отображения. Цепочка преобразований связывает четыре системы координат: мировые координаты, нормированные координаты (NDC-3), нормированные координаты проекции (NPC) и координаты устройства.
15. Стандарт PHIGS+
PHIGS+ - расширение стандарта PHIGS, которое содержит дополнительные процедуры для получения реалистичных изображений трехмерных объектов. Данные функции позволяют получать блики, тени и другие эффекты освещения предметов. На платформе Sun реализована библиотека SunPHIGS, которая включает в себя возможности PHIGS и PHIGS+.
16. Виды систем координат
Координатная система - это совокупность правил, по которой каждой точке ставится в соответствие набор чисел (координаты). Число координат, которые требуются для определения точки, называется размерностью пространства.
В GKS предусмотрены следующие виды координат:
- абсолютные,
- относительные,
- координаты пользователя,
- мировые,
- физические,
- нормированные.
Абсолютная координата определяет позицию точки по отношению к заданной системе координат.
Относительная координата определяет позицию точки по отношению к другой (например, предыдущей) точке.
Координаты пользователя - не зависит от конкретных устройств и задается пользователем.
Мировая координата - независимая от устройства декартова координата виртуального пространства, используемая в прикладной программе при задании графических данных.
Физические координаты - задаются в системе координат графического устройства (пространство визуализации). Она всегда нормирована размером устройства.
Нормализованная координата - задается в независимой от графического устройства системе координат и нормированную относительно некоторого диапазона, обычно от 0 до 1.
17. Принципы аффинных преобразований на плоскости. Поворот.
Помимо декартовых систем координат, используются также афинные, которые определяются следующим преобразованием.
Пусть исходные координаты, а преобразованные - e, h.
Тогда
e =
h =,
причем
det ¹ 0.
Здесь вектор [] определяет сдвиг, а матрица
определяет поворот и растяжение.
Афинное преобразование переводит прямую в прямую, параллельные прямые - в параллельные прямые, а пересекающиеся - в пересекающиеся. Сохраняется топология графического изображения фигур (сохраняется отношение длин отрезков, площадей и объём).
Аналогично выводится афинное преобразование в трехмерном пространстве.
В машинной графике широко применяются также однородные координаты, которые позволяют представить n-мерный объём в n+1-мерном пространстве путем добавления еще одной координаты - скалярного множителя.
Однородные координаты используются в проективной геометрии, а в машинной графике - это удобный прием, позволяющий линеаризовать перспективные изображения.
Пусть на плоскости имеется система афинных координат и в ней точка. Любая тройка чисел, пропорциональная тройке (X,Y,1) называется однородными координатами точки P, определенными данной афинной системой координат.
Отсюда следует, что однородным представлением может быть любая тройка чисел, полученная умножением вектора (X,Y,1) на скалярный множитель. Например 
при h®0 стремится в начало координат. Аналогичные действия производятся и в 3Д пространстве.
С использованием однородных координат афинные преобразование формально может быть представлено в виде:
 | | ||||||||||
 |  | | |||||||||
 | |||||||||||
e x
h = y
1 0 0 1 1
или X = AX, где X и X - соответственно преобразованный и исходный векторы, A - матрица преобразований.
Эта форма представления позволяет удобно описать геометрические преобразования.
Поворот на угол j относительно начала координат
 | |
cos j -sin j 0
A = sin j cos j 0
0 0 1
18. Принципы аффинных преобразований на плоскости. Перенос.
Перенос
1 0 - перенос вдоль X
A = 0 1 - перенос вдоль Y
0 0 1
19. Принципы аффинных преобразований на плоскости. Масштабирование.
Масштабирование
- масштаб по X
- масштаб по Y
20. Кодирование изображений. Фильтрация
Понятие фильтрации в данном случае весьма обширно, и включает в себя любое преобразование графической информации. Фильтрация может быть задана не только в виде формулы, но и в виде алгоритма, его реализующая. Человек запоминает графическую информацию, в основном, в виде трех ее составляющих
Низкочастотные составляющие изображения. Они несут информацию о локализации объектов, составляющих изображения. Эта составляющая наиболее важна, так как связка глаз - мозг уделяет ей первостепенное внимание.
Высокочастотные составляющие изображения. Они отвечают за цветовые перепады - контуры изображения. Увеличивая их, мы повышаем резкость изображения.
Текстуры изображения. Чтобы понятно объяснить, что это такое проведем небольшой эксперимент. Расслабьтесь, вспомните интерьер вашего дома, например, письменный стол. Вы знаете его очертания, местоположение, цвет - это низкочастотные характеристики, вспомнили его заостренные углы, небольшую царапину где-нибудь ближе к его кромке - это высокочастотные составляющие. Также Вы знаете, что стол деревянный, но не можете в точности рассказать обо всех мельчайших деталях его поверхности, хотя общие характеристики (коричневый с темными впадинами, две области расхождения концентрических эллипсов от сучков) - наверняка. В данном случае в скобках - описание текстуры. Можно трактовать текстуру как характеристику участков в контурах изображения.
Будем рассматривать фильтры в виде квадратной матрицы A. Пусть исходное изображение X, а получаемое как результат фильтрации - Y. Для простоты будем использовать матрицы 3x3:
Рекурсивными фильтрами первого рода будут такие фильтры, выход Y которых формируется перемножением весовых множителей A с элементами изображения X. Для примера рассмотрим фильтры низких частот:
.
Фильтром низких частот пользуются часто для того, чтобы подавить шум в изображении, сделать его менее резким. Используя фильтр A3, будем получать изображение Y следующим образом:
Выход фильтра второго рода формируется аналогично первому, плюс фильтра B:
Для простоты рассмотрим одномерный фильтр вида: 
:
Рассмотрим и другие фильтры:
Высокочастотные (для подчеркивания резкости изображения):
Для подчеркивания ориентации:
Подчеркивание без учета ориентации (фильтры Лапласа):
.
Корреляционный:
,где
- коэффициенты корреляции между соседними элементами по строке (столбцу). Если они равны нулю то отфильтрованное изображение будет совпадать с исходным, если они равны единице, то фильтр будет эквивалентен лапласиану. При обработке изображений очень часто используют последовательность фильтров: низкочастотный + Лапласа. Часто используют и нелинейную фильтрацию. Для контрастирования перепадов изображения используют градиентный фильтр:
, или его упрощенный вид:
.
Еще один часто используемый нелинейный фильтр - Собела:
A0 ... A7 - входы, yi,j - результат фильтрации.
Рекурсивная версия:
где B0... B7 - выход отфильтрованного изображения.
Нелинейная фильтрация - достаточно загадочная область цифровой обработки сигналов, многое еще в ней пока не изучено. Важность же ее не вызывает сомнений, потому, что окружающий нас мир по своей сути не так линеен, как порою хочется его нам интерпретировать.
21. Кодирование изображений. Сжатие
Изображения, в машинном представлении, - двумерная матрица N на M, где N - его ширина, M - высота. При сканировании обычно используют разрешение от 72 до 2400 dpi (dots per inch - точек на дюйм). Наиболее часто - 300 dpi. Если взять лист бумаги 21/29 см с изображением и отсканировать его в RGB Truecolor, то несжатое изображение будет занимать ~27300000 байтов или 26 Мбайт. Обычно в базах данных применяют изображения порядка от 320x240 до 640x480. Но и они занимают 76 до 900 Кбайт. А что, если таких изображений сотни, тысячи? В данном разделе рассмотрим методы сжатия. Они применительны для любых массивов данных, а не только для изображений. О методах сжатия, характерных только для изображений узнаем немного позже. Будем рассматривать статическое сжатие, то есть массив данных для сжатия целиком сформирован. Методы сжатия статического часто подразделяют на последовательное и энтропийное. Последовательное сжатие использует в работе наличие повторяющихся участков. Энтропийное используется с целью сокращения к минимуму избыточности информации. Последовательное применение этих методов позволяет получить хороший результат.
22. Цифровой дифференциальный анализатор
Один из методов разложения отрезка в растр состоит в решении дифференциального уравнения, описывающего этот процесс. Для прямой линии имеем:
или 
Решение представляется в виде
| (1) |
где x1, y1 и x2 , y2 – концы разлагаемого отрезка и yi – начальное значение для очередного шага вдоль отрезка. Фактически уравнение (1.) представляет собой рекуррентное соотношение для последовательных значений y вдоль нужного отрезка. Этот метод, используемый для разложения в растр отрезков, называется цифровым дифференциальным анализатором (ЦДА). В простом ЦДА либо 
, либо 
(большее из приращений) выбирается в качестве единицы растра. Ниже приводится простой алгоритм, работающий во всех квадрантах:
Процедура разложения в растр отрезка по методу цифрового дифференциального анализатора (ЦДА)
предполагается, что концы отрезка (x1,y1) и (x2,y2) не совпадают
Integer – функция преобразования вещественного числа в целое.
Примечание: во многих реализациях функция Integer означает взятие целой части, т.е. Integer (- 8.5) = - 9, а не - 8. В алгоритме используется именно такая функция.
Sign - функция, возвращающая - 1, 0, 1 для отрицательного нулевого и положительного аргумента соответственно.
if abs (x2 -x1 ) ³ abs (y2 - y1 ) then
Длина = abs (x2 - x1 )
else
Длина = abs (y2 - y1 )
end if
полагаем большее из приращений Dx или Dy равным единице растра
Dx = (x2 -x1 ) / Длина
Dy = (y2 - y1 ) / Длина
округляем величины, а не отбрасываем дробную часть
использование знаковой функции делает алгоритм пригодным для всех квадрантов
x = x1 + 0.5 * Sign (Dx)
y = y1 + 0.5 * Sign (Dy)
начало основного цикла
i =1
while (i £ Длина)
Plot (Integer (x), Integer (y))
x = x + Dx
y = y + Dy
i = i + 1
end while
finish
С помощью этого алгоритма получают прямые, вполне удовлетворительного вида, но у него есть ряд недостатков. Во-первых, плохая точность в концевых точках. Во-вторых, результаты работы алгоритма зависят от ориентации отрезка. Вдобавок предложенный алгоритм использует вещественную арифметику, что заметно снижает скорость выполнения.
23. Алгоритм Брезенхема для генерации линии
Алгоритм Брезенхема выбирает оптимальные растровые координаты для представления отрезка. В процессе работы одна из координат - либо x, либо у (в зависимости от углового коэффициента) - изменяется на единицу. Изменение другой координаты (либо на нуль, либо на единицу) зависит от расстояния между действительным положением отрезка и ближайшими координатами сетки. Такое расстояние называется ошибкой.
½ £ Dy £ 1 (ошибка ³ 0)
0 £ Dy/Dx < ½ (ошибка <0)
Инициировать ошибку в – ½
ошибка = ошибка + Dy/Dx
Алгоритм построен так, что требуется проверять лишь знак этой ошибки. На рис.1 это иллюстрируется для отрезка в первом октанте, т. е. для отрезка с угловым коэффициентом, лежащим в диапазоне от нуля до единицы. Из рисунка можно заметить, что если угловой коэффициент отрезка из точки (0,0) больше чем 1/2, то его пересечение с прямой x = 1 будет расположено ближе к прямой у = 1, чем к прямой у = 0. Следовательно, точка растра (1,1) лучше аппроксимирует ход отрезка, чем точка (1,0). Если угловой коэффициент меньше 1/2, то верно обратное. Для углового коэффициента равного 1/2 нет какого-либо предпочтительного выбора. В данном случае алгоритм выбирает точку (1,1).
Быстродействие алгоритма можно существенно увеличить, если использовать только целочисленную арифметику и исключить деление. Т.к. важен лишь знак ошибки, то приняв
можно добиться хорошей скорости выполнения алгоритма.
|
Чтобы реализация алгоритма была полной необходимо обрабатывать отрезки во всех октантах. Когда абсолютная величина углового коэффициента больше 1, y постоянно изменяется на единицу, а критерий ошибки Брезенхема используется для принятия решения об изменении величены x. Выбор постоянно изменяющейся (на +1 или –1) координаты зависит от квадранта (рис. 2).
Алгоритм Брезенхема может быть оформлен в следующем виде.
Алгоритм промежуточной точки
xc- координата x центра
yc- координата y центра
Наклон = 1-r
Y = r
X = -1
Повторять пока (x>y)
{x=x+1;
putpixel(xc+x, yc+y);
putpixel(xc+x, yc+y);
putpixel(xc+x, yc+y);
putpixel(xc+x, yc+y);
putpixel(xc+x, yc+y);
putpixel(xc+x, yc+y);
putpixel(xc+x, yc+y);
putpixel(xc+x, yc+y);
if наклон>0{
наклон=наклон+2*(x-y)+1;
}
else наклон = =наклон+2*x+1;
}
Обобщённый целочисленный алгоритм Брезенхема квадрантов
предполагается, что концы отрезка (x1,y1) и (x2,y2) не совпадают и все переменные - целые.
Функция Sign возвращает - 1, 0, 1 для отрицательного нулевого и положительного аргумента соответственно.
инициализация переменных
x = x1
y = y1
Dx = abs (x2 - x1 )
Dy = abs (y2 - y1 )
s1 = Sign (x2 - x1 )
s2 = Sign (y2 - y1 )
обмен значение Dx и Dy в зависимости от углового коэффициента наклона отрезка
if Dy > Dx then
Врем = Dx
Dx = Dy
Dy = Врем
Обмен = 1
else
Обмен = 0
end if
инициализация 
с поправкой на половину пиксела
= 2 * Dy - Dx
основной цикл
for i = 1 to Dx
Plot (x,y)
While ( ³ 0)
If Обмен = 1 then
x = x + s1
else
y = y + s2
end if
= - 2 * Dx
end while
if Обмен = 1 then
y = y + s2
else
x = x + s1
end if
= + 2 * Dy
next i
finish
Этот алгоритм удовлетворяет самым строгим требованиям. Он имеет приемлемую скорость и может быть легко реализован на аппаратном или микропрограммном уровне.
24. Алгоритм Брезенхема для генерации окружностей
В растр нужно разлагать не только линейные, но и другие, более сложные функции. Разложению конических сечений, т. е. окружностей, эллипсов, парабол, гипербол посвящено значительное число работ.Наибольшее внимание, разумеется, уделено окружности. Один из наиболее эффективных и простых для понимания алгоритмов генерации окружности принадлежит
|
Брезенхему. Для начала заметим, что необходимо сгенерировать только одну восьмую часть окружности. Остальные её части могут быть получены последовательными отражениями, как это показано на рис. 2.3. Если сгенерирован первый октант (от 0° до 45° против часовой стрелки), то второй октант можно получить зеркальным отражением относительно прямой у = x, что дает в совокупности первый квадрант. Первый квадрант отражается относительно прямой x = 0 для получения соответствующей части окружности во втором квадранте. Верхняя полуокружность отражается относительно прямой у = 0 для завершения построения. На рис.3. приведены двумерные матрицы соответствующих преобразований.
Для вывода алгоритма рассмотрим первую четверть окружности с центром в начале координат. Заметим, что если работа алгоритма начинается в точке x = 0, у = R, то при генерации окружности по часовой стрелке в первом квадранте у является монотонно убывающей функцией аргумента x (рис. 2.4). Аналогично, если исходной точкой является y = 0, x = R, то при генерации окружности против часовой стрелки x будет монотонно убывающей функцией аргумента у. В нашем случае выбирается генерация по часовой стрелке с началом в точке x = 0, у = R. Предполагается, что центр окружности и начальная точка находятся точно в точках растра.
Для любой заданной точки на окружности при генерации по часовой стрелке существует только три возможности выбрать следующий пиксел, наилучшим образом приближающий окружность: горизонтально вправо, по диагонали вниз и вправо, вертикально вниз. На рис.2.5 эти направления обозначены соответственно mH, mD, mV. Алгоритм выбирает пиксел, для которого минимален квадрат расстояния между одним из этих пикселов и окружностью, т. е. минимум из
mH = | (xi + 1)2 + (yi )2 – R2 |
mH = | (xi + 1)2 + (yi - 1)2 – R2 |
mH = | (xi)2 + (yi - 1)2 – R2 |
|
| ||||
Вычисления можно упростить, если заметить, что в окрестности точки (xi, yi) возможны только пять типов пересечений окружности и сетки растра, приведенных на рис.2.6.
Разность между квадратами расстояний от центра окружности до диагонального пиксела (xi + 1, yi- 1) и от центра до точки на окружности R2 равна
Как и в алгоритме Брезенхема для отрезка, для выбора соответствующего пикселя желательно использовать только знак ошибки, а не её величину.
При D < 0 диагональная точка (xi + 1, yi- 1) находится внутри реальной окружности, т. е. это случаи 1 или 2 на рис.2.6. Ясно, что в этой ситуации следует выбрать либо пиксел (xi + 1, yi)т. е. mH, либо пиксел (xi + 1, yi- 1), т. е. mD. Для этого сначала рассмотрим случай 1 и проверим разность квадратов расстояний от окружности до пикселов в горизонтальном и диагональном направлениях:
При d < 0 расстояние от окружности до диагонального пиксела
(mD)больше, чем до горизонтального (mH). Напротив, если d > 0, расстояние до горизонтального пиксела (mH)больше. Таким образом,
при d < 0 выбираем mH (xi + 1, уi )
при d > 0 выбираем mD (xi + 1, уi – 1)
При d = 0, когда расстояния от окружности до обоих пикселов одинаковы, выбираем горизонтальный шаг.
Количество вычислений, необходимых для оценки величины d, можно сократить, если заметить, что в случае 1
так как диагональный пиксел (xi + 1, уi – 1) всегда лежит внутри окружности, а горизонтальный (xi + 1, уi ) - вне ее. Таким образом, d можно вычислить по формуле
Дополнение до полного квадрата члена (yi)2 с помощью добавления и вычитания - 2уi + 1 дает
В квадратных скобках стоит по определению Di, и его подстановка
d = 2(Di + yi) – 1
существенно упрощает выражение.
 |
поскольку в случае 2 горизонтальный (xi + 1, уi ) и диагональный (xi + 1, уi – 1) пикселы лежат внутри окружности. Следовательно, d < 0, и при использовании того же самого критерия, что и в случае 1, выбирается пиксел (xi + 1, уi ).
Если Di > 0, то диагональная точка (xi + 1, уi – 1) находится вне окружности, т. е. это случаи З и 4 на рис.2.6. В данной ситуации ясно, что должен быть выбран либо пиксел (xi + 1, уi – 1), т. е. mD, либо (xi, уi – 1), т. е. mV. Аналогично разбору предыдущего случая критерий выбора можно получить, рассматривая сначала случай З и проверяя разность между квадратами расстояний от
|
окружности до диагонального mD и вертикального mV пикселов, т. е.
При d\ < 0 расстояние от окружности до вертикального пиксела (xi, уi – 1) больше и следует выбрать диагональный шаг mD, к пикселу (xi + 1, уi – 1). Напротив, в случае d\ > 0 расстояние от окружности до диагонального пиксела больше и следует выбрать вертикальное движение к пикселу (xi, уi – 1). Таким образом,
при d £ 0 выбираем mD в (xi + 1, уi – 1)
при d < 0 выбираем mV в (xi, уi – 1)
Здесь в случае d = 0, т. е. когда расстояния равны, выбран диагональный шаг.
Проверка компонент d\ показывает, что
поскольку для случая З диагональный пиксел (xi + 1, уi – 1) находится вне окружности, тогда как вертикальный пиксел (xi, уi – 1) лежит внутри ее. Это позволяет записать d\ в виде
Дополнение до полного квадрата члена (xi)2 с помощью добавления и вычитания 2xi + 1 дает
Использование определения Di приводит выражение к виду
Теперь, рассматривая случай 4, снова заметим, что следует выбрать вертикальный пиксел (xi, уi – 1), так как y является монотонно убывающей функцией при возрастании x. проверка компонент d\ для случая 4 показывает, что
поскольку оба пиксела находятся вне окружности. Следовательно, d\ > 0 и при использовании критерия, разработанного для случая 3, происходит верный выбор mV.
Осталось проверить только случай 5 на рис.2.7, который встречается, когда диагональный пиксел (xi + 1, уi – 1) лежит на окружности, т. е. Di = 0. Проверка компонент d показывает, что
Следовательно, d > 0 и выбирается диагональный пиксел (xi + 1, уi – 1). Аналогичным образом оцениваем компоненты d\:
и d < 0, что является условием выбора правильного диагонального шага к (хi + 1, уi – 1). Таким образом, случай Di = 0 подчиняется тому же критерию, что и случай Di < 0 или Di > 0.
Подведем итог полученных результатов:
Di < 0
d £ 0 выбираем пиксел (хi + 1, уi ) ® mH
d > 0 выбираем пиксел (хi + 1, уi – 1) ® mD
Di > 0
d\ £ 0 выбираем пиксел (хi + 1, уi – 1) ® mD
d\ > 0 выбираем пиксел (хi, уi – 1) ® mV
Di = 0 выбираем пиксел (хi + 1, уi – 1) ® mD
Легко разработать простые рекуррентные соотношения дня реализации пошагового алгоритма. Сначала рассмотрим горизонтальный шаг mH к пикселу (хi + 1, уi ). Обозначим это новое положение пиксела как (i + 1). Тогда координаты нового пиксела и значение Di равны
Аналогично координаты нового пиксела и значения Di для шага mD к пикселу (хi + 1, уi – 1) таковы:
То же самое для шага mV к (хi, уi – 1)
Реализация алгоритма Брезенхема для окружности приводиться ниже.
Пошаговый алгоритм Брезенхема для генерации окружности в первом квадранте
все переменные целые
xi = 0
yi = R
Di = 2(1 – R)
Предел = 0
Plot (xi, yi)
if yi £ Предел then 4
выделение случая 1 или 2, 4 или 5, или 3
if Di < 0 then 2
if Di > 0 then 3
if Di = 0 then 20
определение случая 1 или 2
d = 2Di + 2yi – 1
if d £ 0 then 10
if d > 0 then 20
определение случая 4 или 5
d = 2Di + 2xi – 1
if d £ 0 then 20
if d > 0 then 30
выполнение шагов
шаг mH
xi = xi +1
Di = Di +2xi + 1
goto 1
шаг mD
xi = xi +1
yi = yi – 1
Di = Di +2xi – 2yi + 2
goto 1
шаг mV
30 yi = yi – 1
Di = Di – 2xi + 1
goto 1
finish
25. Алгоритм поточечного заполнения (с затравкой)
Как уже отмечалось, для приложений, связанных в основном с интерактивной работой, используются алгоритмы заполнения области с затравкой.
При этом тем или иным образом задается заливаемая (перекрашиваемая) область, код растра, которым будет выполняться заливка и начальная точка в области, с которой начнется заливка.
Основное отличие заполнения многоугольника от заливки области с затравкой состоит в том, что в последнем случае мы сразу имеем всю информацию о предельных размерах части экрана, занятой многоугольником. Поэтому определение принадлежности растра многоугольнику базируется на быстро работающих алгоритмах, использующих когерентность строк и ребер (см. предыдущий раздел). В алгоритмах же заливки области с затравкой нам вначале надо прочитать растр, затем определить принадлежит ли он области и если принадлежит, то перекрасить.
Заливаемая область или ее граница - некоторое связное множество растров. По способам доступа к соседним растрам области делятся на 4-х и 8-ми связные. В 4-х связных областях доступ к соседним растрам осуществляется по четырем направлениям - горизонтально влево и вправо и в вертикально вверх и вниз. В 8-ми связных областях к этим направлениям добавляются еще 4 диагональных. Используя связность, мы можем, двигаясь от точки затравки, достичь и закрасить все растры области.
Важно отметить, что для 4-х- связной прямоугольной области граница 8-ми связна (рис. 5а) и наоборот у 8-ми- связной области граница 4-х связна (см. рис.5б). Поэтому заполнение 4-х- связной области 8-ми связным алгоритмом может привести к "просачиванию" через границу и заливке растров в примыкающей области.
В общем, 4-х связную область мы можем заполнить как 4-х, так и 8-ми связным алгоритмом. Обратное же неверно. Так область на рис.6 а мы можем заполнить любым алгоритмом, а область на рис.5б, состоящую из двух примыкающих 4-х связных областей можно заполнить только 8-ми связным алгоритмом.
26. Алгоритм построчного заполнения (ВЕКТОРНЫЙ)
Реально используются алгоритмы построчного заполнения, основанные на том, что соседние растры в строке скорее всего одинаковы и меняются только там, где строка пересекается с ребром многоугольника. Это называется когерентностью растровых строк (строки сканирования Yi, Yi+1, Yi+2 на рис.5). При этом достаточно определить X-координаты пересечений строк сканирования с ребрами. Пары отсортированных точек пересечения задают интервалы заливки.
Построчная закраска многоугольника
Кроме того, если какие-либо ребра пересекались с i-й строкой, то они? скорее всего? будут пересекаться также и со строкой i+1. (строки сканирования Yi и Yi+1 на рис.4). Это называется когерентностью ребер. При переходе к новой строке легко вычислить новую X-координату точки пересечения ребра, используя X-координату старой точки пересечения и тангенс угла наклона ребра:
| Xi+1 = Xi + 1/k | (18) |
(тангенс угла наклона ребра - k = dy/dx, так как dy = 1, то 1/k = dx).
Смена же количества интервалов заливки происходит только тогда, когда в строке сканирования появляется вершина. Учет когерентности строк и ребер позволяет построить для заполнения многоугольников различные высокоэффективные алгоритмы построчного сканирования. Для каждой строки сканирования рассматриваются только те ребра, которые пересекают строку. Они задаются списком активных ребер (САР). При переходе к следующей строке для пересекаемых ребер перевычисляются X-координаты пересечений. При появлении в строке сканирования вершин производится перестройка САР. Ребра, которые перестали пересекаться, удаляются из САР, а все новые ребра, пересекаемые строкой заносятся в него.
Общая схема алгоритма, динамически формирующего список активных ребер и заполняющего многоугольник снизу-вверх, следующая:
Подготовить служебные целочисленные массивы Y-координат вершин и номеров вершин.
Совместно отсортировать по возрастанию Y-координаты и массив номеров вершин для того, чтобы можно было определить исходный номер вершины.
Определить пределы заполнения по оси Y - Yмin и Ymax. Стартуя с текущим значением Ytek = Ymin, исполнять пункты 4-9 до завершения раскраски.
Определить число вершин, расположенных на строке Ytek - текущей строке сканирования.
Если вершины есть, то для каждой из вершин дополнить список активных ребер, используя информацию о соседних вершинах.
Для каждого ребра в список активных ребер заносятся:
максимальное значение Y-координаты ребра;
приращение X-координаты при увеличении Y на 1;
начальное значение X-координаты.
Если обнаруживаются горизонтальные ребра, то они просто закрашиваются и информация о них в список активных ребер не заносится. Если после этого обнаруживается, что список активных ребер пуст, то заполнение закончено.
По списку активных ребер определяется Yслед - Y-координата ближайшей вершины. (Вплоть до Yслед можно не заботиться о модификации САР а только менять X-координаты пересечений строки сканирования с активными ребрами).
В цикле от Ytek до Yслед:
выбрать из списка активных ребер и отсортировать X-координаты пересечений активных ребер со строкой сканирования;
определить интервалы и выполнить закраску;
перевычислить координаты пересечений для следующей строки сканирования.
Проверить не достигли ли максимальной Y-координаты. Если достигли, то заливка закончена, иначе выполнить пункт.
Очистить список активных ребер от ребер, закончившихся на строке Yслед, и перейти к пункту 4.
Рассмотрен (простейший) алгоритм. Он вполне работоспособен, но генерирует двух и трехкратное занесение части растров. Это мало приемлемо для устройств вывода типа матричных или струйных принтеров.
27. Кривая Эрмита
28. Кривая Безье
29. Задание объектов и сцен в 3d графике
Покажем здесь достаточно распространенную схему задания 3D объектов и сцен. Подобная схема, кстати, используется, в 3D Studio.
Каждая сцена представляет собой следующее:
- набор объектов
- набор источников света
- набор текстур
- набор камер (хотя обычно используется одна)
Каждый объект задается следующим:
- набор вершин
* вершина определяется своими 3D координатами и соответствующими ей координатами в текстуре
- набор граней
* грань определяется тремя вершинами и текстурой (вообще говоря, не текстурой, а материалом: кроме текстуры могут быть заданы, например, коэффициенты рассеивания и отражения света)
- поведение объекта
* то есть, расположение (то есть смещение, ось поворота, угол поворота, коэффициент масштабирования, и т.д.) в зависимости от номера кадра;
обычно задается в нескольких ключевых точках и интерполируется между ними с помощью сплайнов
Каждый источник света задается следующим:
- положение
- ориентация (точка, в которую направлен этот источник, target)
- тип (фоновый/направленный/ненаправленный)
- цвет (обычно RGB)
Каждая текстура представляет собой прямоугольную 2D картинку, часто бывает фиксированных размеров (например, 64x64, 128x128, 256x256).
Каждая камера задается следующим:
- положение (location)
- направление (точнее, точкой, в которую направлена эта камера; target)
- угол зрения (FOV)
- угол поворота относительно своей оси (roll)
30. Рисование одноцветного треугольника (3d)
Без понимания того, как рисовать залитый одним цветом треугольник, дальше лезть в 3D графику явно не стоит. Поэтому вот объяснение.
Возьмем любой треугольник. Его изображение на экране - набор горизонтальных отрезков, причем из-за того, что треугольник - фигура выпуклая, каждой строке экрана соответствует не более одного отрезка. Поэтому достаточно пройтись по всем строкам экрана, с которыми пересекается треугольник (то есть, от минимального до максимального значения y для вершин треугольника), и нарисовать соответствующие горизонтальные отрезки.
----------------------------
| A |
| **** |
| ******* |
| ********** |
| B************ |
| *********** |
| ********* |
|-----------@@@@@@@--------|
| ***** |
| *** |
| C |
----------------------------
Отсортируем вершины так, чтобы вершина A была верхней, C - нижней, тогда у нас min_y = A.y, max_y = C.y, и нам надо пройтись по всем линиям от min_y до max_y. Рассмотрим какую-то линию sy, A.y <= sy <= C.y. Если sy < B.y, то она пересекает стороны AB и AC; если sy >= B.y - то стороны BC и AC. Мы знаем координаты всех вершин, поэтому мы можем написать уравнения сторон и найти пересечение нужной стороны с прямой y = sy. Получим два конца отрезка. Так как мы не знаем, какой из них левый, а какой правый, сравним их координаты по x и обменяем значения, если надо. Рисуем этот отрезок, повторяем процедуру для каждой строки - и вуаля, трегуольник нарисован. Остановимся более подробно на нахождении пересечения прямой y = sy (текущей строки) и стороны треугольника, например AB. Напишем уравнение прямой AB в форме x = k*y+b:
x = A.x+(y-A.y)*(B.x-A.x)/(B.y-A.y)
Подставляем сюда известное для текущей прямой значение y = sy:
x = A.x+(sy-A.y)*(B.x-A.x)/(B.y-A.y)
Вот, в общем-то, и все. Для других сторон пересечение ищется совершенно точно
так же. А вот и пример кода.
//...
// здесь сортируем вершины (A,B,C)
//...
for (sy = A.y; sy <= C.y; sy++) {
x1 = A.x + (sy - A.y) * (C.x - A.x) / (C.y - A.y);
if (sy < B.y)
x2 = A.x + (sy - A.y) * (B.x - A.x) / (B.y - A.y);
else
x2 = B.x + (sy - B.y) * (C.x - B.x) / (C.y - B.y);
if (x1 > x2) { tmp = x1; x1 = x2; x2 = tmp; }
drawHorizontalLine(sy, x1, x2);
}
//...
Надо, правда, защититься от случая, когда B.y = C.y - в этом (и только этом, потому как если C.y = A.y, то треугольник пустой и рисовать его не стоит, или можно рисовать горизонтальную линию; а если B.y = A.y, то sy >= A.y и до деления на B.y - A.y не дойдет) случае произойдет попытка деления на ноль. Код изменится совсем чуть-чуть:
//...
// здесь сортируем вершины (A,B,C)
//...
for (sy = A.y; sy <= C.y; sy++) {
x1 = A.x + (sy - A.y) * (C.x - A.x) / (C.y - A.y);
if (sy < B.y)
x2 = A.x + (sy - A.y) * (B.x - A.x) / (B.y - A.y);
else {
if (C.y == B.y)
x2 = B.x;
else
x2 = B.x + (sy - B.y) * (C.x - B.x) / (C.y - B.y);
}
if (x1 > x2) { tmp = x1; x1 = x2; x2 = tmp; }
drawHorizontalLine(sy, x1, x2);
}
//...
Вот и все. Ну, горизонтальную линию, надеюсь, нарисовать сумеют все желающие.
Перспективное и плоское проецирование. Стандартная камера.
Переход от произвольной камеры к стандартной
Алгоритм художника. Метод сортировки по глубине.
Пусть имеется некий набор граней (т.е. сцена), который требуется нарисовать. Отсортируем грани по удаленности от камеры и отрисуем все грани, начиная с самых удаленных. Довольно распространенная характеристика удаленности для грани ABC - это среднее значение z, mid_z = (A.z+B.z+C.z)/3. Вот и весь алгоритм. Просто, и обычно достаточно быстро. Существует, правда, несколько проблем.
Во-первых, при некотором расположении граней этот алгоритм вообще не может дать правильного результата - в каком порядке грани не рисуй, получится неправильно. Вот стандартный пример.
+----+ +----+
| | | |
+---| |--------------
| | | |
+---| |--------------
| | | |
| | | |
+-------------| |---+
| | | |
+-------------| |---+
| | | |
+----+ +----+
Во-вторых, при некотором расположении граней и использовании среднего значения z как характеристики удаленности алгоритм тоже дает неправильный результат. Пример чуть ниже. В этом случае горизонтальную грань надо отрисовывать второй, но по среднему значению z она лежит дальше и таким образом получается, что ее надо отрисовывать первой. Возможные пути решения этой проблемы - какие-то изменения характеристики удаленности, либо моделирование, не вызывающее таких ситуаций.
y
| |
| | <- грань #1 (параллельна Oxy)
| |
| --------------------------------------
| ^^^ грань #2 (параллельна Oxz)
|
|
|
|
--*------O-------------------------------------------------z
^-- камера
И наконец, при использовании этого алгоритма отрисовываются вообще все грани сцены, и при большом количестве загораживающих друг друга граней мы будем тратить большую часть времени на отрисовку невидимых в конечном итоге частей. То есть совершенно впустую. В таком случае целесообразно использовать какие-то другие методы (например BSP и PVS, порталы, и т.д).
31. Z-буфер
Заведем буфер (собственно z-буфер) размером с экран, и забьем его каким-то большим числом, настолько большим, что координаты z для точек сцены заведомо меньше. Например, если z - fixedpoint 16:16, то можно использовать максимально возможное значение, то есть 0x7FFFFFFF. Для каждой рисуемой точки считаем значение z; если оно больше, чем значение в z-буфере (точка закрыта какой-то другой точкой), или меньше, чем -dist (точка находится за камерой), то переходим к следующей точке. Если меньше, то рисуем точку на экране (или в видеобуфере), а в z-буфер записываем текущее значение z. Вот кусок кода для лучшего понимания:
//...
if (z > -dist && z < zbuffer[screenX][screenY]) {
screen[screenX][screenY] = color;
zbuffer[screenX][screenY] = z;
}
//...
Имеет смысл считать значения не z, а z1 = 1/(z+dist), так как эта величина изменяется по грани линейно, и линейная интерполяция дает точные результаты (более подробно это описано в 4.3). Тогда условия чуть изменяются – точка загорожена другой, если значение z1 *меньше* значения в z-буфере; и точка находится за камерой, если z1 < 0. Буфер инициализируем нулями. Тогда не нежна проверка на положительность z1 - точка попадает в z-буфер и на экран, только если z1 больше текущего значения, и поэтому точки, для которых z1 < 0 в буфер и без проверки никогда не попадут. Код тоже чуть изменится:
//...
if (z1 > zbuffer[screenX][screenY]) {
screen[screenX][screenY] = color;
zbuffer[screenX][screenY] = z1;
}
//...
Вот и все. Осталось упомянуть, что этот метод иногда называют w-буфером, подчеркивая разницу между хранением z и какой-то обратной величины, w.
Это самый простой метод удаления невидимых частей, причем всегда дающий полностью правильные результаты. Единственная проблема - скорость, z-буфер, как самый простой, является и самым медленным методом.
32. Порталы, Z-отсечение, Отсечение при растеризации
Этот метод предназначен для т.н. indoor environments - в буквальном переводе "комнатная среда"; это как бы внутренность какого-то здания. В качестве примера могут служить Doom, Quake.
В этом случае сцена составляется из комнат. Комнаты связаны друг с другом какими-то проходами - дверями, окнами, чем угодно. На каждый такой проход вешается обычный полигон, называемый порталом. Для отрисовки сцены достаточно нарисовать текущую комнату вместе с тем, что из нее видно. Но то, что из нее видно, может быть видно *только* через порталы.
Таким образом, для отрисовки всей сцены мы просто берем и рисуем текущую комнату, используя любые методы удаления невидимых частей (например, алгоритм художника и отброс нелицевых граней). А если в процессе отрисовки нам встречается полигон, помеченный как портал, то мы рисуем комнату, которую видно через этот портал, причем отсекаем ее уже по проекции этого портала.
Как обычно, кусок кода для уяснения:
//...
void drawRoom(int roomID, polygon *clipArea) {
int i;
for (i = 0; i < rooms[roomID].numFaces; i++)
drawFace(&rooms[roomID].face[i], clipArea);
}
void drawFace(polygon *face, polygon *clipArea) {
polygon *newClipArea;
if (face->isPortal) {
if (isVisible(face, clipArea) {
newClipArea = clipPolygon(face, clipArea);
drawRoom(face->destinationRoom, newClipArea);
}
} else drawClippedPolygon(face, clipArea);
}
//...
drawRoom(currentRoom, fullScreen);
//...
Здесь функция isVisible(face, clipArea) возвращает false, если грань face и область отсечения clipArea не пересекаются; функция clipPolygon возвращает пересечение полигонов face и clipArea (то есть отсекает face в clipArea и наоборот); fullScreen - полигон размером с экран (или любую нужную область отрисовки).
В природе есть Alpha 2 - готовый engine, использующий порталы и написанный на TMT Pascal, причем, что приятно, доступный в исходниках. Скачать его когда-то было можно с http://www.geocities.com/CapeCanaveral/5402. Есть, впрочем, надежда, что найти этот engine особых проблем не составит.
Осталось упомянуть, что несмотря на то, что в изложенной форме метод и требует возможности отрисовки произвольной грани, отсеченной в произвольную грань, можно обойтись и отсечением по bounding box проекции портала.
Z-отсечение
Необходимость в этой процедуре возникает, когда, в конце концов, оказывается, что надо нарисовать грань, у которой часть вершин лежит перед камерой, а часть - за камерой. То есть грань, пересекающуюся с экраном. Сама по себе она правильно не нарисуется. Поскольку камера видит только то, что перед ней находится, все те точки, для которых z < -dist, рисовать не надо. То есть, каждую грань надо обрезать плоскостью z = -dist. Принципиально различных случаев расположения грани относительно этой плоскости может быть всего четыре; когда перед камерой находятся соответственно 0, 1, 2 или 3 вершины. Первый и последний случаи тривиальны - если перед камерой находится 0 вершин, то грань просто не видна и рисовать ее не надо; если 3 вершины, то грань видна целиком и полностью и ее достаточно просто взять и нарисовать. Рассмотрим оставшиеся два случая.
Случай первый, когда перед камерой находится только одна вершина:
|
|
A |
/ \|
B D
\ |\
\ | \
E \
| \ \
| \\
| C
|
--------|-------------------------> z
|
| z = -dist
|
В этом случае перед камерой находится только треугольник CDE. Его и надо будет нарисовать вместо грани.
Случай второй, когда перед камерой находятся две вершины:
|
|
| A
|/ \
D B
/| /
/ | /
/ E
/ / |
// |
C |
|
--------|-------------------------> z
|
| z = -dist
|
Здесь уже надо будет нарисовать трапецию DABE; она разбивается на два треугольника, DAB и DBE. Их и рисуем вместо грани.
Координаты и текстурные координаты для точек D, E считаются совсем просто: с одной стороны, D лежит на AC, с другой стороны, D.z = -dist. Для точки D как лежащей на AC любая величина t (вместо t подставляем x/y/u/v) считается следующим образом:
D.t = A.t + (C.t - A.t) * (D.z - A.z) / (C.z - A.z) =
= A.t + (C.t - A.t) * (-dist - A.z) / (C.z - A.z)
Все это сводится в следующий алгоритм отрисовки грани:
- выясняем, сколько вершин лежит перед камерой; то есть - какой из случаев мы имеем;
- ставим точки A, B, C в соответствие с вершинами (то есть, если вершина v0 находится перед камерой, а вершины v1, v2 - нет, то имеем первый случай, где C = v0, A = v1, B = v2);
- считаем, если нужно, координаты D, E;
- рисуем (или добавляем в список отрисовки) полученные треугольники.
Осталось только добавить, что обрезание на самом деле надо проводить не плокостью z = -dist, а плоскостью z = -dist + smallvalue, smallvalue > 0, чтобы избежать проблем при проецировании.
В процессе отрисовки граней мы почти сразу столкнемся со следующей неприятной ситуацией: проекция грани лежит в плоскости экрана, но она вовсе не обязана точно попадать в прямоугольник-экран. Поэтому эту самую проекцию желательно корректно обрезать по границе экрана (можно, конечно, выводить все на экран через свою функцию putpixel() и проверять в ней x, y на попадание в экран, но это извращение и вдобавок очень медленно). Операцией обрезания как раз и занимаются разные алгоритмы отсечения (clipping).
Дата добавления: 2015-11-26; просмотров: 79 | Нарушение авторских прав