Десять лет алгоритму Slug / Хабр

Алгоритм Slug, используемый для рендеринга на GPU шрифтов непосредственно из кривых Безье, был разработан осенью 2016 года, а значит, в этом году мы отмечаем десятилетие его рождения. В середине 2017 года я опубликовал в JCGT статью об этой методике, а вскоре после этого моя компания продала первую лицензию на версию 1.0 Slug Library. С тех пор Slug многократно лицензировался разработчиками видеоигр, а также компаниями, специализирующихся в научной визуализации, CAD, редактировании видео, медицинском оборудовании и даже создании планетариев. Среди наших клиентов Activision, Blizzard, id Software, 2K Games, Ubisoft, Warner Brothers, Insomniac, Zenimax и Adobe. Slug оказался моим самым успешным программным продуктом.

Изначально я создавал Slug с целью улучшения рендеринга текста в C4 Engine, шрифты которого должны выглядеть идеально не только в GUI, но и внутри игровых уровней, где они могут быть очень крупными и отображаться под разными углами. Недавно я использовал Slug в создании редактора формул Radical Pie, в котором, разумеется, необходим крайне качественный рендеринг шрифтов, а также векторной графики для таких обозначений, как скобки, знаки корня и чисто графических элементов наподобие стрелок и выделения математических вы��ажений. Кроме того, Slug используется для рендеринга всего интерфейса пользователя внутри основного окна редактирования и всех диалоговых окон.

В этом посте я расскажу об изменениях в методике рендеринга с 2017 года, когда была опубликована научная статья и выпущена первая версия Slug Library. Завершается статья важным объявлением для тех, кто захочет реализовать алгоритм Slug в собственных проектах.

Эволюция рендеринга

Slug рендерит на GPU текст и векторную графику непосредственно из данных кривых Безье, не применяя текстурные карты, содержащие заранее вычисленные или кэшированные изображения. Когда имеешь дело с погрешностями округления чисел с плавающей запятой, сложно реализовывать всё это надёжным образом, обеспечивая при этом быстрые и качественные результаты. Алгоритм ни в коем случае не должен создавать артефакты наподобие пропущенных пикселей, пятен или линий, и гарантированное отсутствие таких проблем должно быть доказано математически. Под высокой скоростью подразумевается, что алгоритм может рендерить любой разумный объём текста на игровых консолях 2016 года без существенного снижения частоты кадров. Под качественными результатами подразумевается получение красивого текста с антиалиасингом, плавными кривыми и острыми углами в любых масштабах и под любыми углами обзора. Принципы, благодаря которым алгоритм рендеринга Slug достигает всех этих целей, вкратце приведены на схеме ниже. (Версия в PDF.)

Методика определения параметра root eligibility и вычисления winding number, отвечающих за надёжность, практически не изменилась с 2017 года. Однако некоторые другие части кода рендеринга, описанные в научной статье, за прошедшие годы всё же менялись. Я вкратце объясню небольшие изменения, а потом перейду к важному дополнению, названному dynamic dilation («динамическое расширение»), которому посвящу отдельный раздел.

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

В разделе Extensions в конце научной статьи я говорю о суперсэмплинге. Хоть он и необязателен для рендеринга текста произвольного размера, адаптивный суперсэмплинг был реализован в ранних версиях Slug для улучшения качества текста, который отрисовывается в очень маленьком размере. Если маленький текст рендерился в 3D-сцене очень далеко, то суперсэмплинг существенно снижал величину алиасинга при движении камеры, а поскольку он был адаптивным, количество сэмплов в случае большого текста всё равно было равно единице. Я решил избавиться от суперсэмплинга, потому что (а) он влиял только на настолько маленький текст, что он всё равно был едва читаем, и (б) проблема алиасинга крошечного текста в большой степени решалась описанной нише техникой расширения. Кроме того, устранение суперсэмплинга существенно упростило пиксельный шейдер. (Условная компиляция и так устраняла код суперсэмплинга, когда он был отключен, поэтому его удаление не приводило к ускорению ни одного шейдера с одинарным сэмплированием.)

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

Динамическое расширение

После выпуска Slug Library в алгоритм рендеринга было внесено одно серьёзное усовершенствование. Динамическое расширение решает проблему, о которой я говорил в посте 2019 года. До появления динамического расширения пользователь должен был вручную задавать постоянное расстояние, на которое должен расширяться ограничивающий полигон глифа для полной растеризации частично перекрытых пикселей. У такого подхода было два недостатка: (а) если выбрать слишком маленькое расстояние, то при рендеринге глифов меньше определённого размера по их границам возникали артефакты алиасинга, (б) любое выбранное расстояние было слишком большим для глифов, превышающих определённый размер, из-за чего оставалось пустое пространство, снижавшее производительность.

Благодаря динамическому расширению оптимальный вариант выбирается автоматически; он заново вычисляется в вершинном шейдере при каждом рендеринге глифа. Методика использует текущую матрицу model-view-projection (MVP) и размеры вьюпорта, чтобы определить, насколько вершину нужно сместить наружу вдоль направления нормали в пространстве объектов, чтобы увеличить ограничивающий полигон на половину пикселя в пространстве вьюпорта. Благодаря этому центры всех частично перекрытых пикселей находятся внутри ограничивающего полигона для того, чтобы растеризатор их обрабатывал. При перспективном отображении текста расстояние расширения будет разным для каждой вершины. Код всегда вычисляет оптимальное значение, поэтому не добавляет ненужные границы, из-за которых ресурсы GPU тратятся впустую.

Вычисления динамического расширения, выполняемые в вершинном шейдере, приведены в показанной выше схеме, но я пока не показывал, как вывел их. Наша цель заключается в нахождении расстояния , на которое нужно сместить позицию вершины в пространстве объектов вдоль вектора её нормали $\mathbf n = (n_x, n_y, 0, 0)$ , чтобы это соответствовало расширению на полпикселя ограничивающего полигона в пространстве вьюпорта. Нормаль не имеет единичной длины, а отмасштабирована так, чтобы указывать на новое местоположение вершины в случае, если обе соседние стороны ограничивающего полигона были смещены на одну единицу расстояния (см. схему). Сначала мы вычисляем расстояние вдоль направления единичной нормали $\hat{\mathbf n} = (\hat n_x, \hat n_y, 0)$ , а затем применяем его к исходному вектору нормали , чтобы получить новую позицию вершины $\mathbf p + d\mathbf n$ .

Применив матрицу MVP (имеющую размер 4×4), перспективное разделение и масштабирование вьюпорта на его ширину и высоту к позиции пространства объектов, смещённой на расстояние в направлении единичной нормали $\hat{\mathbf n}$ , мы можем выразить разности $\Delta x$ и $\Delta y$ в пространстве вьюпорта следующим образом:

$\begin{split}\Delta x &= \dfrac{w}{2}\left[\dfrac{m_{00}(p_x + d\hat n_x) + m_{01}(p_y + d\hat n_y) + m_{03}}{m_{30}(p_x + d\hat n_x) + m_{31}(p_y + d\hat n_y) + m_{33}} - \dfrac{m_{00}p_x + m_{01}p_y + m_{03}}{m_{30}p_x + m_{31}p_y + m_{33}}\right] \\ \Delta y &= \dfrac{h}{2}\left[\dfrac{m_{10}(p_x + d\hat n_x) + m_{11}(p_y + d\hat n_y) + m_{13}}{m_{30}(p_x + d\hat n_x) + m_{31}(p_y + d\hat n_y) + m_{33}} - \dfrac{m_{10}p_x + m_{11}p_y + m_{13}}{m_{30}p_x + m_{31}p_y + m_{33}}\right].\end{split}$

Если выполнить присвоение $(\Delta x)^2 + (\Delta y)^2 = (\frac{1}{2})^2$ , то смещение в пространстве вьюпорта составит половину пикселя. Нам нужно всего лишь найти из этого уравнения , но делать это довольно неудобно. Перемножив всё, максимально упростив и записав в виде квадратного уравнения для , получим:

$\begin{split}&{\large[}w^2(m_{03} (m_{30}\hat n_x + m_{31}\hat n_y) - m_{33}(m_{00}\hat n_x + m_{01}\hat n_y) + (m_{00}m_{31} - m_{01}m_{30})(p_x \hat n_y - p_y \hat n_x))^2 \\ & + h^2(m_{13} (m_{30}\hat n_x + m_{31}\hat n_y) - m_{33}(m_{10}\hat n_x + m_{11}\hat n_y) + (m_{10}m_{31} - m_{11}m_{30})(p_x \hat n_y - p_y \hat n_x))^2 \\ & - (m_{30}p_x + m_{31}p_y + m_{33})^2(m_{30}\hat n_x + m_{31}\hat n_y)^2{\large]}d^2 - 2{\large[}(m_{30}p_x + m_{31}p_y + m_{33})^3(m_{30}\hat n_x + m_{31}\hat n_y){\large]}d \\ & - (m_{30}p_x + m_{31}p_y + m_{33})^4 = 0.\end{split}$

Добавив обозначения $s = m_{30}p_x + m_{31}p_y + m_{33}$ и $t = m_{30}\hat n_x + m_{31}\hat n_y$ , можно записать это как

$\begin{split}&{\large[}w^2(s(m_{00}\hat n_x + m_{01}\hat n_y) - t(m_{00}p_x + m_{01}p_y + m_{03}))^2 \\ & + h^2(s(m_{10}\hat n_x + m_{11}\hat n_y) - t(m_{10}p_x + m_{11}p_y + m_{13}))^2 - s^2 t^2{\large]}d^2 \\ & - 2s^3td -s^4 = 0.\end{split}$

Введя дополнительные обозначения:

$\begin{split}u &= w(s(m_{00}\hat n_x + m_{01}\hat n_y) - t (m_{00}p_x + m_{01}p_y + m_{03})) \\ v &= h(s(m_{10}\hat n_x + m_{11}\hat n_y) - t(m_{10}p_x + m_{11}p_y + m_{13}))\end{split}$

мы получим упрощённое квадратное уравнение

имеющее решения

$d = \dfrac{s^3t \pm s^2\sqrt{u^2 + v^2}}{u^2 + v^2 - s^2t^2}.$

Выбрав решение с плюсом, мы получим расстояние вдоль вектора единичной нормали, на которое нужно сместить вершину наружу, чтобы получить расширение на полпикселя. Чтобы глиф рендерился в исходном размере, необходимо также сместить типографские координаты сэмплирования. С каждой вершиной хранится обратная матрица Якоби размером 2×2, дающая нам информацию, необходимую для преобразования смещения в пространстве объектов в вектор типографского смещения. До инвертирования матрицы Якоби она представляет собой верхнюю левую часть матрицы преобразования размером 2×2, преобразующую типографские координаты в координаты пространства объектов с учётом масштаба, растяжения, сдвига и отражения по осям координат.

Объявление о патенте

В 2019 году я получил патент на алгоритм Slug и юридически имею на него исключительные права до 2038 года. Но мне кажется, что это слишком долго. Патент уже послужил свою службу, и я считаю, что удерживание прав на него больше никому не приносит пользы. Поэтому с сегодняшнего дня я окончательно и бесповоротно делаю патент на Slug общественным достоянием. Это означает, что теперь каждый может свободно и без лицензии реализовывать алгоритм Slug для любых целей, не беспокоясь о нарушении прав интеллектуальной собственности. (Для специалистов сообщу, что моя компания заполнила форму SB/43 Ведомства по патентам и товарным знакам США и уплатила пошлину на отказ от срока действия патента #10,373,352 с 17 марта 2026 года.)

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