Оптимизация графики. Интересный 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, о котором постараюсь рассказать в следующей статье.
Поделиться публикацией

Комментарии 34

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

    Действительно интересно. Я так понимаю графический движок у вас самописный?

      0
      Да, движок самописный.
      0
      Интересно, продолжайте =)
      Инстансы статических мешей еще нет?
      Мне кажется странным, вроде ничего особенного из графики нет и фпса нет, большие движки большое количество трисов спокойно переваривают, может и у Вас проблема в чем-то другом?
        0
        Еще много чего интересного не реализовано. Сейчас больше сосредоточен на реализации геймплейных механик. Работа над оптимизацией вывода графики вынужденное отвлечение от центральной задачи, но постепенно приходится реализовывать и докручивать некоторые функции. Проект пишется на Java, что накладывает некоторые ограничения. 4 миллиона трисов при 60 FPS это неплохой результат на gtx 660. Или может вы заметили на скрине с пальмами 30 FPS? Это экспериментирую с синхронизацией и ограничил планку в 30 FPS.
        0
        и правда хорошо, спасибо, уяснил некую информацию для себя, а то оптимизация дело тонкое...=)
          0
          Какой момент был интересен?
            0
            вообще конечно всё) ибо я еще зелен и молод, тем более пытаюсь что то сделать на юнити, но в целом информация про полигональную сетку ландшафта, мне тут под ухо объясняют похожее + ваш материал, дает материал в голове, который я понимать начинаю но выразить не могу, как то так хДд Спасибо в общем) буду следить за новостями
              0
              Рад что информация оказалась полезной ;)
          0
          Если я правильно понял — то затык был на CPU стороне, а не GPU?
          В таком случае, надо уменьшать количество дроуколлов. Я так полагаю, вы не используете инстансинг? Судя по скринам — у вас много однотипных мешей, самое оно для инстансинга. Заставьте GPU этим заниматься.
            0
            Да, узким местом был CPU. Инстансинг не использую, есть небольшие проблемы с определением однотипности объектов и их хранением для сцены, конечно это решаемая задача, но честно не хватает рук на решение всех задач.
              0
              но честно не хватает рук на решение всех задач.

              Понимаю, но это сильно поможет вам в long-term.

              Еще пару вопросов:
              1) LOD-ирование работает надеюсь?
              2) На скринах, с такого расстояния, я бы уже переключал на imposters. Или я просто не замелил и это уже реализовано?
                0
                Полностью согласен, задача по инстансингу стоит в таск листе, возможно стоит её подвинуть на более ранний этап разработки.
                1. Геометрия у нас упрощена до минимума, и малейшее её упрощение приводит к видимым искажениям, даже с такого расстояния. Тут играет роль ракурс камеры.
                2. Нет, не реализовано. Поясню. В билде не будет отдаления камеры на такое расстояние. При отдалении камеры, в определенный момент, будет происходить переключение на стратегическую 2D карту.
            +1
            Используете ли triangle strips? Хотя с оптимизированной сеткой это нетривиальная задача.
            И вот в этих местах нет «дырок»? Там по сути разрыв в топологии. Может «дребезжать» на больших расстояниях.
              0
              Может «дребезжать» на больших расстояниях.

              Кстати, да. В таких местах рекомендуется «сшивать» вершины.
                0
                Обычно не заморачиваются, а делают юбки — просто копируют крайние ребра и опускают вниз с копией uv — получается затыкание потенциальных дыр с относительно простой реализацией.
                  0
                  Будет плохо работать с динамическим лодированием. Но как простой вариант — да, сработает.
                0
                В том то и дело, задача не тривиальна, так что пришлось отказаться от triangle strips.
                Но такие места обходятся путем:
                image
                Все эти вертексы лежат на одной линии. А выделенные трисы как раз служат неким переходом, дабы нивелировать подобные разрывы.
                  0

                  Мне кажется что сравнимый можно получить построив квадродерево.

                    0
                    Мысль проскальзывала о Q-деревьях, но есть одна заминка, у меня у каждого тайла 9 внутренних узлов — субтайлов. Что усложняет реализацию, и эту мысль я откинул.
                      0
                      Запекать готовую карту для большого отдаления в текстуру — это сейчас дешево и производительно.
                0
                Как боретесь с GC? Бывают микрофризы?
                  0
                  На огромных картах такие проблемы были при перерасчете видимых тайлов, но при вынесение таких вычислений в отдельный поток удается избегать видимых фризов.
                  +3
                  В Fortnite используют очень эффектный и эффективный метод оптимизации для повторяющейся природы: менять такие модели на хитрый набор спрайтов.
                  www.shaderbits.com/blog/octahedral-impostors

                  Третий пример:
                    +1

                    Недавно была статья как из 2 полигонов, 3 текстур и шейдера собрать ворсистый ковер.

                    0
                    Спасибо за ссылку, интересный подход.
                      0
                      На средней игровой карте, при максимальном отдалении и при большом скоплении пальм
                      Вот тут скрыта возможность оптимизации, которую Вы, кажется упустили. Дело в том, что на большом удалении многие элементы объекта становятся меньше одного пикселя, так что нет никакого смысла подробно анализировать и отрисовывать.
                      Следовательно, для каждого объекта надо иметь несколько векторных моделей — для разных расстояний. Дальше, кажется, очевидно — но могу разобрать подробно.

                      Далее: при отрисовке объектов есть несколько разных алгоритмов определения видимости объекта (и отдельно каждой его части). В некоторых алгоритмах можно применить такую оптимизацию:
                      Вся сцена (все имеющиеся объекты) выстраивается в иерархию. Например, допустим, у нас есть несколько людей в пустоте. Тогда:
                      • сцена = человек1 + человек2 + ...
                      • человек = туловище + голова + две руки + две ноги
                      • рука = плечо + предплечье + кисть (этот уровень разбиения можно совместить с вышележащим — т.е. рука не будет присутствовать в иерархии, а кисть будет сразу частью человека)
                      • кисть = ладонь + пальцы
                      Для кажого объекта в иерархии строим «обнимающий шар» (или другую фигуру) — минимальный шар, такой, что весь объект находится внутри него. Сразу замечу, что любое слагаемое всегда является частью суммы; однако, обнимающий шар слагаемого может выходить за пределы обнимающего шара суммы.
                      Если обнимающий шар объекта не попадает в экран — его рисовать вообще не нужно. Т.е. можно выбросить сразу много заведомо ненужной работы.
                      Если обнимающие шары двух объектов при проецировании на экран не пересеклись — то эти два объекта никак не перекрывают друг-друга; так что незачем искать пересечения треугольников.
                      При использовании «лучей зрения»: если луч зрения не попал в обнимающий шар, то он не попадёт ни в какой элемент (треугольник) объекта.
                        0
                        Сразу замечу, что любое слагаемое всегда является частью суммы; однако, обнимающий шар слагаемого может выходить за пределы обнимающего шара суммы.

                        Если обнимающий шар объекта не попадает в экран — его рисовать вообще не нужно.

                        Если обнимающие шары двух объектов при проецировании на экран не пересеклись — то эти два объекта никак не перекрывают друг-друга

                        Я один вижу здесь противоречие?

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

                          Ну так это и есть LOD-ирование, о котором мы говорили чуть выше в комментариях.

                          Если обнимающий шар объекта не попадает в экран — его рисовать вообще не нужно. Т.е. можно выбросить сразу много заведомо ненужной работы.

                          У меня это работает по другому принципу, так как у меня все объекты находятся в тайлах, определение их видимости простая задача.
                          0
                          А почему не пирамидой лодов? При максимальном удалении большинство деталей ландшафта просто не видны особо и их можно «упрощать»
                            0
                            Вот куда еще упрощать эту пальму?
                              0
                              Это не последний лод, можно ещё дальше собирая пачки пальмы в билдборды:

                              i.imgur.com/ss5CB1A.jpg

                              То есть простой треугольник/квад с запечённым изоражением вашей пальмы. С применением нормал-мапы смотрится вдалеке вполне сносно.

                              Ну и группы пальм рендерить всегда дешевле чем поштучно из-за DrawCall bottleneck
                                0
                                Так у меня и так рендерятся паки пальм, а не отдельные пальмы.
                                Идея с импостером понятна и на поверхности, но повторюсь, что не будет такого отдаления в игре, да не приходит на ум, как это реализовать с динамическим освещением.
                                  0
                                  да не приходит на ум, как это реализовать с динамическим освещением.

                                  Нормалмапу пеките для импостера, и будет вам рил-тайм освещение.

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

                          Самое читаемое