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

Автор: admin от 14-01-2019, 14:55, посмотрело: 19

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



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



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



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



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



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



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



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



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



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



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




  • Оптимизировать количество полигонов в моделях.

  • Оптимизировать полигональную сетку ландшафта.

  • Реализация многопоточного рендера.



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



    1. Оптимизация количества полигонов в моделях



    В нашем движке растительность рисуется «паками», весь ландшафт разбит на тайлы и субтайлы, минимальный пак — один субтайл.



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



    Один пак это один меш, так как уменьшение количества мешей ощутимо снижает кол-во вызовов CPUGPU.



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



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



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



    Вишенкой на торте стало решение убрать стволы у деревьев, так как при нашем ракурсе камеры они были просто не видны.



    В итоге, у нас получилось сократить количество полигонов, на одном паке елок, в среднем на 40%. Отличий практически не видно:



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



    С пальмами было сложнее, но паки по 5000 — 6000 полигонов необходимо было исправлять. Каким образом достичь массивности и плотности джунглей? Высокая плотность джунглей достигалась за счет большого количества пальм:



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



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



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



    Сокращение количества полигонов в 10 раз — отличный результат.



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



    2. Оптимизация полигональной сетки ландшафта





    Изначально сетка ландшафта имела вид:



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



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



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



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



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



    В приведенном примере получалось: 1 массив треугольников не подлежащих изменению, так как они были все разной высоты (красные треугольники) и список состоящий из двух массивов треугольников с одинаковой высотой (массивы залиты цветом).



    Теперь стояла задача найти из массива треугольников их выпукло-вогнутый контур (Concave Hull), при чем множество треугольников могло иметь дырки. Ранее я сталкивался в своей работе с выпуклыми контурами (Convex Hull), проблем с ними не было, я уже использовал алгоритм  Грэхема (Graham scan). А вот с построением  Concave Hull появились проблемы...  Информации на эту тему найти в интернете оказалось достаточно сложно. Пришлось писать реализацию алгоритмов с нуля. Не совру, если скажу, что прочитал с десяток разных диссертаций на эту тему. Но все предложенные алгоритмы давали приближенный результат с некоторой погрешностью. После недели мучений и боли мне пришла идея своего алгоритма.



    Я пытался построить контур по множеству вершин треугольников, т.е. массив треугольников я переводил в массив вершин и уже по ним строил оболочку. Но для моей задачи этого не требовалось. Согласно моим умозаключениям построить оболочку непосредственно по треугольникам было проще, и точность concave hull’а получалась 100%.



    Изначально я хотел выложить сюда портянку исходного кода алгоритма, но проще как мне кажется, его описать в двух словах: Основа — правило: если вершина треугольника входит в четыре и менее треугольников, то одно из ребер которое образует вершина лежит на границе. Далее формируется список таких ребер с учетом удаления одинаковых ребер. Находим ребро с наименьшим Х и У и от него начинаем проход/сортировку ребер с попутным добавлением уникальных вершин в список. Этот список и будет являться оболочкой множества треугольников. Единственное, в финале, необходимо из полученного списка удалить коллинеарные точки.



    В результате этого я мог строить Concave Hull практически любой сложности. Данный алгоритм не подходил к множеству с дырками, но я обошел это путем, простого разделения этого множества на две половины по дырке. Далее получал контур и триангулировал его:



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



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



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



    Получилось все отлично:



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



    Но, в итоге, я был расстроен полученным результатом. Разработанный мной алгоритм давал ощутимую прибавку в производительности при отрисовке сцены, так как количество полигонов в среднем сокращалось на 60 — 70%. Но при этом генерация карты стала происходить раз в 10 медленнее. Алгоритм оказался весьма требовательным к затратам по времени.



    Три дня ушло на обдумывание облегченной версии алгоритма оптимизации полигональной сетки ландшафта, который давал вот такие результаты:



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



    Сейчас вычисления данных для оптимизации стали не заметны на фоне генерации карты, а количество полигонов снизилось в среднем на 40-50%.



    Данная статья пробная и несет поверхностный характер. Если кому будет интересна тема разработки игры, я готов продолжать и расширять статью с привидением конкретных шагов, решений и дальнейших планов. Также, думаю, вам будет интересна тема построения многопоточного Open GL приложения разработанного на Java, о котором постараюсь рассказать в следующей статье.

    Источник: Хабр / Интересные публикации

    Категория: Веб-разработка

    Уважаемый посетитель, Вы зашли на сайт как незарегистрированный пользователь.
    Мы рекомендуем Вам зарегистрироваться либо войти на сайт под своим именем.

    Добавление комментария

    Имя:*
    E-Mail:
    Комментарий:
    Полужирный Наклонный текст Подчеркнутый текст Зачеркнутый текст | Выравнивание по левому краю По центру Выравнивание по правому краю | Вставка смайликов Выбор цвета | Скрытый текст Вставка цитаты Преобразовать выбранный текст из транслитерации в кириллицу Вставка спойлера
    Введите два слова, показанных на изображении: *