[] Оптимизация графики. Интересный Concave Hull

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

Причина проста — в новых процессорах много ядер, но по факту они менее производительны в однопоточных приложениях. На тот момент, у меня был рендер в один поток. Но на самом деле причины была не столько в этом. И в процессе поиска проблемы, я решил посчитать сколько полигонов присутствует в сцене:

На средней игровой карте, при максимальном отдалении и при большом скоплении пальм — 15 824 756 треугольников! Почти 16 миллионов! Огромная цифра.

Немного поиграв с генератором карт, удалось найти место с 16,75 миллионами:

Хотя, вот, подобное место с елками давало всего 8,5 миллионов треугольников:

В среднем сцена состояла из ~ 4 миллионов:

В общем, я был рад, что мой рендер справляется с таким огромным числом треугольников, но их количество было чрезмерным. Решение было на поверхности:

1. Оптимизировать количество полигонов в моделях.
2. Оптимизировать полигональную сетку ландшафта.
3. Реализация многопоточного рендера.

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

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, о котором постараюсь рассказать в следующей статье.

Автор: Юрий Ладик

Источник