Эволюция рендеринга пробок в MAPS.ME
Всем привет! В прошлом году мы запустили пробки в нашем приложении. Мы долго готовились к запуску, и в ходе этой подготовки наши взгляды на решение задач, связанных с пробками, менялись. Рендеринг пробок прошёл длинный путь от первых прототипов до первой реализации, и сегодня я хочу рассказать об эволюции рендеринга пробок на пути к релизу.
Исходная задача
В самом начале пути мы поставили задачу научиться рисовать пробки очень быстро. Во-первых, «очень быстро» означало скорость появления. Пробки должны возникать на экране смартфона с минимальными задержками (в идеале — вообще без них), чтобы пользователь не ждал и, соответственно, не раздражался. Во-вторых, общая производительность рендеринга в приложении не должна серьёзно пострадать. В-третьих, нужно отображать пробки на второстепенных дорогах на таких уровнях масштаба, где наши конкуренты пробки уже не показывают.
Короче говоря, требовалось научиться быстро рисовать очень много дополнительных данных на мобильных устройствах. Благо наш графический движок проектировался с учетом рендеринга больших объёмов данных. Чтобы вы оценили рабочие объёмы нашего движка, приведу следующую статистику.
| Город | Количество полигонов в сцене |
|---|---|
| Москва | 400 000 |
| Нью-Йорк | 600 000 |
| Лондон | 800 000 |
NB: измерения здесь и далее проводились на уровне зума с лучшей детализацией и наибольшей видимой областью карты (разрешение экрана 2732 × 2048, iPad Pro 12,9″).
На таких объёмах данных мы поддерживаем 30—60 FPS на целевом наборе устройств в режиме просмотра карты, и этот показатель важно было сохранить.
Прототип
Здесь следует упомянуть об исходных данных для пробок. В данном посте мы не будем говорить о формате передачи и сжатии. Примем за входные данные массив пар (сегмент дороги; цвет). Сегмент — это двухточечный прямой отрезок дороги + бит направления, необходимый для двунаправленных дорог. Кроме того, данные поступают к нам в таком виде, что мы всегда получаем полный список сегментов для всех дорог на карте. Ниже приведён пример входных данных для графического движка.
(P1; P2; правая сторона) — жёлтый
(P1; P2; левая сторона) — жёлтый
(P2; P3; правая сторона) — жёлтый
(P2; P3; левая сторона) — зелёный
(P2; P4; правая сторона) — красный
Как я уже когда-то писал, наш графический движок использует векторные данные и рендерит карту в реальном времени. С помощью батчинга мы минимизируем количество draw call«ов, что позволяет нам эффективно рендерить большие объёмы геометрических данных. Данные о пробках, к счастью, обладают хорошей однородностью и удачно вписываются в текущую систему батчинга.
Для прототипа мы выбрали следующую архитектуру. Мы разделили геометрические данные на две части: изменяемые (цвет) и неизменяемые (позиция, нормаль и т. д.). Для каждой из частей мы создали отдельные вершинные и индексные буферы и на отрисовку отдавали геометрические данные в двух потоках данных. Когда приходило время обновлять цвета пробок, мы переписывали только изменяемые буферы. Чтобы ускорить формирование геометрических буферов, мы использовали прекеширование неизменяемых частей.
Когда прототип заработал, мы увидели, что пробки действительно появлялись и рендерились очень быстро при условии, что прекеширование было завершено. Пробки появлялись даже быстрее, чем сама карта. Однако размер кеша нас неприятно удивил. Для Москвы на кеш пришлось потратить примерно 700 Мб оперативной памяти — примерно 10 миллионов полигонов. С одной стороны, мы были горды, что наш движок смог обработать такой объём данных на мобильном устройстве, с другой стороны — стало очевидно, что для production такое решение не годится.
Во втором прототипе мы стали решать задачу быстрого появления пробок без чрезмерного потребления оперативной памяти. Для этого мы «перевернули» кеш, поставив во главу угла не неизменяемые геометрические данные, а данные о цвете. Мы стали кешировать данные о цвете сегментов дорог, а геометрические данные формировали на лету для той области экрана, на которую в текущий момент смотрел пользователь. Кеш цветов при этом не являлся подготовленным для отправки в OpenGL буфером, он использовался исключительно для получения цветов заданных сегментов дорог. Итог: геометрические буферы пробок стали формироваться схожим с тайлами карты образом.
Размер памяти, потребляемой рендерингом пробок, уменьшился до 50 Мб для Москвы, однако мы сильно потеряли в скорости появления карты на некоторых уровнях масштаба. Пробки теперь возникали вместе с картой, но задержка появления карты сильно увеличилась, что тоже было недопустимо.
После профилирования мы выяснили, что генерация в реальном времени геометрических буферов для пробок выполняется слишком долго на тех уровнях масштаба, где включаются второстепенные дороги, но при этом видно довольно большой участок карты. Основной проблемой было то, что алгоритмически ускорить генерацию геометрии мы не могли. Бутылочным горлышком оказались функции OpenGL по передаче данных из памяти, управляемой CPU, в память под управлением GPU. Единственным выходом из данной ситуации было уменьшение объёма геометрических данных.
Реализация
Для уменьшения объёма геометрических данных мы выбрали широко известный в real-time рендеринге приём — использование уровней детализации (LOD — level of details). Если ширина пробки для дороги заданного класса на заданном уровне масштаба меньше установленного предела, то мы рисуем её как аппаратную линию (с использованием примитива GL_LINES). Геометрический буфер для аппаратной линии формировать всё равно необходимо, однако размер такого буфера существенно меньше.
У такого подхода два существенных недостатка:
- Максимальная ширина аппаратной линии отличается на разных устройствах. Более того, на некоторых устройствах она может быть совсем маленькой (в худшем случае — один пиксель). В таком случае мы не можем использовать аппаратные линии для большинства пробок. К счастью, в большинстве своём эти устройства или устаревшие, или относятся к низшему ценовому сегменту, имеют экран низкого разрешения, а значит, и меньший объём отображаемых данных.
- Аппаратные линии визуально не слишком привлекательны. На них хорошо проявляется алиасинг, а сочленений между сегментами нет. Поэтому нам пришлось использовать аппаратные линии там, где это менее всего заметно: на второстепенных дорогах.
Тем не менее после настройки ширины сегментов пробок на различных уровнях масштаба результат нас почти удовлетворил.
Чтобы ещё уменьшить объём потребляемой пробками памяти, мы ввели дополнительный вытесняющий кеш. Дело в том, что картографические данные у нас разбиты на достаточно небольшие области, а данные о пробках разбиты точно таким же образом. Если пользователь активно двигал карту на глобальных уровнях масштаба или оказывался на границе областей разбиения, то он мог получать и хранить бесполезные для него данные о цветах пробок. Вытесняющий кеш позволил исключить подобные сценарии использования, ограничив сверху объём потребляемой памяти.
Результаты
- Память, потребляемая рендерингом пробок, находится в пределах 25—50 Мб. Этот показатель варьируется в зависимости от местности, качества маппинга дорог в OSM, количества данных о пробках.
- Рендеринг пробок почти не влияет на время формирования кадра на целевом наборе устройств.
- На наиболее нагруженных уровнях зума до 70% пробок отображаются с использованием аппаратных линий. На крупном масштабе мы стараемся рисовать пробки с максимальным качеством.
В данном посте мы рассмотрели важную, но всего лишь внешнюю, видимую пользователю часть сложной системы предоставления информации о пробках. Чтобы наши пользователи получили её, потребовались усилия всей команды MAPS.ME. Мы много работали над минимизацией сетевого трафика, роутинг научился строить маршруты с учётом пробок, у нас появился первый серьёзный server-side.
Хочу напомнить, что клиентская часть MAPS.ME — opensource-продукт, она доступна в GitHub для всех желающих.
P.S. We are hiring! У нас открыто несколько интересных вакансий и в клиентской, и в серверной разработке. Если вам интересно то, чем мы занимаемся, присоединяйтесь, и вместе мы сделаем ещё больше крутых фич.
