Всем привет! В прошлом году мы запустили пробки в нашем приложении. Мы долго готовились к запуску, и в ходе этой подготовки наши взгляды на решение задач, связанных с пробками, менялись. Рендеринг пробок прошёл длинный путь от первых прототипов до первой реализации, и сегодня я хочу рассказать об эволюции рендеринга пробок на пути к релизу.
Исходная задача
В самом начале пути мы поставили задачу научиться рисовать пробки очень быстро. Во-первых, «очень быстро» означало скорость появления. Пробки должны возникать на экране смартфона с минимальными задержками (в идеале — вообще без них), чтобы пользователь не ждал и, соответственно, не раздражался. Во-вторых, общая производительность рендеринга в приложении не должна серьёзно пострадать. В-третьих, нужно отображать пробки на второстепенных дорогах на таких уровнях масштаба, где наши конкуренты пробки уже не показывают.
Короче говоря, требовалось научиться быстро рисовать очень много дополнительных данных на мобильных устройствах. Благо наш графический движок проектировался с учетом рендеринга больших объёмов данных. Чтобы вы оценили рабочие объёмы нашего движка, приведу следующую статистику.
| Город | Количество полигонов в сцене |
|---|---|
| Москва | 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! У нас открыто несколько интересных вакансий и в клиентской, и в серверной разработке. Если вам интересно то, чем мы занимаемся, присоединяйтесь, и вместе мы сделаем ещё больше крутых фич.
Комментарии (40)
unwrecker
19.02.2018 22:39А что у вас за источник данных о пробках? Вижу какое-то непонятное перекрытие на Тверской.
rokuz Автор
19.02.2018 23:11+1Мы агреггируем информацию о треках и скоростях движения в реальном времени. Не все ещё идеально, возможно, там действительно что-то не то в районе Тверской
ZverArt
20.02.2018 10:28То есть собираете свои данные (с устройств, на которых установлены maps.me)?
rokuz Автор
20.02.2018 10:59Когда пользователь включает пробки в нашем приложении (и при этом находится в режиме автонавигации), он активирует анонимный сбор статистики в реальном времени. Без этого получить актуальные пробки, к сожалению, не представляется возможным
unwrecker
20.02.2018 13:49А статистические данные и предсказания есть? С тоской вспоминаю те времена, когда у меня был телефон на Windows mobile, и на нём был Покетгис с
Пробковоротом, который умел так хорошо прокладывать маршруты по пробкам как до сих пор никакая
другая программа не умеет...
kibizoidus
20.02.2018 10:42+1Всеми навесками сверху вы убили главную фичу Maps.me — отличные карты и навигация БЕЗ интернета. И это очень жаль…
rokuz Автор
20.02.2018 11:01Вы всегда можете продолжать пользоваться только оффлайн-фичами. Пробки включаются по вашему желанию
kibizoidus
20.02.2018 12:46А вы пробовали?
rokuz Автор
20.02.2018 13:19Включать пробки по желанию? Да) Пользоваться приложением без интернета? Тоже да)
kibizoidus
20.02.2018 14:53Видать я что-то не так делаю, но Maps.me без интернета стало абсолютно неюзабельно (.
Zverik
20.02.2018 18:17Да, видимо, что-то не так у вас. Я за границей всегда включаю авиарежим и пользуюсь картами для всего. Опишите свои проблемы, пожалуйста, на support@maps.me
crazyv
20.02.2018 11:03Источником данных о пробках являются ваши же пользователи? На сколько они точны, измеряли? Например по сравнению с двумя самыми крупными навигационными сервисами в России?
Как дела с этим за границей? Ведь, на сколько я понимаю, ваши карты часто используют именно там в связи с удобством доступа и простой автономностью.rokuz Автор
20.02.2018 11:05Про пользователей ответ выше. Достаточно точны, чтобы использовать их для автонавигации. В отличие от двух других крупных российских сервисов наши пользователи распределены по всему миру, и мы можем показывать пробки во многих крупных туристических городах.
rekia
20.02.2018 16:53Пробовал включать пробки в Риге, пишет Traffic data is not available.
Если перевести карту на Москву, то там трафик видно.
Чяднт?rokuz Автор
20.02.2018 16:54Вы все делаете так, к сожалению, для некоторых городов мы собираем недостаточно данных, чтобы показать пробки. Ваш город, видимо, один из таких
KirEv
20.02.2018 12:36в киеве пользовался гугл.картами и яндексом, к сожалению, информация о заторах не всегда соответствует действительности, особенно в пятницу вечером )… дорогу рисует зеленым, а на самом деле — затор в 1км… или наоборот, пишет затор — едешь — все свободно.
maps.me использую из-за возможности офф-лайн карт, пробки еще не тестил :)
tangro
20.02.2018 11:11-2Блин, maps.me, оказывается, принадлежит mail.ru, вот это я тормоз. Спасибо за статью, пойду удалю.
krokhmalyuk
20.02.2018 12:44Ну здрасьте. Maps.me — один из тех продуктов, который после продажи стал еще лучше, чем до.
tangro
21.02.2018 01:26Я же никаких претензий к maps.me не имею. Но меил.ру — это меил.ру. Тут только закопать и забыть.
vindy123
20.02.2018 13:08Наверное, моя проблема не так сильно проявляется на более новых телефонах, но на iphone 4s при уходе с маршрута его перестройка может легко занять секунд 30 и более. А так как за 30 секунд уезжаешь далеко, перестроенный маршрут уже устаревает и приложение начинает перестраивать маршрут второй, третий и четвертый раз. При этом на гугл мэпс рерутинг — это пара секунд. Очевидно, что-то можно оптимизировать в алгоритме перестроения маршрута? Забросил продукт после того, как несколько раз проехал пару лишних километров, ожидая окончания этих итераций.
rokuz Автор
20.02.2018 13:17В отличие от тех же GoogleMaps мы не используем серверные мощности для расчета маршрутов, а выполняем все вычисления на устройстве, чтобы это работало оффлайн. Поэтому на слабых устройствах маршруты могут строиться несколько дольше.
Мы совершенствуем наш роутинг в том числе и по производительности. Если последний раз пользовались приложением давно, попробуйте поставить последнюю версию.
eatmore
20.02.2018 13:40На iPhone 4s в MAPS.ME и сама карта отрисовывается достаточно медленно, иногда приходится несколько секунд ждать, пока всё отрисуется (обычно это при увеличении масштаба, когда увеличивается уровень детализации). Те же Яндекс.Карты, как мне кажется, работают быстрее (в оффлайн-режиме).
prs123
20.02.2018 13:25Правильно ли я понимаю, что я открываю карту города с пробками (ту же Москву) через мобильный интернет и весь мой месячный лимит начинает стремится к нулю?
rokuz Автор
20.02.2018 13:26Неправильно) Мы оптимизировали интернет-трафик по пробкам. Наш целевой показатель — не более 1Мб/час
eatmore
20.02.2018 13:27А почему в MAPS.ME нет работающего автоматического перехода на ночной режим? Каждый раз, когда нужно ночью в машине посмотреть карту, приходится лезть в меню и включать ночной режим, а потом обратно выключать.
rokuz Автор
20.02.2018 13:37Автоматическое переключение работает только в режиме автонавигации, так как большинству пользователей, кто этим режимом не пользуется, автоматическое переключение может мешать.
eatmore
20.02.2018 13:50Пользователи, которым мешает автопереключение, всегда могут его выключить. Мне кажется, что то, что в других приложениях (карты Яндекс, Google и т. д.) автопереключение работает независимо от режима навигации, свидетельствует о том, что пользователи с вами не согласны. Почему нельзя было сделать автопереключение только в режиме навигации как отдельную опцию? Пускай это будет только для тех, кому это надо.
rokuz Автор
20.02.2018 14:06Я понял вашу потребность :) Мы рассмотрим возможность создания опции автоматического переключения не только в режиме автонавигации.
kisaa
20.02.2018 13:30Роман, а можно ответить на отклоненный комментарий про апартаменты от booking.com хотя бы в личку, если уж это идёт в разрез с интересами компании?
rokuz Автор
20.02.2018 13:33Вопрос про отключение booking.com не является запрещенным и в разрез ни с чем не идет :) Однако, к теме данного поста не относится, поэтому, видимо, и был отклонен. Отключить нельзя.
nanshakov
20.02.2018 14:06А почему нельзя собрать статистику за год примерно и не рендерить «примерные» пробки офлайн? Или за год ситуация так меняется, что проблемные перекрестки перестают такими быть? Ок, ну тогда раз в неделю загружать данные, для тех, у кого нет интернета…
rokuz Автор
20.02.2018 14:19Пробки очень часто меняются, особенно, в крупных городах. Когда вы едете на автомобиле вам обычно не интересно, что здесь по статистике 250 дней в году пробка, вам интересно сколько вам еще стоять и как быстрее объехать :) Пробки, к счастью или сожалению, нужны в реальном времени.
ooprizrakoo
20.02.2018 21:24слишком большой лаг, например где-то начали ремонтировать полосу дороги — и вот пробка, где-то строить развязку — ещё одна, и каждое изменение может кардинально менять карту пробок — т.к. жители других районов будут выбирать новые пути объезда, создавая пробки там, где их раньше не было.
Или представьте обычное ДТП — которое меняет всю картину за пол часа…
Daemonic
20.02.2018 17:25Господа, для того, чтобы хотя бы начать говорить про пробки, нужно сперва сделать нормальную автомобильную навигацию. Алгоритм построения маршрута сейчас не просто медленный — он опасный для водителя.
Простой пример — слева Maps.me, справа Google Maps:
Нет, мы не доедем через центр Хельсинки за 27 минут — мы потеряем там время на светофорах и заплутаем на ремонтах дорог. Нужно вести именно по шоссе.
igor_kuznetsov
Оно уже перестало внезапно переворачивать навигатор верх ногами? А то тем летом благодаря навигатору уехал черте куда в горы. Не замечал что карта переворачивалась…
rokuz Автор
По идее не должно быть такого.
Напишите, пожалуйста, на support@maps.me
Чем точнее сможете описать условия воспроизведения, тем более вероятно, что мы это найдём и исправим)