Треугольник становится пикселями: растеризация и z-буфер

Всем привет! Меня зовут Гриша Дядиченко, и я технический директор и основатель White Label Games. Больше десяти лет работаю с компьютерной графикой, AR/VR и компьютерным зрением — в основном заказная разработка и собственные прототипы.

В прошлой статье вершина прошла весь путь до экрана: матрицы, проекция, деление на w — и вот у треугольника есть три точки в пиксельных координатах. Но сам треугольник всё ещё никто не закрасил. А в этом месте конвейера живёт своя пачка знакомых всем багов. Тонкий провод вдали то виден, то нет. Два далёких объекта мерцают полосами друг сквозь друга. Знакомо?

Собственно, всё это относится к паре вопросов: какой пиксель внутри треугольника — и кто из них ближе к камере? Ими и займёмся. Разберём:

• как GPU решает «внутри или нет» пиксель — edge-функции, сэмпл в центре пикселя и правило top-left;
• как решается «кто ближе» — z-буфер, его точность и откуда берётся z-fighting;
• почему пиксель закрашивается по несколько раз — overdraw, early-Z и depth pre-pass;
• и зачем при закраске снова всплывает деление на w — перспективно-корректная интерполяция.

Пять частей, в каждой — интерактив.

Часть 1. Кто внутри треугольника

На входе — три вершины в экранных координатах. На выходе должны появиться закрашенные пиксели. Узел, который этим занимается, называется растеризатором, и в отличие от вершинных и пиксельных шейдеров он не программируется: это зашитый в железо автомат. Тем интереснее понимать, по каким правилам он играет, — потому что правила эти простые.

Пиксель — это точка, а не квадратик

Первое, что нужно принять: для растеризатора пиксель — не маленький квадрат, который можно «зацепить краем». Пиксель — это одна точка-сэмпл в его центре, на полуцелых координатах (x + 0.5, y + 0.5). Так это определено и в правилах растеризации Direct3D, и в OpenGL с Vulkan. Треугольник закрашивает пиксель тогда и только тогда, когда накрывает его центр. Накрыл 99% площади квадратика, но не центр — пикселя нет.

Edge-функция: с какой стороны точка

Как проверить, что точка внутри треугольника? Ответ растеризатора — edge-функция. Для ребра из вершины a в вершину b и точки p считается вот такое выражение:

По сути это векторное произведение: знак E говорит, с какой стороны ребра лежит точка, ноль — точка ровно на ребре. У треугольника три ребра — и точка внутри, когда все три edge-функции одного знака. Этот тест «внутри пиксель или снаружи» и называют покрытием (coverage) — дальше по статье он будет встречаться именно так.

Схему предложил Хуан Пинеда в статье «A Parallel Algorithm for Polygon Rasterization» (1988) — и слово «parallel» в названии главное. Edge-функция в каждой точке считается независимо от соседей: можно проверить хоть весь экран разом, была бы арифметика.

Пощупайте руками — так быстрее, чем читать:

Прижмите вершину к основанию. Площадь у треугольника есть, а фрагментов — ноль: полоска прошла между центрами пикселей. Теперь представьте, что это тонкая антенна или провод, и камера чуть движется: сэмплы то ловят его, то нет. Вот и мерцание тонкой геометрии — не баг драйвера, а прямое следствие «пиксель — это точка». Лечат его сглаживанием с несколькими сэмплами на пиксель (MSAA) или геометрией потолще — но это уже история про сглаживание, до неё серия ещё дойдёт.

Ребро на двоих: правило top-left

Второй режим демки — про вопрос, который на собеседованиях по графике задают реже, чем стоило бы. Соседние треугольники меша делят ребро. Если сэмпл лежит ровно на нём, E = 0 у обоих — и «все знаки неотрицательны» выполняется у обоих. Закрасить дважды? С непрозрачной геометрией вы этого даже не заметите. А с прозрачностью или декалями по шву пройдёт тёмный рубец: пиксель смешался с фоном два раза. Потребовать строгого «больше нуля»? Тогда сэмпл не достанется никому, и по мешу побежит строчка дырок.

Договорённость индустрии — правило top-left, как в Direct3D: сэмпл на ребре принадлежит треугольнику, для которого это ребро верхнее или левое.

Со «внутри» разобрались. Но в демке треугольник был один, а в кадре их тысячи, и в один и тот же пиксель они попадают пачками. Кто из них останется на экране? Это часть 2.

Часть 2. Кто ближе: z-буфер

Два треугольника накрыли один сэмпл. На экран попадёт один — тот, что ближе к камере. Вопрос в том, как это «ближе» вычислять на каждый пиксель кадра и не разориться.

Сначала — решение «руками»

Первое, что приходит в голову: отсортировать треугольники по глубине и рисовать сзади-вперёд — дальние сначала, ближние поверх. Это алгоритм художникаPainter's algorithm: рисовать полигоны сзади-вперёд, ближние поверх дальних — как художник накладывает краску слоями. Классическое решение задачи видимости (Newell, Newell & Sancha, 1972)., и для простых сцен он даже работает. Дальше начинаются проблемы, и все они про одно: сортировка держится на том, что для любых двух треугольников можно сказать, какой ближе. А это верно не всегда.

Во-первых, треугольники могут пересекаться — воткнуться друг в друга крест-накрест. Тогда часть первого оказывается перед вторым, а часть — за ним. Единого ответа «кто ближе» нет, и чтобы такую пару всё-таки упорядочить, треугольник пришлось бы разрезать по линии пересечения на куски — то есть переделывать саму геометрию прямо во время отрисовки.

Во-вторых, порядка может не существовать в принципе. Представьте три длинные планки, уложенные внахлёст по кругу: первая лежит на второй, вторая — на третьей, а третья — снова на первой. Какую рисовать первой? Любой ответ где-нибудь да соврёт — правильной очереди «сзади-вперёд» тут просто нет.

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

Буфер глубины

Решение, до которого индустрия дошла к середине семидесятых (диссертация Эда Кэтмулла 1974 года; независимо ту же идею описал Вольфганг Штрассер), переворачивает задачу. Не надо упорядочивать треугольники — надо запоминать глубину на каждый пиксель. Рядом с цветовым буфером заводится второй, z-буфер: в нём лежит глубина текущего победителя. Каждый новый фрагмент сравнивает свою глубину с записанной: ближе — записал цвет и глубину, дальше — молча выбросился. Это и есть depth test.

Смотрите, что произошло. Глобальная задача «упорядочить всю сцену» превратилась в локальную «в этом пикселе сравнить два числа». Порядок отрисовки перестал что-либо решать: на экране остаётся не тот, кого нарисовали последним, а тот, чья глубина меньше. И пересечения геометрии разруливаются сами собой.

Плата за это — второй буфер размером с целый экран, только под значения глубины. В 1974-м держать в памяти лишний полный экран было расточительством.

Уровни глубины и z-fighting

Подвох в том, что глубина в буфере — не бесконечно точное число. Типичный формат — 24-битный целочисленный или 32-битный float: конечное количество различимых уровней. Пока поверхности далеко друг от друга, всё хорошо. Но положите одну почти на другую — накладку поверх стены, дорогу поверх террейна — и их глубины начнут попадать в один уровень. В таком пикселе победителя определяет уже не настоящая глубина, а то, в какую сторону округлилось значение и в каком порядке нарисованы поверхности. От пикселя к пикселю и от кадра к кадру победитель меняется — по стыку ползут рваные мерцающие полосы. Это и есть z-fighting, тот самый, из-за которого мерцают далёкие склоны в опенворлдах.

Почему страдают именно далёкие? Помните нелинейную кривую глубины из прошлой статьи? После деления на w в буфере лежит величина вида 1/z: уровни точности густо лежат у ближней плоскости и стремительно редеют к дальней. Разбор с картинками — у Натана Рида в «Depth Precision Visualized».

Теперь давайте пощупаем это в демке. Две плоскости пересекаются под очень острым углом — как дорога и террейн:

Крутите битность. На 24 битах граница между плоскостями — ровная линия, как её видит геометрия. К 8–10 битам вокруг линии расползается полоса, в которой победителя выбирает округление, — точь-в-точь мерцающий стык в игре. А режим «без буфера» показывает, от чего z-буфер нас избавил: последний нарисованный ложится поверх, и дальняя плоскость нахально перекрывает ближнюю.

Победитель на каждый пиксель у нас есть. Но обратите внимание: проигравшие фрагменты мы к этому моменту уже посчитали. Сколько стоит проигрыш и можно ли не платить — часть 3.

Часть 3. Overdraw: платим за невидимое

Depth test из второй части отвечает «кто победил». Экономика вопроса — отдельная история: когда мы это узнали и что успели потратить.

Рисуем сцену в порядке загрузки. Пиксель накрыт пятью слоями геометрии: пять раз отработал пиксельный шейдер — со всеми его текстурами, светом и туманом, — а виден один слой. Четыре запуска ушли в мусор. Это и есть overdrawСколько раз пиксель закрашивается за кадр. Overdraw ×3 — каждый пиксель в среднем оплачен трижды. — и в тяжёлых сценах он спокойно съедает половину бюджета кадра.

Early-Z: выбросить до оплаты

По логике конвейера depth test стоит после пиксельного шейдера — вдруг шейдер сам поменяет глубину. Но железо давно делает ход конём: если шейдер глубину не трогает, тест выполняется до него — это early-Z. Фрагмент, который заведомо дальше записанного, отбрасывается ещё до запуска шейдера. Подробности механики — у Гизена в седьмой части цикла; там же — про hierarchical-Z, грубый буфер, который отбрасывает целые тайлы, не глядя на отдельные пиксели.

Нюанс: early-Z помогает, только если ближнее нарисовано раньше дальнего — иначе дальние фрагменты успевают отшейдиться, пока буфер ещё пуст, и отбрасывать им нечему. Отсюда стандартная практика: непрозрачную геометрию сортируют спереди-назад. Заметьте симметрию с прошлой частью: художнику для корректности нужно было «сзади-вперёд», нам для скорости — наоборот; корректность теперь держит z-буфер, а от порядка зависит уже не правильность картинки, а только её цена. И ещё нюанс: шейдер, который пишет глубину или делает discard, выключает early-Z — альфа-тест листвы не зря считается дорогим.

Depth pre-pass: заплатить геометрией

Когда пиксельные шейдеры дорогие, а сортировка не спасает, применяют ход радикальнее — depth pre-pass. Первый проход рисует сцену вообще без цвета, только глубину: z-буфер заполняется финальными победителями. Второй проход рисует цвет с тестом «равно» — и шейдит ровно один фрагмент на пиксель, overdraw шейдинга становится единицей. Плата: вся геометрия проходит конвейер дважды. Классический размен, выгодный при дорогом шейдинге и дешёвой геометрии.

Давайте проверим всё это на демке — картинка во всех режимах одна, различается только счёт за неё:

Смотрите на хитмап и счётчик фрагментов: «сзади-вперёд» оплачивает каждый слой, «спереди-назад» гасит перекрытые фрагменты early-Z, pre-pass выравнивает шейдинг в ровно один слой ценой двойной геометрии.

Итак, с победителем разобрались: и кто он в каждом пикселе, и как не переплатить за проигравших. Осталось понять, чем его красить: цвет и текстурные координаты заданы в трёх вершинах, а закрашиваем мы точку между ними. Часть 4 — про интерполяцию и про то, почему в ней снова всплывает w.

Часть 4. Деление на w, дубль два

Пиксель прошёл покрытие (его центр внутри треугольника) и depth test. Теперь его надо закрасить — а цвет, текстурные координаты, нормаль заданы только в трёх вершинах. Значение в точке между ними надо интерполировать, и веса для этого у нас уже есть: барицентрики из первой части, побочный продукт edge-функций.

Наивный вариант — взять и смешать атрибуты с этими весами напрямую, линейно по экрану. Для квада, стоящего к камере в лоб, это даже правильный ответ. А вот для пола, уходящего в глубину, — уже нет. Дело в том, что перспектива неравномерно сжимает пространство: ближняя половина пола занимает на экране куда больше пикселей, чем дальняя. Середина отрезка на экране — вовсе не середина отрезка в мире. Линейная интерполяция по экрану об этом не знает — и текстура начинает ползти.

Правильная схема выглядит неожиданно просто. Линейно по экрану ведут себя не сами атрибуты, а атрибуты, поделённые на w вершины, — и величина 1/w заодно. Их и интерполируем, а в пикселе делим одно на другое:

Это перспективно-корректная интерполяция, она прописана в спецификациях всех графических API — и это второе пришествие w. В прошлой статье мы делили на него координаты вершин, чтобы получить перспективу положения; теперь делим атрибуты, чтобы получить перспективу закраски.

Самая знаменитая иллюстрация того, что бывает без этого деления, — целая игровая эпоха. PlayStation 1 после растеризации не хранила w и делить на него попиксельно не умела: текстуры интерполировались аффинно, прямо по экрану. Отсюда фирменный вид ранних 3D-игр — плывущие, изламывающиеся по диагоналям квадов текстуры, особенно на полах и стенах. Сегодня этот артефакт воспроизводят нарочно, шейдерами, — как ретро-стилизацию.

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

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

Ну и всё, конструктор собран: покрытие, глубина, экономика, закраска. Осталось прогнать весь путь целиком, по шагам, — часть 5.

Часть 5. Растеризация по шагам

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

1. Вершины уже в экранных координатах — это сделали матрицы и деление на w (прошлая статья).
2. Покрытие: три edge-функции решают, накрыт ли центр пикселя; сэмплы ровно на рёбрах раздаёт правило top-left (часть 1).
3. Depth test: глубина фрагмента против z-буфера; при возможности — early-Z, до шейдинга (части 2 и 3).
4. Интерполяция: барицентрики тянут атрибуты с вершин, деля на w, чтобы текстура не ползла (часть 4).
5. Шейдинг и запись: пиксельный шейдер считает цвет, победитель записывается в кадр и в z-буфер.

И всё это — не цикл по треугольнику, а один и тот же конвейер, прожёвывающий сэмплы миллионами, тайлами и квадами, параллельно. В демке мы его нарочно замедлим до одного сэмпла за шаг:

Прокрутите кадр слайдером и посмотрите на счётчики: фрагментов всегда больше, чем записей, — разницу съели перекрытия. Вид «глубина» — это буквально содержимое z-буфера (ближе — светлее). А теперь выключите буфер: треугольники нарисованы «в порядке загрузки», и дальний ржавый нагло ложится поверх ближних. Одна галка depth test отделяет правильный кадр от каши — а стоит она, как мы теперь знаем, одного сравнения на фрагмент.

Шпаргалка: симптом → куда смотреть

Выводы

Растеризация с виду — «GPU сам закрасит треугольник». Под капотом это два вопроса, заданных миллиард раз за кадр: накрыт ли сэмпл — и кто из накрывших ближе. Всё остальное в этой статье — цена этих двух ответов и способы платить меньше.

И обратите внимание на закономерность, она сквозная для всей серии про путь кадра. Каждое «простое решение» здесь работает — в своей области применимости. Алгоритм художника корректен, пока для сцены вообще существует порядок «сзади-вперёд». Аффинная интерполяция точна… на фронтальном к камере квадрате. Отрисовка в порядке загрузки безобидна, пока сцена мала. Ломается не приём — ломается его применение там, где предпосылки уже не выполняются. Знать, где проходит этот предел, и есть разница между «нарисовалось» и «понимаю, почему нарисовалось».

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

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