Удаление невидимых ребер - раздел Компьютеры, ОСНОВЫ КОМПЬЮТЕРНОЙ ГРАФИКИ После Первого Этапа Удаления Нелицевых Отрезков Необходимо Выяснить, Существу...
После первого этапа удаления нелицевых отрезков необходимо выяснить, существуют ли такие отрезки, которые экранируются другими телами в картинке или в сцене. Для этого каждый оставшийся отрезок или ребро нужно сравнить с другими телами сцены или картинки.
Возможны следующие случаи:
¨ Грань ребра не закрывает. Ребро остается в списке ребер.
¨ Грань полностью закрывает ребро. Ребро удаляется из списка рассматриваемых ребер.
¨ Грань частично закрывает ребро. В этом случае ребро разбивается на несколько частей, видимыми из которых являются не более двух. Само ребро удаляется из списка рассматриваемых ребер, но в список проверяемых ребер добавляются те его части, которые данной гранью не закрываются.
Для оптимизации используется приоритетная сортировка (z-сортировка), а также, сравнения с прямоугольными объемлющими оболочками тел. Такой подход позволяет удалить целые группы или кластеры отрезков и тел. Например, если все тела в сцене упорядочены в некотором приоритетном списке, использующем значения z ближайших вершин для представления расстояния до наблюдателя, то никакое тело из этого списка, у которого ближайшая вершина находится дальше от наблюдателя, чем самая удаленная из концевых точек ребра, не может закрывать это ребро. Более того, ни одно из оставшихся тел, прямоугольная оболочка которого расположена полностью справа, слева, над или под ребром, не может экранировать это ребро. Использование этих приемов значительно сокращает число тел, с которыми нужно сравнивать каждый отрезок или ребро. Рис. 8.10 иллюстрирует работу алгоритма.
Рис. 8.10. Результат работы алгоритма Робертса
8.4. Алгоритм, использующий z–буфер
Алгоритм, использующий z-буфер это один из простейших алгоритмов удаления невидимых поверхностей. Впервые он был предложен Кэтмулом. Работает этот алгоритм в пространстве изображения. Идея z-буфера является простым обобщением идеи о буфере кадра. Буфер кадра используется для запоминания атрибутов (интенсивности) каждого пикселя в пространстве изображения, z-буфер - это отдельный буфер глубины, используемый для запоминания координаты z или глубины каждого видимого пикселя в пространстве изображения. В процессе работы глубина или значение z каждого нового пикселя, который нужно занести в буфер кадра, сравнивается с глубиной того пикселя, который уже занесен в z-буфер. Если это сравнение показывает, что новый пиксель расположен впереди пикселя, находящегося в буфере кадра, то новый пиксель заносится в этот буфер и, кроме того, производится корректировка z-буфера новым значением z. Если же сравнение дает противоположный результат, то никаких действий не производится. По сути, алгоритм является поиском по х и у наибольшего значения функции z (х, у).
Главное преимущество алгоритма – его простота. Кроме того, этот алгоритм решает задачу об удалении невидимых поверхностей и делает тривиальной визуализацию пересечений сложных поверхностей. Сцены могут быть любой сложности. Поскольку габариты пространства изображения фиксированы, оценка вычислительной трудоемкости алгоритма не более чем линейна. Поскольку элементы сцены или картинки можно заносить в буфер кадра или в z-буфер в произвольном порядке, их не нужно предварительно сортировать по приоритету глубины. Поэтому экономится вычислительное время, затрачиваемое на сортировку по глубине.
Основной недостаток алгоритма - большой объем требуемой памяти. Если сцена подвергается видовому преобразованию и отсекается до фиксированного диапазона значений координат z, то можно использовать z-буфер с фиксированной точностью. Информацию о глубине нужно обрабатывать с большей точностью, чем координатную информацию на плоскости (х, y); обычно бывает достаточно 20-ти бит. Буфер кадра размером 512´512´24 бит в комбинации с z-буфером размером 512´512´20 бит требует почти 1.5 мегабайт памяти. Однако снижение цен на память делает экономически оправданным создание специализированных запоминающих устройств для z-буфера и связанной с ним аппаратуры.
Альтернативой созданию специальной памяти для z-буфера является использование для этой цели оперативной памяти. Уменьшение требуемой памяти достигается разбиением пространства изображения на 4, 16 или больше квадратов или полос. В предельном варианте можно использовать z-буфер размером в одну строку развертки. Для последнего случая имеется интересный алгоритм построчного сканирования. Поскольку каждый элемент сцены обрабатывается много раз, то сегментирование z-буфера, вообще говоря, приводит к увеличению времени, необходимого для обработки сцены. Однако сортировка на плоскости, позволяющая не обрабатывать все многоугольники в каждом из квадратов или полос, может значительно сократить этот рост.
Другой недостаток алгоритма z-буфера состоит в трудоемкости и высокой стоимости устранения лестничного эффекта, а также реализации эффектов прозрачности и просвечивания. Поскольку алгоритм заносит пиксели в буфер кадра в произвольном порядке, то нелегко получить информацию, необходимую для методов устранения лестничного эффекта, основывающихся на предварительной фильтрации. При реализации эффектов прозрачности и просвечивания пиксели могут заноситься в буфер кадра в некорректном порядке, что ведет к локальным ошибкам.
Формальное описание алгоритма z-буфера таково:
1. Заполнить буфер кадра фоновым значением интенсивности или цвета.
2. Заполнить z-буфер минимальным значением z.
3. Преобразовать каждый многоугольник в растровую форму в произвольном порядке.
4. Для каждого Пиксель(x,y) в многоугольнике вычислить его глубину z(x,y).
5. Сравнить глубину z(х,у) со значением Zбуфер(х,у), хранящимся в z-буфере в этой же позиции.
Если z(х,у) > Zбуфер (х,у), то записать атрибут этого многоугольника (интенсивность, цвет и т. п.) в буфер кадра и заменить Zбуфер(х,у) на z(х,у). В противном случае никаких действий не производить.
На псевдокоде алгоритм можно представить так:
for all objects
for all covered pixels
compare z
В качестве предварительного шага там, где это целесообразно, применяется удаление нелицевых граней.
Если известно уравнение плоскости, несущей каждый многоугольник, то вычисление глубины каждого пикселя на сканирующей строке можно проделать пошаговым способом. Грань при этом рисуется последовательно (строка за строкой). Для нахождения необходимых значений используется линейная интерполяция (рис. 8.11).
Рис. 8.11. Сканирующая строка по грани
Для рисунка y меняется от y1 до y2 и далее до y3, при этом для каждой строки определяется xa, za, xb, zb:
xa = x1 + (x2 - x1)× ;
xb = x1 + (x3 - x1)× ;
za = z1 + (z2 - z1)× ;
zb = z1 + (z3 - z1)× .
На сканирующей строке x меняется от xa до xb и для каждой точки строки определяется глубина z:
z = za + (zb - za)×
Реализация алгоритма вдоль сканирующей строки позволяет совместить алгоритм z-буфера с алгоритмами растровой развертки ребер и алгоритмами закраски грани.
Проиллюстрируем работу алгоритма на примере для рис. 8.12.
Рис. 8.12. Протыкающий треугольник
В начале в буфере кадра и в z-буфере содержатся нули. После растровой развертки прямоугольника содержимое буфера кадра будет иметь вид
Содержимое z-буфера таково:
При обработке треугольника преобразование его в растровую форму и сравнение по глубине дает новое значение буфера кадра:
Новое содержимое z-буфера таково:
Все темы данного раздела:
Г Р А Ф И К И
Рекомендовано в качестве учебного пособия Редакционно-издательским советом Томского политехнического университета
Издательство
Томс
Способы представления изображений в ЭВМ
Компьютерная (машинная) графика – область деятельности, изучающая создание, способы хранения и обработки изображений с помощью ЭВМ. Под интерактивной ко
Растровое представление изображений
Что такое растровое изображение?
Возьмём фотографию (например, см. рис. 1.1). Конечно, она тоже состоит из маленьких элементов, но будем считать, что отдельные элементы мы рассмотреть не м
Параметры растровых изображений
Как уже говорилось ранее, растровое изображение представляется в памяти ЭВМ в виде матрицы отдельных пикселей. В этой связи возникает вопрос о том, каково должно быть число этих пикселей и какое чи
Векторное представление изображений
Для векторной графики характерно разбиение изображения на ряд графических примитивов – точки, прямые, ломаные, дуги, полигоны. Таким образом, появляется возможность хранить
Представление изображений с помощью фракталов
В последние время фракталы стали очень популярны. Большую роль в этом сыграла книга франко-американского математика Бенуа Мандельброта "Фрактальная геометрия природы", изданная в 1975 год
Геометрические фракталы
Фракталы этого класса самые наглядные. В двухмерном случае их получают с помощью некоторой ломаной (или поверхности в трехмерном случае), называемой генератором. За один шаг алгоритма каждый из отр
Алгебраические фракталы
Это самая крупная группа фракталов. Получают их с помощью нелинейных процессов в n-мерных пространствах. Наиболее изучены двухмерные процессы. Интерпретируя нелинейный итерационный
Системы итерируемых функций
Метод "Систем Итерируемых Функций" (Iterated Functions System - IFS) появился в середине 80-х годов как простое средство получения фрактальных структур.
IFS представляет собой си
Свет и цвет
Понятия света и цвета в компьютерной графике тесно связаны и являются основополагающими.
Свет может рассматриваться либо как электромагнитная волна, либо как поток фотонов. Одной из характ
Цветовые модели и пространства
Как видим из вышеизложенного, описание цвета может опираться на составление любого цвета на основе основных цветов или на такие понятия, как светлота, насыщенность, цветовой тон. Применительно к ко
Цветовая модель RGB
В основе одной из наиболее распространенных цветовых моделей, называемой RGB моделью, лежит воспроизведение любого цвета путем сложения трех основных цветов: красного (Red), зеленого (Green) и сине
Субтрактивные цветовые модели
Модель CMY использует также три основных цвета: Cyan (голубой), Magenta (пурпурный, или малиновый) и Yellow (желтый). Эти цвета описывают отраженный от белой бумаги свет трех о
Модели HSV и HSL
Рассмотренные модели ориентированы на работу с цветопередающей аппаратурой и для некоторых людей неудобны. Поэтому модели HSV, HLS опираются на понятия тона, насыщенности и яркости (светлоты).
Системы управления цветом
Ситуация, когда дизайнерам и полиграфистам приходится работать в разных цветовых пространствах, приводит к возникновению ошибок в цветопередаче на этапе перехода от одной цветовой модели к другой.
Графические файловые форматы
Как уже говорилось ранее, при хранении растровых изображений, как правило, приходится иметь дело с файлами большого размера. В этой связи важной задачей является выбор соответствующего формата файл
PostScript
Это язык описания страниц, предназначеный для формирования изображений произвольной сложности и вывода их на печать. Для этого в языке имеется широкий набор графических операторов, используемых в п
Растровые алгоритмы
Большинство графических устройств являются растровыми, представляя изображение в виде прямоугольной матрицы (сетки, целочисленной решетки) пикселей (растра), и большинство графических библиотек сод
Алгоритмы растеризации
Прежде чем перейдем к непосредственному рассмотрению возможности перевода математического описания объекта (линии и пр.) в растровую форму, рассмотрим понятие связности. Связность
Растровое представление отрезка. Алгоритм Брезенхейма
Рассмотрим задачу построения растрового изображения отрезка, соединяющего точки A(xa, ya) и B(xb, yb). Для простоты будем считать, что
Кривые Безье
Кривые Безье были разработаны в 60-х годах XX века независимо друг от друга Пьером Безье из автомобилестроительной компании «Рено» и Полем де Касталье (Кастельжо) из компании «Ситроен», где применя
Квадратные кривые
Квадратная кривая Безье (n = 2) задаётся 3-я опорными точками: P0, P1 и P2. Кривая задаётся уравнением:
B(t) = (1–
Кубические кривые
В параметрической форме кубическая кривая Безье (n = 3) описывается следующим уравнением:
B(t) = (1–t)3 P0 + 3t
Сплайн Безье
Кривые Безье обладают рядом свойств:
1. непрерывность заполнения сегмента между начальной и конечной точками;
2. инвариантность относительно аффинных преобразований. Как следствие
Закраска области, заданной цветом границы
Рассмотрим область, ограниченную набором пикселей заданного цвета и точку (x, y), лежащую внутри этой области.
Задача заполнения области заданным цветом в случае, когда эта область не явля
Отсечение многоугольников
Отсечение многоугольников чаше всего проводится для отбрасывания частей многоугольника, выходящих за границу прямоугольной области, которая определяет экран или область окна. Однако отсечение может
Заполнение многоугольников
Рассмотрим, каким образом можно заполнить многоугольник, задаваемый замкнутой ломаной линией без самопересечений.
Простейший способ закраски многоугольника состоит в проверке принадлежност
Метод увеличения частоты выборки
Первый метод устранения ступенчатости связан с увеличением частоты выборки. Увеличение частоты выборки достигается с помощью увеличения разрешения растра. Таким образом учитываются более мелкие дет
Яркость и контраст
Яркость и контраст являются субъективными характеристиками изображения, воспринимаемыми человеком.
Яркость (brightness) представляет собой характеристику, определяющую
Масштабирование изображения
Масштабирование изображения позволяет сжать или растянуть его по горизонтали и/или вертикали. При этом изменяется ширина и/или высота изображения. Для масштабирования задаются масштабные коэффициен
Преобразование поворота
Преобразование поворота, также как и при рассмотрении плоских геометрических объектов, позволяет поворачивать исходное изображение на заданный угол. Поворот осуществляется вокруг центра изображения
Линейные фильтры
Линейные фильтры представляют собой семейство фильтров, имеющих очень простое математическое описание. Вместе с тем они позволяют добиться самых разнообразных эффектов. Будем считать, что задано ис
Сглаживающие фильтры
Результатом применения сглаживающего фильтра является размытие изображения, устранение резких цветовых переходов. Простейший прямоугольный сглаживающий фильтр радиуса r задается при помощи м
Контрастоповышающие фильтры
Если сглаживающие фильтры снижают локальную контрастность изображения, размывая его, то контрастоповышающие фильтры производят обратный эффект. Ядро контрастоповышающего фильтра имеет значение, бол
Разностные фильтры
Разностные фильтры часто используются для нахождения границ в изображениях. При этом используют дифференциальный оператор, вычисляющий приближенное значение градиент[2] яркости изображения. Результ
Нелинейные фильтры
Основное отличие нелинейного фильтра от линейного заключается в том, что выход нелинейного фильтра формируется нелинейным образом от данных исходного изображения.
Линейные фильтры, несмотр
Векторизация с помощью волнового алгоритма
Векторизация – преобразование изображения из растрового представления в векторное. Векторизация - процесс, обратный растеризации. Векторизация проводится, как правило, в случае
Построение скелета изображения
Для построения скелета изображения на объекте (отрезке) выбирается начальная (затравочная) точка, от которой начинается распространяться волна, путем добавления пикселей сначала к затравочной точке
Оптимизация скелета изображения
Полученный скелет изображения не является оптимальным. Это связано прежде всего с тем, что мы имеем дело с растровым изображением, а значит, изображение имеет искажения тем большие, чем меньше разр
Сегментация изображений
Сегментация – это процесс разбиения изображения на неперекрывающиеся области (сегменты), покрывающие все изображение и однородные по некоторому признаку. Все пиксели в сегменте
Методы, основанные на кластеризации
В постановке задачи сегментации прослеживается аналогия с задачей кластеризации[3]. Для того чтобы свести задачу сегментации к задаче кластеризации, достаточно задать отображение точек изображения
Алгоритм разрастания регионов
Алгоритм разрастания регионов (“region growing”) является методом автоматической сегментации и учитывает пространственное расположение точек напрямую.
Метод разрастания регионов основан на
Двумерные преобразования
Компьютерная геометрия есть математический аппарат, положенный в основу компьютерной графики. В свою очередь, основу компьютерной геометрии составляют различные преобразования
Преобразование единичного квадрата
Четыре вектора положения точек единичного квадрата с одним углом в начале координат записываются в виде
Применение общего матричного преобразования к единичному квадрату пр
Однородные координаты
Преобразования переноса, масштабирования и поворота записываются в матричной форме в виде
,
,
.
Очевидно, что перенос, в отличие от масштабирования и поворота, р
Двумерное вращение вокруг произвольной оси
Выше было рассмотрено вращение изображения около начала координат. Однородные координаты обеспечивают поворот изображения вокруг точек, отличных от начала координат. В общем случае вращение около
Трехмерные преобразования
Рассмотрим трехмерную декартовую систему координат, являющуюся правосторонней. Примем соглашение, в соответствии с которым будем считать положительными такие повороты, при к
Проекции
В общем случае проекции преобразуют точки, заданные в системе координат размерностью n, в системы координат размерностью меньше чем n.
Будем рассматривать случай проецировани
Математическое описание плоских геометрических проекций
Каждую из проекций можно описать матрицей 4´4. Этот способ оказывается удобным, поскольку появляется возможность объединить матрицу проецирования с матрицей преобразования.
Ц
Изображение трехмерных объектов
Процесс вывода трехмерной графической информации более сложный, чем соответствующий двумерный процесс. В двумерном случае просто задается окно в двумерном мировом координатном пространстве и поля в
Видимый объем
В процессе вывода трехмерной графической информации (рис. 6.19) мы задаем видимый объем (ВО) в мировом пространстве, проекцию на КП и поле вывода на видовой поверхности. В о
Преобразование видимого объема
В случае центральной перспективы, для решения задачи отсечения по ВО требуются значительные вычисления. Решение заключается в преобразовании ВО к виду, в котором вычисления проводились бы значитель
Представление пространственных форм
Во многих приложениях машинной графики возникает потребность в представлении трехмерных форм: при проектировании самолетов, при восстановлении трехмерных тел по изображениям их поперечных сечений,
Алгоритм плавающего горизонта
Алгоритм плавающего горизонта можно отнести к классу алгоритмов, работающих в пространстве изображения. Алгоритм плавающего горизонта чаше всего используется для удаления невидимых линий трехмерног
Алгоритм Робертса
Алгоритм Робертса представляет собой первое известное решение задачи об удалении невидимых линий. Это математически элегантный метод, работающий в объектном пространстве. Алгоритм прежде всего удал
Определение нелицевых граней
Пусть F — некоторая грань многогранника. Плоскость, несущая эту грань, разделяет пространство на два подпространства. Назовем положительным то из них, в которое смотрит внешняя нормаль к гра
Методы трассировки лучей
В простейшем методе, использующим лучи, для каждого пикселя картинной плоскости определяется ближайшая к нему грань, для чего через этот пиксель выпускается луч, находятся все его пересечения с гра
Алгоритмы, использующие список приоритетов
При реализации всех обсуждавшихся алгоритмов удаления невидимых линий и поверхностей устанавливались приоритеты, т. е. глубины объектов сцены или их расстояния от точки наблюдения. Алгоритмы, испол
Алгоритм Ньюэла-Ньюэла-Санча для случая многоугольников
Сформировать предварительный список приоритетов по глубине, используя в качестве ключа сортировки значение zmin для каждого многоугольника. Первым в списке будет многоугольник с м
Алгоритм Варнока (Warnock)
Алгоритм Варнока является одним из примеров алгоритма, основанного на разбиении картинной плоскости на части, для каждой из которых исходная задача может быть решена достаточно просто.
Пос
Алгоритм Вейлера-Азертона (Weiler-Atherton)
Разбиение картинной плоскости можно производить не только прямыми, параллельными координатным осям, но и по границам проекций граней. В результате получается точное решение задачи.
Предлаг
Диффузное отражение и рассеянный свет
Матовые поверхности обладают свойством диффузного отражения, т. е. равномерного по всем направлениям рассеивания света. Поэтому кажется, что поверхности имеют одинаковую ярк
Зеркальное отражение
Зеркальное отражение можно получить от любой блестящей поверхности. Осветите ярким светом яблоко – световой блик на яблоке возникает в результате зеркального отражения, а свет, отраженный от осталь
Однотонная закраска полигональной сетки
Существует три основных способа закраски объектов, заданных полигональными сетками. В порядке возрастания сложности ими являются:
1) однотонная закраска;
2) метод Гуро (основан на
Метод Гуро
Метод закраски, который основан на интерполяции интенсивности и известен как метод Гуро (по имени его разработчика), позволяет устранить дискретность изменения интенсивности. Процесс закраски по ме
Метод Фонга
В методе закраски, разработанном Фонгом, используется интерполяция вектора нормали к поверхности вдоль видимого интервала на сканирующей строке внутри многоугольника, а не интерполяция инте
Поверхности, пропускающие свет
Поверхности могут обладать не только свойствами зеркального и диффузного отражения, но и свойствами направленного и диффузного пропускания. Направленное пропускание света происходит сквозь прозрачн
Детализация фактурой
Идея детализации фактурой состоит в отображении массива узора, представляющего собой оцифрованное изображение, на плоскую или криволинейную поверхность. Значения из массива узора используются для м
Библиотека OpenGL
На данный момент в Windows существует два стандарта для работы с трёхмерной графикой: OpenGL, являющийся стандартом де-факто для всех графических рабочих станций, и Direct3D – стандарт, предложенны
Особенности использования OpenGL в Windows
OpenGL представляет собой универсальную графическую библиотеку, которая может быть реализована в любой оконной среде. Поставляется в составе операционной системы Windows, начиная с версии OSR2 в ви
Основные типы данных
Все команды (процедуры и функции) OpenGL начинаются с префикса gl, а все константы – с префикса GL_. Кроме того, в имена функций и процедур OpenGL входят суффиксы,
Рисование точек, линий и многоугольников
Для задания размеров точки служит процедура glPointSize(GLfloat size), которая устанавливает размер точки в пикселях, по умолчанию он равен единице.
Для задания ширины линии в пикселях слу
Преобразования в пространстве
В процессе построения изображения координаты вершин подвергаются определенным преобразованиям. Подобным преобразованиям подвергаются заданные векторы нормали.
Изначально камера находится в
Получение проекций
Видимым объемом при перспективном преобразовании в OpenGL является усеченная пирамида.
Для задания перспективного преобразования в OpenGL служит процедура gIFrustrum(GLdouble teft, GLdoubt
Освещение
OpenGL использует модель освещённости, в которой свет приходит из нескольких источников, каждый из которых может быть включён или выключен. Кроме того, существует еще общее фоновое (ambient) освеще
Наложение текстуры
Текстурирование позволяет наложить изображение на многоугольник и вывести этот многоугольник с наложенной на него текстурой, соответствующим образом преобразованной. OpenGL поддерживает одно- и дву
Сканеры
Сканером называется устройство, позволяющее вводить в компьютер образы изображений, представленных в виде текста, рисунков, слайдов, фотографий или другой графической информации. Традиционно сканер
Основные характеристики
При выборе конкретной модели сканера необходимо учитывать ряд характеристик, связанных с техническими возможностями модели.
Разрешение (Resolution) – число точек или р
Основные характеристики
Механизм регистрации позволяет получить шаг считывания информации намного меньше шага сетки (до 100 линий на мм). Шаг считывания информации называется разрешением дигитайзера
Цифровые фотокамеры
Цифровая камера получает изображения, обрабатывает их и хранит в цифровом формате. Вместо пленки она использует встроенную или сменную полупроводниковую память, чтобы хранить снимки. Она обладает т
Принцип действия
Принцип действия цифровой фотокамеры аналогичен принципу действия видеокамеры и состоит в следующем. Пучок лучей света от объекта съемки, проходя через линзу (или систему линз) объектива и диафрагм
Фирмы-производители
В настоящее время на рынке работают десятки известнейших фирм-производителей как традиционного фотооборудования и материалов (Kodak, Konica, Nikon, Fuji, Agfa, Olympus и др.), так и компьютерной пе
О С Н О В Ы К О М П Ь Ю Т Е Р Н О Й Г Р А Ф И К И
Учебное пособие
Научный редактор
доктор технических наук,
профессор В.К. Погребной
Редактор И.О.
Новости и инфо для студентов