[Перевод] Почему векторная графика 2D намного сложнее, чем 3D
В последнее время появилось много фантастических исследований по 2D-рендерингу. Пётр Кобаличек и Фабиан Айзерман работают над Blend2D: это один из самых быстрых и точных CPU-растеризаторов на рынке, с инновационной техникой JIT. Патрик Уолтон из Mozilla изучил не один, а три разных подхода в Pathfinder, кульминацией чего стал Pathfinder v3. Раф Левиен построил вычислительный конвейер по технологии, описанной в научной статье Гана с коллегами о векторных текстурах (2014). Похоже, некое дальнейшее развитие получают поля расстояний со знаком: здесь независимо работают Адам Симмонс и Сара Фрискен.
Это ведь не может быть намного сложнее, чем 3D, верно? Кто-то может спросить: а почему вокруг 2D так много шума? Тут у нас на носу трассировка лучей в режиме реального времени с точным освещением, а вы не можете осилить невзрачную 2D-графику со сплошными цветами? 3D — совершенно другое измерение!
Но в 2D-графике множество уникальных ограничений, которые чрезвычайно её усложняют. Для тех, кто не очень хорошо разбирается в деталях современного GPU, это вправду очень удивительно! Давайте прогуляемся по исторической дорожке, которая нас сюда привела.
К тому же она не поддаётся параллелизации.
Взлёт PostScript
В начале был плоттер. Первое графическое устройство, способное взаимодействовать с компьютером, называлось «плоттер» (графопостроитель): одно или несколько перьев, способных передвигаться по бумаге. Всё работает по команде «перо-вниз», затем чертёжная головка перемещается неким уникальным способом, возможно, по кривой, и поступает команда «перо-вверх». HP, производитель некоторых из самых ранних плоттеров, на управляющем компьютере использовал вариант BASIC под названием AGL, который затем отправлял команды плоттеру на другом языке, типа HP-GL. В 1970-е годы всё дешевле и популярнее становились графические терминалы, начиная с Tektronix 4010. Он показывал изображение с помощью ЭЛТ, но не обманывайтесь: это не пиксельный дисплей. Tektronix пришёл из индустрии аналоговых осциллографов, и эти машины работают, управляя электронным пучком по определённому пути. Таким образом, у Tektronix 4010 не было пиксельного вывода. Вместо этого вы посылали ему команды в простом графическом режиме, который мог рисовать линии, но, опять же, в режиме «перо вниз», «перо вверх».
Исследователи начали разрабатывать новый тип принтера, более вычислительно выразительный, чем плоттер. Как и во многих других областях, всё изменило изобретение Xerox PARC. Очевидно, Xerox не смогла найти ему достойное применение, поэтому изобретатели покинули корабль и основали маленький стартап под названием Adobe. Этот новый принтер работал на маленьком стековом тьюринг-полном языке программирования, похожем на Forth, и назвали его… Interpress! Помимо милого, тьюринг-полного стекового языка, в четвёртой главе оригинального справочного руководства PostScript Language Reference описана Imaging Model, которая почти идентична современным программным интерфейсам. Они взяли с собой Interpress, а по мере исправления и улучшений тот изменился до неузнаваемости, так что ему дали другое название: PostScript. 1 из руководства содержит пример кода, который можно почти построчно перевести на HTML5 <canvas>. Пример 4.
/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();
Это не совпадение.
Джобс думал, что полиграфический бизнес будет прибыльным, и пытался купить Adobe ещё при рождении. Стив Джобс из Apple познакомился с инженерами Interpress во время своего визита в PARC. Третьим столпом в плане Джобса было финансирование небольшого стартапа Aldus, который делал WYSIWYG-приложение для создания PostScript-документов. Но Adobe выдвинула встречное предложение и в конечном итоге продала Apple пятилетнюю лицензию на PostScript. В начале 1985 года Apple выпустила первый принтер, совместимый с PostScript — Apple LaserWriter. Оно называлось PageMaker. Основной конкурент Hewlett-Packard в итоге тоже купил лицензию на PostScript для серии конкурирующих принтеров LaserJet. Сочетание Macintosh, PageMaker и LaserWriter мгновенно перевернуло полиграфическую индустрию с ног на голову, а новый хит «настольные издательские системы» укрепил за PostScript его место в истории. Это случилось в 1991 году после давления со стороны потребителей.
Умные программисты изучили, в каком виде команды PostScript отправляются на принтер — и начали создавать документы PostScript вручную, добавив в свои документы диаграммы, графики и рисунки, при этом PostScript использовался для вывода графики на дисплей. PostScript медленно перешёл из языка управления принтером в формат файла. Adobe это заметила и быстро выпустила формат Encapsulated PostScript, который представлял собой не более чем несколько специально отформатированных комментариев PostScript с метаданными о размере изображения и ограничениями на использование принтерных команд, таких как “page feed”. Возник спрос на графику вне принтера! Затем эти файлы можно было перенести в текстовый процессор, который создавал… документы PostScript для отправки на принтеры PostScript. В том же 1985 году Adobe начала разработку Illustrator — приложения, где художники работали в формате Encapsulated PostScript в удобном UI. Когда Microsoft работала над Windows 1. Весь мир перешёл на PostScript, и Adobe не могла быть ещё счастливее. Этот API в конечном итоге выпустили как GDI — основной компонент, используемый каждым инженером во время стремительного роста популярности Windows в 90-е годы. 0 и хотела создать собственный графический API для разработчиков, основной целью было сделать его совместимым с существующими принтерами, чтобы графика отправлялась на принтеры так же легко, как экран. Поколения программистов на платформе Windows начали неосознанно отождествлять векторную графику 2D с моделью изображений PostScript, закрепив за ней этот статус де-факто.
И это может быть медленно. Единственной серьёзной проблемой PostScript была тьюринг-полнота: просмотр 86-й страницы документа означает сначала запуск скрипта для страниц 1-85. Из него выбросили язык программирования, но графическая технология осталась прежней. Adobe узнала об этой жалобе пользователей и решила создать новый формат документов, у которого не было таких ограничений, его назвали “Portable Document Format” или для краткости “PDF”. 1, «Модель изображения»: Цитата из спецификаций PDF, глава 2.
Эта возможность достигается за счёт использования модели изображений Adobe, того же высокоуровневого, независимого от устройства представления, которое используется в языке описания страниц PostScript. В основе PDF лежит его способность описывать внешний вид сложной графики и типографики.
Когда консорциум W3C рассматривал претендентов на язык разметки 2D-графики в интернете, Adobe отстаивала PGML на основе XML, в основе которого лежала графическая модель PostScript:
PGML должен включать в себя модель изображений PDF/PostScript, чтобы гарантировать возможность масштабируемой 2D-графики, которая удовлетворяет потребностям как обычных пользователей, так и профессионалов графики.
Конкурирующий формат VML от Microsoft был основан на GDI, который, как мы знаем, основан на PostScript. Два конкурирующих предложения, которые по-прежнему представляли собой по сути PostScript, объединили вместе, так что W3C принял стандарт «масштабируемой векторной графики» (SVG), который мы знаем и любим сегодня.
У PostScript-принтера LaserWriter от Apple процессор был вдвое мощнее, чем у Macintosh, который его контролировал, просто для интерпретации PostScript и растеризации векторных путей до точек на бумаге. Даже если он стар, давайте не будем притворяться, что инновации PostScript, принесённые в этот мир — что-то меньшее, чем технологическое чудо. В своём первом воплощении PostScript изобрёл довольно сложную модель визуализации со всеми функциями, которые мы сегодня считаем само собой разумеющимися. Это может показаться чрезмерным, но если вы уже покупали модный принтер с лазером внутри, то не нужно удивляться дорогому процессору. Шрифты. Какая самая мощная, потрясающая особенность? В 1977 году Дональд Кнут показал миру, на что способна его система METAFONT, которую он представил вместе с текстовым редактором TeX, но она не прижилась. В то время шрифты рисовались от руки линейкой и транспортиром и отливались на плёнку для фотохимической печати. Большинство разработчиков шрифтов не хотели это изучать. Она требовала от пользователя математического описания шрифтов, используя кисти и кривые. PostScript предложил новое решение: алгоритм «привязки» очертаний к более грубым сеткам, которыми оперировали принтеры. А причудливые изгибы при малых размерах превращались в месиво: у принтеров того времени не было достаточного разрешения, поэтому буквы расплывались и сливались друг с другом. Чтобы предотвратить слишком большое искажение геометрии, они позволили шрифтам устанавливать «подсказки», какие части геометрии являются наиболее важными и что следует сохранить. Это известно как «подгонка сетки» (grid-fitting).
Кстати, это возможно, потому что шрифты, или, более формально, «гарнитуры», являются одной из пяти вещей, явно исключённых из закона США об авторском праве, поскольку их изначально обозначили как «слишком простые или утилитарные, чтобы быть творческими работами». Оригинальная бизнес-модель Adobe заключалась в том, чтобы продавать разработчикам принтеров эту технологию шрифтов и продавать издателям специальные воссозданные шрифты с добавленными подсказками, поэтому Adobe по сей день продаёт свои версии Times и Futura. Таким образом, чтобы люди не могли копировать шрифты Adobe и добавлять свои собственные, формат Type 1 Font изначально был собственностью Adobe и содержал код «шифрования шрифтов». Вместо этого защищается авторским правом цифровая программа, которая воспроизводит шрифт на экране. Только PostScript от Adobe мог интерпретировать шрифты Type 1, и только в них была реализована фирменная технология хинтов, которая обеспечивает чёткость на малых размерах.
Вместо того, чтобы указывать декларативные «подсказки», TrueType даёт автору шрифта полноценный тьюринг-полный стековый язык, чтобы автор мог контролировать все аспекты подгонки сетки (избегая патентов Adobe на декларативные хинты). Подгонка сетки, кстати, стала настолько популярной, что когда Microsoft и Apple устали платить лицензионные сборы Adobe, то изобрели альтернативный метод для своего альтернативного формата шрифтов TrueType. В конце концов, индустрия достигла компромисса: OpenType. Много лет бушевала война между форматами Adobe Type 1 и TrueType, а разработчики шрифтов застряли посередине, предоставляя пользователям оба формата. Adobe теперь зарабатывала не на продаже шрифтов Type 1, а на программах Photoshop и Illustrator, так что удалила шифровальную часть, доработала формат и представила шрифты CFF / Type 2, которые целиком вошли в OpenType как таблица cff. Но вместо того, чтобы реально определить победителя, они просто плюхнули обе спецификации в один формат файла. Хотя и несколько уродливый, но OpenType вроде бы выполнял работу для пользователей, в основном, брал их измором: просто требуйте, чтобы всё программное обеспечение поддерживало оба типа шрифтов, потому что OpenType требует, чтобы вы поддерживали оба типа шрифтов. С другой стороны, TrueType вставили в качестве glyf и других таблиц.
Стоит рассмотреть и другие варианты. Конечно, мы вынуждены спросить: если PostScript, что вместо него? Вместо этого Кнут, в типичной своей манере, в статье «Математическая типографика» предложил для типографики математическую концепцию, которая «наиболее приятна». Ранее упомянутый METAFONT не использовал строго определённые очертания литер (filled paths). Можете накладывать эти очертания поверх друг на друга: определить какое-то из них как «перо», а затем «перетащить перо» через какую-то другую линию. Вы указываете несколько точек, и какой-то алгоритм находит через них правильную «наиболее приятную» кривую. Его студент Джон Хобби разработал и реализовал алгоритмы вычисления «самой приятной кривой», наложения вложенных путей и растеризации таких кривых. Кнут, в глубине души учёный-компьютерщик, ввёл даже рекурсию. Для дополнительной информации о METAFONT, кривых и истории типографики в целом настоятельно рекомендую книгу «Шрифты и кодировки», а также статьи Джона Хобби.
Хотя они определённо заумные и нетрадиционные, но они недавно пробрались в Apple iWork Suite, и являются там типом сплайна по умолчанию. К счастью, возобновившийся интерес к исследованиям 2D-графики означал, что сплайны Кнута и Хобби не полностью забыли.
Взлёт треугольников
Не слишком вдаваясь в математические дебри, на высоком уровне мы называем такие подходы, как кривые Безье и сплайны Хобби, неявными кривыми, потому что они указаны как математическая функция, которая генерирует кривую. Они хорошо смотрятся на любом разрешении, что отлично подходит для 2D-изображений, предназначенных для масштабирования.
Аппаратное и программное обеспечение для вычисления этих путей в режиме реального времени было дорогим, но из полиграфической промышленности пришёл большой толчок для векторной графики, а большая часть остального существующего промышленного оборудования уже была намного дороже, чем лазерный принтер с причудливым процессором. 2D-графика поддержала импульс вокруг этих неявных кривых, которые почти обязательны при моделировании глифов.
С самого начала почти универсальным подходом было использование многоугольников (полигонов), которые часто вручную размечались и вручную вводились в компьютер. Однако 3D-графика пошла совсем по другому маршруту. 3D-эквивалент неявной кривой — это неявная поверхность, состоящая из основных геометрических примитивов, таких как сферы, цилиндры и кубы. Впрочем, такой подход не был универсальным. Одна из немногих компаний, которые разрабатывали графику с неявными поверхностями, была MAGI. Идеальная сфера с бесконечным разрешением может быть представлена простым уравнением, поэтому на заре развития 3D для геометрии она была явно предпочтительнее полигонов. К сожалению, этот подход быстро сошёл на нет. В сочетании с умным художественным использованием процедурных текстур они выиграли контракт с Disney на дизайн «светового мотоцикла» для фильма «Трон» 1982 года. Благодаря ускорению CPU и исследованию таких проблем, как «удаление скрытой поверхности», стремительно росло количество треугольников, которые вы могли бы отобразить в сцене, а для сложных фигур художникам было намного проще думать о полигонах и вершинах, которые можно щёлкнуть и перетащить, а не использовать комбинации кубов и цилиндров.
Техники вроде алгоритма Кэтмелла — Кларка к началу 80-х годов стали общепринятым отраслевым стандартом, позволяя художникам создавать гладкие, органичные простые геометрические формы. Это не означает, что неявные поверхности не использовались в процессе моделирования. Тогда это рассматривалось как итерационный алгоритм: способ разделения полигонов на ещё большее количество полигонов. Хотя до начала 2000-х годов алгоритм Кэтмелла — Кларка даже не определялся как «неявная поверхность», которую можно вычислить с помощью уравнения.
Новые разработчики и дизайнеры видеоигр и спецэффектов в фильмах обучались исключительно на программах моделирования с полигональными сетками, таких как Maya, 3DS Max и Softimage. Треугольники захватили мир, и за ними последовали инструменты для создания 3D-контента. Хотя в ранних проектах GPU, таких как NVIDIA NV1, имелась ограниченная аппаратная поддержка кривых, но она глючила, и её быстро убрали из линейки продуктов. Когда в конце 80-х годов на сцене появились «ускорители 3D-графики» (GPU), их разработали специально для ускорения существующего контента: треугольников.
Доминирующая модель 2D-изображений PostScript началась с продукта, который мог отображать кривые в «реальном времени». Эта культура в основном распространяется на то, что мы видим сегодня. В то же время 3D-индустрия игнорировала кривые, с которыми трудно работать, а вместо этого полагалась на автономные решения для предварительного преобразования кривых в треугольники.
Неявные поверхности возвращаются
Но почему неявные кривые 2D можно было просчитывать в режиме реального времени на принтере в 80-е годы, и те же самые неявные кривые 3D по-прежнему сильно глючат в начале 2000-х? Ну, алгоритм Кэтмелла — Кларка намного сложнее, чем кривая Безье. Кривые Безье в 3D известны как B-сплайны, и они хорошо вычислимы, но есть недостаток, что они ограничивают способы соединения сетки. Поверхности вроде Кэтмелла — Кларка и NURBS допускают произвольно связанные сетки для расширения возможностей художников, но это может привести к полиномам больше четвёртой степени, которые, как правило, не имеют аналитического решения. Вместо этого вы получаете аппроксимации, основанные на разделении полигонов, как это делается в OpenSubdiv от Pixar. Если кто-то когда-либо найдет аналитическое решение для поиска корней Кэтмелла — Кларка или NURBS, компания Autodesk много ему заплатит. По сравнению с ними треугольники кажутся намного приятнее: просто вычислите три линейных уравнения на плоскости, и у вас есть лёгкий ответ.
Именно таким вопросом задался графический разработчик Иньиго Кильес, когда проводил исследования неявных поверхностей. … Но что, если нам не нужно точное решение? Поля расстояний со знаком (signed distance fields, SDF). Решение? Аналогично разнице между аналитически вычисленным интегралом и интегралом Эйлера, если у вас есть расстояние до ближайшего объекта, вы можете «маршировать» по сцене, в любой заданной точке спрашивая, как далеко вы находитесь, и проходя это расстояние. Вместо выдачи точной точки пересечения с поверхностью они говорят, как далеко вы находитесь от неё. Хак старой техники моделирования MAGI приносит нам невероятные находки, такие как Surfer Boy от Кильеса, рассчитанный с бесконечной точностью как неявная поверхность. Такие поверхности вдохнули совершенно новую жизнь в индустрию через демосцену и сообщества вроде Shadertoy. Вам не нужно искать алгебраические корни Surfer Boy, вы просто чувствуете, как проходит сцена.
Ещё нет инструментов для геометрии SDF, весь код пишется вручную. Конечно, проблема в том, что сотворить Surfer Boy способен только гений вроде Кильеса. Игра MediaMolecule Dreams на PS4 — это набор для создания контента, основанный на комбинировании неявных поверхностей. Тем не менее, учитывая захватывающее возрождение неявных поверхностей и естественные формы кривых, теперь к этой технике много интереса. Это многообещающий подход, а инструменты интуитивно понятны и интересны. В процессе разрушается и создаётся заново большая часть традиционной графики. Это определённо многообещающий взгляд на то, как может выглядеть будущее 3D-графики и инструментов следующего поколения. Oculus Medium и unbound.io тоже провели хорошие исследования по этой проблеме.
В общих игровых 3D-сценах, как правило, продвинутые материалы и текстуры, но мало расчётов геометрии, на что сразу указывают многие критики и продавцы сомнительных продуктов. Но некоторые из этих подходов меньше подходят для 2D, чем вы могли бы подумать. Подходы вроде 4x MSAA могут подойти для многих игр, но для маленьких шрифтов со сплошными цветами вы вместо 16 фиксированных выборочных местоположений скорее вычислите точную площадь под кривой для каждого пикселя, что даст вам столько разрешения, сколько хотите. Это означает, что нам меньше требуется сглаживание, поскольку силуэты не так важны.
Во многих играх это помогает скрыть артефакты в эффектах постобработки, таких как временное сглаживание, на которые сильно полагаются Dreams и unbound.io, чтобы получить хорошую производительность сцены. Вращение экрана в 3D-игре вызывает эффекты, похожие на саккадическое подавление, поскольку мозг перенастраивается на новый вид. На 2D смотрят иначе, и ожидания выше. И наоборот, в типичной 2D-сцене у нас нет этой роскоши перспективы, поэтому попытка использовать её заставит глифы и формы кипеть и дрожать с этими артефактами по полной программе. При масштабировании, панорамировании и прокрутке важна стабильность.
В конечном счёте, рендеринг 2D-графики сложен, потому что речь идёт о формах — точных буквах и символах, а не о материалах и освещении, у которых в основном сплошной цвет. Ни один из этих эффектов невозможно реализовать на GPU, но они показывают радикальный отход от “3D” контента, с другими приоритетами. Возможно, если бы PostScript не победил, у нас была бы 2D-модель изображения без кривых Безье в качестве основного требования для реального времени. Графические ускорители в результате эволюции решили не обсчитывать неявную геометрию реального времени, такую как кривые, а вместо этого сконцентрировались на всём, что происходит внутри этих кривых. В конце концов, всегда забавно помечтать. Возможно, в таком мире вместо треугольников бы использовались лучшие геометрические представления, инструменты создания контента сосредоточились на 3D-сплайнах, а GPU поддерживали кривые реального времени на аппаратном уровне.