Удаление невидимых поверхностей Дано: камера (наблюдатель) набор объектов Задача - определить видимые объекты Проблема: объекты при проектировании могут закрывать друг друга

Классификация методов: По способу представления объектов: полигональное аналитическое (явное или неявное) ( F(x,y,z) = 0 ) параметрическое ( p = p ( t ) ) По пространству в котором проводится анализ Работаем в картинной плоскости - для каждого пиксела определить видимый объект Работаем в трехмерном пространстве - определяем области видимости По виду получаемого результата: значения на некоторой сетке (растровое представление) в виде объектов (аналитическое, точное представления)

Простейший случай - одно выпуклое тело n v (n,v) > 0- лицевая грань (n,v) < 0- нелицевая грань Если тело выпукло, то только его лицевые грани могут быть видны В случае одного выпуклого объекта задача полностью решена

Несколько выпуклых тел n v Если тел несколько - все нелицевые грани не видны некоторые лицевые грани могут быть закрыты лицевыми гранями других тел Одного удаления нелицевых граней в этом не достаточно

Основные методы Метод трассировки лучей (ray casting) Метод трассировки лучей (ray casting) Метод буфера глубины (z-buffer, depth-buffer) Метод буфера глубины (z-buffer, depth-buffer) Методы упорядочивания - Методы упорядочивания - алгоритм художника (Painters algorithm) алгоритм художника (Painters algorithm) использование BSP-деревьев использование BSP-деревьев

Трассировка лучей (ray casting) for all pixels: for all objects: find intersection compare z Затраты - O(C*n) Можно довести до - O(C*log n) Может работать с широким классов объектов - аналитические, параметрические, CSG, объемные

z-буфер (буфер глубины) (color, depth) def init(): for p in screen: p.color = (0,0,0) p.depth = infinity def putPixel(x, y, z, c): p = screen [x][y] if p.depth < z: return p.color = c p.depth = z color depth

z-буфер (буфер глубины) Ничего не выведеноВыведен объект АВыведены объекты А и В Выведены объекты А, В и С

z-буфер (буфер глубины) Работает только с полигональными объектами Работает только с полигональными объектами Порядок вывода объектов не играет роли Порядок вывода объектов не играет роли Аппаратно реализован на современных GPU Аппаратно реализован на современных GPU Огромная скорость работы Огромная скорость работы Требует обработки всех объектов Требует обработки всех объектов ++: --:

sort back-to-front draw sorted ABC Сортировка невозможна Метод художника draw C draw B draw A

Binary Space Partitioning (BSP) деревья A B C D E F

B A C D E F D E F C B A

def buildTree( objects ): plane = choosePlane ( objects ) left = [] right = [] for p in objects: code = plane.classify ( p ) if code == POSITIVE: left.insert ( p ) elif code == NEGATIVE: right.insert ( p ) else: pp = p.splitBy ( plane ) left.insert ( pp [0] ) right.insert ( pp [1] ) root = BspNode ( plane ) root.left = buildTree ( left ) root.right = buildTree ( right ) return root D E F C B A

Binary Space Partitioning (BSP) деревья Не зависит от положения наблюдателя Разбивает все пространство на набор выпуклых многогранников Обеспечивает быстрое упорядочивания объектов для любого положения наблюдателя Поддерживает упорядочивание back- to-front и front-to-back def render ( node, pos ): if node.isLeaf (): node.draw () return code = node.plane.classify (p) if code == POSITIVE: render ( node.left, p ) render ( node.right, p ) else: render ( node.right, p ) render ( node.left, p )

Сцена очень большая (миллионы объектов) Очень небольшая часть объектов видна Очень высокий overdraw Frustum cullingOcclusion cullingOcclusion fusion Необходимо как можно быстрее отбросить все невидимое

Оптимизация проверок на видимость Гораздо удобнее проверять не по одному многоугольнику, а по целой группе Часто используемые тела: Axis-Aligned Bounding Box (AABB) Сфера Опишем вокруг группы близко расположенных объектов достаточно простое тело (Bounding Volume)

Оптимизация проверок на видимость Описанное тело не видимо Вся группа объектов не видна Отбрасываем всю эту группу

Оптимизация проверок на видимость Построим по набору тел дерево, у каждого узла - свое ограничивающее тело Получаем простой и эффективный способ отбрасывания невидимых объектов def render ( node ): if ! isNodeVisible ( node ): return if isLeaf ( node ): node.draw () else: for c in node.children: render ( c )

Оптимизация проверок на видимость Эффективное использование occlusion culling и occlusion fusion требует полной информации о попиксельной видимости Вся эта информация лежит в буфере глубины GPU Переложим эти проверки на GPU GPU occlusion test

Аппаратный запрос проверки видимости Объект А не меняет содержимое z-буфера, поэтому он невидим по отношению к z- буферу Объект В изменяет содержимое z-буфера, поэтому он видим по отношению к z-буферу

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

Аппаратный запрос проверки видимости. Расширение GL_HP_occlusion_test // запретить запись в буфера // включить проверку glDepthMask ( GL_FALSE ); glColorMask ( GL_FALSE, GL_FALSE, GL_FALSE, GL_FALSE ); glEnable ( GL_OCCLUSION_TEST_HP ); // вывести (послать) тестовый объект drawTestObject (); // восстановить состояние glDisable ( GL_OCCLUSION_TEST_HP ); glDepthMask ( GL_TRUE ); glColorMask ( GL_TRUE, GL_TRUE, GL_TRUE, GL_TRUE ); // получить ответ на запрос glGetBooleanv ( GL_OCCLUSION_TEST_RESULT_HP, &objectVisible );

Аппаратный запрос проверки видимости. Расширение GL_HP_occlusion_test ++: Аппаратная проверка с использование z-буфера Поддержка occlusion fusion Поддержка произвольных тестовых объектов Попиксельная точность --: можно послать только один запрос (для следующего надо дожидаться ответа на текущий) Синхронная обработка - прежде, чем продолжать, надо дождаться ответа Ответ только типа «Да/Нет». Даже если для объекта из 20К пикселов виден всего один, то ответ будет - «Видим»

Аппаратный запрос проверки видимости. Расширения GL_NV_occlusion_query и GL_ARB_occlusion_query Можно послать только сколько угодно запросов (каждый запрос имеет свой уникальный идентификатор) Есть возможность быстро проверить готов ли результат для запроса по его идентификатору Ответ - количество пикселов, прошедших тест глубины Входит в OpenGL, начиная с версии 1.5

Аппаратный запрос проверки видимости. Расширения GL_NV_occlusion_query и GL_ARB_occlusion_query unsigned query [N]; // получить идентификаторы для запросов glGenOcclusionQueriesNV ( N, query );. send query [0]// послать первый запрос. send query [1]// послать следующий запрос. send query [N-1]// послать последний запрос..// проверить готов ли результат первого запроса glGetBooleanv ( query [0], GL_PIXEL_COUNT_AVAILABLE_NV, &res ); if ( res )// получить результат первого запроса glGetIntegerv ( query [0], GL_PIXEL_COUNT_NV, &count );

Пример использования аппаратных запросов проверки видимости.

for col in range ( cameraCol, infinity): for cell in col: sendQuery ( cell ) if queryReady: if cellVisible: drawCell if noMoreQueries: break if all cells invisible: return

Пример использования аппаратных запросов проверки видимости. Иерархии. Использование иерархий (различных деревьев), позволяет крайне эффективно отбрасывать невидимые объекты сразу большими группами kD-дерево - на каждом шаге строим ААВВ вокруг имеющихся в узле объектов и разбиваем его вдоль наиболее длинного его ребра на две части => получаем двоичное дерево Обратите внимание, что один и тот же объект может входить сразу в несколько узлов дерева, т.е. Нет необходимости разбивать объекты

Пример использования аппаратных запросов проверки видимости. Иерархии. def render ( node ): q = queryVisibility ( node ) if !q.isVisible: return if isLeaf ( node ): node.draw () else: render ( node.c [0] ) render ( node.c [1] ) --: При посылании запроса мы ждем окончания его обработки для продолжения работы. Ответ будет когда очередь в GPU дойдет до нашего запроса. Все это время простаивает CPU и не поступаю новые команды в очередь GPU => Выполним проверку на видимость GPU будет ждать поступления новых команд => Теперь простаивает GPU

Пример использования аппаратных запросов проверки видимости. Иерархии. Будем обходить дерево не в глубину, а в ширину - тогда можно сразу посылать много запросов про ряд узлов и по мере получения ответа обрабатывать узлы и посылать новые запросы Фактически возможности расширения использовались очень слабо - запросы посылались по одному и работа продолжалась по получении ответа на запрос

Пример использования аппаратных запросов проверки видимости. Иерархии. Будем считать, что узел остается видимым N кадров после проверки Сразу выведем узлы, видимые в предыдущем кадре Для тех из них, видимость которых проверялась больше чем N кадров назад пошлем запрос на видимость Для большинства задач видимость в от кадра к кадру практически не меняется

Пример использования аппаратных запросов проверки видимости. Иерархии. Для каждого выведенного узла пошлем запрос на видимость для его ближайшего «родственника» - «брата», «Дяди» и т.д. (Родительский узел проверять смысла нет - он видим, так как видим его дочерний узел)

Пример использования аппаратных запросов проверки видимости. Иерархии. Уже выведенные узлы Узлы, для которых сейчас будет послан запрос

Пример использования аппаратных запросов проверки видимости. Иерархии. Мы одновременно обрабатываем большое количество запросов и выводим объекты, т.е. избегаем простоев как CPU, так и GPU. Количество обрабатываемых объектов в общем случае пропорционально количеству реально видимых объектов