3 февраля 2011

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

Я начал неделю с работы над загрузкой и выгрузкой блоков данных кубов по мере того, как вы перемещаетесь по миру. Это просто. Что сложнее - так это быстро отрисовывать данные кубов и создавать уменьшенную детальную версию для использования на расстоянии. Такова тема этой части.

Производительность графики

Как отмечали Флориан и другие, мой код для рисования кубов, который восходит к первой части, весь неправильный. Я реализовал свой код для рисования так, как вы бы это сделали двадцать лет назад, когда я впервые освоил 3D-компьютерную графику. Тогда видеокарта была просто куском видеопамяти без всякого интеллекта. Все делалось на центральном процессоре. Сейчас, чем больше вы делаете на CPU, и чем меньше вы делаете на видеокарте (GPU), тем медленнее будет код.

Рис. 1: Мой тест на скорость - 416 634 кубов

У нас есть два типа данных - непрозрачные и прозрачные. Непрозрачные данные могут быть отрисованы в любом порядке. Как упоминалось в части 4, z-буфер используется графической картой для рисования ближайших к нам кубов поверх удаленных кубов. Прозрачные данные отличаются - они должны быть отсортированы и нарисованы от дальних к ближним так, чтобы дальние кубы отображались сквозь более близкие кубы (представьте себе сцену, которую вы рассматриваете через стакан с водой).

Демонстрационный код части 4 рисует непрозрачный и прозрачный за два прохода. Сначала он проходит по кубикам сцены, хранящимся в Octree. Для каждого куба есть шесть флагов, говорящих о том, какие из сторон видны. Каждая видимая сторона образована двумя треугольниками. Каждая сторона имеет свою текстуру в зависимости от типа куба (камень, дерево и т.д.).

Самый простой способ сделать это - нарисовать каждую грань каждого куба по мере того, как мы вытаскиваем их из Octree. Я знал, что переключение текстур между гранями каждого куба повредит производительности, поэтому я этого не делал. Вместо этого я сохраняю буфер для каждой текстуры. По мере считывания кубов, треугольники добавляются в различные буферы. Когда буфер заполнен, кусок треугольников (все в одной текстуре) отправляется на графическую карту для рисования.

Прозрачные данные не могут использовать даже эту оптимизацию. Так как прозрачные данные должны быть отрисованы по порядку, от дальних к ближним, я не могу их буферизировать, чтобы избежать переключения текстур. Если есть блок листьев за стеклянным блоком за блоком воды, я должен нарисовать их в таком порядке и переключить текстуры три раза. Сначала нарисовать всю воду не получится.

Это отсутствие оптимизации действительно проявляется. Мой компьютер - это шестиядерный процессор AMD Phenom II с частотой 2,8 ГГц и видеокартой NVidia GTS 250. Мой тестовый пример показан на рисунке 1, кусок данных Minecraft 128 на 128 на 128 кубов. Всего 416 634 куба, которые после учета флагов видимости на каждой грани генерируют 315 188 непрозрачных треугольников и 33 600 прозрачных. Некоторые из непрозрачных треугольников - это маленькие сферы, которые я рисую вместо факелов Minecraft.

Итак, вот мои данные для кода Демо 4, который был моей отправной точкой на этой неделе:

Непрозрачные: 31,19 мс Прозрачные 39,83 мс Всего: 71,02 мс Частота кадров: 14 fps

Отметим, что, несмотря на 33 600 прозрачных треугольников, на рисование их уходит больше времени, чем на 315 000 непрозрачных. Это потому, что я их вообще не буферизирую. Каждый из них - это два вызова графики (установить текстуру, нарисовать треугольник).

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

Вершинные и индексные буферы

Вы можете создавать буферы на видеокарте, а не в памяти системы. В DirectX они называются вершинными и индексными буферами. Нам нужны данные на графической карте, чтобы графический процессор мог быстро получить к ним доступ. Вершина на самом деле содержит больше данных, чем просто расположение точки. Есть местоположение, нормаль (в каком направлении плоскость обращена в этой точке) и координаты текстуры. Это восемь 4-байтовых значений с плавающей точкой на вершину.

Можно было бы подумать, что мы можем использовать вершины повторно, так как у куба всего 8 вершин, но, к сожалению, это не так. Нормали точек на верхней стороне куба указывают вверх, а нормали точек на передней стороне - наружу. Таким образом, на самом деле существует 6x4=24 уникальных вершины на одном кубе, из которых формируется 12 треугольников, составляющих куб.

Так как непрозрачные кубы могут быть нарисованы в любом порядке, моя первая оптимизация заключается в том, чтобы сгенерировать все нужные нам вершины и поместить их в Vertex Buffer Object (VBO) на видеокарте. Затем, чтобы их нарисовать, мне просто нужно сказать GPU, чтобы он нарисовал этот буфер, а не генерировал все точки и перемещал их на видеокарту 60 раз в секунду.

Индексный буфер представляет из себя список номеров вершин. Поэтому вместо того, чтобы нарисовать треугольник, дав ему вершину 0, вершину 1 и вершину 2, мы создаем индексный буфер с числами 0, 1, 2 в нем, и графическая карта пойдет искать эти вершины в VBO. Это позволяет нам легко повторно использовать вершины, не дублируя их. Вместе буфер вершин и буфер индексов описывают список треугольников.

На самом деле, в этой первой версии я не использую ни одного индексного буфера. Мне все еще приходится менять текстуры, когда я рисую сцену. Так что вместо того, чтобы генерировать треугольники в буфере, как это делает Demo 4, я генерирую все вершины, а затем отдельный индексный буфер для каждой текстуры. Так что все дерево имеет один индексный буфер, а все камни - другой. Это значит, что я рисую 20+ кусков данных, а не один. Но все они имеют один и тот же буфер вершин.

Позже я взглянул на DirectX API еще раз и понял, что могу держать все индексы в одном буфере, так как есть вызов для отрисовки части индексного буфера. Это позволяет мне увеличить скорость:

Непрозрачные: 1,87 мс Прозрачные: 49,44 мс Всего: 51,31 мс Частота кадров: 19 fps

Непрозрачные треугольники теперь очень быстрые, более чем в 16 раз быстрее, чем раньше! Я очень доволен этим результатом, несмотря на то, что я делаю более 40+ вызовов графики для рендеринга (устанавливаю текстуры и рисую треугольники для каждой из 20+ текстур.) Прозрачные данные еще хуже, из-за некоторых изменений, которые я внес в интерфейсы. Это так плохо, что не позволило нам реально улучшить частоту кадров. 19 кадров в секунду все еще неприемлемо.

Более быстрые прозрачные треугольники

Мне все равно нужно рисовать эти прозрачные треугольники по порядку, а это значит, что список потенциально отличается для каждого кадра и не может просто находиться на видеокарте. В последний раз код прозрачного треугольника почти не изменился, что означает, что он все еще рисует треугольники отдельными вызовами. Я не обязан это делать.

Так как все вершины уже есть в VBO, я могу, по крайней мере, менять прозрачные данные только в индексах. Я буду заполнять индексный буфер до тех пор, пока не придет время менять текстуры, затем рисовать треугольники, которые у меня есть, и сбрасывать буфер. Эта оптимизация дает мне следующий результат:

Непрозрачные: 1,87 мс Прозрачные: 26,51 мс Всего: 28,38 мс Частота кадров: 35 fps

Интересно, что моя первая реализация была ужасно медленной - намного медленнее, чем раньше - и мне потребовалось некоторое время, чтобы разобраться в этом. Я использовал тот же индексный буфер, что и для непрозрачных данных, просто зарезервировав его часть для прозрачных треугольников. Однако, открытие этого буфера и его изменение при каждом цикле обновления означало, что DirectX не мог держать его в памяти видеокарты. Возможно, он даже копировал все это в память видеокарты каждый раз, когда я его изменял. Поскольку для рисования сцены используется более миллиона индексов, по 4 байта на индекс, это означало бы копирование 4 мегабайт за каждый цикл обновления! Чтобы исправить это, мне пришлось создать отдельный индексный буфер только для прозрачных данных и объявить его "динамическим" для DirectX.

Мы сократили время прозрачного прохода почти вдвое, не выполняя отдельные системные вызовы и не генерируя вершины. Но не очевидно, что будет следующим шагом. Переключение текстур так часто означает, что для рисования сцены осталось 2390 изменений. Каждый из них представляет собой два вызова - установка текстуры и рисование треугольников.

Нам еще предстоит пройти весь Octree, с его полумиллионом узлов, каждый из которых обновляется. В каждом узле есть немного кода, который нужно запустить. Пришло время взглянуть на это.

Некоторые люди используют инструменты профилирования, чтобы получить время, потраченное на каждую процедуру. Я нахожу эти инструменты вводящими в заблуждение. Они не понимают, что вы делаете функционально, и легко заблудиться в сорняках. В конце концов, вы пытаетесь улучшить реализацию, а не алгоритмы. Я предпочитаю просто укорачивать куски кода и видеть, как меняется общее время.

Общее время - 26 мс. Если я сгенерирую все треугольники, но не нарисую их, это займет у меня 20 мс. Это говорит о том, что большая часть времени находится в моем коде, а не в DirectX или видеокарте. Если я просто прохожу по дереву, ничего не делая с узлами, это занимает 3 мс. Это говорит мне, что проблема в том, как я генерирую список индексов.

Я пялюсь на него некоторое время и кажется, что тут нечего исправлять. Я должен посмотреть на все шесть сторон куба, и для каждой из них с пометкой "видимый", нарисовать два треугольника. Я просто генерирую список индексов для каждого треугольника, что является минимальным объемом работы, который мне нужен. Я суечусь с интерфейсами моего индексного буфера, чтобы использовать меньше вызовов методов, и я смотрю на свой код, чтобы пересечь Octree в отсортированном порядке. Ничего не меняется!

Потом приходит момент "doh!" - я проверяю все грани всех кубов дерева, даже когда мой флаг-байт ("vis") равен нулю для всех граней, что указывает на закопанный куб. Как говорил мой учитель информатики: "Самый быстрый код - это код, который вы никогда не запускаете". Такая быстрая проверка исключает большой процент кубиков.

Тогда я понимаю, что проверяю куб на прозрачные стороны, даже когда тип куба (дерево или камень) не имеет прозрачных граней. Я добавляю суммарный флаг для каждого типа куба, и теперь я могу быстро отбрасывать эти кубы без проверки сторон вообще.

Эти два улучшения дают мне следующие результаты:

Непрозрачные: 1,87 мс Прозрачные: 16,49 мс Всего: 18,36 мс Частота кадров: 54 fps

Только эти очевидные оптимизации, которые добавили всего несколько строк кода, сэкономили мне 10 мс из 26 мс. Из оставшихся 16 мс, сколько составляет мой код, сколько связано с переключением текстур, и сколько времени рисования?

Если я скажу коду использовать одну текстуру для всех прозрачных блоков так, чтобы не было переключения, время сократится до 10.82 мс. Если я говорю ему не рисовать графику, время падает до 10,14 мс. Другими словами, время на реальную прорисовку графики ничтожно мало. Что действительно занимает время, так это генерация индексов и выполнение всех DirectX-вызовов.

Время для OpenGL?

Для устранения вызовов, связанных с переключением текстур, мне нужно использовать то, что называется " Texture Arrays" (Массивы текстур). Обычно вершинам даются две координаты текстуры, называемые u и v. Это индексы x и y в изображении текстуры. Использование текстурного массива добавляет третью координату, которая выбирает, какая текстура используется вершиной.

С помощью этой функции я заранее генерировал бы все свои вершины, и каждая из них была бы помечена текстурой, как непрозрачной, так и прозрачной. Тогда я смогу генерировать все индексы для прозрачных треугольников за один пакет, никогда не меняя текстуры. Это сэкономит мне дополнительные 5 мс, общее время 12,69 мс, и даст частоту 78 кадров в секунду.

К сожалению, не похоже, что DirectX 9 поддерживает текстурные массивы. В нем есть что-то под названием Texture Volumes (тома текстур), но заметки о нем в API заставляют меня нервничать. Во-первых, когда он масштабирует объем текстуры (mip-mapping), он хочет масштабировать и третье измерение глубины. Это усреднит вместе мои различные текстуры для дерева, воды и т.д., и просто устроит беспорядок. Я также не уверен, что когда я рендерю треугольник, он не будет усреднять "близлежащие" текстуры, которые совершенно разные.

Я могу оставить код в покое, так как он достаточно быстр даже без массивов текстур. Я могу перейти на DirectX 10, который поддерживает текстурные массивы. Это лишит меня всех пользователей Windows XP. Или я могу перейти на OpenGL.

Обсуждая это с Флорианом, он приводит доводы в пользу того, что у меня будет больше пользователей с реализацией OpenGL даже под Windows, так как массивы текстур поддерживаются как расширение в более ранних версиях OpenGL. И у меня будут пользователи MacOS и Linux с OpenGL.

Я купил OpenGL SuperBible и начал её изучать. Я все еще думаю о том, стоит ли переходить. Я конвертирую демо в OpenGL и посмотрю, как все пройдет. Также хочу посмотреть, что можно сделать с шейдерами, чтобы еще больше ускорить процесс. Есть чему поучиться.

Уровни детализации

В предыдущих частях и в комментариях я упоминал о том, что с низкополигональными зданиями в стиле Minecraft будут проблемы. Рассмотрим рисунок 2. Если вы сократите разрешение пополам, вам нужно будет суммировать 8 кубов с 1 более грубым кубом. Для этого нужно выбрать цвет, который будет представлять 8 заменённых кубов. Это испортит внешний вид этих структур.

Рис. 2: Как вы уменьшите масштаб этого?

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

Могут быть и другие формы, которые нужно будет обновлять реже. Я пытался придумать, как построить блоки вокруг структуры, которые бы работали. Если вместо того, чтобы заменить 8 кубов на один, я заменил бы кусок 8х8х8 на большой куб, на котором было бы правильное изображение, нарисованное на поверхности, возможно, это сработало бы.

Читая документацию OpenGL, я прочитал описание различных примитивов, в том числе и "точечных спрайтов". Они используются для эффектов частиц в сцене и рисуются быстро. Некоторое время спустя мое подсознание предложило использовать их для обобщения зданий. Вместо того, чтобы рисовать кубы, я бы просто нарисовал точку нужного цвета. На расстоянии, это выглядело бы убедительно? Я быстро изменил демо-версию, чтобы выяснить это.

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

Рис. 3: Результат point-sprite LOD.

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