В последнее время появилось много фантастических исследований по 2D-рендерингу. Пётр Кобаличек и Фабиан Айзерман работают над Blend2D: это один из самых быстрых и точных CPU-растеризаторов на рынке, с инновационной техникой JIT. Патрик Уолтон из Mozilla изучил не один, а три разных подхода в Pathfinder, кульминацией чего стал Pathfinder v3. Раф Левиен построил вычислительный конвейер по технологии, описанной в научной статье Гана с коллегами о векторных текстурах (2014). Похоже, некое дальнейшее развитие получают поля расстояний со знаком: здесь независимо работают Адам Симмонс и Сара Фрискен.

Кто-то может спросить: а почему вокруг 2D так много шума? Это ведь не может быть намного сложнее, чем 3D, верно? 3D — совершенно другое измерение! Тут у нас на носу трассировка лучей в режиме реального времени с точным освещением, а вы не можете осилить невзрачную 2D-графику со сплошными цветами?

Для тех, кто не очень хорошо разбирается в деталях современного GPU, это вправду очень удивительно! Но в 2D-графике множество уникальных ограничений, которые чрезвычайно её усложняют. К тому же она не поддаётся параллелизации. Давайте прогуляемся по исторической дорожке, которая нас сюда привела.

Взлёт PostScript

В начале был плоттер. Первое графическое устройство, способное взаимодействовать с компьютером, называлось «плоттер» (графопостроитель): одно или несколько перьев, способных передвигаться по бумаге. Всё работает по команде «перо-вниз», затем чертёжная головка перемещается неким уникальным способом, возможно, по кривой, и поступает команда «перо-вверх». HP, производитель некоторых из самых ранних плоттеров, на управляющем компьютере использовал вариант BASIC под названием AGL, который затем отправлял команды плоттеру на другом языке, типа HP-GL. В 1970-е годы всё дешевле и популярнее становились графические терминалы, начиная с Tektronix 4010. Он показывал изображение с помощью ЭЛТ, но не обманывайтесь: это не пиксельный дисплей. Tektronix пришёл из индустрии аналоговых осциллографов, и эти машины работают, управляя электронным пучком по определённому пути. Таким образом, у Tektronix 4010 не было пиксельного вывода. Вместо этого вы посылали ему команды в простом графическом режиме, который мог рисовать линии, но, опять же, в режиме «перо вниз», «перо вверх».

Как и во многих других областях, всё изменило изобретение Xerox PARC. Исследователи начали разрабатывать новый тип принтера, более вычислительно выразительный, чем плоттер. Этот новый принтер работал на маленьком стековом тьюринг-полном языке программирования, похожем на Forth, и назвали его… Interpress! Очевидно, Xerox не смогла найти ему достойное применение, поэтому изобретатели покинули корабль и основали маленький стартап под названием Adobe. Они взяли с собой Interpress, а по мере исправления и улучшений тот изменился до неузнаваемости, так что ему дали другое название: PostScript. Помимо милого, тьюринг-полного стекового языка, в четвёртой главе оригинального справочного руководства PostScript Language Reference описана Imaging Model, которая почти идентична современным программным интерфейсам. Пример 4.1 из руководства содержит пример кода, который можно почти построчно перевести на HTML5 <canvas>.

/box {                  function box() {
    newpath                 ctx.beginPath();
    0 0 moveto              ctx.moveTo(0, 0);
    0 1 lineto              ctx.lineTo(0, 1);
    1 1 lineto              ctx.lineTo(1, 1);
    1 0 lineto              ctx.lineTo(1, 0);
    closepath               ctx.closePath();
} def                   }
                         
gsave                   ctx.save();
72 72 scale             ctx.scale(72, 72);
box fill                box(); ctx.fill();
2 2 translate           ctx.translate(2, 2);
box fill                box(); ctx.fill();
grestore                ctx.restore();

Это не совпадение.

Стив Джобс из Apple познакомился с инженерами Interpress во время своего визита в PARC. Джобс думал, что полиграфический бизнес будет прибыльным, и пытался купить Adobe ещё при рождении. Но Adobe выдвинула встречное предложение и в конечном итоге продала Apple пятилетнюю лицензию на PostScript. Третьим столпом в плане Джобса было финансирование небольшого стартапа Aldus, который делал WYSIWYG-приложение для создания PostScript-документов. Оно называлось PageMaker. В начале 1985 года Apple выпустила первый принтер, совместимый с PostScript — Apple LaserWriter. Сочетание Macintosh, PageMaker и LaserWriter мгновенно перевернуло полиграфическую индустрию с ног на голову, а новый хит «настольные издательские системы» укрепил за PostScript его место в истории. Основной конкурент Hewlett-Packard в итоге тоже купил лицензию на PostScript для серии конкурирующих принтеров LaserJet. Это случилось в 1991 году после давления со стороны потребителей.

PostScript медленно перешёл из языка управления принтером в формат файла. Умные программисты изучили, в каком виде команды PostScript отправляются на принтер — и начали создавать документы PostScript вручную, добавив в свои документы диаграммы, графики и рисунки, при этом PostScript использовался для вывода графики на дисплей. Возник спрос на графику вне принтера! Adobe это заметила и быстро выпустила формат Encapsulated PostScript, который представлял собой не более чем несколько специально отформатированных комментариев PostScript с метаданными о размере изображения и ограничениями на использование принтерных команд, таких как “page feed”. В том же 1985 году Adobe начала разработку Illustrator — приложения, где художники работали в формате Encapsulated PostScript в удобном UI. Затем эти файлы можно было перенести в текстовый процессор, который создавал… документы PostScript для отправки на принтеры PostScript. Весь мир перешёл на PostScript, и Adobe не могла быть ещё счастливее. Когда Microsoft работала над Windows 1.0 и хотела создать собственный графический API для разработчиков, основной целью было сделать его совместимым с существующими принтерами, чтобы графика отправлялась на принтеры так же легко, как экран. Этот API в конечном итоге выпустили как GDI — основной компонент, используемый каждым инженером во время стремительного роста популярности Windows в 90-е годы. Поколения программистов на платформе Windows начали неосознанно отождествлять векторную графику 2D с моделью изображений PostScript, закрепив за ней этот статус де-факто.

Единственной серьёзной проблемой PostScript была тьюринг-полнота: просмотр 86-й страницы документа означает сначала запуск скрипта для страниц 1-85. И это может быть медленно. Adobe узнала об этой жалобе пользователей и решила создать новый формат документов, у которого не было таких ограничений, его назвали “Portable Document Format” или для краткости “PDF”. Из него выбросили язык программирования, но графическая технология осталась прежней. Цитата из спецификаций PDF, глава 2.1, «Модель изображения»:

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

Когда консорциум W3C рассматривал претендентов на язык разметки 2D-графики в интернете, Adobe отстаивала PGML на основе XML, в основе которого лежала графическая модель PostScript:

PGML должен включать в себя модель изображений PDF/PostScript, чтобы гарантировать возможность масштабируемой 2D-графики, которая удовлетворяет потребностям как обычных пользователей, так и профессионалов графики.

Конкурирующий формат VML от Microsoft был основан на GDI, который, как мы знаем, основан на PostScript. Два конкурирующих предложения, которые по-прежнему представляли собой по сути PostScript, объединили вместе, так что W3C принял стандарт «масштабируемой векторной графики» (SVG), который мы знаем и любим сегодня.

Даже если он стар, давайте не будем притворяться, что инновации PostScript, принесённые в этот мир — что-то меньшее, чем технологическое чудо. У PostScript-принтера LaserWriter от Apple процессор был вдвое мощнее, чем у Macintosh, который его контролировал, просто для интерпретации PostScript и растеризации векторных путей до точек на бумаге. Это может показаться чрезмерным, но если вы уже покупали модный принтер с лазером внутри, то не нужно удивляться дорогому процессору. В своём первом воплощении PostScript изобрёл довольно сложную модель визуализации со всеми функциями, которые мы сегодня считаем само собой разумеющимися. Какая самая мощная, потрясающая особенность? Шрифты. В то время шрифты рисовались от руки линейкой и транспортиром и отливались на плёнку для фотохимической печати. В 1977 году Дональд Кнут показал миру, на что способна его система METAFONT, которую он представил вместе с текстовым редактором TeX, но она не прижилась. Она требовала от пользователя математического описания шрифтов, используя кисти и кривые. Большинство разработчиков шрифтов не хотели это изучать. А причудливые изгибы при малых размерах превращались в месиво: у принтеров того времени не было достаточного разрешения, поэтому буквы расплывались и сливались друг с другом. PostScript предложил новое решение: алгоритм «привязки» очертаний к более грубым сеткам, которыми оперировали принтеры. Это известно как «подгонка сетки» (grid-fitting). Чтобы предотвратить слишком большое искажение геометрии, они позволили шрифтам устанавливать «подсказки», какие части геометрии являются наиболее важными и что следует сохранить.

Оригинальная бизнес-модель Adobe заключалась в том, чтобы продавать разработчикам принтеров эту технологию шрифтов и продавать издателям специальные воссозданные шрифты с добавленными подсказками, поэтому Adobe по сей день продаёт свои версии Times и Futura. Кстати, это возможно, потому что шрифты, или, более формально, «гарнитуры», являются одной из пяти вещей, явно исключённых из закона США об авторском праве, поскольку их изначально обозначили как «слишком простые или утилитарные, чтобы быть творческими работами». Вместо этого защищается авторским правом цифровая программа, которая воспроизводит шрифт на экране. Таким образом, чтобы люди не могли копировать шрифты Adobe и добавлять свои собственные, формат Type 1 Font изначально был собственностью Adobe и содержал код «шифрования шрифтов». Только PostScript от Adobe мог интерпретировать шрифты Type 1, и только в них была реализована фирменная технология хинтов, которая обеспечивает чёткость на малых размерах.

Подгонка сетки, кстати, стала настолько популярной, что когда Microsoft и Apple устали платить лицензионные сборы Adobe, то изобрели альтернативный метод для своего альтернативного формата шрифтов TrueType. Вместо того, чтобы указывать декларативные «подсказки», TrueType даёт автору шрифта полноценный тьюринг-полный стековый язык, чтобы автор мог контролировать все аспекты подгонки сетки (избегая патентов Adobe на декларативные хинты). Много лет бушевала война между форматами Adobe Type 1 и TrueType, а разработчики шрифтов застряли посередине, предоставляя пользователям оба формата. В конце концов, индустрия достигла компромисса: OpenType. Но вместо того, чтобы реально определить победителя, они просто плюхнули обе спецификации в один формат файла. Adobe теперь зарабатывала не на продаже шрифтов Type 1, а на программах Photoshop и Illustrator, так что удалила шифровальную часть, доработала формат и представила шрифты CFF / Type 2, которые целиком вошли в OpenType как таблица cff. С другой стороны, TrueType вставили в качестве glyf и других таблиц. Хотя и несколько уродливый, но OpenType вроде бы выполнял работу для пользователей, в основном, брал их измором: просто требуйте, чтобы всё программное обеспечение поддерживало оба типа шрифтов, потому что OpenType требует, чтобы вы поддерживали оба типа шрифтов.

Конечно, мы вынуждены спросить: если не PostScript, то что вместо него? Стоит рассмотреть и другие варианты. Ранее упомянутый METAFONT не использовал строго определённые очертания литер (filled paths). Вместо этого Кнут, в типичной своей манере, в статье «Математическая типографика» предложил для типографики математическую концепцию, которая «наиболее приятна». Вы указываете несколько точек, и какой-то алгоритм находит через них правильную «наиболее приятную» кривую. Можете накладывать эти очертания поверх друг на друга: определить какое-то из них как «перо», а затем «перетащить перо» через какую-то другую линию. Кнут, в глубине души учёный-компьютерщик, ввёл даже рекурсию. Его студент Джон Хобби разработал и реализовал алгоритмы вычисления «самой приятной кривой», наложения вложенных путей и растеризации таких кривых. Для дополнительной информации о METAFONT, кривых и истории типографики в целом настоятельно рекомендую книгу «Шрифты и кодировки», а также статьи Джона Хобби.

К счастью, возобновившийся интерес к исследованиям 2D-графики означал, что сплайны Кнута и Хобби не полностью забыли. Хотя они определённо заумные и нетрадиционные, но они недавно пробрались в Apple iWork Suite, и являются там типом сплайна по умолчанию.

Взлёт треугольников

Не слишком вдаваясь в математические дебри, на высоком уровне мы называем такие подходы, как кривые Безье и сплайны Хобби, неявными кривыми, потому что они указаны как математическая функция, которая генерирует кривую. Они хорошо смотрятся на любом разрешении, что отлично подходит для 2D-изображений, предназначенных для масштабирования.

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

Однако 3D-графика пошла совсем по другому маршруту. С самого начала почти универсальным подходом было использование многоугольников (полигонов), которые часто вручную размечались и вручную вводились в компьютер. Впрочем, такой подход не был универсальным. 3D-эквивалент неявной кривой — это неявная поверхность, состоящая из основных геометрических примитивов, таких как сферы, цилиндры и кубы. Идеальная сфера с бесконечным разрешением может быть представлена простым уравнением, поэтому на заре развития 3D для геометрии она была явно предпочтительнее полигонов. Одна из немногих компаний, которые разрабатывали графику с неявными поверхностями, была MAGI. В сочетании с умным художественным использованием процедурных текстур они выиграли контракт с Disney на дизайн «светового мотоцикла» для фильма «Трон» 1982 года. К сожалению, этот подход быстро сошёл на нет. Благодаря ускорению CPU и исследованию таких проблем, как «удаление скрытой поверхности», стремительно росло количество треугольников, которые вы могли бы отобразить в сцене, а для сложных фигур художникам было намного проще думать о полигонах и вершинах, которые можно щёлкнуть и перетащить, а не использовать комбинации кубов и цилиндров.

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

Треугольники захватили мир, и за ними последовали инструменты для создания 3D-контента. Новые разработчики и дизайнеры видеоигр и спецэффектов в фильмах обучались исключительно на программах моделирования с полигональными сетками, таких как Maya, 3DS Max и Softimage. Когда в конце 80-х годов на сцене появились «ускорители 3D-графики» (GPU), их разработали специально для ускорения существующего контента: треугольников. Хотя в ранних проектах GPU, таких как NVIDIA NV1, имелась ограниченная аппаратная поддержка кривых, но она глючила, и её быстро убрали из линейки продуктов.

Эта культура в основном распространяется на то, что мы видим сегодня. Доминирующая модель 2D-изображений PostScript началась с продукта, который мог отображать кривые в «реальном времени». В то же время 3D-индустрия игнорировала кривые, с которыми трудно работать, а вместо этого полагалась на автономные решения для предварительного преобразования кривых в треугольники.

Неявные поверхности возвращаются

Но почему неявные кривые 2D можно было просчитывать в режиме реального времени на принтере в 80-е годы, и те же самые неявные кривые 3D по-прежнему сильно глючат в начале 2000-х? Ну, алгоритм Кэтмелла — Кларка намного сложнее, чем кривая Безье. Кривые Безье в 3D известны как B-сплайны, и они хорошо вычислимы, но есть недостаток, что они ограничивают способы соединения сетки. Поверхности вроде Кэтмелла — Кларка и NURBS допускают произвольно связанные сетки для расширения возможностей художников, но это может привести к полиномам больше четвёртой степени, которые, как правило, не имеют аналитического решения. Вместо этого вы получаете аппроксимации, основанные на разделении полигонов, как это делается в OpenSubdiv от Pixar. Если кто-то когда-либо найдет аналитическое решение для поиска корней Кэтмелла — Кларка или NURBS, компания Autodesk много ему заплатит. По сравнению с ними треугольники кажутся намного приятнее: просто вычислите три линейных уравнения на плоскости, и у вас есть лёгкий ответ.

… Но что, если нам не нужно точное решение? Именно таким вопросом задался графический разработчик Иньиго Кильес, когда проводил исследования неявных поверхностей. Решение? Поля расстояний со знаком (signed distance fields, SDF). Вместо выдачи точной точки пересечения с поверхностью они говорят, как далеко вы находитесь от неё. Аналогично разнице между аналитически вычисленным интегралом и интегралом Эйлера, если у вас есть расстояние до ближайшего объекта, вы можете «маршировать» по сцене, в любой заданной точке спрашивая, как далеко вы находитесь, и проходя это расстояние. Такие поверхности вдохнули совершенно новую жизнь в индустрию через демосцену и сообщества вроде Shadertoy. Хак старой техники моделирования MAGI приносит нам невероятные находки, такие как Surfer Boy от Кильеса, рассчитанный с бесконечной точностью как неявная поверхность. Вам не нужно искать алгебраические корни Surfer Boy, вы просто чувствуете, как проходит сцена.

Конечно, проблема в том, что сотворить Surfer Boy способен только гений вроде Кильеса. Ещё нет инструментов для геометрии SDF, весь код пишется вручную. Тем не менее, учитывая захватывающее возрождение неявных поверхностей и естественные формы кривых, теперь к этой технике много интереса. Игра MediaMolecule Dreams на PS4 — это набор для создания контента, основанный на комбинировании неявных поверхностей. В процессе разрушается и создаётся заново большая часть традиционной графики. Это многообещающий подход, а инструменты интуитивно понятны и интересны. Oculus Medium и unbound.io тоже провели хорошие исследования по этой проблеме. Это определённо многообещающий взгляд на то, как может выглядеть будущее 3D-графики и инструментов следующего поколения.

Но некоторые из этих подходов меньше подходят для 2D, чем вы могли бы подумать. В общих игровых 3D-сценах, как правило, продвинутые материалы и текстуры, но мало расчётов геометрии, на что сразу указывают многие критики и продавцы сомнительных продуктов. Это означает, что нам меньше требуется сглаживание, поскольку силуэты не так важны. Подходы вроде 4x MSAA могут подойти для многих игр, но для маленьких шрифтов со сплошными цветами вы вместо 16 фиксированных выборочных местоположений скорее вычислите точную площадь под кривой для каждого пикселя, что даст вам столько разрешения, сколько хотите.

Вращение экрана в 3D-игре вызывает эффекты, похожие на саккадическое подавление, поскольку мозг перенастраивается на новый вид. Во многих играх это помогает скрыть артефакты в эффектах постобработки, таких как временное сглаживание, на которые сильно полагаются Dreams и unbound.io, чтобы получить хорошую производительность сцены. И наоборот, в типичной 2D-сцене у нас нет этой роскоши перспективы, поэтому попытка использовать её заставит глифы и формы кипеть и дрожать с этими артефактами по полной программе. На 2D смотрят иначе, и ожидания выше. При масштабировании, панорамировании и прокрутке важна стабильность.

Ни один из этих эффектов невозможно реализовать на GPU, но они показывают радикальный отход от “3D” контента, с другими приоритетами. В конечном счёте, рендеринг 2D-графики сложен, потому что речь идёт о формах — точных буквах и символах, а не о материалах и освещении, у которых в основном сплошной цвет. Графические ускорители в результате эволюции решили не обсчитывать неявную геометрию реального времени, такую как кривые, а вместо этого сконцентрировались на всём, что происходит внутри этих кривых. Возможно, если бы PostScript не победил, у нас была бы 2D-модель изображения без кривых Безье в качестве основного требования для реального времени. Возможно, в таком мире вместо треугольников бы использовались лучшие геометрические представления, инструменты создания контента сосредоточились на 3D-сплайнах, а GPU поддерживали кривые реального времени на аппаратном уровне. В конце концов, всегда забавно помечтать.