Под капотом рендеринга навигационных данных в MAPS.ME23.09.2015 12:18

Всем привет! Навигация в приложении 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). В итоге, в ходе вещественной арифметики в шейдерах мы теряли в точности, что приводило к появлению графических артефактов. Все наши попытки добиться нужной точности, во-первых, сильно усложняли фрагментный шейдер, а, во-вторых, всегда находилась такая длина линии маршрута, при которой это не работало. Поэтому мы приняли решение разбивать линию маршрута на такие отрезки, чтобы их длины не превышали определенного расстояния в системе координат Меркатора. Теперь величины интерполировались независимо друг от друга для каждого сегмента, что избавило нас от проблем с точностью. Чтобы в месте стыка сегментов не образовывалось разрывов, место разреза выбиралось специальным образом. Разрезался сегмент ломаной, наиболее близкий к желаемому месту, и при этом достаточно длинный для того, чтобы стрелка маневра не могла достигнуть точки разреза. В результате этого этапа мы получаем набор вершинных и индексных буферов с триангулированной геометрией линии маршрута.
Этап обновления геометрических данных. Код, относящийся к этому этапу, выполняется на каждый кадр непосредственно перед рендерингом. Первой задачей данного этапа является выяснение, какие сегменты линии маршрута видны на экране. Затем для каждого видимого сегмента выполняется проецирование на него стрелочек маневров. Дело в том, что для рисования стрелочек мы используем ту же самую геометрию, что и для рисования самой линии маршрута, и в шейдер необходимо передавать массив координат начала и конца стрелочек. Для вычисления этого массива мы выполняем следующие действия:
1. Проецируем стрелочки на сегмент линии маршрута как есть (исходный массив поступает из системы построения маршрута).
2. Сливаем пересекающиеся стрелочки в одну (стрелочки имеют определенные ограничения по своей длине, как в координатах Меркатора, так и в пикселях, и поэтому могут пересекаться).
3. Смещаем головную часть стрелки так, чтобы она полностью лежала на ровном участке маршрута (это необходимо во избежание искажений при выборке из текстуры).
В результате данного этапа мы определяем, какую именно геометрию мы должны нарисовать в текущем кадре, а также вычисляем массив с координатами начала и конца стрелок маневров.
Этап рендеринга. Здесь, понятное дело, мы загружаем 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 еще много чего можно рассказать, но нам хотелось бы понять, что интересно нашим читателям более всего. Пишите в комментариях, о чем вам интересно было бы прочитать и, возможно, следующий пост будет на тему, предложенную именно вами.