Удаление невидимых плоскостей.
Введение.
Для построения правильного изображения трехмерных объектов необходимо уметь определять, какие части объектов (ребра, грани) будут видны при заданном проектировании, а какие будут закрыты другими гранями объектов. В качестве возможных видов проектирования традиционно рассматриваются параллельное и центральное (перспективное) проектирования.
Проектирование осуществляется на так называемую картинную плоскость (экран): проектирующий луч к картинной плоскости проводится через каждую точку объектов. При этом видимыми будут те точки, которые вдоль направления проектирования ближе всего расположены к картинной плоскости.
Несмотря на кажущуюся простоту, эта задача является достаточно сложной и требует зачастую больших объемов вычислений. Поэтому существует ряд различных методов решения задач удаления невидимых граней, включая и методы, опирающиеся на аппаратные решения.
Далее будем считать, что все объекты представлены набором выпуклых плоских граней, которые пересекаются только вдоль своих ребер.
К решению задачи удаления невидимых линий и поверхностей можно выделить два основных подхода.
Первый подход заключается в определении для каждого пикселя того объекта, который вдоль направления проектирования является ближайшим к нему. При этом работа ведется в пространстве картинной плоскости и существенно используются растровые свойства дисплея.
Второй подход заключается в непосредственном сравнении объектов друг с другом для выяснения того, какие части каких объектов будут являться видимыми. В данном случае работа ведется в исходном пространстве объектов и никак не привязана к растровым характеристикам дисплея.
Отсечение нелицевых граней.
Рассмотрим многогранник, для каждой грани которого задан единичный вектор внешней нормали. Несложно заметить, что если вектор нормали грани составляет с вектором , задающим направление проектирования, тупой угол, то эта грань заведомо не может быть видна. Такие грани называются нелицевыми. В случае, когда соответствующий угол является острым, грань называется лицевой.
В случае, когда сцена представляет собой один выпуклый многогранник, удаление нелицевых граней полностью решает задачу удаления невидимых граней.
В общем случае предложенный подход хотя и не решает задачу полностью, но позволяет примерно вдвое сократить количество рассматриваемых граней.
Метод Z-буфера.
Одним из самых простых алгоритмов удаления невидимых граней и поверхностей является метод z-буфера (буфера глубины). В силу крайней простоты этого метода часто встречаются его аппаратные реализации.
Сопоставим каждому пикселю (х, у) картинной плоскости, кроме цвета, хранящегося в видеопамяти, его расстояние до картинной плоскости вдоль направления проектирования z(x, у) (его глубину).
Изначально массив глубин инициализируется на "бесконечность".
Для вывода на картинную плоскость произвольной грани она переводится в свое растровое представление на картинной плоскости и для каждого пикселя этой грани находится его глубина. В случае, если эта глубина меньше значения глубины, хранящегося в z-буфере, пиксель рисуется и его глубина заносится в z-буфер.
Данный метод работает исключительно в пространстве картинной плоскости и не требует никакой предварительной обработки.
Метод W-буфера.
Данный метод является простым усовершенствованием Z-буфера. Различие состоит в том, что в буфере вместо значения глубины мы храним величину, обратную величине глубины. Благодаря этому количество расчетов сокращается.
Алгоритмы упорядочения.
Подход заключается в таком упорядочении граней, чтобы при их выводе в этом порядке получалось корректное изображение. Для этого необходимо, чтобы более дальние грани выводились раньше, чем более близкие.
Существуют различные методы построения такого упорядочения, однако часто встречаются такие случаи, когда заданные грани нельзя упорядочить. В подобных случаях необходимо произвести разбиение одной или нескольких граней, чтобы получившееся после разбиения множество граней можно было упорядочить.
Основные алгоритмы упорядочения рассматриваются ниже.
Метод сортировки по глубине.
Наиболее простым подходом к упорядочиванию граней является их сортировка по минимальному расстоянию до картинной плоскости (вдоль направления проектирования) с последующим выводом их в порядке приближения.
Этот метод великолепно работает для ряда сцен, включая, например, построение изображения нескольких непересекающихся достаточно простых тел.
Однако возможны случаи, когда просто сортировка по расстоянию до картинной плоскости не обеспечивает правильного упорядочения граней; поэтому желательно после такой сортировки проверить порядок, в котором грани будут выводиться.
Предлагается следующий алгоритм этой проверки. Для простоты будем считать, что рассматривается параллельное проектирование вдоль оси Oz.
Перед выводом грани Р следует убедиться, что никакая другая грань Q, проекция которой на ось Oz пересекается с проекцией грани Р, не может закрываться гранью Р. И если это условие выполнено, то грань Р должна быть выведена раньше. Предлагаются следующие 5 тестов в порядке возрастания сложности проверки:
- Пересекаются ли проекции этих граней на ось Ох?
- Пересекаются ли их проекции на ось Оу?
- Находится ли грань Р по другую сторону от плоскости, проходящей через грань Q, чем начало координат (наблюдатель)?
- Находится ли грань Q по ту же сторону от плоскости, проходящей через грань Р, что и начало координат (наблюдатель)?
- Пересекаются ли проекции этих граней на картинной плоскости?
Если хотя бы на один из этих вопросов получен отрицательный ответ, то считаем что эти две грани - Р и Q упорядочены верно, и сравниваем Р со следующей гранью. В противном случае считаем, что эти грани необходимо поменять местами, для чего проверяются следующие тесты:
3'. Находится ли грань Q по другую сторону от плоскости, проходящей через грань Р, чем начало координат?
4'. Находится ли грань Р по ту же сторону от плоскости, проходящей через грань Q, что и начало координат?
В случае если ни один из этих тестов не позволяет с уверенностью решить, какую из этих двух граней нужно выводить раньше, то одна из них разбивается плоскостью, проходящей через другую грань. В этом случае вопрос об упорядочении оставшейся грани и частей разбитой грани легко решается.
Метод двоичного разбиения пространства.
Существует другой, крайне элегантный способ упорядочивания граней.
Рассмотрим некоторую плоскость в объектном пространстве. Она разбивает множество всех граней на два непересекающихся множества (кластера), в зависимости от того, в каком полупространстве относительно плоскости эти грани лежат (будем считать, что плоскость не пересекает ни одну из этих граней).
При этом, очевидно, что ни одна из граней, лежащих в полупространстве, не содержащем наблюдателя, не может закрывать собой ни одну из граней, лежащих в том же полупространстве, что и наблюдатель. Тем самым сначала необходимо вывести грани из дальнего кластера, а затем уже и из ближнего.
Применим подобную технику для упорядочения граней внутри каждого кластера. Для этого построим разбиение граней каждого кластера на два множества очередной плоскостью; а затем для вновь полученных граней повторим процесс разбиения, и будем поступать так, до тех пор, пока в каждом получившемся кластере останется не более одной грани.
Обычно в качестве разбивающей плоскости рассматривается плоскость, проходящая через одну из граней (на самом деле при этом множество всех граней разбивается на 4 класса - лежащих на плоскости, пересекающих ее, лежащих в положительном полупространстве и лежащие в отрицательном полупространстве относительно этой плоскости). Грани, пересекаемые плоскостью, разобьем вдоль этой плоскости.
В результате мы приходим к дереву разбиения пространства (Binary Space Partitioning), узлами которого являются грани. Каждый узел такого дерева можно представить в виде следующей структуры:
Struct BSPNode
{
Facet * facet; // corresponding facet
Vector n; // normal to facet
double d; // plane parameter
BSPNode * Left; // left subtree
BSPNode * Right; // right subtree
};
При этом Left указывает на вершину поддерева, содержащуюся в положительном полупространстве, a Right - на поддерево содержащееся в отрицательном полупространстве.
Процесс построения дерева заключается в выборе грани, проведении через нее плоскости и разбиении множества всех граней. В этом процессе присутствует определенный произвол в выборе очередной грани. Существует два основных критерия для выбора:
- получить как можно более сбалансированное дерево;
- минимизировать количество разбиений.
К сожалению, эти критерии, как правило, являются взаимоисключающими, поэтому выбирается некоторый компромиссный вариант.
После того как это дерево построено, осуществляется построение изображения в зависимости от используемого проектирования.
Одним из основных преимуществ этого метода является его полная независимость от положения центра проектирования, что делает его крайне удобным для построения серий изображений одной и той же сцены из разных точек наблюдения.
Метод построчного сканирования.
Метод построчного сканирования является еще одним примером метода, работающего в пространстве картинной плоскости. Однако вместо того, чтобы решать задачу удаления невидимых граней для проекций объектов на картинную плоскость, сведем ее к серии простых одномерных задач. Все изображение на картинной плоскости можно представить как ряд горизонтальных (вертикальных) линий пикселей. Рассмотрим сечение сцены плоскостью, проходящей через такую линию пикселей и центр проектирования. Пересечением этой плоскости с объектами сцены будет множество непересекающихся (за исключением концов) отрезков, которые и необходимо спроектировать. Задача удаления невидимых частей для такого набора отрезков решается тривиально. Рассматривая задачу удаления невидимых граней для каждой такой линии, мы тем самым разбиваем исходную задачу на набор гораздо более простых задач.
Подобные алгоритмы с успехом используются для создания компьютерных игр типа Wolfenstein 3d и DOOM.
Рассмотрим, каким путем возможно применение этого метода для создания игры типа Wolfenstein 3d.
В этой игре вся сцена представляет собой прямоугольный лабиринт с постоянной высотой пола и потолка и набором вертикальных стен.
Разложим изображение сцены в ряд вертикальных линий. Каждая такая линия однозначно определяет вертикальную полуплоскость, проходящую через нее, и точку наблюдения. Ясно, что в данном случае среди всех пересечений этой полуплоскости со стенами лабиринта видимым будет только одно, ближайшее. При рассматриваемых условиях вся задача поиска пересечений может решаться в плоскости Oxy, что позволяет свести ее к поиску пересечений луча с набором отрезков, представляющих собой проекции стен лабиринта.
После того, как такое пересечение построено, пользуясь свойствами центрального проектирования, находится проекция стены на эту линию.
На самом деле каждая вертикальная линия изображения состоит из трех частей - пола, части стены и потолка. Поэтому после определения части линии, занимаемой проекцией стены (она представляв собой отрезок), оставшаяся часть линии заполняется цветом пола и потолка.
Алгоритм Варнака.
Алгоритм Варнака является еще одним примером алгоритма, основанного на разбиении картинной плоскости на части, для каждого из которых исходная задача может быть решена достаточно просто.
Разобьем видимую часть картинной плоскости на 4 равные части. В случаях, когда часть полностью накрывается проекцией ближайшей грани и часть не накрывается проекцией ни одной грани, вопрос о закрашивании соответствующей части решается тривиально.
В случае, когда ни одно из этих условий не выполнено, данная часть разбивается на 4 части, для каждой из которых проверяется выполнение этих условий, и так далее. Очевидно, что разбиение имеет смысл проводить до тех пор, пока размер части больше чем размер пикселя. В противном случае для части размером в один пиксель явно находится ближайшая к ней грань и осуществляется закрашивание.