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.

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

Multithreading in OpenGL API

Как известно, OpenGL имеет некоторые неудобства для работы в разных потоках, по сравнению с Direct3D. Сам недавно столкнулся с этими неудобствами на платформе Windows.
Согласно документации MSDN, для каждого потока в котором будет работа с OpenGL API, должен быть свой текущий контекст рендеринга, установку текущего контекста
осуществляется с помощью функции wglMakeCurrent.
Если это не так, то при любом обращении к функциям OpenGL API будет ошибка GL_INVALID_OPERATION, ну а дальше нарушенный доступ к памяти и далее поведение
программы не определено.
Для решения этой проблемы, нужно создать для нового потока новый контекcт воспроизведения, используя функцию wglCreateContext.
В качестве контекста окна можно передать контекст окна приложения, хотя по некоторым советам, следует создать дополнительное маленькое окно размером 1x1 пиксель.
Хотя у меня работало и без дополнительного окна. Далее, нужно что-бы все изменения между потоками были известны друг другу. К примеру, создается
текстура, вершинный или индексный буфер и т.д. в одном потоке, а использоваться будет в другом. Осуществить это нужно с помощью функции wglShareLists,
причем тут дисплейные списки в описании функции я не знаю.
Лучше сделать расшаривание контекстов друг на друга, хотя все зависит от задачи, т.е. если есть к примеру есть load_context и render_context, которые используются в потоке загрузки и рендеринга соответственно, то пара вызовов:
wglShareLists(load_context, render_contex);
wglShareLists(render_contex, load_context);
обеспечат видимость изменений между этими потоками.
В случае неудачи вызова wglShareLists у меня GetLastError возвращает ошибку, строковое соответствие полученное через FormatMessage было таким:
"невозможно создать файл так как он уже существует", почему это так, для меня загадка.
При завершении каждого потока нужно не забыть освободить связанный с ним контекст.

Различные доработки.

Итак, после долгой паузы решил написать что еще сделано, что еще планируется.
Добавлено задание Анизотропной фильтрации в материале. Значение фильтрации задается там-же, в случае если нет поддержки со стороны железа текущего значения, подменяется ближайшее по значению, если анизотропная фильтрация не поддерживается, производится замена на трилинейную. Есть идея с большого расстояния отключать анизотропную фильтрацию и включать трилинейную, но даст это что-то для повышения быстродействия, нужно подумать.

Написаны реализации кубических и трехмерных текстур. Так-же в случае реализации рендера в текстуру для них.

Как известно, на сложных сценах рисуется много объектов. Если не применять инстансинг, то встает проблема минимизации числа вызовов рисования геометрии, имеется ввиду вызовы соответствующей функциональности в Direct3D9, Direct3D10 и в OpenGL: IDirect3DDevice9::DrawIndexedPrimitive, ID3D10::DrawIndexed, glDrawElements, glDrawRangeElements. Инстансинг стоит в планах, а пока для каждого объекта сцены ставиться вершинный и индексный буфер. Если объектов будет тысячи, на моей тестовой сцене это число уже больше, то число переключений вершинных и индексных буферов буферов будет снижать быстродействие. Возникла идея, собрать все меши имеющее одинаковый формат вершин в единый вершинный буфер, аналогично поступить с индексными. Это будет еще более актуально, если число объектов отличающихся по геометрической форме будет большим.
Вот некоторая статистика для сцены вместе с тенями для 1377 объектов, всего разных объектов для текущей сцены около 50:
Число переключений буферов в случае общих вершинных и индексных: 59, 58
Число переключений буферов в случае отдельных вершинных и индексных: 96, 84

Улучшилась работа профайла. Сделал усреднение времени по 10 кадрам, теперь значения не "прыгают". Фильтрация показа малых значений времени.

В файле описания уровня можно задавать Render Target'ы, привязанные к объектам сцены. Параметры, такие как размеры, формат пикселей, пишутся там-же. Если Render Target служит для отражения то указывается в параметре для какой плоскости это происходит. В таком случае при обходе Scene Graph'a, будет происходить сбор как самих видимых объектов, так и заполняться список видимых объектов для каждого заданного Render Target'а. Такой подход удобен для реализации отражений для моделирования воды, зеркал или еще чего нибудь. В данный момент реализовываю отражение в воде.

Добавлена реализация менеджера камер. Камеры можно задавать из файла уровня, вместе с параметрами и некого имени. Текущую камеру можно подменить, это дает мозможность смотреть сцену с различных точек. Планируется сделать доступ к такой функциональности из Lua скриптов. В планах исправить ошибки с реализацией треков камеры. Движок может записывать треки камеры в заданный файл, запуская отдельный поток, происходит это в специальном режиме, включаемой командой консоли. Готовые треки камеры можно задавать в уровне или грузить на лету. Пускать текущую камеру по заданному треку, пока что можно с помощью консольной команды.

FastArray

Сейчас очень много сделано в движке. Есть некоторые недоделанные реализации чего либо.
К примеру Hierarchy Occlusion Culling, обход SceneGraph для поиска объектов являющихся RenderTarget'ами вода, зеркала и т.д. Постепенно проводиться оптимизация движка. В частности замер профайлером работу отдельных функций. На данный момент есть частое добавление объектов в динамический массив в каждом кадре. Как для от рисовки в текстуру теней так и для поиска видимых объектов. Для этого использовался ранее обычный std::vector с заранее вызванным std::vector::reserve. Почитав пост известного всем IronPeter'а Банановые шкурки, я подумал что сам метод std::vector::push_back уж очень универсален, там есть проверка на текущий размер с выделением памяти при необходимости и много других вызовов. К примеру std::vector::operator [] очень быстрый, но лишен универсальности, к примеру проверка выхода за диапазон, для этого есть std::vector::at. Иногда возникает вопрос, почему разработчик STL Александр Степанов не добавил быструю реализацию push_back, назвав ее к примеру fast_push_back?
Для некоторых частных специфических задач, требующих минимальной загрузки CPU, проверять выход за пределы не нужно вообще, к примеру как в этом случае - быстрое добавление данных с инкрементом указателя, который смещается к концу масса, причем размер массива уже известен.
Поэтому я написал свою довольно простую реализацию FastArray унаследовав с защищенным доступом от std::vector. Реализация выглядит так:

#ifndef __FASTARRAY_H__ #define __FASTARRAY_H__ #include "exceptions.h" #include <cassert> #include <vector> // Fast Dynamic Array template<typename T> class FastArray : protected std::vector<T> { private: typedef std::vector<T> BaseClass; T* last; public: typedef T* iterator; typedef const T* const_iterator; void resize(size_t count) { BaseClass::resize(count); last = &*BaseClass::end(); } void reserve(size_t count) { BaseClass::reserve(count); last = &*BaseClass::end(); } const_iterator end() const { return last; } iterator end() { return last; } const_iterator begin() const { return &*BaseClass::begin(); } iterator begin() { return &*BaseClass::begin(); } T& back() { assert(last && "NULL Pointer"); assert(!empty() && "Empty Array"); return *(last - 1); } const T& back() const { assert(last && "NULL Pointer"); assert(!empty() && "Empty Array"); return *(last - 1); } T& front() { assert(!empty() && "Empty Array"); BaseClass::front(); } const T& front() const { assert(!empty() && "Empty Array"); return BaseClass::front(); } bool empty() const { return &BaseClass::front() == last; } size_t size() const { assert(last >= &*begin() && "Out of Range"); return static_cast<size_t>(last - &*begin()); } size_t capacity() const { return BaseClass::capacity(); } void pop_back() { assert(last && "NULL Pointer"); assert(last >= &*begin() && "Out of Range"); --last; } void push_back(const T& val) { assert(last && "NULL Pointer"); *(last++) = val; } T& operator [] (size_t index) { assert(&*begin() + index < last && "Out of Range"); return *(begin() + index); } const T& operator [] (size_t index) const { assert(&*begin() + index < last && "Out of Range"); return *(begin() + index); } void clear() { last = &*begin(); } FastArray(size_t count, const T& val = T()) : BaseClass(count, val), last(&BaseClass::back()) { } FastArray() : last(&BaseClass::back()) { } ~FastArray() { } }; #endif

Такая реализация обеспечивает быстрое добавление в конец и очистку массива, так-же работу с итераторами. Единственным минусом является небезопасное добавление, если число элементов превышает длину массива.

Parallel Split Shadow Map тени.

Наконец Внедрил Parallel Split Shadow Map в движок. Реализация основана на демке PSSM
Разбиения рассчитаны по логарифмической схеме logarithmic split scheme.
Было несколько ошибок: Дикие растяжения теней проблема из-за неправильного построения Crop Matrix, проблемы с глубиной, исчезновение объектов и листьев ландшафта.
Crop Matrix это некая матрица трансформации с масштабированием и смещением. Как раз она корректирует текущую матрицу проекции источника света подгоняя под ограничивающую область текущего сплита, для оптимального использования разрешения текстуры теней, избегая проблем алгоритма стандартных теней Shadow Map Aliasing. Спасибо Арсению Капулкину(Zeux) за подсказку.
Вторая проблема была связана с рисованием объектов через FFP(что я планирую исправить на шейдеры по умолчанию) в Direct3D9/OpenGL при выключении шейдера на большом расстоянии, я просто не учел матрицу проекции для текущего split.
Третья проблема тоже простая, для видимого объекта ставился флаг видимости, и если он виден в текущем разбиении н не виден в предыдущем или последующем флаг сбрасывался и объект не рисовался.
Четвертая проблема еще проще, рисовался повторно ландшафт, затирая то, что уже отрисовано создавая эффект выпадания листьев.
Приведу несколько удачных скриншотов показывающих разницу между Parallel Split Shadowm Map и Standart Shadow Map. Скриншоты сделаны в режиме Direct3D9 рендера.

SSM

PSSM

SSM

PSSM

SSM

PSSM


SSM

PSSM

В процессе внедрения PSSM использовал подход в выставлении отладочного пиксельного шейдера, который выставляется для объектов текущего разбиения подсвечивая их красным цветом игнорируя текстуры и освещение. Спасибо Сергею Милойкову(Zemedelec) за предоставленный совет. Данная функциональность удобно включалась командой с консоли "debug_split i" - где i номер разбиения.
"debug_split -1" - отключал отладку.
Выглядит это вот так:

Split 0

Split 1

Split 2

Как видно из отладки объекты могут рисоваться повторно если попали сразу в несколько разбиений, что подсаживает производительность. Над этом буду думать.
В планах исправить небольшие недочеты в режиме теней PSSM, доработать реализацию под OpenGL, скорей всего там просто просто учесть порядок хранения матриц.

Тени в OpenGL рендере. Прогресс и дальнейшие планы.

Сначала я сделал тени для Direct3D 9. Потом переделал для OpenGL. Тени работали, но отличались в OpenGL по сравнению Direct3D в худшую сторону. Эту задачу я отложил до лучших времен. Иногда к ней возвращался но так и не мог понять в чем дело. Реализация у меня была с использованием рендера в текстуру и с использованием расширений GL_ARB_vertex_program и GL_ARB_fragment_program. (Код получен как результат компиляции Cg компилятором.)На данный момент частично используется GLSL полученный как результат компиляции из Cg.Сначала я думал что проблема в проблема была в использовании или инициализации рендера в текстуру с использованием GL_EXT_frame_buffer_object в связке с текстурами с плавающей точкой через расширение GL_ARB_texture_float. Но вскоре выяснилось что я немного неправильно построил матрицу источника света и матрицу текстуры. Теперь тень пиксель в пиксель совпадает с Direct3D.

OpenGL:

Direct3D:

В общем я решил пока не удалять OpenGL рендер из движка. Не так все плохо. Но еще есть проблемы на ATI.

На данный момент добавил рендер всей сцены в глубину. Результат сохраняется в float текстуру. Используя это эту возможность расширил в связи с этим менеджер постропцессинга, который может использовать эту текстуру. К примеру к примеру на основании этого реализовал эффект постпроцессинга Dof - Depth of Filed. Спасибо за переработанный шейдер из различных SDK Глебу Гущину(innuendo), а помощь в исправлении расчета преобразования глубины Арсению Капулкину(Zeux).
На данный момент идет улучшение теней с использованием алгоритма
Parallel Split Shadow Map.

В дальнейших планах исправление ошибок. Сейчас их накопилось много. Есть серьезные, а есть просто много мелочей. Параллельно буду писать редактор. Пусть пока простой - расстановка объектов, cохранение и загрузка.

Передача констант в шейдеры.

Всем известно что передавать константы лучше все сразу, а не по отдельности, либо минимизировать эти вызовы.
Достичь это можно несколькими путями и по разному для каждого API. Опишу отдельно для Direct3D9, Direct3D10, OpenGL.
Для Direct3D9 лучше Не использовать ID3DXEffect для шейдеров, не использовать ID3DXConstantTable для установки констант. Они не несомненно удобны но не очень быстрые в работе. Почему сейчас расскажу.
Возьмем любой метод ID3DXEffect/ID3DXConstantTable для установки констант. Все они имеют параметр D3DXHANDLE - это либо строка либо указатель возвращаемый
другими методами. Напрашивается вопрос как значение этого параметра внутри распознается. Внутри это может быть либо свой указатель либо строка с именем константы.
Что конкретно определяется проверкой установленного старшего бита параметра, если установлен то HANDLE, если нет то строка. Таким образом, мы имеем некие потери при установки константы. При чем внутри таких вызовов будут еще и проверки. Если это строка то будет поиск по строке, пусть даже через Hash. В случае с указателем чуть быстрее. Итого, представив много шейдера на сложной сцене, с большим числом констант, которые еще что хуже всего передаются по имени через строку.
В данных интерфейсах есть средства для засылки констант группой, за справкой отсылаю к DirectX SDK. Но нет средств что-бы заслать все константы для всего шейдера разом, что по идее должно быть идеально. Что бы слать все, лучше использовать напрямую интерфейсы IDirect3DPixelShader9/IDirect3DVeretxShader9 и использовать методы:
IDirect3DDevice9::SetPixelShaderConstant*/IDirect3DDevice9::SetVertexShaderConstant*
при таком подходе можно заслать единообразно все константы определенного типа за 1 вызов начиная со стартового регистра. Причем ID3DXConstantTable/ID3DXEffect являются wrapper'ами над этими методами.
Для Direct3D10 все намного проще. Есть константные буферы которые и предназначены для передачи группы констант. Кроме того данная функциональность есть в ID3D10Effect интерфейсе.
К сожалению в OpenGL с этим немного похуже ситуация. В расширениях GL_ARB_fragment_program/GL_ARB_vertex_program есть функция glProgramLocalParameter4fvARB, но она не позволяет слать больше 4 float(1 регистр).
Можно использовать для матриц константы GL_MATRIX0_ARB - GL_MATRIX31_ARB
и передавать через glMatrixMode это чуть улучшает ситуацию. Недавно я использовал новое расшерение GL_EXT_gpu_program_parameters оно позовляет засылать константы пачками. Причем это прямой аналог передачи констант для Direct3D9. Радует поддержка расширения на ATI.
Для GLSL передавать все константы для шейдера за 1 вызов не получится. Потому что нет у порядочности хранения uniform переменных. И функции для передачи параметров могут передавать либо матрицу либо vector4 и т.д. Можно передать матрицы 1 вызовом но их нужно хранить в массиве. Но с появлением расширения GL_EXT_bindable_uniform ситуация улучшилась но оно поддерживается пока только nVidia картами.