Всем привет! Сегодня я бы хотел рассказать о рендеринге, который не имеет отношения к компьютерным играм, анимационным фильмам или промышленным системам проектирования. Речь пойдет о движке для рендеринга карт в реальном времени для проекта MAPS.ME. В данном посте я опишу общие принципы работы движка и некоторые грабли, на которые мы наступили (и те, которые успешно обошли). Если вы занимаетесь рендерингом больших объемов данных, в особенности картографического характера, наш опыт, надеюсь, будет полезен в ваших проектах или, по крайней мере, любопытен. Всех заинтересовавшихся прошу под кат.

О MAPS.ME и рендеринге

MAPS.ME — это мобильное приложение, позволяющее пользователю получить на своем устройстве полноценные офлайн-карты с поиском, навигацией и еще целым рядом классных штук. Картографические данные мы получаем из OpenStreetMap, обрабатываем, упаковываем и предоставляем пользователям через приложение. На сегодняшний день OpenStreetMap покрывает весь мир с достаточно высокой степенью детализации, карту нам необходимо рендерить на устройстве, а объем отображаемых картографических данных может быть очень значительным. Для эффективного отображения картографических данных мы в MAPS.ME разработали движок, который получил название Drape. Данный движок только готовится к релизу, он во многом превосходит текущую графическую библиотеку, поэтому сегодня (немного авансом) поговорим о Drape.

Понятно, что решение о создании нового графического движка в существующем проекте возникает не на пустом месте, предыдущие механизмы отрисовки не позволяли развивать проект в желаемом направлении. Многие (особенно ребята из геймдева) имеют устойчивое (вполне понятно какое) отношение к «движко-писателям». К сожалению, в данной области крайне бедный выбор сторонних разработок, а требования к рендерингу карт сильно отличаются от требований к рендерингу игр. Главное направление деятельности графического разработчика в геймдеве — отображение виртуального мира сообразно стилю игры. Рядом с игровым графическим программистом традиционно стоят геймдизайнеры, художники, моделлеры, которые всегда могут прийти на помощь: уменьшить полигонаж моделей, перерисовать текстуры или перестроить игровой уровень так, чтобы не тормозило или не были заметны артефакты. Мы же рисуем мир реальный, более того — нанесенный на карту людьми из открытого сообщества. Несмотря на достаточно высокую культуру картографирования, в OpenStreetMap встречается много векторных данных, которые в исходном виде слабо пригодны для отображения. Лишь благодаря ребятам, занимающимся алгоритмами предподготовки данных, у нас есть шанс нарисовать карту. Таким образом, в нашем деле рассчитывать можно только на свое умение оптимизировать рендеринг и алгоритмы предподготовки данных. Наша главная задача — нарисовать карту, состоящую из множества объектов, как можно более быстро, красиво и по данным, которым нельзя слепо доверять. Именно эту проблему и решает наш движок Drape, к принципам работы которого мы плавно переходим.

О природе движка Drape

Если говорить о картах, к которым мы привыкли в web, то подавляющее большинство приложений использует тайловую модель отображения. Тайл — это изображение, которое содержит часть карты определенного уровня детализации. При различных манипуляциях с картой (масштаб, сдвиг, начальная загрузка) мы получаем от сервера необходимые тайлы, а браузер их отображает. Все это прекрасно работает в онлайне и даже немного в офлайне, если кэшировать тайлы на стороне пользователя. Но как только мы начинаем задумываться о полноценных офлайновых картах, такой подход оказывается неприемлемым. На текущий момент крайне сложно так сжать предподготовленные растровые данные, чтобы на мобильном устройстве пользователя хватило дискового пространства. Поэтому в Drape мы оперируем векторными данными и рендерим карту в реальном времени. Движок Drape — кроссплатформенная многопоточная система, написанная на C++. Сам движок оперирует тремя основными потоками:

1. UI-поток. В данном потоке регистрируются действия пользователя и выполняется код, специфичный для той или иной платформы (iOS, Android). Данный поток порождает та операционная система, на которой запущено приложение.
2. FR-поток (сокращение от Frontend Renderer). Главная задача этого потока — рендеринг подготовленных вершинных и индексных буферов на экран. Данный поток порождается самим движком.
3. BR-поток (сокращение от Backend Renderer). В этом потоке происходит формирование вершинных и индексных буферов и других данных для отрисовки на FR. Данный поток также порождается движком.

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



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

1. На UI-потоке действия пользователя (в нашем случае бездействие), а также все необходимое для расчета viewport’а будет собрано, упаковано и отправлено на FR.
2. FR по входным данным сформирует viewport (матрицы мира, вида и проекции), определит уровень детализации картографических данных. Рассчитанные данные спроецируются на так называемое дерево тайлов. Это дерево чем-то похоже на небезызвестное квадродерево, широко используемое в графических движках для оптимизации отрисовки сцены. Так же как и в квадродереве, в дереве тайлов поддерживается идея вложенности пространств. Например, 4 тайла 7-го уровня детализации будут составлять 1 тайл 6-го уровня. В отличии от классического квадродерева, наше дерево перестраивает свою структуру в зависимости от набора тайлов, которые отображаются в текущий момент. Т.е. если в текущий момент отображаются тайлы только 6-го уровня детализации, то дерево вырождается в список. И если вдруг пользователь увеличивает масштаб карты до 7-го уровня детализации, то тайлы 7-го уровня становятся дочерними узлами для соответствующих тайлов 6-го уровня. Когда 4 тайла 7-го уровня будут подготовлены для отрисовки, соответсвующий им тайл с 6-го уровня будет вытеснен из дерева тайлов. Здесь следует пояснить, что под тайлами я не имею ввиду заранее подготовленные изображения. Дерево оперирует лишь областями пространства и связанными с этими областями графическими данными (вершинными и индексными буферами, текстурами, шейдерами и т. д.).
   После небольшого лирического отступления о природе дерева тайлов, вернемся к FR. Имея в распоряжении новый viewport, FR помечает узлы дерева тайлов, которые более не видимы, если таковые существуют, а также определяет, какие тайлы должны появиться в дереве, чтобы полностью покрыть новый viewport. Все эти данные упаковываются в сообщение и отправляются на BR-поток. FR-поток в это время продолжает отображать то, что у него есть на текущий момент с учетом новых матриц.
3. BR принимает сообщение и начинает генерировать геометрию (и прочие сопутствующие графические данные) для новых тайлов. Он распараллеливает генерацию при помощи нескольких вспомогательных потоков. Как только графические данные для тайла сформированы, они незамедлительно отправляются в сообщении на FR-поток. Другие тайлы в это время могут еще находится в процессе генерации.
4. FR принимает графические данные для тайла, ищет им место в дереве тайлов и реорганизует структуру дерева сообразно текущей ситуации. Новые данные могут быть отрисованы уже на следующем кадре. Со временем FR получает данные для всех тайлов, и система приходит в состояние покоя до тех пор, пока от UI-потока не придет новый viewport.

Вышеприведенное описание главного принципа работы движка, конечно, является высокоуровневым. Воплощение всего этого в C++ коде таит в себе огромное количество нюансов, некоторые из которых мы сейчас рассмотрим.

О нюансах

Синхронизация потоков и производительность

Внимательный читатель мог догадаться, что потоки будут активно обмениваются друг с другом сообщениями в ситуации, когда пользователь двигает карту. Движение пальца по экрану устройства, как правило, плавное, а значит в FR-поток будет отправляться огромное количество сообщений, каждое из которых будет порождать еще десятки сообщений из FR в BR, что будет сопровождаться тяжеловесными операциями по генерации геометрии. Перспектива малоприятная, как вы понимаете. Чтобы преодолеть эту проблему, мы, наступив на горло собственной песне, отказались от использования сообщений для выставления viewport'а. Это единственный случай, когда данные из UI-потока выставляются в FR-поток напрямую, минуя очередь. И обновляется viewport один раз в кадр.

Вообще, при наличии потокобезопасных очередей здравый смысл подсказывает, что трафик сообщений должен быть как можно ниже. Чем меньше сообщений, тем меньше очереди блокируются на записи/чтении. У нас же большое количество сообщений c графическими данными отправляется с BR на FR по завершению процесса генерации. Чтобы преодолеть эту проблему мы начали агрегировать данные, собирая разноплановую геометрию в общие буферы (это, к слову, полезно также и при рендеринге для минимизации drawcall'ов). В итоге мы дошли до того, что наши буферы по размеру близки к максимально допустимым при адресации 16-битными индексами.

Пламенные приветы от OpenGL ES

OpenGL ES и многопоточность — весьма горячая смесь. Ситуация усугубляется драйверами для мобильных графических чипов, особенно в ОС Android. Проблемы возникали практически на всем пути разработки, возникают сейчас, и, к сожалению, никаких предпосылок к тому, что возникать перестанут, пока нет.

1. Контексты OpenGL создаются средствами операционной системы, и для FR- и BR-потока они собственные. Спецификация OpenGL запрещает обращение к контексту вне потока, в котором он создан. Однако графические ресурсы (по крайне мере, некоторые) между потоками можно расшаривать. Только это и делает возможным асинхронную подготовку ресурсов. Получается, у нас есть 2 потока, которые оперируют контекстами OpenGL, и есть поток операционной системы, который управляет временем жизни этих контекстов. Например, в ОС Android контекст OpenGL может спокойно умереть, когда приложение уйдет в фон. И к этому времени оба потока, которые пользуются контекстами, должны освободить все ресурсы и прекратить выполнять любые команды OpenGL. Это заставляет нас прикладывать дополнительные усилия для управления временем жизни FR- и BR-потоков, чтобы гарантировать, что они завершатся раньше, чем это сделает системный поток.
2. Глифы шрифтов у нас также подготавливаются на BR-потоке. Они сначала загружаются при помощи библиотеки FreeType, обрабатываются алгоритмом SDF (Signed Distance Field), а затем перемещаются на текстуру при помощи функции glTexSubImage2D. Получается, что один поток (BR) пишет в текстуру, в то время как другой (FR) читает из этой текстуры при рендеринге. К сожалению, не все драйвера справлялись с этой задачей, и мы были вынуждены перенести вызов glTexSubImage2D на поток рендеринга. Получилось, что не только BR-поток подготавливает нам данные для отрисовки.
3. Особенную радость нам доставил чип Tegra 3, на котором то не работает glGetActiveUniform, если вызываешь glDetachShader сразу после линковки шейдеров, то в шейдере умножение на 0, дает какие-то непредсказуемые результаты.

Обновление геометрических данных

Иногда возникают ситуации, когда геометрию необходимо обновлять в процессе отрисовки. Речь здесь даже не идет о вершинных анимациях, хотя для них также будет справедливо все нижеизложенное. В нашем случае ярким примером может служить обновление вершинных данных в зависимости от масштаба карты. Вершинные данные необходимо обновлять, если мы хотим, например, чтобы текстурный рисунок сохранял свои размеры вне зависимости от масштаба, как в случае со стрелками, указывающими направление течения рек. Решение с использованием uniform-переменных не всегда годится, так как в ряде случаев потребовался бы массив uniform-переменных, равный длине вершинного буфера. Для решения этой проблемы мы использовали следующий трюк. Неизменяемые части вершинного буфера мы упаковываем стандартным способом, например:

{ [позиция 1, нормаль 1] [позиция 2, нормаль 2] … [позиция N, нормаль N] }

Для изменяемых компонентов вершин формируем отдельный буфер:

{ [текстурные координаты 1] [текстурные координаты 2] … [текстурные координаты N] }

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

Пересечение объектов

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

О будущем

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

P.S. Господа графические разработчики, если при прочтении данного поста у вас возникло устойчивое желание создать собственные карты с преферансом и куртизанками, спешу сообщить, что у вас есть альтернатива — присоединиться к нашей команде! Если есть какие-то вопросы, можете смело писать в личку.