Привет. В прошлой статье я описал математику, которая необходима для вывода трехмерной сцены на экран в виде сетки — т.е. мы остановились на моменте получения координат вершин в пространстве экрана. Следующий шаг — это «заполнение» полигонов из которых состоит объект, т.е. поиск пикселей, которые входят в изображение объекта на экране. Процесс поиска этих точек называется растеризацией. Мы так же хотим иметь возможность текстурировать и освещать объекты — для этого необходимо уметь интерполировать атрибуты, заданные в вершинах (например, текстурные координаты, нормали, цвет и другие).
Наши входные данные — это набор полигонов (мы будем рассматривать только треугольники): координаты их вершин (система координат зависит от алгоритма) и значения атрибутов в каждой из этих вершин, которые в дальнейшем будут интерполироваться вдоль поверхности треугольника. Существует несколько подводных камней, которые я рассмотрю в этой статье:
Я рассмотрю три подхода к растеризации:
Так же в конце будет ссылка на проект, который является примером реализации, оттуда же будут и примеры кода.
Итак, растеризация — это процесс поиска пикселей, «входящих» в заданный полигон. Для начала, мы будем считать, что нам достаточно закрасить полигон сплошным цветом — ничего лишнего.
Представим, что у нас есть следующий треугольник для вывода на экран (все координаты уже представлены в пространстве экрана):
Какие пиксели необходимо закрасить? Пиксель может быть целиком вне полигона, частично в полигоне и целиком в полигоне:
Все просто для двух случаев:
Третий случай (пиксель частично находится внутри полигона) — сложнее. Первое решение, которое приходит на ум — считать что все такие пиксели либо входят в полигон, либо нет. Но оно ведет к неверному результату. Трехмерные модели, которые мы собираемся отрисовывать, состоят из множества треугольников, которые, в общем случае, не должны накладываться друг на друга. Перекрывающие друг друга треугольники не имеют смысла, поскольку всего лишь дублируют уже существующую информацию. Таким образом, множество полигонов имеют общие между собой грани. Самый простой пример — прямоугольник:
Оранжевым цветом отмечены пиксели, которые частично входят в оба полигона. Теперь представим, что мы растеризуем оба этих полигона. Если мы решаем, что все пиксели, частично входящие в полигон, должны быть заполнены, мы получим заполнение одних и тех же пикселей дважды (или больше, в случае если есть общая вершина для более чем двух полигонов). Это может не показаться проблемой на первый взгляд, но, на самом деле, это приведет к различным артефактам при использовании некоторых техник, таких как альфа-смешивание (отрисовка с использованием альфа-канала для имитации прозрачности). Так же это ведет к снижению производительности, т.к. количество пикселей, для которых нам необходимо вычислять значения атрибутов, увеличивается. Если же мы, наоборот, решим, что такие пиксели не входят в итоговое изображение и не должны быть заполнены, мы получим «дыры» между полигонами, что неприемлимо.
Таким образом мы пришли к пониманию того, что каждый пиксель при отрисовке смежных полигонов должен быть заполнен ровно один раз. Это требование, которое соблюдают и Direct3D и OpenGL.
Проблема возникает из-за необходимости отображения из непрерывного (система координат экрана) в дискретное (пиксели на мониторе). Традиционный алгоритм растеризации (при отрисовке без сглаживания) решает это следующим образом: каждому пикселю сопоставляется некая точка (sample point), которая и отвечает за вхождение пикселя в полигон. Так же, именно в этой точке считаются значения всех необходимых атрибутов. Другими словами, все пространство, занимаемое пикселем в системе координат экрана, «представляется» одной точкой. Как правило, это центр: (0.5, 0.5):
Теоретически, можно брать любую точку внутри пикселя, вместо центра. Другие значения приведут к тому, что изображение может быть «сдвинуто» на пиксель в одну из сторон. Так же, в ситуации со смежным полигонами, для пикселей, в которых не расположены вершины треугольников, использование точки (0.5, 0.5) обладает хорошим свойством: эта точка входит в тот полигон, который охватывает более 50% площади прямоугольника, представляющего пиксель.
Таким образом, если центр пикселя входит в полигон, то считается, что пиксель принадлежит полигону. Но теперь возникает следующая проблема: что, если два полигона имеют общую грань, которая проходит через центр пикселя? Мы уже поняли, что пиксель должен принадлежать только одному из двух треугольников, но какому именно? На картинке ниже такой пиксель помечен красным цветом:
Эту проблему решает так называемое «соглашение о заполнении пикселей» (filling convention).
Итак, предположим мы столкнулись с ситуацией, описаной выше — два полигона делят между собой грань, которая проходят ровно через центр пикселя. Наша задача состоит в том, чтобы выяснить, какому из полигонов принадлежит этот пиксель.
Де-факто стандартом является так называемое top-left rule: ему следует DirectX и большинство реализаций OpenGL. Суть этого правила такова: если грань полигона проходит через центр пикселя, то этот пиксель принадлежит полигону в двух случаях — если это левая грань или верхняя грань (отсюда и название).
Понятия левой, правой, верхней и нижней граней требуют пояснений. Пока что мы не будем давать точных определений (мы это сделаем, когда дойдем до traversal-алгоритмов), а опишем их более простым языком:
Примеры:
Теперь рассмотрим случай смежных полигонов. Если грань — смежная, и является левой в одном полигоне, то эта же грань является правой для всех полигонов, которые делят эту грань с этим полигоном. Аналогичное правило работает для верхних и нижних граней:
Мы можем использовать это свойство для того, чтобы определять, какому из смежных полигонов принадлежит пиксель. Если мы договоримся, что пиксель, чей центр лежит на общей грани, принадлежит только полигонам, у которых эта грань — левая, то он автоматически не будет принадлежать смежным полигонам, поскольку для них эта грань — правая. И то же самое для верхней грани.
Несмотря на то, что правило верхней и левой грани встречается чаще всего, мы можем использовать любое подходящее сочетание. Например, правило нижней и левой грани, верхней и правой и т.д. Direct3D обязывает использовать top-left rule, OpenGL же не так строг и позволяет использовать любое правило, решающее проблему принадлежности пикселя. Я в дальнейшем буду предполагать использование top-left rule.
Рассмотрим следующие два полигона:
Второй полигон может быть получен из первого в результате вращения на некоторый угол. В итоге, некоторые пиксели дополнительно включаются в итоговое изображение (такие пиксели помечены зеленым), а некоторые, наоборот, исчезают из него (помечены красным). Соответственно, нам необходимо учитывать дробные части координат вершин. Если мы будем их отбрасывать, то получим проблемы при рисовании нестатической сцены. Если, например, заставить полигон очень медленно вращаться, то он будет это делать дерганно — поскольку грани будут резко «прыгать» из одного положения в другое, вместо того, чтобы корректно обрабатывать промежуточные результаты. Разницу легко понять, сравнив два этих видео:
Конечно, в случае со статической сценой таких проблем не возникнет.
Прежде чем перейти непосредственно к алгоритмам растеризации, остановимся на интерполяции атрибутов.
Атрибут — это некая информация, связанная с объектом, которая необходима для его корректной отрисовки по заданному алгоритму. Таким атрибутом может быть все, что угодно. Одними из самых частых вариантов являются: цвет, текстурные координаты, координаты нормали. Значения атрибута задаются в вершинах сетки объекта. При растеризации полигонов, эти атрибуты интерполируются вдоль поверхности треугольников и используются для вычисления цвета каждого из пикселей.
Самым простым примером (и своеобразным аналогом «hello world») является отрисовка треугольника, в каждой вершине которого задан один атрибут — цвет:
В этом случае, если мы будем присваивать каждому пикселю полигона цвет, являющийся результатом линейной интерполяции цветов трех вершин, мы получим следующее изображение:
Способ, которым производится интерполяция, зависит от данных, которыми мы оперируем в процессе отрисовки, а они, в свою очередь, зависят от алгоритма, который используется при растеризации. Например, при использовании «стандартного» алгоритма мы можем использовать простую линейную интерполяцию значений между двумя пикселями, а при использовании traversal-алгоритмов — барицентрические координаты. Поэтому мы отложим это до описания самих алгоритмов.
Тем не менее, есть еще важная тема, на которой необходимо остановиться заранее: интерполяция атрибутов с коррекцией перспективы.
Самым простым способом интерполяции является линейная интерполяция в пространстве экрана: после того, как полигон был спроецирован на плоскость проекции, мы линейным образом интерполируем атрибуты вдоль поверхности треугольника. Важно понимать, что эта интерполяция не является корректной, поскольку она не учитывает произведенную проекцию.
Рассмотрим проецирование линии на плоскость проекции d = 1. На начальной и конечной вершинах установлены некие атрибуты, которые линейно изменяются в пространстве камеры (и в мировом). После того, как произведена проекция, эти атрибуты не растут линейно в пространстве экрана. Если, например, взять среднюю точку в пространстве камеры (v = v0 * 0.5 + v1 * 0.5), то после проекции эта точка не будет лежать в середине спроецированной линии:
Легче всего это заметить при текстурировании объектов (я буду использовать простое текстурирование без фильтрации в примерах ниже). Я еще не описывал процесс текстурирования подробно (и это тема отдельной статьи), поэтому пока что ограничусь кратким описанием.
При текстурировании в каждой вершине полигона задается значение атрибута текстурных координат (его часто называют uv по названию соответствующих осей). Это нормализованные координаты (от 0 до 1), которые определяют, какой участок текстуры будет использован.
Теперь представим, что мы хотим нарисовать текстурированный прямоугольник и задали четыре значения атрибута uv таким образом, чтобы текстура использовалась целиком:
Кажется, все неплохо:
Правда, эта модель расположена параллельна плоскости проекции, а значит и искажений за счет перспективы быть не должно. Попробуем сдвинуть верхние две вершины на единицу вдоль оси z, и проблема станет видна сразу:
Таким образом, необходимо учитывать перспективу при интерполяции атрибутов. Ключевым фактом к этому является то, что, хотя z не может быть корректно интерполировано в пространстве экрана, 1/z — может. Снова рассмотрим проецирование линии:
Мы так же уже знаем, что по подобным треугольникам:
Интерполируя x в пространстве экрана, получаем:
Интерполируя x в пространстве камеры, получаем:
Эти три равенства является ключевыми и на их основе выводятся все последующие формулы. Я не буду приводить полный вывод, поскольку это легко сделать и самостоятельно, и опишу его только вкратце, акцентируя внимание на результатах.
Подставив эти два равенства в уравнение, полученное из соотношений сторон треугольника, и упростив все выражения, мы в итоге получим, что величина, обратная z-координате, может быть линейно интерполирована в пространстве экрана:
Важно, что в данном выражении интерполяция происходит между величинами, обратными z-координатам в пространстве камеры.
Далее, предположим, что в вершинах A и B заданы значения некого атрибута, обозначим их T1 и T2, который так же может быть линейно интерполирован в пространстве камеры:
Используя промежуточные результаты из вывода выше, мы можем записать, что величина Tc / Zc может быть так же корректно интерполирована в пространстве экрана:
Подведя итоги, мы получили, что 1 / Zc и Tc / Zc могут быть линейно интерполированы в пространстве экрана. Теперь мы легко можем получить значение Tc:
Собственно, стоимость перспективно-корректной интерполяции и заключается, в основном, в этом делении. Если в ней нет большой необходимости, то лучше минимизировать количество атрибутов, для которых она используется и обойтись простым линейным интерполированием в пространстве экрана, если это возможно. Ниже изображен корректный результат текстурирования:
Для реализации коррекции перспективы нам нужны значения, обратные глубине (z-координате) вершин в пространстве камеры. Вспомним, что происходит при умножении на матрицу проекции:
Вершины из пространства камеры переходят в пространство отсечения. В частности, z-координата подвергается определенным изменениям (которые в дальнейшем понадобятся для буфера глубины) и уже не совпадает с z-координатой вершины в пространстве камеры, так что использовать ее мы не можем. А что совпадает — так это w-координата, поскольку мы явно кладем в нее z из пространства камеры (достаточно посмотреть на 4-й столбец матрицы). На самом деле, нам нужно даже не сама z, а 1 / z. И мы получаем ее фактически «бесплатно», поскольку при переходе в NDC мы делим все вершины на z (которая лежит в w-координате):
А, значит, можем просто заменить ее на обратное значение:
Ниже будет представлено описание трех подходов к растеризации полигонов. Полные примеры кода будут отсутствовать, поскольку очень многое в нем зависит от реализации, и это будет скорее путать, чем помогать. В конце статьи будет ссылка на проект, и, если необходимо, можно посмотреть код реализации в нем.
Я назвал этот алгоритм «стандартным», поскольку это наиболее часто описываемый алгоритм растеризации для программных рендереров. Он проще для понимания, чем traversal-алгоритмы и растеризация в однородных координатах, и, соответственно, проще в реализации.
Итак, начнем с треугольника, который мы хотим растеризовать. Предположим, для начала, что это треугольник с горизонтальной нижней гранью.
Суть этого алгоритма заключается в последовательном движении вдоль боковых граней и закрашивании пикселей между ними. Для этого сначала вычисляются значения смещения вдоль оси X за каждое смещение на единицу вдоль оси Y.
Затем, начинается движение вдоль сторон. Важно, что движение начинается с ближайшего центра, а не с Y-координаты вершины v0, поскольку пиксели представлены именно этими точками. Если Y-координата v0 уже лежит на центре, то мы все равно переходим к следующему центру по этой оси, поскольку v0 лежит как на левой так и на правой грани, а значит этот пиксель не должен включаться в изображение:
Когда мы переходим к следующей строке, мы так же начинаем движение только со следующего центра вдоль оси X. Если же грань проходит через центр пикселя, то на левой грани мы включаем пиксель в изображение, а на правой нет.
Аналогичным образом алгоритм работает для треугольников с горизонтальной верхней стороной. Те треугольники, который не имеют ни одной горизонтальной стороны, просто делятся на два треугольника — один с горизонтальной верхней и один с горизонтальной нижней. Для этого ищется пересечение горизонтальной линии, проходящей через одну из вершин треугольника (средней по Y-координате), с другой гранью:
После этого каждый из этих треугольников растеризуется по алгоритму выше. Необходимо так же корректно вычислить значения z и w координат в новой вершине — например, интерполировать их. Аналогично, наличие этой вершины необходимо учитывать при интерполяции атрибутов.
Интерполяция атрибутов без коррекции перспективы происходит следующим образом — при движении вдоль боковых граней мы вычисляем интерполированные значения атрибутов в начальной и конечной точки линии, которую собираемся растеризовывать. Затем, эти значение линейно интерполируются вдоль этой линии. Если коррекция перспективы нужна для атрибута, то вместо этого мы интерполируем T/z вдоль граней полигона (вместо того, чтобы интерполировать просто T — значение атрибута), а так же 1/z. Затем, эти значения в начальной и конечной точках линии интерполируются вдоль нее и используются, чтобы получить итоговое значение атрибута с учетом перспективы, по формуле, данной выше. Нужно помнить, что 1/z, на которую я ссылаюсь, на самом деле лежит в w-координате вектора после всех произведенных трансформаций.
Это целая группа алгоритмов, использующих один и тот же подход, основанный на уравнениях граней полигона.
Уравнение грани — это уравнение линии, на которой лежит эта грань. Другими словами, это уравнение прямой, проходящей через две вершины полигона. Соответственно, каждый треугольник характеризуется тремя линейными уравнениями:
Начнем с того, что опишем уравнение прямой, проходящей через две точки (в качестве них выступают пара вершин треугольника):
Мы можем переписать его в следующем виде:
Из последнего выражения видно, что вектор n перпендикулярен вектору v0 — v1 (координаты поменяны местами, и X-координата взята со знаком минус). Таким образом, n — это нормаль к линии, образованной двумя вершинами. Это все то же уравнение прямой, а, значит, подставив туда точку (x, y) и получив ноль, мы знаем, что эта точка лежит на прямой. Что насчет остальных значений? Тут нам и пригодится форма записи с нормалью. Мы знаем, что скалярное произведение двух векторов вычисляет длину проекции первого вектора на второй, умноженную на длину второго вектора. В качестве первого вектора выступает нормаль, а в качестве второго — вектор из первой вершины к точке (x, y):
И у нас есть три возможных варианта:
Все они изображены ниже:
Мы так же можем задать уравнение прямой таким образом, чтобы нормаль указывала в обратном направлении — достаточно просто домножить его на минус единицу. В дальнейшем я буду предполагать, что уравнение составлено таким образом, что нормаль указывает внутрь треугольника.
Используя эти уравнения, мы можем определить треугольник как пересечение трех положительных полуплоскостей.
Таким образом, общая часть traversal-алгоритмов выглядит следующим образом:
Остановимся на реализации top-left rule. Теперь, когда мы оперируем нормалью к грани, мы можем дать более строгие определения для левой и верхней граней:
Так же важно заметить, что координаты нормали совпадают с коэффициентами a и b в каноническом уравнении прямой: ax + by + c = 0.
Ниже представлен пример функции, определяющей, находится ли пиксель в положительной полуплоскости относительно одной из граней (используя top-left rule). Ей достаточно принимать три аргумента на вход: значение уравнения грани в точке, и координаты нормали:
Простая и полезная оптимизация при вычислении значений уравнений: если мы знаем значение в пикселе с координатами (x, y), то для вычисления значения в точке (x + 1, y) достаточно добавить значение коэффициента a. Аналогично, для вычисления значения в (x, y + 1) достаточно добавить коэффициент b:
Следующий шаг — интерполяция атрибутов и коррекция перспективы. Для этого используются барицентрические координаты. Эти координаты, в которых точка треугольника описывается как линейная комбинация вершин (формально, подразумевая, что точка является центром масс треугольника, при соответствующем весе вершин). Мы будем использовать нормализованный вариант — т.е. суммарный вес трех вершин равен единице:
У этой системы координат так же есть очень полезное свойство, которое позволяет их вычислять: барицентрические координаты равны отношению площадей треугольников, образованных на рисунке выше, к общей площади треугольника (по этой причине они так же иногда называются areal coordinates):
Третья координата может вычисляться не через площади треугольников, поскольку сумма трех координат равна единице — фактически, мы имеем только две степени свободы.
Теперь все готово для линейной интерполяции атрибутов: значение атрибута в заданной точке треугольника равно линейной комбинации барицентрических координат и значений атрибута в соответствующих вершинах:
Для коррекции перспективы мы используем другую формулу — сначала, вычисляем интерполированное значение T/z, затем интерполированное значение 1/z, и затем делим их друг на друга, чтобы получить итоговое значение T с учетом перспективы:
Разница между различными traversal-алгоритмами заключается в том, как выбираются пиксели для проверки. Мы рассмотрим несколько вариантов.
Как ясно из названия, этот алгоритм просто строит axis-aligned bounding box полигона, и проходит по всем пикселям внутри него. Пример:
Этот алгоритм состоит из следующих шагов:
Это можно изобразить следующим образом:
Проверить, что пиксель находится левее полигона можно следующим образом — хотя бы для одной грани, у которой нормаль указывает вправо (т.е. a > 0), значение уравнения этой грани отрицательно.
Этот алгоритм можно рассматривать как улучшенный вариант backtracking-алгоритма. Вместо того чтобы «вхолостую» проходить по пикселям в линии, пока не найдется пиксель, с которого мы можем начать двигаться в правую сторону, мы запоминаем информацию о пикселе, с которого мы начали движение на линии, а затем проходим по пикселям слева и справа от него.
Этот алгоритм изначально был описан в публикации Triangle scan conversion using 2D homogeneous coordinates, Marc Olano & Trey Greer. Его основными преимуществами являются отсутствие необходимости в отсечении и делении на w-координату в процессе трансформации вершин (за исключением пары оговорок — они будут описаны позже).
Первым делом, предположим, что, к началу растеризации, x и y координаты вершин содержат в себе значения, которые отображаются в координаты на экране простым делением на соответствующую w-координату. Это может немного изменить код трансформации вершин, при условии, что поддерживается несколько алгоритмов растеризации, поскольку он не включает в себя деление на w-координату. Координаты в однородном двухмерном пространстве передаются напрямую в функцию, которая производит растеризацию.
Рассмотрим подробнее вопрос линейной интерполяции атрибутов вдоль полигона. Поскольку значение атрибута (назовем его p) растет линейно, он должен удовлетворять следующему уравнению (в трехмерном пространстве):
Поскольку точка (x, y, z) проецируется на плоскость с использованием однородных координат (x, y, w), где w = z, мы так же можем записать это уравнение в однородных координатах:
Представим, что мы знаем коэффициенты a, b и с (мы рассмотрим их нахождение чуть позже). При растеризации мы имеем дело с координатами пикселей в пространстве экрана, которые связаны с координатам в однородном пространстве по следующей формуле (это было наше первоначальное предположение):
Мы можем выразить значение p/w используя только координаты в пространстве экрана, путем деления на w:
Для получение корректного значения p при помощи экранных координат, нам достаточно поделить это значение на 1/w (или, что то же самое, умножить на w):
1/w, в свою очередь, может быть посчитано по аналогичному алгоритму — достаточно представить, что мы имеем некий параметр, который одинаков во всех вершинах: p = [1 1 1].
Теперь рассмотрим, каким образом мы можем найти коэффициенты a, b и с. Поскольку для каждого атрибута заданы его значения в вершинах полигона, мы на самом деле имеем систему уравнений вида:
Мы можем переписать эту систему в матричной форме:
И решение:
Важно заметить, что нам необходимо посчитать всего лишь одну обратную матрицу на полигон — затем эти коэффициенты могут использоваться для нахождения корректного значения атрибута в любой точке экрана. Так же, поскольку нам необходимо вычислить определитель матрицы для ее инвертирования, мы получаем некоторую вспомогательную информацию, поскольку определитель так же вычисляет объем тетраэдра с вершинами в начале координат и точках полигона, умноженного на два (это следует из определения смешанного произведения векторов). Если определитель равен нулю, это значит, что полигон не может быть отрисован, поскольку он либо вырожденный, либо повернут ребром по отношению к камере. Так же, объем тетраэдра может быть со знаком плюс и со знаком минус — и это может использоваться при отсечении полигонов, которые повернуты «спиной» к камере (так называемое backface culling). Если мы считаем корректным порядок вершин против часовой стрелки, то полигоны, у которых значением определителя положительно, должны быть пропущены (при условии использования левосторонней системы координат).
Таким образом, вопрос интерполяции атрибутов уже решен — мы можем вычислить корректное значение (с учетом перспективы) любого атрибута в заданной точке экрана. Осталось только решить, каким точкам экрана принадлежит полигону.
Вспомним, каким образом проверялась принадлежность пикселю к полигону в traversal-алгоритмах. Мы вычисляли уравнения граней, и затем проверяли их значения в нужной точке экрана. Если они все были положительные (или нулевые, но принадлежали к левой или верхней граням), то мы закрашивали пиксель. Поскольку мы уже умеем интерполировать атрибуты вдоль поверхности треугольника, мы можем использовать точно такой же подход, считая, что интерполируем некий псевдо-атрибут, который равен нулю вдоль грани и некоему положительному значению (самое удобное — 1) в противоположной вершине (фактически, это плоскости, проходящие через эти грани):
Соответственно, значения этих псевдо-атрибутов для каждой из граней:
Используя их мы можем вычислить соответствующие коэффициенты a, b и с для каждой из граней и получить их уравнения:
Теперь мы можем аналогичным образом интерполировать их значения вдоль поверхности треугольника и вычислять их значения в нужной нам точке. В случае, если оно положительно, либо же оно нулевое, но мы находимся на левой и верхней грани, пиксель находится внутри полигона и должен быть закрашен. Мы так же можем применить небольшую оптимизацию — нам совсем не нужны точные значения уравнений граней, достаточно его знака. Поэтому можно избежать деления на 1/w, мы можем просто проверить знаки p/w и 1/w — они должны совпадать.
Поскольку мы оперируем все теми же уравнения граней, многое, сказанное в разделе о traversal-алгоритмах, может быть применено и к этому алгоритму тоже. Например, top-left rule может быть реализован аналогичным образом, а значения уравнений граней могут рассчитываться инкрементально, что является полезной оптимизацией.
При представлении этого алгоритма, я написал, что данный алгоритм не требует реализации отсечения, поскольку оперирует в однородных координатах. Это почти целиком верно, за исключением одного случая. Могут быть ситуации при работе с w-координатами точек, которые близки к началу координат (или совпадают с ним). В этом случае могут произойти переполнения при интерполяции атрибутов. Так что хорошей идеей будет добавление еще одной «грани», которая расположена параллельно плоскости xy и находится на расстоянии z near от начала координат, чтобы избежать подобных ошибок.
При описании traversal-алгоритмов я упомянул несколько вариантов выбора множества пикселей, которые следует проверять на принадлежность треугольнику (axis aligned bounding box, backtracking, zigzag алгоритмы). Их можно применить и здесь. Это и есть ситуация, в которой все-таки необходимо будет деление вершин на w-координату для вычисления граничных значений (например, координат bounding box'а), следует только предусмотреть ситуации, когда w <= 0. Конечно, есть и другие способы. Проход по всем пикселям экрана — заведомо неудачный в виду производительности. Можно так же использовать тайловую растеризацию, описание которой выходит за рамки этой статьи.
Проект, в котором можно посмотреть примеры реализаций: github.com/loreglean/lantern. Пулл реквесты с фиксами и прочим приветствуются, об ошибках в коде или вопросы по нему лучше писать в личку.
Наши входные данные — это набор полигонов (мы будем рассматривать только треугольники): координаты их вершин (система координат зависит от алгоритма) и значения атрибутов в каждой из этих вершин, которые в дальнейшем будут интерполироваться вдоль поверхности треугольника. Существует несколько подводных камней, которые я рассмотрю в этой статье:
- Правило заполнения пикселей (filling convention)
- Точность
- Коррекция перспективы при интерполяции аттрибутов (perspective-correct interpolation)
Я рассмотрю три подхода к растеризации:
- «стандартный» алгоритм, использующий наклон граней
- целый ряд алгоритмов, основанных на использовании уравнений граней полигона (traversal-алгоритмы)
- алгоритм растеризации в однородных координатах
Так же в конце будет ссылка на проект, который является примером реализации, оттуда же будут и примеры кода.
Основы
Итак, растеризация — это процесс поиска пикселей, «входящих» в заданный полигон. Для начала, мы будем считать, что нам достаточно закрасить полигон сплошным цветом — ничего лишнего.
Представим, что у нас есть следующий треугольник для вывода на экран (все координаты уже представлены в пространстве экрана):
Какие пиксели необходимо закрасить? Пиксель может быть целиком вне полигона, частично в полигоне и целиком в полигоне:
Все просто для двух случаев:
- Пиксель не входит в полигон целиком (красный цвет на картинке) — не закрашиваем
- Пиксель входит в полигон целиком (зеленый цвет на картинке) — закрашиваем
Третий случай (пиксель частично находится внутри полигона) — сложнее. Первое решение, которое приходит на ум — считать что все такие пиксели либо входят в полигон, либо нет. Но оно ведет к неверному результату. Трехмерные модели, которые мы собираемся отрисовывать, состоят из множества треугольников, которые, в общем случае, не должны накладываться друг на друга. Перекрывающие друг друга треугольники не имеют смысла, поскольку всего лишь дублируют уже существующую информацию. Таким образом, множество полигонов имеют общие между собой грани. Самый простой пример — прямоугольник:
Оранжевым цветом отмечены пиксели, которые частично входят в оба полигона. Теперь представим, что мы растеризуем оба этих полигона. Если мы решаем, что все пиксели, частично входящие в полигон, должны быть заполнены, мы получим заполнение одних и тех же пикселей дважды (или больше, в случае если есть общая вершина для более чем двух полигонов). Это может не показаться проблемой на первый взгляд, но, на самом деле, это приведет к различным артефактам при использовании некоторых техник, таких как альфа-смешивание (отрисовка с использованием альфа-канала для имитации прозрачности). Так же это ведет к снижению производительности, т.к. количество пикселей, для которых нам необходимо вычислять значения атрибутов, увеличивается. Если же мы, наоборот, решим, что такие пиксели не входят в итоговое изображение и не должны быть заполнены, мы получим «дыры» между полигонами, что неприемлимо.
Таким образом мы пришли к пониманию того, что каждый пиксель при отрисовке смежных полигонов должен быть заполнен ровно один раз. Это требование, которое соблюдают и Direct3D и OpenGL.
Проблема возникает из-за необходимости отображения из непрерывного (система координат экрана) в дискретное (пиксели на мониторе). Традиционный алгоритм растеризации (при отрисовке без сглаживания) решает это следующим образом: каждому пикселю сопоставляется некая точка (sample point), которая и отвечает за вхождение пикселя в полигон. Так же, именно в этой точке считаются значения всех необходимых атрибутов. Другими словами, все пространство, занимаемое пикселем в системе координат экрана, «представляется» одной точкой. Как правило, это центр: (0.5, 0.5):
Теоретически, можно брать любую точку внутри пикселя, вместо центра. Другие значения приведут к тому, что изображение может быть «сдвинуто» на пиксель в одну из сторон. Так же, в ситуации со смежным полигонами, для пикселей, в которых не расположены вершины треугольников, использование точки (0.5, 0.5) обладает хорошим свойством: эта точка входит в тот полигон, который охватывает более 50% площади прямоугольника, представляющего пиксель.
Таким образом, если центр пикселя входит в полигон, то считается, что пиксель принадлежит полигону. Но теперь возникает следующая проблема: что, если два полигона имеют общую грань, которая проходит через центр пикселя? Мы уже поняли, что пиксель должен принадлежать только одному из двух треугольников, но какому именно? На картинке ниже такой пиксель помечен красным цветом:
Эту проблему решает так называемое «соглашение о заполнении пикселей» (filling convention).
Соглашение о заполнении
Итак, предположим мы столкнулись с ситуацией, описаной выше — два полигона делят между собой грань, которая проходят ровно через центр пикселя. Наша задача состоит в том, чтобы выяснить, какому из полигонов принадлежит этот пиксель.
Де-факто стандартом является так называемое top-left rule: ему следует DirectX и большинство реализаций OpenGL. Суть этого правила такова: если грань полигона проходит через центр пикселя, то этот пиксель принадлежит полигону в двух случаях — если это левая грань или верхняя грань (отсюда и название).
Понятия левой, правой, верхней и нижней граней требуют пояснений. Пока что мы не будем давать точных определений (мы это сделаем, когда дойдем до traversal-алгоритмов), а опишем их более простым языком:
- Верхняя грань — горизонтальная грань, которая находится выше всех остальных граней
- Нижняя грань — горизонтальная грань, которая находится ниже всех остальных граней
- Левая грань — грань, которая расположена в левой части треугольника и не является горизонтальной
- Правая грань — грань, которая расположена в правой части треугольника и не является горизонтальной
Примеры:
Теперь рассмотрим случай смежных полигонов. Если грань — смежная, и является левой в одном полигоне, то эта же грань является правой для всех полигонов, которые делят эту грань с этим полигоном. Аналогичное правило работает для верхних и нижних граней:
Мы можем использовать это свойство для того, чтобы определять, какому из смежных полигонов принадлежит пиксель. Если мы договоримся, что пиксель, чей центр лежит на общей грани, принадлежит только полигонам, у которых эта грань — левая, то он автоматически не будет принадлежать смежным полигонам, поскольку для них эта грань — правая. И то же самое для верхней грани.
Несмотря на то, что правило верхней и левой грани встречается чаще всего, мы можем использовать любое подходящее сочетание. Например, правило нижней и левой грани, верхней и правой и т.д. Direct3D обязывает использовать top-left rule, OpenGL же не так строг и позволяет использовать любое правило, решающее проблему принадлежности пикселя. Я в дальнейшем буду предполагать использование top-left rule.
Точность
Рассмотрим следующие два полигона:
Второй полигон может быть получен из первого в результате вращения на некоторый угол. В итоге, некоторые пиксели дополнительно включаются в итоговое изображение (такие пиксели помечены зеленым), а некоторые, наоборот, исчезают из него (помечены красным). Соответственно, нам необходимо учитывать дробные части координат вершин. Если мы будем их отбрасывать, то получим проблемы при рисовании нестатической сцены. Если, например, заставить полигон очень медленно вращаться, то он будет это делать дерганно — поскольку грани будут резко «прыгать» из одного положения в другое, вместо того, чтобы корректно обрабатывать промежуточные результаты. Разницу легко понять, сравнив два этих видео:
Конечно, в случае со статической сценой таких проблем не возникнет.
Интерполяция атрибутов
Прежде чем перейти непосредственно к алгоритмам растеризации, остановимся на интерполяции атрибутов.
Атрибут — это некая информация, связанная с объектом, которая необходима для его корректной отрисовки по заданному алгоритму. Таким атрибутом может быть все, что угодно. Одними из самых частых вариантов являются: цвет, текстурные координаты, координаты нормали. Значения атрибута задаются в вершинах сетки объекта. При растеризации полигонов, эти атрибуты интерполируются вдоль поверхности треугольников и используются для вычисления цвета каждого из пикселей.
Самым простым примером (и своеобразным аналогом «hello world») является отрисовка треугольника, в каждой вершине которого задан один атрибут — цвет:
В этом случае, если мы будем присваивать каждому пикселю полигона цвет, являющийся результатом линейной интерполяции цветов трех вершин, мы получим следующее изображение:
Способ, которым производится интерполяция, зависит от данных, которыми мы оперируем в процессе отрисовки, а они, в свою очередь, зависят от алгоритма, который используется при растеризации. Например, при использовании «стандартного» алгоритма мы можем использовать простую линейную интерполяцию значений между двумя пикселями, а при использовании traversal-алгоритмов — барицентрические координаты. Поэтому мы отложим это до описания самих алгоритмов.
Тем не менее, есть еще важная тема, на которой необходимо остановиться заранее: интерполяция атрибутов с коррекцией перспективы.
Самым простым способом интерполяции является линейная интерполяция в пространстве экрана: после того, как полигон был спроецирован на плоскость проекции, мы линейным образом интерполируем атрибуты вдоль поверхности треугольника. Важно понимать, что эта интерполяция не является корректной, поскольку она не учитывает произведенную проекцию.
Рассмотрим проецирование линии на плоскость проекции d = 1. На начальной и конечной вершинах установлены некие атрибуты, которые линейно изменяются в пространстве камеры (и в мировом). После того, как произведена проекция, эти атрибуты не растут линейно в пространстве экрана. Если, например, взять среднюю точку в пространстве камеры (v = v0 * 0.5 + v1 * 0.5), то после проекции эта точка не будет лежать в середине спроецированной линии:
Легче всего это заметить при текстурировании объектов (я буду использовать простое текстурирование без фильтрации в примерах ниже). Я еще не описывал процесс текстурирования подробно (и это тема отдельной статьи), поэтому пока что ограничусь кратким описанием.
При текстурировании в каждой вершине полигона задается значение атрибута текстурных координат (его часто называют uv по названию соответствующих осей). Это нормализованные координаты (от 0 до 1), которые определяют, какой участок текстуры будет использован.
Теперь представим, что мы хотим нарисовать текстурированный прямоугольник и задали четыре значения атрибута uv таким образом, чтобы текстура использовалась целиком:
Кажется, все неплохо:
Правда, эта модель расположена параллельна плоскости проекции, а значит и искажений за счет перспективы быть не должно. Попробуем сдвинуть верхние две вершины на единицу вдоль оси z, и проблема станет видна сразу:
Таким образом, необходимо учитывать перспективу при интерполяции атрибутов. Ключевым фактом к этому является то, что, хотя z не может быть корректно интерполировано в пространстве экрана, 1/z — может. Снова рассмотрим проецирование линии:
Мы так же уже знаем, что по подобным треугольникам:
Интерполируя x в пространстве экрана, получаем:
Интерполируя x в пространстве камеры, получаем:
Эти три равенства является ключевыми и на их основе выводятся все последующие формулы. Я не буду приводить полный вывод, поскольку это легко сделать и самостоятельно, и опишу его только вкратце, акцентируя внимание на результатах.
Подставив эти два равенства в уравнение, полученное из соотношений сторон треугольника, и упростив все выражения, мы в итоге получим, что величина, обратная z-координате, может быть линейно интерполирована в пространстве экрана:
Важно, что в данном выражении интерполяция происходит между величинами, обратными z-координатам в пространстве камеры.
Далее, предположим, что в вершинах A и B заданы значения некого атрибута, обозначим их T1 и T2, который так же может быть линейно интерполирован в пространстве камеры:
Используя промежуточные результаты из вывода выше, мы можем записать, что величина Tc / Zc может быть так же корректно интерполирована в пространстве экрана:
Подведя итоги, мы получили, что 1 / Zc и Tc / Zc могут быть линейно интерполированы в пространстве экрана. Теперь мы легко можем получить значение Tc:
Собственно, стоимость перспективно-корректной интерполяции и заключается, в основном, в этом делении. Если в ней нет большой необходимости, то лучше минимизировать количество атрибутов, для которых она используется и обойтись простым линейным интерполированием в пространстве экрана, если это возможно. Ниже изображен корректный результат текстурирования:
Для реализации коррекции перспективы нам нужны значения, обратные глубине (z-координате) вершин в пространстве камеры. Вспомним, что происходит при умножении на матрицу проекции:
Вершины из пространства камеры переходят в пространство отсечения. В частности, z-координата подвергается определенным изменениям (которые в дальнейшем понадобятся для буфера глубины) и уже не совпадает с z-координатой вершины в пространстве камеры, так что использовать ее мы не можем. А что совпадает — так это w-координата, поскольку мы явно кладем в нее z из пространства камеры (достаточно посмотреть на 4-й столбец матрицы). На самом деле, нам нужно даже не сама z, а 1 / z. И мы получаем ее фактически «бесплатно», поскольку при переходе в NDC мы делим все вершины на z (которая лежит в w-координате):
float const w_inversed{ 1.0f / v.w };
v.x *= w_inversed;
v.y *= w_inversed;
v.z *= w_inversed;
// NDC to screen
// ...
А, значит, можем просто заменить ее на обратное значение:
float const w_inversed{ 1.0f / v.w };
v.x *= w_inversed;
v.y *= w_inversed;
v.z *= w_inversed;
v.w = w_inversed;
// NDC to screen
// ...
Алгоритмы растеризации
Ниже будет представлено описание трех подходов к растеризации полигонов. Полные примеры кода будут отсутствовать, поскольку очень многое в нем зависит от реализации, и это будет скорее путать, чем помогать. В конце статьи будет ссылка на проект, и, если необходимо, можно посмотреть код реализации в нем.
«Стандартный» алгоритм
Я назвал этот алгоритм «стандартным», поскольку это наиболее часто описываемый алгоритм растеризации для программных рендереров. Он проще для понимания, чем traversal-алгоритмы и растеризация в однородных координатах, и, соответственно, проще в реализации.
Итак, начнем с треугольника, который мы хотим растеризовать. Предположим, для начала, что это треугольник с горизонтальной нижней гранью.
Суть этого алгоритма заключается в последовательном движении вдоль боковых граней и закрашивании пикселей между ними. Для этого сначала вычисляются значения смещения вдоль оси X за каждое смещение на единицу вдоль оси Y.
Затем, начинается движение вдоль сторон. Важно, что движение начинается с ближайшего центра, а не с Y-координаты вершины v0, поскольку пиксели представлены именно этими точками. Если Y-координата v0 уже лежит на центре, то мы все равно переходим к следующему центру по этой оси, поскольку v0 лежит как на левой так и на правой грани, а значит этот пиксель не должен включаться в изображение:
Когда мы переходим к следующей строке, мы так же начинаем движение только со следующего центра вдоль оси X. Если же грань проходит через центр пикселя, то на левой грани мы включаем пиксель в изображение, а на правой нет.
Аналогичным образом алгоритм работает для треугольников с горизонтальной верхней стороной. Те треугольники, который не имеют ни одной горизонтальной стороны, просто делятся на два треугольника — один с горизонтальной верхней и один с горизонтальной нижней. Для этого ищется пересечение горизонтальной линии, проходящей через одну из вершин треугольника (средней по Y-координате), с другой гранью:
После этого каждый из этих треугольников растеризуется по алгоритму выше. Необходимо так же корректно вычислить значения z и w координат в новой вершине — например, интерполировать их. Аналогично, наличие этой вершины необходимо учитывать при интерполяции атрибутов.
Интерполяция атрибутов без коррекции перспективы происходит следующим образом — при движении вдоль боковых граней мы вычисляем интерполированные значения атрибутов в начальной и конечной точки линии, которую собираемся растеризовывать. Затем, эти значение линейно интерполируются вдоль этой линии. Если коррекция перспективы нужна для атрибута, то вместо этого мы интерполируем T/z вдоль граней полигона (вместо того, чтобы интерполировать просто T — значение атрибута), а так же 1/z. Затем, эти значения в начальной и конечной точках линии интерполируются вдоль нее и используются, чтобы получить итоговое значение атрибута с учетом перспективы, по формуле, данной выше. Нужно помнить, что 1/z, на которую я ссылаюсь, на самом деле лежит в w-координате вектора после всех произведенных трансформаций.
Traversal алгоритмы
Это целая группа алгоритмов, использующих один и тот же подход, основанный на уравнениях граней полигона.
Уравнение грани — это уравнение линии, на которой лежит эта грань. Другими словами, это уравнение прямой, проходящей через две вершины полигона. Соответственно, каждый треугольник характеризуется тремя линейными уравнениями:
Начнем с того, что опишем уравнение прямой, проходящей через две точки (в качестве них выступают пара вершин треугольника):
Мы можем переписать его в следующем виде:
Из последнего выражения видно, что вектор n перпендикулярен вектору v0 — v1 (координаты поменяны местами, и X-координата взята со знаком минус). Таким образом, n — это нормаль к линии, образованной двумя вершинами. Это все то же уравнение прямой, а, значит, подставив туда точку (x, y) и получив ноль, мы знаем, что эта точка лежит на прямой. Что насчет остальных значений? Тут нам и пригодится форма записи с нормалью. Мы знаем, что скалярное произведение двух векторов вычисляет длину проекции первого вектора на второй, умноженную на длину второго вектора. В качестве первого вектора выступает нормаль, а в качестве второго — вектор из первой вершины к точке (x, y):
И у нас есть три возможных варианта:
- Значение равно 0 — точка лежит на прямой
- Значение больше 0 — точка лежит в положительной полуплоскости
- Значение меньше 0 — точка лежит в отрицательной полуплоскости
Все они изображены ниже:
Мы так же можем задать уравнение прямой таким образом, чтобы нормаль указывала в обратном направлении — достаточно просто домножить его на минус единицу. В дальнейшем я буду предполагать, что уравнение составлено таким образом, что нормаль указывает внутрь треугольника.
Используя эти уравнения, мы можем определить треугольник как пересечение трех положительных полуплоскостей.
Таким образом, общая часть traversal-алгоритмов выглядит следующим образом:
- Вычисляем значения уравнений граней для точки
- Если все значения положительные — пиксель закрашивается. Если одно из них нулевое, значит пиксель лежит на одной из граней, и мы используем top-left правило, чтобы решить, принадлежит ли пиксель полигону
- Переходим к следующему пикселю
Остановимся на реализации top-left rule. Теперь, когда мы оперируем нормалью к грани, мы можем дать более строгие определения для левой и верхней граней:
- Левая грань — грань, нормаль которой имеет положительную x-координату (т.е. указывает в правую сторону)
- Верхняя грань — грань, нормаль которой имеет отрицательную y-координату, в случае, если ось Y указывает вверх. Если ось Y указывает вниз (я буду придерживаться этого варианта), то y-координата у верхних граней положительна
Так же важно заметить, что координаты нормали совпадают с коэффициентами a и b в каноническом уравнении прямой: ax + by + c = 0.
Ниже представлен пример функции, определяющей, находится ли пиксель в положительной полуплоскости относительно одной из граней (используя top-left rule). Ей достаточно принимать три аргумента на вход: значение уравнения грани в точке, и координаты нормали:
Пример кода
inline bool pipeline::is_point_on_positive_halfplane_top_left(
float const edge_equation_value, float const edge_equation_a, float const edge_equation_b) const
{
// Если точка находится на грани, используем top-left rule
//
if (std::abs(edge_equation_value) < EPSILON)
{
if (std::abs(edge_equation_a) < EPSILON)
{
// edge.a == 0.0f, значит это горизонтальная грань, либо верхняя, либо нижняя
//
// Если y-координата нормали положительна, мы на верхней грани
// Иначе на нижней
return edge_equation_b > 0.0f;
}
else
{
// Если x-координата нормали положительна, мы на левой грани
// Иначе на правой
return edge_equation_a > 0.0f;
}
}
else
{
// Просто проверяем, что мы в положительной полуплоскости
return edge_equation_value > 0.0f;
}
}
Простая и полезная оптимизация при вычислении значений уравнений: если мы знаем значение в пикселе с координатами (x, y), то для вычисления значения в точке (x + 1, y) достаточно добавить значение коэффициента a. Аналогично, для вычисления значения в (x, y + 1) достаточно добавить коэффициент b:
Следующий шаг — интерполяция атрибутов и коррекция перспективы. Для этого используются барицентрические координаты. Эти координаты, в которых точка треугольника описывается как линейная комбинация вершин (формально, подразумевая, что точка является центром масс треугольника, при соответствующем весе вершин). Мы будем использовать нормализованный вариант — т.е. суммарный вес трех вершин равен единице:
У этой системы координат так же есть очень полезное свойство, которое позволяет их вычислять: барицентрические координаты равны отношению площадей треугольников, образованных на рисунке выше, к общей площади треугольника (по этой причине они так же иногда называются areal coordinates):
Третья координата может вычисляться не через площади треугольников, поскольку сумма трех координат равна единице — фактически, мы имеем только две степени свободы.
Теперь все готово для линейной интерполяции атрибутов: значение атрибута в заданной точке треугольника равно линейной комбинации барицентрических координат и значений атрибута в соответствующих вершинах:
Для коррекции перспективы мы используем другую формулу — сначала, вычисляем интерполированное значение T/z, затем интерполированное значение 1/z, и затем делим их друг на друга, чтобы получить итоговое значение T с учетом перспективы:
Разница между различными traversal-алгоритмами заключается в том, как выбираются пиксели для проверки. Мы рассмотрим несколько вариантов.
AABB-алгоритм
Как ясно из названия, этот алгоритм просто строит axis-aligned bounding box полигона, и проходит по всем пикселям внутри него. Пример:
Backtracking-алгоритм
Этот алгоритм состоит из следующих шагов:
- Начинаем с самого верхнего пикселя, расположенного ниже самой верхней вершины
- Двигаемся налево до тех пор, пока не встретим пиксель левее полигона (backtracking)
- Двигаемся направо и закрашиваем пиксели до тех пор, пока не встретим пиксель правее полигона
- Переходим на линию ниже и начинаем снова со второго шага
Это можно изобразить следующим образом:
Проверить, что пиксель находится левее полигона можно следующим образом — хотя бы для одной грани, у которой нормаль указывает вправо (т.е. a > 0), значение уравнения этой грани отрицательно.
Zigzag-алгоритм
Этот алгоритм можно рассматривать как улучшенный вариант backtracking-алгоритма. Вместо того чтобы «вхолостую» проходить по пикселям в линии, пока не найдется пиксель, с которого мы можем начать двигаться в правую сторону, мы запоминаем информацию о пикселе, с которого мы начали движение на линии, а затем проходим по пикселям слева и справа от него.
- Начинаем с самого верхнего пикселя, расположенного ниже самой верхней вершины
- Запоминаем положение
- Двигаемся налево и закрашиваем пиксели, входящие в полигон, до тех пор, пока не встретим пиксель левее полигона (backtracking)
- Возвращаемся к пикселю, с которого мы начали (мы запомнили его в шаге 2), и двигаемся направо, закрашивая пиксели, входящие в полигон, пока не встретим пиксель вне полигона
- Переходим на линию ниже и начинаем снова со второго шага
Алгоритм растеризации в однородных координатах
Этот алгоритм изначально был описан в публикации Triangle scan conversion using 2D homogeneous coordinates, Marc Olano & Trey Greer. Его основными преимуществами являются отсутствие необходимости в отсечении и делении на w-координату в процессе трансформации вершин (за исключением пары оговорок — они будут описаны позже).
Первым делом, предположим, что, к началу растеризации, x и y координаты вершин содержат в себе значения, которые отображаются в координаты на экране простым делением на соответствующую w-координату. Это может немного изменить код трансформации вершин, при условии, что поддерживается несколько алгоритмов растеризации, поскольку он не включает в себя деление на w-координату. Координаты в однородном двухмерном пространстве передаются напрямую в функцию, которая производит растеризацию.
Рассмотрим подробнее вопрос линейной интерполяции атрибутов вдоль полигона. Поскольку значение атрибута (назовем его p) растет линейно, он должен удовлетворять следующему уравнению (в трехмерном пространстве):
Поскольку точка (x, y, z) проецируется на плоскость с использованием однородных координат (x, y, w), где w = z, мы так же можем записать это уравнение в однородных координатах:
Представим, что мы знаем коэффициенты a, b и с (мы рассмотрим их нахождение чуть позже). При растеризации мы имеем дело с координатами пикселей в пространстве экрана, которые связаны с координатам в однородном пространстве по следующей формуле (это было наше первоначальное предположение):
Мы можем выразить значение p/w используя только координаты в пространстве экрана, путем деления на w:
Для получение корректного значения p при помощи экранных координат, нам достаточно поделить это значение на 1/w (или, что то же самое, умножить на w):
1/w, в свою очередь, может быть посчитано по аналогичному алгоритму — достаточно представить, что мы имеем некий параметр, который одинаков во всех вершинах: p = [1 1 1].
Теперь рассмотрим, каким образом мы можем найти коэффициенты a, b и с. Поскольку для каждого атрибута заданы его значения в вершинах полигона, мы на самом деле имеем систему уравнений вида:
Мы можем переписать эту систему в матричной форме:
И решение:
Важно заметить, что нам необходимо посчитать всего лишь одну обратную матрицу на полигон — затем эти коэффициенты могут использоваться для нахождения корректного значения атрибута в любой точке экрана. Так же, поскольку нам необходимо вычислить определитель матрицы для ее инвертирования, мы получаем некоторую вспомогательную информацию, поскольку определитель так же вычисляет объем тетраэдра с вершинами в начале координат и точках полигона, умноженного на два (это следует из определения смешанного произведения векторов). Если определитель равен нулю, это значит, что полигон не может быть отрисован, поскольку он либо вырожденный, либо повернут ребром по отношению к камере. Так же, объем тетраэдра может быть со знаком плюс и со знаком минус — и это может использоваться при отсечении полигонов, которые повернуты «спиной» к камере (так называемое backface culling). Если мы считаем корректным порядок вершин против часовой стрелки, то полигоны, у которых значением определителя положительно, должны быть пропущены (при условии использования левосторонней системы координат).
Таким образом, вопрос интерполяции атрибутов уже решен — мы можем вычислить корректное значение (с учетом перспективы) любого атрибута в заданной точке экрана. Осталось только решить, каким точкам экрана принадлежит полигону.
Вспомним, каким образом проверялась принадлежность пикселю к полигону в traversal-алгоритмах. Мы вычисляли уравнения граней, и затем проверяли их значения в нужной точке экрана. Если они все были положительные (или нулевые, но принадлежали к левой или верхней граням), то мы закрашивали пиксель. Поскольку мы уже умеем интерполировать атрибуты вдоль поверхности треугольника, мы можем использовать точно такой же подход, считая, что интерполируем некий псевдо-атрибут, который равен нулю вдоль грани и некоему положительному значению (самое удобное — 1) в противоположной вершине (фактически, это плоскости, проходящие через эти грани):
Соответственно, значения этих псевдо-атрибутов для каждой из граней:
Используя их мы можем вычислить соответствующие коэффициенты a, b и с для каждой из граней и получить их уравнения:
Теперь мы можем аналогичным образом интерполировать их значения вдоль поверхности треугольника и вычислять их значения в нужной нам точке. В случае, если оно положительно, либо же оно нулевое, но мы находимся на левой и верхней грани, пиксель находится внутри полигона и должен быть закрашен. Мы так же можем применить небольшую оптимизацию — нам совсем не нужны точные значения уравнений граней, достаточно его знака. Поэтому можно избежать деления на 1/w, мы можем просто проверить знаки p/w и 1/w — они должны совпадать.
Поскольку мы оперируем все теми же уравнения граней, многое, сказанное в разделе о traversal-алгоритмах, может быть применено и к этому алгоритму тоже. Например, top-left rule может быть реализован аналогичным образом, а значения уравнений граней могут рассчитываться инкрементально, что является полезной оптимизацией.
При представлении этого алгоритма, я написал, что данный алгоритм не требует реализации отсечения, поскольку оперирует в однородных координатах. Это почти целиком верно, за исключением одного случая. Могут быть ситуации при работе с w-координатами точек, которые близки к началу координат (или совпадают с ним). В этом случае могут произойти переполнения при интерполяции атрибутов. Так что хорошей идеей будет добавление еще одной «грани», которая расположена параллельно плоскости xy и находится на расстоянии z near от начала координат, чтобы избежать подобных ошибок.
При описании traversal-алгоритмов я упомянул несколько вариантов выбора множества пикселей, которые следует проверять на принадлежность треугольнику (axis aligned bounding box, backtracking, zigzag алгоритмы). Их можно применить и здесь. Это и есть ситуация, в которой все-таки необходимо будет деление вершин на w-координату для вычисления граничных значений (например, координат bounding box'а), следует только предусмотреть ситуации, когда w <= 0. Конечно, есть и другие способы. Проход по всем пикселям экрана — заведомо неудачный в виду производительности. Можно так же использовать тайловую растеризацию, описание которой выходит за рамки этой статьи.
На этом все
Проект, в котором можно посмотреть примеры реализаций: github.com/loreglean/lantern. Пулл реквесты с фиксами и прочим приветствуются, об ошибках в коде или вопросы по нему лучше писать в личку.
