Методы приоритетов (художника, плавающего горизонта)

↑

▷ Содержание

⇐ ПредыдущаяСтр 18 из 43Следующая ⇒

4.1. Алгоритм Робертса

Этот алгоритм, предложенный в 1963 г., является первой разработкой такого рода и предназначен для удаления невидимых линий при штриховом изображении объектов, составленных из выпуклых многогранников. На нём мы остановимся подробнее.

Выпуклый многогранник однозначно определяется набором плоскостей, образующих его грани, поэтому исходными данными для алгоритма являются многогранники, заданные списком своих граней. Грани задаются в виде плоскостей, заданных в канонической форме (см. гл. 2) в объектной системе координат: .

Рис. 4.2. Внешние нормали тетраэдра

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

.

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

.

Умножая столбцы матрицы на вектор , получим n-мерный вектор, и если все его компоненты неотрицательны, то точка принадлежит многограннику. Это условие будем записывать в виде  (имеется в виду умножение вектор-строки на матрицу).

В алгоритме рассматриваются только отрезки, являющиеся пересечением граней многогранника.

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

.

Эту систему можно записать в матричном виде:

, где .

где  — матрица, составленная из вектор-столбцов . Значит, координаты вершины определяются соотношением

,

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

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

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

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

,

а прямая, идущая в точку, соответствующую параметру t, — уравнением

.

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

.

Эти условия должны выполняться для всех плоскостей.

Полагая , получаем систему уравнений, решения которой дают нам точки «смены видимости» отрезка. Результат можно получить путем совместного решения всевозможных пар уравнений из этой системы. Число всевозможных решений при N плоскостях равно .

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

4.2. Метод Z-буфера

Это один из простейших алгоритмов удаления невидимых поверхностей. Впервые он был предложен Кэтмулом в 1975 г. Работает этот алгоритм в пространстве изображения. Идея Z ‑буфера является простым обобщением идеи о буфере кадра. Буфер кадра используется для запоминания атрибутов каждого пикселя в пространстве изображения, а Z ‑буфер предназначен для запоминания глубины (расстояния от картинной плоскости) каждого видимого пикселя в пространстве изображения. Поскольку достаточно распространенным является использование координатной плоскости XOY в качестве картинной плоскости, то глубина равна координате z точки, отсюда и название буфера. В процессе работы значение глубины каждого нового пикселя, который нужно занести в буфер кадра, сравнивается с глубиной того пикселя, который уже занесен в Z ‑буфер. Если это сравнение показывает, что новый пиксель расположен впереди пикселя, находящегося в буфере кадра, то новый пиксель заносится в этот буфер и, кроме того, производится корректировка Z ‑буфера новым значением глубины. Если же сравнение дает противоположный результат, то никаких действий не производится. По сути, алгоритм является поиском по x и у наибольшего значения функции z(х , у).

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

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

Например, можно разбивать пространство изображения на 4, 16 или больше прямоугольников или полос. В предельном варианте можно использовать буфер размером в одну строку развертки. Для последнего случая был разработан алгоритм построчного сканирования. Поскольку каждый элемент сцены обрабатывается много раз, то сегментирование Z ‑буфера, вообще говоря, приводит к увеличению времени, необходимого для обработки сцены.

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

В целом алгоритм выглядит так:

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

2. Заполнить Z ‑буфер минимальным значением z (глубины) .

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

4. Для каждого объекта

4.1. Для каждого пикселя (х, у) образа вычислить его глубину z (х у).

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

4.3. Если z (х, у) > Z ‑буфер(х у), то занести атрибуты пикселя в буфер кадра и заменить Z ‑буфер(х, у) на z (x у). В противном случае никаких действий не производить.

Алгоритм, использующий Z‑буфер, можно также применять для построения сечений поверхностей. Изменится только оператор сравнения:

z (х, у) > Z ‑буфер(х у) и z(x, у) = z сечения

где z сечения — глубина искомого сечения.

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

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

Пусть поверхность задана уравнением

.

В качестве картинной плоскости выберем плоскость XOY. В области задания функции на осях координат построим сетку узлов:

.

Тогда  представляют собой набор «высот» для данной поверхности по отношению к плоскости XOY. Поверхность будем аппроксимировать треугольниками с вершинами в точках  так, что каждому прямоугольнику сетки узлов будут соответствовать два треугольника:  и . Для построения наглядного изображения поверхности повернем ее на некоторый угол сначала относительно оси OX, а затем относительно оси OY, причем направление вращения выберем таким образом, что точки, соответствующие углам координатной сетки, расположатся в следующем порядке по удаленности от картинной плоскости: , т. е. точка  окажется наиболее близкой к картинной плоскости (и наиболее удаленной от наблюдателя). Предполагается, что способ закрашивания треугольников уже определен. Тогда процесс изображения поверхности можно коротко записать так:

Для i = n , . . . , 1

Для j = m , . . . , 1

         Нарисовать ; нарисовать .

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

Рис. 4.4. Простое каркасное изображение
поверхности

Рис. 4.5. Каркасное изображение с
диагональными ребрами

Алгоритм художника можно применять для полностью закрашенной сцены, а для каркасного изображения, когда объект представляется в виде набора кривых или ломаных линий, он непригоден. Для этого случая предложен еще один метод, весьма эффективный — метод плавающего горизонта. Вернемся к предыдущему примеру изображения поверхности. Каркасное изображение получается путем изображения кривых, получаемых при пересечении этой поверхности плоскостями  и  (рис. 4.4).

На самом деле мы будем рисовать четырехугольник и одну диагональ. В процессе рисования нам понадобятся два целочисленных массива: LHor (нижний горизонт) и HHor (верхний горизонт) размерностью, соответствующей горизонтальному размеру экрана в пикселях. Они нужны для анализа видимости участков изображаемых отрезков. Сначала мы инициализируем верхний горизонт нулем, а нижний — максимальным значением вертикальной координаты на экране. Каждая выводимая на экран точка может закрывать другие точки, которые «скрываются за горизонтом». По мере рисования нижний горизонт «опускается», а верхний «поднимается», постепенно оставляя все меньше незакрытого пространства. В отличие от метода художника, здесь мы продвигаемся от ближнего угла к дальнему. Теперь опишем алгоритм подробнее.

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

Если (HHor[i]<j), то HHor[i]=j; вывести пиксель;

Иначе если (LHor[i]>j), то LHor[i]=j; вывести пиксель

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

Для i = 0 , . . . , n-1

Для j = 0 , . . . , m-1

segment( );segment( );segment( ).

На рис. 4.5 приведен пример изображения поверхности с использованием этого алгоритма.

Познавательные статьи:



Техника прыжка в длину с разбега

Организация работы процедурного кабинета

Области применения синхронных машин

Оптимизация по Винеру и Калману