0.7.1 Алгоритм Сазерленда-Ходгмана

Простой метод решения проблемы охвата отсекаемым многоугольником вершины окна предлагается в алгоритме Сазерленда-Хогдмана [40], когда весь многоугольник последовательно отсекается каждой границей окна, как это показано на рис. 0.3.23.

При отсечении ребра, соединяющего очередную пару вершин K и L, возможны 4 случая взаимного расположения (рис. 0.3.24):

а) ребро на внутренней стороне границы,

б) ребро выходит из окна наружу,

в) ребро на внешней стороне границы,

г) ребро входит снаружи в окно.

Рис. 0.3.22: Относительные расположения ребра и границы окна.

В случае а) в результат добавляется вершина L. В случае б) в результат заносится S - точка пересечения ребра с границей. В случае в) нет вывода. В случае г) выдаются точка пересечения S и конечная точка ребра L.

Для определения взаимного расположения и направленности используется векторное произведение вектора P₁P₂, проведенного из начальной в конечную точку текущего ребра окна, на вектор P₁S из начальной точки текущего ребра окна в очередную вершину S многоугольника (рис. 0.3.25).

Если P₁P₂ ×P₁S < 0, то поворот от P₁P₂     к    P₁S по часовой стрелке, т.е. точка S внутри окна. Если P₁P₂ ×P₁S > 0, то поворот от P₁P₂     к    P₁S против часовой стрелки, т.е. точка S вне окна.

0.7.2 Простой алгоритм отсечения многоугольника

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

0.7.3 Алгоритм отсечения многоугольника Вейлера-Азертона

1. Строятся списки вершин отсекаемого многоугольника и окна.

2. Отыскиваются все точки пересечения. При этом расчете касания не считаются пересечением, т.е. когда вершина или ребро отсекаемого многоугольника инцидентна или совпадает со стороной окна (рис. 0.3.29 и 0.3.30).

3. Списки координат вершин отсекаемого многоугольника и окна дополняются новыми вершинами - координатами точек пересечения. Причем если точка пересечения Pk находится на ребре, соединяющем вершины Vi, Vj, то последовательность точек Vi, Vj превращается в последовательность Vi, Pk, Vj. При этом устанавливаются двухсторонние связи между одноименными точками пересечения в списках вершин отсекаемого многоугольника и окна. Входные и выходные точки пересечения образуют отдельные подсписки входных и выходных точек в списках вершин.

4. Определение части обрабатываемого многоугольника, попавшей в окно выполняется следующим образом: Если не исчерпан список входных точек пересечения, то выбираем очередную входную точку. Двигаемся по вершинам отсекаемого многоугольника пока не обнаружится следующая точка пересечения; все пройденные точки, не включая прервавшую просмотр, заносим в результат; используя двухстороннюю связь точек пересечения, переключаемся на просмотр списка вершин окна. Двигаемся по вершинам окна до обнаружения следующей точки пересечения; все пройденные точки, не включая последнюю, прервавшую просмотр, заносим в результат. Используя двухстороннюю связь точек пересечения, переключаемся на список вершин обрабатываемого многоугольника. Эти действия повторяем пока не будет достигнута исходная вершина - очередная часть отсекаемого многоугольника, попавшая в окно, замкнулась. Переходим на выбор следующей входной точки в списке отсекаемого многоугольника.

6. Алгоритмы удаления невидимых линий и поверхностей. Алгоритм плавающего горизонта. Другие методы удаления невидимых линий к поверхностей: алгоритм Варнока, алгоритм Вейлера-Азертона, алгоритм разбиения криволинейных поверхностей.

Алгоритм плавающего горизонта чаше всего используется для удаления невидимых линий трех­мерного представления функций, описывающих по­верхность в виде:

F(x, у, z) = 0

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

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

На рис. 5.2 приведен пример, где указанные параллельные плоскости определяются по­стоянными значениями z. Функция F(x,у,z) = 0 сводится к последовательности кривых, лежащих в каждой из этих параллельных плоско­стей, например к последовательности у=f(x,z) или х=g(у,z), где z постоянно на каждой из заданных параллельных плоскостей.

Рис. 4.3 Секущие плоскости с постоянной координатой

Рис. 4.4 Секущие плоскости с постоянной координатой

Итак, поверхность теперь складывается из последовательности кривых, лежащих в каж­дой из этих плоскостей, как показано на рис. 5.3. Здесь предполагается, что полученные кривые являются однозначными функциями не­зависимых переменных. Если спроецировать полученные кривые на плоскость z = 0, как показано на рис. 5.4, то сразу становится ясна идея алгоритма удаления невидимых участков исходной поверхности.

Рис. 4.5 Проекция кривых на плоскость z = 0

Алгоритм сначала упорядочивает плоскости z = const по возрастанию расстояния до них от точки наблюдения. Затем для каждой плоскости, начиная с ближайшей к точке наблюдения, строится кривая, лежащая на ней, т. е. для каждого значения координаты х в пространстве изображения определяется соответствующее значение y. Ал­горитм удале­ния невидимой линии заключается в следующем:

Если на текущей плоскости при некотором заданном значении x соответствующее зна­чение у на кривой больше значения y для всех предыдущих кривых при этом значении x, то текущая кривая видима в этой точке; в против­ном случае она невидима.

Невидимые участки показаны пунктиром на рис. 5.4. Реализация данного алгоритма достаточно проста. Для хранения максимальных значений y при каждом значении x ис­пользуется массив, длина которого равна числу различимых точек (разрешению) по оси x в пространстве изображения. Значения, хранящиеся в этом массиве, представляют собой текущие значения "горизонта". Поэтому по мере рисования каждой очередной кривой этот горизонт "всплывает". Фактически этот алгоритм удаления невидимых линий рабо­тает каждый раз с одной ли­нией.

Алгоритм работает очень хорошо до тех пор, пока какая-нибудь очередная кривая не окажется ниже самой пер­вой из кривых, как показано на рис. 5.5а.

Рис. 4.6 Обработка нижней стороны поверхности

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

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

Полученный результат показан на рис. 5.5b.

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

7. Алгоритмы удаления невидимых линий и поверхностей. Алгоритм, использующий 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-буфера состоит в трудоемкости и высокой стоимости устранения лестничного эффекта, а также реализации эффектов прозрачности и просве­чивания. Поскольку алгоритм заносит пикселы в буфер кадра в произвольном порядке, то нелегко получить информацию, необходимую для методов устранения лестничного эффекта, основывающихся на предварительной фильтрации. При реализации эффектов прозрачности и просвечивания, пикселы могут заноситься в буфер кадра в некорректном порядке, что ведет к ло­кальным ошибкам.

Формальное описание алгоритма z-буфера таково:

1. Заполнить буфер кадра фоновым значением интенсивности или цвета.

2. Заполнить z -буфер минимальным значением z.

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

4. Для каждого Пиксел(x,y) в многоугольнике вычислить его глубину z(x,y).

5. Сравнить глубину z(х,у) со значением Zбуфер(х,у), хранящимся в z-буфере в этой же позиции.

Если z(х, у) > Zбуфер (х,у), то записать атрибут этого многоугольника (интенсивность, цвет и т. п.) в буфер кадра и заменить Zбуфер(х,у) на z(х,у). В противном случае никаких действий не производить.

3. Построение изображения (теоретический вопрос)

1. В каких единицах измеряют: разрешение экрана, разрешение принтера, разрешение изображения?

2. Назовите наименьший элемент растрового изображения.

3. Назовите наименьший элемент векторного изображения.

4. Почему цветовую модель RGB называют аддитивной?

5. Почему цветовую модель CMYK называют субтрактивной?

6. Как задается цвет пикселя в режиме True Color? Сколько байтов оперативной памяти для этого нужно?

7. Какие основные цвета вы знаете? Какой цвет дает сумма основных цветов в аддитивной модели?

8. Какие дополнительные цвета вы знаете? Какой цвет дает сумма дополнительных цветов в субтрактивной модели? Какой цвет даст их сумма в аддитивной модели?

9. Для чего предназначены растровые графические редакторы?

10. Какие источники графических изображений для обработки в графическом редакторе вы знаете?

11. Какие форматы графических файлов вы знаете?

12. Что обозначает понятие палитра в графическом формате?

13. Построение реалистических изображений. Свойства человеческого глаза.

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