Всем привет! Навигация в приложении MAPS.ME является одной из главных особенностей, на которые мы делаем упор. Недавно мы рассказали вам про пешеходную навигацию. Сегодня я хочу вам рассказать о том, как мы отображаем навигационные данные в MAPS.ME. Под навигационными данными я подразумеваю линии маршрута, стрелочки для отображения маневров и положение пользователя на маршруте. Данный пост не коснется ни алгоритмов построения маршрутов по данным OSM, ни алгоритмов выделения маневров, а исключительно рендеринга. Заинтересовавшихся прошу под кат.
Начнем наш разговор с определения требований к отображению вышеупомянутых навигационных данных.
- Линия маршрута должна иметь переменную толщину в зависимости от масштаба карты. Очевидно, что на мелком масштабе эта линия должна быть достаточно тонкой, чтобы не перекрывать важные картографические ориентиры, и при этом достаточно толстой, чтобы быть различимой. На крупном масштабе ширина линии маршрута в идеале не должна превышать ширину дороги.
- Пройденная часть маршрута должна скрываться.
- На маршруте должны отображаться маневры. На текущий момент маневры у нас ограничиваются поворотами и должны отображаться в виде стрелочек, указывающих направление поворота.
- Линия маршрута может иметь произвольный цвет (включая полупрозрачность). Сейчас цвет однороден на всем протяжении маршрута.
- Положение пользователя отображается в виде стрелочки в направлении движения.
- Конец маршрута также отмечается специальной пиктограммой.
Теперь посмотрим, что у нас имеется в наличии, чтобы отобразить все это. От системы построения маршрута мы получаем:
- ломаную линию, которая определяет центральную ось линии маршрута;
- точки на ломаной линии, определяющие точку маневра (поворота);
- точку на ломаной линии, определяющую положение пользователя.
Кроме этого, у нас есть:
- цвет линии маршрута в формате RGBA;
- текстура со скином карты.
Точки на ломаной линии являются логическими, т.е. не входят в состав этой ломаной, и определяются как расстояние от начала линии. Например, 0.0 обозначает первую точку ломаной, а значение, равное длине ломаной, обозначает последнюю точку.
Теперь, когда мы определились со всеми входными условиями, приступим к разбору процесса рендеринга.
Формирование геометрии линии маршрута
Геометрию линии маршрута мы формируем как список треугольников. Так как в требованиях у нас значится переменная ширина, а переформировывать геометрию каждый кадр мы не можем себе позволить, то ширина линии выносится в uniform-переменную. В исходном состоянии все точки сгруппированы вдоль центральной оси. Для каждой вершины мы сохраняем вектор, в направлении которого мы будем эту вершину смещать в вершинном шейдере (назовем этот вектор нормалью). В итоге получим нечто похожее на рисунок ниже.
На рисунке видно, что в точке 3 сосуществуют 2 пары нормалей. Нормали, обозначенные на рисунке одним цветом, параллельны друг другу и разнонаправлены, и, если известна одна из них, вторая вычисляется инверсией вектора.
Чтобы в точке содержать 2 разнонаправленные непараллелельные нормали, точку необходимо продублировать, что происходит естественным образом при формировании полигонов. Также видно, что в месте перелома сформированные полигоны будут с одной стороны перекрываться, а с другой, наоборот, образовывать разрыв. На первый взгляд кажется, что перекрывающие полигоны не представляют проблемы. Так и есть до тех пор, пока линия маршрута полностью непрозрачна. В случае с полупрозрачной линией места пересечения полигонов будут темнее, следовательно, от них надо избавляться. Разрыв преодолеть гораздо проще, на его месте формируется полигональная вставка.
Для устранения перекрывающихся полигонов мы модифицируем нормали таким образом, чтобы сформированные полигоны не перекрывались. Для этого надо посчитать среднее для двух соседних нормалей и смещать обе точки вдоль нового вектора.
При таком подходе появляется одна тонкость. Нормали больше не являются нормализованными, поскольку нам может потребоваться значительно смещать вершины при острых углах. Как уже было упомянуто, разрывы в линии маршрута мы устраняем при помощи полигональных вставок. Мы поддерживаем 3 способа формирования этих вставок.
В первом случае полигональная вставка формируется триангуляцией части окружности, вписанной в сочленение сегментов линии маршрута. Во втором случае формируется острый угол, в третьем вставляется ровно один треугольник. Алгоритм генерации геометрии оценивает величину разрыва, степень расхождения нормалей и выбирает один из способов формирования полигональной вставки. Кроме всего прочего, на концах линии маршрута добавляются закругления. Они формируются тем же способом, что и вставки 1-го типа. В результате мы получили неразрывную геометрию линии маршрута, которую можем рисовать с любым цветом, в том числе полупрозрачно.
Отображение пройденной части маршрута
Для отсечения пройденной части маршрута самым очевидным решением является перегенерация геометрии по мере прохождения маршрута. Очевидно, этот способ будет затратным в плане производительности, и дело здесь даже не столько в сложности алгоритма генерации геометрии, сколько в затратах на пересылку новых вершинных и индексных буферов на GPU. Чтобы не перегенерировать геометрию на каждое обновление GPS-координат, мы придумали следующий подход. В каждую вершину сгенерированной геометрии мы добавляем величину, равную длине от начала линии маршрута до проекции этой вершины на линию маршрута.
Вследствие интерполяции значений между вершинами для каждого фрагмента мы будем обладать величиной, равной расстоянию от начала линии маршрута до данного фрагмента вдоль линии маршрута (DISTANCE_FROM_START). И при помощи следующего простого псевдокода шейдера часть линии маршрута будет отсекаться.
vec4 mainFragment()
{
vec4 color = ROUTE_LINE_COLOR;
if (DISTANCE_FROM_START < CURRENT_CLIP_DISTANCE)
color.a = 0.0;
return color;
}
Здесь ROUTE_LINE_COLOR — цвет линии маршрута, CURRENT_CLIP_DISTANCE — текущее пройденное вдоль маршрута расстояние. В данном подходе есть один небольшой недостаток: все вершины полигональной вставки будут давать проекцию в одну точку.
В приведенном примере точки 1, 2 и 3, входящие в полигональную вставку 2-го типа, проецируются на центральную ось линии маршрута со значением 7.4. На практике это будет выражено в образовании неровного среза линии на границе двух сегментов. Но, на самом деле, для нас такое поведение проблемой не является, поскольку срез (ровный или неровный) будет в подавляющем большинстве случаев находиться под пиктограммой, обозначающей положение пользователя.
Отображение маневров
Маневры, как я уже говорил, сейчас у нас ограничиваются стрелками с обозначением поворота. Главную проблему здесь представляет то, что на разных уровнях масштаба несколько стрелок должны сливаться в одну, чтобы не быть слишком мелкими и нечитаемыми.
Понятно, что и на этот раз нам хотелось обойтись без перегенерации геометрии на каждый кадр. Мы реализовали следующий алгоритм:
- Этап прекэширования. На данном этапе загружен в основном CPU. Линия, которая поступает от системы построения маршрута, разбивается на сегменты. Изначально мы оперировали одной неделимой линией, однако в процессе столкнулись с одной серьезной проблемой при построении длинного маршрута. К сожалению, при интерполяции длины на больших расстояниях мы уперлись в точность float-чисел. В приложении мы используем координаты Меркатора, что обуславливает достаточно большое количество значимых разрядов после запятой, а в шейдерах в OpenGL ES точность float-чисел уступает точности float-чисел в коде для CPU (2-16 при highp против 2-24). В итоге, в ходе вещественной арифметики в шейдерах мы теряли в точности, что приводило к появлению графических артефактов. Все наши попытки добиться нужной точности, во-первых, сильно усложняли фрагментный шейдер, а, во-вторых, всегда находилась такая длина линии маршрута, при которой это не работало. Поэтому мы приняли решение разбивать линию маршрута на такие отрезки, чтобы их длины не превышали определенного расстояния в системе координат Меркатора. Теперь величины интерполировались независимо друг от друга для каждого сегмента, что избавило нас от проблем с точностью. Чтобы в месте стыка сегментов не образовывалось разрывов, место разреза выбиралось специальным образом. Разрезался сегмент ломаной, наиболее близкий к желаемому месту, и при этом достаточно длинный для того, чтобы стрелка маневра не могла достигнуть точки разреза. В результате этого этапа мы получаем набор вершинных и индексных буферов с триангулированной геометрией линии маршрута.
- Этап обновления геометрических данных. Код, относящийся к этому этапу, выполняется на каждый кадр непосредственно перед рендерингом. Первой задачей данного этапа является выяснение, какие сегменты линии маршрута видны на экране. Затем для каждого видимого сегмента выполняется проецирование на него стрелочек маневров. Дело в том, что для рисования стрелочек мы используем ту же самую геометрию, что и для рисования самой линии маршрута, и в шейдер необходимо передавать массив координат начала и конца стрелочек. Для вычисления этого массива мы выполняем следующие действия:
- Проецируем стрелочки на сегмент линии маршрута как есть (исходный массив поступает из системы построения маршрута).
- Сливаем пересекающиеся стрелочки в одну (стрелочки имеют определенные ограничения по своей длине, как в координатах Меркатора, так и в пикселях, и поэтому могут пересекаться).
- Смещаем головную часть стрелки так, чтобы она полностью лежала на ровном участке маршрута (это необходимо во избежание искажений при выборке из текстуры).
В результате данного этапа мы определяем, какую именно геометрию мы должны нарисовать в текущем кадре, а также вычисляем массив с координатами начала и конца стрелок маневров. - Этап рендеринга. Здесь, понятное дело, мы загружаем GPU. Мы используем для рендеринга геометрию линии маршрута (нужные вершинные и индексные буферы мы определили на предыдущем этапе). Во фрагментный шейдер мы передаем массив границ и текстуру с изображением стрелочки. Каждый элемент массива границ содержит одномерную координату начала и окончания стрелочки, где координата является расстоянием от начала текущего сегмента линии маршрута. По этим координатам во фрагментном шейдере рассчитываются текстурные координаты для такого наложения текстуры на геометрию линии маршрута, чтобы формируемые стрелочки оказались в заданных областях. Чтобы стрелочка могла выступать за линию маршрута выставляется особая ширина линии (помните, мы задаем ее как uniform-переменную). Кроме того, текстура стрелочки разделяется на 3 части: хвостовую, головную и центральную. Центральная часть может растягиваться вдоль маршрута без искажений, хвостовая и головная части всегда сохраняют свои пропорции. Псевдокод фрагментного шейдера для рисования стрелочек ниже.
struct Arrow { float start; float end; }; Arrow arrows[MAX_ARROWS_COUNT]; sampler2D arrowTexture; vec4 mainFragment(float distanceFromStart, float v) { for (int i = 0; i < MAX_ARROWS_COUNT; i++) { if (distanceFromStart <= arrows[i].start && distanceFromStart < arrows[i].end) { float u = (distanceFromStart - arrows[i].start) / (arrows[i].end - arrows[i].start); return texture(arrowTexture, vec2(u, v)); } } return vec4(0, 0, 0, 0); }
Заключение
Сегодня мы рассмотрели процесс рендеринга навигационных данных в MAPS.ME. Наши решения не претендуют на роль универсальных, тем не менее, надеюсь, что вы нашли здесь что-то полезное для себя и ваших проектов. О рендеринге в MAPS.ME еще много чего можно рассказать, но нам хотелось бы понять, что интересно нашим читателям более всего. Пишите в комментариях, о чем вам интересно было бы прочитать и, возможно, следующий пост будет на тему, предложенную именно вами.
Комментарии (27)
agent10
23.09.2015 13:56+2С удовольствием почитал бы о рендеринге текста. Читал уже, что используете SDF и т.д. но хотелось бы детальнее.
OneArt
23.09.2015 15:16+3Пользуясь случаем хочу передать привет разработчикам maps.me. На днях платная версия взбесилась и прислала мне порядка 30 push уведомлений на всех языках мира. Телефон(Nexus) аж вскипел.
Proof
rokuz
23.09.2015 15:20+1Приносим извинения за досадный сбой.
> На днях платная версия взбесилась
Актуальная версия приложения полнофункциональна и бесплатна во всех сторах.OneArt
23.09.2015 15:27Точно помню, что только в платной версии была навигация, поэтому и купил ее, может давно это было просто.
В любом случае хорошо, что это не была глубокая ночь)
KoGor
23.09.2015 15:36Только что обновлял, после прочтения статьи, аналогичная ситуация. Сообщения иероглифами и вязью немного напрягли.
rokuz
23.09.2015 16:13Чтобы закрыть тему ложных пуш-уведомлений — vc.ru/n/maps-push-bag
В конце текста есть опрос, где вы можете предложить, как нас «наказать» за это :)
KoGor
23.09.2015 15:51Спасибо за статью, очень интересно!
Учитывая как вы заморочились со стыками сегментов маршрута, скажите, не собираетесь ширину линии маршрута менять в зависимости от типа дороги? А то сейчас что шоссе, что дворовый проезд — одинаковая толщина.
Да, для обычных смертных есть простой рабоче-крестьянский метод решения проблемы сложения ?-каналов в месте пересечения линий. Нужно задать буфер в несколько метров и перейти от линий к полигонам, после этого их можно просто объединить. Конечно это накладывает свои ограничения, но в большинстве простых случаев вполне рабочий вариант.rokuz
23.09.2015 16:22Мы постоянно работаем над улучшением визуальной привлекательности наших карт, если поймем, что есть реальная потребность в изменении ширины в зависимости от типа дороги — обязательно сделаем. Пока, на сколько мне известно, обращений по этому поводу очень мало.
Не могли бы поподробнее описать ваш метод? Что вы имеете ввиду под «задать буфер в несколько метров и перейти от линий к полигонам»?KoGor
23.09.2015 17:06Примерно так:
SELECT ST_Union(way_segments) AS whole_way FROM (SELECT ST_Buffer(way, buffer_radius) AS way_segments FROM planet_osm_line WHERE some_clause ) AS segments;rokuz
23.09.2015 17:34Что-то мне подсказывает, что ST_Buffer и ST_Union должны делать примерно то же самое, что я описал, чтобы результирующая геометрия не перекрывалась в местах стыков :)
Из системы построения маршрута к нам в графический движок приходит ломаная, по ней надо сгенерировать полигоны. Функции из Гео Баз Данных мы использовать не можем, просто мы уже не имеем этих баз на уровне приложения :) Данные, которые мы получаем из OSM, упаковываются и обрабатываются нашими алгоритмами, и такие красивые запросы нам уже не доступны.KoGor
23.09.2015 19:23Ну я и не говорил, что этот рецепт вам подойдёт, но может он пригодится кому-то другому =)
Viacheslav01
23.09.2015 18:59Интересно было прочитать, а еще интереснее, что я прошел точно таким же путем, генерируя маршруты движения для нашего приложения. За исключением стрелок, все один в один.
Я все велосипедил, а вы?
Просто это был первый опыт в 3D и не смог найти нужную информацию с ходу :)rokuz
23.09.2015 22:41Не совсем понял ваш вопрос. Если вы про то, собственный ли у нас движок для отрисовки, то да :) Можете даже назвать его велосипедом, если хотите. Однако, сторонних решений, полностью удовлетворяющих нашим потребностям и с подходящей лицензией, просто нет.
Viacheslav01
25.09.2015 12:37Просто интересно было, решения были придуманы или сделаны по подобию готового или описанного?
rokuz
25.09.2015 15:41Мы, конечно, пытаемся воспользоваться любой информацией, которую можем найти :) Интересные вещи иногда пишет Mapbox. Со стрелками сами разработали алгоритм рендеринга, хотя на оригинальность решения не претендуем.
DjOnline
26.09.2015 18:56Странно, ожидал именно на Хабре увидеть статью о новом дизайне Maps.me, а нашёл только на ЦП ( https://vc.ru/p/mapsme-design )
dns78
Добрый день!
Интересно узнать про:
1. Систему скинов в MapsWithMe.
2. Когда будут опубликованы обещанные в прошлом году исходники.
3. Вы по-прежнему используете antigrain для рендеринга?
rokuz
2. Ждите официального анонса;
3. Откуда информация, что мы используем antigrain?) AGG у нас только для рендеринга на Apple Watch.
dns78
2. Терпеливо жду, но хотелось бы, чтобы эпизодически всплывали новости в блоге — «дада, сорцы все же будут опубликованы».
3. Э. Я уже не помню. Вероятно, я когда-то потыкал палочкой ваш .so
Но это было еще очень задолго до всяких Apple Watch, MailRu etc., ближе к началу.
encyclopedist
Они таки сдержали слово: github.com/mapsme/omim
dns78
По поводу п.1 я чуть переформулирую.
Интересно было бы почитать про логику, которая привела к тому, что в maps.me нет до сих пор outdoor скина. Само приложение является чуть ли не эталоном того, как нужно писать карманные оффлайновые навигаторы, но некоторые решения меня ставят в тупик. Все прекрасно, но где контрастная схема? Под контрастной схемой я подразумеваю некое подобие цветовой гаммы, характерной для топографических карт — такой, которая бы, в отличие от текущей, хорошо бы читалась на ярком солнце, на которой бы более четко грунтовки отделялись от фона и т. д.
Zverik
У нас нет лишних дизайнеров, чтобы бросить их на разработку дополнительных стилей. Эта задача совсем не в приоритете, да и даже не в общем списке пожеланий. Но когда мы откроем исходники («ждите анонса», да, мы обещали открыть до конца года), любой сможет сочинить собственный картостиль в любых цветах и с любыми объектами, нарисованными в OSM.
dns78
Сколько нужно дизайнеров, чтобы собрать drules_proto.bin из hiking mapcss от stranger?
Zverik
Если имеется в виду стиль чепецк.net, то очень много: тот mapcss заточен под использование с mapnik и хитро выделанной базой PostGIS. Большинство элементов сработают в MAPS.ME, но не все. Нужно аккуратно пройтись по всем селекторам и убедиться, что они правильно обработаются приложением.
Проблема с MapCSS в том, что он у всех свой, пусть базовые правила и совпадают :)
dns78
Да, я про него. Я не заметил с ним проблем в maps.me, кроме известной темы с coastlines. Тестировал достаточно долго и по-разному.