Методы упорядочивания. 
Компьютерная графика

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

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

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

Простейшим из методов упорядочивания является так называемый алгоритм художника (painters algorithm). Подобно тому, как художник сначала рисует более дальние объекты, а поверх них — более близкие, данный алгоритм сортирует все грани по степени их удаления от центра проектирования (наблюдателя, камеры) и затем выводит их, начиная с самых дальних и заканчивая самыми близкими (такое упорядочивание называется back-to-front).

На практике для сортировки массива всех граней по мере приближения к центру проектирования обычно используют qsort или std: sort. В качестве расстояния от треугольника до центра проектирования берут расстояние между центром проектирования и какой-то определенной точкой грани. В качестве такой точки чаще всего выступает или первая вершина грани, или среднее арифметическое всех вершин грани.

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

Одним из красивых и простых методов получения всегда верно упорядоченных граней является метод, основанный на деревьях, получаемых при двоичном разбиении пространства (BSP, Binary Space Partitioning). Основная идея этого метода крайне проста. Пусть у нас есть две грани (или объекта) А и В, лежащие по разные стороны от некоторой плоскости (рис. 7.14). Тогда грань, не лежащая в одном полупространстве с центром проектирования, никогда не может закрыть собой грань, которая лежит в том же полупространстве, что и центр проектирования.

Рис. 7.14. Грани Л и В, лежащие по разные стороны от заданной плоскости

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

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

Рис. 7.16. Процесс разбиения множества граней.

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

Рис. 7.17. BSP-дерево

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

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

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

Простейшей оптимизацией, которую можно добавить к BSPдереву, является хранение в каждом узле не только разбивающей плоскости, по и минимального прямоугольного параллелепипеда с ребрами, параллельными осям координат, содержащего внутри себя все грани из соответствующего поддерева. Для обозначения прямоугольного параллелепипеда с ребрами, параллельными осям координат, обычно используют термин ААВВ (Axis Aligned Bounding Box). Ниже приведен пример подобного модифицированного класса (без методов):

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

Использование BSP-деревьев играло важную роль в таких классических играх, как Doom, Quake и многих других. Также они используются для ряда других задач, например проверок на пересечения игрока с геометрией сцены.

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

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

Рис. 7.18. Пример разбиения сцены на выпуклые многогранники.

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

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