OEOE.MOE

Содержание

Вступление

Глава 1. Кадровый буфер

Глава 2. Линии

Глава 3. Трёхмерность

Глава 4. Треугольники

Глава 5. Матрицы

Вступление

Процесс трёхмерной растеризации - это преобразование данных о геометрии объекта в двухмерное изображение.

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

Как правило, растеризацией занимается отдельный видеочип, производитель которого обеспечивает ему совместимость с набором стандартов, таких как: DirectX, OpenGL, Vulkan и др. Они описывают то, каким образом разработчик может управлять работой чипа и заставить его отрисовывать нужную ему картинку. Однако

Глава 1. Кадровый буфер

Буфер - это область в оперативной памяти, в которой линейно хранятся несжатые значения цветов. Разрабатывая алгоритмы ратеризации необходимо знать несколько тонкостей, связанных с работой с ними:

1. Буферы хранятся линейно

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

   ПЛОХО:

   while (i--) { buffer[i] = ... }

   for (int x = 0; x < width; ++x) {
       for (int y = 0; y < height; ++y) {
           /* ... */
       }
   }

   ХОРОШО:

   for (int y = 0; y < height; ++y) {
       for (int x = 0; x < width; ++x) {
           /* ... */
       }
   }

2. Чтение обходится дороже, чем запись

   Старайтесь минимизировать количество операций чтения из памяти в регистр. Читайте данные блоками по 32 бита - использование 8-битных типов не даст прироста производительности.

   ПЛОХО:

   u8 *pixel = &((u8 *)buffer)[(x + y * width) * depthInBytes];
   pixel[0] = 0xDD; // a
   pixel[1] = 0xCC; // b
   pixel[2] = 0xBB; // g
   pixel[3] = 0xAA; // r

   ХОРОШО:

   u32 *pixel = &((u32 *)buffer)[x + y * width];
   *pixel = 0xAABBCCDD; // RGBA

3. Предпочтительнее хранить цвета в порядке RGBA

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

   switch (color & 0xFF) {
       case 0x00: /* полностью прозрачный цвет - ничего не делаем */ break;
       case 0xFF: /* полностью НЕпрозрачный цвет - рисуем пиксель */ break;
       default: /* полупрозрачный цвет - выполняем alpha blending */ break;
   }

4. Не все инструкции равны

   Всегда нужно держать в голове, что операция деления во много раз затратнее операции умножения, что переключение между работой с целочисленными и двоичными типами занимает время, что процессор всегда пытается выполнить векторизацию (распараллеливание) циклов и однотипных вычислений, а ещё в любом if-условии процессор ожидает, что результатом будет true и наперёд просчитывает дальнейшее исполнение кода в этой ветке (branch prediction).

   Instruction tables^[pdf]

Глава 2. Рисование линий

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

Существует простой и быстрый алгоритм под названием Digital Differential Analyzer.

Его код выглядит следующим образом:

void DrawLine_DDA(f32 x0, f32 y0, f32 x1, f32 y1, u32 color)
{
    // находим разницу между точками (ширину и высоту линии)
    f32 w = x1 - x0;
    f32 h = y1 - y0;

    // длина линии = наибольшая из сторон
    f32 length = max(abs(w), abs(h));
    if (length > 0) {

        f32 sx = w / length; // шаг по обеим осям
        f32 sy = h / length;

        // проходимся по всей длине линии
        for (int i = 0; i < length; ++i) {
            DrawPoint(ceil(x0), ceil(y0), color);

            x0 += sx; // прибавляем к текущей точке шаг
            y0 += sy;
        }
    }
}

Не вдаваясь в подробности скажу лишь, что приведенный выше алгоритм

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

for (int i = -4; i <= 4; ++i)
{
    int x0 = -4, y0 =  i;
    int x1 =  4, y1 =  i;
    int x2 =  i, y2 = -4;
    int x3 =  i, y3 =  4;

    DrawLine_DDA((x0 + 0.5) * w, (y0 + 0.5) * h,
                 (x1 + 0.5) * w, (y1 + 0.5) * h, 0xFFFFFFFF);

    DrawLine_DDA((x2 + 0.5) * w, (y2 + 0.5) * h,
                 (x3 + 0.5) * w, (y3 + 0.5) * h, 0xFFFFFFFF);
}

Глава 3. Трёхмерная математика

Используя вышеописанные функции,

Вернемся к нашей сетке, которую мы нарисовали в предыдушей главе. Что, если мы поменяем местами оси Y и Z? Вспомним формулу перспективного преобразования - деление на глубину дает нам ощущение трехменрости. Именно это и произойдет с нашей сеткой:

/* Mode 7 style floor rendering */
for (int y = floorStart; y < floorEnd; ++y) {
    for (int x = 0; x < screen->width; ++x) {

        f32 xx = xx - (screen->width / 2);
        xx /= y; /* - perspective divide, y = z (depth) */

        int u = (int)AbsF32(xx * texture->width) % texture->width;
        int v = (int)AbsF32(y * texture->height) % texture->height;

        u32 color = ((u32 *)texture->data)[u + v * texture->step];
        ((u32 *)screen->data)[x + y * screen->step] = color;
    }
}

Глава 4. Заливка треугольников

На первый взгляд может показаться, что заливка треугольника - это тривиальная задача. На самом же деле за ней кроется парочка хитростей и приёмов.

Представим себе треугольник, описанный тремя точками: p1, p2, p3.

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

1. Сортировка координат по оси Y

2. Построчная заливка

function fillTriangle(x0, y0, x1, y1, x2, y2) {
    qwerty
}

Треугольник - простейшая геометрическая фигура, которая имеет площадь. Имея площадь мы можем нанести на неё текстуру.

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

Мы начнем рассмотрение с наиболее простого и очевидного метода - нахождения точки внутри треугольника.

Как мы можем описать трехмерный объект? Это не более, чем набор точек, каждая из которых имеет свою координату в трехмерном пространстве.

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

Для начала нам необходимо найти высоту треугольника и разбить его на две части с плоским низом и с плоским верхом. От точки излома нужно найти противоположную позицию на самом длинном отрезке.

void FillTriangle(int x0, int y0, int x1, int y1, int x2, int y2, u32 color)
{
    /* sort coordinates along y axis */
    if (y0 > y1) { int t = x0; x0 = x1; x1 = t; t = y0; y0 = y1; y1 = t; }
    if (y0 > y2) { int t = x0; x0 = x2; x2 = t; t = y0; y0 = y2; y2 = t; }
    if (y1 > y2) { int t = x1; x1 = x2; x2 = t; t = y1; y1 = y2; y2 = t; }

    /* find edge slopes */
    int x3 = x0 + (int)(((f32)(y1 - y0) / (y2 - y0)) * (x2 - x0));

    int yMin = y0;
    int yMax = y1;
    f32 xMin;
    f32 xMax;
    f32 ix0;
    f32 ix1;

    int height = yMax - yMin;
    if (height > 0) {

        xMin = (f32)(x0);
        xMax = (f32)(x0);

        ix0 = (f32)(x1 - x0) / height;
        ix1 = (f32)(x3 - x0) / height;

        if (ix0 > ix1) {
            f32 t = ix0; ix0 = ix1; ix1 = t;
        }

_FILL_TRIANGLE:
        if (yMin < 0) {
            xMin -= ix0 * yMin;
            xMax -= ix1 * yMin;
            yMin  = 0;
        }

        for (int y = yMin; y < yMax; ++y) {
            for (int x = xMin; x < xMax; ++x) {
                DrawPoint(x, y, color);
            }
            xMin += ix0;
            xMax += ix1;
        }
    }

    if (yMax < y2) {
        yMin = y1;
        yMax = y2;

        height = yMax - yMin;
        if (height > 0) {

            xMin = (f32)(x1);
            xMax = (f32)(x3);

            ix0 = (f32)(x2 - x1) / height;
            ix1 = (f32)(x2 - x3) / height;

            if (ix0 < ix1) {
                f32 t = xMin; xMin = xMax; xMax = t;
                    t =  ix0;  ix0 = ix1;  ix1 = t;
            }

            goto _FILL_TRIANGLE;
        }
    }
}

Глава 5. Матричные преобразования

Для структурирования данных и создания единой модели вычислений используются вектора и матрицы.

transformation: model -> world -> camera -> perspective -> screen

Трехмерная модель существует в своей локальной системе координат, где все точки расположены относительно её центра (координаты (0,0,0)). Если мы хотим разместить модель в игровом мире, то мы выполняем соответствующие преобразования координат к миру. А если мы наполнили мир различными объектами и хотим посмотреть на них под разными углами, то нам потребуется преобразование координат к камере.

Трехмерная модель находится в своей локальной системе координат, где все точки расположены относительно её центра. Центром является нулевая координата.

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

После того, как ваш мир будет наполнен различными объектами, вам наверняка захочется посмотреть на них под разными углами. Здесь придётся выполнить преобразование полученных ранее координат к коодинатам камеры.