Растеризация и барицентрические координаты

Растеризация решает, какие пиксели накрывает треугольник, и плавно смешивает в них данные трёх вершин.

Барицентрические координаты — три веса (u, v, w), которые показывают, насколько точка внутри треугольника близка к каждой из его вершин; их сумма равна 1.

Зачем это знать

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

Идея барицентрических координат

Любую точку P внутри треугольника ABC можно записать как взвешенную смесь вершин: P = u·A + v·B + w·C, где u+v+w=1 и все веса неотрицательны. В вершине A веса (1,0,0), в B — (0,1,0), в C — (0,0,1). В центре — (1/3, 1/3, 1/3).

Барицентрические веса в треугольнике:

          A (1,0,0)
         / \
        /   \
       / P   \     P = u*A + v*B + w*C
      /   .    \    u + v + w = 1
     /__________\
   B (0,1,0)   C (0,0,1)

Интерполяция атрибута

Имея веса, любой атрибут (цвет, UV, глубину) в точке P считают теми же весами от значений в вершинах. Покажем интерполяцию цвета.

# Цвета в вершинах треугольника
colorA = (255, 0, 0)    # красная вершина
colorB = (0, 255, 0)    # зелёная
colorC = (0, 0, 255)    # синяя

def interpolate(u, v, w, A, B, C):
    return tuple(round(u*a + v*b + w*c) for a, b, c in zip(A, B, C))

print("В вершине A (1,0,0):", interpolate(1, 0, 0, colorA, colorB, colorC))
print("В центре (1/3 каждая):", interpolate(1/3, 1/3, 1/3, colorA, colorB, colorC))
print("Между A и B (0.5,0.5,0):", interpolate(0.5, 0.5, 0, colorA, colorB, colorC))

Вывод:

В вершине A (1,0,0): (255, 0, 0)
В центре (1/3 каждая): (85, 85, 85)
Между A и B (0.5,0.5,0): (128, 128, 0)

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

Точка внутри или снаружи

Барицентрические веса заодно отвечают на вопрос «накрывает ли треугольник пиксель»: если все три веса ≥ 0, точка внутри; если хоть один отрицателен — снаружи. Растеризатор перебирает пиксели ограничивающего прямоугольника и оставляет те, у которых все веса неотрицательны.

def is_inside(u, v, w):
    return u >= 0 and v >= 0 and w >= 0

print("Веса (0.3,0.3,0.4):", is_inside(0.3, 0.3, 0.4))   # внутри
print("Веса (0.5,0.7,-0.2):", is_inside(0.5, 0.7, -0.2)) # снаружи

Вывод:

Веса (0.3,0.3,0.4): True
Веса (0.5,0.7,-0.2): False

Как работает под капотом

В перспективе интерполяцию делают перспективно-корректной: атрибуты делят на глубину w перед интерполяцией и умножают обратно после. Без этого текстуры на наклонных поверхностях «поплывут» (заметный артефакт на старых консолях). Глубина (z) тоже интерполируется барицентрически — её потом сравнивает z-buffer.

Частые ошибки

Забыть про перспективную коррекцию — текстуры искажаются на наклонных гранях.
Считать, что интерполяция всегда линейна в экранных координатах — в перспективе это не так.
Путать барицентрические веса с UV-координатами текстуры — это разные вещи.

Итоги

Растеризация определяет покрытые пиксели и интерполирует атрибуты трёх вершин.
Барицентрические веса (u,v,w) суммируются в 1 и задают смесь вершин.
Все веса ≥ 0 ⇒ точка внутри треугольника.
В перспективе интерполяция должна быть перспективно-корректной.