Причина проста — в новых процессорах много ядер, но по факту они менее производительны в однопоточных приложениях. На тот момент, у меня был рендер в один поток. Но на самом деле причины была не столько в этом. И в процессе поиска проблемы, я решил посчитать сколько полигонов присутствует в сцене:
На средней игровой карте, при максимальном отдалении и при большом скоплении пальм — 15 824 756 треугольников! Почти 16 миллионов! Огромная цифра.
Немного поиграв с генератором карт, удалось найти место с 16,75 миллионами:
Хотя, вот, подобное место с елками давало всего 8,5 миллионов треугольников:
В среднем сцена состояла из ~ 4 миллионов:
В общем, я был рад, что мой рендер справляется с таким огромным числом треугольников, но их количество было чрезмерным. Решение было на поверхности:
- Оптимизировать количество полигонов в моделях.
- Оптимизировать полигональную сетку ландшафта.
- Реализация многопоточного рендера.
Тем, кому первый пункт нашей программы оптимизации может быть не интересен, например, матерым специалистам, рекомендую смело переходить ко второй части.
1. Оптимизация количества полигонов в моделях
В нашем движке растительность рисуется «паками», весь ландшафт разбит на тайлы и субтайлы, минимальный пак — один субтайл.
Один пак это один меш, так как уменьшение количества мешей ощутимо снижает кол-во вызовов CPU->GPU.
Изначально наши елки состояли из усеченных конусов, перейдя на полные конуса, удалось убрать пару лишних треугольников:
Вишенкой на торте стало решение убрать стволы у деревьев, так как при нашем ракурсе камеры они были просто не видны.
В итоге, у нас получилось сократить количество полигонов, на одном паке елок, в среднем на 40%. Отличий практически не видно:
С пальмами было сложнее, но паки по 5000 — 6000 полигонов необходимо было исправлять. Каким образом достичь массивности и плотности джунглей? Высокая плотность джунглей достигалась за счет большого количества пальм:
Решили упростить пальмы и ввести второй ярус растительности, что позволило сохранить видимую плотность и добиться искомых 600 — 700 полигонов на пак.
Сокращение количества полигонов в 10 раз — отличный результат.
2. Оптимизация полигональной сетки ландшафта
Изначально сетка ландшафта имела вид:
На скриншоте видны ровные участки ландшафта, это тайлы лугов, равнин, пусть и прочих ровных поверхностей. Небольшие неровности ландшафта решил убрать. Тем самым увеличил площади одинаковых по высоте тайлов. Не хитрой проверкой всех вершин тайлов и субтайлов на равенство по высоте, я смог добиться вот такого результата:
Оставались еще ровные места которые можно было оптимизировать, и я начал строить полигоны из тех треугольников у которых была одинаковая высота. Брался тайл и все его треугольники сортировались на массив неравных по высоте треугольников и на список массивов состоящий из равных по высоте и смежных треугольников.
В приведенном примере получалось: 1 массив треугольников не подлежащих изменению, так как они были все разной высоты (красные треугольники) и список состоящий из двух массивов треугольников с одинаковой высотой (массивы залиты цветом).
Теперь стояла задача найти из массива треугольников их выпукло-вогнутый контур (Concave Hull), при чем множество треугольников могло иметь дырки. Ранее я сталкивался в своей работе с выпуклыми контурами (Convex Hull), проблем с ними не было, я уже использовал алгоритм Грэхема (Graham scan). А вот с построением Concave Hull появились проблемы... Информации на эту тему найти в интернете оказалось достаточно сложно. Пришлось писать реализацию алгоритмов с нуля. Не совру, если скажу, что прочитал с десяток разных диссертаций на эту тему. Но все предложенные алгоритмы давали приближенный результат с некоторой погрешностью. После недели мучений и боли мне пришла идея своего алгоритма.
Я пытался построить контур по множеству вершин треугольников, т.е. массив треугольников я переводил в массив вершин и уже по ним строил оболочку. Но для моей задачи этого не требовалось. Согласно моим умозаключениям построить оболочку непосредственно по треугольникам было проще, и точность concave hull’а получалась 100%.
Изначально я хотел выложить сюда портянку исходного кода алгоритма, но проще как мне кажется, его описать в двух словах: Основа — правило: если вершина треугольника входит в четыре и менее треугольников, то одно из ребер которое образует вершина лежит на границе. Далее формируется список таких ребер с учетом удаления одинаковых ребер. Находим ребро с наименьшим Х и У и от него начинаем проход/сортировку ребер с попутным добавлением уникальных вершин в список. Этот список и будет являться оболочкой множества треугольников. Единственное, в финале, необходимо из полученного списка удалить коллинеарные точки.
В результате этого я мог строить Concave Hull практически любой сложности. Данный алгоритм не подходил к множеству с дырками, но я обошел это путем, простого разделения этого множества на две половины по дырке. Далее получал контур и триангулировал его:
Получилось все отлично:
Но, в итоге, я был расстроен полученным результатом. Разработанный мной алгоритм давал ощутимую прибавку в производительности при отрисовке сцены, так как количество полигонов в среднем сокращалось на 60 — 70%. Но при этом генерация карты стала происходить раз в 10 медленнее. Алгоритм оказался весьма требовательным к затратам по времени.
Три дня ушло на обдумывание облегченной версии алгоритма оптимизации полигональной сетки ландшафта, который давал вот такие результаты:
Сейчас вычисления данных для оптимизации стали не заметны на фоне генерации карты, а количество полигонов снизилось в среднем на 40-50%.
Данная статья пробная и несет поверхностный характер. Если кому будет интересна тема разработки игры, я готов продолжать и расширять статью с привидением конкретных шагов, решений и дальнейших планов. Также, думаю, вам будет интересна тема построения многопоточного Open GL приложения разработанного на Java, о котором постараюсь рассказать в следующей статье.
Комментарии (33)
Watcover3396
14.01.2019 16:15Интересно, продолжайте =)
Инстансы статических мешей еще нет?
Мне кажется странным, вроде ничего особенного из графики нет и фпса нет, большие движки большое количество трисов спокойно переваривают, может и у Вас проблема в чем-то другом?
Zemlaynin
14.01.2019 17:44Еще много чего интересного не реализовано. Сейчас больше сосредоточен на реализации геймплейных механик. Работа над оптимизацией вывода графики вынужденное отвлечение от центральной задачи, но постепенно приходится реализовывать и докручивать некоторые функции. Проект пишется на Java, что накладывает некоторые ограничения. 4 миллиона трисов при 60 FPS это неплохой результат на gtx 660. Или может вы заметили на скрине с пальмами 30 FPS? Это экспериментирую с синхронизацией и ограничил планку в 30 FPS.
KsiOwn1t
14.01.2019 16:20и правда хорошо, спасибо, уяснил некую информацию для себя, а то оптимизация дело тонкое...=)
Zemlaynin
14.01.2019 18:00Какой момент был интересен?
KsiOwn1t
14.01.2019 18:16вообще конечно всё) ибо я еще зелен и молод, тем более пытаюсь что то сделать на юнити, но в целом информация про полигональную сетку ландшафта, мне тут под ухо объясняют похожее + ваш материал, дает материал в голове, который я понимать начинаю но выразить не могу, как то так хДд Спасибо в общем) буду следить за новостями
iOrange
14.01.2019 17:35Если я правильно понял — то затык был на CPU стороне, а не GPU?
В таком случае, надо уменьшать количество дроуколлов. Я так полагаю, вы не используете инстансинг? Судя по скринам — у вас много однотипных мешей, самое оно для инстансинга. Заставьте GPU этим заниматься.Zemlaynin
14.01.2019 17:59Да, узким местом был CPU. Инстансинг не использую, есть небольшие проблемы с определением однотипности объектов и их хранением для сцены, конечно это решаемая задача, но честно не хватает рук на решение всех задач.
iOrange
14.01.2019 19:02но честно не хватает рук на решение всех задач.
Понимаю, но это сильно поможет вам в long-term.
Еще пару вопросов:
1) LOD-ирование работает надеюсь?
2) На скринах, с такого расстояния, я бы уже переключал на imposters. Или я просто не замелил и это уже реализовано?Zemlaynin
15.01.2019 04:09Полностью согласен, задача по инстансингу стоит в таск листе, возможно стоит её подвинуть на более ранний этап разработки.
1. Геометрия у нас упрощена до минимума, и малейшее её упрощение приводит к видимым искажениям, даже с такого расстояния. Тут играет роль ракурс камеры.
2. Нет, не реализовано. Поясню. В билде не будет отдаления камеры на такое расстояние. При отдалении камеры, в определенный момент, будет происходить переключение на стратегическую 2D карту.
Tar
14.01.2019 19:13+1Используете ли triangle strips? Хотя с оптимизированной сеткой это нетривиальная задача.
И вот в этих местах нет «дырок»? Там по сути разрыв в топологии. Может «дребезжать» на больших расстояниях.
iOrange
14.01.2019 19:39Может «дребезжать» на больших расстояниях.
Кстати, да. В таких местах рекомендуется «сшивать» вершины.Leopotam
14.01.2019 21:11Обычно не заморачиваются, а делают юбки — просто копируют крайние ребра и опускают вниз с копией uv — получается затыкание потенциальных дыр с относительно простой реализацией.
iOrange
14.01.2019 22:18Будет плохо работать с динамическим лодированием. Но как простой вариант — да, сработает.
Zemlaynin
15.01.2019 04:21В том то и дело, задача не тривиальна, так что пришлось отказаться от triangle strips.
Но такие места обходятся путем:
Все эти вертексы лежат на одной линии. А выделенные трисы как раз служат неким переходом, дабы нивелировать подобные разрывы.
AngReload
15.01.2019 12:26Мне кажется что сравнимый можно получить построив квадродерево.
Zemlaynin Автор
15.01.2019 12:44Мысль проскальзывала о Q-деревьях, но есть одна заминка, у меня у каждого тайла 9 внутренних узлов — субтайлов. Что усложняет реализацию, и эту мысль я откинул.
MaximSuvorov
16.01.2019 14:31Запекать готовую карту для большого отдаления в текстуру — это сейчас дешево и производительно.
vovkasolovev
15.01.2019 06:49В Fortnite используют очень эффектный и эффективный метод оптимизации для повторяющейся природы: менять такие модели на хитрый набор спрайтов.
www.shaderbits.com/blog/octahedral-impostors
Третий пример:
Deosis
15.01.2019 08:14Недавно была статья как из 2 полигонов, 3 текстур и шейдера собрать ворсистый ковер.
Karpion
15.01.2019 17:19На средней игровой карте, при максимальном отдалении и при большом скоплении пальм
Вот тут скрыта возможность оптимизации, которую Вы, кажется упустили. Дело в том, что на большом удалении многие элементы объекта становятся меньше одного пикселя, так что нет никакого смысла подробно анализировать и отрисовывать.
Следовательно, для каждого объекта надо иметь несколько векторных моделей — для разных расстояний. Дальше, кажется, очевидно — но могу разобрать подробно.
Далее: при отрисовке объектов есть несколько разных алгоритмов определения видимости объекта (и отдельно каждой его части). В некоторых алгоритмах можно применить такую оптимизацию:
Вся сцена (все имеющиеся объекты) выстраивается в иерархию. Например, допустим, у нас есть несколько людей в пустоте. Тогда:- сцена = человек1 + человек2 + ...
- человек = туловище + голова + две руки + две ноги
- рука = плечо + предплечье + кисть (этот уровень разбиения можно совместить с вышележащим — т.е. рука не будет присутствовать в иерархии, а кисть будет сразу частью человека)
- кисть = ладонь + пальцы
Если обнимающий шар объекта не попадает в экран — его рисовать вообще не нужно. Т.е. можно выбросить сразу много заведомо ненужной работы.
Если обнимающие шары двух объектов при проецировании на экран не пересеклись — то эти два объекта никак не перекрывают друг-друга; так что незачем искать пересечения треугольников.
При использовании «лучей зрения»: если луч зрения не попал в обнимающий шар, то он не попадёт ни в какой элемент (треугольник) объекта.
Mingun
15.01.2019 17:41Сразу замечу, что любое слагаемое всегда является частью суммы; однако, обнимающий шар слагаемого может выходить за пределы обнимающего шара суммы.
…
Если обнимающий шар объекта не попадает в экран — его рисовать вообще не нужно.
…
Если обнимающие шары двух объектов при проецировании на экран не пересеклись — то эти два объекта никак не перекрывают друг-другаЯ один вижу здесь противоречие?
Zemlaynin Автор
16.01.2019 03:47Следовательно, для каждого объекта надо иметь несколько векторных моделей — для разных расстояний. Дальше, кажется, очевидно — но могу разобрать подробно.
Ну так это и есть LOD-ирование, о котором мы говорили чуть выше в комментариях.
Если обнимающий шар объекта не попадает в экран — его рисовать вообще не нужно. Т.е. можно выбросить сразу много заведомо ненужной работы.
У меня это работает по другому принципу, так как у меня все объекты находятся в тайлах, определение их видимости простая задача.
MaximSuvorov
16.01.2019 14:30А почему не пирамидой лодов? При максимальном удалении большинство деталей ландшафта просто не видны особо и их можно «упрощать»
Zemlaynin Автор
17.01.2019 08:59Вот куда еще упрощать эту пальму?
MaximSuvorov
17.01.2019 10:14Это не последний лод, можно ещё дальше собирая пачки пальмы в билдборды:
i.imgur.com/ss5CB1A.jpg
То есть простой треугольник/квад с запечённым изоражением вашей пальмы. С применением нормал-мапы смотрится вдалеке вполне сносно.
Ну и группы пальм рендерить всегда дешевле чем поштучно из-за DrawCall bottleneckZemlaynin Автор
17.01.2019 10:33Так у меня и так рендерятся паки пальм, а не отдельные пальмы.
Идея с импостером понятна и на поверхности, но повторюсь, что не будет такого отдаления в игре, да не приходит на ум, как это реализовать с динамическим освещением.
APXEOLOG
Действительно интересно. Я так понимаю графический движок у вас самописный?
Zemlaynin
Да, движок самописный.