воскресенье, 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.



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

3 комментария:

Neill комментирует...

спасибо за пост, полезный. Есть кое-какие вопросы... вот у тебя отсекается в некоторых случаях больше 200 объектов. Является ли браш с травой отдельным объектом? я смотрю травы много на уровне, она идет целиком или отдельными брашами ?
нужна ли необходимость задавать BB в ручную для объектов? такая ситуация, у меня есть авто, ему считается BB автоматом при загрузке, но если я начну отсекать по этому боксу объекты, то будут провалы, потом что крыша задает высоту бокса, а на уровне багажника и капота высота ниже. В итоге получается что нужно в ручную бокс уменьшать ? может тогда какой-то контурный алгоритм использовать и его юзать как для отсечения, так заодно и для отрисовки теней стенсельных раз на то пошло... контуры сейчас вроде даже шейдерами считают...

Andrey комментирует...

Да, браш с травой является отдельным объектом, занимает он определенную область, например 256x256, входит он так-же в Scene Graph и участвует в сортировке имеет, свой BB и т.д. Вся трава рисуется этими брашами, естественно не полностью.
По поводу задания BB для объектов, тут зависит от ситуации, если объект полностью повторяет BB то не стоит. Для дома я взял временно его бокс, хотя это не совсем правильно, ведь начиная с крыши будут ошибки в отсечении. Да, бокс можно уменьшить вручную, для простых объектов это подойдет, например для дома его можно опустить, для автомобиля его еще нужно ужать с двух сторон(в зависимости от формы автомобиля), слева и справа, да еще и снизу.

Kralfy комментирует...

Спасибо огромное за информацию, как раз то, что искал!
А не могли бы Вы выложить исходники собственно алгоритма OC? Был бы очень благодарен.