Задача удаления невидимых линий и поверхностей является одной из наиболее интересных и сложных в компьютерной графике. Алгоритмы удаления заключаются в определении линий ребер, поверхностей или объемов, которые видимы или невидимы для наблюдателя, находящегося в заданной точке пространства.
Необходимость удаления невидимых линий, ребер, поверхностей или объемов проиллюстрирована на рис. 6.1. Рисунок наглядно демонстрирует, что изображение без удаления невидимых линий воспринимается неоднозначно.
(рис 6.1) Неоднозначность восприятия изображения кубаСложность задачи удаления невидимых линий и поверхностей привела к появлению большого числа различных способов ее решения. Многие из них ориентированы на специализированные приложения. Единого (общего) решения этой задачи, годного для различных случаев, естественно, не существует: для каждого случая выбирается наиболее подходящий метод. Например, для моделирования процессов в реальном времени требуются быстрые алгоритмы, в то время как для формирования сложного реалистического изображения, в котором представлены тени, прозрачность и фактура, учитывающие эффекты отражения и преломления цвета в мельчайших оттенках, фактор времени выполнения уже не так существенен. Подобные алгоритмы работают медленно, и зачастую на вычисления требуется несколько минут или даже часов. Существует тесная взаимосвязь между скоростью работы алгоритма и детальностью его результата. Ни один из алгоритмов не может достигнуть хороших оценок для этих двух показателей одновременно. По мере создания все более быстрых алгоритмов можно строить все более детальные изображения. Реальные задачи, однако, всегда будут требовать учета еще большего количества деталей.
Все алгоритмы такого рода так или иначе включают в себя сортировку,
причем главная сортировка ведется по геометрическому расстоянию от
тела, поверхности, ребра или точки до точки наблюдения или картинной
плоскости. Основная идея, положенная в основу сортировки по
расстоянию, заключается в том, что чем дальше расположен объект от
точки наблюдения, тем больше вероятность, что он будет полностью или
частично заслонен одним из объектов, более близких к точке наблюдения.
После определения расстояний или приоритетов по
Алгоритмы удаления невидимых линий или поверхностей можно
классифицировать по способу выбора системы координат или пространства,
в котором они работают. Алгоритмы, работающие в объектном
пространстве, имеют дело с мировой системой координат, в которой
описаны эти объекты. При этом получаются весьма точные результаты,
ограниченные, вообще говоря, лишь
Мы приведем некоторые из алгоритмов, работающих как в объектном пространстве, так и в пространстве изображения, каждый из которых иллюстрирует одну или несколько основополагающих идей теории алгоритмов удаления невидимых линий и поверхностей.
Этот алгоритм, предложенный в 1963 г., является первой разработкой
такого рода и предназначен для удаления невидимых линий при штриховом
изображении объектов, составленных из выпуклых многогранников. Он
относится к алгоритмам, работающим в объектном пространстве, и очень
элегантен с математической точки зрения. В нем очень удачно сочетаются
геометрические методы и методы
Выпуклый многогранник однозначно определяется набором плоскостей, образующих его грани, поэтому исходными данными для алгоритма являются многогранники, заданные списком своих граней. Грани задаются в виде плоскостей, заданных в канонической форме (см. лекцию 3) в объектной системе координат: $$ax+by+cz+d=0$$.
(рис 6.2) Внешние нормали тетраэдраТаким образом, каждая плоскость определяется четырехмерным вектором $$\overline{P}$$, а каждая точка $$\overrightarrow{r}$$, заданная в однородных координатах, также представляет собой четырехмерный вектор:$$\overrightarrow{P}= \begin{pmatrix} a \\ b \\ c \\ d \end{pmatrix}, \overrightarrow{r}= \begin{pmatrix} x \\ y \\ z \\ 1 \end{pmatrix}.$$
Принадлежность точки плоскости можно установить с помощью скалярного произведения, т.е. если $$(\overrightarrow{P}\cdot\overrightarrow{r})=0$$, то точка принадлежит плоскости, если же нет, то знак произведения показывает, по какую сторону от плоскости эта точка находится. В алгоритме Робертса плоскости строятся таким образом, что внутренние точки многогранника лежат в положительной полуплоскости. Это означает, что вектор $$(A,B,C)$$ является внешней нормалью к многограннику (рис. 6.2). Из векторов плоскостей строится прямоугольная матрица порядка $$4\times n$$, которая называется обобщенной матрицей описания многогранника:$$M= \begin{pmatrix} a_1 a_2 a_3 \ldots a_n \\ b_1 b_2 b_3 \ldots b_n \\ c_1 c_2 c_3 \ldots c_n \\ d_1 d_2 d_3 \ldots d_n \end{pmatrix}.$$
Умножая столбцы матрицы на вектор $$\overrightarrow{r}$$, получим n -мерный вектор, и если все его компоненты неотрицательны, то точка принадлежит многограннику. Это условие будем записывать в виде $$(\overrightarrow{r}\cdot M)\ge 0$$ (имеется в виду умножение вектор-строки на матрицу).
В своем алгоритме Робертс рассматривает только отрезки, являющиеся пересечением граней многогранника.
Из обобщенной матрицы можно получить информацию о том, какие грани многогранника пересекаются в вершинах. Действительно, если вершина $$\overrightarrow{v}=(x,y,z,1)$$ принадлежит граням $$\overrightarrow{P}_1, \; \overrightarrow{P}_2, \; \overrightarrow{P}_3$$, то она удовлетворяет уравнениям$$\left. \begin{aligned} (\overrightarrow{v}\cdot\overrightarrow{P}_1)=0 \\ (\overrightarrow{v}\cdot\overrightarrow{P}_2)=0 \\ (\overrightarrow{v}\cdot\overrightarrow{P}_3)=0 \\ (\overrightarrow{v}\cdot\overrightarrow{e}_4)=1 \end{aligned} \right\} , \quad \text{где} \quad \overrightarrow{e}_4= \begin{pmatrix} 0 \\ 0 \\ 0 \\ 1 \end{pmatrix}$$ Эту систему можно записать в матричном виде:$$\overrightarrow{v}\cdot Q = \overrightarrow{e}_4,$$ где $$Q$$ - матрица, составленная из вектор-столбцов $$\overrightarrow{P}_1, \overrightarrow{P}_2, \overrightarrow{P}_3, \overrightarrow{e}_4$$. Значит, координаты вершины определяются соотношением$$\overrightarrow{v}=\overrightarrow{e}_4\cdot Q^{(-1)},$$ т.е. они составляют последнюю строку обратной матрицы. А это означает, что если для каких-либо трех плоскостей обратная матрица существует, то плоскости имеют общую вершину.
Алгоритм прежде всего удаляет из каждого многогранника те ребра или грани, которые экранируются самим телом. Робертс использовал для этого простой тест: если одна или обе смежные грани обращены своей внешней поверхностью к наблюдателю, то ребро является видимым. Тест этот выполняется вычислением скалярного произведения координат наблюдателя на вектор внешней нормали грани: если результат отрицательный, то грань видима.
Затем каждое из видимых ребер каждого многогранника сравнивается с каждым из оставшихся многогранников для определения того, какая его часть или части, если таковые есть, экранируются этими телами. Для этого в каждую точку ребра проводится отрезок луча, выходящего из точки расположения наблюдателя. Если отрезок не пересекает ни одного из многогранников, то точка видима. Для решения этой задачи используются параметрические уравнения прямой, содержащей ребро, и луча.
Если заданы концы отрезка $$\overrightarrow{r}$$ и $$\overrightarrow{s}$$, а наблюдатель расположен в точке $$\overrightarrow{u}$$, то отрезок задается уравнением$$\overrightarrow{v}=\overrightarrow{r}+t\cdot(\overrightarrow{s}-\overrightarrow{r})\equiv\overrightarrow{r}+t\cdot\overrightarrow{d}, \quad 0 \le t \le 1,$$ а прямая, идущая в точку, соответствующую параметру $$t$$, - уравнением$$\overrightarrow{w}=\overrightarrow{v}+\tau\cdot\overrightarrow{g}=\overrightarrow{r}+t\cdot\overrightarrow{d}+\tau\cdot\overrightarrow{g}.$$
Для определения той части отрезка, которая закрывается каким-либо телом, достаточно найти значения $$t$$ и $$\tau$$, при которых произведение вектора $$\overrightarrow{w}$$ на обобщенную матрицу положительно. Для каждой плоскости $$\overrightarrow{P}_i$$ записывается неравенство$$q_i=(\overrightarrow{v}\cdot\overrightarrow{P}_i)+t(\overrightarrow{d}\cdot\overrightarrow{P}_i)+\tau(\overrightarrow{g}\cdot\overrightarrow{P}_i)>0.$$ Эти условия должны выполняться для всех плоскостей.
Полагая $$q_i=0$$, получаем систему уравнений, решения которой дают нам точки "смены видимости" отрезка. Результат можно получить путем совместного решения всевозможных пар уравнений из этой системы. Число всевозможных решений при $$N$$ плоскостях равно $$N\cdot(N-1)/2$$.
Так как объем вычислений растет с увеличением числа многоугольников, то желательно по мере возможности сокращать их число, т.е. если мы аппроксимируем некоторую поверхность многогранником, то в качестве граней можно использовать не треугольники, а более сложные многоугольники. При этом, разумеется, встает проблема, как построить такой многоугольник, чтобы он мало отклонялся от плоской фигуры.
В отличие от алгоритма Робертса, Варнок в 1968 г. предложил алгоритм, работающий не в объектном пространстве, а в пространстве образа. Он также нацелен на изображение многогранников, а главная идея его основана на гипотезе о способе обработки информации, содержащейся в сцене, глазом и мозгом человека. Эта гипотеза заключается в том, что тратится очень мало времени и усилий на обработку тех областей, которые содержат мало информации. Большая часть времени и труда затрачивается на области с высоким информационным содержимым. Так, например, рассматривая помещение, в котором имеется только картина на стене, мы быстро осматриваем стены, пол и потолок, а затем все внимание сосредоточиваем на картине. В свою очередь, на этой картине, если это портрет, мы бегло отмечаем фон, а затем более внимательно рассматриваем лицо изображенного персонажа, в особенности глаза, губы. Как правило, достаточно детально рассматриваются еще и руки и с чуть меньшим вниманием - одежда.
В алгоритме Варнока и его вариантах делается попытка воспользоваться тем, что большие области изображения однородны. Такое свойство называют когерентностью, имея в виду, что смежные области (пиксели) вдоль обеих осей х и у имеют тенденцию к однородности.
В пространстве изображения рассматривается окно и решается вопрос о том, пусто ли оно, или его содержимое достаточно просто для визуализации. Если это не так, то окно разбивается на фрагменты до тех пор, пока содержимое фрагмента не станет достаточно простым для визуализации или его размер не достигнет требуемого предела разрешения. В последнем случае информация, содержащаяся в окне, усредняется, и результат изображается с одинаковой интенсивностью или цветом.
Конкретная реализация алгоритма Варнока зависит от метода разбиения окна и от деталей критерия, используемого для того, чтобы решить, является ли содержимое окна достаточно простым. В оригинальной версии алгоритма каждое окно разбивалось на четыре одинаковых подокна. Многоугольник, входящий в изображаемую сцену, по отношению к окну будем называть (рис. 6.3)
(рис 6.3) Варианты расположения многоугольника по отношению к окнуТеперь можно в самом общем виде описать алгоритм.
Для каждого окна:
Шаги 1–4 рассматривают ситуацию пересечения окна только с одним многоугольником. Они используются для сокращения числа подразбиений. Шаг 5 решает задачу удаления невидимых поверхностей. Многоугольник, находящийся ближе всех к точке наблюдения, экранирует все остальные.
Для реализации алгоритма необходимы функции, определяющие взаимное расположение окна и многоугольника, которые достаточно легко реализуются в случае прямоугольных окон и выпуклых многоугольников. Для определения, является ли многоугольник охватывающим, внешним или внутренним, можно воспользоваться, например, погружением многоугольника в прямоугольную оболочку. Для определения наличия пересечений можно использовать опорные прямые (так же, как использовались плоскости в алгоритме Робертса). Если же многоугольник невыпуклый, то задача усложняется. Методы решения такого рода задач будут рассмотрены в главе, относящейся к геометрическому поиску.
Следует заметить, что существуют различные реализации алгоритма Варнока. Были предложены варианты оптимизации, использующие предварительную сортировку многоугольников по глубине, т. е. по расстоянию от точки наблюдения, и другие.
Вейлер и Азертон попытались оптимизировать алгоритм Варнока в отношении числа выполняемых разбиений, перейдя от прямоугольных разбиений к разбиениям вдоль границ многоугольников (1977). Для этого они использовали ими же разработанный алгоритм отсечения многоугольников. Алгоритм работает в объектном пространстве, и результатом его работы являются многоугольники. В самом общем виде он состоит из четырех шагов.
В процессе предварительной сортировки создается список приблизительных приоритетов, причем близость многоугольника к точке наблюдения определяется расстоянием до ближайшей к ней вершины. Затем выполняется отсечение по самому первому из многоугольников. Отсечению подвергаются все многоугольники из списка, причем эта операция выполняется над проекциями многоугольников на картинную плоскость. При этом создаются списки внешних и внутренних фигур. Все попавшие в список внешних не экранируются отсекающим многоугольником. Затем рассматривается список внутренних многоугольников и выполняется сортировка по расстоянию до отсекающего многоугольника. Если все вершины некоторого многоугольника оказываются дальше от наблюдателя, чем самая удаленная из вершин экранирующего, то они невидимы, и тогда они удаляются. После этого работа алгоритма продолжается с внешним списком.
Если какая-то из вершин внутреннего многоугольника оказывается ближе к наблюдателю, чем ближайшая из вершин экранирующего многоугольника, то такой многоугольник является частично видимым. В этом случае предварительный список приоритетов некорректен, и тогда в качестве нового отсекающего многоугольника выбирается именно этот "нарушитель порядка". При этом используется именно исходный многоугольник, а не тот, что получился в результате первого отсечения. Такой подход позволяет минимизировать число разбиений.
Этот алгоритм в дальнейшем был обобщен Кэтмулом (1974) для изображения гладких бикубических поверхностей. Его подход заключался в том, что разбиению подвергалась поверхность. Коротко этот алгоритм можно описать так:
Эффективность такого метода, как и алгоритм Варнока, зависит от эффективности разбиений. В дальнейшем этот алгоритм был распространен на сплайновые поверхности.
Это один из простейших алгоритмов удаления невидимых поверхностей. Впервые он был предложен Кэтмулом в 1975 г. Работает этот алгоритм в пространстве изображения. Идея Z-буфера является простым обобщением идеи о буфере кадра. Буфер кадра используется для запоминания атрибутов каждого пикселя в пространстве изображения, а Z-буфер предназначен для запоминания глубины (расстояния от картинной плоскости) каждого видимого пикселя в пространстве изображения. Поскольку достаточно распространенным является использование координатной плоскости $$XOY$$ в качестве картинной плоскости, то глубина равна координате $$z$$ точки, отсюда и название буфера. В процессе работы значение глубины каждого нового пикселя, который нужно занести в буфер кадра, сравнивается с глубиной того пикселя, который уже занесен в Z-буфер. Если это сравнение показывает, что новый пиксель расположен впереди пикселя, находящегося в буфере кадра, то новый пиксель заносится в этот буфер и, кроме того, производится корректировка Z-буфера новым значением глубины. Если же сравнение дает противоположный результат, то никаких действий не производится. По сути, алгоритм является поиском по $$x$$ и $$у$$ наибольшего значения функции $$z(х,у)$$.
Главное преимущество алгоритма - его простота. Кроме того, этот алгоритм решает задачу об удалении невидимых поверхностей и делает тривиальной визуализацию пересечений сложных поверхностей. Сцены могут быть любой сложности. Поскольку габариты пространства изображения фиксированы, оценка вычислительной трудоемкости алгоритма не более чем линейна. Поскольку элементы сцены или картинки можно заносить в буфер кадра или в Z-буфер в произвольном порядке, их не нужно предварительно сортировать по приоритету глубины. Поэтому экономится вычислительное время, затрачиваемое на сортировку по глубине.
Основной недостаток алгоритма - большой объем требуемой памяти. В последнее время в связи с быстрым ростом возможностей вычислительной техники этот недостаток становится менее лимитирующим. Но в то время, когда алгоритм еще только появился, приходилось изобретать способы создания буфера как можно большего объема при имеющемся ресурсе памяти.
Например, можно разбивать пространство изображения на 4, 16 или больше прямоугольников или полос. В предельном варианте можно использовать буфер размером в одну строку развертки. Для последнего случая был разработан алгоритм построчного сканирования. Поскольку каждый элемент сцены обрабатывается много раз, то сегментирование Z-буфера, вообще говоря, приводит к увеличению времени, необходимого для обработки сцены.
Другой недостаток алгоритма состоит в трудоемкости реализации эффектов, связанных с полупрозрачностью, и ряда других специальных задач, повышающих реалистичность изображения. Поскольку алгоритм заносит пиксели в буфер кадра в произвольном порядке, то довольно сложно получить информацию, которая необходима для методов, основывающихся на предварительном анализе сцены.
В целом алгоритм выглядит так:
4.1. Для каждого пикселя $$(x,y)$$ образа вычислить его глубину $$z(x,y)$$.
4.2. Сравнить глубину $$z(x,y)$$ со значением глубины, хранящимся в Z-буфере в этой же позиции.
4.3. Если $$z(x,y)>Z- \text{буфер}(x,y)$$, то занести атрибуты пикселя в буфер кадра и заменить $$Z-\text{буфер}(x,y) на z(x,y)$$. В противном случае никаких действий не производить.
Алгоритм, использующий Z-буфер, можно также применять для построения сечений поверхностей. Изменится только оператор сравнения:$$z(x,y)>Z-\text{буфер}(x,y)\text{ и }z(x,y)=z\text{ сечения}$$ где $$z\text{ сечения}$$ - глубина искомого сечения.
Здесь мы рассмотрим группу методов, учитывающих специфику изображаемой сцены для удаления невидимых линий и поверхностей.
При изображении сцен со сплошным закрашиванием поверхностей можно воспользоваться методом художника: элементы сцены изображаются в последовательности от наиболее удаленных от наблюдателя к более близким. При экранировании одних участков сцены другими невидимые участки просто закрашиваются. Если вычислительная трудоемкость получения изображения для отдельных элементов достаточно высока, то такой алгоритм будет не самым лучшим по эффективности, но зато мы избежим анализа (и вполне возможно, тоже дорогостоящего), позволяющего установить, какие же из элементов изображать не надо в силу их невидимости. Например, при изображении правильного многогранника мы довольно легко можем упорядочить его грани по глубине, но такая сортировка для произвольного многогранника возможна далеко не всегда. Мы рассмотрим применение этого метода на примере изображения поверхности, заданной в виде однозначной функции двух переменных.
Пусть поверхность задана уравнением$$z=f(x,y), \quad a\le x \le b, \quad c \le y \le d.$$ В качестве картинной плоскости выберем плоскость $$XOY$$. В области задания функции на осях координат построим сетку узлов:$$a=x_0<x_1<\ldots<x_{n-1}=b, \quad c=y_0<y_1<\ldots<y_{m-1}<y_m=d.$$
Тогда $$z_{ij}=f(x_i,y_i)$$ представляют собой набор "высот" для данной поверхности по отношению к плоскости $$XOY$$. Поверхность будем аппроксимировать треугольниками с вершинами в точках $$\overrightarrow{r}_{ij}=(x_i,y_i,z_{ij})$$ так, что каждому прямоугольнику сетки узлов будут соответствовать два треугольника: $$tr_{i_{j}\:j}^1=\{\overrightarrow{r}_{ij},\overrightarrow{r}_{i+1\:j},\overrightarrow{r}_{i+1\:j+1}\}$$ и $$tr_{i_{j}\:j}^2=\{\overrightarrow{r}_{ij},\overrightarrow{r}_{i\:j+1},\overrightarrow{r}_{i+1\:j+1}\}$$. Для построения наглядного изображения поверхности повернем ее на некоторый угол сначала относительно оси $$OX$$, а затем относительно оси $$OY$$, причем направление вращения выберем таким образом, что точки, соответствующие углам координатной сетки, расположатся в следующем порядке по удаленности от картинной плоскости: $$\overrightarrow{r}_{nm},\overrightarrow{r}_{n0},\overrightarrow{r}_{0m},\overrightarrow{r}_{00}$$, т.е. точка $$\overrightarrow{r}_{nm}$$ окажется наиболее близкой к картинной плоскости (и наиболее удаленной от наблюдателя). Предполагается, что способ закрашивания треугольников уже определен. Тогда процесс изображения поверхности можно коротко записать так:$$\begin{aligned} \text{Для } i=n,\ldots,1 \\ \qquad\qquad\text{Для } j=m,\ldots,1 \\ \qquad\qquad\qquad\qquad\text{Нарисовать }tr_{i\:j}^1;\; \text{нарисовать }tr_{i\:j}^2. \end{aligned}$$
При такой последовательности вывода изображения мы продвигаемся от самого удаленного треугольника к все более близким, частично закрашивая уже изображенные участки поверхности.
(рис 6.5) Простое каркасное изображение с поверхности(рис 6.4) Каркасное изображение диагональными ребрамиАлгоритм художника можно применять для полностью закрашенной сцены, а для каркасного изображения, когда объект представляется в виде набора кривых или ломаных линий, он непригоден. Для этого случая предложен еще один метод, весьма эффективный - метод плавающего горизонта. Вернемся к предыдущему примеру изображения поверхности. Каркасное изображение получается путем изображения кривых, получаемых при пересечении этой поверхности плоскостями $$x=x_i$$ и $$y=y_i$$ (рис. 6.4).
На самом деле мы будем рисовать четырехугольник и одну диагональ. В процессе рисования нам понадобятся два целочисленных массива: $$LHor$$ (нижний горизонт) и $$HHor$$ (верхний горизонт) размерностью, соответствующей горизонтальному размеру экрана в пикселях. Они нужны для анализа видимости участков изображаемых отрезков. Сначала мы инициализируем верхний горизонт нулем, а нижний - максимальным значением вертикальной координаты на экране. Каждая выводимая на экран точка может закрывать другие точки, которые "скрываются за горизонтом". По мере рисования нижний горизонт "опускается", а верхний "поднимается", постепенно оставляя все меньше незакрытого пространства. В отличие от метода художника, здесь мы продвигаемся от ближнего угла к дальнему. Теперь опишем алгоритм подробнее.
Функция $$segment$$ в этом фрагменте предназначена для вывода на экран отрезка прямой, причем в момент инициализации очередного пикселя $$(i,j)$$ она выполняет следующие действия:$$\begin{aligned} \text{Если }(HHor[i]<j),\text{ то }HHor[i]=j;\text{ вывести пиксель}; \\ \text{Иначе если }(LHor[i]>j),\text{ то }LHor[i]=j;\text{ вывести пиксель}. \end{aligned}$$ Таким образом, пиксель выводится только в том случае, если он выше верхнего или ниже нижнего горизонта, после чего его координаты уже сами становятся одним из горизонтов. А в целом алгоритм будет выглядеть так:$$\begin{aligned} \text{Для }i=0,\ldots,n-1 \\ \qquad\text{Для }j=0,\ldots,m-1 \\ \qquad\qquad segment(x_i,y_i,x_{i+1},y_j);segment(x_i,y_i,x_{i+1},y_{j+1});\\ \qquad \qquad \qquad segment(x_i,y_i,x_i,y_{j+1}). \end{aligned}$$ На рис. 6.5 приведен пример изображения поверхности с использованием этого алгоритма.
Идея построчного сканирования, предложенная в 1967 г. Уайли, Ромни,
Эвансом и Эрдалом, заключалась в том, что сцена обрабатывается в
порядке прохождения сканирующей прямой. В объектном пространстве это
соответствует проведению секущей плоскости, перпендикулярной
пространству изображения. Строго говоря, алгоритм работает именно в
пространстве изображения, отыскивая точки пересечения сканирующей
прямой с ребрами многоугольников, составляющих картину (для случая
изображения многогранников). Но при пересечении очередного элемента
рисунка выполняется анализ глубины полученной точки и сравнение ее с
глубиной других точек на сканирующей плоскости. В некоторых случаях
можно построить
Один из таких методов мы уже рассматривали - метод Z–буфера, в котором буфер инициализируется заново для каждой сканирующей строки. Другой метод называют интервальным алгоритмом построчного сканирования. В нем сканирующая строка разбивается проекциями точек пересечения ребер многоугольников на интервалы, затем в каждом из интервалов выбираются видимые отрезки. В этой ситуации их уже можно отсортировать по глубине. Мы остановимся чуть подробнее на методе построчного сканирования для криволинейных поверхностей.
В описании метода приоритетов поверхность задавалась в виде функции двух переменных, здесь мы будем задавать поверхность параметрическими уравнениями:$$x=x(u,v),\quad y=y(u,v),\quad z=z(u,v).$$
Пересечение сканирующей плоскости $$y=y_1$$ с поверхностью дает нам так называемую линию уровня, или изолинию. Эта кривая может быть неодносвязной, т. е. состоять из нескольких отдельных кривых. Чтобы получить эту кривую, мы должны решить уравнение$$y(u,v)=y_i$$ и, определив значения параметров $$u,v$$, найти точки кривой. Для получения решения можно воспользоваться численными итерационными методами, но это вносит дополнительные проблемы (например, при плохом выборе начального приближения итерационный процесс может не сойтись). Выбор подходящего метода решения лежит вне задач нашего курса, поэтому перейдем к описанию алгоритма, считая, что он уже выбран и надежно работает.$$\begin{aligned} \text{Для каждой сканирующей строки со значением ординаты } y_i: \\ \quad\text{Для каждого значения абсциссы } x_j: \\ \qquad\text{Для всех решений уравнений } u=u(x_j,y_j),\;v=v(x_j,y_j) \text{ вычислить глубину } z=z(u,v). \\ \qquad\text{Определить точку с наименьшим значением глубины}\\ \qquad\text{и изобразить.} \end{aligned}$$
Второй шаг этого алгоритма предполагает, что решение отыскивается
только для тех элементов поверхности (или группы поверхностей, если
речь идет о более сложной сцене, содержащей
Теперь разберем один способ использования метода художника при
изображении пространственных сцен, содержащих несколько объектов или
В каждом узле дерева левое поддерево будет содержать грани, отделенные плоскостью, а правое - не отделенные. Рисование сцены осуществляется с помощью рекурсивного алгоритма следующего вида:$$\begin{aligned} \text{Рисуем дерево }(T): \\ \text{Если наблюдатель находится в положительной полуплоскости, то:} \\ \qquad\text{Если правое поддерево }TR \text{ не пусто, рисуем дерево }(TR). \\ \qquad\text{Рисуем корневую грань.} \\ \qquad\text{Если левое поддерево }TL \text{ не пусто, рисуем дерево }(TL). \\ \text{Иначе} \\ \qquad\text{Если левое поддерево }TL \text{ не пусто, рисуем дерево }(TL). \\ \qquad\text{Рисуем корневую грань.} \\ \qquad\text{Если правое поддерево }TR\text{ не пусто, рисуем дерево }(TR). \end{aligned}$$
(рис 6.6) Разбиение пространства и соответствующее ему деревоПостроение плоскостей и дерева в данном случае осуществляется "вручную". Для эффективности работы алгоритма надо стремиться к тому, чтобы дерево было сбалансированным. Если какие-то грани не удается отделить, то их пересекают плоскостями и рисуют как два объекта. Способ определения, по какую сторону плоскости находится наблюдатель, а по какую - грань, очень прост. Параметр плоскости $$d$$ для каждой грани будем задавать так, чтобы грань находилась в положительной полуплоскости. Тогда если при подстановке координат наблюдателя в это уравнение получаем положительное значение, то он находится в одной полуплоскости с гранью, если нет, то в разных.
Алгоритм может применяться не только к многогранникам, но и вообще к любой сцене при условии, что имеется алгоритм изображения составляющих ее объектов. На рис. 6.6 изображена проекция сцены, разбитой вертикальными плоскостями, и соответствующее ей дерево. Положение наблюдателя отмечено кружком с буквой Н. При этой точке зрения объекты будут изображаться в последовательности 5, 6, 1, 2, 3, 4.
Главная идея этого алгоритма была предложена в 1968 г. А.Аппелем, а первая реализация была выполнена в 1971 г.
Наблюдатель видит любой объект посредством испускаемого неким
источником света, который падает на этот объект, отражается или
преломляется согласно законам оптики и затем каким-то путем доходит до
глаза наблюдателя. Из огромного множества лучей света, выпущенных
источником, лишь небольшая часть дойдет до наблюдателя. Следовательно,
отслеживать пути лучей в таком порядке неэффективно с точки зрения
вычислений. Аппель предложил отслеживать (трассировать) лучи в
обратном направлении, т.е. от наблюдателя к объекту. В первой
реализации этого метода трассировка прекращалась, как только луч
пересекал поверхность видимого непрозрачного объекта; т.е. луч
использовался только для обработки скрытых или видимых поверхностей.
Впоследствии были реализованы алгоритмы трассировки лучей с
использованием более
(рис 6.8) Трассировка параллельными лучами(рис 6.7) Трассировка с центральной точкойВ этом алгоритме предполагается, что сцена уже преобразована в пространство изображения. Если используется ортографическая проекция, то точка зрения или наблюдатель находится в бесконечности на положительной полуоси $$OZ$$. В этом случае все световые лучи, идущие от наблюдателя, параллельны оси (рис. 6.7). Каждый луч проходит через пиксель растра до сцены. Траектория каждого луча отслеживается, чтобы определить, какие именно объекты сцены, если таковые существуют, пересекаются с данным лучом. Необходимо проверить пересечение каждого объекта сцены с каждым лучом. Если луч пересекает объект, то определяются все возможные точки пересечения луча и объекта. Можно получить большое количество пересечений, если рассматривать много объектов. Эти пересечения упорядочиваются по глубине. Пересечение с максимальным значением $$z$$ представляет видимую поверхность для данного пикселя. Атрибуты этого объекта используются для определения характеристик пикселя.
Если точка зрения находится не в бесконечности (перспективная проекция), алгоритм трассировки лучей лишь незначительно усложняется. Здесь предполагается, что наблюдатель по-прежнему находится на положительной полуоси $$OZ$$. Картинная плоскость, т.е. растр, перпендикулярна оси $$OZ$$, как показано на рис. 6.8.
Наиболее важным и трудоемким элементом этого алгоритма является процедура определения пересечений, поскольку эта задача отнимает наибольшую часть времени всей работы алгоритма. Поэтому эффективность методов поиска особенно важна. Объекты сцены могут состоять из набора плоских многоугольников, многогранников или тел, ограниченных замкнутыми параметрическими поверхностями. Для ускорения поиска важно иметь эффективные критерии, позволяющие исключить из процесса заведомо лишние объекты.
Одним из способов сокращения числа пересекаемых объектов является
погружение объектов в
Особенно просто выполняется тест на пересечение со сферической оболочкой (в лекции 3 были рассмотрены задачи о пересечении луча со сферой и плоскостью). Несколько большего объема вычислений требует задача о пересечении с прямоугольным параллелепипедом, поскольку необходимо проверить пересечение луча по меньшей мере с тремя бесконечными плоскостями, ограничивающими прямоугольную оболочку. Поскольку точки пересечения могут оказаться вне граней этого параллелепипеда, для каждой из них следует, кроме того, произвести проверку на попадание внутрь. Следовательно, для трех измерений тест с прямоугольной оболочкой оказывается более медленным, чем тест со сферической оболочкой.
После выполнения этих первичных тестов начинается процесс поиска пересечений с объектами, попавшими в список потенциально видимых. При этом задача формирования изображения не исчерпывается нахождением самой точки пересечения: если мы учитываем эффекты отражения и преломления, необходимо отслеживать дальнейший путь луча, для чего, как правило, требуется восстановить нормаль к поверхности, а также определить направление отраженного или преломленного луча. В связи со всеми этими задачами важно выбрать достаточно удобные аппроксимации поверхностей, составляющих сцену. Определение атрибутов пикселя, выводимого в конечном итоге на экран, зависит от выбора модели освещения, о чем более подробно будет рассказано в последующих лекциях.
Алгоритм трассировки лучей для простых непрозрачных поверхностей можно представить следующим образом.
Создать список объектов, содержащий:
Для каждого трассируемого луча:
Выполнить для каждого объекта трехмерный тест на пересечение с оболочкой. Если луч пересекает эту оболочку, то занести объект в список активных объектов.
Если список активных объектов пуст, то изобразить данный пиксель с фоновым значением цвета и продолжать работу. В противном случае для каждого объекта из списка активных объектов:
В настоящее время алгоритм трассировки, несмотря на вычислительную сложность, стал очень популярен, особенно в тех случаях, когда время формирования изображения не очень существенно, но хочется добиться как можно большей реалистичности изображения.
Задача удаления невидимых линий и поверхностей является одной из наиболее интересных и сложных в компьютерной графике. Алгоритмы удаления заключаются в определении линий ребер, поверхностей или объемов, которые видимы или невидимы для наблюдателя, находящегося в заданной точке пространства.
Необходимость удаления невидимых линий, ребер, поверхностей или объемов проиллюстрирована на рис. 6.1. Рисунок наглядно демонстрирует, что изображение без удаления невидимых линий воспринимается неоднозначно.
(рис 6.1) Неоднозначность восприятия изображения кубаСложность задачи удаления невидимых линий и поверхностей привела к появлению большого числа различных способов ее решения. Многие из них ориентированы на специализированные приложения. Единого (общего) решения этой задачи, годного для различных случаев, естественно, не существует: для каждого случая выбирается наиболее подходящий метод. Например, для моделирования процессов в реальном времени требуются быстрые алгоритмы, в то время как для формирования сложного реалистического изображения, в котором представлены тени, прозрачность и фактура, учитывающие эффекты отражения и преломления цвета в мельчайших оттенках, фактор времени выполнения уже не так существенен. Подобные алгоритмы работают медленно, и зачастую на вычисления требуется несколько минут или даже часов. Существует тесная взаимосвязь между скоростью работы алгоритма и детальностью его результата. Ни один из алгоритмов не может достигнуть хороших оценок для этих двух показателей одновременно. По мере создания все более быстрых алгоритмов можно строить все более детальные изображения. Реальные задачи, однако, всегда будут требовать учета еще большего количества деталей.
Все алгоритмы такого рода так или иначе включают в себя сортировку,
причем главная сортировка ведется по геометрическому расстоянию от
тела, поверхности, ребра или точки до точки наблюдения или картинной
плоскости. Основная идея, положенная в основу сортировки по
расстоянию, заключается в том, что чем дальше расположен объект от
точки наблюдения, тем больше вероятность, что он будет полностью или
частично заслонен одним из объектов, более близких к точке наблюдения.
После определения расстояний или приоритетов по
Алгоритмы удаления невидимых линий или поверхностей можно
классифицировать по способу выбора системы координат или пространства,
в котором они работают. Алгоритмы, работающие в объектном
пространстве, имеют дело с мировой системой координат, в которой
описаны эти объекты. При этом получаются весьма точные результаты,
ограниченные, вообще говоря, лишь
Мы приведем некоторые из алгоритмов, работающих как в объектном пространстве, так и в пространстве изображения, каждый из которых иллюстрирует одну или несколько основополагающих идей теории алгоритмов удаления невидимых линий и поверхностей.
Этот алгоритм, предложенный в 1963 г., является первой разработкой
такого рода и предназначен для удаления невидимых линий при штриховом
изображении объектов, составленных из выпуклых многогранников. Он
относится к алгоритмам, работающим в объектном пространстве, и очень
элегантен с математической точки зрения. В нем очень удачно сочетаются
геометрические методы и методы
Выпуклый многогранник однозначно определяется набором плоскостей, образующих его грани, поэтому исходными данными для алгоритма являются многогранники, заданные списком своих граней. Грани задаются в виде плоскостей, заданных в канонической форме (см. лекцию 3) в объектной системе координат: $$ax+by+cz+d=0$$.
(рис 6.2) Внешние нормали тетраэдраТаким образом, каждая плоскость определяется четырехмерным вектором $$\overline{P}$$, а каждая точка $$\overrightarrow{r}$$, заданная в однородных координатах, также представляет собой четырехмерный вектор:$$\overrightarrow{P}= \begin{pmatrix} a \\ b \\ c \\ d \end{pmatrix}, \overrightarrow{r}= \begin{pmatrix} x \\ y \\ z \\ 1 \end{pmatrix}.$$
Принадлежность точки плоскости можно установить с помощью скалярного произведения, т.е. если $$(\overrightarrow{P}\cdot\overrightarrow{r})=0$$, то точка принадлежит плоскости, если же нет, то знак произведения показывает, по какую сторону от плоскости эта точка находится. В алгоритме Робертса плоскости строятся таким образом, что внутренние точки многогранника лежат в положительной полуплоскости. Это означает, что вектор $$(A,B,C)$$ является внешней нормалью к многограннику (рис. 6.2). Из векторов плоскостей строится прямоугольная матрица порядка $$4\times n$$, которая называется обобщенной матрицей описания многогранника:$$M= \begin{pmatrix} a_1 a_2 a_3 \ldots a_n \\ b_1 b_2 b_3 \ldots b_n \\ c_1 c_2 c_3 \ldots c_n \\ d_1 d_2 d_3 \ldots d_n \end{pmatrix}.$$
Умножая столбцы матрицы на вектор $$\overrightarrow{r}$$, получим n -мерный вектор, и если все его компоненты неотрицательны, то точка принадлежит многограннику. Это условие будем записывать в виде $$(\overrightarrow{r}\cdot M)\ge 0$$ (имеется в виду умножение вектор-строки на матрицу).
В своем алгоритме Робертс рассматривает только отрезки, являющиеся пересечением граней многогранника.
Из обобщенной матрицы можно получить информацию о том, какие грани многогранника пересекаются в вершинах. Действительно, если вершина $$\overrightarrow{v}=(x,y,z,1)$$ принадлежит граням $$\overrightarrow{P}_1, \; \overrightarrow{P}_2, \; \overrightarrow{P}_3$$, то она удовлетворяет уравнениям$$\left. \begin{aligned} (\overrightarrow{v}\cdot\overrightarrow{P}_1)=0 \\ (\overrightarrow{v}\cdot\overrightarrow{P}_2)=0 \\ (\overrightarrow{v}\cdot\overrightarrow{P}_3)=0 \\ (\overrightarrow{v}\cdot\overrightarrow{e}_4)=1 \end{aligned} \right\} , \quad \text{где} \quad \overrightarrow{e}_4= \begin{pmatrix} 0 \\ 0 \\ 0 \\ 1 \end{pmatrix}$$ Эту систему можно записать в матричном виде:$$\overrightarrow{v}\cdot Q = \overrightarrow{e}_4,$$ где $$Q$$ - матрица, составленная из вектор-столбцов $$\overrightarrow{P}_1, \overrightarrow{P}_2, \overrightarrow{P}_3, \overrightarrow{e}_4$$. Значит, координаты вершины определяются соотношением$$\overrightarrow{v}=\overrightarrow{e}_4\cdot Q^{(-1)},$$ т.е. они составляют последнюю строку обратной матрицы. А это означает, что если для каких-либо трех плоскостей обратная матрица существует, то плоскости имеют общую вершину.
Алгоритм прежде всего удаляет из каждого многогранника те ребра или грани, которые экранируются самим телом. Робертс использовал для этого простой тест: если одна или обе смежные грани обращены своей внешней поверхностью к наблюдателю, то ребро является видимым. Тест этот выполняется вычислением скалярного произведения координат наблюдателя на вектор внешней нормали грани: если результат отрицательный, то грань видима.
Затем каждое из видимых ребер каждого многогранника сравнивается с каждым из оставшихся многогранников для определения того, какая его часть или части, если таковые есть, экранируются этими телами. Для этого в каждую точку ребра проводится отрезок луча, выходящего из точки расположения наблюдателя. Если отрезок не пересекает ни одного из многогранников, то точка видима. Для решения этой задачи используются параметрические уравнения прямой, содержащей ребро, и луча.
Если заданы концы отрезка $$\overrightarrow{r}$$ и $$\overrightarrow{s}$$, а наблюдатель расположен в точке $$\overrightarrow{u}$$, то отрезок задается уравнением$$\overrightarrow{v}=\overrightarrow{r}+t\cdot(\overrightarrow{s}-\overrightarrow{r})\equiv\overrightarrow{r}+t\cdot\overrightarrow{d}, \quad 0 \le t \le 1,$$ а прямая, идущая в точку, соответствующую параметру $$t$$, - уравнением$$\overrightarrow{w}=\overrightarrow{v}+\tau\cdot\overrightarrow{g}=\overrightarrow{r}+t\cdot\overrightarrow{d}+\tau\cdot\overrightarrow{g}.$$
Для определения той части отрезка, которая закрывается каким-либо телом, достаточно найти значения $$t$$ и $$\tau$$, при которых произведение вектора $$\overrightarrow{w}$$ на обобщенную матрицу положительно. Для каждой плоскости $$\overrightarrow{P}_i$$ записывается неравенство$$q_i=(\overrightarrow{v}\cdot\overrightarrow{P}_i)+t(\overrightarrow{d}\cdot\overrightarrow{P}_i)+\tau(\overrightarrow{g}\cdot\overrightarrow{P}_i)>0.$$ Эти условия должны выполняться для всех плоскостей.
Полагая $$q_i=0$$, получаем систему уравнений, решения которой дают нам точки "смены видимости" отрезка. Результат можно получить путем совместного решения всевозможных пар уравнений из этой системы. Число всевозможных решений при $$N$$ плоскостях равно $$N\cdot(N-1)/2$$.
Так как объем вычислений растет с увеличением числа многоугольников, то желательно по мере возможности сокращать их число, т.е. если мы аппроксимируем некоторую поверхность многогранником, то в качестве граней можно использовать не треугольники, а более сложные многоугольники. При этом, разумеется, встает проблема, как построить такой многоугольник, чтобы он мало отклонялся от плоской фигуры.
В отличие от алгоритма Робертса, Варнок в 1968 г. предложил алгоритм, работающий не в объектном пространстве, а в пространстве образа. Он также нацелен на изображение многогранников, а главная идея его основана на гипотезе о способе обработки информации, содержащейся в сцене, глазом и мозгом человека. Эта гипотеза заключается в том, что тратится очень мало времени и усилий на обработку тех областей, которые содержат мало информации. Большая часть времени и труда затрачивается на области с высоким информационным содержимым. Так, например, рассматривая помещение, в котором имеется только картина на стене, мы быстро осматриваем стены, пол и потолок, а затем все внимание сосредоточиваем на картине. В свою очередь, на этой картине, если это портрет, мы бегло отмечаем фон, а затем более внимательно рассматриваем лицо изображенного персонажа, в особенности глаза, губы. Как правило, достаточно детально рассматриваются еще и руки и с чуть меньшим вниманием - одежда.
В алгоритме Варнока и его вариантах делается попытка воспользоваться тем, что большие области изображения однородны. Такое свойство называют когерентностью, имея в виду, что смежные области (пиксели) вдоль обеих осей х и у имеют тенденцию к однородности.
В пространстве изображения рассматривается окно и решается вопрос о том, пусто ли оно, или его содержимое достаточно просто для визуализации. Если это не так, то окно разбивается на фрагменты до тех пор, пока содержимое фрагмента не станет достаточно простым для визуализации или его размер не достигнет требуемого предела разрешения. В последнем случае информация, содержащаяся в окне, усредняется, и результат изображается с одинаковой интенсивностью или цветом.
Конкретная реализация алгоритма Варнока зависит от метода разбиения окна и от деталей критерия, используемого для того, чтобы решить, является ли содержимое окна достаточно простым. В оригинальной версии алгоритма каждое окно разбивалось на четыре одинаковых подокна. Многоугольник, входящий в изображаемую сцену, по отношению к окну будем называть (рис. 6.3)
(рис 6.3) Варианты расположения многоугольника по отношению к окнуТеперь можно в самом общем виде описать алгоритм.
Для каждого окна:
Шаги 1–4 рассматривают ситуацию пересечения окна только с одним многоугольником. Они используются для сокращения числа подразбиений. Шаг 5 решает задачу удаления невидимых поверхностей. Многоугольник, находящийся ближе всех к точке наблюдения, экранирует все остальные.
Для реализации алгоритма необходимы функции, определяющие взаимное расположение окна и многоугольника, которые достаточно легко реализуются в случае прямоугольных окон и выпуклых многоугольников. Для определения, является ли многоугольник охватывающим, внешним или внутренним, можно воспользоваться, например, погружением многоугольника в прямоугольную оболочку. Для определения наличия пересечений можно использовать опорные прямые (так же, как использовались плоскости в алгоритме Робертса). Если же многоугольник невыпуклый, то задача усложняется. Методы решения такого рода задач будут рассмотрены в главе, относящейся к геометрическому поиску.
Следует заметить, что существуют различные реализации алгоритма Варнока. Были предложены варианты оптимизации, использующие предварительную сортировку многоугольников по глубине, т. е. по расстоянию от точки наблюдения, и другие.
Вейлер и Азертон попытались оптимизировать алгоритм Варнока в отношении числа выполняемых разбиений, перейдя от прямоугольных разбиений к разбиениям вдоль границ многоугольников (1977). Для этого они использовали ими же разработанный алгоритм отсечения многоугольников. Алгоритм работает в объектном пространстве, и результатом его работы являются многоугольники. В самом общем виде он состоит из четырех шагов.
В процессе предварительной сортировки создается список приблизительных приоритетов, причем близость многоугольника к точке наблюдения определяется расстоянием до ближайшей к ней вершины. Затем выполняется отсечение по самому первому из многоугольников. Отсечению подвергаются все многоугольники из списка, причем эта операция выполняется над проекциями многоугольников на картинную плоскость. При этом создаются списки внешних и внутренних фигур. Все попавшие в список внешних не экранируются отсекающим многоугольником. Затем рассматривается список внутренних многоугольников и выполняется сортировка по расстоянию до отсекающего многоугольника. Если все вершины некоторого многоугольника оказываются дальше от наблюдателя, чем самая удаленная из вершин экранирующего, то они невидимы, и тогда они удаляются. После этого работа алгоритма продолжается с внешним списком.
Если какая-то из вершин внутреннего многоугольника оказывается ближе к наблюдателю, чем ближайшая из вершин экранирующего многоугольника, то такой многоугольник является частично видимым. В этом случае предварительный список приоритетов некорректен, и тогда в качестве нового отсекающего многоугольника выбирается именно этот "нарушитель порядка". При этом используется именно исходный многоугольник, а не тот, что получился в результате первого отсечения. Такой подход позволяет минимизировать число разбиений.
Этот алгоритм в дальнейшем был обобщен Кэтмулом (1974) для изображения гладких бикубических поверхностей. Его подход заключался в том, что разбиению подвергалась поверхность. Коротко этот алгоритм можно описать так:
Эффективность такого метода, как и алгоритм Варнока, зависит от эффективности разбиений. В дальнейшем этот алгоритм был распространен на сплайновые поверхности.
Это один из простейших алгоритмов удаления невидимых поверхностей. Впервые он был предложен Кэтмулом в 1975 г. Работает этот алгоритм в пространстве изображения. Идея Z-буфера является простым обобщением идеи о буфере кадра. Буфер кадра используется для запоминания атрибутов каждого пикселя в пространстве изображения, а Z-буфер предназначен для запоминания глубины (расстояния от картинной плоскости) каждого видимого пикселя в пространстве изображения. Поскольку достаточно распространенным является использование координатной плоскости $$XOY$$ в качестве картинной плоскости, то глубина равна координате $$z$$ точки, отсюда и название буфера. В процессе работы значение глубины каждого нового пикселя, который нужно занести в буфер кадра, сравнивается с глубиной того пикселя, который уже занесен в Z-буфер. Если это сравнение показывает, что новый пиксель расположен впереди пикселя, находящегося в буфере кадра, то новый пиксель заносится в этот буфер и, кроме того, производится корректировка Z-буфера новым значением глубины. Если же сравнение дает противоположный результат, то никаких действий не производится. По сути, алгоритм является поиском по $$x$$ и $$у$$ наибольшего значения функции $$z(х,у)$$.
Главное преимущество алгоритма - его простота. Кроме того, этот алгоритм решает задачу об удалении невидимых поверхностей и делает тривиальной визуализацию пересечений сложных поверхностей. Сцены могут быть любой сложности. Поскольку габариты пространства изображения фиксированы, оценка вычислительной трудоемкости алгоритма не более чем линейна. Поскольку элементы сцены или картинки можно заносить в буфер кадра или в Z-буфер в произвольном порядке, их не нужно предварительно сортировать по приоритету глубины. Поэтому экономится вычислительное время, затрачиваемое на сортировку по глубине.
Основной недостаток алгоритма - большой объем требуемой памяти. В последнее время в связи с быстрым ростом возможностей вычислительной техники этот недостаток становится менее лимитирующим. Но в то время, когда алгоритм еще только появился, приходилось изобретать способы создания буфера как можно большего объема при имеющемся ресурсе памяти.
Например, можно разбивать пространство изображения на 4, 16 или больше прямоугольников или полос. В предельном варианте можно использовать буфер размером в одну строку развертки. Для последнего случая был разработан алгоритм построчного сканирования. Поскольку каждый элемент сцены обрабатывается много раз, то сегментирование Z-буфера, вообще говоря, приводит к увеличению времени, необходимого для обработки сцены.
Другой недостаток алгоритма состоит в трудоемкости реализации эффектов, связанных с полупрозрачностью, и ряда других специальных задач, повышающих реалистичность изображения. Поскольку алгоритм заносит пиксели в буфер кадра в произвольном порядке, то довольно сложно получить информацию, которая необходима для методов, основывающихся на предварительном анализе сцены.
В целом алгоритм выглядит так:
4.1. Для каждого пикселя $$(x,y)$$ образа вычислить его глубину $$z(x,y)$$.
4.2. Сравнить глубину $$z(x,y)$$ со значением глубины, хранящимся в Z-буфере в этой же позиции.
4.3. Если $$z(x,y)>Z- \text{буфер}(x,y)$$, то занести атрибуты пикселя в буфер кадра и заменить $$Z-\text{буфер}(x,y) на z(x,y)$$. В противном случае никаких действий не производить.
Алгоритм, использующий Z-буфер, можно также применять для построения сечений поверхностей. Изменится только оператор сравнения:$$z(x,y)>Z-\text{буфер}(x,y)\text{ и }z(x,y)=z\text{ сечения}$$ где $$z\text{ сечения}$$ - глубина искомого сечения.
Здесь мы рассмотрим группу методов, учитывающих специфику изображаемой сцены для удаления невидимых линий и поверхностей.
При изображении сцен со сплошным закрашиванием поверхностей можно воспользоваться методом художника: элементы сцены изображаются в последовательности от наиболее удаленных от наблюдателя к более близким. При экранировании одних участков сцены другими невидимые участки просто закрашиваются. Если вычислительная трудоемкость получения изображения для отдельных элементов достаточно высока, то такой алгоритм будет не самым лучшим по эффективности, но зато мы избежим анализа (и вполне возможно, тоже дорогостоящего), позволяющего установить, какие же из элементов изображать не надо в силу их невидимости. Например, при изображении правильного многогранника мы довольно легко можем упорядочить его грани по глубине, но такая сортировка для произвольного многогранника возможна далеко не всегда. Мы рассмотрим применение этого метода на примере изображения поверхности, заданной в виде однозначной функции двух переменных.
Пусть поверхность задана уравнением$$z=f(x,y), \quad a\le x \le b, \quad c \le y \le d.$$ В качестве картинной плоскости выберем плоскость $$XOY$$. В области задания функции на осях координат построим сетку узлов:$$a=x_0<x_1<\ldots<x_{n-1}=b, \quad c=y_0<y_1<\ldots<y_{m-1}<y_m=d.$$
Тогда $$z_{ij}=f(x_i,y_i)$$ представляют собой набор "высот" для данной поверхности по отношению к плоскости $$XOY$$. Поверхность будем аппроксимировать треугольниками с вершинами в точках $$\overrightarrow{r}_{ij}=(x_i,y_i,z_{ij})$$ так, что каждому прямоугольнику сетки узлов будут соответствовать два треугольника: $$tr_{i_{j}\:j}^1=\{\overrightarrow{r}_{ij},\overrightarrow{r}_{i+1\:j},\overrightarrow{r}_{i+1\:j+1}\}$$ и $$tr_{i_{j}\:j}^2=\{\overrightarrow{r}_{ij},\overrightarrow{r}_{i\:j+1},\overrightarrow{r}_{i+1\:j+1}\}$$. Для построения наглядного изображения поверхности повернем ее на некоторый угол сначала относительно оси $$OX$$, а затем относительно оси $$OY$$, причем направление вращения выберем таким образом, что точки, соответствующие углам координатной сетки, расположатся в следующем порядке по удаленности от картинной плоскости: $$\overrightarrow{r}_{nm},\overrightarrow{r}_{n0},\overrightarrow{r}_{0m},\overrightarrow{r}_{00}$$, т.е. точка $$\overrightarrow{r}_{nm}$$ окажется наиболее близкой к картинной плоскости (и наиболее удаленной от наблюдателя). Предполагается, что способ закрашивания треугольников уже определен. Тогда процесс изображения поверхности можно коротко записать так:$$\begin{aligned} \text{Для } i=n,\ldots,1 \\ \qquad\qquad\text{Для } j=m,\ldots,1 \\ \qquad\qquad\qquad\qquad\text{Нарисовать }tr_{i\:j}^1;\; \text{нарисовать }tr_{i\:j}^2. \end{aligned}$$
При такой последовательности вывода изображения мы продвигаемся от самого удаленного треугольника к все более близким, частично закрашивая уже изображенные участки поверхности.
(рис 6.5) Простое каркасное изображение с поверхности(рис 6.4) Каркасное изображение диагональными ребрамиАлгоритм художника можно применять для полностью закрашенной сцены, а для каркасного изображения, когда объект представляется в виде набора кривых или ломаных линий, он непригоден. Для этого случая предложен еще один метод, весьма эффективный - метод плавающего горизонта. Вернемся к предыдущему примеру изображения поверхности. Каркасное изображение получается путем изображения кривых, получаемых при пересечении этой поверхности плоскостями $$x=x_i$$ и $$y=y_i$$ (рис. 6.4).
На самом деле мы будем рисовать четырехугольник и одну диагональ. В процессе рисования нам понадобятся два целочисленных массива: $$LHor$$ (нижний горизонт) и $$HHor$$ (верхний горизонт) размерностью, соответствующей горизонтальному размеру экрана в пикселях. Они нужны для анализа видимости участков изображаемых отрезков. Сначала мы инициализируем верхний горизонт нулем, а нижний - максимальным значением вертикальной координаты на экране. Каждая выводимая на экран точка может закрывать другие точки, которые "скрываются за горизонтом". По мере рисования нижний горизонт "опускается", а верхний "поднимается", постепенно оставляя все меньше незакрытого пространства. В отличие от метода художника, здесь мы продвигаемся от ближнего угла к дальнему. Теперь опишем алгоритм подробнее.
Функция $$segment$$ в этом фрагменте предназначена для вывода на экран отрезка прямой, причем в момент инициализации очередного пикселя $$(i,j)$$ она выполняет следующие действия:$$\begin{aligned} \text{Если }(HHor[i]<j),\text{ то }HHor[i]=j;\text{ вывести пиксель}; \\ \text{Иначе если }(LHor[i]>j),\text{ то }LHor[i]=j;\text{ вывести пиксель}. \end{aligned}$$ Таким образом, пиксель выводится только в том случае, если он выше верхнего или ниже нижнего горизонта, после чего его координаты уже сами становятся одним из горизонтов. А в целом алгоритм будет выглядеть так:$$\begin{aligned} \text{Для }i=0,\ldots,n-1 \\ \qquad\text{Для }j=0,\ldots,m-1 \\ \qquad\qquad segment(x_i,y_i,x_{i+1},y_j);segment(x_i,y_i,x_{i+1},y_{j+1});\\ \qquad \qquad \qquad segment(x_i,y_i,x_i,y_{j+1}). \end{aligned}$$ На рис. 6.5 приведен пример изображения поверхности с использованием этого алгоритма.
Идея построчного сканирования, предложенная в 1967 г. Уайли, Ромни,
Эвансом и Эрдалом, заключалась в том, что сцена обрабатывается в
порядке прохождения сканирующей прямой. В объектном пространстве это
соответствует проведению секущей плоскости, перпендикулярной
пространству изображения. Строго говоря, алгоритм работает именно в
пространстве изображения, отыскивая точки пересечения сканирующей
прямой с ребрами многоугольников, составляющих картину (для случая
изображения многогранников). Но при пересечении очередного элемента
рисунка выполняется анализ глубины полученной точки и сравнение ее с
глубиной других точек на сканирующей плоскости. В некоторых случаях
можно построить
Один из таких методов мы уже рассматривали - метод Z–буфера, в котором буфер инициализируется заново для каждой сканирующей строки. Другой метод называют интервальным алгоритмом построчного сканирования. В нем сканирующая строка разбивается проекциями точек пересечения ребер многоугольников на интервалы, затем в каждом из интервалов выбираются видимые отрезки. В этой ситуации их уже можно отсортировать по глубине. Мы остановимся чуть подробнее на методе построчного сканирования для криволинейных поверхностей.
В описании метода приоритетов поверхность задавалась в виде функции двух переменных, здесь мы будем задавать поверхность параметрическими уравнениями:$$x=x(u,v),\quad y=y(u,v),\quad z=z(u,v).$$
Пересечение сканирующей плоскости $$y=y_1$$ с поверхностью дает нам так называемую линию уровня, или изолинию. Эта кривая может быть неодносвязной, т. е. состоять из нескольких отдельных кривых. Чтобы получить эту кривую, мы должны решить уравнение$$y(u,v)=y_i$$ и, определив значения параметров $$u,v$$, найти точки кривой. Для получения решения можно воспользоваться численными итерационными методами, но это вносит дополнительные проблемы (например, при плохом выборе начального приближения итерационный процесс может не сойтись). Выбор подходящего метода решения лежит вне задач нашего курса, поэтому перейдем к описанию алгоритма, считая, что он уже выбран и надежно работает.$$\begin{aligned} \text{Для каждой сканирующей строки со значением ординаты } y_i: \\ \quad\text{Для каждого значения абсциссы } x_j: \\ \qquad\text{Для всех решений уравнений } u=u(x_j,y_j),\;v=v(x_j,y_j) \text{ вычислить глубину } z=z(u,v). \\ \qquad\text{Определить точку с наименьшим значением глубины}\\ \qquad\text{и изобразить.} \end{aligned}$$
Второй шаг этого алгоритма предполагает, что решение отыскивается
только для тех элементов поверхности (или группы поверхностей, если
речь идет о более сложной сцене, содержащей
Теперь разберем один способ использования метода художника при
изображении пространственных сцен, содержащих несколько объектов или
В каждом узле дерева левое поддерево будет содержать грани, отделенные плоскостью, а правое - не отделенные. Рисование сцены осуществляется с помощью рекурсивного алгоритма следующего вида:$$\begin{aligned} \text{Рисуем дерево }(T): \\ \text{Если наблюдатель находится в положительной полуплоскости, то:} \\ \qquad\text{Если правое поддерево }TR \text{ не пусто, рисуем дерево }(TR). \\ \qquad\text{Рисуем корневую грань.} \\ \qquad\text{Если левое поддерево }TL \text{ не пусто, рисуем дерево }(TL). \\ \text{Иначе} \\ \qquad\text{Если левое поддерево }TL \text{ не пусто, рисуем дерево }(TL). \\ \qquad\text{Рисуем корневую грань.} \\ \qquad\text{Если правое поддерево }TR\text{ не пусто, рисуем дерево }(TR). \end{aligned}$$
(рис 6.6) Разбиение пространства и соответствующее ему деревоПостроение плоскостей и дерева в данном случае осуществляется "вручную". Для эффективности работы алгоритма надо стремиться к тому, чтобы дерево было сбалансированным. Если какие-то грани не удается отделить, то их пересекают плоскостями и рисуют как два объекта. Способ определения, по какую сторону плоскости находится наблюдатель, а по какую - грань, очень прост. Параметр плоскости $$d$$ для каждой грани будем задавать так, чтобы грань находилась в положительной полуплоскости. Тогда если при подстановке координат наблюдателя в это уравнение получаем положительное значение, то он находится в одной полуплоскости с гранью, если нет, то в разных.
Алгоритм может применяться не только к многогранникам, но и вообще к любой сцене при условии, что имеется алгоритм изображения составляющих ее объектов. На рис. 6.6 изображена проекция сцены, разбитой вертикальными плоскостями, и соответствующее ей дерево. Положение наблюдателя отмечено кружком с буквой Н. При этой точке зрения объекты будут изображаться в последовательности 5, 6, 1, 2, 3, 4.
Главная идея этого алгоритма была предложена в 1968 г. А.Аппелем, а первая реализация была выполнена в 1971 г.
Наблюдатель видит любой объект посредством испускаемого неким
источником света, который падает на этот объект, отражается или
преломляется согласно законам оптики и затем каким-то путем доходит до
глаза наблюдателя. Из огромного множества лучей света, выпущенных
источником, лишь небольшая часть дойдет до наблюдателя. Следовательно,
отслеживать пути лучей в таком порядке неэффективно с точки зрения
вычислений. Аппель предложил отслеживать (трассировать) лучи в
обратном направлении, т.е. от наблюдателя к объекту. В первой
реализации этого метода трассировка прекращалась, как только луч
пересекал поверхность видимого непрозрачного объекта; т.е. луч
использовался только для обработки скрытых или видимых поверхностей.
Впоследствии были реализованы алгоритмы трассировки лучей с
использованием более
(рис 6.8) Трассировка параллельными лучами(рис 6.7) Трассировка с центральной точкойВ этом алгоритме предполагается, что сцена уже преобразована в пространство изображения. Если используется ортографическая проекция, то точка зрения или наблюдатель находится в бесконечности на положительной полуоси $$OZ$$. В этом случае все световые лучи, идущие от наблюдателя, параллельны оси (рис. 6.7). Каждый луч проходит через пиксель растра до сцены. Траектория каждого луча отслеживается, чтобы определить, какие именно объекты сцены, если таковые существуют, пересекаются с данным лучом. Необходимо проверить пересечение каждого объекта сцены с каждым лучом. Если луч пересекает объект, то определяются все возможные точки пересечения луча и объекта. Можно получить большое количество пересечений, если рассматривать много объектов. Эти пересечения упорядочиваются по глубине. Пересечение с максимальным значением $$z$$ представляет видимую поверхность для данного пикселя. Атрибуты этого объекта используются для определения характеристик пикселя.
Если точка зрения находится не в бесконечности (перспективная проекция), алгоритм трассировки лучей лишь незначительно усложняется. Здесь предполагается, что наблюдатель по-прежнему находится на положительной полуоси $$OZ$$. Картинная плоскость, т.е. растр, перпендикулярна оси $$OZ$$, как показано на рис. 6.8.
Наиболее важным и трудоемким элементом этого алгоритма является процедура определения пересечений, поскольку эта задача отнимает наибольшую часть времени всей работы алгоритма. Поэтому эффективность методов поиска особенно важна. Объекты сцены могут состоять из набора плоских многоугольников, многогранников или тел, ограниченных замкнутыми параметрическими поверхностями. Для ускорения поиска важно иметь эффективные критерии, позволяющие исключить из процесса заведомо лишние объекты.
Одним из способов сокращения числа пересекаемых объектов является
погружение объектов в
Особенно просто выполняется тест на пересечение со сферической оболочкой (в лекции 3 были рассмотрены задачи о пересечении луча со сферой и плоскостью). Несколько большего объема вычислений требует задача о пересечении с прямоугольным параллелепипедом, поскольку необходимо проверить пересечение луча по меньшей мере с тремя бесконечными плоскостями, ограничивающими прямоугольную оболочку. Поскольку точки пересечения могут оказаться вне граней этого параллелепипеда, для каждой из них следует, кроме того, произвести проверку на попадание внутрь. Следовательно, для трех измерений тест с прямоугольной оболочкой оказывается более медленным, чем тест со сферической оболочкой.
После выполнения этих первичных тестов начинается процесс поиска пересечений с объектами, попавшими в список потенциально видимых. При этом задача формирования изображения не исчерпывается нахождением самой точки пересечения: если мы учитываем эффекты отражения и преломления, необходимо отслеживать дальнейший путь луча, для чего, как правило, требуется восстановить нормаль к поверхности, а также определить направление отраженного или преломленного луча. В связи со всеми этими задачами важно выбрать достаточно удобные аппроксимации поверхностей, составляющих сцену. Определение атрибутов пикселя, выводимого в конечном итоге на экран, зависит от выбора модели освещения, о чем более подробно будет рассказано в последующих лекциях.
Алгоритм трассировки лучей для простых непрозрачных поверхностей можно представить следующим образом.
Создать список объектов, содержащий:
Для каждого трассируемого луча:
Выполнить для каждого объекта трехмерный тест на пересечение с оболочкой. Если луч пересекает эту оболочку, то занести объект в список активных объектов.
Если список активных объектов пуст, то изобразить данный пиксель с фоновым значением цвета и продолжать работу. В противном случае для каждого объекта из списка активных объектов:
В настоящее время алгоритм трассировки, несмотря на вычислительную сложность, стал очень популярен, особенно в тех случаях, когда время формирования изображения не очень существенно, но хочется добиться как можно большей реалистичности изображения.
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.