воскресенье, 10 января 2010 г.

Software Occlusion Culling

Как известно, в сложных сценах могут возникнуть ситуации, когда объекты могут загораживать  другу-друга. В этом случае, алгоритм  Frustum Culling будет давать положительные результаты о видимости объектов, независимо от того загораживают они друг друга или нет.

Естественно, рендеринг большого числа загороженных объектов будет снижать быстродействие. Для решение данной проблемы используется алгоритм Occlusion Culling. Одна из реализаций алгоритма которая поддерживается аппаратно это Occlusion Query. Большим недостатком данного метода является то, что результат теста будет получен не сразу, а только после завершения работы видео карты, вызывая простои процессора(CPU Stall). Для решения данной проблемы используются несколько подходов, таких как иерархия запросов, получения результата через n-кадров, предсказания запросов и другие реализации. Для аппаратной реализации нужно рисовать упрощенную геометрию и ограничивающий объем объектов для тестирования. Это требует дополнительных вызовов графических API и дополнительных Render Target'ов,что в добавок ко всему усложняет реализацию. Отличная реализация алгоритма  с аппаратной поддержкой описана тут: Hardware Occlusion Queries Made Useful.

Я попробовал получать результаты через n-кадров, объекты мигали, результат меня не удовлетворил, не став больше экспериментировать я попробовал использовать софтварную реализации алгоритма.

Одним из способов софтварной реализации является построения Viewing Frustum по ограничивающему боксу объекта. Все объекты, полученные после обхода Scene Graph и отсортированные  по расстоянию до камеры, полностью попадающие в Frustum, без пересечений с его плоскостями, будут считаться невидимыми, и должны быть выкинуты из списка видимых.
Недавно мне порекомендовали еще более простой способ определения того что один объект полностью закрывает другой. Способ заключается в проверки спроецированных на плоскость экрана ограничивающих боксов объектов на полное попадание друг в друга. На данной реализации я и остановился.
Сначала я написал функцию проецирования точки на экран, заодно пополнив математическую библиотеку движка.
Проанализировав проекцию бокса на плоскость:





Стало видно, что точки 4 и 2 внутренние и должны быть выкинуты:




Таким образом, результатом проекции будет замкнутый шестиугольник.
Если ориентация бокса к камере под прямым углом, то дальние точки после проекции будут совпадать с передними, в этом случае результат проекции будет четырехугольник.Теперь можно
составленный список точек проекции бокса тестируемого объекта, проверять на попадание в замкнутую область проекции бокса закрываемого объекта. Тут подходит общеизвестный алгоритм нахождения точки внутри многоугольника.
Небольшая демка показывающая как это все работает.
Следует заметить, что не все объекту могут полностью закрыть другие. Сам объект должен быть непрозрачным. Обычно такой объект называют Occluder'ом, задавать такие объекты можно при разработке уровня. Геометрия объекта, который может полностью закрыть другие, должна быть сплошной, его ограничивающий бокс должен быть максимально к ней приближен,  если это не так, то следует задавать так называемые Occlusion Box'ы. К примеру для дерева нужно задать Occlusion Box ствола, но наверняка это будет не эффективно. Ведь площадь проекции ствола дерева в большинстве случае мала, и мало объектов будет отброшено за стволом. Идеальным кандидатом будет к примеру дом.

На моей тестовой сцене в некоторых местах иногда отсекается больше 200 объектов.
Теперь о результатах, приведу несколько скриншотов.

Occlusion Culling on, отброшено 243 объекта, FPS 37.



Occlusion Culling off, FPS 30.



Occlusion Culling on, отброшен 71 объект, FPS 41.



Occlusion Culling off,  FPS 35.



Как видно в некоторых случаях производительность можно поднять, особенно на сложных сценах, к примеру город, или если есть сложные объекты которые будут закрыты.