Отрисовка векторной графики — триангуляция, растеризация, сглаживание и новые варианты развития событий23.02.2017 23:18

В далёком 2013 м году вышла игра Tiny Thief, которая наделала много шуму в среде мобильной Flash (AIR) разработки из-за отказа от растровой графики в билдах, включая атласы анимации и прочего — всё что было в сборке хранилось в векторном формате прямиком из Flash редактора.
Это позволило использовать огромное количество уникального контента и сохранить размер установочного файла до ~70 мегабайт (apk файл из Google Play). Совсем недавно снова возник интерес к теме отрисовки векторной графики на мобильных устройствах (и вообще к теме отрисовки вектора с аппаратной поддержкой), и меня удивило отсутствие информации «начального» уровня по этой теме. Это обзорно-справочная статья по возможным способам отрисовки вектора и уже существующим решениям, а так же о том, как подобные вещи можно сделать самостоятельно.

Основной способ

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

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

Слева направо —

исходник в Inkscape,
результат триангулирования с низким количеством треугольников,
получившиеся треугольники

Причина таких обходных путей простая — графическая карта умеет эффективно работать только с вершинами, треугольниками и пикселями (про GPGPU немного другая история, но в данном контексте стоит только упоминания вскользь). Если же рисовать математически верные представления моделей с помощью CPU, то это будет занимать намного больше времени. Поэтому просто триангулируем и отправляем графической карте на отрисовку в сыром виде, как есть.

Подводные камни

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

Field study

Все описанные ниже вещи я проверял с помощью Adreno Profiler, NVIDIA PerfHUD ES и Unity (проверка работоспособности предложенных вариантов решения).

Вот что покажет Adreno Profiler если включить режим цветной сетки:

То есть отрисовка тем самым методом триангуляции. Вершины при этом красятся напрямую, без текстур (параметр color у вершин).

Вот что находится в альфа буфере (очевидно у Adreno GPU есть такое понятие как «альфа-буфер»):

По краям объектов тонкая однопиксельная полоска. Интересно, что на гранях между соседними объектами (белый фон-цветная буква) альфа канал «белый», то есть весь логотип рисуется одним проходом, а сглаживание внутри подобных объектов реализовано немного другим способом.
Шейдер:

{
    lowp vec4 fcolor;

    // Обратите внимание что color отдельно
    fcolor = color;

    // А прозрачность отдельно, через параметр вершины factor
    fcolor.a *= factor.a;

    fcolor = fcolor;
    gl_FragColor = fcolor;
}

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

Сборка по кускам

Написав простой парсер, получилось восстановить исходный меш в Unity. Но меня ждала странная картина:

Рамочки без сглаживания.
В режиме просмотра сетки тоже не видно заполняющих треугольников:

Долго не мог понять в чём дело. Оказалось, что заполняющие треугольники вывернуты в другую сторону. Это становится видно, если посмотреть на логотип с другой стороны:

Также заметно, что между элементами логотипа присутствуют пустые линии, которые заполнены градиентами (градиент сделан с помощью закрашивания вершин в соответствующие цвета), и при этом нет сглаживания.

Если убрать backface culling в шейдере, то получим то, что хотели получить в итоге:

Но возникает интересная особенность — если приближать этот объект к камере, то сглаживание становится слишком заметным и выглядит как размытие:

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

Статистика

Достаточно интересно посмотреть сводную информацию об отрисовке персонажей, в среднем каждый герой (стражник, повар) в триангулированном виде составляет около 3–4 тысяч треугольников. Это примерно как хорошего качества лоу-поли 3Д модель. Сетка настолько плотная, что кажется что объект отрисован текстурой:

Логотип занимает почти 9 тысяч треугольников. Общее количество draw calls в среднем около сотни (было бы намного больше, если бы задний фон не рисовался в виде текстуры), но ФПС стабильно максимальный даже на стареньком ZTE V811 (Билайн смарт 2).

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

С ног на голову

SDF

Если выставить ограничение на количество цветов векторного изображения, то можно пойти по совершенно другому пути. Допустим, что у нас есть простая векторная одноцветная иконка:

Её можно «сжать» почти без потери качества с помощью Signed Distance Field. Суть заключается в том, что мы храним не саму текстуру, а информацию о расстоянии пикселей до границы иконки. Значение на границе обычно считается равным 0.5. Всё что больше считается «внутри» иконки. Всё что меньше — «снаружи». По факту неважно в какую сторону перевешивается граница — иногда можно сделать меньше 0.5 внутри и больше 0.5 снаружи. Для наглядности (чёрные иконки на белом фоне) я покажу именно такой вариант.

Размазанный таким образом игральный кубик выглядит вот так:

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

В интернете и, в частности, на хабре достаточно много статей про SDF, я приведу их в конце статьи.

На картинке хорошо видно различие в качестве между обычной текстурой и двумя вариантами SDF. При увеличении обычной картинки становятся явно видны размытости. Увеличивая же SDF текстуру, мы в любом случае получим резкие границы. Причём даже уменьшив размер текстуры в два раза, наличие артефактов остаётся почти незаметным (про увеличение качества сырой SDF текстуры можно написать отдельную статью). Артефакты, в отличие от обычной текстуры, проявляются в виде сглаженной лесенки на скошенных краях иконки. Это обусловлено тем, что пиксели идут ровно по горизонтали и вертикали, и при уменьшении размера изображения также уменьшается точность аппроксимации косой прямой с помощью двух перпендикулярных (напомню что мы аппроксимируем вектор нормали к границе).

Шейдер для отрисовки будет самую малость сложнее, чем простое чтение текстуры.
В экспериментах я попробовал много разных вариантов, в т.ч. и вариант из статьи [2], в общем виде это выглядит примерно так:

float4 frag (v2fSDF f) : SV_Target {
    float2 uv = f.uv;
    half4 texColor = tex2D(_MainTex, uv);
    // Альфа канал - расстояние
    half distance = texColor.a;
    // Сила сглаживания краёв
    half smoothing = _Smoothing;
    // Сдвиг границы иконки - по умолчанию _Dilate = 0.5
    half2 range = half2(_Dilate - smoothing, _Dilate + smoothing);
    // Итоговое сглаживание (и оно же - полупрозрачность)
    half totalSmoothing = smoothstep(range.x, range.y, distance);

    half3 rgb = f.color.rgb;

    return float4(rgb, totalSmoothing);
}

Стоит отметить, что в данном случае RBG канал текстуры выбрасывается и в расчётах не участвует (к этому мы ещё потом вернёмся). Настраивать _Smoothing можно либо вручную под текущий размер текстуры на экране (но тогда будет та же проблема при увеличении, что и была в случае с отрисовкой через меши), либо использовать cg функцию fwidth, которая примерно оценивает размер текущего фрагмента относительно экрана и «подстраивает» сглаживание под относительный размер иконки на экране.

Поскольку основным ограничением метода SDF является необходимость «бинарности» (одноцветность) исходного символа, наиболее часто его применяют при отрисовке текста — настраивая и видоизменяя варианты обработки одной и той же SDF текстуры, можно создавать обводку, тень, размытие и т.д. [1]. Менее популярным способом использования SDF является отрисовка одноцветных иконок (как в случае с изображением игральной кости), но по большей части это просто частный случай текстового символа.
Ещё одним минусом подобного подхода является потеря резких граней и углов:

Слева — оригинальная текстура. Справа — SDF уменьшенного размера

И ещё пример с текстом из статьи [3]:

Решение проблем по мере поступления

Есть примеры реализации подобного алгоритма, сохраняющего острые углы [4][5]:

Краткая суть алгоритма заключается в следующем:
«сырой» SDF скругляет углы из-за того, что чем дальше от него пиксели, тем сильнее он скругляется. Происходит это из-за того, что к углу нельзя провести перпендикуляр (производная функции в этой точке не существует) — много пикселей будут считать расстояние по радиусу окружности, центром которой как раз и является угол. Этого можно избежать, если отследить все углы символа, проверив разрывы плавно идущей кривой. А затем, используя таблицу истинности, определить, должен ли быть закрашен квадрант угла или нет. То есть углы обычно закрашиваются пересечёнными SDF картами, записанными в разные каналы, а конечное значение пикселя считается по медиане векторов из трёх каналов.
Разумеется я не могу вместить всю статью на 90 страниц в один абзац, поэтому советую посмотреть её полностью [5].
Были и более ранние попытки сделать что-то подобное с пересечением разных полей раскиданных по каналам, но некоторые варианты не предполагают наличие хитрых возможностей добавления тени, обводки или увеличения толщины символа, в отличие от описанного примера (из-за того что фактически там не остаётся поля расстояний как такового).

Меньше каналов — больше точности

В твиттере есть товарищ, который всеми правдами и неправдами делает что-то подобное, но с одним каналом:

Если посмотреть разные ссылки в его твиттере, то можно наткнуться на некоторые варианты реализации. Насколько я понял, подход отличается от стандартного SDF тем, что не используется фактическое расстояние до границ (чтобы избежать того самого округления вокруг угла-центра), а используется немного переинтерпретированная фигура, углы которой продолжаются дальше. Это позволяет избавиться и от скругления углов и от нескольких каналов, упрощая шейдер, и уменьшая общее количество информации, требуемое на представление подобных фигур.
Также у этого товарища есть шейдер, который в реальном времени считает distance field для кривой безье на GPU, но там требуются десктопные вычислительные мощности даже для одной кривой (которая задаётся параметрически и формула её лежит «прямо в шейдере»). Если покрутить настройки и код, то можно посмотреть само поле расстояний без закрашивания и модуляции:

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

Возвращаемся к истокам

Также можно пойти по третьему пути — не хранить растровую информацию о каком-либо символе, а рисовать, так скажем, «из печки» — напрямую из векторного представления кривых. Проблема в том, что относительно сложно передать информацию о кривых на графическую карту без потери производительности. Есть несколько статей, описывающих подобные методы:
GPU text rendering with vector textures [3], а у Microsoft даже есть патент.
Если кратко, то суть в следующем:
Разделяем символ на ячейки, для каждой ячейки делаем карту пересечений кривых с лучами, пущенными под разными углами и пересекающими эту ячейку. Смотрим количество пересечений и расстояние, на которых возникли эти пересечения. Данные о кривых хранятся в виде скомканной текстуры, в которой заданы координаты кривых безье. Одна кривая безье — это 3 или 4 параметра в зависимости от степени этой кривой. Выше 4 го параметра кривые обычно не берут. Шейдер занимается тем, что в зависимости от текущей отрисовываемой ячейки и параметров текстуры, присутствующих на этой ячейке, считывает необходимые пиксели из референсной текстуры и использует их для восстановления аналитического вида кривой на GPU.

Не всё так радужно.

Минусом подобных подходов является использование относительно большого количества операций чтения текстуры. Я как-то имел дело с реалтаймовым рендерингом теней с tap blur размытием на мобильных устройствах, и любые Dependent Texture Reads (DTS — я не нашёл общепринятого аналога на русском) существенно ухудшали производительность. Если очень грубо — DTS возникают, когда координаты чтения текстуры становятся известны только во fragment shader, то есть непосредственно при отрисовке пикселя. Обычно высокая скорость чтения текстуры во fragment shader обуславливается тем, что конкретная интерполированная текстурная координата пикселя становится известна сразу после работы vertex shader, то есть видеокарта заранее читает нужный пиксель текстуры и отдаёт значение пикселя «бесплатно». Алгоритмы, поведение и степень трудозатрат определяется в первую очередь железом, на котором выполняются эти шейдеры. В OpenGL ES 3.0+ вроде как по большей части решается проблема производительности DTS, но на данный момент около половины мобильных устройств работает на OpenGL ES 2.0, поэтому пока надеяться на хорошее железо не стоит.
(источник от 6 февраля 2017)

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

Как жить дальше

У описанных выше методов есть следующие недостатки:

Качество картинки с методом триангуляции в меш существенно зависит от количества треугольников, что увеличивает и выделяемую память, и нагрузку на видеокарту (маленькие, но плотные сетки нагружают GPU сильнее, чем текстура того же размера, рисуемая на кваде).
SDF как есть не предполагает возможности отрисовки разноцветных элементов. Одним из условий является «бинарность» исходного изображения.
Методы «случайного доступа» к пикселям, определяющим различные векторные параметры, требуют большой вычислительной мощности на стороне GPU, в особенности много времени тратится на дополнительные чтения текстуры.

Поэтому у меня возникло желание предложить немного другой способ отрисовки разноцветной векторной графики, основанный на всё том же принципе SDF.

Вторая жизнь для SDF

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

Это внешний вид SVG файла. Можно заметить, что слои не перекрывают друг друга, а «стыкуются» между собой. При просмотре подобных векторных изображений через Inkscape становятся явно видны артефакты, присущие подобной стыковке этих слоёв:

Присутствие артефактов зависит от способа создания векторной графики, но пока возьмём именно этот вариант.

К действиям

Для каждого слоя сделаем свою SDF текстуру и выставим слои друг поверх друга в том же порядке, в котором они идут в SVG файле.

Слева направо — SVG Importer с включённым antialiasing, «слоёный» SDF, увеличенная начальная текстура. SVG Importer не смог нормально распарсить SVG из Inkscape, но суть не в этом.
Если сильно приблизить оба объекта, то различия выглядят примерно так:

Триангуляция:

на скруглениях заметна ступенчатость, ограниченная количеством треугольников (-)
на стыках могут возникать трещины по той же причине (-)
чёткие острые углы (+)
минимальный overdraw (полупрозрачная геометрия, которая перекрывает друг друга) (+)
общий объём треугольников — 568
выделяемая память — 44 Кб

Слоёный SDF:

прямой недостаток классического подхода — потеря острых углов (-)
существенный overdraw (-)
общее количество треугольников — 26 (текстуры рисуются не на квадах, а на автоматически сгенеренных мешах, опоясывающих текстуру по альфе. Для более простого варианта можно просто умножить количество слоёв на 2, то есть 10 треугольников) (+)
На трёхканальную текстуру размером 256×128, сжатую с помощью ETC4. Слои раскиданы по каналам, размер слоя 128×128, то есть три слоя на левой части атласа в отдельном канале и два слоя в правой части атласа. Выделяемая память — 16 Кб (+)

Основным недостатком этого метода по сравнению со всеми другими является существенный ovedraw. Чтобы нарисовать эту коробку требуется 4 полноразмерных слоя, помещённых друг на друга, плюс небольшой квад для пятого слоя (маленькая чёрточка). В худшем случае overdraw будет прямопропорционален количеству слоёв векторной картинки. Чем выше разрешение устройства, тем медленнее будет работать рендеринг.
Но в отличие от большинства пакетов по парсингу SVG файлов в меши, заранее подготовленные текстуры занимают существенно меньше места. Scaleform в этом плане пошли дальше — они генерили все меши на лету при загрузке сцены, не забивая архив приложения заранее созданными файлами. Для сравнения, начальный размер коробки составляет 4 Кб текста, то есть заранее собранный со сглаживанием меш векторной картинки занимает в 11 раз больше места, чем сырой текст, описывающий эту векторную фигуру.

Варианты — тысячи их

Я также наткнулся на другой способ конвертации цветного изображения в SDF вид. [6] Суть заключается в использовании bit planes (бит-карт) изображения для цветов. Бит-карты раскладывают яркости цвета по битам.
То есть берутся по порядку биты яркости и кладутся в отдельную бинарную текстуру. Всего на один канал изображения нужно 8 текстур. То есть 24 текстуры на цветное изображение без прозрачности.
Если пойти дальше и представить каждую такую двоичную текстуру как 8 ми битную SDF текстуру, то получается что для полноценного представления начального изображения потребуется 24 восьмибитных текстуры (а не 24 однобитных, которые получаются сразу после разложения на бит-карты).
Процесс восстановления начального цветного изображения из обработанных с помощью SDF бит-карт выглядит следующим образом:

Для каждой бит-карты каждого канала проверяется текущее значение SDF пикселя.
Если оно меньше 0.5, то исходный бит равен 1, если больше — 0. (0.5 в данном случае абстрактная величина, целые восьмибитные числа сравнивают со значением 127)
Собираются все значения всех бит по порядку и восстанавливается каждый канал по отдельности. Например, если у текущего пикселя красного канала значения бит получились равны ‭01110011‬, то яркость красного канала равна 115
Проходимся по всем каналам текущего пикселя таким же образом
Восстанавливаем значение цвета по трём каналам.

Хотя алгоритм этот достаточно хитрый, на деле качество оставляет желать лучшего:

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

Итоги

Полноценного решения «из коробки» пока предложить не могу, но есть идеи и попытки сделать кодировку SDF по палитрам с маркировкой контуров, что, возможно, позволит избавиться от хранения большого количества разных текстур для разных каналов и уменьшить overdraw.

Статья уже получилась очень большой, и мне пришлось существенно обрезать контент. Из того, что не рассказал:

Самый простой способ растеризации векторной графики без головной боли и бессонных ночей
Статья выше вывела меня на товарища TheRabbitFlash, который поделился огромным количеством информации по поводу растеризации векторной графики вообще и во Flash в особенности. Я провёл кучу экспериментов с разными вариантами отрисовки в «ванильном» Adobe Flash (который вроде как теперь Adobe Animate), но в целом ничего нового или интересного не обнаружил.
Я не затронул обсуждение Scaleform Mobile SDK с одним из разработчиков 5 Ants на форуме Starling, откуда изначально узнал про всю эту заваруху с векторной графикой и Tiny Thief, так как именно в то время я занимался разработкой на Flash + Starling.
Не рассказал про миллиард различных вариантов реализации сглаживания для каноничного способа отрисовки графики через триангуляцию.
Не рассказал про способы отрисовки градиентов векторных картинок (в Tiny Thief используются текстурные градиенты размером 256×1).

Signed Distance Field или как сделать из растра вектор
Рендеринг UTF-8 текста с помощью SDF шрифта
GPU text rendering with vector textures
Sharp Corners with Signed Distance Fields Fonts
Shape Decomposition for Multi-channel
Distance Fields
Signed Distance Field rendering of color bit planes