Векторное представление шрифтов на GPU.

Автор: Вячеслав Е.

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

В силу небольших возможностей шейдеров версии 2.0 решил ограничится ч/б текстурами. Сразу понял, что интересно будет попробовать сделать отрисовку текста. Обычно для его отрисовки используют текстуры, в которых нарисованы изображения глифов. Если хочется рисовать большие буквы, то приходиться увеличивать текстуру со шрифтом или растягивать небольшие изображения.
Для реализации понадобилось написать программу, которая скидывает информацию о контурах, получаемых функцией GetGlyphOutline в изображение. В ней же был написан софтварный рендер для тестов.
GetGlyphOutline выдаёт различное представление для различных элементов глифа. Для прямых всё просто – список точек. А вот для загруглений используются квадратичные сплайны. Было решено их переводить в прямые линии, преобразуя сплайн в несколько отрезков. Формулы нашлись в msdn.


Не сразу понял, как для произвольной точки определить, находится ли она внутри контура или снаружи. Решение вскоре нашлось, возьмём отрезок с началом в текущей точке (x;y) и концом в (+inf;y), и найдём количество его пересечений с контуром глифа. Если число нечётное, то точка внутри.
Но конечно не всё так просто. Нельзя записать список этих отрезков в текстуру и заставить GPU делать сотню (а то и больше) выборок из текстуры в каждом фрагменте. На первых этапах была идея записывать в каждый тексель уравнение прямой, проходящей через него. Но для этого понадобилось довольно высокое разрешение текстуры, особенно для небольших деталей. Поэтому контур буквы делится на кусочки определённого размера:


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


Выглядит просто, но на деле за это отвечает довольно жуткий код. :) Перед тем как броситься и записать полученные данные в текстуру следует дополнительно уменьшить количество отрезков. Я решил уменьшать до 8, и к счастью довольно мало элементов выходили за эти рамки. Уменьшалось количество отрезков в два этапа. На первом этапе выбрасывались горизонтальные, так как они не вляли на результат. На втором этапе, если это было необходимо, выбрасывались отрезки, начиная с самого короткого, и только при условии, если начальная и конечная точка отрезка являлись, соответственно, конечной и начальной точками двух других. Таким образом их можно было удалять так, чтобы «не было разрывов» (с).

Отрезок представляется четырьмя координатами. Для первой реализации на GPU решил в один тексель писать информацию об одном отрезке. Данные одного кусочка занимали линейку из 8 пикселей. Если отрезков было меньше восьми, другие становились равны (0;0)-(0;0). Первый шейдер без оптимизаций раскладывался компилятором в 120 ALU инструкций, поэтому для проверки пришлось выбрать профиль ps_3_0. Вот код шейдера:
http://www.everfall.com/paste/id.php?s4jhxzuiklne

Тут видно отличный от описанного выше подхода к определению принадлежности точки внутренней части сегмента. По умолчанию мы находимся снаружи (белый цвет, wind = 1.0), и при каждом пересечении делаем wind*=-1.0; тоесть меняем белый цвет на чёрный и наоборот. Это плохое решение, цепочку из восьми зависимых умножений оптимизировать не получится. Просто на момент написания первого шейдера нормальный подход я ещё не придумал :). В начале шейдера видны довольно хитрые преобразования текстурной координаты. Смысл заключается в том, что текстурные координаты попадающие на одну линейку из 8 текселей преобразуются в координаты начала этой линейки. Так же получается вектор, который показывает, где мы находимся в пределах нашего квадратика.

Кроме того, в этом шейдере упускается бонус от векторных конвееров, и чтобы исправить это, понадобилось менять формат хранения данных в текстуре. Данные пришлось записывать так, чтобы в одном текселе была информация сразу о четырёх отрезках. Отрезок задаётся четрырьмя числами (x1; y1)-(x2; y2). Записывал немного в другом порядке (x1;x2;y1;y2), но это не имеет значения. В качестве небольших оптимизаций, пара расчётов была скинута в вершинный шейдер и в программу создания текстуры. К сожалению, деление не векторизуется, пришлось с этим жить. А жить стало намного легче. Шейдер влез в рамки ps_2_0 и раскладывается в 42 ALU инструкции:
http://www.everfall.com/paste/id.php?atdtm1rruzvc

Я наверно уже утомил читателей, поэтому самое время обсудить результаты.
Текстура для шрифта Arial получилась размером 512х512 при этом используется только 55% её пространства. Наверно можно упаковать глифы чуть лучше и тогда будет возможно уменьшить размер текстуры. Занимает изображение 1Мб, но сжимается rar’ом до 43кб. В dds векторное изображение сжимать не решился, так как результат заведомо будет ужасным.
Вот рендер полученной текстурки: