Войти
ПрограммированиеТермины

Frustum Culling (Отсечение по пирамиде видимости)

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

Описание
Ссылки

Описание


Существует множество алгоритмов отсечения(Culling) невидимой геометрии, все они, как правило, основаны на особенностях представления сцены (например, для indoor помещений часто используется PVS и порталы, для outdoor ландшафтов - occlusion culling). Такие алгоритмы могут учитывать взаимное перекрытие объектов и другие особенности, некоторые так же могут быть применены к динамическим объектам.
Однако, самый простой и эффективный алгоритм отсечения - View Frustum Culling (VFC) - достаточно универсален и быстр. Во время отрисовки его необходимо применять как можно раньше, т.к. при незначительных затратах процессорного времени может удастся отбросить значительную часть невидимой геометрии и не выполнять ее дальнейшую обработку.

Для начала - небольшие технические подробности (за более полной информацией рекомендуется обратиться к документации Вашего графического API и к литературе по линейной алгебре). Для корректного проектирования полигонов на экран ко всем вершинам применяется проекционная матрица (в случае перспективной проекции она строится исходя из угла обзора камеры, дальность видимости и еще некоторых параметров и задает переход от 3-ех мерного пространства сцены в пространство глаза наблюдателя) и выполняется перспективное деление, в результате чего координаты вершин видимой части сцены лежат внутри единичного куба (фактически, это экранные координаты вершины и глубина). Если после умножения на матрицу вершина оказалась вне экрана (т.е. вне единичного куба), ее можно не рисовать. Таким образом, для всех вершин в пространстве сцены ограничивающим объемом являлась усеченная пирамида видимости (View Frustum, Frustum), а в пространстве камеры Frustum преобразуется в единичный куб.

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

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

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

Ссылки

Более подробную информацию и код можно найти по следующим адресам:
http://pmg.org.ru/nehe/nehex2.htm
http://www.mirgames.ru/articles/directx/d3dcamera.html
http://www.flipcode.com/articles/article_frustumculling.shtml
http://www.racer.nl/reference/vfc.htm
http://www.sjbaker.org/steve/omniv/frustcull.html
http://astronomy.swin.edu.au/~pbourke/projection/frustum/
И еще одно замечание: на практике часто встречается задача нахождения пересечения AABB и Frustum. Один из вариантов решения - для каждой плоскости пирамиды и для каждой вершины AABB находить расстояние скалярным произведением. Существует более эффективная техника: для каждой плоскости пирамиды находится только расстояние до ближайшей и до самой дальней вершины AABB (2 скалярных произведения). Ближние и дальние вершины AABB можно найти по постоянным индексам, которые вычисляются единократно для каждой плоскости.
В следующих документах подробно описаны эта и другие современные техники отсечения по Frustum:
http://www.ce.chalmers.se/~uffe/vfc_bbox.pdf
http://www.ce.chalmers.se/~uffe/vfc.pdf

Что такое Frustum Culling (Отсечение по пирамиде видимости)?

#culling, #frustum, #отсечение невидимой геометрии

27 июля 2005 (Обновление: 9 ноя 2010)

Комментарии [21]