company_banner

Эволюция рендеринга пробок в 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). Геометрический буфер для аппаратной линии формировать всё равно необходимо, однако размер такого буфера существенно меньше.


    У такого подхода два существенных недостатка:


    1. Максимальная ширина аппаратной линии отличается на разных устройствах. Более того, на некоторых устройствах она может быть совсем маленькой (в худшем случае — один пиксель). В таком случае мы не можем использовать аппаратные линии для большинства пробок. К счастью, в большинстве своём эти устройства или устаревшие, или относятся к низшему ценовому сегменту, имеют экран низкого разрешения, а значит, и меньший объём отображаемых данных.
    2. Аппаратные линии визуально не слишком привлекательны. На них хорошо проявляется алиасинг, а сочленений между сегментами нет. Поэтому нам пришлось использовать аппаратные линии там, где это менее всего заметно: на второстепенных дорогах.

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


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


    Результаты


    1. Память, потребляемая рендерингом пробок, находится в пределах 25—50 Мб. Этот показатель варьируется в зависимости от местности, качества маппинга дорог в OSM, количества данных о пробках.
    2. Рендеринг пробок почти не влияет на время формирования кадра на целевом наборе устройств.
    3. На наиболее нагруженных уровнях зума до 70 % пробок отображаются с использованием аппаратных линий. На крупном масштабе мы стараемся рисовать пробки с максимальным качеством.

    В данном посте мы рассмотрели важную, но всего лишь внешнюю, видимую пользователю часть сложной системы предоставления информации о пробках. Чтобы наши пользователи получили её, потребовались усилия всей команды MAPS.ME. Мы много работали над минимизацией сетевого трафика, роутинг научился строить маршруты с учётом пробок, у нас появился первый серьёзный server-side.


    Хочу напомнить, что клиентская часть MAPS.ME — opensource-продукт, она доступна в GitHub для всех желающих.


    P. S. We are hiring! У нас открыто несколько интересных вакансий и в клиентской, и в серверной разработке. Если вам интересно то, чем мы занимаемся, присоединяйтесь, и вместе мы сделаем ещё больше крутых фич.


    Mail.Ru Group 550,88
    Строим Интернет
    Поделиться публикацией
    Похожие публикации
    Комментарии 45
    • 0
      Оно уже перестало внезапно переворачивать навигатор верх ногами? А то тем летом благодаря навигатору уехал черте куда в горы. Не замечал что карта переворачивалась…
      • 0
        По идее не должно быть такого.
        Напишите, пожалуйста, на support@maps.me
        Чем точнее сможете описать условия воспроизведения, тем более вероятно, что мы это найдём и исправим)
        • 0
          Увы тот телефон я уже утопил и ему хана.Это было MotoX первого поколения… Летом я тоже уезжаю, буду тестить
      • 0
        Интересные у вас там задачки
        • 0

          А что у вас за источник данных о пробках? Вижу какое-то непонятное перекрытие на Тверской.

          • +1
            Мы агреггируем информацию о треках и скоростях движения в реальном времени. Не все ещё идеально, возможно, там действительно что-то не то в районе Тверской
            • 0
              То есть собираете свои данные (с устройств, на которых установлены maps.me)?
              • 0
                Когда пользователь включает пробки в нашем приложении (и при этом находится в режиме автонавигации), он активирует анонимный сбор статистики в реальном времени. Без этого получить актуальные пробки, к сожалению, не представляется возможным
              • 0

                А статистические данные и предсказания есть? С тоской вспоминаю те времена, когда у меня был телефон на Windows mobile, и на нём был Покетгис с
                Пробковоротом, который умел так хорошо прокладывать маршруты по пробкам как до сих пор никакая
                другая программа не умеет...

                • 0
                  Все это есть на server-side
            • +1
              Всеми навесками сверху вы убили главную фичу Maps.me — отличные карты и навигация БЕЗ интернета. И это очень жаль…
              • 0
                Ну я так полагаю можно отключить пробки и использовать карты без сети
                • 0
                  Вы всегда можете продолжать пользоваться только оффлайн-фичами. Пробки включаются по вашему желанию
                  • +1
                    А вы пробовали?
                    • 0
                      Включать пробки по желанию? Да) Пользоваться приложением без интернета? Тоже да)
                      • +1
                        Видать я что-то не так делаю, но Maps.me без интернета стало абсолютно неюзабельно (.
                        • 0
                          Да, видимо, что-то не так у вас. Я за границей всегда включаю авиарежим и пользуюсь картами для всего. Опишите свои проблемы, пожалуйста, на support@maps.me
                • 0
                  Источником данных о пробках являются ваши же пользователи? На сколько они точны, измеряли? Например по сравнению с двумя самыми крупными навигационными сервисами в России?
                  Как дела с этим за границей? Ведь, на сколько я понимаю, ваши карты часто используют именно там в связи с удобством доступа и простой автономностью.
                  • 0
                    Про пользователей ответ выше. Достаточно точны, чтобы использовать их для автонавигации. В отличие от двух других крупных российских сервисов наши пользователи распределены по всему миру, и мы можем показывать пробки во многих крупных туристических городах.
                    • 0
                      Пробовал включать пробки в Риге, пишет Traffic data is not available.
                      Если перевести карту на Москву, то там трафик видно.
                      Чяднт?
                      • 0
                        Вы все делаете так, к сожалению, для некоторых городов мы собираем недостаточно данных, чтобы показать пробки. Ваш город, видимо, один из таких
                    • 0
                      в киеве пользовался гугл.картами и яндексом, к сожалению, информация о заторах не всегда соответствует действительности, особенно в пятницу вечером )… дорогу рисует зеленым, а на самом деле — затор в 1км… или наоборот, пишет затор — едешь — все свободно.

                      maps.me использую из-за возможности офф-лайн карт, пробки еще не тестил :)

                    • –12
                      Блин, maps.me, оказывается, принадлежит mail.ru, вот это я тормоз. Спасибо за статью, пойду удалю.
                      • +1
                        Ну здрасьте. Maps.me — один из тех продуктов, который после продажи стал еще лучше, чем до.
                        • 0
                          Я же никаких претензий к maps.me не имею. Но меил.ру — это меил.ру. Тут только закопать и забыть.
                        • +1
                          Maps.me не Вконтакте, хуже от продажи не стал.
                        • 0
                          Наверное, моя проблема не так сильно проявляется на более новых телефонах, но на iphone 4s при уходе с маршрута его перестройка может легко занять секунд 30 и более. А так как за 30 секунд уезжаешь далеко, перестроенный маршрут уже устаревает и приложение начинает перестраивать маршрут второй, третий и четвертый раз. При этом на гугл мэпс рерутинг — это пара секунд. Очевидно, что-то можно оптимизировать в алгоритме перестроения маршрута? Забросил продукт после того, как несколько раз проехал пару лишних километров, ожидая окончания этих итераций.
                          • 0
                            В отличие от тех же GoogleMaps мы не используем серверные мощности для расчета маршрутов, а выполняем все вычисления на устройстве, чтобы это работало оффлайн. Поэтому на слабых устройствах маршруты могут строиться несколько дольше.
                            Мы совершенствуем наш роутинг в том числе и по производительности. Если последний раз пользовались приложением давно, попробуйте поставить последнюю версию.
                            • 0
                              Ну, я гугл мэпс в оффлайн режиме и имел в виду. Тоже пара секунд. В любом случае, спасибо за то, что развиваете важную альтернативу и уделяете внимание отзывам пользователей. Во многих других сценариях ваш продукт выигрывает за счет лучшего качества карт.
                            • 0
                              На iPhone 4s в MAPS.ME и сама карта отрисовывается достаточно медленно, иногда приходится несколько секунд ждать, пока всё отрисуется (обычно это при увеличении масштаба, когда увеличивается уровень детализации). Те же Яндекс.Карты, как мне кажется, работают быстрее (в оффлайн-режиме).
                            • 0

                              Правильно ли я понимаю, что я открываю карту города с пробками (ту же Москву) через мобильный интернет и весь мой месячный лимит начинает стремится к нулю?

                              • +1
                                Неправильно) Мы оптимизировали интернет-трафик по пробкам. Наш целевой показатель — не более 1Мб/час
                                • 0
                                  Здорово. А можно ли об этом по-подробнее? Можете ли вы в статью оформить? Спасибо
                              • 0
                                А почему в MAPS.ME нет работающего автоматического перехода на ночной режим? Каждый раз, когда нужно ночью в машине посмотреть карту, приходится лезть в меню и включать ночной режим, а потом обратно выключать.
                                • 0
                                  Автоматическое переключение работает только в режиме автонавигации, так как большинству пользователей, кто этим режимом не пользуется, автоматическое переключение может мешать.
                                  • 0
                                    Пользователи, которым мешает автопереключение, всегда могут его выключить. Мне кажется, что то, что в других приложениях (карты Яндекс, Google и т. д.) автопереключение работает независимо от режима навигации, свидетельствует о том, что пользователи с вами не согласны. Почему нельзя было сделать автопереключение только в режиме навигации как отдельную опцию? Пускай это будет только для тех, кому это надо.
                                    • 0
                                      Я понял вашу потребность :) Мы рассмотрим возможность создания опции автоматического переключения не только в режиме автонавигации.
                                • 0

                                  Роман, а можно ответить на отклоненный комментарий про апартаменты от booking.com хотя бы в личку, если уж это идёт в разрез с интересами компании?

                                  • 0
                                    Вопрос про отключение booking.com не является запрещенным и в разрез ни с чем не идет :) Однако, к теме данного поста не относится, поэтому, видимо, и был отклонен. Отключить нельзя.
                                    • 0
                                      На «ежедневные» (теперь — ежетрехдневные) карты не накладывают слой booking.com: direct.mapswithme.com/regular/daily Но их не проверяют (как те, что в релизе) и с ними не работают пробки.
                                    • 0
                                      А почему нельзя собрать статистику за год примерно и не рендерить «примерные» пробки офлайн? Или за год ситуация так меняется, что проблемные перекрестки перестают такими быть? Ок, ну тогда раз в неделю загружать данные, для тех, у кого нет интернета…
                                      • +2
                                        Пробки очень часто меняются, особенно, в крупных городах. Когда вы едете на автомобиле вам обычно не интересно, что здесь по статистике 250 дней в году пробка, вам интересно сколько вам еще стоять и как быстрее объехать :) Пробки, к счастью или сожалению, нужны в реальном времени.
                                        • +1
                                          слишком большой лаг, например где-то начали ремонтировать полосу дороги — и вот пробка, где-то строить развязку — ещё одна, и каждое изменение может кардинально менять карту пробок — т.к. жители других районов будут выбирать новые пути объезда, создавая пробки там, где их раньше не было.
                                          Или представьте обычное ДТП — которое меняет всю картину за пол часа…
                                        • +1
                                          Господа, для того, чтобы хотя бы начать говорить про пробки, нужно сперва сделать нормальную автомобильную навигацию. Алгоритм построения маршрута сейчас не просто медленный — он опасный для водителя.
                                          Простой пример — слева Maps.me, справа Google Maps:


                                          Нет, мы не доедем через центр Хельсинки за 27 минут — мы потеряем там время на светофорах и заплутаем на ремонтах дорог. Нужно вести именно по шоссе.
                                          • 0

                                            Аналогичный пример у меня с Варшавой был. Телефон сеть потерял и повёл через центр города вместо объезда.
                                            Вариантов немного — (1) возиться с телефоном на обочине (2) ехать по знакам и рисковать проскочить нужные повороты (3) ехать через центр и потерять часик.
                                            Увы, выбрал третье. Хорошо бы учитывать среднюю "заложенность" дорог для прокладывания маршрута.
                                            Но программа отличная, всё равно спасибо :)

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

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