game-engine /
devlog /
растеризация-треугольников
Софтверная растеризация: быстрый и точный алгоритм растеризации треугольников на C
Translation of this article in English
Основа трехмерной графики - растеризация треугольников. В этой статье я объясню как работает алгоритм софтверной растеризации треугольников в моём игровом движке.
Сперва я представлю сам алгоритм в его конечном виде, а затем мы разберём его поподробнее:
static inline void SwapFloat(float* a, float* b) { float c = *a; *a = *b; *b = c; }
void DrawTriangle(
float ax, float ay, float az, float au, float av,
float bx, float by, float bz, float bu, float bv,
float cx, float cy, float cz, float cu, float cv
) {
// For every vertex:
// x, y - screen coordinates
// z - depth
// u, v - texture coordinates
// Sort vertices by y-coordinate ascending (y1 <= y2 <= y3)
if (ay > by) {
// swap(a, b)
SwapFloat(&ax, &bx);
SwapFloat(&ay, &by);
SwapFloat(&az, &bz);
SwapFloat(&au, &bu);
SwapFloat(&av, &bv);
}
if (ay > cy) {
// swap(a, c)
SwapFloat(&ax, &cx);
SwapFloat(&ay, &cy);
SwapFloat(&az, &cz);
SwapFloat(&au, &cu);
SwapFloat(&av, &cv);
}
if (by > cy) {
// swap(b, c)
SwapFloat(&bx, &cx);
SwapFloat(&by, &cy);
SwapFloat(&bz, &cz);
SwapFloat(&bu, &cu);
SwapFloat(&bv, &cv);
}
// Round y-coordinates and clamp to screen bounds
int y_min = max( (int)ceilf(ay - 0.5f), 0);
int y_mid = min(max((int)ceilf(by - 0.5f), 0), screen_height);
int y_max = min( (int)ceilf(cy - 0.5f), screen_height);
// Prepare values for perspective-correct interpolation
az = 1.0f / az;
bz = 1.0f / bz;
cz = 1.0f / cz;
au *= az;
av *= az;
bu *= bz;
bv *= bz;
cu *= cz;
cv *= cz;
// Rasterize triangle scanlines
for (int y = y_min; y < y_max; y++) {
float pixel_center = (float)y + 0.5f;
float lt, lx, lz, lu, lv; // left edge
float rt, rx, rz, ru, rv; // right edge
// Calculate left edge
lt = (pixel_center - ay) / (cy - ay);
lx = ax + (cx - ax) * lt;
lz = az + (cz - az) * lt;
lu = au + (cu - au) * lt;
lv = av + (cv - av) * lt;
// Determine if we are in the first or the second half of the triangle
if (y < y_mid) {
// Calculate right edge (first half)
rt = (pixel_center - ay) / (by - ay);
rx = ax + (bx - ax) * rt;
rz = az + (bz - az) * rt;
ru = au + (bu - au) * rt;
rv = av + (bv - av) * rt;
} else {
// Calculate right edge (second half)
rt = (pixel_center - by) / (cy - by);
rx = bx + (cx - bx) * rt;
rz = bz + (cz - bz) * rt;
ru = bu + (cu - bu) * rt;
rv = bv + (cv - bv) * rt;
}
// Ensure "l" is always to the left of "r"
if (lx > rx) {
// swap(l, r)
SwapFloat(&lx, &rx);
SwapFloat(&lz, &rz);
SwapFloat(&lu, &ru);
SwapFloat(&lv, &rv);
}
// Round x-coordinates and clamp to screen bounds
int ilx = (int) ceilf(lx - 0.5f); // top-left rule: ceil to include left edge
int irx = (int)floorf(rx - 0.5f); // top-left rule: floor to exclude right edge
int x_min = max(ilx, 0);
int x_max = min(irx + 1, screen_width);
// Loop over the horizontal range of the current scanline
for (int x = x_min; x < x_max; x++) {
int i = (y * screen_width) + x;
float t = (float)(x - ilx) / (rx - lx);
float z = lz + (rz - lz) * t;
if (z > screen_depth[i]) {
float u = (lu + (ru - lu) * t) / z;
float v = (lv + (rv - lv) * t) / z;
screen_color[i] = SampleTextureColor(texture, u, v);
screen_depth[i] = z;
}
}
}
}Разбор алгоритма
Начнем с того, что наметим план действий. Наша цель - самым эффективным образом закрасить пиксели внутри треугольника, избежав избыточных вычислений.
Сразу отметим, что рисовать пиксели внутри треугольника нам стоит строка за строкой, начиная с верхнего-левого угла, потому что таким образом пиксели хранятся в оперативной памяти. Мы хотим избежать "прыжков" по оперативке и проходиться по буферу линейно - это залог хорошей оптимизации.
Мы должны рассчитать переменные для цикла, по которым мы будем двигаться вдоль оси y и заливать пиксели между гранями треугольника, но сперва нужно подготовить сами вершины.
Шаг 1: Отсортируем вершины по y-координате
if (ay > by) { SwapPoint(&a, &b); }
if (ay > cy) { SwapPoint(&a, &c); }
if (by > cy) { SwapPoint(&b, &c); }Сортировка нужна, чтобы упростить проход по треугольнику. Мы будем предполагать, что a - верхняя вершина, b - средняя, c - нижняя. Это позволит разбить треугольник на две части: верхнюю и нижнюю - так нам проще будет рассчитывать начало и конец горизонтального отрезка, поскольку левая и правая грани будут строго прямыми.
Шаг 2: Top-left filling convention (правило верхнего левого угла)
Очень важный момент, который иногда упускается из внимания: правило растеризации. Дело в том, что если мы хотим избежать "щелей" между соседними треугольниками, то важно придерживаться единого принципа, по которому мы будем округлять координаты. В DirectX и Vulkan принято правило: пиксель считается покрытым, если центр пикселя лежит внутри треугольника. В нашем алгоритме мы тоже будем его придерживаться. Для этого мы округляем y - 0.5 вверх, чтобы учесть центр пикселя:
int y_min = (int)ceilf(ay - 0.5f);
int y_mid = (int)ceilf(by - 0.5f);
int y_max = (int)ceilf(cy - 0.5f);Забегая чуть вперед, то же самое мы будем делать и при округлении координаты x, но там мы будем рисовать левый край включительно, и исключать правый край, округляя его вниз:
int ilx = (int) ceilf(lx - 0.5f); // top-left rule: ceil to include left edge
int irx = (int)floorf(rx - 0.5f); // top-left rule: floor to exclude right edgeПридерживаясь таких правил мы избавимся от зазоров между полигонами. Особенно важно это учитывать, если вы собираетесь использовать софтверный растеризатор для отсечения окклюзий (например при реализации алгоритма Hierarchical Depth Buffer).
Шаг 3: Подготовка к интерполяции с учетом перспективы
az = 1.0f / az;
bz = 1.0f / bz;
cz = 1.0f / cz;Инверсия z-координат позволит нам выполнить перспективно-корректную интерполяцию. Если мы не будем этого делать, то при вычислении UV-координат получим эффект растягивающихся текстур с PS1 - если цель достичь именно такого стилистичего эффекта, то можно намеренно пропустить этот шаг.
Шаг 4: Проход по сканлайнам (вдоль координаты y)
for (int y = y_min; y < y_max; y++) {
...
}В этом цикле мы пойдем сверху вниз вдоль каждой строки, рассчитаем начало и конец горизонтального отрезка, и отрисуем его.
Шаг 5: Вычисление начала и конца горизонтального отрезка
В каждой строке вычисляем координаты x для начала и конца отрезка:
lt = (pixel_center - ay) / (cy - ay);
lx = ax + (cx - ax) * lt;
lz = az + (cz - az) * lt;lt - это параметр линейной интерполяции вдоль левой грани. Левая грань всегда a → c
if (y < y_mid) {
rt = (center_y - ay) / (by - ay);
rx = ax + (bx - ax) * rt;
rz = az + (bz - az) * rt;
// ...
} else {
rt = (center_y - by) / (cy - by);
rx = bx + (cx - bx) * rt;
rz = bz + (cz - bz) * rt;
// ...
}rt - это параметр линейной интерполяции вдоль правой грани. Правая грань может быть либо a → b (верхняя половина треугольника), либо b → c (нижняя половина). Это определяется по y < y_mid.
Шаг 6: Гарантия порядка лево-право
if (lx > rx) { SwapFloat(&lx, &rx); SwapFloat(&lz, &rz); }В треугольнике есть как длинная грань (a → c), так и две других, через которые проходит линия разделения по y_mid. Мы заранее не определяли с какой стороны находится длинная грань, потому что это не имеет значения при вычислении координат, но имеет при отрисовке. Поэтому после того, как мы вычислили координаты для левой и правой грани, мы просто убедимся, что координаты l всегда левее r.
Шаг 7: Растеризация строки
Теперь проходим по пикселям от lx до rx (округляя их по правилам растеризации) и выполняем линейную интерполяцию глубины:
for (int x = x_min; x < x_max; x++) {
int i = (y * screen_width) + x;
float t = (float)(x - ilx) / (rx - lx); // фактор по x (0.0 - начало отрезка, 1.0 - конец)
float z = lz + (rz - lz) * t; // значение глубины (интерполяция между левым и правым краем)
if (z > screen_depth[i]) { // пиксель закрашивается, если он ближе к камере, чем предыдущий
screen_color[i] = 0xFFFFFF;
screen_depth[i] = z;
}
}Шаг 8: Дополнительные параметры вершин
В этой статье вершины имели 5 параметров: x, y, z, u, v.
x y - для положения в экранном пространстве
z - для глубины
u v - для текстурных координат
Но ничего не мешает расширить этот метод и добавить новые параметры вершин. К примеру, вы можете добавить параметр l, который будет отвечать за затухание цвета текстуры - это позволит реализовать повертексное освещение. Вы можете добавить ещё одну пару uv координат для мультитекстурирования или лайтпамов. Всё это делается всего лишь добавлением новых параметров, по аналогии с z или uv.
Этот алгоритм расширяемый и все вычисления в нём работают по одинаковому принципу.
Шаг 9: Оптимизация
Я намеренно упростил код, представленный в начале статьи, чтобы улучшить его читабельность в угоду производительности. Если вы дочитали до этого момента и вас интересует дальнейшая оптимизация, то ниже вы найдете финальную версию алгоритма для реального рендерера:
static inline void SwapFloat(float *a, float *b) { float c = *a; *a = *b; *b = c; }
static void DrawTriangle_Span(
const Texture *texture,
int y,
float lx, float lz, float lu, float lv, // left edge
float rx, float rz, float ru, float rv // right edge
) {
// Ensure "l" is always to the left of "r"
if (lx > rx) {
SwapFloat(&lx, &rx);
SwapFloat(&lz, &rz);
SwapFloat(&lu, &ra);
SwapFloat(&lb, &rb);
}
// Precalculate spans
float span_x = rx - lx;
if (span_x <= 0.0f) {
return; // skip if no pixels to draw
}
float inv_span_x = 1.0f / span_x;
float span_z = rz - lz;
float span_u = ru - lu;
float span_v = rv - lv;
// Round x-coordinates and clamp to screen bounds
int ilx = (int) ceilf(lx - 0.5f); // top-left rule: ceil to include left edge
int irx = (int)floorf(rx - 0.5f); // top-left rule: floor to exclude right edge
int x_min = max(ilx, 0);
int x_max = min(irx + 1, screen_width);
// Precompute interpolant steps
float z_step = span_z * inv_span_x;
float u_step = span_u * inv_span_x;
float v_step = span_v * inv_span_x;
// Initial interpolant values
float t = ((float)x_min + 0.5f - lx) * inv_span_x;
float z = lz + span_z * t;
float u = lu + span_u * t;
float v = lv + span_v * t;
// Get scanline pointers
int scanline = (screen_width * y) + x_min;
DWORD *color_ptr = &screen_color[scanline];
float *depth_ptr = &screen_depth[scanline];
// Loop over the horizontal range of the current scanline
for (int x = x_min; x < x_max; x++) {
// Depth test
if (z <= *depth_ptr) {
goto DISCARD;
}
float inv_z = 1.0f / z; // precompute 1/z for perspective-correct interpolation
// Perspective-correct texture interpolation
float correct_u = u * inv_z;
float correct_v = v * inv_z;
// Sample texture color
*color_ptr = SampleTexture(texture, correct_u, correct_v);
*depth_ptr = z;
DISCARD:
// Advance interpolants
z += z_step;
u += u_step;
v += v_step;
// Advance scanline pointers
color_ptr++;
depth_ptr++;
}
}
void DrawTriangle(
const Texture *texture,
float x1, float y1, float z1, float u1, float v1,
float x2, float y2, float z2, float u2, float v2,
float x3, float y3, float z3, float u3, float v3
) {
// Sort vertices by y-coordinate ascending (y1 <= y2 <= y3)
if (y1 > y2) {
SwapFloat(&x1, &x2);
SwapFloat(&y1, &y2);
SwapFloat(&z1, &z2);
SwapFloat(&u1, &u2);
SwapFloat(&v1, &v2);
}
if (y1 > y3) {
SwapFloat(&x1, &x3);
SwapFloat(&y1, &y3);
SwapFloat(&z1, &z3);
SwapFloat(&u1, &u3);
SwapFloat(&v1, &v3);
}
if (y2 > y3) {
SwapFloat(&x2, &x3);
SwapFloat(&y2, &y3);
SwapFloat(&z2, &z3);
SwapFloat(&u2, &u3);
SwapFloat(&v2, &v3);
}
// Round y-coordinates and clamp to screen bounds
int y_min = max( (int)ceilf(y1 - 0.5f), 0);
int y_mid = min(max((int)ceilf(y2 - 0.5f), 0), screen_height);
int y_max = min( (int)ceilf(y3 - 0.5f), screen_height);
if (y_min >= y_max) {
return; // skip if no pixels to draw
}
// Prepare the triangle vertices for perspective-correct interpolation
z1 = 1.0f / z1;
z2 = 1.0f / z2;
z3 = 1.0f / z3;
u1 *= z1;
v1 *= z1;
u2 *= z2;
v2 *= z2;
u3 *= z3;
v3 *= z3;
// Precalculate edges
float dy13 = y3 - y1;
float dx13 = x3 - x1;
float dz13 = z3 - z1;
float du13 = u3 - u1;
float dv13 = v3 - v1;
float dy12 = y2 - y1;
float dx12 = x2 - x1;
float dz12 = z2 - z1;
float du12 = u2 - u1;
float dv12 = v2 - v1;
float dy23 = y3 - y2;
float dx23 = x3 - x2;
float dz23 = z3 - z2;
float du23 = u3 - u2;
float dv23 = v3 - v2;
// Draw the top part of the triangle
for (int y = y_min; y < y_mid; y++) {
float pixel_center = (float)y + 0.5f;
float lt = (pixel_center - y1) / dy13;
float rt = (pixel_center - y1) / dy12;
DrawTriangle_Span(
texture, y,
x1 + dx13 * lt,
z1 + dz13 * lt,
u1 + du13 * lt,
v1 + dv13 * lt,
x1 + dx12 * rt,
z1 + dz12 * rt,
u1 + du12 * rt,
v1 + dv12 * rt
);
}
// Draw the bottom part of the triangle
for (int y = y_mid; y < y_max; y++) {
float pixel_center = (float)y + 0.5f;
float lt = (pixel_center - y1) / dy13;
float rt = (pixel_center - y2) / dy23;
DrawTriangle_Span(
texture, y,
x1 + dx13 * lt,
z1 + dz13 * lt,
u1 + du13 * lt,
v1 + dv13 * lt,
x2 + dx23 * rt,
z2 + dz23 * rt,
u2 + du23 * rt,
v2 + dv23 * rt
);
}
}Спасибо за уделённое внимание! Буду рад, если вы найдете применение этому алгоритму в своих проектах.