Графика и обработка изображений

Удаление невидимых плоскостей

Введение

Отсечение нелицевых граней

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

Метод W-буфера

Алгоритм плавающего горизонта

Алгоритмы упорядочения

Метод сортировки по глубине

Метод двоичного разбиения пространства

Метод построчного сканирования

Алгоритм Варнака

Введение

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

К решению задачи удаления невидимых линий и поверхностей можно выделить два основных подхода.

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

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

Отсечение нелицевых граней

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

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

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

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

Одним из самых простых алгоритмов удаления невидимых граней и поверхностей является метод z-буфера (буфера глубины). В силу крайней простоты этого метода часто встречаются его аппаратные реализации.

Сопоставим каждому пикселю (х, у) картинной плоскости, кроме цвета, хранящегося в видеопамяти, его расстояние до картинной плоскости вдоль направления проектирования z(x, у) (его глубину).

Изначально массив глубин инициализируется на "бесконечность".

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

Данный метод работает исключительно в пространстве картинной плоскости и не требует никакой предварительной обработки.

Метод W-буфера

Данный метод является простым усовершенствованием Z-буфера. Различие состоит в том, что в буфере вместо значения глубины мы храним величину, обратную величине глубины. Благодаря этому количество расчетов сокращается.

Алгоритмы упорядочения

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

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

Основные алгоритмы упорядочения рассматриваются ниже.

Метод сортировки по глубине

Наиболее простым подходом к упорядочиванию граней является их сортировка по минимальному расстоянию до картинной плоскости (вдоль направления проектирования) с последующим выводом их в порядке приближения.

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

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

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

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

1. Пересекаются ли проекции этих граней на ось Ох?

2. Пересекаются ли их проекции на ось Оу?

3. Находится ли грань Р по другую сторону от плоскости, проходящей через грань Q, чем начало координат (наблюдатель)?

4. Находится ли грань Q по ту же сторону от плоскости, проходящей через грань Р, что и начало координат (наблюдатель)?

5. Пересекаются ли проекции этих граней на картинной плоскости?

Если хотя бы на один из этих вопросов получен отрицательный ответ, то считаем что эти две грани - Р и Q упорядочены верно, и сравниваем Р со следующей гранью. В противном случае считаем, что эти грани необходимо поменять местами, для чего проверяются следующие тесты:

3'. Находится ли грань Q по другую сторону от плоскости, проходящей через грань Р, чем начало координат?

4'. Находится ли грань Р по ту же сторону от плоскости, проходящей через грань Q, что и начало координат?

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

Метод двоичного разбиения пространства

Существует другой, крайне элегантный способ упорядочивания граней.

Рассмотрим некоторую плоскость в объектном пространстве. Она разбивает множество всех граней на два непересекающихся множества (кластера), в зависимости от того, в каком полупространстве относительно плоскости эти грани лежат (будем считать, что плоскость не пересекает ни одну из этих граней).

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

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

Обычно в качестве разбивающей плоскости рассматривается плоскость, проходящая через одну из граней (на самом деле при этом множество всех граней разбивается на 4 класса - лежащих на плоскости, пересекающих ее, лежащих в положительном полупространстве и лежащие в отрицательном полупространстве относительно этой плоскости). Грани, пересекаемые плоскостью, разобьем вдоль этой плоскости.

В результате мы приходим к дереву разбиения пространства (Binary Space Partitioning), узлами которого являются грани. Каждый узел такого дерева можно представить в виде следующей структуры:

При этом Left указывает на вершину поддерева, содержащуюся в положительном полупространстве, a Right - на поддерево содержащееся в отрицательном полупространстве.

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

- получить как можно более сбалансированное дерево;

- минимизировать количество разбиений.

К сожалению, эти критерии, как правило, являются взаимоисключающими, поэтому выбирается некоторый компромиссный вариант.

После того как это дерево построено, осуществляется построение изображения в зависимости от используемого проектирования.

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

Метод построчного сканирования

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

Подобные алгоритмы с успехом используются для создания компьютерных игр типа Wolfenstein 3d и DOOM.

Рассмотрим, каким путем возможно применение этого метода для создания игры типа Wolfenstein 3d.

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

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

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

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

Алгоритм Варнака

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

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

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

Простая реализация алгоритма Варнока.

Многоугольник ( ,1) - указатель на первую вершину многоугольника в массиве Вершина

Многоугольник ( ,2) - число вершин многоугольника

Многоугольник ( ,3) - интенсивность света или цвет многоугольника

Многоугольник ( ,4-7) - коэффициенты a, b, c, d уравнения плоскости, несущей многоугольник

Многоугольник ( ,8-11) - габариты Xmin, Xmax, Ymin, Ymax прямоугольной объемлющей оболочки многоугольника

Push - функция, заносящая окна в стек

Pop - функция, извлекающая окна из стека

Wmax - максимальные габариты окна по х и у. Предполагается, что начало координат экрана находится в точке (0, 0)

Окно - массив размером 1x3, который содержит начало координат окна и его размер в форме (Хнач, Унач, Размер)

Внешность - флаг = 0 для пустого окна, >=1 для непустого окна

инициализировать черный фоновый цвет или интенсивность 
Фон = О 
Поместить окно размером с экран в стек 
PUSH ОКНО(0, 0, Wmax) 
while (стек не пуст) 
    взять окно из стека 
    Pop Окно(Хнач, Удач, Размер) 
    инициализировать счетчик многоугольников 
    Внешность = 0 
    Выполнить для каждого многоугольника габаритный тест с 
    прямоугольной оболочкой, чтобы найти внешние многоугольники 
    while (i <= N and внешность = О) 
        call Габарит(i, Многоугольник, Окно, Внешность) 
        i = i + 1 
    end while 
    если хотя бы один многоугольник не является внешним, то 
    разбить окно или изобразить пиксел 
    if Внешность > О then: 
        если размер окна больше пиксела, то разбить окно 
        if Размер > 1 then 
            Размер = Размер/2 
            Push Окно(Хнач + Размер, Унач + Размер, Размер) 
            Push Окно(Хнач, Унач + Размер, Размер) 
            Push Окно(Хнач + Размер, Унач, Размер) 
            Push Окно(Хнач, Унач, Размер) 
        else 
            если окно размером с пиксел, то вычислить его атрибуты 
            call Покрытие(Вершина, N, Многоугольник, Окно; Номер) 
            if Номер > 0 then 
                call Визуализация(Окно, Многоугольник (Номер, 3)) 
            else 
                Изобразить пустое окно 
                call Визуализация(Окно, Фон) 
            end if 
        end if 
    else 
        call Визуализация(Окно, Фон) 
    end if 
end while 
finish

подпрограмма реализации простого габаритного теста с 
прямоугольной оболочкой 
subroutine Габарит(i, Многоугольник, Окно; Внешность) 
вычисление габаритов окна: Хлев, Управ, Хниз, Yвepx 
Хлев  = Окно(1, 1) 
Хправ = Окно(1, 1) + Окно*) - 1 
Yниз  = Окно(1, 2) 
Yвepx = Окно(1, 2) + Окно(1, 3) - 1 
реализация тестов с прямоугольной оболочкой 
Внешность = 1 
if Многоугольник(i, 8)  > Хправ then Внешность = 0
if Многоугольник(i, 9)  < Хлев  then Внешность = 0 
if Многоугольник(i, 10) > Yверх then Внешность = 0 
if Многоугольник(i, 11) < Yниз  then Внешность = 0 
return 

подпрограмма визуализации окна 
subroutine Визуализация(окно, Интенсивность) 
Setpixe(x, у, 1) - функция визуализации пиксела, 
координаты которого (х, у), с интенсивностью I 
    for j = Окно(1, 2) to Окно(1, 2) + Окно(1, 3) - 1 
        for i = Окно(1, 1) to Окно(1, 1) + Окно(1, 3) - 1 
            Setpixe(i, j, Интенсивность) 
        next i 
    next j 
return 

подпрограмма, проверяющая, покрывает ли многоугольник центр окна 
subroutine Покрытие(Вершина, N, Многоугольник, Окно; Номер) 
считается, что многоугольник покрывает окно размером с пиксел, 
    если центр этого окна находится внутри многоугольника 
поскольку вершины многоугольника перечисляются по часовой 
    стрелке, его внутренность лежит справа от контура 
если покрывающие многоугольники не обнаружатся, то 
Номер = О 
если же найден хотя бы один покрывающий многоугольник,
то Номер будет равен номеру того из них, который видим 
    присвоить Zmax начальное значение, равное нулю. Тут предполагается, 
    что все многоугольники расположены в положительном 
    полупространстве Z >= 0 
    Zmax = 0 
    вначале предположим, что покрывающих многоугольников 
    нет 
    Номер = 0 
    установить центр окна 
    ТочкаX = Окно(1, 1) + Окно(1, 3)/2 
    ТочкаY = Окно(1, 2) + Окно(1, 3)/2 
    для каждого многоугольника 
    for i = 1 to N 
        Индекс = Многоугольник(i, 1) 
        Для каждого ребра многоугольника 
        for j = 1 to Многоугольник(i, 2) - 1 
            T1x = Вершина(Индекс, 1) 
            T1у = Вершина(Индекс, 2) 
            T2x = Вершина(Индекс + 1, 1) 
            T2y = Вершина(Индекс + 1, 2) 
            заметим, что Точка, Tl, Т2 - это сокращения для 
            идентификаторов ТочкаX, ТочкаY и т. п. 
            call Видимость(Точка, Tl, Т2; Твидимость)
            if Твидимость < 0 then 1 
            Индекс = Индекс + 1 
        next j 
        проверка относительно последнего ребра многоугольника 
        Т1х = Вершина(Индекс, 1) 
        T1у = Вершина(Индекс, 2) 
        Т2х = Вершина(Многоугольник (i, 1), 1) 
        Т2у = Вершина(Многоугольник (i, 1), 2) 
        call Видимость(Точка, Tl, Т2, Твидимость) 
        if Твидимость >= 0 then 
            call Вычислить(Вершина, i, Многоугольник, Окно; z) 
            if z > Zmax then 
                Zmax = z 
                Номер = i 
            end if 
        end if 
  1 next i 
return 

подпрограмма вычисления видимости точки
subroutine Видимость(Точка, P1, P2; Твидимость)
видимость Точка следует определить относително стороны P1-P2
Твидимость <0, если Точка невидима
           =0, если Точка лежит на  P1-P2
           >0, если Точка видима
в этой подпрограмме используется вычисление векторного произведения
Sign - функция, принимающая значения -1,0,1 в зависимости
       от того, будет ли знак ее аргумента отрицателен, 
       равен нулю или положителен
    Раб1 = (ТочкаX - P1X) * (P2Y-P1Y)
    Раб2 = (ТочкаY - P1Y)*(P2X-P1X)
    Раб3 = Раб1 - Раб2
    Твидимость = Sign(Раб3)
    return
    
подпрограмма вычисления интенсивности пиксела 
subroutine Вычислить(Вершина, i, Многоугольник, Окно; z) 
уравнение плоскости многоугольника используется для вычисления 
многоугольника, который находится ближе других к точке 
наблюдения для этого пиксела 
Мах - обозначение функции, вычисляющей максимум 
    вычисление координат х и у центра пиксела 
    Хцентр = Окно(1, 1) + Окно(1, 3)/2 
    Yцентр = Окно(1, 2) + Окно(1, 3)/2 
    определение координаты z многоугольника в центре пиксела 
    поиск ребра многоугольника, проходящего через центр пиксела 
    заметим, что многоугольник такого типа может совершенно 
    отсутствовать или появиться в качестве набора несвязанных 
    точек - например, в результате ступенчатости 
    if Многоугольник(i, 6) = 0 then 
        for j = 2 to Многоугольник(i, 2) 
            z=Max(Вершина(j, 3), Вершина(j -1, 3)) 
        next j 
    else 
        вычисление z по уравнению плоскости многоугольника 
        А = Многоугольник(i, 4) 
        В = Многоугольник(i, 5) 
        С = Многоугольник(i, 6) 
        D = Многоугольник(i, 7) 
        z = - (А * Хцентр + В * Yцентр + D)/С 
    end if 
    return 
    

Вверх по странице, к оглавлению и навигации