Растеризация треугольников

1996 год, id Software выпускает Quake. Впервые в истории игровой индустрии: полностью 3D мир, perspective-correct texture mapping, настоящие полигональные модели вместо спрайтов. Секрет - Michael Abrash и John Carmack написали software rasterizer настолько быстрый, что 486 процессор рендерил 320x200 пикселей на 30fps. Каждый треугольник: баррицентрические координаты, z-buffer, texture lookup - тысячи раз в секунду. Сегодня современный GPU делает это для 100 миллионов треугольников за 16 миллисекунд. Алгоритм тот же - только в аппаратном обеспечении.

• **Unreal Engine 5**: Nanite - виртуальная геометрия с триллионами полигонов через иерархическую растеризацию на GPU
• **Three.js/WebGL**: каждый браузерный 3D проект использует эти же алгоритмы через GPU pipeline в fragment shaders
• **NVIDIA OptiX**: hybrid rendering - растеризация для primary visibility, ray tracing для shadows/reflections

Эд Кэтмелл (1974)

В 1974 году Эд Кэтмелл (будущий президент Pixar) защитил диссертацию в Университете Юты, где описал z-buffer алгоритм. Тогда это была чисто академическая работа - SGI workstation стоила $50,000. Параллельно Анри Гуро разработал своё shading (1971), Буй Туонг Фонг - specular shading (1973). Университет Юты в 1970-е был мировым центром CG: здесь учились Джим Кларк (основатель Silicon Graphics), Алан Кэй (Smalltalk). В 1993 SGI Reality Engine сделала z-buffer аппаратным. В 1999 GeForce 256 принесла программируемые шейдеры. Кэтмелл получил премию Тьюринга в 2019 году. Z-buffer стал основным алгоритмом определения видимости в real-time rendering; современные GPU содержат dedicated depth test hardware

Scanline: построчная растеризация

Scanline алгоритм растеризует треугольник, обходя его горизонтальными линиями (scan lines). Для каждой строки Y определяются левая (x_left) и правая (x_right) границы треугольника, затем все пиксели между ними закрашиваются. Треугольник разбивается на два подтреугольника по средней вершине.

Scanline эффективен для CPU растеризации: горизонтальное заполнение pixel-за-pixel обеспечивает хорошую cache locality. Однако GPU растеризаторы используют **barycentric coordinates** - параллельное вычисление для всех пикселей bounding box одновременно в compute shaders.

Барицентрические координаты

Барицентрические координаты (λ₁, λ₂, λ₃) для точки P относительно треугольника (A, B, C): каждая координата - отношение площади подтреугольника к полной площади. Свойства: λ₁ + λ₂ + λ₃ = 1. Точка внутри треугольника если и только если 0 ≤ λᵢ ≤ 1 для всех i.

Барицентрические координаты - не только тест принадлежности. Это **универсальный инструмент интерполяции**: цвет, UV-координаты, нормали, любой атрибут вершины плавно интерполируется через λ = l1*attr0 + l2*attr1 + l3*attr2. Именно это делает Gouraud shading и texture mapping возможными.

Z-Buffer: видимость через глубину

Z-buffer (depth buffer) решает задачу определения видимости: когда несколько треугольников проецируются на один пиксель, нужно отрисовать ближайший. Алгоритм: для каждого пикселя хранить минимальную Z-глубину. При растеризации нового фрагмента: если его Z меньше сохранённого - обновить цвет и Z.

**Z-fighting**: два треугольника с очень близкими Z-значениями вызывают мерцание из-за floating point precision. Решения: polygon offset (glPolygonOffset), reversed Z-buffer (1/z вместо z, лучше распределение точности), shadow bias для shadow mapping. **Early Z-test** на GPU: проверка depth перед запуском fragment shader для отсечения невидимых фрагментов.

Интерполяция атрибутов: perspective-correct

Линейная интерполяция барицентрическими координатами в screen space некорректна при perspective projection. Проблема: perspective деление (деление на w) нелинейно деформирует пространство. Решение: **perspective-correct interpolation** - интерполировать attr/w, затем умножить на 1/w фрагмента.

Perspective-correct interpolation впервые правильно реализовали в 1993 году (SGI workstations). До этого 3D игры (Doom, 1993) использовали линейную интерполяцию - знаменитое 'warping' текстур на больших поверхностях. Quake (1996) был первым массовым продуктом с perspective-correct texture mapping на потребительских GPU.

Ключевые идеи

• **Scanline**: построчная растеризация с edge interpolation - эффективна для CPU, плохо параллелизируется
• **Барицентрические координаты**: λ₁+λ₂+λ₃=1, тест принадлежности треугольнику и интерполяция атрибутов
• **Z-buffer**: depth per-pixel, closest fragment wins; z-fighting и reversed Z для precision
• **Perspective-correct interpolation**: интерполяция attr/w, деление на 1/w - устраняет warping текстур

Вопросы для размышления

• Как early Z-test (depth culling перед fragment shader) снижает GPU нагрузку и при каких условиях он не работает?
• Почему Gouraud shading (интерполяция цветов) производит плохие specular highlights по сравнению с Phong shading (интерполяция нормалей)?
• Как MSAA (Multisample Anti-Aliasing) использует несколько Z-тестов на пиксель без запуска fragment shader несколько раз?

Связанные уроки

• cg-03
• cg-05
• cgeom-04
• cg-06
• cg-02
• la-03-cross-product