Тесселяция и дисплейсмент. Часть 2

В этот раз буду краток.

Сделано в Unigine, на Unigine Script. Видео с максимальными настройками в Direct3D 9. FPS был около 65-70 (см. первый кадр), но Fraps его убил. Дисплейсмент происходит программно, без собственных шейдеров, Vertex Texture Fetch и пр. Все алгоритмы и код - моя собственная разработка. В дальнейшем будем использовать эту технологию в наших проектах, а возможно и выпустим отдельную утилиту.
Дальше..

Тесселяция и дисплейсмент

Эта тема последнее время довольно популярна. Особенно в связи с выходом DirectX 11 и бенчмарком Unigine Heaven с его поддержкой.

Normal   Normal Wireframe   Displaced   Displaced Wireframe

Как ни странно, на этой картинке не DX 11 и пресловутая реалтайм тесселяция, а DirectX 9 и результат работы оффлайновой утилиты.

Пост обновлен 21.11.09

Утилиту я сделал под влиянием "глобального заговора" - моя 9600GT не поддерживает новомодную тесселяцию, а попытки сделать дисплейсмент в 3dsmax дают деформацию фигуры, море полигонов, и вообще не очень приятный результат.
При тесселяции полигон разбивается на тысячи мелких полигонов, а вершины деформируются по карте высот. Эту часть мы прекрасно можем сделать и без помощи GPU, но тысячи дополнительных полигонов не пойдут на пользу скорости. Задачу я попробовал решать в лоб - оптимизацией полигонов после дисплейсмента.

Сетка модели без оптимизации выглядит примерно так:

Карта высот 64х64, 4096 вершин, 8192 полигона 64x128, 8192 вершины, 16002 полигона. Невооруженным глазом заметно, что некоторые полигоны откровенно лишние. С учетом особенностей их расположения, есть широкое поле для оптимизаций.
Постараюсь не углубляться в технические детали. Сам процесс оптимизации в нашей утилите обьединяет соседние полигоны по разным критериям. Различные параметры позволяют задавать детализацию и устранять артефакты. Сама полученная сетка (см. начало поста) довольно далека от идеала - некоторые места слишком сложные, есть "висящие" вершины (примыкание вершины к грани треугольника) и пр. Важен другой факт - в модели двери 980 треугольников, это в 9 раз меньше, чем без оптимизации. Для максимального приблежения это вполне приемлимо, а на удаленных участках можно показывать плоскую текстуру. Моя видеокарта такую нагрузку просто не замечает.
Алгоритм оказалась очень требовательным к карте высот - чем "геометричнее" фигуры, тем меньше получается полигонов. Различные полутона, сглаживания, отверстия, градиенты - все это приводит к лишней полигональности.

Вручную нарисованная карта высот для оконной рамы дает на выходе 112 полигонов. Эту же фигуру в 3д пакете можно нарисовать с 74ю треугольниками. Возможно, если задаться целью или просто наплевать на правила, то можно и поменьше сделать. :) Важно другое - порядок чисел один и тот же, значит технология имеет право на жизнь.

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

Update: Вспомнил, что карта высот для двери имеет соотношение 1/2, т.е. размер 64х128, а не 64х64, а сетка полигонов будет 63х127х2, т.е. 16002 треугольника. После оптимизации - 980, т.е. в 16 раз меньше.

Update 2: Подкрутил некоторые гайки и избавился от полигонов с высотой 0. В самом деле - зачем они нужны, если можно считать дисплейсмент добавлением деталей к существующей модели. Результат - 812 треугольников при таком же внешнем виде. По сравнению с 16002 оригинальными это уже оптимизация в ~19,7 раз, да и сетка довольно хороша.


Update 3: Человек - изворотливое создание. 699 треугольников.


Дальше..

Неслучайные неслучайности

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

Работая в среде Mono для генерации случайных чисел RunServer использует System.Random - есть предпосылки считать, что он базируется на /dev/random, но под .Net и Windows используется другой подход - обращение к системной функции RtlGenRandom, известной также под именем SystemFunction036.
Данная функция должна была гарантировать равномерное распределение случайных чисел, отсутствие повторений, многопоточную безопасность. Практика показала, что это не совсем так, а время вызова функции сравнительно велико.
Как оказалось, проблема была не в самой функции, а в ее использовании: при каждом обращении к классу Utility.Random вызывалась функция с временным буфером 4 байта, в то время как функция рассчитана на генерацию страницы cлучайных чисел. Повторения при многопоточном использовании могут быть вызываны различными внутренними кешированиями.
Я думал было отказаться от этой функции, но решил дать функции еще один шанс - вместо вызова для буфера в 4 байта, я сделал генерацию случайного блока в несколько килобайт и его кеширование. Конечно же, при этом встал вопрос синхронизации: боступ к пулу чисел должен быть последовательным, но использовать блокировки при каждом запросе - не очень выгодно. Вопрос был решен с помощью Interlocked операций:

const int PoolLength = 1024;
static readonly int[] s_randomPool = new int[PoolLength];
static int s_poolPosition;

static int rand()
{
       int pos = Interlocked.Increment(ref s_poolPosition) % PoolLength;

       if (pos == 0)
               RtlGenRandom(s_randomPool, PoolLength * 4);

       return s_randomPool[pos];
}

В приведенном коде RtlGenRandom заполняет буфер в 4096 байт, который для удобства хранится как массив int []. Использование Interlocked.Increment гарантирует, что пул будет обновляться один раз в 1024 вызова и извлечение одного и того же числа два раза возможно лишь при 1024 конкурирующих потоках.
Возможна ситуация, когда в одном потоке пул еще обновляется, а в другом идет вызов rand(). Если пул уже был заполнен, то ничего страшного в этом нет - будет извлечено число из нового пула (если заполнение буфера идет последовательно), либо закешированное значение из старого пула. Если первое заполнение еще не произошло, то в муле будут нули, потому целесообразно в статическом конструкторе класса единожды вызывать rand(), чтобы заполнить пул до его использования.

За счет подобной оптимизации в сотни раз сократилось время вызова метода rand(), была обеспечена многопоточная безопасность и равномерность распределения случайных чисел. Возможно, есть и более быстрые реализации, например, комбинация Interlocked операций с математическими, но в случае с RtlGenRandom можно не опасаться частых повторений одного и того же числа, частичного диапазона и других болезней генераторов псевдослучайных чисел.

Update: Обнаружен гадкий баг. Странно, что никто из читателей не заметил. Мы увеличиваем 32-битный инт и когда он дойдет до максимума, начнутся отрицательные значения. Их остаток от деления тоже отрицателен и нам грозит обращение по неверному адресу. Самый простой способ - не остаток от деления использовать, а маску. Например так:

const intPoolLength = 0x400;
const intPoolMask = PoolLength - 1;
...

int pos = Interlocked.Increment(ref s_poolPosition) & PoolMask;

Дальше..

Оптимизация геометрии для 64-битной платформы

Сейчас мы работаем над библиотеками серверной обработки геометрии (нахождение пути, проверка видимости и пр.). В тестовом проекте проявилась интересная проблема: геометрия, особенно со вспомогательными данными, занимала много памяти на платформе х86 и очень много на х64. На первый взгляд все было спроектировано верно, но на диске данные занимали около 100МБ, а в памяти – больше гигабайта.
Геометрия описывается треугольниками, каждый треугольник содержит координаты трех вершин и некоторые вспомогательные данные (нормаль, коэффициенты для расчета пересечения и пр.). Треугольники каждой модели упорядочены в дерево, каждый лист дерева хранит набор треугольников, причем один и тот же треугольник может присутствовать в разных листьях.

Сначала система была прототипирована без различных оптимизаций. Затем было решено отказаться от хранения координат в треугольнике – создан общий пул вершин для каждой модели и в треугольниках хранились только ссылки. Вторым шагом мы сделали то же самое для листьев дерева – заменили треугольники ссылками на общий пул. Именно в этот момент и было замечено чрезмерное потребление памяти, особенно в x64 режиме.
В упрощенной модели можно сказать, что дерево представляло собой массив массивов указателей на треугольники, каждый из которых – массив из трех указателей на вершины. В С++ это упрощенно можно записать так:

typedef Vertex** Triangle;
typedef Triangle** Leaf;
typedef Leaf* Tree;

Запись

Tree m_tree;

эквивалентна

Vertex ***** m_tree;

Выглядит достаточно страшно :). Для визуальности можно воспользоваться STL и придуманным шаблоном stdext::triplet и написать так:

typedef stdext::triplet<Vertex*, Vertex*, Vertex*> Triangle;
typedef std::vector<Triangle*> Leaf;
typedef std::vector<Leaf> Tree;

Запись

Tree m_tree;

эквивалентна

std::vector<
    std::vector<
        stdext::triplet<Vertex*, Vertex*, Vertex*>* > >
           m_tree;

Конечно же, в реальной ситуации треугольник, лист и дерево – отдельные классы с различными свойствами и методами, но сейчас нам важна именно схема их вложенности, иерархия. Не трудно догадаться, что каждый указатель в архитектуре x86 занимает 4 байта, а в x64 – 8 байт. У нас же указателей вышло много, что и вылилось в существенное потребление памяти.
Для серверной геометрии нередко используются упрощенные модели – нет особой разницы, выделяется ли оконная рама для просчета пути NPC, количество полигонов ствола дерева почти не влияет на расчет линии видимости возле него. Это обуславливает небольшой размер моделей – редко когда модель имеет несколько тысяч вершин. Выходит, что для адресации вершин и треугольников можно было бы использовать 16-битовые индексы, в то время как мы используем на х64 системе 64-битовые указатели.

Дальнейшее развитие оптимизации достаточно предсказуемо – мы заменили наиболее используемые ссылки индексами unsigned short, что уменьшило потребляемую иерархией память в 2 раза на х86 системах и в 4 раза на архитектуре х64. Следующим шагом были созданы шаблонные классы, которые позволяют использовать любой тип в качестве индексов: в зависимости от сложности модели создается Tree либо Tree. Более сложные модели удобнее разбивать на части, чем хранить с 32-битными индексами. Более 50% моделей из нашего тестового проекта попали в категорию с 8-битными индексами. По сравнению с изначальным вариантом с указателями разница получилась огромная.

А теперь немного цифр:

8-bit: models 5140, leafs 157489, leaf references 899038, triangles 409962
16-bit: models 4376, leafs 2950551, leaf references 13938081, triangles 6774482

Это значит, что ранее у нас было 21553332 указателей на вершины и 14837119 указателей на треугольники, что в 64-битах означает 291123608 байт ~= 277 мегабайт данных.
После оптимизации получилось 1229886 8-битных индексов вершин, 20323446 16-битных, 899038 8-битных указателей на треугольники, 13938081 16-битных. В сумме это 70651978 байт ~= 67 мегабайт данных. Выигрыш более чем в 4 раза на 64-битной архитектуре.

Были и другие оптимизации, например, в дереве массив листьев был превращен в единый массив индексов треугольника с разделителем, но наибольшее значение имел именно отказ от указателей в пользу индексов.

Дальше..

КРИ 2009

В этом году мы ездили в Москву на КРИ 2009 показывать свой проект.
В прошлом году я уже был на этом мероприятии вместе с командой Syndicate Online и остался весьма доволен, потому расчитывал как минимум на радушный прием и благоприятную почву для сеяния семян RunServer.


Видимо, наши оценки влияния кризиса на игровую индустрию вцелом оказались не верны. Если говорить кратко, то некоторая польза от поездки была - проект показали, некоторое количество контактов наладили, раздали визитки, пообщались с коллегами. Ждали мы немного другого, но уж что есть, то есть.

Первый казус оказался с погодой - конец мая месяца выдался не просто холодным, а Очень холодным. Мы мёрзли в поеде, мёрзли в Москве, мёрзли в транспорте. При этом, на самой конференции вокруг "Ярмарки Проектов" были установлены довольно яркие лампы, от которых было откровенно жарко.

В первый день мы немного опоздали из-за заселения и пришли к обеду. Остальные проекты "Ярмарки" уже активно крутили видео и показывали демки, в то время как наш компьютер еще стоял в виде коробок под стендом в самом углу помещения. Особенно удивило расположение "Ярмарки" - небольшое помещение 5х15 метров, где приютилось 20 стендов по 2-3 участника от каждого. Было откровенно тесно. Долго удивляться времени не было, потому за пару минут техника была собрана и мы обнаружили, что там стоит Windows XP SP3 без последнего DirectX, без .Net Framework, кодеков видео и с проблемами обнаружения устройств (не определялась мышь, флешка и пр.).
Проблемы решились через некоторое время, но хорошего настроения вся эта ситуация не добавила.

Следующим ударом стала работа с интернетом. Для показа онлайн проекта он довольно полезен, но организаторы конференции этим вопросом озаботились очень условно, потому первый день мы подключались к Beeline EDGE/GPRS, который был просто удручающего качества.
На следующий день была приобретена карта Comstar WiFi, но у указанного провайдера в эти дни были проблемы с сервером авторизации, потому интернет работал лишь в третий день, когда был и не особо нужен. Кстати, качество и стабильность указанного Comstar также далеки от идеала.
Конечно же, эти небольшие неприятности не должны были составить особой проблемы, ведь у нас был с собой и локальный сервер, и несколько видеороликов, чего было бы достаточно для показа не привередливой публике. Проблема же заключалась в отсутствии этой публики: неизвестно, сколько было посетителей, но 95% ее составляли программисты с других стендов. Особого интереса "очередная фентези-онлайн РПГ" у них не вызывала и полноценное общение получалось лишь с теми, кому мы успевали рассказать, что показываем демо серверного движка. Как справедливо заметил один из собеседников, надо было повесить плакаты, графики, большими буквами написать "Мы - не просто игра", показывать в клиенте "бегающие пакеты", загрузку сервера и пр. Воспользуемся его советом в следующий раз, если соберемся снова посетить Москву.

Глобально конференция вышла очень бедной по сравнению с 2008м годом - в два раза меньше площадь, отсутствие толпы и зрителей, невзрачные Booth Babies. Большая часть проектов "Ярмарки" была онлайновыми, но интернет бывал редко и далеко не у всех. Инвесторов, да и просто желающих купить что-либо не было видно вообще. Что было на высоте, так это питание в ресторане "Калинка", но это наврядли заслуга организаторов :)




Напоследок - подборка из трех фотографий "эволюции" стенда 1C, выложенных тов grayraw:




Дальше..

Открытие сайта и анонс проекта MMT Online

Думаю, многим будет интересна причина малой активности в этом блоге за последние полгода. Как ни странно, заключается она не в потере интереса, а в активной работе над собственным игровым проектом.
Наш сайт был введен в действие несколько дней назад (http://runserver.net) и сегодня команда RunServer оффициально анонсирует проект MMT Online. Детальне читайте в новостях на сайте: http://runserver.net/ru/mmt/19-mmt-anounce


В двух словах расскажу, почему проект называется "демонстрационным".
Основная цель проекта - показать возможности нашей серверной платформы, да и нашей команды в целом. Это означает, что все усилия направлены на разработку одной-двух локаций и показ как можно большего количества серверных возможностей. Мы пока не планируем сотни континентов, различные расы, десятки подземелий и пр.
С другой стороны, наш гейм-дизайнер Ипполит придумал достаточно необычный мир (точнее два мира) и было бы интересно реализовать его идеи в будующем. Возможно, ситуация изменится, если будет найден инвестор.

Немного истории.
В гейм-деве мы достаточно давно (с 2004го года как минимум), но основным направлением была серверная часть, хотя и были эксперименты над клиентской (замороженный ныне проект Heroes Offline, различные аддоны к WoW, наработки на Ogre 3D и пр.). Не смотря на это, первый наш блин в 3D игростроении вышел, как водится, комом - проект на движке Unigine (http://unigine.com) стартовал в начале 2007го года, но через полгода был заморожен и закрыт. Сказался недостаток опыта и контента.
В конце 2007го года фирма МСМ Онлайн (дочерняя компания провайдера WNet) начала разработку проекта Syndicate Online (http://syndicate-online.com) c использованием платформы RunServer и понемногу начала снабжать нас 3д контентом. Это позволило осенью 2008го года начать разработку собственной игры. Движок взяли тот же - Unigine, но программную часть написали заново. Так и родился MMT Online. К предоставленному высококачественному контенту мы начали дорисовывать своими силами собственные поделия. Местами это смотрится хорошо, местами - убого :)
Надеюсь, участие в КРИ 2009 покажет, насколько мы продвинулись в нашей цели, и получилось ли привлечь внимание к RunServer и нашей команде.

Дальше..