Привет, меня зовут Сергей Загребин, я из команды разработки графического движка 2ГИС. Кроме рендеринга, мы также отвечаем за формат доставляемых офлайн- и онлайн-данных. В этой статье расскажу, как мы игрались со способом разбиения картографических данных на тайлы и искали баланс между размером офлайн-пакетов и производительностью в рантайме.
Надеюсь, этот материал будет полезен не только тем, кто занимается доставкой картографических данных, но и всем, кому интересно, как работает карта 2ГИС.
Разбиение карты на тайлы
В нашем движке мы используем координаты, приближенные к координатам проекции Web Mercator в сантиметрах. Они преобразованы таким образом, чтобы весь диапазон значений проекции был растянут на все значения int32.
Мир в этой проекции можно представить в виде квадродерева квадратных тайлов:
Тайл уровня 0 (z0) содержит весь мир.
Он делится на четыре z1-тайла.
Каждый из них, в свою очередь, на четыре z2-тайла и т.д.
В наших тайлах используется локальная система координат, ограниченная диапазоном значений uint16, что позволяет для уровня z16 добиться сантиметровой точности. Так мы сокращаем вдвое размер исходных координат, при этом их можно восстановить по локальным координатам внутри тайла и положению самого тайла в квадродереве.
Когда мы говорим о тайловой разрезке, мы должны ответить на два вопроса:
На тайлы каких уровней квадродерева мы хотим выгрузить все наши данные?
И на каких зумах (масштабах) мы хотим тайлы этих уровней загружать?
Опустив детали, связанные с разными экранами и разрешениями, значения зумов можно представить аналогично уровням квадродерева:
зум 0 — на экране девайса виден весь мир,
зум 1 — только четверть мира,
зум 2 — одна шестнадцатая и т.д.
Зум сопоставим с высотой камеры и используется в стилях, которые определяют отрисовку выгруженных объектов по их атрибутам.
Связь тайловой разрезки с размером пакета и перфомансом
Скачивая через приложение свой город, пользователь в числе прочего получает офлайн-пакет карты — именно с ним можно пользоваться 2ГИС без интернета.
Размер офлайн-пакета зависит от того, на тайлы каких уровней мы разрезаем наши данные:
Выгрузка одной и той же геометрии в тайлы разных уровней приводит к множественному дублированию. Ограничение выгрузки, исходя из природы данных, (например, исключение трёхмерных домов на дальних зумах) снижает дублирование, однако при большом количестве уровней всё равно не устраняет его полностью.
Сама разрезка данных на тайлы добавляет новые искусственные вершины на границах тайлов, увеличивая объём данных.
Даже «почти пустые» тайлы (например, если это совсем мелкий тайл в глуши, содержащий единственный квадратный участок леса) занимают место.
Для отрисовки наших тайлов мы используем современные графические API — Vulkan, Metal, а для старых девайсов OpenGL. Все они мотивируют использовать батчинг для ускорения рендеринга — объединять все однообразные объекты в один вызов отрисовки (draw call).
В движке мы батчим объекты внутри одного тайла, что является сильным аргументом в пользу выгрузки тайлов на каждый уровень квадродерева с небольшими диапазонами видимости. Именно такая естественная разрезка используется в веб-версии 2ГИС: режем данные на тайлы каждого уровня с диапазонами видимости шириной в один зум.
Новая тайловая разрезка
Предыстория
Во времена, когда 2ГИС рисовал карту только из скачиваемых офлайн-пакетов, инженеры движка реализовали возможность разбиения картографических данных на любое количество тайловых разрезок, в частности на специфичные разрезки для данных с генерализациями.
Так, например, береговую линию можно выгрузить следующим образом:
красивую подробную геометрию в тайлы z14 для ближних зумов,
упрощённую генерализованную геометрию в тайлы z10 для дальних зумов.
Данные в наших тайлах векторные, порядок отрисовки объектов определяется стилями, и движок без проблем рисует одни тайлы поверх других. Манипуляции с наложением тайлов разных разрезок позволяют существенно облегчить итоговый офлайн-пакет, поскольку уменьшают дублирование геометрий между тайлами разных уровней.
Со временем фокус сместился в сторону онлайна и пришло время гибрида — режима отрисовки карты с выбором источника данных в зависимости от сети и наличия скачанного офлайн-пакета города. Для гибрида важно соответствие тайловых разрезок в онлайне и офлайне, чтобы тайлы из онлайна могли корректно замещать офлайн-тайлы и наоборот: так при наличии сети мы покажем онлайн-тайл, а при отсутствии сети и наличии офлайн-пакета — аналогичный офлайн-тайл.
Задача реализации гибрида была довольно большой и сложной, до неё мы в движке совсем не работали с сетью. Поэтому мы пошли самым простым путём и выбрали одну тайловую разрезку для всех данных, удовлетворяющую обоим мирам:
для офлайна разрезка должна обеспечивать адекватный размер пакетов,
а для онлайна — адекватный трафик и плотность данных в отдельных скачиваемых тайлах.
Так мы пришли к единой разрезке — выгрузке всех данных на нечётные уровни квадродерева со смещенным диапазоном видимости шириной в два зума. На разных зумах выглядит она так:
Пропуск чётных уровней хорошо сократил размер офлайн-пакетов, но негативно сказывался на скорости загрузки, отрисовки и общем визуале — карта загружалась квадратной мозаикой.
Баланс скорости и размера
Чтобы улучшить производительность, мы решили переосмыслить наш гибрид и вернуть гибкость в управлении тайловыми разрезками.
Баланс нашёлся в разделении всех данных на две разрезки разной специфики:
недетальная — для больших по площади объектов (основные дороги, реки и леса), с выгрузкой на несколько уровней квадродерева с относительно широкими диапазонами видимости,
детальная — для всех остальных объектов, с выгрузкой на каждый уровень до z15 с диапазонами видимости шириной в один зум.
Так мы получили небольшой прирост в размере офлайн-пакетов, но заметный буст в скорости отрисовки кадров и полезный визуальный эффект — быстрозагружаемую подложку в виде недетальных тайлов до полной загрузки всей видимой сцены. И ещё один приятный сайд-эффект от большего количества небольших тайлов — улучшение распараллеливания загрузки.
Результаты
Совсем не трогая движок, а просто расслоив данные по двум отдельным тайловым разрезкам, мы получили:
увеличение размеров офлайн-пакетов в среднем на +15%,
но при этом уменьшение среднего времени отрисовки кадров до -20%,
и классный визуальный эффект быстрой информативной подложки, позволяющий с бо́льшим комфортом скроллить карту без мозаичной загрузки тайлов.
Теперь конфигурация тайловых разрезок в конечных приложениях может быть настроена на любой сетап, нужно лишь указать, откуда вытягивать тайлы каждой разрезки и на каких зумах какой уровень тайлов загружать. Этим мы собираемся воспользоваться в ближайшем будущем, выделив часть данных в ещё одну разрезку с единственным 16 уровнем для красивых иммерсивных данных на близких зумах, но только для пользователей онлайна — так мы облегчим офлайн-пакеты.
Если захочешь работать в нашей команде, у нас открыто четыре вакансии: C++ Team Lead, Rendering engineer C++, C++ разработчик, Senior QA-инженер.
