Привет! Меня зовут Арсений Кононов. На прошлой неделе мы зарелизили трёхмерные развязки и тоннели, которые можно увидеть в режиме навигатора. Я расскажу о простой и гибкой технике, реализованной в графической подсистеме нашего графического движка для отображения плоских объектов на произвольной трехмерной поверхности. Например, линии маршрута на поверхности развязки.

Надеюсь, пост будет полезен интересующимся компьютерной графикой на уровне, абстрагированном от конкретных графических API, но ниже, чем абстракции, предлагаемые большими игровыми движками, такими как Unity или Unreal Engine.

Немного «дорожной» истории 2ГИС

Изначально развязки в 2ГИС рисовались совсем плоскими и нельзя было понять, какая дорога идёт поверх.

Несколько лет назад мы научились рисовать их так, чтобы линии разных уровней отображались не как перекрёсток, а как скрещивающиеся.

Сейчас 2ГИС переходит на более реалистичные карты — мы уже добавили красивые дома с текстурами и деревья, которые меняют цвет листвы в зависимости от сезона.

Но реалистичные карты невозможны без реалистичных дорог, трёхмерных развязок и тоннелей. И надо не просто поднять старую оранжевую линию и сгенерировать под ней подложку, а сделать так, чтобы потом легко добавить реалистичную ширину дороги и разметку.

На первый взгляд задача простая — посадить толпу людей рисовать модельки для развязок с опорами, разметкой и прочим. Но так пропадает очень важная возможность — пустить поверх этих развязок произвольные объекты, генерируемые в рантайме, например, линию маршрута и линии пробок, поскольку эти объекты должны быть согласованы со сложной трёхмерной геометрией дорог. Кроме того, подробные модели всех дорог увеличат объём загружаемых данных.

Нужен был способ нарисовать наши привычные плоские объекты — линии, пунктиры, полигоны, спрайты — поверх произвольного трёхмерного объекта. Причём с возможностью рисовать их в несколько независимых уровней развязки и непрерывного перехода объектов с одного уровня на другой. При этом плоские объекты не должны зависеть от высот развязки настолько, насколько это возможно.

Возможные подходы

Сначала мы проанализировали существующие подходы, так как вряд ли мы первые, кто столкнулся с подобной задачей 3D‑графики.

Декали

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

• Вырезать кусок меша не можем — объекты с независимой геометрией создаются в рантайме.

• Можно было бы попробовать техники наподобие screen‑space decals, но они требуют баундбокса накладываемого объекта. А мы не знаем, на какой высоте будет поверхность, при этом рядом может оказаться другая, на которой ничего рисовать не надо, и о ней мы не знаем вообще ничего.

Честное 3D

Простая отрисовка, сложные вычисления при подготовке геометрии, увеличенный объём загружаемых данных. То есть проецирование линий на трёхмерные поверхности при подготовке данных. Но так данные довольно сильно разбухнут, ведь на каждый отрезок линии надо добавить точки в местах пересечения с рёбрами поверхности. Хуже всего с проецированием спрайтов — вместо одной точки мы должны подготовить полноценную полигональную сетку, которая даже в самом простом случае будет иметь четыре вершины. Кроме того, станет очень сложно докинуть объекты из другого источника данных, например, линию маршрута — надо, чтобы она использовала те же самые высоты с большой точностью.

Наш подход

Нарисовать плоские объекты в текстуру, а затем использовать её для трёхмерных объектов.

• Не очень эффективны в плане памяти на текстуру, но легко реализуются.

• Не требуют от объектов дополнительных данных, кроме номера поверхности, на которую их надо нарисовать.

• Уже используются для рисования рельефа на 2gis.ru.

Что есть в данных

При разработке подхода отталкивались от опыта добавления рельефа на 2gis.ru и информации, которая уже выгружается в пакеты данных. Начнём с данных.

Плоские линии и уровни отрезков для их сортировки на развязках: число больше — линия рисуется позже. Никаких высот на каждую точку, только целые числа: нулевой, первый, второй уровень. Уровень отрезка, конечно, не высота, но уже хоть что‑то можно сказать — например, что один уровень равен 6,5 метрам.

Но пока сложно правильно сгенерировать уклоны. Например, возьмём простую линию, проходящую через 3 точки. У каждого отрезка задан один уровень. Возникает вопрос — в каких местах этих двух отрезков надо начинать плавное изменение высоты. Вот если бы были данные о высотах не для отрезков, а для вершин.

Идём выше по конвейеру, к данным, поступающим на вход утилиты подготовки пакета картографических данных. И видим, что уровень отрезка вычисляется по двум числам — уровням его начала и конца. «Вычисляется» — не совсем корректно, так как линия режется пополам: сначала отрезок начального уровня, потом отрезок конечного.

Это уже значительно лучше, ведь можно по середине отрезка поставить интерполированную высоту и получить дороги с уклоном, настроенном в редакторе карты.

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

И уже тут мы понимаем, что для отрисовки поверх развязки не хватит знания высот начала и конца. Теперь высота возле конца зависит от всех смежных дорог. Например, на рисунке красная дорога нарисована с простой интерполяцией, а зелёная — с учётом смежной дороги. Даже в таком простом примере разметка на зелёной дороге должна хранить слишком много информации о своём окружении. А ведь в будущем хочется дальше повышать детальность данных.

Вспоминаем, как сделан рельеф — сначала рисуется плоская карта. А потом она натягивается на трёхмерную сетку рельефа. В итоге объектам карты даже не надо знать о рельефе.

Остаётся только одна загвоздка — у большинства трёхмерных развязок есть скрещивающиеся участки, то есть когда один пролёт развязки проходит над другим, как на картинке ниже. И иногда расстояние по высоте может быть небольшим. Но определённо нельзя рисовать линии на дороге, проходящей снизу поверх верхней дороги.

Решение проблемы — разбить развязку на ярусы, внутри каждого из которых не будет скрещивающихся дорог. И, возвращаясь к данным, понимаем, что достаточно выбрать максимум из уровней начала и конца, которые уже есть в данных.

Построение по двум уровням, в отличие от выбора его произвольно, позволяет вычислить совпадающий ярус и для линии маршрута, в которую достаточно легко прокинуть уровни начала и конца.

Алгоритм отрисовки

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

• Отсортировать объекты по их ярусу

• Для каждого яруса в порядке возрастания:

  • нарисовать в отдельную текстуру плоские объекты с заданного яруса развязки или туннеля;

  • нарисовать на экран трёхмерные объекты, используя текстуру, содержащую плоские объекты. При отрисовке развязки на экран её полигоны должны пойти в соответствующую текстуру, найти на ней правильные координаты и нарисовать её поверх себя.

Сортировка уменьшает расход памяти и позволяет не вводить ограничений на максимальное количество ярусов. При сортировке по ярусам текстура объектов текущего очищается перед переходом к рисованию следующего, не создавая по текстуре на каждый ярус.

Сразу возникает вопрос, как выставить камеру при отрисовке плоских объектов, чтобы в кадр попали все объекты, которые видны на трёхмерных. Просто вид сверху не подойдет, поскольку объекты возле горизонта не получится нарисовать. Наиболее простым и довольно эффективным решением оказывается выставить камеру при отрисовке текстуры так же, как и основную. Такое расположение позволяет вычислять текстурные координаты из координат трёхмерного объекта простым проецированием на плоскость с последующим применением MVP‑матрицы.

Наглядно всё это можно продемонстрировать на типичном примере.

В первую очередь отрисовываются объекты, которые лежат в плоскости карты или могут быть отрисованы простым проходом с буфером глубины, например, бортики дорог.

Дальше начинается интересная часть: рисуем объекты первого яруса

Как только текстура готова, можем начинать рисовать первый ярус развязки на экран

И повторяем процедуру для второго яруса

На первый взгляд не видно различий между плоской текстурой и трёхмерным результатом. Различие становится очевидным, если наложить промежуточную текстуру на изображение на экране. Для контраста перекрасим эту текстуру в серый цвет.

Осталось только повторить процедуру для третьего яруса.

Вот собственно и всё — дальше только технические детали, без которых это всё не заработает.

Проблемы и решения

На практике оказывается, что нельзя просто отсортировать все объекты по ярусу. Так, например, объекты, не относящиеся к развязкам, у нас находятся в специальном нулевом ярусе. Простая сортировка по ярусу создаёт массу весёлых спецэффектов.

На самом деле, аналогичную проблему мы решили, ещё когда делали порядок отрисовки для развязок без ширины и высоты. Тогда мы в дополнение к разделению объектов по слоям (грубо говоря, по типу: дома, речки, заборы…) ввели дополнительную группировку этих слоёв и сортировали только внутри группы. Порядок самих групп остаётся фиксированным. Это позволяет очень легко настроить объекты как объекты, которые должны рисоваться всегда до развязок (поверхность земли) так и всегда после (дома и подписи). То есть всё плоское рисуется в первой группе, дороги — во второй, а дальше — дома и надписи.

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

Для решения проблемы увеличили размер текстуры так, чтобы объекты, выходящие за нижний край экрана, помещались в неё.

Но тут же при тестировании на реальных устройствах оказывается, что теперь приложение вообще падает. Теперь фреймбуфер может оказаться слишком большим, чтобы запихнуть в текстуру на некоторых устройствах. На FullHD (1920×1080) экране удвоение размера даёт размер текстуры 3840, довольно близкий к 4096 (максимальный размер текстуры, который гарантирует большинство устройств). Если устройство будет разрешать чуть меньшую текстуру или будет с экраном побольше, то создать такую текстуру уже не получится.

Решение — понизить разрешение настолько, чтобы текстуры хватило. Разумеется, нельзя понижать разрешение слишком сильно, чтобы разница между линиями на карте и на развязках была не очень заметна.

Итог

Трёхмерные развязки и тоннели уже успешно работают в боевом приложении. Описанное решение позволило минимизировать объём загружаемых данных и существенно уменьшить трудозатраты на сбор данных о трёхмерной геометрии дорог.