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

Постановка задач

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

1. Использование только базового объёма ОЗУ (2 килобайта).

2. Возможность попиксельного редактирования графики.

3. Вывод двумерных примитивов.

4. Вывод графики в монохромном и четырёхцветном режиме.

5. Методы быстрого вывода горизонтальных линий.

6. Эффективный метод растеризации треугольников.

7. Импорт STL-моделей.

8. Определение видимости полигонов относительно камеры.

9. Вращение трёхмерных моделей.

10. Трансформация трёхмерных моделей.

Этот минимальная функциональность, которую требуется реализовать.

Реализация

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

Вот основные технические параметры консоли:

• Центральный процессор: 8-битный MOS Technology 6502 (1,79 МГц);

• ОЗУ: 2 КБ;

• ПЗУ: 32 КБ;

• Графика: пиксельная, 256x240 пикселей, 64 спрайта (8x8 или 8x16 пикселей);

• Память для графики: 8 КБ;

• Кадры в секунду: 60 FPS (NTSC) или 50 FPS (PAL).

Организация памяти и маппер

Базовый картридж NES имеет 32 килобайта для хранения кода и констант (ПЗУ) и 8 килобайтов для хранения графики (в виде двух страниц по 256 тайлов). Для работы движка необходима возможность редактирования видеопамяти, а стандартный картридж использует ПЗУ для хранения графической информации. Поэтому далее в проекте буду использовать картридж на основе маппера UnROM, о нём я рассказывал в одной из прошлых статей. Этот маппер позволяет использовать до 256 килобайтов для хранения программы и константных данных, а также содержит ОЗУ вместо ПЗУ для хранения графической информации, что позволяет редактировать содержимое видеопамяти в реальном времени.

Из имеющихся у нас двух килобайтов ОЗУ для видеобуфера получится использовать только один килобайт, остальной объём будет использоваться для системных нужд (из них 256 байтов можно будет использовать для хранения значений переменных).

Редактирование отдельных пикселей

Как я уже говорил выше, все графика состоит из тайлов 8х8 пикселей. При этом каждый пиксель описывается двумя битами, то есть в рамках одного тайла нам доступно всего лишь три цвета (нулевой цвет означает прозрачность). Так как на каждый пиксель у нас уходит два бита, для хранения одного тайла требуется 16 байтов.

Способ хранения информации о цветах каждого пикселя довольно оригинальный. Изображение разбивается на два слоя по восемь байтов. В первом слое хранится информация о младших битах цветов, то есть на каждую строку тайла уходит ровно один байт (где младший бит — это крайний правый пиксель). Во втором слое всё то же самое, только для старших битов. Ниже привожу хорошую иллюстрацию кодирования тайла, который изображает символ «1/2»:

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

Буфер видеопамяти разбит на четыре массива по 256 значений, чтобы не использовать двухбайтные индексные переменные. Это немного усложняет код, но ускоряет обращение к элементам массива. Компилятор CC65 не оптимизирует такие моменты. Давайте рассмотрим функцию редактирования одного пикселя в буфере:

// Тут опишем монохромный режим для наглядности
// Верхние 32 пикселя хранятся в первом буфере
// А нижние 32 пикселя хранятся во втором буфере
//
// X, Y – задают положение пикселя
void set_pixel_to_screen_buffer (void) {
    // Определяем буфер для записи пикселя
    if (Y > 31) {
        pointer = screen_buffer2;
        Y -= 32;
    } else {
        pointer = screen_buffer;
    }
    // Определяем номер первого байта тайла линии для редактирования буфера
    // 8 тайлов на строку, 8 байтов на тайл, 64 байта на строку
    // temp3 = ((y_h & b1111_1000) >> 3) * 64;
    // Номер строки буфера в байтах
    byte_index = ((Y & b1111_1000) << 3) ;    byte_index  += (X & b1111_1000); // Номер тайла в байтах
    // Добавляем номер строки внутри тайла (Один байт - это одна строка тайла)
    byte_index  += (Y & b0000_0111);
    // Определяем положение пикселя/бита
    bit_index = (X & b0000_0111);
    // Ставим пиксель
    // switch позволяет обойтись без операций сдвига
    switch (bit_index) {
        case 0:
            pointer [byte_index] |= b1000_0000;
            break;
        case 1:
            pointer [byte_index] |= b0100_0000;
            break;
        case 2:
            pointer [byte_index] |= b0010_0000;
            break;
        case 3:
            pointer [byte_index] |= b0001_0000;
            break;
        case 4:
            pointer [byte_index] |= b0000_1000;
            break;
        case 5:
            pointer [byte_index] |= b0000_0100;
            break;

        case 6:
            pointer [byte_index] |= b0000_0010;
            break;
        case 7:
            pointer [byte_index] |= b0000_0001;
            break;
    }

}

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

Схема вывода текущего кадра

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

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

Выбор размера итоговой сцены в 8х8 тайлов обусловлен не только размером доступной памяти ОЗУ, но и особенностями вывода спрайтов (в NES тайлы, которое можно выводить в произвольном месте экрана, называются спрайтами, а тайлы, которые выводятся строго по сетке, называется фоновыми тайлами). На одной строке нельзя вывести более 8 спрайтов, поэтому мы ограничены максимальным разрешением в 64 пикселя по горизонтали — это четверть ширины экрана.

Если использовать фоны вместо спрайтов, то можно получить картинку 128×128 пикселей (это размер одной страницы видеопамяти), но это потребует четыре килобайта для буфера и в четыре раза замедлит вывод одного кадра.

Ещё вывод сцены через спрайты позволяет выводить её в любом месте экрана. Это может быть полезно для перемещения 3D-модели относительно статичного фона с минимальными вычислителями затратами.

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

// Функция вывода буфера в видеопамять
// функция подходит для монохромного и цветного режима
// Вывод в монохромном режиме будет не в два раза быстрее,
// так как видеобуфер редактируется только в промежутке между кадрами (время возврата луча ЭЛТ в начало кадра)
void draw_screen_full_buffer (void) {
Wait_Vblank ();
PPU_ADDRESS = 0x0;
PPU_ADDRESS = 0x0;
// Start Tile #0.0:
PPU_DATA = screen_buffer [0];
PPU_DATA = screen_buffer [1];
PPU_DATA = screen_buffer [2];
PPU_DATA = screen_buffer [3];
PPU_DATA = screen_buffer [4];
PPU_DATA = screen_buffer [5];
PPU_DATA = screen_buffer [6];
PPU_DATA = screen_buffer [7];
PPU_DATA = screen_buffer3 [0];
PPU_DATA = screen_buffer3 [1];
PPU_DATA = screen_buffer3 [2];
PPU_DATA = screen_buffer3 [3];
PPU_DATA = screen_buffer3 [4];
PPU_DATA = screen_buffer3 [5];
PPU_DATA = screen_buffer3 [6];
PPU_DATA = screen_buffer3 [7];
// Start Tile #1.0:
PPU_DATA = screen_buffer [8];
PPU_DATA = screen_buffer [9];
PPU_DATA = screen_buffer [10];
PPU_DATA = screen_buffer [11];
…
// Start Tile #12.0:
PPU_DATA = screen_buffer [96];
PPU_DATA = screen_buffer [97];
PPU_DATA = screen_buffer [98];
PPU_DATA = screen_buffer [99];
PPU_DATA = screen_buffer [100];
PPU_DATA = screen_buffer [101];
PPU_DATA = screen_buffer [102];
PPU_DATA = screen_buffer [103];
PPU_DATA = screen_buffer3 [96];
PPU_DATA = screen_buffer3 [97];
PPU_DATA = screen_buffer3 [98];
PPU_DATA = screen_buffer3 [99];
PPU_DATA = screen_buffer3 [100];
PPU_DATA = screen_buffer3 [101];
PPU_DATA = screen_buffer3 [102];
PPU_DATA = screen_buffer3 [103];
SCROLL = 0;
SCROLL = 0;
PPU_CTRL = b1001_0000;
// Ждем следующего конца кадра
Wait_Vblank ();
PPU_ADDRESS = 0x0;
PPU_ADDRESS = 0xd0;
// Start Tile #13.0:
// И т.д.
}

В цветном режиме за один промежуток между кадрами можно загрузить около 15 тайлов, а в монохромном режиме примерно 22 тайла (в PAL-режиме на несколько тайлов больше, но я буду говорить только о NTSC-режиме).

Чтобы не писать 100500 строк вручную, я написал простой скрипт для генерации кода на Python:

# Генератор вывода буфера в видеопамять
addr = 0;
print ("Wait_Vblank ();")
i = 0
while i < 256:
    print ("PPU_DATA = " + "screen_buffer [" + str (i) + "];")
    i += 1
    if i/8 % 22 == 0 and (i != 0):
        print ("SCROLL = 0;")
        print ("SCROLL = 0;")
        print ("Wait_Vblank ();")
    if i % 8 == 0 and (i != 0):
        print ("// Начально тайла " + str (i/8) + ":")
        addr += 16
        print ("PPU_ADDRESS = " +  str ( hex ( (addr & 0x0F00) >> 8 ) ) + ";")
        print ("PPU_ADDRESS = " +  str ( hex (addr & 0x00F0) ) + ";")
i = 0
while i < 256:
    print ("PPU_DATA = " + "screen_buffer2 [" + str (i) + "];")
    i += 1
    if i/8 % 22 == 0 and (i != 0):
        print ("SCROLL = 0;")
        print ("SCROLL = 0;")
        print ("Wait_Vblank ();")
    if i % 8 == 0 and (i != 0):
        print ("// Начально тайла " + str (i/8) + ":")
        addr += 16
        print ("PPU_ADDRESS = " +  str ( hex ( (addr & 0x0F00) >> 8 ) ) + ";")
        print ("PPU_ADDRESS = " +  str ( hex (addr & 0x00F0) ) + ";")

После загрузки буфера в видеопамять он выглядит так (слева изображение на экране, а справа содержимое видеопамяти):

Рисование двумерных примитивов

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

Рисование отрезков

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

// На входе функции координаты начала и конца отрезка
// Функция оптимизирована и не использует дроби и операции умножения
void gen_line(void) {
    dx = x1 - x0;
    dy = y1 - y0;

    // Рассчитываем смещение по горизонтали и вертикали
    // Проверяем направление линии (угол наклона)
    if (dx >= 0) {
        x_inc = 1;
    }  else { // линия направлена вправо
        x_inc = -1;
        dx = -dx; // Нужна абсолютная величина
    } 
    
    // Линия направлена влево
    // проверяем y-составляющую наклона
    if (dy >= 0)  {
        y_inc = 1;
    } else { // Линия направлена вниз
        y_inc = -1;
        dy = -dy; // Нужна абсолютная величина
    } // Линия направлена вверх
    
    // Вычисляем (dx,dy) * 2
    dx2 = dx << 1;
    dy2 = dy << 1;
    // Теперь рисуем линию с учетом того, вдоль какой оси приращение больше
    if (dx > dy) {
        // инициализируем ошибку
        error = dy2 - dx;
        // Чертим линию
        for (k = 0; k <= dx; ++k) {
            // Выводим пиксель
            X = x0;
            Y = y0;
            set_pixel_to_screen_buffer ();
            // Проверяем, нет ли переполнения ошибки
            if (error >= 0) {
                error -= dx2;
                // Переходим на следующую линию
                y0 += y_inc;
            } // if
            // Корректируем ошибку
            error += dy2;
            x0 += x_inc;
        }  
    } else {
        // Инициализируем ошибку
        error = dx2 - dy;
        // Рисуем линию
        for (k = 0; k <= dy; ++k) {
            // Выводим пиксель
            X = x0;
            Y = y0;
            //set_pixel_to_screen_buffer ();
            set_colored_pixel_to_screen_buffer ();
            // Проверяем, нет ли переполнения ошибки
            if (error >= 0) {
                error -= dy2;
                // Переходим к следующей линии
                x0 += x_inc;
            }
            // Корректируем ошибку
            error += dx2;
            y0 += y_inc;
        }  
    } 
}

Алгоритм отлично описан в википедии, а еще лучше почитайте Ламота «Программирование игр для Windows» (книгу легко найти в свободном доступе). В итоге код Ламота я и взял за основу.

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

Вот так выглядит рисование произвольного треугольника с помощью нашей функции рисования отрезков:

// Функция рисования треугольника
// На входе три координаты вершин треугольника
void gen_triangle (void) {
    x0 = vert_x0;
	y0 = vert_y0;	
	x1 = vert_x1;
	y1 = vert_y1;
    gen_line ();
    x0 = vert_x1;
	y0 = vert_y1;	
	x1 = vert_x2;
	y1 = vert_y2;
    gen_line ();
    x0 = vert_x2;
	y0 = vert_y2;	
	x1 = vert_x0;
	y1 = vert_y0;
    gen_line ();
}

Пример вывода треугольника (заодно тестируем и рисование линий):

Быстрое рисование горизонтальных линий

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

В вопросе оптимизации заливки нам очень поможет особенность хранения тайлов в видеопамяти. Думаю, вы уже догадались, как можно быстро нарисовать горизонтальную линию, исходя из информации, которая приведена выше. Мы знаем, что один байт тайла описывает одну строку пикселей тайла (один бит — один пиксель строки). Это значит, что если записать единицы во все биты, то мы выведем сразу 8 пикселей. А запись одного байта — это всего одна инструкция для процессора и никаких дополнительных расчётов. Рассмотрим алгоритм быстрого рисования горизонтальных линий:

// На входе начало и конец отрезка по Х и одна координата Y
void gen_h_line (void) {
    // Меня координаты местами, если начальная координата больше
    if (x0 > x1) {
        temp = x1;
        x1 = x0;
        x0 = temp;
    } else {
        // Линия состоит из одной линии
        if (x0 == x1) {
            X = x0;
            Y = y0;
            set_pixel_to_screen_buffer ();
            return;
        }
    }

    y_h = y0;
     // Определяем буфер для записи пикселей
// В один буфер вся сцена не помещается
    if (y_h > 31) {
        pointer = screen_buffer2;
        y_h -= 32;
    } else {
        pointer = screen_buffer;
    }
    // Определяем номер первого байта тайла линии для редактирования буфера
    // 8 тайлов на строку, 8 байтов на тайл, 64 байта на строку
    // temp3 = ((y_h & b1111_1000) >> 3) * 64; 
    temp3 = ((y_h & b1111_1000) <<3); // Номер строки буфера в байтах
    temp3  += (x0 & b1111_1000); // Номер тайла в байтах
    // Добавляем номер строки внутри тайла (Один байт - это одна строка тайла)
    temp3  += (y_h & b0000_0111);
    
    // Длина линии
    temp = x1 - x0;
    // Генерируем байт для записи в байт тайла
    // (x0 & b0000_0111)  - номер бита в строке первого тайла
    temp2 = (x0 & b0000_0111);
    // Если линия длиннее 7 пикселей
    if (temp > 7) {
        // Заполняем первый тайл
   // Такой некрасивый код нужен для оптимизации
        switch (temp2) {
            case 0:
                temp_tile_0 = b1111_1111;
                break;
            case 1:
                temp_tile_0 = b0111_1111;
                break;
            case 2:
                temp_tile_0 = b0011_1111;
                break;
            case 3:
                temp_tile_0 = b0001_1111;
                break;
            case 4:
                temp_tile_0 = b0000_1111;
                break;
            case 5:
                temp_tile_0 = b0000_0111;
                break;
            case 6:
                temp_tile_0 = b0000_0011;
                break;
            case 7:
                temp_tile_0 = b0000_0001;
                break;
        }
        // Выводим первый тайл линии
        pointer [temp3] |= temp_tile_0;

        // Заполняем тайлы с целыми линиями по 8 пикселей за раз
        temp -= (7 - temp2);
        for (; temp > 7; temp -= 8) {
            temp3 += 8;
            // Закрашиваем сразу 8 пикселей на строке тайла
            pointer [temp3] |= b1111_1111;
        }
        // Рисуем неполный остаток линии, если он есть
        if (temp > 0) {
            switch (temp) {
                case 1:
                    // Рисуем один пиксель
                    temp_tile_0 = b1000_0000; 
                    break;
                case 2:
                    temp_tile_0 = b1100_0000;
                    break;
                case 3:
                    temp_tile_0 = b1110_0000;
                    break;
                case 4:
                    temp_tile_0 = b1111_0000;
                    break;
                case 5:
                    temp_tile_0 = b1111_1000;
                    break;
                case 6:
                    temp_tile_0 = b1111_1100;
                    break;
                case 7:
                    temp_tile_0 = b1111_1110;
                    break;
            }
            // Переходим к следующему тайлу
            temp3 += 8;
            // Закрашиваем последний тайл линии
            pointer [temp3] |= temp_tile_0;
        }
        
    } else {
        // Линия помещается в текущий тайл
  // Начало линии может оказаться в любом пикселе тайла по Х
        if (temp <= (7 - temp2) ) {
            switch (temp) {
                case 1:
				// Рисуем один пиксель
                    temp_tile_0 = b1000_0000; 
                    break;
                case 2:
                    temp_tile_0 = b1100_0000;
                    break;
                case 3:
                    temp_tile_0 = b1110_0000;
                    break;
                case 4:
                    temp_tile_0 = b1111_0000;
                    break;
                case 5:
                    temp_tile_0 = b1111_1000;
                    break;
                case 6:
                    temp_tile_0 = b1111_1100;
                    break;
                case 7:
                    temp_tile_0 = b1111_1110;
                    break;
            }
            temp_tile_0 >>= temp2;
            pointer [temp3] |= temp_tile_0;
        } else {
            // Отрезок не помещает в один тайл
            // Получаем первый тайл,
            switch (temp2) {
                case 0:
                    temp_tile_0 = b1111_1111;
                    break;
                case 1:
                    temp_tile_0 = b0111_1111;
                    break;
                case 2:
                    temp_tile_0 = b0011_1111;
                    break;
                case 3:
                    temp_tile_0 = b0001_1111;
                    break;
                case 4:
                    temp_tile_0 = b0000_1111;
                    break;
                case 5:
                    temp_tile_0 = b0000_0111;
                    break;
                case 6:
                    temp_tile_0 = b0000_0011;
                    break;
                case 7:
                    temp_tile_0 = b0000_0001;
                    break;
            }
            // Записываем первый байт
            pointer [temp3] |= temp_tile_0;
            // Заполняем второй тайл
            // Определяем остаток длины
            temp -= (7 - temp2);
            switch (temp) {
                case 1:
                    temp_tile_0 = b1000_0000; // Рисуем один пиксель
                    break;
                case 2:
                    temp_tile_0 = b1100_0000;
                    break;
                case 3:
                    temp_tile_0 = b1110_0000;
                    break;
                case 4:
                    temp_tile_0 = b1111_0000;
                    break;
                case 5:
                    temp_tile_0 = b1111_1000;
                    break;
                case 6:
                    temp_tile_0 = b1111_1100;
                    break;
                case 7:
                    temp_tile_0 = b1111_1110;
                    break;
            }
            // Переходим к следующему тайлу
            temp3 += 8;
            // Закрашиваем последний тайл линии
            pointer [temp3] |= temp_tile_0;
        }
    }
}

Этот алгоритм особо эффективен для рисования длинных линий, но из-за большого количества сценариев дробления отрезка по тайлам (в худшем случае будет два неполных и один полный тайл на линию). Идеи по оптимизации этой функции приветствую в комментариях ☺

Быстрые вертикальные линии

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

// Функция рисования вертикальных линий
void gen_v_line (void) {
    if (y0 > y1) {
        SWAP (y0, y1);
    }

    // Длина отрезка в пикселях
    dy = y1 - y0; 
    Y = y0;
    // Определяем буфер для записи пикселя
    if (Y > 31) {
        pointer = screen_buffer2;
        Y -= 32;
    } else {
        pointer = screen_buffer;
    }
    // Определяем номер первого байта тайла линии для редактирования буфера
    // 8 тайлов на строку, 8 байтов на тайл, 64 байта на строку
    // temp3 = ((y_h & b1111_1000) >> 3) * 64; 
    byte_index   = ((Y & b1111_1000) << 3) ; // Номер строки буфера в байтах
    byte_index  += (x0 & b1111_1000); // Номер тайла в байтах
    // Добавляем номер строки внутри тайла (Один байт - это одна строка тайла)
    byte_index  += (Y & b0000_0111);

    // Определяем положение пикселя/бита
    bit_index = (x0 & b0000_0111);
    // Определяем какой бит будем включать
    // Всегда ставим один бит за раз в одно и тоже положение
    switch (bit_index) {
        case 0:
            temp = b1000_0000;
            break;
        case 1:
            temp = b0100_0000;
            break;
        case 2:
            temp = b0010_0000;
            break;
        case 3:
            temp = b0001_0000;
            break;
        case 4:
            temp = b0000_1000;
            break;
        case 5:
            temp = b0000_0100;
            break;
        case 6:
            temp = b0000_0010;
            break;
        case 7:
            temp = b0000_0001;
            break;
    }

    // Линия начинается в первом и заходит во второй буфер
    if ( Y + dy > 31) {
        // Рисуем линию до перехода в следующий буфер
        temp_y = Y & b0000_0111;
        for (; Y <= 31; ++Y) {
             // Заполняем текущий тайл
            while (temp_y < 8) {
                pointer [byte_index] |= temp;
                ++byte_index;
                ++Y;
                ++temp_y; 
            }
            temp_y = 0;
            // Переходим к тайлу на новой строке тайлов
            // 56, так как на строку 64 байта, но 8 байт мы прошли в цикле, остается 56
            byte_index += 56;
        }
        // Y = 0, так как мы перешли в новый буфер
        Y = 0;
        // Переходим в следующий буфер
        byte_index  = (x0 & b1111_1000); // Номер тайла в байтах
        pointer = screen_buffer2;
        y1 -= 32;
        // Дорисовываем остаток линии во второй буфер
        while (Y <= y1 ) {
            temp_y = 0;
            // Заполняем текущий тайл
            while (Y <= y1 && temp_y < 8) {
                pointer [byte_index] |= temp;
                ++byte_index;
                ++Y;
                ++temp_y; 
            }
            // Переходим к тайлу на новой строке
            // 56, так как на строку 64 байта, но 8 байт мы прошли в цикле, остается 56
            byte_index += 56;
        }
    } else {
        // Линия помещает в один буфер
        // Определяем сколько еще пикселей попадет в текущий тайл
        temp_y = Y & b0000_0111;
        while (Y <= y1 ) {
            // Заполняем текущий тайл
            while (Y <= y1 && temp_y < 8) {
                pointer [byte_index] |= temp;
                ++byte_index;
                ++Y;
                ++temp_y; 
            }
            temp_y = 0;
            // Переходим к тайлу на новой строке
            // 56, так как на строку 64 байта, но 8 байт мы прошли в цикле, остается 56
            byte_index += 56;
        }
    }
}

Произвольные залитые треугольники

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

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

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

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

Рассмотрим код алгоритма:

// Основная функция растеризации треугольника
void rasterizeTriangle(void) {
    // Сортируем вершины по y-координате
    if (vert_y0 > vert_y1) {  
        temp_x = vert_x0;
        temp_y = vert_y0;

        vert_x0 = vert_x1;
        vert_y0 = vert_y1;

        vert_x1 = temp_x;
        vert_y1 = temp_y; 
    }
    if (vert_y1 > vert_y2) {  
        temp_x = vert_x1;
        temp_y = vert_y1; 

        vert_x1 = vert_x2; 
        vert_y1 = vert_y2; 

        vert_x2 = temp_x; 
        vert_y2 = temp_y; 

        if (vert_y0 > vert_y1) {  
            temp_x = vert_x0; 
            temp_y = vert_y0; 

            vert_x0 = vert_x1; 
            vert_y0 = vert_y1; 
            
            vert_x1 = temp_x; 
            vert_y1 = temp_y; 
        }
    }
    
    //
    // Треугольник плоский сверху 
    //
    /*
      vert_0    vert_1
            \````/
             \  /
        vert_2\/
    */
    
    if (vert_y0 == vert_y1) {
        // Вычисляем приращения для левой стороны
        a  = GET_BIN (vert_x2 - vert_x0, 0); 
        b =  GET_BIN (vert_y2 - vert_y0, 0);
        if (b == 0)
            return;
        DIV_FIX (a, b, c); //(x2-x0)/(y2-y0)
        // Приращение для начала строки
        dxy_l = c;

        a  = GET_BIN (vert_x2 - vert_x1, 0); 
        b =  GET_BIN (vert_y2 - vert_y1, 0);
        if (b == 0)
            return;
        DIV_FIX (a, b, c); // (x2-x1)/(y2-y1)
        // Приращение для конца строки
        dxy_r = c;
        // Начальная и конечная точки вычерчиваемой линии треугольника
        xs = GET_BIN (vert_x0, 0);
        xe = GET_BIN (vert_x1, 0);

        end_y = vert_y2;
    } else {
        //
        // Треугольник, плоский cнизу 
        //
        /*vert_0
            /\
           /  \
    vert_2/____\ vert_1
        */
        // Вычисляем приращения для левой стороны
        a  = GET_BIN (vert_x2 - vert_x0, 0); 
        b =  GET_BIN (vert_y2 - vert_y0, 0);
        if (b == 0)
            return;
        DIV_FIX (a, b, c); //(x2-x0)/(y2-y0)
        // Приращение для левой стороны
        dxy_l = c;

        a  = GET_BIN (vert_x1 - vert_x0, 0); 
        b =  GET_BIN (vert_y1 - vert_y0, 0);
        DIV_FIX (a, b, c); // (x2-x1)/(y2-y1)
        // Приращение для правой
        dxy_r = c;
        // Начальная и конечная точки вычерчиваемой линии треугольника
        xs = GET_BIN (vert_x0, 0);
        xe = GET_BIN (vert_x0, 0);

        end_y = vert_y1;
    }

    // Закрашиваем верхнюю часть треугольника (плоскую снизу или сверху)
    for(y0 = vert_y0; y0 <= end_y; ++y0) {
        // Чертим линию от xs до xe для
        // заданного значения y цветом c
        // Draw_Line((int)(xs+0.5),(int)(xe+0.5),y,c);
        temp16 = xs + 128;
        x0 = GET_INT (temp16);
        temp16 = xe + 128;
        x1 = GET_INT (temp16);
        gen_h_line ();
        // Переходим к следующей строке
        xs += dxy_l;
        xe += dxy_r;
    }

    // Если у треугольника есть нижняя половина
    // Она будет плоская сверху 
    if (end_y == vert_y1) {
        if (x0 > x1) {
            SWAP (x0, x1);
        }
       
        // Вычисляем приращения для левой стороны
        a  = GET_BIN (vert_x2 - x0, 0); 
        b =  GET_BIN (vert_y2 - vert_y1, 0);
        if (b == 0)
            return;
        DIV_FIX (a, b, c); //(x2-x0)/(y2-y0)
        // Приращение для начала строки
        dxy_l = c;

        a  = GET_BIN (vert_x2 - x1, 0); 
        b =  GET_BIN (vert_y2 - vert_y1, 0);
        if (b == 0)
            return;
        DIV_FIX (a, b, c); // (x2-x1)/(y2-y1)
        // Приращение для конца строки
        dxy_r = c;

        // Обновляем значения стартовых точек
        xs = GET_BIN (x0, 0);
        xe = GET_BIN (x1, 0);

        // Закрашиваем нижнюю часть треугольника (она всегда плоская сверху)
        // Начальное значение y0 остается после рисования верхней части треугольника
        for(; y0 <= vert_y2; ++y0) {
            // Чертим линию от xs до xe для
            // заданного значения y цветом c
            // Draw_Line((int)(xs+0.5),(int)(xe+0.5),y,c);
            temp16 = xs + 128;
            x0 = GET_INT (temp16);
            temp16 = xe + 128;
            x1 = GET_INT (temp16);
            gen_h_line ();
            // Переходим к следующей строке
            xs += dxy_l;
            xe += dxy_r;
        }
    }
}

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

Давайте протестируем заливку произвольного треугольника:

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

Окружности

Представленный алгоритм рисования окружности тоже был разработан Брезенхэмом и работает довольно эффективно. Его легко доработать для рисования кругов (залитых окружностей). Моя адаптация алгоритма выглядит так:

// Функция рисования окружностей
// На входе координаты центры и радиус окружности
void gen_circle (void) {
    x = 0;
    y = radius;
    delta = 1 - 2 * radius;
    error = 0;

    while (y >= 0) {
        // Устанавливаем координаты и рисуем точки в восьми симметричных положениях
        X = x0 + x; Y = y0 + y; set_pixel_to_screen_buffer();
        X = x0 + x; Y = y0 - y; set_pixel_to_screen_buffer();
        X = x0 - x; Y = y0 + y; set_pixel_to_screen_buffer();
        X = x0 - x; Y = y0 - y; set_pixel_to_screen_buffer();
        X = x0 + y; Y = y0 + x; set_pixel_to_screen_buffer();
        X = x0 + y; Y = y0 - x; set_pixel_to_screen_buffer();
        X = x0 - y; Y = y0 + x; set_pixel_to_screen_buffer();
        X = x0 - y; Y = y0 - x; set_pixel_to_screen_buffer();

        error = 2 * (delta + y) - 1;
        if (delta < 0 && error <= 0) {
            x++;
            delta += 2 * x + 1;
            continue;
        }
        if (delta > 0 && error > 0) {
            y--;
            delta += 1 - 2 * y;
            continue;
        }
        x++;
        delta += 2 * (x - y);
        y--;
    }
}

Результат работы такого алгоритма выглядит примерно так:

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

Заключение

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

P. S. Кроме трехмерного движка я разрабатываю survival horror-игры для Dendy. В недавнем обновлении заменил все спрайты. Сейчас игра выглядит примерно так (в видео небольшой рассказ о истории разработки и показан актуальный геймплей):

Актуальную версию игры можно получить на странице со всеми моими Dendy-играми или в ТГ-канале (там я выкладываю обновления проектов).

P. P. S. Спасибо, что проголосовали в прошлой статье за создание трёхмерного движка. Это побудило меня взяться за оперативную разработку и было действительно весело ☺

Жду ваши вопросы и предложения по оптимизации в комментариях. Мне очень важна ваша обратная связь. Всем спасибо за внимание.

Ссылки

1. Портирование Dangerous Dave для NES/Dendy

2. Использование маппера UNROM при разработке игр для Dendy на языке Си

3. Алгоритм Брезенхэма

4. Числа с фиксированной запятой для NES/DENDY