Как оптимизировать игру с помощью полигональных атласов

Как всем известно, жизнь разработчика мобильных игр непроста. Он должен найти свой путь на очень узкой дорожке. С одной ее стороны — требования гейм-дизайнеров, уверенно устремляющиеся к бесконечности. Больше функционала, больше красивой графики, больше эффектов, больше анимаций, больше звуков. А с другой стороны — ограниченные ресурсы мобильного устройства. И раньше всего, как правило, заканчивается оперативная память.

Например, iPad 2 — всего в нем 512 Мб RAM. Однако приложению доступно только примерно 275 Мб. Когда занимаемая приложением память будет приближаться к этой границе, операционная система пришлет так называемое «Memory warning» — мягко, но настойчиво предложит освободить память. И если лимит все же будет превышен, операционная система остановит приложение. Пользователь будет думать, что ваша игра упала и побежит писать гневное письмо в саппорт.

fc7c0587893685cb83be74203b8135da.png

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

Текстуры и атласы


Как всем опять же известно, рисовать текстуры напрямую из исходных файлов — плохая идея. Вместо этого их упаковывают в текстурные атласы.

Текстурный атлас — это большое изображение, полученное склеиванием маленьких текстур. Тем самым экономится память и, что еще более важно, уменьшается количество батчей при отрисовке. Есть два видео, наглядно демонстрирующих почему атлас — это хорошо, а отдельные текстуры — это плохо: раз и два. Таким образом, задача упаковки текстурного атласа обычно сводится к следующему: взять прямоугольники разных размеров (исходные текстуры) и максимально плотно уложить их в один большой прямоугольник, или, чаще, квадрат. Мы не на олимпиаде и идеальная упаковка нам не нужна, а написать алгоритм, плотно упаковывающий текстуры за разумное время, совсем не сложно. Мы довольно давно пользуемся таким алгоритмом, который генерирует нам текстурные атласы. Примерно такие:

89b59b380d53cf6e8668ef8fae650a77.png

Как легко заметить, в нем довольно много свободного места и прямо-таки хочется упаковать текстуры поплотнее. Причина неэффективной упаковки в том, что многие текстуры содержат довольно большие прозрачные области. Поэтому однажды мы решили попробовать отказаться от обычной прямоугольной упаковки и сделать то, что в итоге получило название «полигональный атлас». Для этого нужно решить 2 задачи:

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

2. Получившиеся фигуры сложной формы (те самые полигоны) нужно как можно плотнее упаковать в атлас. Здесь был использован один из вариантов алгоритма пчелиного роя, который, проводя многочисленные попытки с использованием генератора случайных чисел, пытался найти достаточно плотный вариант упаковки. Здесь потребовался компромисс другого рода — между качеством упаковки и затрачиваемым на упаковку временем.

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

45a2a5002be0c1ae3d66ff35fe364b49.png

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

146d42d2fc7ae97beacf98e4ffba9d1e.png

Помимо самого атласа, генерируется его описание, в котором указаны имена исходных текстур и координаты получившихся треугольников.

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

Есть еще одна проблема, с которой мы столкнулись при переходе на новые атласы. Часто требуется нарисовать не текстуру целиком, а только ее часть. Например, если надо сделать постепенное появление объекта на экране или какой-нибудь индикатор прогресса. При использовании обычных атласов задача легко решается при помощи коррекции uv-координат. В случае же полигональных атласов все становится сложнее. Посмотрим на примере. Синим на картинке выделена часть текстуры, которую надо нарисовать:

fbe54f725960af79b8de87060ada4d37.png

Потребуется:
  • Исключить из отрисовки треугольники, которые не попадают в рисуемую часть текстуры
  • Найти пересечения новой границы текстуры с исходными треугольниками. Результат может уже не быть треугольником, и может потребоваться разбить его на 2 новых треугольника.

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

Бывают и более сложные случаи. Например, круговой прогресс или какие-то искажения текстуры. Поэтому оказалось, что проще некоторые текстуры упаковывать в обычные атласы или не упаковывать совсем, чтобы не усложнять процесс отрисовки.

Немного технических подробностей. Время упаковки полигонального атласа сильно зависит от настройки качества упаковки. Поскольку при любом изменении набора текстур атласы надо пересобирать, это приходится делать довольно часто. Поэтому обычно у нас включен режим «минимальная плотность, максимальная скорость». В таком режиме 8 атласов размером 2048×2048 пакуются примерно 5 минут. В общих чертах процесс упаковки выглядит так:

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

Как правило, уже предварительная упаковка является достаточно плотной. При попытке повышения качества, время упаковки вырастает очень сильно — до нескольких часов на 1 атлас —, а выигрыш может составлять 2–3 дополнительно упакованные текстуры.

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

class Drawable {
	virtual int Width() const;
	virtual int Height() const;
	virtual bool HitTest(int x, int y) const;
	virtual void Draw(SpriteBatch* batch, const FPoint& position);
}

У неё уже были функции получения размера, проверки непрозрачности пикселя для обработки кликов и отрисовки. Потребовалось только создать еще один класс PolygonalSprite, который правильно реализовывал бы эти функции с учетом разбиения текстуры на треугольники.

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

virtual void GetGeometry(std::vector& geometry) const;

Для обычных текстур и обычных атласов эта функция возвращает четыре вершины, образующие прямоугольник, соответствующий исходной текстуре. А для текстур из полигональных атласов — массив вершин треугольников на которые разбита текстура.

Сейчас полигональные атласы используются во многих наших проектах и можно считать, что они прошли испытание временем. Например, в нашем следующем free-to-play проекте Gardenscapes, мировой релиз которого состоится совсем скоро, основная часть игрового процесса происходит в принадлежащем игроку саду.

Для него нарисовано просто огромное количество разнообразных текстур, некоторые из них использованы в настоящей статье как примеры. Сейчас все эти текстуры умещаются в 8 полигональных атласов 2048×2048. А вот если бы мы упаковывали атласы обычным способом, то их получилось бы уже 11. Таким образом, мы получаем экономию оперативной памяти, в зависимости от применяемого графического формата, от 6 до 48 МБ. А гейм-дизайнеры могут предложить на четверь красивеньких текстур больше!

Об авторе: Сергей Шестаков, технический директор компании Playrix.

Комментарии (1)

  • 27 июля 2016 в 18:10

    +1

    Концепция хороша, но habrahabr вроде бы про код, а его тут не наблюдается.

© Habrahabr.ru