Удаление невидимых линий компьютерная графика

Обновлено: 25.11.2022

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

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

Схема пространственной фильтрации иллюстрируется на рисунке ниже (см. рисунок 1).

image


Рисунок 1. Схема пространственной фильтрации

Процесс основан на простом перемещении маски фильтра от точки к точке изображения; в каждой точке (x,y) отклик фильтра вычисляется с использованием предварительно заданных связей. В случае линейной пространственной фильтрации отклик задается суммой произведения коэффициентов фильтра на соответствующие значения пикселей в области, покрытой маской фильтра. Для маски 3х3 элемента, показанной на рисунке 1, результат (отклик) R линейной фильтрации в точке (x,y) изображения составит:

image

(1.1)

что, как видно, есть сумма произведений коэффициентов маски на значения пикселей непосредственно под маской. В частности заметим, что коэффициент w(0,0) стоит при значении f(x,y), указывая тем самым, что маска центрирована в точке (x,y).

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

Первая производная одномерной функции f(x) определяется как разность значений соседних элементов:

image

(1.2)

Здесь использована запись в виде частной производной для того, чтобы сохранить те же обозначения в случае двух переменных f(x,y), где придется иметь дело с частными производными по двум пространственным осям. Использование частной производной не меняет существа рассмотрения.

Аналогично, вторая производная определяется как разность соседних значений первой производной:

image

(1.3)

Вычисление первой производной цифрового изображения основано на различных дискретных приближениях двумерного градиента. По определению, градиент изображения f(x,y) в точке (x,y) — это вектор [2]:

image

(1.4)

Как известно из курса математического анализа, направление вектора градиента совпадает с направлением максимальной скорости изменения функции f в точке (x,y) [2].
Важную роль при обнаружении контуров играет модуль этого вектора, который обозначается ∇f и равен

image

(1.5)

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

Направление вектора градиента также является важной характеристикой. Обозначим α(x,y) угол между направлением вектора ∇f в точке (x,y) и осью x. Как известно из математического анализа [2],

image

(1.6)

Отсюда легко найти направление контура в точке (x,y), которое перпендикулярно направлению вектора градиента в этой точке. А вычислить градиент изображения можно, вычислив величины частных производных ∂f/∂x и ∂f/∂y для каждой точки.

Оператор Робертса

Пусть область 3х3, показанная на рисунке ниже (см. рис. 2), представляет собой значения яркости в окрестности некоторого элемента изображения.

image


Рисунок 2. Окрестность 3х3 внутри изображения

image

Один из простейших способов нахождения первых частных производных в точке состоит в применении следующего перекрестного градиентного оператора Робертса [1]:

(1.7)
и
(1.8)

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

image


Рисунок 3. Маски оператора Робертса

Реализация масок размерами 2х2 не очень удобна, т.к. у них нет четко выраженного центрального элемента, что существенно отражается на результате выполнения фильтрации. Но этот «минус» порождает очень полезное свойство данного алгоритма – высокую скорость обработки изображения.

Оператор Превитта

Оператор Превитта, так же как и оператор Робертса, оперирует с областью изображения 3х3, представленной на рисунке 2, только использование такой маски задается другими выражениями:

(1.9)
и
(1.10)

В этих формулах разность между суммами по верхней и нижней строкам окрестности 3х3 является приближенным значением производной по оси x, а разность между суммами по первому и последнему столбцам этой окрестности – производной по оси y. Для реализации этих формул используется оператор, описываемый масками на рисунке 4, который называется оператором Превитта.

image


Рисунок 4. Маски оператора Превитта

Оператор Собеля

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

(1.11)
и
(1.12)

Это увеличенное значение используется для уменьшения эффекта сглаживания за счет придания большего веса средним точкам.

Маски, используемые оператором Собеля, отображены на рисунке ниже (см. рис. 5).

image


Рисунок 5. Маски оператора Собеля

image

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

(1.14)
или
(1.15)

Ну и в завершении продемонстрирую результаты обработки изображений (см. рисунки 6-8) описанными методами.

image


Рисунок 6. Исходное изображение №1

image


Рисунок 7. Исходное изображение №2

image


Рисунок 8. Исходное изображение №3

Результаты обработки методами Робертса, Превитта и Собеля продемонстрированы ниже:



Рисунок 9. Исходные изображения после обработки методом Робертса




Рисунок 10. Исходные изображения после обработки методом Превитта




Рисунок 11. Исходные изображения после обработки методом Собеля

Аннотация: Исторический экскурс. Методы переборного типа. Метод Z-буфера. Методы удаления нелицевых граней многогранника. Алгоритмы Варнака и Вейлера — Азертона. Методы приоритетов (художника, плавающего горизонта). Метод двоичного разбиения пространства. Алгоритмы построчного сканирования для криволинейных поверхностей. Алгоритм определения видимых поверхностей путем трассировки лучей

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

Необходимость удаления невидимых линий, ребер, поверхностей или объемов проиллюстрирована на рис. 6.1. Рисунок наглядно демонстрирует, что изображение без удаления невидимых линий воспринимается неоднозначно.

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

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

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

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

Удаление нелицевых граней многогранника

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

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

ax+by+cz+d=0

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

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

\overrightarrow<P></p>
= \begin a \\ b \\ c \\ d \end, \overrightarrow= \begin x \\ y \\ z \\ 1 \end.

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

M= \begin</p>
<p>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.

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

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

Из обобщенной матрицы можно получить информацию о том, какие грани многогранника пересекаются в вершинах. Действительно, если вершина =(x,y,z,1)" />
принадлежит граням _1, \; \overrightarrow_2, \; \overrightarrow_3" />
, то она удовлетворяет уравнениям

\left. \begin</p>
(\overrightarrow\cdot\overrightarrow_1)=0 \\ (\overrightarrow\cdot\overrightarrow_2)=0 \\ (\overrightarrow\cdot\overrightarrow_3)=0 \\ (\overrightarrow\cdot\overrightarrow_4)=1 \end \right\> , \quad \text \quad \overrightarrow_4= \begin 0 \\ 0 \\ 0 \\ 1 \end

\overrightarrow<v></p>
<p>\cdot Q = \overrightarrow_4,

где - матрица, составленная из вектор-столбцов _1, \overrightarrow_2, \overrightarrow_3, \overrightarrow_4" />
. Значит, координаты вершины определяются соотношением

\overrightarrow<v></p>
<p>=\overrightarrow_4\cdot Q^,

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

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

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

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

\overrightarrow<v></p>
<p>=\overrightarrow+t\cdot(\overrightarrow-\overrightarrow)\equiv\overrightarrow+t\cdot\overrightarrow, \quad 0 \le t \le 1,

t

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

\overrightarrow<w></p>
<p>=\overrightarrow+\tau\cdot\overrightarrow=\overrightarrow+t\cdot\overrightarrow+\tau\cdot\overrightarrow.

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

q_i=(\overrightarrow<v></p>
\cdot\overrightarrow_i)+t(\overrightarrow\cdot\overrightarrow_i)+\tau(\overrightarrow\cdot\overrightarrow_i)>0.

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

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

Аннотация: Исторический экскурс. Методы переборного типа. Метод Z-буфера. Методы удаления нелицевых граней многогранника. Алгоритмы Варнака и Вейлера — Азертона. Методы приоритетов (художника, плавающего горизонта). Метод двоичного разбиения пространства. Алгоритмы построчного сканирования для криволинейных поверхностей. Алгоритм определения видимых поверхностей путем трассировки лучей

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

Необходимость удаления невидимых линий, ребер, поверхностей или объемов проиллюстрирована на рис. 6.1. Рисунок наглядно демонстрирует, что изображение без удаления невидимых линий воспринимается неоднозначно.

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

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

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

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

Удаление нелицевых граней многогранника

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

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

ax+by+cz+d=0

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

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

\overrightarrow<P></p>
= \begin a \\ b \\ c \\ d \end, \overrightarrow= \begin x \\ y \\ z \\ 1 \end.

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

M= \begin</p>
<p>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.

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

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

Из обобщенной матрицы можно получить информацию о том, какие грани многогранника пересекаются в вершинах. Действительно, если вершина =(x,y,z,1)" />
принадлежит граням _1, \; \overrightarrow_2, \; \overrightarrow_3" />
, то она удовлетворяет уравнениям

\left. \begin</p>
(\overrightarrow\cdot\overrightarrow_1)=0 \\ (\overrightarrow\cdot\overrightarrow_2)=0 \\ (\overrightarrow\cdot\overrightarrow_3)=0 \\ (\overrightarrow\cdot\overrightarrow_4)=1 \end \right\> , \quad \text \quad \overrightarrow_4= \begin 0 \\ 0 \\ 0 \\ 1 \end

\overrightarrow<v></p>
<p>\cdot Q = \overrightarrow_4,

где - матрица, составленная из вектор-столбцов _1, \overrightarrow_2, \overrightarrow_3, \overrightarrow_4" />
. Значит, координаты вершины определяются соотношением

\overrightarrow<v></p>
<p>=\overrightarrow_4\cdot Q^,

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

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

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

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

\overrightarrow<v></p>
<p>=\overrightarrow+t\cdot(\overrightarrow-\overrightarrow)\equiv\overrightarrow+t\cdot\overrightarrow, \quad 0 \le t \le 1,

t

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

\overrightarrow<w></p>
<p>=\overrightarrow+\tau\cdot\overrightarrow=\overrightarrow+t\cdot\overrightarrow+\tau\cdot\overrightarrow.

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

q_i=(\overrightarrow<v></p>
\cdot\overrightarrow_i)+t(\overrightarrow\cdot\overrightarrow_i)+\tau(\overrightarrow\cdot\overrightarrow_i)>0.

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

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

Аннотация: Исторический экскурс. Методы переборного типа. Метод Z-буфера. Методы удаления нелицевых граней многогранника. Алгоритмы Варнака и Вейлера — Азертона. Методы приоритетов (художника, плавающего горизонта). Метод двоичного разбиения пространства. Алгоритмы построчного сканирования для криволинейных поверхностей. Алгоритм определения видимых поверхностей путем трассировки лучей

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

Необходимость удаления невидимых линий, ребер, поверхностей или объемов проиллюстрирована на рис. 6.1. Рисунок наглядно демонстрирует, что изображение без удаления невидимых линий воспринимается неоднозначно.

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

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

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

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

Удаление нелицевых граней многогранника

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

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

ax+by+cz+d=0

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

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

\overrightarrow<P></p>
= \begin a \\ b \\ c \\ d \end, \overrightarrow= \begin x \\ y \\ z \\ 1 \end.

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

M= \begin</p>
<p>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.

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

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

Из обобщенной матрицы можно получить информацию о том, какие грани многогранника пересекаются в вершинах. Действительно, если вершина =(x,y,z,1)" />
принадлежит граням _1, \; \overrightarrow_2, \; \overrightarrow_3" />
, то она удовлетворяет уравнениям

\left. \begin</p>
(\overrightarrow\cdot\overrightarrow_1)=0 \\ (\overrightarrow\cdot\overrightarrow_2)=0 \\ (\overrightarrow\cdot\overrightarrow_3)=0 \\ (\overrightarrow\cdot\overrightarrow_4)=1 \end \right\> , \quad \text \quad \overrightarrow_4= \begin 0 \\ 0 \\ 0 \\ 1 \end

\overrightarrow<v></p>
<p>\cdot Q = \overrightarrow_4,

где - матрица, составленная из вектор-столбцов _1, \overrightarrow_2, \overrightarrow_3, \overrightarrow_4" />
. Значит, координаты вершины определяются соотношением

\overrightarrow<v></p>
<p>=\overrightarrow_4\cdot Q^,

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

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

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

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

\overrightarrow<v></p>
<p>=\overrightarrow+t\cdot(\overrightarrow-\overrightarrow)\equiv\overrightarrow+t\cdot\overrightarrow, \quad 0 \le t \le 1,

t

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

\overrightarrow<w></p>
<p>=\overrightarrow+\tau\cdot\overrightarrow=\overrightarrow+t\cdot\overrightarrow+\tau\cdot\overrightarrow.

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

q_i=(\overrightarrow<v></p>
\cdot\overrightarrow_i)+t(\overrightarrow\cdot\overrightarrow_i)+\tau(\overrightarrow\cdot\overrightarrow_i)>0.

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

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

В статьях 7 и 8 мы поговорим о программировании непосредственно под OpenGL. Есть ненулевая вероятность получить краткий курс OpenCL/CUDA в статьях 9+.

Знакомьтесь, это мой друг z-buffer головы абстрактного африканца. Он нам поможет убрать визуальные артефакты отбрасывания задних граней, которые у нас оставались в прошлой статье.


Кстати, не могу не упомянуть, что эта модель, которую я использую в хвост и в гриву, была любезно предоставлена замечательным Vidar Rapp.

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

В теории можно не отбрасывать невидимые грани, а просто рисовать всё подряд, начав с самых задних, и заканчивая передними.

Это называется алгоритмом художника. К сожалению, он весьма затратен, на каждое изменение положения камеры нужно пересортировывать сцену. А бывают ещё и динамические сцены… Но даже не это основная проблема. Проблема в том, что не всегда это можно сделать.

Давайте представим себе простейшую сцену из трёх треугольников, камера смотрит сверху вниз, мы проецируем наши треугольники на белый экран:


Вот так должен выглядеть рендер этой сцены:


Синяя грань — она за красной или перед? Ни то, ни то. Алгоритм художника здесь ломается. Ну, то есть, можно синюю грань разбить на две, одна часть перед красной, другая за. А та, что перед красной, ещё на две — перед зелёной и за зелёной… Думаю, достаточно ясно, что в сценах с миллионами треугольников это быстро становится непростой задачей. Да, у неё есть решения, например, пользоваться двоичными разбиениями пространства, заодно это помогает и для сортировки при смене положения камеры, но давайте не будем себе усложнять жизнь!

Давайте потеряем одно из измерений, рассмотрим двумерную сцену, полученную пересечением нашей сцены и жёлтой плоскости разреза:

То есть, наша сцена состоит из трёх отрезков (пересечение жёлтой плоскости и каждого из треугольников), а её рендер — это картинка
той же ширины, что и нормальный рендер, но в один пиксель высотой:

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


Вот так выглядит наша двумерная сцена, наша задача посмотреть на эти отрезки сверху.

Давайте теперь её рендерить. Напоминаю, рендер — это картинка шириной во всю сцену и высотой в один пиксель. В моём коде я её объявил высотой в 16, но это чтобы не ломать глаза, рассматривая один пиксель на экранах высокого разрешения. Функция rasterize пишет только в первую строчку картинки render.

Итак, я объявил загадочный массив ybuffer ровно в размер нашего экрана (width, 1). Этот массив инициализирован минус бесконечностью. Затем я передаю в функцию rasterize и картинку render, и этот загадочный массив. Как выглядит сама функция?

Очень-очень просто: я прохожу по всем x-координатам между p0.x и p1.x и вычисляю соответствующую y-координату нашей линии.
Затем я проверяю, что у нас в массиве ybuffer по этой координате x. Если текущий пиксель ближе к камере, нежели то, что там сохранено,
то я и его рисую в картинке, и ставлю новую y-координату в игрек-буфере.

Давайте разбираться поэтапно: после вызова растеризатора для первой (красной) линии вот что мы имеем в памяти:


содержимое экрана:


содержимое y-буфера:

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

Дальше мы рисуем зелёную линию, вот память после вызова её растеризатора:



Ну и напоследок синюю:



Поздравляю вас, мы нарисовали нашу двумерную сцену! Ещё раз полюбуемся на финальный рендер:


Снимок кода на гитхабе.
Внимание: в этой статье я использую ту же самую версию растеризатора треугольника, что и в предыдущей. Улучшенная версия растеризатора (проход всех пикселей описывающего прямоугольника) будет вскорости любезно предоставлена и описана в отдельной статье уважаемым gbg! Stay tuned.

Поскольку у нас экран теперь двумерный, то z-буфер тоже должен быть двумерным:

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


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


Это просто ужасно, насколько код похож на растеризатор из прошлой статьи. Что изменилось? (Используйте vimdiff и посмотрите).
Vec2 был заменён на Vec3 в вызове функции и сделана проверка if (zbuffer[idx] Всё! Вот наш настоящий рендер без огрехов отсечения невидимых поверхностей:


Обратите внимание, что backface culling в моём коде оставлен:

Он не является необходимым для получения этой картинки, это только ускорение вычислений.

Текстуры! Это будет домашняя работа.

В .obj файле есть строчки vt u v, они задают массив текстурных координат.
Среднее число между слешами в f x/x/x x/x/x x/x/x — это текстурные координаты данной вершины в данном треугольнике. Интерполируете их внутри треугольника, умножаете на ширину-высоту текстурного файла и получаете цвет пикселя из файла текстуры.
Диффузную текстуру брать здесь.


Вот пример того, что должно получиться:

Читайте также: