Slug — GPU‑рендеринг шрифтов из кривых Безье лицензирован MIT / Хабр

То, что сейчас известно как алгоритм Slug для рендеринга шрифтов непосредственно из кривых Безье на GPU, разработано осенью 2016 года, так что в этом году исполняется полных десять лет с момента его создания. В середине 2017 года я опубликовал работу об этом методе в JCGT, и вскоре после этого моя компания продала первую лицензию на Slug Library.

С тех пор Slug широко лицензируется в индустрии видеоигр и в ряде компаний, специализированных в таких областях, как научная визуализация, САПР, видеомонтаж, медицинское оборудование и даже планетарии. Среди наших клиентов — Activision, Blizzard, id Software, 2K Games, Ubisoft, Warner Brothers, Insomniac, Zenimax, Adobe и многие другие компании. Slug оказался самым успешным программным продуктом, который я когда‑либо создавал.

Изначально я создал Slug в стремлении улучшить рендеринг текста в движке C4, где шрифты должны были выглядеть отлично не только в графическом интерфейсе, но и внутри игровых уровней, где они могли отображаться очень крупно и под острыми углами. Совсем недавно я использовал Slug для создания редактора уравнений Radical Pie, которому, конечно же, требуется рендеринг шрифтов чрезвычайно высокого качества, а также векторная графика для таких элементов, как скобки, радикалы и чисто графических объектов, например, стрелок и выделений, прикреплённых к выражениям. Slug рендерит весь пользовательский интерфейс внутри главного окна редактирования и всех диалоговых окон.

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

Развитие рендеринга Slug

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

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

Принципы, благодаря которым Slug достигает всего этого, обобщены на следующей диаграмме:

Метод, определяющий допустимость корня [уравнения] и вычисляющий число обхода, который отвечает за надежность, сейчас практически такой же, каким был в первом релизе Slug. Однако некоторые другие части кода рендеринга из статьи за эти годы изменились. Прежде чем в отдельном разделе говорить о большом дополнении — динамической дилатации — кратко опишу меньшие изменения.

Оригинальная статья содержала описание «оптимизации разделения полос» (band split optimization), которую можно было включить, когда было известно, что глифы будут рендериться в большом размере. Она действительно ускоряла крупные глифы, но вносила некоторую дивергенцию в пиксельный шейдер, что могло немного снизить производительность для текста в малом размере.

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

В разделе «Расширения» [Extensions] в конце статьи обсуждался суперсэмплинг. Адаптивный суперсэмплинг не был необходим для рендеринга текста обычных размеров, но был реализован в ранних версиях для улучшения текста в очень малых размерах. Если маленький текст в 3D‑сцене рендерился вдали, то суперсэмплинг значительно сокращал алиасинг при движении камеры, и поскольку он был адаптивным, количество сэмплов, взятых для текста большего размера, всё равно оставалось равным одному.

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

В «Расширениях» также говорилось о добавлении в пиксельный шейдер цикла для рендеринга разноцветных эмодзи, которые, по сути, представляют собой стек глифов, где все слои разноцветные. Цикл оказался неоптимальным, потому что многие слои часто покрывали лишь небольшую часть общей площади составного глифа, но вычисления рендеринга для каждого слоя всё равно выполнялись по всему ограничивающему полигону. Лучше оказалось рендерить набор независимых глифов друг над другом. Это увеличивало объём данных вершин, зато каждый слой мог иметь собственный ограничивающий полигон. Это снова упростило и ускорило код пиксельного шейдера.

Динамическая дилатация

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

Это имеет два недостатка: а) если выбрать слишком малое расстояние, глифы, которые рендерятся ниже определённого размера, вдоль своих границ покроются артефактами алиасинга, и б) для глифов выше определённого размера любое выбранное расстояние будет слишком большим, оставит пустое пространство. Последнее приведёт к неоправданному расходу ресурсов GPU.

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

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

Вычисление динамической дилатации в вершинном шейдере показано на диаграмме выше, но я нигде не приводил вывод. Итак, вот он.

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

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

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

$\Delta x = \frac{w}{2} \left[ \frac{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}} - \frac{m_{00}p_x + m_{01}p_y + m_{03}}{m_{30}p_x + m_{31}p_y + m_{33}} \right]$ $\Delta y = \frac{h}{2} \left[ \frac{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}} - \frac{m_{10}p_x + m_{11}p_y + m_{13}}{m_{30}p_x + m_{31}p_y + m_{33}} \right]$

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

Перемножим, упростим, насколько возможно, и запишем формулу относительно как квадратное уравнение:

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

Удобно принять $s = m_{30}p_x + m_{31}p_y + m_{33}$ и $t = m_{30}\hat{n}_x + m_{31}\hat{n}_y$ , тогда:

$\begin{aligned}[l]& \Bigl[ w^2 \bigl( s(m_{00}n_x + m_{01}n_y) - t(m_{00}p_x + m_{01}p_y + m_{03}) \bigr)^2 \\& {} + h^2 \bigl( s(m_{10}n_x + m_{11}n_y) - t(m_{10}p_x + m_{11}p_y + m_{13}) \bigr)^2 - s^2 t^2 \Bigr] d^2 \\& - 2s^3 t d - s^4 = 0\end{aligned}$

Дополнительно примем:

$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}))$

И, наконец, получим упрощённое квадратное уравнение:

Оно имеет решения:

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

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

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

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

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

В 2019 году я получил патент на алгоритм Slug, и юридически обладаю исключительными правами на него до 2038 года. Но считаю, что это слишком долго. Патент уже хорошо послужил своей цели, и его удержание никому не принесёт пользы. Поэтому, с сегодняшнего дня [17 марта 2026 года], я навсегда и безвозвратно передаю патент на Slug в общественное достояние.

Это означает, что любой человек может свободно реализовывать алгоритм Slug для любых целей без лицензии, и не нужно беспокоиться о нарушении каких‑либо прав интеллектуальной собственности.
Для всех юридических экспертов, читающих это: моя компания подала форму SB/43 в USPTO и оплатила пошлину за отказ от конечной части срока действия патента № 10 373 352, действующий с 17 марта 2026 года.

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

Табличка для патента США № 10373352 — Табличка с патентом США № 10 373 352

Ссылки

Эталонные шейдеры Slug на GitHub.
Динамическая дилатация глифов, пост 2019 года.
GPU-Centered Font Rendering Directly from Glyph Outlines, Journal of Computer Graphics Techniques, 2017.
Сайт Slug Library.