Раскрашиваем треугольник программным способом

Мне интересно воссоздавать работу GPU программно, поэтому я решил поделиться моим пониманием того, как можно выполнить раскраску треугольников методами простой линейной алгебры.

Я напишу обобщённый 2D-массив элементов типа uint32_t под названием colorBuffer, который может быть резервным хранилищем чего-то простого, например, выводимого в файл изображения, или буфером цвета окна SDL.

Задаём треугольник

Треугольник можно задать тремя точками, или вершинами. Каждая вершина имеет различные атрибуты; пока мы добавим каждой вершине только положение на экране.

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

struct Point
{
	float x;
	float y;
};

struct Vertex
{
	Point position;
};

// Top middle
Vertex v0 = {WINDOW_WIDTH/2, 0.0f};

// Bottom right
Vertex v1 = {WINDOW_WIDTH, WINDOW_HEIGHT};

// Bottom left
Vertex v2 = {0.0f, WINDOW_HEIGHT};

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

Каждая вершина имеет позицию, состоящую из двух значений с плавающей запятой. Их два, потому что при работе с экраном у нас есть всего два измерения: ширина (x) и высота (y).

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

Функция ребёр

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


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

Это красные векторы, названные e10 (v1 — v0), e21 (v2 — v1) и e02 (v0 — v2).

Если мы хотим узнать, находится ли точка P внутри треугольника, то можно использовать свойство векторного произведения 2D-векторов. Для каждого ребра (e10, e21, e02) мы можем найти векторное произведение вектора этого ребра с вектором из начальной точки ребра к точке P.


Новый вектор является результатом вычитания p — v0, что создаёт вектор из v0 в p. Если мы возьмём двухмерное векторное произведение двух зелёных векторов (p-v0 и e10), то получим значение, являющееся отрицательным, положительным или нулевым.

• Положительное: точка P находится справа от e10 (внутри треугольника)
• Отрицательное: точка P находится слева от e10 (снаружи треугольника)
• Нулевое: точка P находится на e10 (ни внутри, ни снаружи)

То же самое мы делаем для двух других векторов рёбер.


Зелёный вектор является результатом вычитания p — v1, что создаёт вектор из v1 в p.


Зелёный вектор является результатом вычитания p — v2, что создаёт вектор из v2 в p.

Двухмерное векторное произведение получается довольно просто:

A x B = A.x * B.y — A.y * B.x

Vector e10 = v1 - v0;
Vector e21 = v2 - v1;
Vector e02 = v0 - v2;

Vector p0 = p - v0;
Vector p1 = p - v1;
Vector p2 = p - v2;

Тогда если мы хотим протестировать точку P относительно e10:

float result = Edge(e10, p);

Всё это означает, что если мы хотим узнать, находится ли точка внутри треугольника, можно взять векторные произведения вектора каждой точки с вектором каждого ребра. Если все они больше нуля (или равны ему), то точка находится внутри треугольника и мы можем раскрасить этот пиксель.

Мы можем задать ещё одну структуру для представления Vector и перегрузить оператор вычитания, чтобы создавать Vector из вычитания двух точек. Структуры Point и Vector имеют одинаковое содержимое (два float), но благодаря их разделению код становится более понятным.

struct Vector
{
	float x;
	float y;
};

Vector operator-(Point lhs, Point rhs)
{
	Vector result;

	result.x = lhs.x - rhs.x;
	result.y = lhs.y - rhs.y;

	return result;
}

Затем мы создаём функцию, сообщающую нам по позициям двух векторов (точек рёбер) и тестируемой точки векторное произведение векторов из этих точек.

float Edge(Point v0, Point v1, Point p)
{
	// Vector from edge origin to test point
	Vector a = p - v0;

	// Vector from edge origin to edge end
	Vector b = v1 - v0;

	// 2D cross product
	// Zero: Point is on edge
	// Positive: Point is right of edge
	// Negative: Point is left of edge
	return a.x * b.y - a.y * b.x;
}

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

Чтобы отрендерить треугольник, мы итеративно обходим все пиксели экрана и проверяем, содержится ли их позиция внутри треугольника. Если да, то раскрашиваем пиксель белым. Если нет, то ничего не делаем.

// Top middle
Vertex v0 = {WINDOW_WIDTH/2, 0.0f};

// Bottom right
Vertex v1 = {WINDOW_WIDTH, WINDOW_HEIGHT};

// Bottom left
Vertex v2 = {0.0f, WINDOW_HEIGHT};

for (unsigned int y = 0; y < WINDOW_HEIGHT; ++y)
{
	for (unsigned int x = 0; x < WINDOW_WIDTH; ++x)
	{
		Point p = {(float)x, (float)y};

		// Clockwise
		float e10 = Edge(v1.position, v0.position, p);
		float e21 = Edge(v2.position, v1.position, p);
		float e02 = Edge(v0.position, v2.position, p);

		// Point is inside triangle
		if (e10 >= 0.0f && e21 >= 0.0f && e02 >= 0.0f)
		{
			colorBuffer[y][x] = 0xffffffff;
		}
	}
}

Так мы получаем следующее изображение:

Затенение треугольника

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

Это можно реализовать при помощи барицентрических координат. Векторное произведение двух 2D-векторов на самом деле является площадью параллелограмма, образованного этими двумя векторами. Половина площади этого параллелограмма — это площадь меньшего треугольника, образованного двумя точками треугольника и проверяемой точкой.

Если соединить проверяемую точку с каждой вершиной, то можно визуализировать три меньших треугольника, образующих общий треугольник. Сумма площадей этих треугольников составляет площадь всего треугольника.


Каждая из этих раскрашенных площадей обозначает меньший треугольник.

Если указать на каждом меньшем треугольнике его площадь, то мы увидим нечто интересное.

• Когда точка P приближается к v0, площадь красного треугольника становится больше.
• Когда точка P приближается к v1, больше становится площадь зелёного треугольника.
• Когда точка P приближается к v2, больше становится площадь синего треугольника.

При перемещении точки P по треугольнику площади составляющих его треугольников изменяются в зависимости от близости точки к каждой из трёх вершин. Другими словами, если с каждой вершиной связаны какие-то атрибуты (например цвет), то можно использовать выведенное выше векторное произведение для получения значения, сообщающего, какая пропорция атрибута каждой из вершин должна вносить вклад в точку как целое.

Если мы разделим каждый из результатов, возвращённых из функции рёбер и разделим их на общую площадь основного треугольника, то получим нормализованное значение (от 0.0 до 1.0) для каждой вершины. Это значение является весом этой вершины в проверяемой точке. Можно умножить вес каждой вершины на атрибут вершины и сложить все три взвешенных значения, чтобы получить окончательное значение.

Это можно продемонстрировать, назначив каждой вершине цвет.

Мы создадим struct для задания цвета, которая будет всего лишь четырьмя float, и добавим переменную цвета в структуру Vertex.

struct Color
{
	float r, g, b, a;
};

struct Vertex
{
	Point position;
	Color color;
};

Затем мы переопределим треугольник и назначим красный цвет вершине v0, зелёный — v1, а синий — v2.

// Top middle - red
Vertex v0 =
{
	{WINDOW_WIDTH/2, 0.0f},
	{1.0f, 0.0f, 0.0f, 1.0f}
};

// Bottom right - green
Vertex v1 =
{
	{WINDOW_WIDTH, WINDOW_HEIGHT},
	{0.0f, 1.0f, 0.0f, 1.0f}
};

// Bottom left - blue
Vertex v2 =
{
	{0.0f, WINDOW_HEIGHT},
	{0.0f, 0.0f, 1.0f, 1.0f}
};

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

float area = Edge(v2.position, v1.position, v0.position);

for (unsigned int y = 0; y < WINDOW_HEIGHT; ++y)
{
	for (unsigned int x = 0; x < WINDOW_WIDTH; ++x)
	{
		Point p = {(float)x, (float)y};

		// Clockwise
		float e0 = Edge(v2.position, v1.position, p);
		float e1 = Edge(v0.position, v2.position, p);
		float e2 = Edge(v1.position, v0.position, p);

		// Point is inside triangle
		if (e0 >= 0.0f && e1 >= 0.0f && e2 >= 0.0f)
		{
			// Barycentric weights
			float w0 = e0 / area;
			float w1 = e1 / area;
			float w2 = e2 / area;

			float r =
				  w0 * v0.color.r
				+ w1 * v1.color.r
				+ w2 * v2.color.r;

			float g =
				  w0 * v0.color.g
				+ w1 * v1.color.g
				+ w2 * v2.color.g;

			float b =
				  w0 * v0.color.b
				+ w1 * v1.color.b
				+ w2 * v2.color.b;

			uint8_t red = r * 255;
			uint8_t green = g * 255;
			uint8_t blue = b * 255;
			uint8_t alpha = 255;

			colorBuffer[y][x] = (red << 24 | green << 16 | blue << 8 | alpha);
		}
	}
}

Значение, возвращаемое функцией Edge, является площадью параллелограмма, образованного векторами, но нас интересует площадь треугольника, равная её половине. Однако, поскольку мы делим результаты функции Edge (e1, e2, e3) на ещё один результат функции Edge (площадь), то 1/2 сокращается, поэтому нам не нужно об этом заботиться.

Когда треугольник меньше размера всего окна/изображения, то будет неэффективно обходить весь размер окна/изображения. Логичнее будет создать ограничивающий прямоугольник этого треугольника, вычислив его минимальные и максимальные значения X и Y, а затем обойдя только эту область.

Результаты

После выполнения программы получается следующий затенённый треугольник:


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

Заключение

Все, кто работал с графическими API наподобие OpenGL должны увидеть сходства между написанным мной и тем, как используется OpenGL.

В OpenGL мы передаём в GPU буфер данных вершин, содержащий атрибуты каждой вершины (например, позицию, цвет, нормаль), а он затем интерполирует эти атрибуты между пикселями (фрагментами), составляющими треугольник на экране.

В статье мы выполнили похожие действия.