В один прекрасный момент, в ходе разработки игры, я столкнулся с вопросом производительности на современных ПК. У нашего моделлера достаточно мощный современный компьютер красной сборки. Но у него наш проект жутко тормозил, загружая одно ядро процессора.
Причина проста — в новых процессорах много ядер, но по факту они менее производительны в однопоточных приложениях. На тот момент, у меня был рендер в один поток. Но на самом деле причины была не столько в этом. И в процессе поиска проблемы, я решил посчитать сколько полигонов присутствует в сцене:
На средней игровой карте, при максимальном отдалении и при большом скоплении пальм — 15 824 756 треугольников! Почти 16 миллионов! Огромная цифра.
Немного поиграв с генератором карт, удалось найти место с 16,75 миллионами:
Хотя, вот, подобное место с елками давало всего 8,5 миллионов треугольников:
В среднем сцена состояла из ~ 4 миллионов:
В общем, я был рад, что мой рендер справляется с таким огромным числом треугольников, но их количество было чрезмерным. Решение было на поверхности:
Тем, кому первый пункт нашей программы оптимизации может быть не интересен, например, матерым специалистам, рекомендую смело переходить ко второй части.
В нашем движке растительность рисуется «паками», весь ландшафт разбит на тайлы и субтайлы, минимальный пак — один субтайл.
Один пак это один меш, так как уменьшение количества мешей ощутимо снижает кол-во вызовов CPU->GPU.
Изначально наши елки состояли из усеченных конусов, перейдя на полные конуса, удалось убрать пару лишних треугольников:
Вишенкой на торте стало решение убрать стволы у деревьев, так как при нашем ракурсе камеры они были просто не видны.
В итоге, у нас получилось сократить количество полигонов, на одном паке елок, в среднем на 40%. Отличий практически не видно:
С пальмами было сложнее, но паки по 5000 — 6000 полигонов необходимо было исправлять. Каким образом достичь массивности и плотности джунглей? Высокая плотность джунглей достигалась за счет большого количества пальм:
Решили упростить пальмы и ввести второй ярус растительности, что позволило сохранить видимую плотность и добиться искомых 600 — 700 полигонов на пак.
Сокращение количества полигонов в 10 раз — отличный результат.
Изначально сетка ландшафта имела вид:
На скриншоте видны ровные участки ландшафта, это тайлы лугов, равнин, пусть и прочих ровных поверхностей. Небольшие неровности ландшафта решил убрать. Тем самым увеличил площади одинаковых по высоте тайлов. Не хитрой проверкой всех вершин тайлов и субтайлов на равенство по высоте, я смог добиться вот такого результата:
Оставались еще ровные места которые можно было оптимизировать, и я начал строить полигоны из тех треугольников у которых была одинаковая высота. Брался тайл и все его треугольники сортировались на массив неравных по высоте треугольников и на список массивов состоящий из равных по высоте и смежных треугольников.
В приведенном примере получалось: 1 массив треугольников не подлежащих изменению, так как они были все разной высоты (красные треугольники) и список состоящий из двух массивов треугольников с одинаковой высотой (массивы залиты цветом).
Теперь стояла задача найти из массива треугольников их выпукло-вогнутый контур (Concave Hull), при чем множество треугольников могло иметь дырки. Ранее я сталкивался в своей работе с выпуклыми контурами (Convex Hull), проблем с ними не было, я уже использовал алгоритм Грэхема (Graham scan). А вот с построением Concave Hull появились проблемы... Информации на эту тему найти в интернете оказалось достаточно сложно. Пришлось писать реализацию алгоритмов с нуля. Не совру, если скажу, что прочитал с десяток разных диссертаций на эту тему. Но все предложенные алгоритмы давали приближенный результат с некоторой погрешностью. После недели мучений и боли мне пришла идея своего алгоритма.
Я пытался построить контур по множеству вершин треугольников, т.е. массив треугольников я переводил в массив вершин и уже по ним строил оболочку. Но для моей задачи этого не требовалось. Согласно моим умозаключениям построить оболочку непосредственно по треугольникам было проще, и точность concave hull’а получалась 100%.
Изначально я хотел выложить сюда портянку исходного кода алгоритма, но проще как мне кажется, его описать в двух словах: Основа — правило: если вершина треугольника входит в четыре и менее треугольников, то одно из ребер которое образует вершина лежит на границе. Далее формируется список таких ребер с учетом удаления одинаковых ребер. Находим ребро с наименьшим Х и У и от него начинаем проход/сортировку ребер с попутным добавлением уникальных вершин в список. Этот список и будет являться оболочкой множества треугольников. Единственное, в финале, необходимо из полученного списка удалить коллинеарные точки.
В результате этого я мог строить Concave Hull практически любой сложности. Данный алгоритм не подходил к множеству с дырками, но я обошел это путем, простого разделения этого множества на две половины по дырке. Далее получал контур и триангулировал его:
Получилось все отлично:
Но, в итоге, я был расстроен полученным результатом. Разработанный мной алгоритм давал ощутимую прибавку в производительности при отрисовке сцены, так как количество полигонов в среднем сокращалось на 60 — 70%. Но при этом генерация карты стала происходить раз в 10 медленнее. Алгоритм оказался весьма требовательным к затратам по времени.
Три дня ушло на обдумывание облегченной версии алгоритма оптимизации полигональной сетки ландшафта, который давал вот такие результаты:
Сейчас вычисления данных для оптимизации стали не заметны на фоне генерации карты, а количество полигонов снизилось в среднем на 40-50%.
Данная статья пробная и несет поверхностный характер. Если кому будет интересна тема разработки игры, я готов продолжать и расширять статью с привидением конкретных шагов, решений и дальнейших планов. Также, думаю, вам будет интересна тема построения многопоточного Open GL приложения разработанного на Java, о котором постараюсь рассказать в следующей статье.
Причина проста — в новых процессорах много ядер, но по факту они менее производительны в однопоточных приложениях. На тот момент, у меня был рендер в один поток. Но на самом деле причины была не столько в этом. И в процессе поиска проблемы, я решил посчитать сколько полигонов присутствует в сцене:
На средней игровой карте, при максимальном отдалении и при большом скоплении пальм — 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, о котором постараюсь рассказать в следующей статье.