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

Часто при построении 3-х мерных сцен возникает ситуация, когда количество треугольников (граней), из которых состоит сцена оказывается велико, и на вывод сцены уходит много времени, хотя только небольшое число граней может быть одновременно видимо из точки наблюдения. Для оптимизации вывода сцены служат методы удаления невидимых граней, которые используют те или иные особенности геометрии сцены и расположения наблюдателя относительно её объектов. Ниже описываются основные методы удаления невидимых граней и различные методы оптимизации, применяемые в настоящее время для визуализации сцен.

Метод трассировки лучей

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

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

Данный метод является одним из самых простых и распространённых методов удаления невидимых граней и имеет аппаратную реализацию в большинстве современных графических акселераторах. Метод заключается в том, что для каждого пикселя, выводимого на экран, находится грань, расстояние до которой минимально. Для этого каждому пикселю, выводимому на экран, кроме его цвета ставится в соответствие расстояние до картинной плоскости вдоль направления проектирования (его глубина). z-буфер инициализируется значением +Ґ. Для вывода произвольной грани, эта грань сначала переводится в растровое представление (используя конкретное перспективное преобразование), а затем для каждого пикселя этой грани вычисляется значение его глубины. Если это значение глубины меньше значения, хранящегося значения в z-буфере для соответствующего пикселя, то это значение глубины заносится в z-буфер, а пиксель выводится на экран. Если это не так, то в z-буфер ничего не заносится, а пиксель не выводится на экран. Таким образом, после выполнения этих операций в каждой точке экрана будет находиться пиксель, соответствующий грани, находящейся ближе всего к картинной плоскости в данной точке. Довольно эффективным является совмещение растеризации грани с выводом в z-буфер. При этом могут применяться инкрементальные методы, требующие всего нескольких операций сложения на пиксель. В этом случае грань рисуется построчно, с применением линейной интерполяции для вычисления координат строки и её длины. Так как при использовании перспективного преобразования значения глубины пикселя изменяются нелинейно при линейном изменении значений координат X и Y пикселя, то для вычисления значения глубины пикселя инкрементальными методами используется w-буфер, в котором хранятся не значения глубины (z) пикселя, а значения 1/z, которые уже изменяются линейно при линейном изменении координат X и Y пикселя, и для нахождения значений 1/z могут применяться инкрементальные методы.

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

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

Одним из наиболее распространённых модификаций алгоритма z-буфера является алгоритм иерархического z-буфера. Назовём грань скрытой (невидимой) по отношению к z-буферу, если для всех её точкек их глубины не меньше соответствующих значений в z-буфере (при попытке вывести такую грань в z-буфер ничего не изменится). Куб (прямоугольный параллелепипед) назовём скрытым по отношению к z-буферу, если все его лицевые грани являются скрытыми. Теперь объединим несколько граней сцены и обведём вокруг них куб. Для вывода этих граней в z-буфер проверяется, является ли этот куб скрытым по отношению к z-буферу. Если это так, что и все грани, объединённые кубом являются скрытыми по отношению к z-буферу и не выводятся в него, сокращая количество вычислений и ненужных операций сравнения. Если же это не так, то всё равно не все грани, объединённые кубом являются видимыми и этот куб разбивается на части, а затем для каждой части выполняются такие же операции сравнения. Таким образом реализация данного алгоритма может выглядеть следующим образом. Вокруг всей сцены описывается куб, он разбивается на 8 частей (тоже кубы), а каждая из частей, в свою очередь, разбивается ещё на 8 частей и так до тех пор, пока количество граней в кубе не станет меньше заданного числа, при котором уже нет смысла в дальнейшей разбивке на части. Далее для вывода очередного куба в z-буфер для него проверяется, является он скрытым или нет. Если да, то все грани, объединённые этим кубом игнорируются, а если нет, то соответствующая проверка выполняется для всех его частей и т.д. Для упрощения проверки на скрытость грани строится z-пирамида. Основанием такой пирамиды является сам z-буфер, каждый последующий уровень пирамиды образуется из предыдущего объединением 4 (2 на 2) пикселей предыдущего уровня и присваиванием наибольшей глубины из этих 4 пикселей значению глубины соответствующего пикселя последующего уровня пирамиды. Вершиной пирамиды является уровень, состоящий из одного единственного пикселя. Далее для проверки скрытости грани по отношению к z-буферу сначала сравнивается значение минимальной глубины для этой грани с значением в вершине пирамиды. Если значение в вершине пирамиды меньше, то грань игнорируется, в противном случае она разбивается на 4 части и для каждой части выполняется сравнение с значениями на следующем (более низком) уровне пирамиды. И так до тех пор пока все части грани не будут отвергнуты, или пока текущим уровнем пирамиды не станет её основание.

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

Метод отсечения по нормалям

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

Метод сортировки по глубине (алгоритм художника)

Этод метод является самым простым из методов сортировки граней и работает аналогично тому, как художник рисует картину - сначала рисуются более далёкие объекты, а затем более близкие. Метод основывается на том факте, что если самая дальняя точка грани A ближе к наблюдателю (картинной плоскости), чем самая ближняя точка грани B, то грань B ни как не может закрыть грань A. Однако, в некоторых случаях это не всегда так. Можно подобрать такие две грани A и B, что для них не будет выполняться это правило. Иногда применяют следующую модификацию данного алгоритма: берутся средние значения расстояний от вершин граней до наблюдателя и для двух граней A и B выполняется сравнение этих значений. Если среднее значение глубины для грани A меньше соответствующего значения для грани B, то грань A закрывает грань B и сначала рисуется грань B, а затем - грань A. Наиболее распространённая реализации алгоритма сортировки по глубине заключается в том, что произвольное множество граней сортируется по ближайшему расстоянию до наблюдателя, а затем отсортированные грани выводятся на экран в порядке от самой дальней к самой ближней (back-to-front)). Метод работает лучше для построения сцен, в которых отсутствуют пересекающиеся грани.

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

Метод сортировки по глубине имеет тот же недостаток, что и метод z-буфера - избыточность. Несколько граней могут перекрываться, что приводит к неоднократному выводу некоторых пикселей. Для исправления этого недостатка используется вывод от самой ближней грани к самой дальней (front-to-back), причём вывод пикселей на экран осуществляется только в том случае, если они ранее ещё не были выведены. Если все пиксели экрана уже были выведены, то обработку следующих граней можно прекратить.

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

Метод используется для упорядочивания граней при помощи построения двоичного дерева. Суть метода заключается в следующем. Пусть имеется множество непересекающихся граней. Разобъём плоскостью это множество на два не пересекающихся подмножества, выбрав разбивающую плоскость так, чтобы она не пересекалысь ни с какой гранью. Плоскость разбивает всё пространство на два полупространства (кластера). Каждая грань попадает в то или иное полупространство относительно разбивающей плоскости. Ни одна из граней, лежащая в полупространстве, не содержащем в себе наблюдателя, не может перекрывать ни одну грань из полупространства, содержащего наблюдателя. Грани выводятся сначала из полупространства, не содержащего наблюдателя (дальний кластер), а затем из полупространства, содержащего наблюдателя (ближний кластер). Для упорядочения граней внутри каждого кластера используется аналогичный подход - выбирается плоскость, разбивающая каждый кластер на два подкластера и т.д. Данный процесс повторяется до тех пор, пока в каждом кластере останется не более одной грани. В итоге получается двоичное дерево (BSP tree - binary space partitioning tree). Узлами дерева являются плоскости, производящие разбиение, а листьями дерева являются грани. Теперь для вывода всех граней выполняются следующие действия - для текущего узла дерева определяется, где находится наблюдатель - в левом полупространстве от разбивающей плоскости или в правом. Если наблюдатель находится в левом полупространстве, то сначала выводятся грани из правого поддерева, а затем из левого. Таким образом, алгоритм вывода граней является рекурсивным. Если необходимо выводить грани в порядке от ближней к дальней (front-to-back), то порядок вывода поддеревьев меняется местами.

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

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

Метод двоичного разбиения пространства используется в таких играх, как DooM, Quake и Quake II. Например, в игре Quake для каждого листа BSP дерева строится список листьев, которые могут быть потенциально выдимы из этого листа. При построении сцены сначала определяется, какой лист содержит в себе наблюдателя, затем берётся список видимых листьев и сортируется при помощи BSP дерева.

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

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

Метод построения списка потенциально видимых граней

При реализации этого метода вся сцена разбивается на несколько частей (например, комнат). Для каждой из таких частей определяется какие грани потенциально могут быть видимы, если наблюдатель находится в пределах этой части и составляется список потенциально видимых граней (PVS - Potentially Visible Set). Далее при выводе сцены определяется в пределах какой из частей сцены находится наблюдатель и по соответствующему списку производится рисование граней с применением одного из методов удаления невидимых граней или оптимизации. Обычно, список потенциально видимых граней строится заранее, так как требует больших затрат и большого объёма вычислений.

Метод порталов

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

Метод иерархических подсцен

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